Subject: Re: [dtn-users] bundle fragmentation

From: Amy Alford <[email-masked]>
Date: Sat, 2 Mar 2013 18:23:07 -0500

Makes sense.  I modified my implementation to use recv_blocks, and that did
make for a much cleaner solution.

The one glaring issue is predicting the size of the generated extension
blocks.  Currently, I'm letting the user configure the maximum length of a
payload, and fragmenting based on that.  That works beautifully for my
testing purposes, but is obviously unhelpful if the concern is MTUs.

There are a whole bunch of cases to consider in predicting the size of the
extension blocks:
1) Received extension blocks which may be copied unchanged, or
expanded/reduced by their block processors.
2) Extension blocks created by registered block processors when their
prepare methods are called to give them a chance to add blocks.
3) Extension Security Blocks encapsulating either of the above.
4) Age blocks, metadata blocks, PIB/PCB/BAB, and anything else which has
its own hooks in BundleProtocol::prepare_out_blocks

Existing BSP ciphersuites can predict a maximum block size.  PIB/PCB/ESB
need to know the security src/destination (which isn't link dependent) to
predict the size of the CMS formatted security result (which may contain
large amounts of data related to the security certificates).  BAB doesn't
use CMS, so while it may change security src/dest based on the link, the
security result size won't change based on this.  It is possible that
future ciphersuites will need to know the link in order to provide maximum
block sizes.

I'm thinking the best solution is to add a maximum_block_size method to
BlockProcessors, which takes a bundle and optionally a received block.  ESB
(which encapsulates another block) will probably need some special handling.

On Tue, Feb 26, 2013 at 7:33 AM, Elwyn Davies <[email-masked]> wrote:

> 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.
>
> > Whether that's what you want for BSP (as opposed to fragmenting then
> > 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).
> >
> > On Mon, Feb 25, 2013 at 12:02 PM, Elwyn Davies <[email-masked]>
> > wrote:
> >         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).
> >
>
>

---

From: Elwyn Davies <[email-masked]>
Date: Sun, 03 Mar 2013 02:12:01 +0000

Hi.

I was wondering how you were getting on with this!

Is it not the case that at the point you find out you need to do
proactive fragmentation that you have a set of xmit blocks set up?  

I don't think that any of these blocks will get bigger if you reduce the
size of the payload (not certain about the security blocks but can't see
how that would be likely).  So I would have thought you could use the
xmit block sizes to decide (firstly) whether fragmentation is possible
and (if it is) how to split up the payload.

However, a horrible thought just struck me... The security blocks with a
before and after part if fragmentation is taking place at a security
source... How do these calculate the after part in a fragmented bundle?
This needs the whole payload.  May have to have a pointer to the
original bundle or some other fudge. Yuck!  A nasty horrible trick I
just thought up would be to send the 'securitized' bundle to yourself in
such a way that the node is no longer the security source.  The blocks
then all end up on the recv_blocks list and just have to be split up by
the fragmentation rather needing regeneration.  Super-yuck!!

OTOH if the fragmenting node is not a security source, then the two part
security blocks can't be altered so the smit blocks solution works I
think.
Some comments on the changing block size question below...

Regards,
Elwyn 

