Subject: [dtn-users] bundle fragmentation

From: Lana Black <[email-masked]>
Date: Sun, 24 Feb 2013 12:33:09 +0000

Hi,

I've been trying to find some information on how to deal with bundle
fragmentation in the docs and in the code itself, but no luck.

Should I just send bundle in pieces produced by
BundleProtocol::produce() with correct offset and len arguments, or use
FragmentManager either directly or through some other class?

With best regards.

---

From: Elwyn Davies <[email-masked]>
Date: Sun, 24 Feb 2013 14:30:56 +0000

Hi, Lana.
> fragmentation in the docs and in the code itself, but no luck.
The technical term is proactive fragmentation.  You can read a bit about
what DTN2 does about this in the functional spec document I wrote a
while ago.
http://www.n4c.eu/Download/n4c-wp2-023-dtn-infrastructure-fs-12.pdf

Section 4.6.4 and specifically item 167 talk about proactive
fragmentation. 
> FragmentManager either directly or through some other class?
As you will read in the document above there is functionality in DTN2 to
deal with proactive fragmentation but none of the CLs uses it (as far as
I could understand).  There is a method in the FragmentManager class
(servlib/bundling) called FragmentManager::proactively_fragment which
does the work of splitting up a bundle but nothing calls it.

(Probably) the point at which this should be called is in
BundleActions::queue_bundle where the link mtu is tested to decide if
the bundle could be sent on the link.  At present if the bundle is too
big for the configured link mtu, queue_bundle fails and the bundle is
just left pending until some other link can take it (I think - haven't
checked this logic).

I suspect that the code in proactively_fragment is essentially untested,
so no guarantees that it does the business correctly but it looks
reasonably sane.  However what *does* need to be done is to inform the
central loop that there are now alternative (fragment) bundles to
process.  Have a look at the code in
FragmentManager::try_to_reactively_fragment.  I think you will need to
get the new fragments into the BundleDaemon event loop by calling 
    // treat the new fragment as if it just arrived
    BundleDaemon::post_at_head(
        new BundleReceivedEvent(<new fragment bundle>, EVENTSRC_FRAGMENTATION));
for each fragment that is created.  

Have a look at the code in BundleDaemon::handle_bundle_transmitted that
deals with reactive fragmentation to decide how to deal with the
original 'whole' bundle. [HMM! Looking at the code, none of the places
where queue_bundle is called actually test the return code!  So if
queueing fails the code just ploughs on.  Not sure whether this matters
or not. Thats definitely FFS!]  THis is quite a complicated issue.
After thinking about it a bit, one should probably keep both the
fragmented bundle and the original, but add a flag to the bundle data
structure to say that it has already been fragmented once.. this might
even have to be a list of MTU's that it has been fragmented for so that
it isn't fragmented again at the same MTU (or larger).  Maybe just
keeping the smallest MTU is has been fragmented for would do.  Then it
would only be refragmented for even smaller MTUs (hopefully an unlikely
event).

Hope this helps a bit!

/Elwyn
PS
Implementing proactive fragmentatio would be useful more generally!
/E

> 
> With best regards.
> 
> _______________________________________________
> dtn-users mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/dtn-users

---

From: Amy Alford <[email-masked]>
Date: Sun, 24 Feb 2013 15:06:48 -0500

I've just been looking at this in order to test how the BSP code interacts
with fragmentation.

> for each fragment that is created.
This is essentially what I did (with the additional twist that I'm trying
to force fragmentation based on configuration settings in order to test
BSP), but I've had some difficulty getting the new bundles queued on links.
 Calling
