Subject: [6lowpan] making progress on fragmentation

From: Richard Kelsey <[email-masked]>
Date: Tue, 18 Aug 2009 08:26:50 -0400

I would like to work towards the adoption of Pascal's
fragmentation draft (draft-thubert-6lowpan-simple-fragment-
recovery) as a working group document.  Partly for the
reason giving in the draft, that retries are needed to make
delivery of large packets reliable, but also because retries
are needed to make delivery of *small* packets reliable.

With Ember's earlier, non-IP stacks, we have found that
customers expect IP-like reliability even from non-IP
protocols.  We have gotten reliable delivery (as reliable as
UDP packets in the Internet, say) on a radio mesh only by
repairing routes without dropping data packets.

The hard part of route repair is knowing when to do it.  The
most reliabile way is to use end-to-end ACKs within the
mesh.  Using NACKs would be more efficient that ACKs, but
these are lossy networks and NACKs are even less reliable
than data packets, because they only get sent when something
is already broken.

When a route breaks, we get the following sequence of
events:

  1. send a packet
  2. fail to receive an ACK
  3. update the route
  4. resend the packet
  
This has allowed us to get end-to-end mesh reliability
approaching that expected from IP links.  The usual
higher-level IP retry mechanisms can take over from there.

(Sending fragments multiple hops in a route-over network
will require some kind of label switching.  That will need
to be discussed over in ROLL.)

How close are we to consensus on Pascal's draft?  What
needs to be fixed/improved/removed?

                               -Richard Kelsey

---

From: Carsten Bormann <[email-masked]>
Date: Tue, 18 Aug 2009 15:26:30 +0200

Richard,

thank you for seconding Pascal's draft.

We have had multiple discussions of the fragment recovery drafts in  
IETF meetings.
Each time, we found some aspect some of us didn't like, and then  
Pascal submitted an updated version solving that problem.
The only thing that got considerable push-back this time was that the  
draft shouldn't try to deprecate 4944's fragment headers.
I think this is a statement that could easily be taken out in a  
working group draft submission.
(Of course, any other technical wrinkles can be ironed out during the  
period the document is a WG draft.)

So I would like to take the opportunity to ask here on the mailing  
list whether we should adopt
http://tools.ietf.org/html/draft-thubert-6lowpan-simple-fragment-recovery-06
(with the abovementioned change) as a working group document.

-->
   If you want to advance this draft, please indicate your support on  
the mailing list.
   If you think this is a bad idea, please say so, too.
   (I would like to receive responses by this Friday, Aug 21, as I'm  
going on vacation after that.)

Note that we also have to hear from our AD on this item, as it is not  
formally on our charter.
A year ago, Mark Townsley gave us some form of go ahead when we  
discussed whether we should be delaying the charter for adding this as  
a work item.
He said that waiting wasn't necessary, and we were free to start work.
http://www.mail-archive.com/[email-masked]/msg01114.html
Still, we would need to add a line item under the deliverables, and  
our new AD would have to concur -- which is probably easiest after the  
yays and nays.

Gruesse, Carsten

---

From: Ralph Droms <[email-masked]>
Date: Tue, 18 Aug 2009 09:37:03 -0400

I've had a couple of off-line discussions; now seems like a good time  
to ask the WG: does anyone have empirical evidence about the impact of  
fragment loss in 802.15.4 networks that would motivate the need for  
reliable fragment delivery?

- Ralph

On Aug 18, 2009, at 9:26 AM 8/18/09, Carsten Bormann wrote:

> The only thing that got considerable push-back this time was that  
> the draft shouldn't try to deprecate 4944's fragment headers.
> (Of course, any other technical wrinkles can be ironed out during  
> the period the document is a WG draft.)
>
> Note that we also have to hear from our AD on this item, as it is  
> not formally on our charter.
> discussed whether we should be delaying the charter for adding this  
> as a work item.
> our new AD would have to concur -- which is probably easiest after  
> the yays and nays.
>
> Gruesse, Carsten
>
> _______________________________________________
> 6lowpan mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/6lowpan

---

From: Carsten Bormann <[email-masked]>
Date: Tue, 18 Aug 2009 15:54:05 +0200

> to be discussed over in ROLL.)

To document what everyone has been saying on the hallway:

If you think strictly in layers, you have to reassemble the packet on  
each L2/L3 boundary, and then re-fragment on each L3/L2 boundary.
However, the following optimization is obvious to anyone skilled in  
the art of layer violation:

