Subject: [Roll] FW: New Version Notification for draft-thubert-roll-fundamentals-01

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 9 Apr 2009 10:59:34 +0200

Dear Rollers:

Taking feedback from a number of sources, we decided to publish a new version of draft-thubert-roll-fundamentals that lets out some gory details of the exact operations from 00 to provide a clearer and more comprehensive view of the overall proposed approach. The goal of the draft is certainly not to compete with the DT effort but to provide some input to the DT that was just formed and help its kick-off. 

1) This contribution details the formation of a Distance Vector tree using ND extensions; most existing contributions to this WG suggest that approach (Teco's BRDP, Arsalan & al. 's Hydro's Default Route Formation, Phil & al. Usenix paper's Tree based routing...) and the value we provide here is more refined details on such operation, to address for instance merging and splitting of trees or the integration with the 6LoWPAN backbone. 

2) Forwarding along the tree to the sink is a bit different from one draft and paper to another. We (ROLL) have a clear requirement to forward and enable retries over multiple next hops along a graph to the sink that derives from the lossyness of some of the links we operate on. This draft suggests that the tree is merely a skeleton for such a fabric and that packets can be forwarded along a graph that forms the 'aura' of that tree. 

Basically, since we have a depth, we have feasible parents (of lesser depth) and siblings (of same depth). The draft suggests that we can select any parent to forward on a per packet basis using the best metric or more advanced load balancing functionality; if that fails then we can use a sibling with some basic loop avoidance like poison return or more advanced path vector (for hydrophiles).

One benefit of that approach is that there is not one DAG fits-it-all, but an equal opportunity between siblings to use one another on a per packet basis. So router B might forward a given packet to sibling router A that passes it to one of its parents whereas later router B would forward another packet to A that would pass it to one of its parents, all for an unchanged same tree structure.

Another benefit is that we can be a lot more lazy in restructuring the tree to adapt the routing to the metric changes since the forwarding can start using the metric update a lot earlier anyway. The idea is that we adapt to and propagate the metric rapidly but we act upon the metric to restructure the tree only after it appears that the new conditions are stable enough to justify the effort.

3) routing towards the leaves is a more major difference and I guess we need to talk. This draft suggests that the interesting leaves can percolate unicast and multicast information in NA messages towards the root, enabling routing along the tree. You find a similar idea with Teco's BRIO. The draft also allows for:
- multiple alternate trees for more specific destinations 
- source routing along the tree that’s dynamically compressed when routing states match the source route info

4) finally the draft lists a number of additional features that might or might not be considered for inclusion to better fit some specific requirements. You'll find some hints on how to use Multiple topology Routing using multiple default trees, Offline Routing for basic Traffic Engineering (similar to Hydro), some on-demand adhoc using reactive MANET (similar to 802.11S) etc...

Happy reading,

Pascal

-----Original Message-----
From: IETF I-D Submission Tool [mailto:[email-masked]] 
Sent: jeudi 9 avril 2009 08:02
To: Pascal Thubert (pthubert)
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: New Version Notification for draft-thubert-roll-fundamentals-01 

A new version of I-D, draft-thubert-roll-fundamentals-01.txt has been successfuly submitted by Pascal Thubert and posted to the IETF repository.

Filename:	 draft-thubert-roll-fundamentals
Revision:	 01
Title:		 LLN Routing Fundamentals
Creation_date:	 2009-04-09
WG ID:		 Independent Submission
Number_of_pages: 29

Abstract:
This document describes a basic set of fundamental mechanisms for
routing on a Low-power and Lossy Network (LLN).  It does not intend
to specify a full-blown protocol.  It is rather offered as a basis to
support the discussion while designing the ROLL protocol.

The IETF Secretariat.

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 9 Apr 2009 15:10:12 -0400

Date: Thu, 9 Apr 2009 10:59:34 +0200
   From: "Pascal Thubert (pthubert)" <[email-masked]>

   3) routing towards the leaves is a more major difference and I guess
      we need to talk. This draft suggests that the interesting leaves
      can percolate unicast and multicast information in NA messages
      towards the root, enabling routing along the tree.

