Subject: [Roll] Some clarifications on RPL

From: Tim Winter <[email-masked]>
Date: Sun, 05 Jul 2009 18:52:07 -0400

WG,

Thanks to everyone for their feedback and comments to the RPL draft so far.
There are some good threads here that will definitely help us to improve
the RPL design- and there is no doubt more work to be done.  I would like
to make some clarifications that may be useful in discussing some of the
common concerns so far:

1) Why a DAG?
        A dominant traffic flow in the requirements drafts is MP2P, flowing
from the sensors inwards towards a sink, typically an LBR.  The design
approach taken was to handle this case, use it to restrict the routing
problem, and then try to build support for P2MP, P2P, and other cases on
top of it.  A tree provides the simplest structure for supporting the MP2P
flows, but a tree has many single points of failure along the edges from
children to parents.  A DAG, allowing each node to select and maintain
multiple successors in order to forward traffic inwards toward the root,
offers the advantage of ready-to-use options.  An implementation may then
select from the successors as necessary, possibly in response to a
temporary failure to forward to one parent, or a load balancing algorithm,
or a short-term fluctuation in a link metric that leads the forwarding
engine to prefer one next hop over the other.

2) What about other flows?
        The DAG, and the orientation of the edges in the DAG, is used in
routing the MP2P traffic towards the DAG root.  The structure of the DAG is
then used to restrict the complexity of the P2MP routing problem on the
nodes.  The Destination Advertisement mechanism lets a node set up routes
in support of outward traffic flows, from the DAG root towards the leaf
nodes in the LLN.  The Destination Advertisement mechanism distributes
routing state inwards along the DAG, allowing nodes to learn routing state
in support of the sub-DAGs below them.  Nodes who are unable to learn
routing state pass the Destination Advertisements inward, building up
source routing information along the way so that they may be traversed
again on the outward flow.  The exact implementation of source routing in
support of this mechanism is not something that has been addressed by RPL
as yet.

        Further, arbitrary P2P traffic can be supported by the DAG as is by
sending traffic inwards along the DAG until a parent is encountered, who
has stored routing state and is common to the source and destination of the
traffic, who is able to direct the traffic towards the destination.

        RPL does not discuss any mechanisms to install more optimal P2P
routes, but nor does it preclude them, once the fundamentals have been
addressed we can have a look at such mechanism to more efficiently route
`across' the DAG.

3) Metrics
        RPL allows for each node to select its set of DAG parents according
to its own set of constraints, utilizing whatever subset of metrics it
requires to do so.  The exact considerations and weighting can be
implementation specific.

        A key design point, one that may need to be further constrained, is
that under RPL each node does not assume that other nodes are acting
cooperatively, or even that they are using or understand the same set of
metrics.  One node could be optimizing for latency, another node could be
optimizing for ETX, and a third could be optimizing for
minimum energy.  This design point informs some of the loop avoidance
rules, such as the use of depth as a `common language'.

        Once a node as selected its DAG parents, according to whatever
metrics and constraints it chooses, then it has effectively taken up a
position in the DAG.  It now has a best-case path to the DAG root, through
its best parent, and a worst-case path to the DAG root, through its worst
parent.  Now, as a *consequence* of selecting parents according to its
metrics, the node has taken on a depth within the DAG.

4) Loop avoidance
        The DAG, and the nodes position within the DAG, are used in support
of some loop avoidance rules.

        RPL always allows a node to move inwards along the DAG, towards the
root.  Moving inwards along the DAG has little chance of creating a loop;
the node has only improved its position.  Such a move would be based on
receiving and processing DIOs with superior metrics from a node of a lesser
depth in the DAG.

        RPL does not allow a node to move outwards along the DAG,
increasing its depth.  Such a move is possible, but would require the node
to leave the DAG, wait for a DAG Hop timer to elapse, and then re-attach at
the lower point.  RPL would not allow this movement unless the DAG parents
of the node have failed, requiring the node to detach and re-attach to the
DAG.

        In general, RPL is taking a conservative approach.  For a node N,
any node M such that depth(M)>depth(N) MAY be in the sub-DAG of
node N.  Suppose that node N thought it could improve its metrics through
node M.  By detaching first, and waiting to observe node M to see that node
M remains attached to the DAG, node N may then determine that node M is not
part of its own sub-DAG and may safely re-attach at the lower point. BUT if
node N is wrong, then an instability has been created for no gain.
For this reason, in its current specification, RPL does not allow a node N
to process and DIO from node M and detach from the DAG based on information
in the DIO from node M.  NOTE that this is in part a consequence of the
design consideration that not all nodes may be using the same metrics and
making the same optimizations.  For example, if all nodes in the network
were minimizing ETX, then node N may be mostly certain that any node
M advertising a superior ETX is NOT in its own sub-DAG.

        A further complication may come if node N and node M are trying to
