Subject: [Roll] ROLL and new technology

From: Richard Kelsey <[email-masked]>
Date: Fri, 03 Jul 2009 11:41:42 -0400

ROLL has a very aggressive schedule.  The argument was that
we could make rapid progress by building on existing
protocols that are already in use.  That doesn't seem to be
what we are doing.  In particular, there are a number of
mechanisms in draft-dt-roll-rpl-00 which I do not believe
have seen widespread use.  Some of them have been discussed
on the mailing list.  The nature of those discussions
indicates that those features are neither well understood or
in common use.

I am not saying that we shouldn't use any or all of these,
or even necessarily singling out these particular features.
My point is we should strongly limit the amount of algorithm
development that we undertake.  This is a time for refining,
not inventing.

 - using separate metrics for loop avoidance and for parent
   selection

 - allowing a node to have multiple parents (using a DAG
   instead of a tree)

 - using Trickle to suppress DAG (or tree) discovery
   messages

 - routing messages via siblings

 - the Destination Advertisement mechanism

I am certainly not aware of everything in IP or in the
sensor network space.  If any of these are widely used, I
suggest that we make sure we are not modifying them in
significant ways.

There are a lot of ROLL-style networks out there today.  If
the routing algorithms they use are good enough, and I
believe that they are, then weshould use the same
mechanisms.  If they are not good enough, then we will have
to back off on the schedule.

                                -Richard Kelsey

---

From: JP Vasseur <[email-masked]>
Date: Fri, 3 Jul 2009 18:16:38 +0200

Hi Richard,

Few observations in line.

On Jul 3, 2009, at 5:41 PM, Richard Kelsey wrote:

> protocols that are already in use.

This was not the argument. The reason for this aggressive schedule is  
the urgent need
to have a routing solution for LLN. As spelled out in our charter, we  
could either extend
an existing protocol or define a new one, or any mix of the two.

> That doesn't seem to be

I do agree with you that some of the proposed features need  
clarifications and require
further discussion and agreement. Bear in mind that we have 3  
candidates among which
the DT draft that was posted in its first revision a few days ago.

> to back off on the schedule.

This is why we have a WG: to discuss and agree on what the solution  
should look like.
I am agreeing with you here on the fact that there is no need to re- 
invent the wheel if
something exists that works and satisfies our requirements. On the  
other hand, there is
no need to prevent ourselves from inventing something new. We need to  
find the right
trade-off.

If you have a solution that you think works, please propose it and it  
will be discussed in the
WG of course.

Thanks again for your excellent contribution to the WG by the way.

JP.

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

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Sat, 4 Jul 2009 14:48:12 +0200

Hi Richard:

There is a wide consensus even in implementations to go for a Distance
Vector approach.

- Good thing, DV properties are very well know. We know RIP and its
limitations, and we know that even in a clean wired space it would not
fit the scale that we are considering.

- Good thing, DV technology has evolved since then, and the techniques
employed in IGRP and EIGRP have been widely deployed and verified over
the last decade.

I cannot argue on the specific implementation that you know best. 
All I can say is that it is:

1) *inacceptable* to be content with the basic RIP mechanisms (INFINITY
is 16 there for a reason or 2)
2) *useful* to learn from more modern DV protocols (route poisoning, 
3) *necessary* to adapt to the LLN constraints and requirement 

>have seen widespread use.  Some of them have been discussed

As you might have experienced yourself if you tried it and as the
protocol designers well warned, RIP is generally recognized as wholly
inadequate for large and complex networks (slow and costly due to count
to infinity). 

Since RIP, a number of DV improvements have been integrated in IGPs:
-	Source tracing (too costly for us in terms of states)
-	Composite metrics (IGRP, we're doing our on as part of the
metrics work; trick is whether one fits it all forever and consequences
if not)
-	Path holddown (early IGRP) 
-	Route poisoning (Later IGRP, improves Path holddown) 
-	Distributed Update ALgorithm (DUAL, in EIGRP) the diffusion
algorithm prefers to create a temporary black hole than a loop, and
saves on control to resolve the routing issue.

You'll realize that RPL inherits from those with a few tweaks to support
adhoc & mobility:
-	In particular, RPL benefits from the properties that were
demonstrated by Garcia-Luna-Aceves for DUAL like you can safeluy move
towards the root but cannot move down.
-	Yet RPL does not require reliable multicast for diffusion like
EIGRP does, the trade off is that it is not always loopless unless the
sequence is used. 

The main tweaks are
-	The way a node is frozen (being frozen in RPL == pertaining to a
new DAG id of the node that found the breakage) 
-	and unfrozen (tree hop timer + seq as opposed to EIGRP query /
reply)
-	The DAG hop timer to merge back DAGs (saves additional control
messages, to do things orderly as opposed to swiftly)