On Sat, 2013-03-02 at 18:23 -0500, Amy Alford wrote:
> Makes sense.  I modified my implementation to use recv_blocks, and
> that did make for a much cleaner solution.  
> 
> 
> The one glaring issue is predicting the size of the generated
> extension blocks.  Currently, I'm letting the user configure the
> maximum length of a payload, and fragmenting based on that.  That
> works beautifully for my testing purposes, but is obviously unhelpful
> if the concern is MTUs.  
> 
> 
> There are a whole bunch of cases to consider in predicting the size of
> the extension blocks:
As far as I know changes can't happen apart possibly for the age block
(have to check that one).
> prepare methods are called to give them a chance to add blocks.
Again there aren't any examples AFAIK apart from the two part security
blocks.
You could get (in theory - but as far as I know nobody has found a use
for it) extra generated metadata blocks but you'd know about those
because (A) they have to be in the generated metadata block list for the
link when the prepare method is called and (B) you's have seen them in
the xmit blocks list for the whole bundle.
> 3) Extension Security Blocks encapsulating either of the above.
(see previous comment)
> 4) Age blocks, metadata blocks, PIB/PCB/BAB, and anything else which
> has its own hooks in BundleProtocol::prepare_out_blocks
It might be legitimate to force 'don't fragment' for any of these cases
that was really serious, but I don't think in practice its a big deal.
I think the xmit blocks list is still your friend here.
> 
> 
> Existing BSP ciphersuites can predict a maximum block size.
>  PIB/PCB/ESB need to know the security src/destination (which isn't
> link dependent) to predict the size of the CMS formatted security
> result (which may contain large amounts of data related to the
> security certificates).  BAB doesn't use CMS, so while it may change
> security src/dest based on the link, the security result size won't
> change based on this.  It is possible that future ciphersuites will
> need to know the link in order to provide maximum block sizes.
> 
> 
> I'm thinking the best solution is to add a maximum_block_size method
> to BlockProcessors, which takes a bundle and optionally a received
> block.  ESB (which encapsulates another block) will probably need some
> special handling.
> 
> 
> 
>

---

From: Elwyn Davies <[email-masked]>
Date: Sun, 03 Mar 2013 11:24:23 +0000

PS.

After sleeping on it, I realized that there is still a snag if somebody
eventually gets around to using the generated metadata blocks on a per
link basis - and also the previous hop block which is also essentially a
per link (type) but would have to go with every fragment on a link type
that needed it.

I have a horrible suspiscion that this is just rerunning all the
discussion there has been about IPv6 and tunnel MTUs with a slightly
different set of parameters.

I guess the best one can do is to leave a bit of slack in every fragment
to cater for (particularly) Previous Hop Blocks.

Thoughts?

All this stuff is certainly something that needs to feed into the
RFC5050bis discussion that we are supposed to be having in DTNRG.

Regards,
Elwyn

Hi.

Regards,
Elwyn 