1) Upon receiving an initial fragment for a tuple (SA, DA, datagram  
size, datagram tag), if there is no reassembly buffer, do not create  
an actual full reassembly buffer, but just a rump data structure that  
records the IP addresses in that first fragment as well as the  
coverage of the packet space by actual data forwarded.  Forward (or  
deliver locally) the fragment based on the IP addresses.
2) Upon receiving a non-initial fragment, if there already is a rump  
reassembly buffer for the tuple, forward based on that, and record  
coverage.  Otherwise, create a full reassembly buffer with the data  
received -- it might be for you!
3) Upon receiving an initial fragment for a tuple that has a full  
reassembly buffer, (if not for local delivery) forward the initial  
fragment, record the IP addresses (and the coverage).  Then pump out  
the data in the reassembly buffer as bandwidth permits.

Each time a (full or rump) reassembly buffer gets full coverage, drop  
it (or keep it some short additional amount of time to account for  
late-coming duplicates).

Of course, the uncertainty when to drop reassembly buffers remains,  
but at least you don't have to keep the actual data (as soon as you  
have the initial fragment).  The way the (lack of) information works  
resequences on every hop, so the likelihood of initial fragments  
missing is limited.

What we didn't provide in 4944 was a way to indicate "It's for you" in  
each fragment.  The last-hop sender may not always know, but when it  
does, having that information might help with buffer management.

Gruesse, Carsten

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 18 Aug 2009 10:37:10 -0400

From: Carsten Bormann <[email-masked]>
   Date: Tue, 18 Aug 2009 15:54:05 +0200
   Cc: [email-masked]

We clearly hang out in different hallways :-).

   [... store routing data from the initial fragment for use
    in forwarding subsequent ones ...]

The difficulty is that the various fragments may easily take
different paths through the mesh.  Even if no route changes
occur, there may still be multiple paths.  The current RPL
draft, for example, allows a router to maintain multiple
next hops for a given DAG root.  A router that alternates
between two next hops for load balancing is going to be a
bit of a problem.
                                -Richard Kelsey

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 18 Aug 2009 11:02:08 -0400

In responding to Carsten, I wrote:

Please ignore all that.  I am clearly not skilled in
the art of layer violation and will need to think
about this some more.
                          -Richard Kelsey

---

From: Carsten Bormann <[email-masked]>
Date: Tue, 18 Aug 2009 17:05:32 +0200

On Aug 18, 2009, at 16:37, Richard Kelsey wrote:

> A router that alternates

Indeed; so the procedure I have described would benefit from recording  
the next hop chosen in the rump reassembly buffer.
(Another obvious hack would be to send the initial fragment to both/ 
all next hops; unfortunately the obvious optimization of only sending  
the actual data to one of them and just the first bytes with the  
addresses to other other ones is outlawed by 4944, page 12,  
penultimate paragraph.)

Gruesse, Carsten

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 18 Aug 2009 17:26:46 +0200

Hi Carsten

You right. But please also include mesh under in your reasoning; I initially crafted this work in the light of the work at ISA100.11a, that is mesh under and thus needs end to end recovery.

Pascal

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On Behalf Of Carsten Bormann
>Sent: mardi 18 août 2009 15:54
>To: Richard Kelsey
>Cc: [email-masked]
>Subject: Re: [6lowpan] making progress on fragmentation
>

---

From: Carsten Bormann <[email-masked]>
Date: Tue, 18 Aug 2009 18:27:21 +0200

On Aug 18, 2009, at 15:37, Ralph Droms wrote:

> does anyone have empirical evidence about the impact of fragment  
> loss in 802.15.4 networks that would motivate the need for reliable  
> fragment delivery?

(no WG chair hat:)

I can't answer that question.

But it is important to describe the applicability of http://tools.ietf.org/html/draft-thubert-6lowpan-simple-fragment-recovery-06 
  some more.

As it stands, the draft addresses the mesh-under case.  There is  
little gain for the hop-by-hop fragmentation/reassembly implied by  
route-over; it is also not clear how to apply the draft to the route- 
over fragmentation optimization I described in the other sub-thread  
(who would send the FRACK?).

We do have "fragment recovery" in 4944 in the sense that it is (lower- 
case) recommended to use 802.15.4's link-layer ACK to increase the  
reliability of each (L2) hop (4944, Section 2, first paragraph).

What we don't have is recovery on the whole L2 path from the  
fragmenting L3/L2 boundary (mesh-under ingress, MUI) to the  
reassembling L2/L3 boundary (mesh-under egress, MUE).  The argument I  
have understood for the draft is that there may be (MU) route changes  
(possibly including MU multipath routing) between MUI and MUE during  
transmission of the fragments of a single (larger) packet, causing  
some parts to be lost even with good use of per-hop acknowledgements.