BundleDaemon::post_at_head(new BundleReceivedEvent(*it,
EVENTSRC_FRAGMENTATION));
doesn't actually get the fragments sent.  Calling queue_bundle again isn't
an option because the xmit_blocks have already been created (and shouldn't
be prepare/generate/finalize'd again).  I ended up duplicating the code in
queue_bundle that actually queues the bundle on the link to queue the
fragments.  You also need to calculate the fragment lengths before you do
this.

The code in proactively fragment (and the version of create_fragment it
calls) is very buggy.
Issues I know of in create_fragment are:
- It needs to set the eid dictionary of the fragment based on the source
one.
- The payload length of the fragment is set by the PayloadBlockProcessor's
generate method, so this needs to be called on the copy of the payload
block in the new fragment.
- The last block flag needs to be adjusted, since the last block may have
changed (the first fragment only contains extension blocks that proceed the
payload, or have the REPLICATE_IN_EVERY_FRAGMENT flag set.
- The PrimaryBlockProcessor's generate_primary method needs to be called
again on the primary block in the new fragment in order to include the
fragment info (original block length, fragment offset) in the serialized
primary block.
In proactively_fragment:
- The code tracks extension blocks that should appear in the first fragment
versus extension blocks that should appear in all fragments.  It actually
needs to track three sets of blocks.  The first fragment is supposed to
contain all extension blocks that proceed the payload and any other
extension blocks that have the REPLICATE_IN_EVERY_FRAGMENT flag set.  The
last fragment contains all extension blocks that follow the payload, as
well as the extension blocks that should appear in all fragments.  All
other fragments contain only the extension blocks with the
REPLICATE_IN_EVERY_FRAGMENT flag set.  In particular, the current code
doesn't include the extension blocks that should be replicated in all
fragments in the first fragment.
- It may not be possible to create fragments less than max_length because
the length of the extension blocks required in the first or last fragment
may exceed that size.  proactively_fragment needs to check for this.
- The loop that calls create_fragment needs to decide whether to use the
first_frag_blocks, all_frag_blocks, or last_frag_blocks.

> would only be refragmented for even smaller MTUs (hopefully an unlikely
I deleted the original bundle, but this is probably insufficient.  An added
complication is that the next receiving node will both forward the
fragments and reassemble them and try to forward the reassembled bundle.  I
don't know if that's desirable or undesirable in various situations, but it
does cause a lot of duplication.
- Amy

---

From: Elwyn Davies <[email-masked]>
Date: Mon, 25 Feb 2013 17:02:40 +0000

Hi.. yes, the proactively_fragment routine has clearly never been used.

As Amy noted below it  has to consider the three cases - first, middle
and last.  The first and last have preordained minimum sizes given that
they have to have respectively all the pre-payload blocks for the
'first' case and all the REPLICATE blocks plus all the post-payload
blocks for the 'last' case so this may mean that fragmentation is
impossible for a given MTU.

There is a further complication that it may be dealing with
refragmentation if the bundle being fragmented is already a fragment.

Looking at the two create_fragment methods, the second one is
essentially useless (that's the one with 'link' in its parameters - it
should probably be deleted as it is pointless copying the xmit blocks as
Amy discovered) and the first one needs some refinement to make it work
properly. If we actually generated a new recv_blocks list (and possibly
an api_blocks list - but that is probably not vital) the new fragments
would get transmitted properly without needing to fudge queue_bundles
and also without deleteing the original full size bundle (I believe).
However I think recording the MTU size to which the bundle has been
fragmented would help as we could avoid refragmenting the whole bundle
if it got tested on the same  link again (as it might after a new link
opened). 

In particular create_fragment has to deal with the dictionary (as Amy
found out - neither create_fragment seems to do that).  It also has to
deal with the metadata block structures.  Also for extension blocks that
create local data structures (BPQ blocks and Metadata blocks at least)
the local data structures have to be recreated -and BPQ blocks don't
(yet) have a copy constructor.  WARNING: the append and push_back
routines used on the BlockInfoList (which are at heart std::list
classes) are very dangerous.  They call delete and copy routines if the
list gets extended and these can screw up extension blocks that use the
locals storage.  This can be worked around (and the creation speed
improved) by counting how many blocks have to go in the list and
pre-reserving enough entries for all the blocks that might go in - this
avoids lots of reallocation and copying. So I think that probably the
first create_fragment method needs significant updating and the second
one should be junked.

Its also more complex to deal with cases where extra blocks might be
added on a link specific basis.  proactively_fragment currently works
with the link's xmit_blocks list.  You win some and you lose some here.
The xmit_blocks list doesn't have the BP_Locals filled in as it is
irrelevant for transmission so the delete/copy problem doesn't hit you
BUT (more difficult - and highly relevant to Amy's work) there may be
link specific security or metadata blocks added to the list before the
fragmentation is done. This probably means that one should do a check to
see if the largest possible per link version can be fragmented for the
specified MTU.. this needs some discussion I think to see exactly how
this should be handled.

Oh, dear!  This sounds as if the traditional adage about cans of worms
applies:
"Never open a can of worms unless you have a larger can ready to put
them back into!"

/Elwyn

On Sun, 2013-02-24 at 15:06 -0500, Amy Alford wrote:
> I've just been looking at this in order to test how the BSP code
> interacts with fragmentation.
> 
>         (servlib/bundling) called
>         FragmentManager::proactively_fragment which
> This is essentially what I did (with the additional twist that I'm
> trying to force fragmentation based on configuration settings in order
> to test BSP), but I've had some difficulty getting the new bundles
> queued on links.  Calling
> doesn't actually get the fragments sent.  Calling queue_bundle again
> isn't an option because the xmit_blocks have already been created (and
> shouldn't be prepare/generate/finalize'd again).  I ended up
> duplicating the code in queue_bundle that actually queues the bundle
> on the link to queue the fragments.  You also need to calculate the
> fragment lengths before you do this.
> 
> 
> The code in proactively fragment (and the version of create_fragment
> it calls) is very buggy.  
> - It needs to set the eid dictionary of the fragment based on the
> source one.
> - The payload length of the fragment is set by the
> PayloadBlockProcessor's generate method, so this needs to be called on
> the copy of the payload block in the new fragment.
> - The last block flag needs to be adjusted, since the last block may
> have changed (the first fragment only contains extension blocks that
> proceed the payload, or have the REPLICATE_IN_EVERY_FRAGMENT flag set.
> - The PrimaryBlockProcessor's generate_primary method needs to be
> called again on the primary block in the new fragment in order to
> include the fragment info (original block length, fragment offset) in
> the serialized primary block.
> In proactively_fragment:
> - The code tracks extension blocks that should appear in the first
> fragment versus extension blocks that should appear in all fragments.
>  It actually needs to track three sets of blocks.  The first fragment
> is supposed to contain all extension blocks that proceed the payload
> and any other extension blocks that have the
> REPLICATE_IN_EVERY_FRAGMENT flag set.  The last fragment contains all
> extension blocks that follow the payload, as well as the extension
> blocks that should appear in all fragments.  All other fragments
> contain only the extension blocks with the REPLICATE_IN_EVERY_FRAGMENT
> flag set.  In particular, the current code doesn't include the
> extension blocks that should be replicated in all fragments in the
> first fragment.
> - It may not be possible to create fragments less than max_length
> because the length of the extension blocks required in the first or
> last fragment may exceed that size.  proactively_fragment needs to
> check for this.
> - The loop that calls create_fragment needs to decide whether to use
> the first_frag_blocks, all_frag_blocks, or last_frag_blocks.  
>  
>         
>         Have a look at the code in
>         BundleDaemon::handle_bundle_transmitted that
> I deleted the original bundle, but this is probably insufficient.  An
> added complication is that the next receiving node will both forward
> the fragments and reassemble them and try to forward the reassembled
> bundle.  I don't know if that's desirable or undesirable in various
> situations, but it does cause a lot of duplication.
> - Amy

---

From: Amy Alford <[email-masked]>
Date: Mon, 25 Feb 2013 20:21:12 -0500

Why is it pointless to copy the xmit_blocks?  They certainly need patching
up, but I've been able to do that AFAICT.  It ends up behaving as though
you sent the original bundle on the link, then the next hop fragmented it.
 Whether that's what you want for BSP (as opposed to fragmenting then
adding BSP blocks), I don't know.

---

From: Elwyn Davies <[email-masked]>
Date: Tue, 26 Feb 2013 12:33:56 +0000

Hi, Amy.

On Mon, 2013-02-25 at 20:21 -0500, Amy Alford wrote:
> 
> Why is it pointless to copy the xmit_blocks?  They certainly need
> patching up, but I've been able to do that AFAICT.  It ends up
> behaving as though you sent the original bundle on the link, then the
> next hop fragmented it.  
Perhaps pointless was the wrong word. The problem is that the Bundle
structure that is created for each fragment is not properly 'valid'.
Things will probably work out as long as it remains on the link for
which the xmit blocks were created, but things will a.s. go very pear
shaped if the daemon is shutdown and restarted because the bundle, as
stored in persistent storage, will have no blocks since the storage is
driven from recv_blocks and api_blocks which remain empty.  The
resulting bundle read back will be flagged as invalid because it has no
primary or payload blocks - at best it will be flagged and discarded -
but there is a good chance it will trigger an assert somewhere.  A
similar problem will occur if a new link is opened along which the
fragment bundle could be routed - reroute_all_blocks will be called and
the fragments may end up on other links. An attempt to create
xmit_blocks for this new link will also barf. The same will happen if
the the link is closed down and/or restarted.

> adding BSP blocks), I don't know.
Right.. that depends on what sort of blocks you were adding.  The
hop-by-hop integrity checks might have to be different - I don't know
whether BAB blocks for hop-by-hop would be verified at the next security
destination before or after reassembly (or indeed whether fragmentation
of such a bundle would be allowed).

Generated metadata blocks could also be a problem although that is more
of a theoretical problem at the moment because the generated metadata
block capability is not really used at present (the BPQ stuff that I am
working on is nearest to it AFAICS as it generates bundles in response
to queries if it has a match in the bundle cache and these have metadata
blocks).

---

From: Elwyn Davies <[email-masked]>
Date: Tue, 26 Feb 2013 19:58:44 +0000

PS
If the recv_blocks were copied instead of the xmit_blocks, the
dictionary takes care of itself.

/E