Subject: [Lwip] Routing Over 6lowpan fragments and collisions

From: "Angelo P. Castellani" <[email-masked]>
Date: Fri, 29 Jul 2011 10:02:43 -0400

As asked during today's WG presentation about the guidance document, I
refer my comment on the list.

The technique employed relays on the fact that on nodes at hop number
higher that 2, there will be no collision on the datagram_tag field.

At the first hop you can assume, with a good approximation, that if
you pair the datagram_tag with the L2 source of the packet you should
have no collisions on that field, this doesn't holds anymore at later
hops.

In the jabber room, Carsten suggested to circumvent this problem by
changing the datagram_tag at each hop.

In my opinion, that will solve the problem in a basic scenario, but
poses an added load on the very limited RAM of these devices.

Moreover I can imagine a more advanced scenario where route-over
routers load-balance the packets across different routes; in this
scenario the reassembly at the end of the 6lowpan network will not
succeed, if fragments have been routed across different routes in the
network.

At the end of the day, in my opinion, this optimization could be
useful in some environment, but you have to carefully review its
requirements before implementing it.

Best,
Angelo

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 29 Jul 2011 16:49:55 +0200

> higher that 2, there will be no collision on the datagram_tag field.

The optimization relies on the same basic assumptions that L2 fragment reassembly relies on in general.

> have no collisions on that field,

If you can't rely on that, L2 fragment reassembly does not work right in the first place.
The optimization does not change that.

> this doesn't holds anymore at later
> hops.
> 

You have to choose a datagram_tag that fits the new L2 source, of course, because that is an essential part of reassemble-forward-fragment already.
The optimization does not change that.

> poses an added load on the very limited RAM of these devices.

The outgoing datagram_tag needs to be chosen with the first fragment (as always) and kept as part of the virtual reassembly buffer.
(That should be indeed be mentioned in the text, thank you for the hint.)

> succeed, if fragments have been routed across different routes in the

Yes.  This is not changed by doing the optimization (actually, the optimization may make some more fragments going forward where complete reassembly is then not possible).

Route-over selects an (outgoing interface/source address and) next hop for the packet (i.e., all of its fragments).
Reassemble-forward-fragment sends out all fragments on that interface.
The optimization will have to, too.
(Which is obvious, as it can't rely on the next hop to have the optimization.)
Again, you'll have to keep that state (interface/next hop) as part of the virtual reassembly buffer.

> requirements before implementing it.

There are no additional requirements that I know at this point.

Gruesse, Carsten

---

From: "Angelo P. Castellani" <[email-masked]>
Date: Fri, 29 Jul 2011 14:32:05 -0400

> (That should be indeed be mentioned in the text, thank you for the hint.)

OK, if you assume that you change datagram_tag at each hop one problem
is solved. However I'm not that confortable on making L2.5 fragments
being routed at L3:

- you will have no TTL, I hope that your fragments will find no loop..
- you can route only if and after you receive the first fragment
- you have to handle a timeout related to the fact that you can never
receive the first fragment
- a single fragment loss leads to lose of all the fragments

> Again, you'll have to keep that state (interface/next hop) as part of the virtual reassembly buffer.

OK, however all this state should be clarified in the text. Neither
the changing of datagram_tag, and to fix the output IF for a flow can
be found there.

Moreover the router should run also some complex algorithm (and the
required state) to understand that it has routed all the fragments of
an IP packet, or select an appropriate timeout to purge this cache.

At the end I'm not fully convinced that all the complexity we are
introducing is worth avoiding the reassemble-forward-fragment
processing.

Best,
Angelo

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 29 Jul 2011 21:08:31 +0200

> - you will have no TTL, I hope that your fragments will find no loop..

Good point.  But note that the non-initial fragments only continue to circulate while the initial fragment is in place.

> - you can route only if and after you receive the first fragment

Yes.  We could add the obvious recommendation to send the first fragment first (and the last fragment last, see below).
(A constrained router will be well-advised to *not* create a runt buffer if that is not done -- this is probably the most important take-home message for those who want to interoperate with very constrained implementations.)

> receive the first fragment

As with reassembly.  No change.

> - a single fragment loss leads to lose of all the fragments

As with reassembly.  No change.
(Fragmentation is bad -- optimizing its implementation does not change that.)

> the changing of datagram_tag, and to fix the output IF for a flow can

Right, all this should be added for those who are not aware of what reassemble-forward-fragment entails.

> an IP packet, or select an appropriate timeout to purge this cache.

I wrote: "Runt buffers should time out like full reassembly buffers, and may
either keep a map of fragments forwarded or they may simply be removed
upon forwarding the final fragment, assuming that no out-of-order
fragments will follow."

The latter is a nice optimization.

> introducing is worth avoiding the reassemble-forward-fragment

That is of course for each implementer to decide.

I'd say: Do this if buffer memory is limited, in particular if you don't have the space for multiple reassembly buffers carrying the interleaved fragments of multiple large IP packets that you happen to receive concurrently.
Note that obviously there is no way to completely avoid the creation of buffers, as the forwarded fragment may compete on the same interface with the next incoming fragment -- if the latter happens to win, you still have to buffer the outgoing fragment (this time outside the reassembly buffer, it's in your output queue instead).  That potential for added media contention is actually the only negative I know about this optimization -- reassemble-forward-fragment nicely sequences the receive phase before the send phase.

Again, thank you for bringing all this up -- this discussion definitely will help improving the text for -01.

Gruesse, Carsten