A 1280 byte packet will take some 40 ms of pure airtime on 2.4 GHz or  
some 500 ms on .868 GHz.  Multiply this by a realistic media sharing  
multiplier, and there does appear some opportunity for radio  
characteristics to change during that time.  But that is just a hunch,  
and some numbers from a real-life network would indeed help.

For now, my (WG member) answer to the WG chair's question whether we  
should adopt that draft is a luke-warm "I wouldn't mind".

Gruesse, Carsten

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 18 Aug 2009 16:34:46 -0400

From: Ralph Droms <[email-masked]>
   Date: Tue, 18 Aug 2009 09:37:03 -0400

I do not have any empirical evidence on the impact of
fragment loss.  I do have empirical evidence on the utility
of end-to-end ACKs for message reliability in a 802.15.4
mesh.  The need for end-to-end ACKs stems from the lack of
any reliable self-repair mechanism for mesh routes.  When a
route breaks, it isn't enough to wait and resend.  Often
some kind of active repair is needed.  Speaking figuratively,
when a backhoe cuts a cable, you have to send a truck.

In advocating for Pascal's fragmentation proposal I am
trying to kill four birds with two stones.  The birds are:
  - using end-to-end ACKs to detect when routes are broken
  - avoiding the need to reassemble and refragment large
    packets in a route-over network
  - increasing the reliability of large, fragmented packets
  - compact and efficient source routing
The stones are:
  - Pascal's proposal or something like it
  - LoWPAN-compatible label switching

                                -Richard Kelsey

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 19 Aug 2009 09:16:48 +0200

Hi Richard:

Upon the first fragment, the trick is to lay an label along the path followed by that fragment (that is IP routed), and all further fragments are label switched along that path. So alternate routes are not possible for fragments. The label game is played by swapping the datagram_tag to make a new locally significant one at each hop. I'm ready to accept such a violation considering the penalty of reassembling at each hop :)

The fragment recovery helps in a number of fashions:
- it provides explicit signaling that the reception is complete and thus enables to clean up intermediate states.
- it enables the source to swap a path by resending a first fragment that will take a new route
- and then the obvious, recovery and flow control. Too bad ECN is gone for the time being.

Cheers,

Pascal

>From: [email-masked] [mailto:[email-masked]] On Behalf Of Richard Kelsey
>Sent: mardi 18 août 2009 17:02
>To: Richard Kelsey
>Cc: [email-masked]; [email-masked]

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 19 Aug 2009 09:45:41 -0400

Date: Wed, 19 Aug 2009 09:16:48 +0200
   From: "Pascal Thubert (pthubert)" <[email-masked]>

Pascal,

   Upon the first fragment, the trick is to lay an label along the path
   followed by that fragment (that is IP routed), and all further
   fragments are label switched along that path. So alternate routes are
   not possible for fragments.

I did eventually realize that Carsten was describing
using datagram tags as labels.

You could get end-to-end ACKs in this scheme by having
only the destination intiate ACKs and only the source
initiate retries.  Intermediate nodes would only relay
fragments and ACKs.  This would require an explicit
description of the process, rather than leaving it up
to implementors.

   The label game is played by swapping the datagram_tag to
   make a new locally significant one at each hop.

This works only if all fragments take the same path.
Fragments that took different paths would arrive at
the destination with different datagram_tags and not
be associated with one another.  On the other hand,
if you don't swap the datagram_tags you are vulnerable
to collisions.

   I'm ready to accept such a violation considering the
   penalty of reassembling at each hop :)

I would prefer to have explicit labelling, both for
clarity and because it could be used for sequences of
short packets as well as for fragmented long packets.

   - it provides explicit signaling that the reception is complete and
     thus enables to clean up intermediate states.

   - it enables the source to swap a path by resending a first fragment
     that will take a new route

For a packet that doesn't fit evenly into N fragments you
could make the first fragment shorter and have all
subsequent fragments be of maximal size.

                                 -Richard Kelsey

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 19 Aug 2009 17:38:19 +0200

>using datagram tags as labels.

In more words:

In route over the L2 source changes at each hop. The datagram tag is
associated to the source MAC and only valid (and unique) for that source
MAC.

Upon a first fragment:
----------------------
Source IPv6 address = IP_A (maybe hops away) Destination IPv6 address =
IP_B (maybe hops away) Source MAC = MAC_prv Datagram_tag= DT_prv

-  do a route lookup and get Next hop IPv6 to B = IP_nxt
-  do a ND resolution and get IP_nxt MAC = MAC_nxt

