Subject: Re: [6lowpan] Complete reassemble at every hop (was: New charter for 6lowpan)

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 2 Jun 2008 12:23:52 +0200

Hi Jonathan:

As I expected we are off sync.

>over a different link technology appear as a single link, I'd much
>rather see a Mesh Addressing header that can hold PANIDs of the source
>and destination and then simply bridge 802.15.4 frames across the
>backbone network. Then you aren't constrained to forcing all fragments
>to ingress/egress through a single BbR. If you truly want to enable
>multi-path routing, then why not support it in full?

Do you mean D should reassemble 6LoWPAN packets? 
D should not see 6LoWPAN. D is an IPv6 node on the internet.

>> 1) How the receive interface in C knows that the 6LowPAN continues
>>   (it is not the LoWPAN endpoint so it should not reassemble)
>
>If you're doing L3 forwarding, then simply match on the IPv6
>destination address. If you're doing L2 forwarding, then you need the
>Mesh Addressing header if you're forwarding over >1 802.15.4 hop.

The receive interface should not have to do a route lookup to decide to
terminate L2. That's what I tried to tell you in the beginning of this
thread. 

>> 2) How we make sure that all fragments reach BbR for reassembly.
>
>If you're doing L3 forwarding, fragments are constrained to a single
>path. The BbR is replaced with a traditional IP router.

There's nothing in IP routing that constrains all packets to go over a
single path.

Let's try again.

Now we have: 

A---->B---->C---->Router1---------->D

<----------------->     <----------->
LoWPAN (same PAN ID)     Internet

In my view, if a routing process in router 1 computes a path from A to D
and passes the source route info to A, that is still route over. If the
source route path is translated into a mesh header, that's just a
mapping. So I have nothing against using mesh header for route over.
Looks quite natural to me.

Now if we have

A---->B---->C---->Router1---------->D
|                                   ^
|                                   |
+---->E---->F---->Router2-----------+

<----------------->     <----------->
LoWPAN (same PAN ID)     Internet

It is certainly possible for the routing to enable both routes. And if
fragments are spread over those routes we have an issue. We need
something to force that all fragments go through either one of the
routers for recomposition. A mesh header looks like the natural way of
doing this. Obvisouly, a routing header could do but RH0 is being
deprecated...

Pascal