(see previous comment)
>         >         if it got tested on the same  link again (as it

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

---

From: Amy Alford <[email-masked]>
Date: Mon, 4 Mar 2013 20:02:27 -0500

> and (if it is) how to split up the payload.
Reducing the payload size won't increase any of the existing security
blocks's sizes.  Changing which link you send the bundle on may.  So, I
guess the worst case there is that the bundle is fragmented repeatedly at
the node.

> the fragmentation rather needing regeneration.  Super-yuck!!
I think this isn't an issue in practice.  Adding BAB either before or after
fragmentation is acceptable.  If we add BAB after fragmentation (which is
what naturally happens if we use the recv_blocks in fragmentation), then it
all works cleanly.

> (have to check that one).
We have an experimental extension block that accumulates data over time.
 Not only does it get longer at each node, it gets longer as it sits at a
node (meaning that if it's sent out two links, the version that goes out
the second link may be longer).

> Again there aren't any examples AFAIK apart from the two part security

The two part security blocks are actually added elsewhere.  The security
blocks need to be added after everything else, so they have their own hooks
in BundleProtocol::prepare_blocks

---

From: Amy Alford <[email-masked]>
Date: Fri, 8 Mar 2013 15:43:02 -0500

Am I correct in my read of 5050 section 5.8 and 5.9: there are no
requirements on how extension blocks are handled during fragment
reassembly? In other words, while it would be a horrible idea, a conforming
implementation could simply drop all extension blocks during reassembly.

Assuming no extension blocks are added or modified after fragmentation
occurs, the sensible behavior is obvious.

However, BSP can add PIB blocks after fragmentation.  In this case, I can't
see how to reconstruct what PIB blocks already existed at the time a given
PIB block was added (which is important, because we hash over those
blocks).
- Amy

---

From: Elwyn Davies <[email-masked]>
Date: Sat, 09 Mar 2013 00:57:39 +0000

Hi Amy.

I think you just prised the lid off a large can of worms.
Better go find the larger can to put them back in :-(

On Fri, 2013-03-08 at 15:43 -0500, Amy Alford wrote:
> reassembly? 
Well, reading the specification from a "let's do the absolute minimum"
perspective, you could come to that conclusion.  There is indeed lots of
stuff about explicitly dropping blocks .. but it doesn't say anything
about insisting on keeping blocks if aren't explicitly dropped. 
> In other words, while it would be a horrible idea, a conforming
Hmm! I feel a rather large erratum coming on here!

The stuff I have just spent several months fiddling with would be
completely wrecked if this was a valid interprestation.  I want a BPQ
block and one or two Metadata blocks carried e2e please and no
arguments.

Let's think briefly about custody.. I inject a bundle like the one I
just mentioned with extension and metadata blocks and it asks for
custody transfer.  So it arrives at a node which says: "yes, I'll take
custody"... so what has it committed itself to taking custody of????

> occurs, the sensible behavior is obvious. 
Certainly I would like to get the set of blocks I injected at the source
back at the destination less possibly ones that couldn't be processed.
Of course having a block that has been hashed over but can't be
processed at some intemediate node might get you into trouble.. there
are weasel words in the BSP about this.  
>  
> 
> 
> However, BSP can add PIB blocks after fragmentation.  In this case, I
> can't see how to reconstruct what PIB blocks already existed at the
> time a given PIB block was added (which is important, because we hash
> over those blocks). 
And in principle, any node is free to add on metadata blocks and take
them away. However going back to the PIB Block issue:

I don't think the PIB stuff is a problem (assuming the implementation
conforms to the BSP spec) but I may not understand the problem.  

- Any PIB block from before a fragmentation will only be in the first
fragment of the block that was fragmented; its corresponding correlator
(if it has one) will be in the last fragment.  If there are intermediate
fragments they won't have PIBs (but might have PCBs if they have
replicate in all blocks set)
- There's a stack of PIB blocks with associated security destinations
and if the PIB applies to a part of payload it is supposed to say what
part (I think - s2.3 of BSP).
- When you reach a security destination (maybe the final destination),
you start unwinding the stack in each bundle.  Deal with the BAB in each
fragment first.  Then for each fragment that has an PIB as its first
security block and has the current node as current 'outside' (top of the
tack) security destination, look at the range of payload bytes the PIB
covers.  Do whatever reassembly is implied by this (may have to be
postponed if not all the bits have arrived yet) putting together the
fragments needed to make up the piece of payload protected by the PIB.
Reconstruct the bundle that was fragmented after this PIB was put in
place (which may be a fragment of the larger bundle.) Check the PIB and
its correlator and then discard them (or the whole bundle if the check
fails).  Repeat the exercise for all the fragments in turn.  Do any PCB
and ESB actions for this security destination.  Then recurse up the
stack of PIBs if relevent starting from the lowest offset fragemnt each
time.

That's pretty complex and tedious but I think it works.