In the distributed update algorithm a router that discovers that it will
get deeper becomes 'active'. It locks its routing table and diffuses the
information. RPL does that by leaving the DAG and belonging to the self
rooted DAG of the parent that discovers the breakage. The diffusion
happens recursively: a child that has a solution to stay in the main DAG
stays "passive" by remaining in the main DAG but losing that parent. A
child that cannot freezes by following its parent in the detached DAG.

> - using separate metrics for loop avoidance and for parent selection

A node makes its own decision to select one or a number of other nodes
as parents. That decision is ruled by the node's specific logic I call
plugin for the lack of a better term. This comes from the fact that a L3
protocol works on abstractions that must be valid on multiple types of
links and environments. We can't expect a single metric to express what
we need to express to make a parent selection in ROLL. So we just took
it off, this much is out of scope and will be instantiated per need. So
you can have your own plugin that does exactly what your implementation
does today to select a best parent.

At that point you'll have to interact with nodes from different vendors
and different generations, so you need to sort out a common metric to be
avoid loops and guarantee stability. Separating the 2 actually gives you
a lot more latitude in parent selection than enforcing any specific (set
of) metric and logic.

> - allowing a node to have multiple parents (using a DAG instead of a
tree)

It is pretty clear from the requirements, though, that any spec that
does not allow forwarding across multiple parents *is out*. Note that
the fundamentals draft allowed that too. Now you can use RPL to build a
tree if you limit to a single parent, so the protocol enables that as a
degenerated case, like it allows the depth metric to be the parent
selection metric as another degenerated case.

> - routing messages via siblings

That does not represent an uncontrolled risk. It mostly a way to improve
on traditional DAG thinking to get more fwd solution, then again a MUST
for LLNs. We note that having multiple parents and siblings enables the
routing part that built the graph to let some latitude to the component
that selects the next hop for a given packet. That feature is *heavily
required* in LLNs because the link conditions can change a lot faster
than the graph construction can cope with.

> - the Destination Advertisement mechanism

Yet another low risk technique because this mechanism does not draw the
graph, it merely colors it. And it is triggered only for destination
that need it so it is optional in a given deployment though required in
implementations. 

There are only 2 ways to do that simply, either sync db (ala OSPF) or
repeat over and over (ala RIP). For the sake of simplicity and because
of the mobility that's inherent to LLNs, the draft picked the latter.
And yes, there are implementations of this that have been operated in
multiple environments, radio and wired. On the Moon I'm unsure but maybe
soon :)

What I see here is a set of adaptations of rather well known techniques
in the DV family plus a set of adaptations to meet LLN requirements.
Pretty much what ROLL is chartered to do. There's still a lot of tuning
to do but the main lines seem properly defined...

Pascal

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Richard Kelsey
>Sent: vendredi 3 juillet 2009 17:42
>To: [email-masked]
>Subject: [Roll] ROLL and new technology
>

---

From: Alexandru Petrescu <[email-masked]>
Date: Sat, 04 Jul 2009 15:14:33 +0200

> There is a wide consensus even in implementations to go for a Distance

IMHO Distance-Vector protocols (a node sends to its immediate neighbors 
the distance it knows from everybody else, and Bellman-Ford path 
computation) are better when there are a few (if not one) backbone links 
and the distances are small, RIP less than 15.

However, in the example picture in the graph we can't see such structure 
of the network: there are many edges, no priviledged backbone.

At the same time, sensors are probably having a single interface, and 
thus pertain to a potential backbone picture: all sensors are connected 
to one or a few such backbones.   But the graph in the RPL draft shows a 
sensor with many more interfaces.

If we knew how many interfaces does a ROLL node have, and what is the 
structure of the network - a little more than just an arbitrary graph, 
then we could make decisions on the type of protocol - distance-vector, 
link-state, vector-path, and more combinations.

With a totally arbitrary network of links like a random graph it's 
difficult to say that Distance Vector protocols are recommended.

Alex

---

From: Richard Kelsey <[email-masked]>
Date: Sun, 05 Jul 2009 18:17:17 -0400

Date: Sat, 4 Jul 2009 14:48:12 +0200
   From: "Pascal Thubert (pthubert)" <[email-masked]>

I completely agree.

The only core algorithmic difference between RIP and RPL is
how loop detection is done.  Everyone, including myself,
agrees that RIP's counting-to-infinity won't work.  Many
people agree that RPL's hop count won't work either.

I have never proposed using RIP's loop detection mechanism
for ROLL.  It is obvious that it won't work.

My draft-kelsey-roll-lip-00 uses (or was intended to use,
the draft explicitly does not specify a complete routing
protocol) the data traffic path validation of the Collection
Tree Protocol (CTP).  The draft was a result of my noticing
that CTP and RIP have nearly identical routing control
frames, modulo the sizes of the fields.  CTP appears to be
simple, dynamic, and robust, which for me are the main
requirements of a ROLL protocol.

(The other main idea in the draft, using CTP/RIP in the
context of MPLS, made it easy to add CTP's path-cost field
to data messages and also allowed source routes to be added
and removed when a packet crosses in and out of a ROLL
subnet.  The subnet-local source routes can then be used for
outward routing within the tree.)