>-----Original Message-----
>From: Jonathan Hui [mailto:[email-masked]]
>Sent: vendredi 30 mai 2008 19:13
>To: Pascal Thubert (pthubert)
>Cc: Jean Philippe Vasseur (jvasseur); Philip Levis; Mark Townsley
(townsley); [email-masked]
>Subject: Re: Complete reassemble at every hop (was: [6lowpan] New
charter for 6lowpan)
>
>
>Hi Pascal,
>
>On May 30, 2008, at 9:45 AM, Pascal Thubert (pthubert) wrote:
>> Say the path over a LoWPAN from a node A to a Backbone Router BbR is
>> via
>> B and C
>> Say A sends a packet to D that is reachable over the BbR that acts as
>> default
>> gateway and 6LoWPAN termination for the LoWPAN.
>>
>> A---->B---->C---->BbR---------->D
>> <-----------------> <----------->
>>      LoWPAN           Backbone
>>
>> How I see things:
>> If we use a mesh header then it will show (A->BbR) all the way
through
>> the LoWPAN
>> In particular, between B and C, it seems to me that the frame should
>> have:
>> - (b->c) in the MAC hdr;
>> - (a->BbR) in the mesh header;
>> - and indicate in the HC that A address is compressed whereas D is
>> not.
>> That seems to work whether the routing is computed at L2 or L3.
>
>Okay. Given your scenario, the Mesh Addressing header may not identify
>the endpoints of an IP hop. For me, things get more complex and
>confusing in this scenario. You're trying to bridge one or more
>802.15.4 PANs using a different link technology but the Mesh
>Addressing header doesn't provide the means to address nodes in other
>PANs. To cleanly support the scenario where multiple PANs connected
>over a different link technology appear as a single link, I'd much
>rather see a Mesh Addressing header that can hold PANIDs of the source
>and destination and then simply bridge 802.15.4 frames across the
>backbone network. Then you aren't constrained to forcing all fragments
>to ingress/egress through a single BbR. If you truly want to enable
>multi-path routing, then why not support it in full?
>
>> Now if you do not have a mesh header, I fail to understand:
>> 1) How the receive interface in C knows that the 6LowPAN continues
>>   (it is not the LoWPAN endpoint so it should not reassemble)
>
>If you're doing L3 forwarding, then simply match on the IPv6
>destination address. If you're doing L2 forwarding, then you need the
>Mesh Addressing header if you're forwarding over >1 802.15.4 hop.
>
>> 2) How we make sure that all fragments reach BbR for reassembly.
>
>If you're doing L3 forwarding, fragments are constrained to a single
>path. The BbR is replaced with a traditional IP router.
>
>--
>Jonathan Hui
>
>>
>>
>> Pascal
>>
>>> -----Original Message-----
>>> From: Jonathan Hui [mailto:[email-masked]]
>>> Sent: vendredi 30 mai 2008 17:33
>>> To: Jean Philippe Vasseur (jvasseur)
>>> Cc: Pascal Thubert (pthubert); Philip Levis; Mark Townsley
>>> (townsley);
>> [email-masked]
>>> Subject: Re: Complete reassemble at every hop (was: [6lowpan] New
>> charter for 6lowpan)
>>>
>>>
>>> Hi Pascal and JP, see below:
>>> On May 29, 2008, at 7:16 PM, JP Vasseur wrote:
>>>>>> First is whether or not route-over implies complete reassembly at
>>>>>> every hop. In my view, it doesn't. A node could simply cache the
>>>>>> datagram tag when the first fragment arrives and forward the
>>>>>> subsequent fragments accordingly.
>>>>
>>>> Oops ! You mean route a fragment based on the routing decision made
>>>> for the
>>>> first fragment ? Not sure I personally like this, since this
>>>> introduces some
>>>> states on intermediate nodes, which has strong implication.
>>>> Further, this means that a fragmented packet cannot be rerouted
>>>> along a
>>>> backup path once the first fragment has been sent out since nodes
>>>> along the
>>>> alternate path would not have the required states to route them.
>>>
>>> Yes, it does consume extra state, but the overhead is pretty small,
>>> around 10-bytes for caching two tags, two addresses, and timing
>>> information. When the last fragment rolls by, you can quickly clean
>>> up
>>> the state. It's still an open question for me how may simultaneous
>>> flows of fragmented datagrams is truly needed. Re-routing mid-stream
>>> is arguably less important for delivering a fragmented datagram,
>>> especially due to temporal properties of the link.
>>>
>>>> Note that this also saves header
>>>>>> overhead because the mesh header doesn't have to be included in
>>>>>> every
>>>>>> fragment. When forwarding between different links, reassembly has
>> to
>>>>>> happen anyway.
>>>>>>
>>>>>
>>>>> This should be addressed in the architecture very clearly. Whether
>>>>> the
>>>>> path is computed at L2 or L3, there's a need to decide and express
>>>>> clearly in the packet what is the source that does the 6LowPAN
>>>>> compression, and what is the destination that expands the packet.
>>>>> An
>>>>> interface on a router should not have to make assumptions on
>>>>> whether a
>>>>> packet will be routed on another interface of the same type or
not.
>>>
>>> Yes, I've said all along that the architecture document is
necessary.
>>> Where reassembly happens has been pretty clear in my mind, and must
>>> happen before you exit a 6lowpan-based IP link.
>>>
>>>>> I've been trying to parse another of your mails on the same
subject
>>>>> and
>>>>> still fail to understand the model you have in mind for what goes
>>>>> in the
>>>>> mesh header if any and what is uncompressed over a multihop LowPAN
>>>>> path.
>>>>> I believe that a few examples with figures would help a lot and
>>>>> that
>>>>> they should end up in the architecture doc once we agree on them.
>>>
>>> The Mesh Addressing header is currently defined in RFC4944 and the
>>> addresses carried within that header identify the end-points of an
IP
>>> hop. With L3 forwarding, the Mesh Addressing header contains the
same
>>> addresses as the 802.15.4 header and so the Mesh Addressing header
>>> can
>>> be elided. I've provided a few examples at the WG meetings. Can you
>>> tell me what specific scenarios you're confused about, so I can
>>> address them directly?
>>>
>>> --
>>> Jonathan Hui
>>>
>>>>>
>>>>>
>>>>> Fair?
>>>>
>>>> Indeed.
>>>>
>>>> Cheers,
>>>>
>>>> JP.
>>>>
>>>>>
>>>>> Pascal
>>>>>> -----Original Message-----
>>>>>> From: Jonathan Hui [mailto:[email-masked]]
>>>>>> Sent: mardi 27 mai 2008 18:27
>>>>>> To: Pascal Thubert (pthubert)
>>>>>> Cc: Philip Levis; Jean Philippe Vasseur (jvasseur); Mark Townsley
>>>>> (townsley); [email-masked]
>>>>>> Subject: Re: [6lowpan] New charter for 6lowpan
>>>>>>
>>>>>>
>>>>>> Hi Pascal, I see a few underlying issues in this discussion.
>>>>>>
>>>>>> First is whether or not route-over implies complete reassembly at
>>>>>> every hop. In my view, it doesn't. A node could simply cache the
>>>>>> datagram tag when the first fragment arrives and forward the
>>>>>> subsequent fragments accordingly. Note that this also saves
header
>>>>>> overhead because the mesh header doesn't have to be included in
>>>>>> every
>>>>>> fragment. When forwarding between different links, reassembly has
>> to
>>>>>> happen anyway.
>>>>>>
>>>>>> The second issue is whether or not we constrain forwarding
>> fragments
>>>>>> of a given datagram to a single path. This is where mesh-under
and
>>>>>> route-over diverge. But to me, there are a lot of advantages to
>>>>>> constraining delivery of a datagram to a single path. Hop-by-hop
>>>>>> recovery can ensure in-order delivery. Hop-by-hop congestion
>> control
>>>>>> becomes much more meaningful. It's unclear to me what end-to-end
>>>>>> congestion notification means in a mesh-under setting. We can
also
>>>>>> take advantage of link optimizations to increase throughput and
>>>>>> decrease latency. And, as mentioned before, reduces header
>>>>>> overhead by
>>>>>> not needing addressing information in subsequent fragments.
>>>>>>
>>>>>> The third issue is whether or not end-to-end mechanisms should be
>>>>>> used
>>>>>> for recovery and congestion control. I think we agree that
hop-by-
>>>>>> hop
>>>>>> mechanisms are required regardless. They increase reliability and
>>>>>> can
>>>>>> provide effective congestion control and mitigation. To me, hop-
>>>>>> by-
>>>>>> hop
>>>>>> mechanisms are generally much more effective than end-to-end ones
>>>>>> because they react to local conditions and can quickly provide
>> back-
>>>>>> pressure all the way to the source. From a reliability
standpoint,
>>>>>> we've seen solutions deliver >99.9% without end-to-end recovery.
>>>>>> So
>>>>>> one question is how much more reliability do we really need? and
>>>>>> does
>>>>>> it justify the added energy overhead and code size?
>>>>>>
>>>>>> --
>>>>>> Jonathan Hui
>>>>>>
>>>>>>
>>>>>>
>>>>>> On May 26, 2008, at 7:18 AM, Pascal Thubert (pthubert) wrote:
>>>>>>
>>>>>>> Hi Phil:
>>>>>>>
>>>>>>> We do agree on the problem.
>>>>>>>
>>>>>>> Per-hop reassembly, though, comes at the expense of that traffic
>>>>>>> fluidity that was so desirable to the ATM designers. In other
>>>>>>> words,
>>>>>>> because per-hop reassembly forces each intermediate node to
store
>>>>>>> and
>>>>>>> forward a full packet, it is augmenting the latency of the flow
>> and
>>>>>>> the
>>>>>>> memory requirements on the forwarding nodes on the way.
>>>>>>>
>>>>>>> This is why I had in mind to couple a few per-hop recovery with
a
>>>>> more
>>>>>>> solid end-to-end recovery and flow control mechanism between the
>>>>>>> LoWPAN
>>>>>>> endpoints.
>>>>>>>
>>>>>>> Now I wonder what this discussion becomes in route over v.s.
mesh
>>>>>>> under.
>>>>>>> In route over, it seems that the forwarding node terminates a
>>>>>>> link
>>>>>>> so it
>>>>>>> has to reassemble before it forwards on a different link that
>> might
>>>>> or
>>>>>>> might not be a LoWPAN; so maybe we end up doing the same thing
in
>>>>> that
>>>>>>> case.
>>>>>>>
>>>>>>> Jonathan, what do you think?
>>>>>>>
>>>>>>> Pascal
>>>>>>>
>>>>>>>> -----Original Message-----
>>>>>>>> From: Philip Levis [mailto:[email-masked]]
>>>>>>>> Sent: vendredi 23 mai 2008 19:46
>>>>>>>> To: Pascal Thubert (pthubert)
>>>>>>>> Cc: Jean Philippe Vasseur (jvasseur); Mark Townsley (townsley);
>>>>>>> [email-masked]
>>>>>>>> Subject: Re: [6lowpan] New charter for 6lowpan
>>>>>>>>
>>>>>>>>
>>>>>>>> On May 23, 2008, at 3:50 AM, Pascal Thubert (pthubert) wrote:
>>>>>>>>
>>>>>>>>> Hi JP:
>>>>>>>>>
>>>>>>>>> I see your concern.
>>>>>>>>>
>>>>>>>>> I'd argue that ECN is now pretty well defined now in RFC 3168,
>>>>>>>>> and
>>>>>>>>> that
>>>>>>>>> the basic operation is pretty simple: emulate a packet loss in
>>>>>>>>> RED
>>>>>>> but
>>>>>>>>> save the packet. So the real problem is not ECN itself but
what
>>>>>>>>> RED
>>>>>>>>> becomes in a LowPAN forwarding node. And that is something
that
>>>>>>>>> the
>>>>>>>>> node
>>>>>>>>> will have to define whether it does ECN or RED.
>>>>>>>>>
>>>>>>>>> If we do not have ECN then the LowPAN forwarding nodes will
>>>>>>>>> have to
>>>>>>>>> destroy frames which might be fragments. Considering the cost
>>>>>>>>> of
>>>>>>>>> energy
>>>>>>>>> and bandwidth to getting the frame up to that forwarding node,
>>>>>>>>> the
>>>>>>>>> latency introduced by transport layer time out, and the risk
of
>>>>>>>>> congestion collapse introduced by resending the whole segment,
>>>>>>>>> I'd
>>>>>>>>> suggest that ECN is actually a good idea.
>>>>>>>>
>>>>>>>> This gets back to the point I brought up December 14, 2006. In
>>>>>>>> lossy
>>>>>>>> networks, end-to-end fragmentation and assembly is a real
>> problem.
>>>>> It
>>>>>>>> makes much more sense to do per-hop fragmentation and assembly.
>> In
>>>>>>>> the
>>>>>>>> former, the number of retransmitted fragments is exponential in
>>>>>>>> the
>>>>>>>> number of hops; in the latter, it is linear.
>>>>>>>>
>>>>>>>> Phil
>>>>>
>>>>
>>

