Subject: RE: [6lowpan] WG last call on Format document

From: "Schumacher Christian Peter Pii" <[email-masked]>
Date: Fri, 5 Jan 2007 10:05:46 +0100

Dear 6lowpanners 
The deadline for the last call has passed.

There have been a few comments on the list:

Comment 1. Reassembly (Philip Levis and Carsten Bormann):
- Carsten assumes a mesh forwarder doesn't need to reassemble.
- Philip believes a mesh forwarder must reassemble, as that would be
more energy efficient.

Comment 2. IANA considerations (Philip Levis):
- Is arbitration of the 00xxxxxx values under its  
purview? (Regarding NALP)

To resolve comment 1: I urge the mailing list to respond with your
opinions on this matter.
To resolve comment 2: I believe it is within the purview of IANA, but
can anyone confirm this?

A final question, is there anyone who doesn't feel the format document
is ready for IESG review?

Regards
Christian

-----Original Message-----
From: Philip Levis [mailto:[email-masked]] 
Sent: 14. december 2006 17:47
To: Carsten Bormann
Cc: 6lowpan
Subject: Re: [6lowpan] WG last call on Format document

On Dec 14, 2006, at 12:58 AM, Carsten Bormann wrote:

>> I still have a concern about the ordering of the fragmentation and  
>> mesh delivery headers. Can anyone offer a good argument on why  
>> fragmentation is within mesh and not vice versa?
>
> I think the general rule is that a node should only have to parse  
> the subheaders that it is concerned with.
>
> I'm assuming a mesh forwarder does not reassemble (I don't happen  
> to know any good reason why it should).

Energy. Imagine a theoretical route from N0 to NX of nodes N0, N1,  
N2, ... NX. Let us suppose that each link (NZ,NZ+1) has a packet loss  
rate of L. If you have no e2e fragment recovery, then an IPv6 packet  
P composed of F fragments has a ((1-L)^X)^F probability of successful  
delivery. The probability of any fragment being delivered  
successfully is (1-L)^X, and the probability of all of them being  
delivered successfully is (1-L)^X^F. It decreases exponentially with  
path length and packet size. With no fragment recovery, you have to  
resend the entire packet when this occurs. So the cost of a single  
fragment failure is FX transmissions and the overall cost to deliver  
a packet successfully is approximately FX + FX * (1-L)^-XF.

With multihop reassembly, a single fragment loss requires control  
traffic to request the fragment, which itself also has a loss rate of  
(1-L)^X, then the fragment being retransmitted. So the cost of a  
single fragment failure is 2X transmissions, and the cost to deliver  
a packet successfully is approximately FX + 2FX * (1-L)^-X.

With single-hop reassembly, each hop reassembles the packet as  
needed. Because losses are locally recovered, you do not have the  
exponential growth in packet loss. Unlike multihop recovery, where  
the number of packets transmitted is going to approximately be FX *  
((1-L)^X)^-1, (the expected number of transmissions per packet is the  
inverse of the loss rate), in single-hop recovery the equation is  
multiplicative: FX* (1-L)^-1. Each link sends only (1-L)^-1 copies of  
its each fragment, with retransmissions caused by local failures. So  
the cost becomes FX + 2FX * (1-L)^-1.

Recap:

F is number of fragments
X is length of route
L is loss rate on each hop

Multihop reassembly with full packet retransmission: FX + FX * (1-L)^-XF
Multihop reassembly with fragment retransmission: FX + 2FX * (1-L)^-X
Single-hop reassembly with fragment retransmission: FX + 2FX * (1-L)-1

Additionally, if you layer mesh on top of fragmentation, then every  
mesh packet has a fragmentation header in it. If the mesh header  
length is M and the fragment header length is G, then each fragment  
has M+G bytes added to it, for a total of F * (M + G). If you reverse  
the layering, then only the first fragment has the mesh header, and  
so you have a header cost of M + FG.

Finally, it is (in my experience, others might differ on this) also  
easier to manage the state and retransmission policies, as reassembly  
does not have to worry about greatly different latencies caused by  
route changes between fragments.

That being said, if X, F, and L are always going to be small, then  
the exponents don't matter. But there's a fundamental scalability  
problem.

> So a mesh forwarder is concerned with the forwarding header only;  
> these therefore should come first.
> Only at the L2 destination is it necessary to peek further into the  
> header, e.g. the fragmentation header for reassembly.
>
> Compare this with IPv6: The forwarding header (here the IP header)  
> is in front of the fragmentation header, which is a destination  
> header (only "opened" at the destination address set in the IP  
> header).
>

Two mails ago:

I have one concern with the current draft: the ordering of the  
fragmentation and mesh headers. In his presentation at IETF 67,  
Jonathan noted that the order followed the model presented by  
standard IPv6. In IPv6, fragmentation/reassembly must be end-to-end,  
so the ordering makes sense. However, this is sub-IP. I think that  
most of the real-world experiments with 15.4 radios, as well as basic  
loss models, suggest that per-hop fragmentation/reassembly is greatly  
preferable to e2e, particularly for energy reasons. You don't need to  
add a mesh header on each fragment, you have fewer retransmissions,  
and less state maintenance. Including a mesh routing header is  
essentially to provide IP routing; following the guidelines of RFC  
2460 Section 5, I believe the order of these two headers should be  
reversed: a node fragments and reassembles a mesh packet on a per-hop  
basis, rather than routing an IPv6 datagram one fragment at a time.