I think that we need to be careful with this to avoid
requiring too much routing state.  The root and its children
could end up having to store a lot of information.  As
spelled out in the protocol survey document, routing state
should be bounded by O(D), where D is the number of "unique
destinations".  I couldn't find a definition for this, but
the document states that it scales at less than O(N), where
N is the number of nodes.  This means that most nodes cannot
be included in the disseminated information.  Presumably
these less-interesting devices can be reached via route
records or other topology information stored on a root.

Given that most nodes can only be reached via a root in any
case, it isn't clear to me that route dissemination is worth
the trouble.
                                   -Richard Kelsey

---

From: Philip Levis <[email-masked]>
Date: Fri, 10 Apr 2009 06:52:04 -0700

On Apr 9, 2009, at 1:59 AM, Pascal Thubert (pthubert) wrote:

> 1) This contribution details the formation of a Distance Vector tree  
> using ND extensions; most existing contributions to this WG suggest  
> that approach (Teco's BRDP, Arsalan & al. 's Hydro's Default Route  
> Formation, Phil & al. Usenix paper's Tree based routing...) and the  
> value we provide here is more refined details on such operation, to  
> address for instance merging and splitting of trees or the  
> integration with the 6LoWPAN backbone.

It's worth noting that the networking abstractions paper is, at this  
point, 5 years old. Protocols have progressed a lot since then. And I  
think it's safe to say that the statements of "IP doesn't seem to be  
useful" should be "at that time, we didn't think IP would be useful  
and gosh were we wrong!"

> Basically, since we have a depth, we have feasible parents (of  
> lesser depth) and siblings (of same depth). The draft suggests that  
> we can select any parent to forward on a per packet basis using the  
> best metric or more advanced load balancing functionality; if that  
> fails then we can use a sibling with some basic loop avoidance like  
> poison return or more advanced path vector (for hydrophiles).

Here's a URL to a paper that describes one way to solve this problem,  
using the techniques I mentioned a few weeks ago and touched on in my  
talk in SF:

http://sing.stanford.edu/pubs/ctp.pdf

The source code for CTP (the tree protocol in the paper) is part of a  
TinyOS release and is under a BSD license. It can be found at

http://www.tinyos.net/tinyos-2.x/tos/lib/net/ctp/

Phil

---

From: Richard Kelsey <[email-masked]>
Date: Fri, 10 Apr 2009 13:56:54 -0400

From: Philip Levis <[email-masked]>
   Date: Fri, 10 Apr 2009 06:52:04 -0700

Good stuff.  Relating this back to the Routing Fundamentals
draft, it seems clear that ROLL will most likely use trees
for at least some routing, and while Router Advertisements
can be used to build trees, it will be good if tree
building and/or maintenance can be performed independently
of Router Advertisements.  They add too much overhead
to make it easy to react quickly to changing conditions.

                                   -Richard Kelsey

---

From: Zach Shelby <[email-masked]>
Date: Sat, 11 Apr 2009 10:07:14 +0300

Richard,

> to make it easy to react quickly to changing conditions.

Don't think of router advertisements as overhead - as we are working 
with IP networks you will always have RAs as they are an integral part 
of network bootstrapping and maintenance (Neighbor Discovery). As you 
have RAs anyways, you might as well piggyback some tree information. 
Trickle can also be used to optimize the RA traffic to an appropriate 
level.

The same can be said about other ND traffic in these networks such as 
NS/NAs (IPv6), or RR/RCs (in 6LoWPAN). If you have the ND traffic 
anyways, piggybacking is good.

That said, I do see the need for carrying metric information (as done in 
the CTP protocol Phil is referencing) in data traffic (using an IPv6 
hop-by-hop option) especially for very dynamic networks. I had this in 
mind when we wrote the Routing Fundamentals draft as an option. From my 
practical experience it is useful, and only needs to be applied to 1-10% 
of data packets depending on how dynamic the network is.

- Zach

>                                    -Richard Kelsey
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

-- 
http://zachshelby.org - My blog “On the Internet of Things”
Mobile: +358 40 7796297

Zach Shelby
Head of Research
Sensinode Ltd.
Kidekuja 2
88610 Vuokatti, FINLAND

This e-mail and all attached material are confidential and may contain 
legally privileged information. If you are not the intended recipient, 
please contact the sender and delete the e-mail from your system without 
producing, distributing or retaining copies thereof.

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 13 Apr 2009 06:04:42 -0400

Date: Sat, 11 Apr 2009 10:07:14 +0300
   From: Zach Shelby <[email-masked]>

   > to make it easy to react quickly to changing conditions.

   Don't think of router advertisements as overhead - as we
   are working with IP networks you will always have RAs as
   they are an integral part of network bootstrapping and
   maintenance (Neighbor Discovery).  As you have RAs
   anyways, you might as well piggyback some tree
   information.

To be pedantic, they aren't application payload, so they are
overhead.  That wasn't the point I was making, though.

The piggybacking only works if there happens to be an RA
going out around the time that new tree information needs to
be sent.  Am I missing a connection between the two that
makes this likely?  The Collection Tree Protocol mentioned
above reacts to topology changes within a second or two.  I
don't know if that low a response time is necessary, but it
does seem clear that tree topology will sometimes be
changing much faster than the data in the RAs.  If new tree
information needs to be sent, but new RA information does
not, then the RA data is overhead.

I am not suggesting that we not piggyback tree information
on RAs, just that it would be good to also be able to
piggyback it on other messages or send it independently.

                               -Richard Kelsey

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 14 Apr 2009 16:46:57 +0200

Hi Richard:

The routing - that builds the tree - in the fundamentals draft reacts
lazily to metrics changes, so seconds are OK, even way longer and that
can match an acceptable RA period. The reason is that changing the tree
has more dramatic impacts then just forwarding over a better parent.

The catch is that the forwarding reacts a lot quicker, and yes, another
(faster) way to carry the metrics would be very helpful. The draft
mentions an out-of-band forwarding protocol in [6.2.3. Graph
forwarding], and in-band piggy backed with data could be used too as
Zach indicates.
 
Pascal

>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Richard Kelsey
>Sent: lundi 13 avril 2009 12:05
>To: [email-masked]
>Cc: [email-masked]
>Subject: Re: [Roll] FW: New VersionNotification for
draft-thubert-roll-fundamentals-01

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 14 Apr 2009 16:49:09 +0200

Thanks Phil :) 

