Subject: [Roll] Simplifying RPL: (2) relax loop avoidance

From: Thomas Watteyne <[email-masked]>
Date: Fri, 25 Sep 2009 18:01:50 -0700

[this e-mail is part 3/3 of the thread “Simplifying RPL”]

__background__:
In a DAG structure, each node acquires a rank such that ranks in the LLN 
form a gradient rooted at the DAG root. The further away from the root 
(according to the path cost calculation defined in the OCP), the larger 
the rank. If this rule is not satisfied, a packet can have backward 
progress, with the possibility of creating a loop, if the packet then 
finds its way back in the right direction.

__current state__:
RPL currently very much focuses on avoiding loops, even if those are 
transient. Inside a given DAG, a node is allowed to reduce its rank 
immediately and at no cost. When it needs to increase its rank, the node 
need to first form the LLN detach, then reattach to a different location 
(i.e. with a higher rank). Because a node relays packets for its 
sub-DAG, this detaching/reattaching needs to be done in a coordinated 
way. Similar to jumping from DAG to DAG (see thread “Simplifying RPL: 
(1) multiple DAGs”), the complexity of this procedure increases the 
chances of inconsistent states and race conditions.

__proposed change__:
(We call DAG inconsistency the case where the node ranks do not increase 
while moving away from the root; DAG inconsistency may trigger loops.)

If the DAG rank calculation is done right, all DAG inconsistencies are 
transient in nature, and there is no need for complex coordinated moves 
of the nodes. We propose to calculate a node’s rank as follows (this is 
very much in line with 5.8.1 “self’s rank is computed as the preferred 
parent rank plus the step in rank with that parent”):
- a node maintain a list of neighbor, indicating the rank of each 
neighbor, and also the cost of the link connecting that node to each of 
its neighbors.
- every time the information in that list changes, the node calculates, 
for each of its neighbors, the potential rank it would acquire if it 
chose that neighbor as preferred parent. The node finally pick the 
lowest of all potential ranks.
- when forwarding, a node simply picks its neighbor with lowest rank as 
next hop.

Note that this simple technique is different to what RPL currently states:
- a node can acquire a higher rank immediately and at no cost without 
coordinating with its sub-DAG
- although this creates a transient inconsistency (and a potential 
loop), it is quickly ironed away by successive RA-DIOs (this process is 
further sped up by the use of Trickle).

The cost of this technique is to have transient loops, i.e. sometimes a 
packet will take a hop more to reach the root. The benefit is that this 
technique does not require coordination over a complete sub-DAG. We 
believe that the benefits outweigh the cost.

---

From: Richard Kelsey <[email-masked]>
Date: Sun, 27 Sep 2009 12:02:12 -0400

Date: Fri, 25 Sep 2009 18:01:50 -0700
   From: Thomas Watteyne <[email-masked]>

Thomas,
   
   We propose to calculate a node’s rank as follows (this is 

Isn't this how RIP works?  What about the counting-to-infinity
problem?

The current draft has another method for increasing rank,
which is that a node can acquire a higher rank whenever the
DAG sequence number is incremented.  This is done without
any need to coordinate with the sub-DAG.  This technique is
in use today in millions of deployed devices.  It can
certainly be improved on, but it does work.

   The cost of this technique is to have transient loops, i.e. sometimes a 
   packet will take a hop more to reach the root.

My experience is that a loop doesn't just add a hop or two.
A few packets going around a loop can consume much of the
local bandwidth, to the point of interfering with attempts
to resolve the loop.  If we do allow transient loops we also
need a method for holding up looping packets, such as used
in CTP (Collection Tree Protocol).
                                       -Richard Kelsey

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 29 Sep 2009 17:44:14 +0200

Hi Thomas

>- when forwarding, a node simply picks its neighbor with lowest rank as

Isn't that arch greediness? 

Pascal