_______________________________________________
6lowpan mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/6lowpan

---

From: Jonathan Hui <[email-masked]>
Date: Mon, 2 Jun 2008 09:13:40 -0700

Hi Pascal:

> D should not see 6LoWPAN. D is an IPv6 node on the internet.

No, I did not mean that D should reassemble 6LoWPAN packets. I simply  
stated that if you want to support multi-path forwarding of fragments  
at L2, then ideally we wouldn't limit delivering fragments into/out of  
a PAN through a single BbR. Your examples imply that we have to limit  
the multi-path through a single BbR. Of course, if you're forwarding  
off the BbR-connected 6LoWPAN network, then you've got to reassemble  
before doing so. In my example below, BbR4 acts as the fragmentation/ 
reassembly point for the 6LoWPAN IP Link. But if nodes in PAN 1 want  
to send large datagrams to PAN 2, they should be allowed to utilize  
both BbR 1 and BbR 2.

        6LoWPAN IP Link           |  Traditional IP Link
                                  |
  /---------\                     |
  |         |- BbR 1 -\           |
  |  PAN 1  |          |          |
  |         |- BbR 2 --|          |
  \---------/          |-- BbR4 --|-- Other IP Network
                       |          |
  /---------\          |          |
  |  Pan 2  |- BbR 3 -/           |
  \---------/                     |