Absolutely.  My main concern with RPL is that it fails to
adapt to LLN constraints and requirements.  But we disagree
on this.

   [much interesting discussion of individual features
   removed]

   What I see here is a set of adaptations of rather well
   known techniques in the DV family plus a set of
   adaptations to meet LLN requirements.  Pretty much what
   ROLL is chartered to do. There's still a lot of tuning to
   do but the main lines seem properly defined...

And here too we disagree.  To me the discussions on this
list (does hop count trump other metrics, how does having
multiple metrics interact with having multiple parents, for
example) are evidence of this.

My main concern is that RPL is significantly more complex
than the existing WSN routing protocols that I have used or
am familiar with.  More complex protocols take longer to
develop than simpler ones, and tend to be less robust.

                                   -Richard Kelsey

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 6 Jul 2009 10:23:36 +0200

Hi Richard:

RPL definitively tries to endorse the good ideas in CTP. There are 2
main ones, the forwarding time path validation and trickle. We spent
most of our time on the trickle piece, and that's not finished as you
saw on the list. The path validation is on the shelf, ready to be
included depending on the exact properties of the RPL protocol as some
final decisions are made.

>   I cannot argue on the specific implementation that you know best.

This is not about implementation. This is about widely deployed
protocols (IGRP, EIGRP) that brought and validated improvements on DV
that we need to understand and figure how we can reuse. It's very clear
to me that the IETF has enough experience on RIP to know that it fails
to pass our requirements (scalability, cost and time of convergence)
without such improvements. 

So the question for RPL was really how can we simply adapt those proven
ideas. What you're doing there with CPL, we also did with modern DV
IGPs. Before you reject our work, you need to understand those
principles, how they work and then you can figure out whether RPL
inherits properly those proven properties.

My point here is that we are going L3. We need to learn from both sides,
IETF and WSN engineering, and make sense to the cross-breeding. You
can't just reject the experience form the other side because you're not
familiar with it.

Same goes for the metric. Going L3 means that you can't use your
traditional radio metric(s) as-is. You need to abstract and generalize.
We are talking here about an abstraction that can be instantiated on
many sorts of radios, powerline, infrared/laser, sat, you name it.

Same goes for interoperation and expected deployments. We are not
talking about a topical setup based on an homogeneous proprietary
implementation by one brand. We are talking about interoperation across
brands and generations of device.

I think I understand your point on risks exploring terra incognita. I'd
argue that the terra is less incognita as you might think if you include
the DV experience that I already mentioned in this thread (path
holddown, route poisoning, DUAL). I'd turn the question into whether you
can use the RPL model to do exactly what you want to do, or what it
would take, like allowing to increment the depth by more than one for
instance.

Pascal
>From: Richard Kelsey [mailto:[email-masked]]
>Sent: lundi 6 juillet 2009 00:17
>To: Pascal Thubert (pthubert)
>Cc: [email-masked]
>Subject: Re: [Roll] ROLL and new technology
>

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 06 Jul 2009 08:04:20 -0400

Hi Pascal,

   Date: Mon, 6 Jul 2009 10:23:36 +0200
   From: "Pascal Thubert (pthubert)" <[email-masked]>

   >   I cannot argue on the specific implementation that you know best.

   This is not about implementation. [...]

You wrote that line, not I.

   My point here is that we are going L3. We need to learn
   from both sides, IETF and WSN engineering, and make sense
   to the cross-breeding. You can't just reject the
   experience form the other side because you're not
   familiar with it.

Many of the things in RPL have been tried before in the WSN
community.  I am unhappy with them precisely because they
are familiar.  I know the problems that are going to arise
because I have already seen them happen.

I am not rejecting the ideas in RPL.  I have been pointing
out flaws that need to be fixed and arguing that given the
tight schedule we need to stick to what is already in use
rather than inventing something new.

                               -Richard Kelsey

---

From: JP Vasseur <[email-masked]>
Date: Tue, 7 Jul 2009 14:29:11 +0200

Hi Richard,

>  experience form the other side because you're not

You are perfectly when saying that both communities may benefit from  
the experience
of each other. It has been a challenge since day 1 *but* we are all  
making excellent
progress with a community that now "almost" speak the same language  
and thanks
to all of you for the time and energy to make it a success.

> rather than inventing something new.

Flaws must be resolved, I fully agree and I also have some concerns  
(like the DT) about
some of existing mechanisms. The lack of determinism worries me, and  
we cannot rely on
a solution that does not allow to re-attach to a deeper node that  
offers a better path.
Let's collectively work on those issues.
I asked the DT to provide more explanation how the design choices  
thanks to concrete examples.
Let's use them to work this out.
Then the best thing to do is I think to work on these issues one by one.

One last note, we cannot because of the timing reject new ideas (still  
we need to be cautious !),
since we first need a solution that works.

Thanks.

JP.