Pascal

>From: Philip Levis [mailto:[email-masked]]
>Sent: vendredi 10 avril 2009 15:52
>Subject: Re: [Roll] FW: New Version Notification for

---

From: Philip Levis <[email-masked]>
Date: Tue, 14 Apr 2009 16:52:38 -0700

> overhead.  That wasn't the point I was making, though.

Even if it isn't the point you were trying to make, I'd agree with  
it. :) It's hard to say that a routing protocol is efficient if it  
sends 1000 RAs for every data packet. At the most abstract level, a  
protocol's overhead is (total bytes - data bytes)/data bytes. That  
being said, the presence of energy as a critical metric means that  
there can and are situations where higher overhead can lead to greater  
efficiency. For example, a header field that gives some sort of  
rendezvous timing as in Jonathan's IP stack.

> above reacts to topology changes within a second or two.

Even faster -- one experiment we did on this saw 10-15 packet times,  
which was 200-300ms. It turns out that, for 802.15.4 at least, in  
tough environments links tend to have a coherence time around 500ms,  
so you'd like to be able to either react much faster or much slower  
than that. Faster so you don't keep on hammering a bad link, or slower  
so that the next transmission is a random coin toss.

>  I

I agree with this: it's the exact problem that adaptive beaconing  
tries to solve. Any periodic RA mechanism introduces a tough tradeoff:  
beacon faster for fast adaptation but high cost, or beacon slower for  
efficiency but slow adaptation.  Hence the point of borrowing and  
extending Trickle -- send just enough RAs for nodes to discover each  
other and verify that the tree is still consistent. Data path  
validation allows the protocol to verify the tree's consistency  
without introducing additional (RA) overhead.