> terminate L2. That's what I tried to tell you in the beginning of this

Let me try arguing it a different way. If we don't include a Mesh  
Addressing header, then we are implicitly requiring fragmentation/ 
reassembly at every hop along the way. No route lookup required.  
Whether or not a node actually reassembles a datagram before  
forwarding it again is an implementation decision. A 6LoWPAN node  
doing L3 routing can simply update the 802.15.4 and fragmentation  
header and forward the fragment on to the next hop. The next hop has  
no way of telling that the datagram wasn't completely reassembled then  
fragmented before forwarding.

> There's nothing in IP routing that constrains all packets to go over a

IP routing doesn't constrain all datagrams to go over a single path,  
but L2 fragmentation with L3 forwarding does. In my diagram above, L3  
forwarding implies that each BbR is, in fact, an IP router and that  
BbR 4 knows nothing about 6LoWPAN adaptation. As a result, you've got  
to constrain forwarding of all fragments for a datagram through a  
single BbR.

> A---->B---->C---->Router1---------->D

Sure, you're following the MPLS approach of L3 routing combined with  
L2 forwarding. I'm not convinced that an MPLS-like approach for  
6LoWPAN is the best one. It means that we have to define forwarding  
mechanisms along with the appropriate configuration and management  
mechanisms at L2. Similar functionality may be provided at L3,  
increasing the node resource requirements. At this stage, I prefer to  
have forwarding at L3 because it unifies many of the networking  
mechanisms into a single layer.