Phil

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

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

---

From: "Timothy J. Salo" <[email-masked]>
Date: Fri, 05 Jan 2007 16:01:11 -0600

Philip Levis wrote:
>> I think the general rule is that a node should only have to parse the 
>> subheaders that it is concerned with.
>>
>> I'm assuming a mesh forwarder does not reassemble (I don't happen to 
>> know any good reason why it should).
> 
> Energy. ... With no fragment recovery, you have to resend the 
> entire packet when this occurs. So the cost of a single fragment failure 
> is FX transmissions and the overall cost to deliver a packet 
> successfully is approximately FX + FX * (1-L)^-XF.
> 
> (1-L)^X, then the fragment being retransmitted. ...
> 
> With single-hop reassembly, each hop reassembles the packet as needed. 
> Because losses are locally recovered, you do not have the exponential 
> growth in packet loss. ...

I believe that hop-by-hop reassembly is one potential solution, and
perhaps not the best solution, to a more general problem.

In heavily resource-constrained environments, it may be reasonable
to expect that no data are ever retransmitted unnecessarily (at
least as a result of the design of the protocol).  That is, once
a fragment is successfully received, it should never be transmitted
again.  Of course, actually achieving this objective in a
nontrivial network is not particularly easy.

It is not clear to me that hop-by-hop reassembly within the WLAN
is necessarily a good idea for several reasons:

o  This may fail in the face of topology changes or node failures.
    In these cases, you would like some better way to recover than
    simply loosing the packet and letting the higher-layer protocols
    retransmit (or not).

o  Hop-by-hop reassembly requires buffering, which will probably be
    at a premium in this environment.  There are at least several
    possible approaches:

    -   Each node could have enough memory that it	
        never runs out of buffers.  Clearly, this
        isn't much of a solution.

    -   A hop-by-hop buffer reservation protocol could
        be created that would prevent reassembly lockup.
        While I think this would work well, it requires some thought
        and perhaps even modeling.

    -   A node could simply discard fragments if it runs
        out of buffers, but then we are back to discarding
        data that were correctly received and perhaps retransmitting
        something from somewhere.

I suspect that hop-by-hop retransmission may be much
preferable to hop-by-hop reassembly.  I forget what the
format document says about this...  And, yes, hop-by-hop
retransmissions _can_ result in poor interactions with
TCP congestion control algorithms.  However, I am not
convinced that this is necessarily an issue in this
case because:

o  The retransmission timeout on the WLAN should be, or
    should be made, very small compared to the end-to-end
    round-trip-time and retransmission timeout.

o  In actual practice, the granularity of TCP's retransmission
    timer is pretty large.  I don't have time to look it up,
    but isn't it 500 ms on BSD systems?  Our timescales should
    be so much smaller than that, that we ought to be able to
    make lots of attempts to get a packet through the WLAN
    before TCP decides to retransmit.

Hop-by-hop retransmission still has the problem that if the
route changes or a node fails, the packet will be lost.  How should
we recover from this?

I think that a reasonable approach is to probably do hop-by-hop
retransmissions and when that fails, retransmit (either the
packet or select fragments) from the IP/WSN gateway.  This,
of course, raises a number of, largely non-technical, issues.
Perhaps, the most significant one is that we don't appear to
have the resources in this Working Group to tackle this issue.

Now, a few more general thoughts.

To me, this discussion is the sort of thing that should have
occurred in an architecture specification.  I think that there
are a number of these issues that we may discuss piecemeal (or,
perhaps at all).  I don't believe that discussing architectural
issues piecemeal as they come up is a reliable way to create a
strong architecture.

I believe that we would have a stronger technical solution if we
thought more carefully about what functionality should be
implemented in the gateway between the wireless sensor network
(WSN) and the IP network to which it is attached.  Above, I
essentially suggested that this gateway should include a
particular type of performance-enhancing proxy (PEP).  I believe
that there are actually a number of these PEPs that we ought
to consider for implementation in the WSN/IP gateway.

As an example of the range of things we might consider, I have
suggested privately that the WSN/IP gateway should (maybe)
translate pretty much all IPv6 addresses to 16-bit addresses.

(By the way, I think that our focus on running IPv6 over IEEE
802.15.4 networks, rather than interconnecting IEEE 802.15.4
networks with IPv4 and IPv6 networks has tended to narrow the
range of technical solutions that we consider.)

Having said all that, that leaves the question of what we should
do about all this.

It seems pretty clear to me that we simply don't have the resources
within the Working Group to do much.  If this observation is correct,
then it might be reasonable to conclude that we should focus on
pushing _something_ out the door and hope that wireless sensor
networks will generate more interest within the IETF at some point
in the future.

(For what it is worth, I am trying to find resources that would
permit me to spend a lot more time on this, but the outcome is
uncertain.  And, while I would like to think that I could make a
real difference to the Working Group if I spend more time on
this, there is no reason to believe that this notion is
universally accepted...)

-tjs