> piggyback it on other messages or send it independently.

The design question here is *what* information to piggyback. One  
interesting way that the paper I sent out differs from Jonathan's IP  
stack is his stack includes hop count in data packets (Section 8.1.4  
of the SenSys 2008 paper). From an academic standpoint, it would be an  
interesting evaluation to see whether the cost of this field is less  
than the cost of false positives on CTP's loop detection (the case  
where a node's ETX goes up but its children don't know yet, so it  
thinks there might be a loop). I say it's academic because my guess is  
that it's a comparatively small difference either way, compared to  
other, more important issues.

Om -- this might be a nice experiment to look at from the traces, just  
compute how often CTP beacon resets are false positives on loop  
detection.

Phil

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 15 Apr 2009 12:58:17 +0200

Hi Phil,

The fundamentals draft was published as a proposed approach to the
problem - basically build a tree, forward over a graph, and then provide
additional optional features. 

This draft being done, I'm happy to switch to a DT hat and discuss if
such an approach is desirable. If that's so, CTP presents a number of
advantages for building the tree that the DT will certainly recognize. 

The cool thing is that from the very beginning of the IETF work, we
already have a wealth of ideas and experiments on the table. Considering
the schedule we have, this existing art is certainly welcome.

Pascal

>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Philip Levis
>Sent: mercredi 15 avril 2009 01:53
>To: Richard Kelsey
>Cc: [email-masked]

---

From: JP Vasseur <[email-masked]>
Date: Fri, 17 Apr 2009 10:41:04 +0200

Hi Zach,

On Apr 11, 2009, at 9:07 AM, Zach Shelby wrote:

>>   > Basically, since we have a depth, we have feasible parents  
>> (of     > lesser depth) and siblings (of same depth). The draft  
>> suggests that     > we can select any parent to forward on a per  
>> packet basis using the     > best metric or more advanced load  
>> balancing functionality; if that     > fails then we can use a  
>> sibling with some basic loop avoidance like     > poison return or  
>> more advanced path vector (for hydrophiles).
>>   Here's a URL to a paper that describes one way to solve this  
>> problem,     using the techniques I mentioned a few weeks ago and  
>> touched on in my     talk in SF:
> with IP networks you will always have RAs as they are an integral  
> part of network bootstrapping and maintenance (Neighbor Discovery).  
> As you have RAs anyways, you might as well piggyback some tree  
> information. Trickle can also be used to optimize the RA traffic to  
> an appropriate level.
>
> The same can be said about other ND traffic in these networks such  
> as NS/NAs (IPv6), or RR/RCs (in 6LoWPAN). If you have the ND traffic  
> That said, I do see the need for carrying metric information (as  
> done in the CTP protocol Phil is referencing) in data traffic (using  
> an IPv6 hop-by-hop option) especially for very dynamic networks. I  
> had this in mind when we wrote the Routing Fundamentals draft as an  
> option. From my practical experience it is useful, and only needs to  
> be applied to 1-10% of data packets depending on how dynamic the  
> network is.
>

I do agree with you ... Just a word of cautious though. Piggybacking  
can be an interesting option but we need to be a bit careful at not  
spreading out routing control plane traffic in N existing protocols.  
In this particular I do not want to wait for traffic to make my  
routing decision.

Cheers,

JP.

> This e-mail and all attached material are confidential and may  
> contain legally privileged information. If you are not the intended  
> recipient, please contact the sender and delete the e-mail from your  
> system without producing, distributing or retaining copies thereof.

---

From: JP Vasseur <[email-masked]>
Date: Fri, 17 Apr 2009 10:49:43 +0200

[snip]

> tries to solve. Any periodic RA mechanism introduces a tough  
> tradeoff: beacon faster for fast adaptation but high cost, or beacon  
> slower for efficiency but slow adaptation.