But I am wondering if we need a Metadata block to say whet extension
blocks (and other Metadata blocks were in the original bundle plus a
flag in the primary block to say it is there??  That way custody would
know what it was taking charge of.

Thoughts?

/Elwyn

---

From: Amy Alford <[email-masked]>
Date: Fri, 15 Mar 2013 20:13:21 -0400

I can't prove to myself that you can't successfully do incremental
defragmentation using the BSP info to decide which subset of fragments to
reassemble.  However, it would require major reworking of DTN2 since you'd
have to use the BSP blocks to decide which fragments to recombine.

I was hoping that you could reassemble the bundle and use the heuristic
that PIB blocks always applied to other blocks whose range is a superset of
theirs and who start at the same offset.  Unfortunately, if a bundle is
fragmented differently along different paths, this isn't true.

I have a crazy scenario I'm trying to untangle.

A bundle of 100 bytes is created.  It's fragmented into bytes 0-50 and
50-100 and independently into 0-25 and 25-100.  Some node adds PIB to the
0-50 fragment, so that fragment is now (PIB 0-50)(0-50).  Another node
fragments this fragment into (PIB 0-50)(0-25) and (25-50).  Another node
adds PIB to the first of these, yielding (PIB 0-25)(PIB 0-50)(0-25).  Some
other node also adds PIB to the original unadorned 0-25 giving us (PIB
0-25)(0-25).

Now, I have PIB 0-50 and PIB 0-25 blocks floating around when I reassemble.
 One PIB 0-25 covers one PIB 0-50, but the other PIB 0-25 does not relate
to any PIB 0-50s.

So, this leaves us needing to use your idea of partial reassembly. Which
means making really substantial changes to the validation/fragment
reassembly code since there's no conceptual idea of a "subfragment" in 5050
and so we need to try to use the extension blocks to infer a subfragment
structure.

---

From: Elwyn Davies <[email-masked]>
Date: Mon, 18 Mar 2013 07:42:58 +0000

Hi.

I think you are part of the way there, at least for some cases in your
second paragraph...

Let's consider the simple case first.. assume the security destination
for all of these PIBs is the final bundle destination ao the reassembly
is being done at the final destination and so all the fragments that are
going to arrive will arrive there.

Let's also initially assume that there is no encryption, just PIBs.  

One way of handling this seems to be:
- ignore the PIBs for a moment and reassemble the payload.  Assuming we
have a full set of fragments, we can put the whole payload back
together.  If there are no overlaps and no gaps then this is
straightforward. 

- Now, if I understand correctly, the PIB(s) are still applicable to
whatever chunks of payload they were applied to in the first place.
Thus, you can look at the PIB and take the chunk of payload that it
covered and check whether the hash is satisfied. Furthermore, assuming
that the PIB is a good strong one, we can optimize this.  If a PIB
covers a range of octets that are fully covered by some other PIB, we
can just ignore it - checking the covering one should be good enough.
So if there is a PIB for the whole payload, then we can just ignore any
others that it has accumulated.

So much for the easy case... some more awkward cases:

- In the case above let's suppose that all is not well.  There are now
some overlapping fragments and their contents don't match in the
overlap.  What do we do?  I just checked the existing code in
FragmentManager.cc and FragmentState.cc and it appears that we don't
compare the content - we just overwrite with later arriving overlapping
fragments.  So as it stands, all we can do is check the PIB(s) and if
any of them fails then junk the bundle and all its fragments.  I think
that the Sainted Michael originally had a more cunning plan because the
fragmented payload was originally supposed to be represented by a sparse
bitmap (there are traces of this still in the code) and this would have
allowed us to check more easily if there was an overlap and do something
cleverer like taking the content from a PIBbed fragment rather than an
unPIBbed one or keeping both copies and seeing if either satisfied the
PIB.  In practice this is probably far too complicated and the status
quo may be good enough.  

- If the security destination is not the final destination, then we can
use the partly reassembled payload which we get for free to see if the
whole segment protected by the fragment is present.  There is no need to
actually defragment the bundle, BUT you have to hold unchecked fragments
off the pending queue until the whole segment has arrived and can be
checked - the router code shouldn't try to forward these fragments until
they have been checked.

In all these cases checking the PIB(s) has to be postponed until the
whole segment concerned has arrived.  I'm not sure how this ties in with
the BSP code as it stands but you could make a version of
FragmentState::check_completed which looked to see if you had the whole
of the segment protected by a PIB.  In the case of the final destination
its easy enough to postpone the checks until the whole bundle has
arrived.  For intermediate security destinations life is more
complicated: There is a nasty corner case where a corrupted overlapping
fragment arrives after you have checked the PIB.  It definitely
indicates that you ought to check for inconsistent data in overlapping
fragments but doing something other than throwing away the whole
bundle/set of fragments is going to be hideously complicated, and with
the intermediate security destination you may already have forwarded
correctly checked fragments (actually this is probably good news
provided you know you have checked the existing fragments - you can just
throw away the incoming one).

What I am not up to speed on is how all this interacts with encrypted
fragments that are not the whole bundle.  Presumably you have a similar
problem in that you have to postpone decryption.. but on the other hand
the accumulated payload is just what you need to operate on.

Hope this all make some sort of sense.

/Elwyn 

On Fri, 2013-03-15 at 20:13 -0400, Amy Alford wrote:
> defragmentation using the BSP info to decide which subset of fragments
> to reassemble.  However, it would require major reworking of DTN2
> since you'd have to use the BSP blocks to decide which fragments to
> recombine.
> 
> 
> I was hoping that you could reassemble the bundle and use the
> heuristic that PIB blocks always applied to other blocks whose range
> is a superset of theirs and who start at the same offset.
>  Unfortunately, if a bundle is fragmented differently along different
> paths, this isn't true.
> 
> 
> 50-100 and independently into 0-25 and 25-100.  Some node adds PIB to
> the 0-50 fragment, so that fragment is now (PIB 0-50)(0-50).  Another
> node fragments this fragment into (PIB 0-50)(0-25) and (25-50).
>  Another node adds PIB to the first of these, yielding (PIB 0-25)(PIB
> 0-50)(0-25).  Some other node also adds PIB to the original unadorned
> 0-25 giving us (PIB 0-25)(0-25).
> 
> 
> Now, I have PIB 0-50 and PIB 0-25 blocks floating around when I
> reassemble.  One PIB 0-25 covers one PIB 0-50, but the other PIB 0-25
> does not relate to any PIB 0-50s.  
> 
> 
> So, this leaves us needing to use your idea of partial reassembly.
> Which means making really substantial changes to the
> validation/fragment reassembly code since there's no conceptual idea
> of a "subfragment" in 5050 and so we need to try to use the extension
> blocks to infer a subfragment structure.
> 
> 
> 
>         stack of PIBs if relevent starting from the lowest offset
>         fragment each
>         time.
>

---

From: Amy Alford <[email-masked]>
Date: Tue, 19 Mar 2013 14:09:35 -0400

I think I explained the situation badly.  The default PIB ciphersuite
doesn't just hash and sign the payload.  It also hashes most of the primary
block and any existing PIB or PCB blocks.  So, in order to validate a PIB
block, I need to know what PIB/PCB blocks were attached to the bundle at
the time this one was added.  BSP uses the order of PIB/PCB blocks to
determine this.

If you reassemble the bundle before validating, you need some way to figure
out which PIB blocks hash over each other.  I haven't thought of a good way
to do this yet.  In particular, if an intermediate node reassembles a
bundle, I don't think we have enough information left to validate the PIB
blocks.  The example I gave demonstrates this.  If I'm wrong and there's
some way to infer the order of BSP blocks in the fragments from the
reassembled bundle, that would be the easy solution.

OTOH, if all the reassembling nodes are BSP aware, I think it's doable, but
it isn't elegant.  The individual fragments carry the most information
about the order in which BSP fragments were added.  Those fragments can
only be validated with access to the payload (and possibly other fragments
if you have a two block PIB ciphersuite).  So, reassembly and validation
probably have to happen in a few passes (reassemble the payload, validate
the fragments, confirm that the validated fragments let you reassemble the
whole payload).  There are probably additional headaches if a node receives
a set of fragments that allow it to reassemble the whole payload, but is
missing a fragment needed to validate another fragment (you receive only
one of a pair of fragments containing correlated PIB blocks in a two block
PIB ciphersuite).