make optimizations which are antagonistic to each other.  For example, if
node N where to try to move under node M, it could create a chain of events
whereby node M tried to reverse its position with respect to node M, and a
chain reaction of instability could result.  A simple example of such a
case would be where both nodes M and N have a common neighbor and parent P,
and nodes M and N subsequently each try to increase the size of their
parent set to be 2.  (This case has been more thoroughly explained by
Pascal, see "Re: [Roll] Fwd: I-D Action:draft-dt-roll-rpl-00.txt Q1" sent 30
June 2009.)

        RPL has nodes advertise a depth deeper than that of their deepest
DAG parent.  Consider an example where node X has parents of depth {2, 7},
and node Y chooses X as a parent.  Suppose that nodes then advertise their
`best' depth, i.e. node X advertises a depth of 3.  Then node Y will
advertise a depth of 4.  Then suppose node Z adds node Y as a parent, and
advertises a depth of 5.  Now, Z can actually come to be a successor of
node X's depth 7 parent.  The result could be Z->Y->X->(cost 7
parent)->(...)->Z and then there is a loop.  By advertising a depth deeper
that of its deepest parent, a node advertises its worst case scenario, and
in the worst case scenario a loop can be avoided.

        RPL does not require that the DAG is invariant, rather that the
movement of the node with respect to the DAG is coordinated in such a way
so as to avoid loops.  The thought is, whatever the topology, uncoordinated
movement in LLNs may increase overhead and churn and require more reliance
on expensive mechanisms such as count-to-infinity.

        The use of depth (~ hop count) in RPL is not meant to trump other
metrics, but once a node has taken up a position in the DAG by using its
metrics the node acquires a depth, which then restricts the further options
that the node has in order to avoid loops.

Regards,

-Tim

---

From: Richard Kelsey <[email-masked]>
Date: Sun, 05 Jul 2009 22:16:19 -0400

Date: Sun, 05 Jul 2009 18:52:07 -0400
   From: Tim Winter <[email-masked]>

           [...] Nodes who are unable to learn

In general, is adding an IP source route to a forwarded
packet allowed?  Could a root add a source route to an
incoming packet before forwarding it down the DAG?

   3) Metrics
   minimum energy.

This doesn't seem very useful to me.  To the extent that
these three are independent, you could easily end up with
routes that were bad at all of them.  Why is this a key
design point?

Also, it seems to me that this interacts poorly with having
a DAG.  With a tree a node receives a single value for each
metric from its parent.  With a DAG, one parent may have a a
low latency but high energy cost while another parent has
high latency and low energy cost.  What metric values should
the child advertise?

Given the dubious benefits of having different nodes
optimize different metrics, and the bad interaction with
having multiple parents, I really don't understand the
emphasis on this feature.

                                    -Richard Kelsey

---

From: Mukul Goyal <[email-masked]>
Date: Sun, 5 Jul 2009 22:13:17 -0500 (CDT)

Tim

Thanks for this explanation. I think most of this email should become part of RPL draft. 

I would like to convey the discomfort that many of us feel because RPL does not yet support a good P2P routing solution. Tree based P2P routing is not acceptable in many cases. We need to give this problem a high priority.

Thanks
Mukul
  
----- Original Message -----
From: "Tim Winter" <[email-masked]>
To: "ROLL WG" <[email-masked]>
Sent: Sunday, July 5, 2009 5:52:07 PM GMT -06:00 US/Canada Central
Subject: [Roll] Some clarifications on RPL

WG,

1) Why a DAG?

3) Metrics

4) Loop avoidance

Regards,

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

---

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

Hi Mukul,

On Jul 6, 2009, at 5:13 AM, Mukul Goyal wrote:

> I would like to convey the discomfort that many of us feel because  
> RPL does not yet support a good P2P routing solution. Tree based P2P  
> routing is not acceptable in many cases. We need to give this  
> problem a high priority.
>

The solution MUST of course support P2P and this is the case of RPL.  
Now we need to define what we mean by "Good" P2P routing solution. As  
of today RPL will branch the traffic as soon as the packet reaches a  
node that has the destination address in its routing table pointing to  
one of its children or sibling. This path may not be the most optimal  
path indeed and may even be unacceptable. Furthermore it is  
constrained by the shape of the DAG, which are dependent upon the  
metrics used by nodes closer to the root. The question is to determine  
how optimal should that path, and should we decide to adopt a routing  
solution a la RPL, do we need to complement it with another mechanism  
when optimal P2P path are required ?

Thanks.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Tue, 7 Jul 2009 15:16:53 +0200

Hi Tim,

Thanks for taking the timing to write this text,

> engine to prefer one next hop over the other.

Note also that one may decide to make use of more than one DAG for the  
same destination, when DAGs may be used using different metrics or  
constraints.

> support of this mechanism is not something that has been addressed  

The choice was made to make it an open item. Options (to be discussed  
later on in the WG) are (compressed) IP source routing or label  
switching.

> traffic, who is able to direct the traffic towards the destination.

Let's just point out that the level of optimality of that P2P route is  
not deterministic and more optimal P2P path may require additional  
functionality to be defined.

> requires to do so.  The exact considerations and weighting can be

I would like to mention that the use of non coherent policy between  
nodes may lead to some undesirable lack of determinism in the DAG  
optimality. Should RPL be adopted by the WG, this will be discussed in  
the METRIC ID.

> optimizing for ETX, and a third could be optimizing for

This is a point I am not comfortable with since the result is simply  
not deterministic and may not make any sense .... still provides a  
"path" but the use of non coherent metrics means not using any metric.

My proposal is to add the selected metric advertised in the RA at a  
minimum.

Let's flag this as an open issue and discuss it in Stockholm.

> This design point informs some of the loop avoidance

Which may or may not be acceptable since it requires a temporary loss  
of connectivity with no guarantee that a better route exists. We need  
to discuss the ability to still listen RAs from deeper nodes.

> in the DIO from node M.

Currently traveling (not easy to draw a picture ...) but it could be  
useful to illustrate such instability with an example ... and add it  
to the ID (to be removed eventually or moved to an appendix).

> NOTE that this is in part a consequence of the

Yet another reason for using a consistent metric (although not  
sufficient).

> Pascal, see "Re: [Roll] Fwd: I-D Action:draft-dt-roll-rpl-00.txt Q1"  

Our well-known count to infinity problem if we do not poison. But  
ignoring RAs does not allow for finding more optimal routes unless  
explicitly detaching. Let's add Pascal text in there.

> DAG parent.

Just mention that this is to avoid loops.

> Consider an example where node X has parents of depth {2, 7},

That is a weak point that we need to address though.

Cheers.

JP.

---

From: [email-masked]
Date: Tue, 7 Jul 2009 15:46:40 -0500

JP,

I agree with Mukal. 

If two or more nodes are all within radio proximity and hence neighbors 
they should all be able to exchange messages amongst themselves without 
needing to traverse the DAG.  In the commercial building environment this 
will happen in the equipment rooms.  These rooms are electromechanical 
rooms holding air handling, heating and air conditioning equipment.  There 
may me as many as 20 controllers (routing devices), 20 sensors and 20 
actuators (non-routing devices) all in the same 500 sq ft room.  The 
concept of finding candidate parents and connecting into the DAG for this 
simple communication seems to be overkill.

I am only to page 41 of the draft and may be pleasantly surprised as I 
read on; but the sense I have of the draft so far is it is optimizing 
router efficiency of devices (i.e. no loops) while ignoring the logical 
cohesion of many of the devices.  Again, in a commercial building there 
are hundreds of rooms.  Each room is a microcosm of the overall network 
(e.g occupancy, lights, heating/cooling, shade control).  For the most 
part these devices are completely independent of all the other rooms. They 
should be able to communicate bidirectionally and freely amongst 
themselves with minimal impact to the rest of the LLN. 

The DAG discovery and maintenance policies described in the draft looks 
like each device positions itself on the DAG as best as it can and then 
communicates as high up and then back down the DAG as necessary to reach 
its intended destination.  I would think this would create an unbalanced 
network traffic where the higher layers are unfairly taxed at forwarding 
uninteresting messages while the lower layers are awaiting message 
delivery.  As I mentioned in a previous email, this architecture tends to 
make some devices more important to the LLN than others which has negative 
fault tolerance impact.

My definition of 'Good P2P Routing' is that if a device has direct radio 
contact with another device; these devices can pass messages between 
themselves directly as needed.

Regards,

Jerry

JP Vasseur <[email-masked]> 
Sent by: [email-masked]
07/07/2009 12:45 PM

To
Mukul Goyal <[email-masked]>
cc
ROLL WG <[email-masked]>
Subject
Re: [Roll] Some clarifications on RPL

Hi Mukul,

Thanks.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Wed, 8 Jul 2009 16:18:26 +0200

Hi Jerry,

On Jul 7, 2009, at 10:46 PM, [email-masked] wrote:

>
> JP,
>
>
> I agree with Mukal.
>
> If two or more nodes are all within radio proximity and hence  
> neighbors they should all be able to exchange messages amongst  
> themselves without needing to traverse the DAG.  In the commercial  
> building environment this will happen in the equipment rooms.  These  
> rooms are electromechanical rooms holding air handling, heating and  
> air conditioning equipment.  There may me as many as 20 controllers  
> (routing devices), 20 sensors and 20 actuators (non-routing devices)  
> all in the same 500 sq ft room.  The concept of finding candidate  
> parents and connecting into the DAG for this simple communication  
> seems to be overkill.
>
> I am only to page 41 of the draft and may be pleasantly surprised as  
> I read on; but the sense I have of the draft so far is it is  
> optimizing router efficiency of devices (i.e. no loops) while  
> ignoring the logical cohesion of many of the devices.  Again, in a  
> commercial building there are hundreds of rooms.  Each room is a  
> microcosm of the overall network (e.g occupancy, lights, heating/ 
> cooling, shade control).  For the most part these devices are  
> completely independent of all the other rooms.  They should be able  
> to communicate bidirectionally and freely amongst themselves with  
> minimal impact to the rest of the LLN.
>
> The DAG discovery and maintenance policies described in the draft  
> looks like each device positions itself on the DAG as best as it can  
> and then communicates as high up and then back down the DAG as  
> necessary to reach its intended destination.  I would think this  
> would create an unbalanced network traffic where the higher layers  
> are unfairly taxed at forwarding uninteresting messages while the  
> lower layers are awaiting message delivery.  As I mentioned in a  
> previous email, this architecture tends to make some devices more  
> important to the LLN than others which has negative fault tolerance  
> impact.
>
> My definition of 'Good P2P Routing' is that if a device has direct  
> radio contact with another device; these devices can pass messages  
> between themselves directly as needed.
>

Thanks for shedding some light on this important scenario. You are  
quite right that most focus has been given to P2MP/MP2P traffic  
patterns. In this scenario, the notion of sibling could help. Another  
alternative would be to first try to check neighbor reachability  
(nodes in direct neighborhood) before sending along the DAG. Still the  
DA may provide a non optimal path but optimal path from any point to  
any point required off-line path computation. How does this sound?

Thanks.

JP.

---

From: [email-masked]
Date: Wed, 8 Jul 2009 10:25:12 -0500

JP,

I'm not quite sure I understand the last phrase of the last sentence of 
your email ("but optimal path from any point to any point required 
off-line path computation"); but yes I think that first checking for 
direct radio communication  to a node (i.e. neighbors) and then using the 
DAG would allow isolated communication between neighbor nodes to proceed 
locally without affecting the overall traffic patterns of the LLN. 

Jerry

07/08/2009 09:18 AM

To
[email-masked]
cc
ROLL WG <[email-masked]>, Mukul Goyal <[email-masked]>, 
[email-masked], [email-masked]
Subject
Re: [Roll] Some clarifications on RPL

Hi Jerry,

JP, 

I agree with Mukal.   

Thanks for shedding some light on this important scenario. You are quite 
right that most focus has been given to P2MP/MP2P traffic patterns. In 
this scenario, the notion of sibling could help. Another alternative would 
be to first try to check neighbor reachability (nodes in direct 
neighborhood) before sending along the DAG. Still the DA may provide a non 
optimal path but optimal path from any point to any point required 
off-line path computation. How does this sound?

Thanks.

JP.

Regards, 

Jerry 

To

Hi Mukul,

Thanks.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Thu, 9 Jul 2009 08:31:14 +0200

Hi Jerry,

On Jul 8, 2009, at 5:25 PM, [email-masked] wrote:

>
>
>
> JP,
>
> I'm not quite sure I understand the last phrase of the last sentence  
> of your email ("but optimal path from any point to any point  
> required off-line path computation");

I meant to say that a distributed DV protocol will always lead to  
areas of sub-optimality. One approach could consist of relying on RPL  
to build connectivity and augment it with a PCE-based approach whereby  
more optimal would be built by the path computation engine (off-line  
path computation) having a global view of the system (thanks to  
topology acquisition using a mechanism similar to what HYDRO proposed  
since by contrast with other PCE-based approach running the link state  
routing protocol, we would need a topology acquisition mechanism). We  
can discuss such an option later on. PCE-based architecture are now  
very well understood, we have been working on them for several years  
in the PCE WG (see RFC4655 for architecture)

> but yes I think that first checking for direct radio communication   
> to a node (i.e. neighbors) and then using the DAG would allow  
> isolated communication between neighbor nodes to proceed locally  
> without affecting the overall traffic patterns of the LLN.
>

Excellent.

Cheers.

JP.

> ROLL WG <[email-masked]>, Mukul Goyal <[email-masked]>, [email-masked] 
> , [email-masked]
> Subject
> patterns. In this scenario, the notion of sibling could help.  
> Another alternative would be to first try to check neighbor  
> reachability (nodes in direct neighborhood) before sending along the  
> DAG. Still the DA may provide a non optimal path but optimal path  
> from any point to any point required off-line path computation. How  
> does this sound?
>
> Thanks.
>
> JP.
>
> Regards,
>
> Jerry
>
>
>