Right and this is not specific to RA but any routing protocol control  
plane.

Look at routing protocol such as OSPF. If you quickly want to detect a  
failure, you increase the periodic hellos or use BFD: more overhead,  
higher cost faster reaction. It is just that in LLN higher cost is a  
serious issue, thus the need for Trickle but I do not need to convince  
you there ;-)

> Hence the point of borrowing and extending Trickle -- send just  
> enough RAs for nodes to discover each other and verify that the tree  
> is still consistent. Data path validation allows the protocol to  
> verify the tree's consistency without introducing additional (RA)  
> overhead.

There seems to be a confusion floating around: we do not need to  
recompute the tree/DAG to find an alternate path. The backup path MUST  
be in place before any failure thanks to the use of an alternate  
parent/sibling in forwarding or alternate parent in a DAG or alternate  
tree.

> of the SenSys 2008 paper). From an academic standpoint, it would be  
> an interesting evaluation to see whether the cost of this field is  
> less than the cost of false positives on CTP's loop detection (the  
> case where a node's ETX goes up but its children don't know yet, so  
> it thinks there might be a loop). I say it's academic because my  
> guess is that it's a comparatively small difference either way,  
> compared to other, more important issues.
>
> Om -- this might be a nice experiment to look at from the traces,  
> just compute how often CTP beacon resets are false positives on loop  
> detection.
>
> Phil
>
>

---

From: Richard Kelsey <[email-masked]>
Date: Fri, 17 Apr 2009 13:56:42 -0400

From: JP Vasseur <[email-masked]>
   Date: Fri, 17 Apr 2009 10:49:43 +0200

Does the requirement for a backup path stem from some
particular reliability or latency requirement?  Whether
having a precomputed backup path performs better or worse
than a local on-demand tree recomputation would seem to
depend on the particular details of the protocols used and
the stability characteristics of the network.  For example,
it isn't at all clear to me how configuring redundant paths
using HYDRO would perform compared to the Collection Tree
Protocol's local recomputation.  It would be interesting to
try them both out on a selection of deployed networks; it
would also be a lot of work.

                               -Richard Kelsey

---

From: JP Vasseur <[email-masked]>
Date: Fri, 17 Apr 2009 20:04:37 +0200

Hi Richard,

> would also be a lot of work.

The major advantage of "local reroute" is not only to improve the  
convergence
time but also to limit the repair scope as opposed to recompute an  
entire tree/DAG/...

Cheers.

JP.

---

From: Philip Levis <[email-masked]>
Date: Fri, 17 Apr 2009 11:50:23 -0700

> time but also to limit the repair scope as opposed to recompute an  

The problem with pursuing stability is that it comes at a cost of  
efficiency. I think that one of the lessons you can draw from the CTP  
paper, and wireless measurement studies in general, is that the idea  
of "convergence time" is a red herring. It implies that the underlying  
wireless network is itself stable on time scales well beyond a few  
packets, suggesting there is some notion of the "true" network  
topology that you wish to converge to. But this is often really not  
the case. You can pick only highly stable links with a high SNR, but  
in so doing waste energy. Furthermore, interference means that the  
link-layer topology itself changes with load.

That being said, limiting repair scope is a good design principle.

Phil

---

From: Kris Pister <[email-masked]>
Date: Sat, 18 Apr 2009 15:39:16 -0700

Let's be careful to stay link agnostic.  Convergence time is definitely 
not a red herring with a channel hopping 15.4 wireless DLL, for 
example.  If you hop on at least a handful of channels in the 2.4GHz 
spectrum your links are in fact stable on time scales well beyond a few 
packets.  Individual channels often vary from 100% to 0% PDR and back 
again on short time scales, but the link average remains relatively 
constant in commercial and industrial environments over periods of hours 
to months.
In many of these networks there really are long-lived "true" network 
topologies, and corresponding optimal routes.
I imagine this will also be true for networks with PLC links as well.

ksjp