Since it is a first fragment of a packet from that source MAC MAC_prv
for that tag DT_prv:
- clean up any leftover resource associated to the tupple (MAC_prv,
DT_prv)
- allocate a new label for that flow, DT_nxt, from a LRU pool or
something.
- allocate a Label swap structure for (MAC_prv, DT_prv) that contains
(MAC_nxt, DT_nxt)
- allocate a Label swap structure for (MAC_nxt, DT_nxt) that contains
(MAC_prv, DT_prv)
- swap the MAC info to "from me to MAC_nxt"; Swap the datagram_tag to
DT_nxt; Forward.

Upon next fragments (that are not first fragments)
--------------------------------------------------
- lookup (MAC_nxt, DT_nxt) to get (MAC_prv, DT_prv)
- If not found drop fragment. (ICMP error back could be possible)
- else swap mac and tag and forward, as before

Upon fr-acks:
----------
- lookup (MAC_nxt, DT_nxt) to get (MAC_prv, DT_prv)
- If not found drop.
- else swap mac and tag and forward, as before
- if the bitmap is acks all (could change the draft to make it all ones)
or errors (all zeroes) cleanup resource

Add some aging stuff to clean up stale states and there you are :)

>description of the process, rather than leaving it up

Sure

>if you don't swap the datagram_tags you are vulnerable

Agreed; They have to since the first fragment sets the path.
The key consequence is that we cannot benefit from rerouting along a
DAG. 
So we end up with the loss statistics of one link times the number of
hops.
IOW the fragment recovery is badly needed if we play this game.

>short packets as well as for fragmented long packets.

Makes sense. Ideally both would look and feel the same to the
intermediate nodes. At the end of day the difference could be subtle,
like a type or something. I'm also interested in cleanly removing the
states when all done.

It appears that with the local operation above any node can play the
game or not without knowledge that the peers also do. In other words, we
could reassemble along the way and only nodes that wish/know_how_to skip
the process would do so.

>subsequent fragments be of maximal size.

Neat. I also like the idea of enabling fragments not to be fragments but
a series of packets.

Cheers,

Pascal

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 19 Aug 2009 12:36:21 -0400

Date: Wed, 19 Aug 2009 17:38:19 +0200
   From: "Pascal Thubert (pthubert)" <[email-masked]>

Pascal,

   Upon a first fragment:
   ----------------------
   [...]

   [...]

   Upon fr-acks:
   ----------

You have to be careful about cleaning up just because you
see a complete ack.  Transmission is unreliable in both
directions.  If an intermediate node deletes the record and
the source fails to get the complete ack, the source will
start over from the beginning, even though the destination
already has the packet.  And with the label/datagram_tag
swapping, the destination has no way of knowing that the
retransmission is a copy of a packet it has already received.

   It appears that with the local operation above any node
   can play the game or not without knowledge that the peers
   also do. In other words, we could reassemble along the
   way and only nodes that wish/know_how_to skip the process
   would do so.

I still think that there needs to be a way to distinguish
between an intermittent problem, where just resending a
dropped fragment is enough, and a broken route.  This gets
a lot harder if an intermediate node might reassemble the
packet.
                             -Richard Kelsey

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 20 Aug 2009 11:08:08 +0200

Hi Richard

>   associated to the source MAC and only valid (and unique) for that
source

Say that an ack(all) or and ack (0 == error) cleans up the states down
to a point where it gets lost midway. 

If the retried fragment is not the first fragment, the first node that
cannot forward that fragment because it has its states cleanup has to
ack (0 == error), effectively cleaning the rest of the way between the
source and itself. A node that exhausts retries on a fragment can also
to that.

One side question is whether the packet that ends up in ack(0 == error)
should be retried at the source, and I think not.

So the problem is limited to loosing the ack that acks the first
fragment. The source will retry it and establish a new path, where the
packet will be resent. If the lost ack was an ack(all), that means that
all the fragments were acked in a single shot. The packet will be
duplicated. 

One way of avoiding duplication is to drop a packet when the first
fragment is lost. 
Another is to have intermediate acks that force to ack the first
fragment before they are all sent.

It appears that the frag draft would benefit from a way for the source
to clean up all on the way forward like the ack(0) does on the way back.
I'll look into it.

>a lot harder if an intermediate node might reassemble the

The whole idea is that a path is broken but that routing should find a
new one. If you reassemble at midway, then the packet has progressed
forward and the router that now owns the packet is the new source for a
fragmentation process. 

If the label path gets broken between it and the next fragmentation
endpoint, the router is entitled to find a new path. If it cannot, it is
up to routing to fix that. RPL attempts to maintain DAGs to enable
multiple forwarding solutions and limit that risk.

My question to the group is whether this frag forwarding process should
be described in the frag draft. The reason why we might need to do so is
the need to ack(0 == error) en route when the label path is broken or
the retries are exhausted. The need to do this comes from the label
switching trick and does not make sense otherwise.

What do you think?

Cheers,

Pascal