> +---->E---->F---->Router2-----------+

If you truly want to do multipath forwarding of fragments, then I  
agree that you have to do it at L2. But if you're going to do that,  
then I'd much rather not constrain the architecture to limit  
forwarding through a single BbR. Instead, a "meta"-BbR should be used  
as the egress router to other connected IP network when reassembly is  
needed. Whether that's a separate BbR or an elected BbR connected  
directly to the PAN is an implementation decision.

> doing this. Obvisouly, a routing header could do but RH0 is being

Note that RFC 5095 does acknowledge benign uses of RH0 and suggests  
future Routing Header specifications to serve those purposes.

--
Jonathan Hui

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 3 Jun 2008 12:11:25 +0200

Hi Jonathan:

I would not send fragments over a backbone for multiple reasons; the
backbone must be native IPv6 on whatever medium is being used, so you
can connect any node to it and provide end to end IPv6 connectivity with
the LoWPAN field device.

Anyway, it seems that we agree on what we have to do but I still fail to
see which mechanism you have in mind to actually do it and what is in
the packet or in the node states to enable that. 

For instance:
- your BbR4. Do you have something in the packet that points to it like
my mesh header or routing header so that all packets go towards it? 

- How does a node on the way decide that it should recompose the packet?
I mean, how does BbR 1 know whether it is a BbR1 and not a BbR4? 

I disagree that this is up to implementation. The whole system must make
sense and interoperate and we need an architecture that says who does
what based on which info. 

At the moment, the only things that I figure can work are hop-by-hop
fragment recomposition and mesh header to indicate the source and the
destination of the fragments. 

What else?

Pascal

>Sent: lundi 2 juin 2008 18:14
charter for 6lowpan)

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 3 Jun 2008 14:25:25 -0700

Hi Pascal:

> can connect any node to it and provide end to end IPv6 connectivity  

So maybe I'm confused about the architecture you had in mind with the  
backbone-router draft. There is the following statement in the draft:  
"knowledge of the 64-bit address of another node on the same extended  
LoWPAN is enough to derive its link-local address and reach it over  
IP." That seems to imply that the BbR's are responsible for making one  
or more PANs appear as a single IP link. They are technically doing L2  
forwarding because the Hop Limit should not get decremented between  
the source and destination when communicating over link-local. If that  
is the case, BbRs aren't simply doing IP routing. However, they do  
function as IP routers to route datagrams between the Extended LoWPAN  
network and other IP networks.

> my mesh header or routing header so that all packets go towards it?

A couple emails ago, I said that the Mesh Addressing header specified  
in RFC4944 is insufficient for supporting my ideal scenario for L2  
forwarding and that I prefer a L2 forwarding header that identifies  
the ends of an IP hop. To be fair, the Mesh Addressing header was  
designed for L2 forwarding within a single LoPAN, not an Extended  
LoWPAN.

> I mean, how does BbR 1 know whether it is a BbR1 and not a BbR4?

The BbR that is elected as the IP router does the reassembly. Note  
that not all BbRs do not have to be full-fledged IP routers if they  
are simply doing L2 forwarding.

> what based on which info.

My comment on implementation details was w.r.t. delivering LoWPAN  
fragments over a LoWPAN using L3 forwarding. All I said was that  
complete reassembly at each hop is not strictly required. If done  
properly, there should be no perceivable difference in the 6LoWPAN  
packets being transmitted. At the protocol level, we're primarily  
concerned with what and how bits are passed around, but if different  
implementations can deliver those bits in the same way, then it is an  
implementation detail.

> destination of the fragments.

Yes, but I'd argue that a mesh header should indicate the source and  
destination of an IP hop. If a primary goal of L2 forwarding is to  
support multi-path delivery of 6LoWPAN fragments, why limit it to a  
single choke point in the PAN? You don't achieve any of the receiver/ 
spatial diversity that you were trying to achieve at all of the other  
hops. And that last hop often tends to be where much of the benefits  
can be realized.

This is a good discussion to have, but I'm not convinced on the  
benefits of L2 forwarding over L3 forwarding in 6LoWPAN networks. I do  
agree that enables multi-path forwarding of fragmented IPv6 datagrams.  
But, as I've mentioned, it's still limited to a single choke point at  
the BbR. And, do we really know whether fragmented datagrams will be  
the common case vs. the exception?

--
Jonathan Hui