Subject: [Roll] Loop free local DODAG repair solution

From: Jianlin Guo <[email-masked]>
Date: Tue, 23 Oct 2012 10:11:36 -0400

Dear ROLL WG members,

As we all know that loop is an open issue in RPL. Experiment shows that 
loop occurs quite often. We have proposed a loop free local DODAG repair 
solution. The proposed repair method does not increase rank, and 
therefore, it does not create any loop. Also, the proposed repair method 
does not require any modification to RPL and works for both storing mode 
and non-storing mode of RPL. It provides benefits to RPL.

The detailed solution is specified in 
draft-guo-roll-loop-free-dodag-repair-00. Please review the draft. Your 
comments and feedback are welcome.

Best regards,
Jianlin Guo
Senior Principal Member Research Staff
Mitsubishi Electric Research Laboratories
201 Broadway, Cambridge, MA, USA

---

From: Philip Levis <[email-masked]>
Date: Tue, 23 Oct 2012 08:39:20 -0700

I thought the hop-by-hop header detects loops and triggered DIOs repair them?

Phil

On Oct 23, 2012, at 7:11 AM, Jianlin Guo wrote:

> Dear ROLL WG members,
> 
> As we all know that loop is an open issue in RPL. Experiment shows that loop occurs quite often. We have proposed a loop free local DODAG repair solution. The proposed repair method does not increase rank, and therefore, it does not create any loop. Also, the proposed repair method does not require any modification to RPL and works for both storing mode and non-storing mode of RPL. It provides benefits to RPL.
> 
> The detailed solution is specified in draft-guo-roll-loop-free-dodag-repair-00. Please review the draft. Your comments and feedback are welcome.
> 
> Best regards,
> Jianlin Guo
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: Jianlin Guo <[email-masked]>
Date: Tue, 23 Oct 2012 12:17:12 -0400

Hi Phil,

Thank you for your comment. Goal of our local repair method is to 
prevent loop from occurring and therefore, loop detection is unnecessary.

Jianlin

---

From: Jianlin Guo <[email-masked]>
Date: Tue, 23 Oct 2012 12:33:39 -0400

Hi Phil,

One more point, I think that DIO repair needs to build a new DODAG 
version, and global DODAG re-building process may interrupt application 
data transmission and increase delay, which is not acceptable for some 
applications.

Jianlin

---

From: Philip Levis <[email-masked]>
Date: Tue, 23 Oct 2012 09:34:01 -0700

The original observation behind loop detection and repair is that it is often much simpler and less expensive than loop prevention. This is not always true; I wouldn't to use it on core routers. But the tradeoffs that LLNs introduce make it an attractive option. 

Phil

On Oct 23, 2012, at 9:17 AM, Jianlin Guo wrote:

> Hi Phil,
> 
> Thank you for your comment. Goal of our local repair method is to prevent loop from occurring and therefore, loop detection is unnecessary.
> 
> Jianlin

---

From: Philip Levis <[email-masked]>
Date: Tue, 23 Oct 2012 09:34:37 -0700

On Oct 23, 2012, at 9:33 AM, Jianlin Guo wrote:

> Hi Phil,
> 
> One more point, I think that DIO repair needs to build a new DODAG version, and global DODAG re-building process may interrupt application data transmission and increase delay, which is not acceptable for some applications.
> 
> Jianlin

You would be incorrect; please re-read 6550.

Phil

---

From: Jianlin Guo <[email-masked]>
Date: Tue, 23 Oct 2012 14:02:17 -0400

Phil,

Our local repair method is to locally repair DODAG by a node whose 
parent set becomes empty. In this case, RPL provides following set of 
actions:

1) Start its own floating DODAG
2) Poison the broken path
3) Trigger a local repair

It would be appreciated if you could point out what local repairs are 
specified?

Jianlin

---

From: Michael Richardson <[email-masked]>
Date: Thu, 25 Oct 2012 08:08:13 -0400

Jianlin Guo <[email-masked]> wrote:
    JG> Dear ROLL WG members,

    JG> As we all know that loop is an open issue in RPL. Experiment shows that loop
    JG> occurs quite often. We have proposed a loop free local DODAG

Can you quantify "quite often"?
Do you have any metrics for how often loops occur, and what the cost is
of their repair?

I think that the WG would be very very very interested in additional -experiences
draft, or pointers to papers explaining same, that gives a repeateable
experiment in which loops are observed.

-- 
Michael Richardson <[email-masked]>, Sandelman Software Works 
IETF ROLL WG co-chair.    http://datatracker.ietf.org/wg/roll/charter/

---

From: Jianlin Guo <[email-masked]>
Date: Thu, 25 Oct 2012 10:01:36 -0400

Hi Michael,

For your first question, draft-clausen-lln-rpl-experiences-04 pointed 
out that "it can be observed that with current implementations of RPL, 
such as the ContikiRPL implementation, loops do occur - and, frequently. 
During the same experiments described in Section 13, a snapshot of the 
DODAG was made every ten seconds. In 74.14% of the 4114 snapshots, at 
least one loop was observed".

For your second question, further investigation and experiments are needed.

Jianlin

---

From: C Chauvenet <[email-masked]>
Date: Thu, 25 Oct 2012 16:06:56 +0000

Hi,

Le 25 oct. 2012 à 16:01, Jianlin Guo a écrit :

Hi Michael,

For your first question, draft-clausen-lln-rpl-experiences-04 pointed out that "it can be observed that with current implementations of RPL, such as the ContikiRPL implementation, loops do occur - and, frequently. During the same experiments described in Section 13, a snapshot of the DODAG was made every ten seconds. In 74.14% of the 4114 snapshots, at least one loop was observed".

Is it something that you observed in your own deployments ?
More specifically : did you find similar results ?

Best,

Cédric.

Jianlin

Jianlin Guo <[email-masked]><mailto:[email-masked]> wrote:
    JG> Dear ROLL WG members,

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

---

From: Jianlin Guo <[email-masked]>
Date: Fri, 26 Oct 2012 09:27:54 -0400

On 10/25/2012 12:06 PM, C Chauvenet wrote:
>> out that "it can be observed that with current implementations of 
>> RPL, such as the ContikiRPL implementation, loops do occur - and, 
>> frequently. During the same experiments described in Section 13, a 
>> snapshot of the DODAG was made every ten seconds. In 74.14% of the 
>> 4114 snapshots, at least one loop was observed".
>
We observed the occurrence of loops, unfortunately we did not measure 
the percentage.

>>> Jianlin Guo<[email-masked]>  wrote:
>> [email-masked] <mailto:[email-masked]>

---

From: C Chauvenet <[email-masked]>
Date: Fri, 26 Oct 2012 15:21:34 +0000

Hi,
Thank you for your answer.
See inline.

Le 26 oct. 2012 à 15:27, Jianlin Guo a écrit :

Hi Michael,

Is it something that you observed in your own deployments ?
More specifically : did you find similar results ?
We observed the occurrence of loops, unfortunately we did not measure the percentage.

So how did you evaluate the benefit of the mechanism that you proposed ?

Cédric.

Best,

Cédric.

Jianlin

---

From: Jianlin Guo <[email-masked]>
Date: Fri, 26 Oct 2012 11:36:45 -0400

We compared performance metrics such as packet delivery rate.
On 10/26/2012 11:21 AM, C Chauvenet wrote:
>>>> For your first question, draft-clausen-lln-rpl-experiences-04 
>>>> pointed out that "it can be observed that with current 
>>>> implementations of RPL, such as the ContikiRPL implementation, 
>>>> loops do occur - and, frequently. During the same experiments 
>>>> described in Section 13, a snapshot of the DODAG was made every ten 
>>>> seconds. In 74.14% of the 4114 snapshots, at least one loop was 
>>>> observed".
>>>

---

From: C Chauvenet <[email-masked]>
Date: Fri, 26 Oct 2012 16:10:55 +0000

Le 26 oct. 2012 à 17:36, Jianlin Guo a écrit :

Ok.

In general do you have a document about your experiments that you would like to share ?
I think it could be a good way to defend your mechanism.

There are 2 sub questions related to your draft :

 - Is there a strong need for an additional mechanism to prevent loops ? (the HbH header option mentioned by phil is already there).
 - Is your mechanism the good way to do so (overhead induced, efficiency...)

As mentioned by Phil, this subject has been previously discussed inside ROLL few years ago, and did not recommend to add such mechanisms.

For instance, [1] concludes that

"the turmoil caused
by dismantling of the sub-DAGs in order to increase ranks
may be much more than what the routing loops themselves
will cause. Consequently, the use of such loop avoidance
mechanism in the operation of a DAG based routing protocol
can not be universally recommended."

[1] : http://www.emmanuelbaccelli.org/publications/AINA_2010.pdf

Best,

Cédric.

Hi Michael,

Cédric.

Best,

Cédric.

Jianlin

---

From: Jianlin Guo <[email-masked]>
Date: Fri, 26 Oct 2012 15:18:17 -0400

Thank you for the paper. I agree with [1] on that "dismantling of the 
sub-DAG, rooted at the node doing the rank increase, causes more turmoil 
in the network than the routing loops themselves".

Now, consider a case in which a node's parent set becomes empty. In this 
case, RPL provides following set of actions:

Both 1) and 2) actions will increase packet delivery delay time (which 
may be not acceptable for some applications) and possibly cause packet 
dropping due to limited buffer size of a LLN node (which may also be not 
acceptable for some applications). So, trigger a local repair is a 
practical option. Our local repair mechanism is designed for this 
purpose and it does not create any loops.

Jianlin

On 10/26/2012 12:10 PM, C Chauvenet wrote:
>  - Is there a strong need for an additional mechanism to prevent loops 
> ? (the HbH header option mentioned by phil is already there).
> As mentioned by Phil, this subject has been previously discussed 
> inside ROLL few years ago, and did not recommend to add such mechanisms.
>
> /
> /
> /"the turmoil caused/
> /by dismantling of the sub-DAGs in order to increase ranks/
> /may be much more than what the routing loops themselves/
> /will cause. Consequently, the use of such loop avoidance/
> /mechanism in the operation of a DAG based routing protocol/
> /can not be universally recommended."/
>
>>>>>> described in Section 13, a snapshot of the DODAG was made every 
>>>>>> ten seconds. In 74.14% of the 4114 snapshots, at least one loop 
>>>>>> was observed".
>>>>>

---

From: Philip Levis <[email-masked]>
Date: Mon, 29 Oct 2012 15:09:46 -0700

I'd like to take a step back here and discuss MaxRankIncrease and the notion of null parent sets.

The two major cases where a RPL node has a null parent set are:
  1) The node has no members in its neighbor set
  2) The node has members of its neighbor set, but all of them advertise a Rank of INFINITE_RANK. The major case we're concerned about here is when rule 3 of 8.2.2.4 requires nodes to advertise INFINITE_RANK due to the value of MaxRankIncrease.

I don't think the local repair scheme will fix case 1. So we're really talking about case 2. 

MaxRankIncrease emerged in specifying RPL as a way to support both ZigBee-style centralized periodic tree reconstruction triggers (MaxRankIncrease == 0) as well as CTP-style completely distributed operation while simultaneously providing a cap to the count-to-infinity problem. So really, the issue here is when you have a network with a small MaxRankIncrease and don't want to reconstruct the entire tree, there are valid parents that could be used, but a node does not have them in its neighbor/parent set.

Thinking about it this way (am I wrong?), I am a bit confused by the claim that the draft is a local repair. Assuming a node has to follow rule 3 in 8.2.2.4, this is not a repair mechanism, but rather a neighbor discovery mechanism. Could you explain how DRQ/DRP solve a problem that a DIS with a proper Solicited Information option can't solve? This was the original intent of DIS with Solicited Information. Or perhaps I'm not understanding DRQ/DRP correctly?

Phil

On Oct 26, 2012, at 12:18 PM, Jianlin Guo wrote:

> Thank you for the paper. I agree with [1] on that "dismantling of the sub-DAG, rooted at the node doing the rank increase, causes more turmoil in the network than the routing loops themselves".
> 
> Now, consider a case in which a node's parent set becomes empty. In this case, RPL provides following set of actions: 
> 
> Both 1) and 2) actions will increase packet delivery delay time (which may be not acceptable for some applications) and possibly cause packet dropping due to limited buffer size of a LLN node (which may also be not acceptable for some applications). So, trigger a local repair is a practical option. Our local repair mechanism is designed for this purpose and it does not create any loops.
> 
> Jianlin
>

---

From: Jianlin Guo <[email-masked]>
Date: Tue, 30 Oct 2012 12:01:23 -0400

Hi Phil,

Thank you for your valuable comments. There may be one more major case 
where a RPL node has a null parent set, that is, parent node of a RPL 
node becomes unreachable. This is a typical case in lossy networks. For 
example, a mobile object could block wireless link between two RPL nodes.

The key differences between DIS and DRQ/DRP are:
1) A DRQ message can travel multiple hops. # of hops is controlled by a 
parameter named MH (Maximum Hop) in DRQ message.
2) Upon receiving a DRQ message, a neighbor node responds with DRP 
message only if neighbor node has non-empty parent set and a rank lower 
than rank of the DRQ transmitting node. Otherwise, it may forward DRQ 
message to its parent node.
3) Receiving of a DRP message guarantees the discovery of a new parent node.
4) Value of MH parameter controls local repair. MH can be set to a small 
value, e.g. 1,2 or 3, so that DRQ message do not travel too far.

Jianlin

---

From: Philip Levis <[email-masked]>
Date: Tue, 30 Oct 2012 10:03:20 -0700

So it's basically a multihop DIS? How is that then a local repair? In the case of a subtree becoming disconnected due to the top of the subtree having a null parent set, those nodes at the top would issue a DIS with Solicited Information to repair their local routes (next hop). Nodes below them in the DODAG shouldn't have to trigger a local repair.

Put another way, can you describe a concrete case where DIS with Solicited Information can't solve the problem, yet DRQ/DRP can? Or is this purely an efficiency optimization? If the latter, I'd love to see concrete results indicating the savings (from a real LLN, not simulation).

Phil

On Oct 30, 2012, at 9:01 AM, Jianlin Guo wrote:

> Hi Phil,
> 
> Thank you for your valuable comments. There may be one more major case where a RPL node has a null parent set, that is, parent node of a RPL node becomes unreachable. This is a typical case in lossy networks. For example, a mobile object could block wireless link between two RPL nodes.
> 
> 1) A DRQ message can travel multiple hops. # of hops is controlled by a parameter named MH (Maximum Hop) in DRQ message.
> 2) Upon receiving a DRQ message, a neighbor node responds with DRP message only if neighbor node has non-empty parent set and a rank lower than rank of the DRQ transmitting node. Otherwise, it may forward DRQ message to its parent node.
> 4) Value of MH parameter controls local repair. MH can be set to a small value, e.g. 1,2 or 3, so that DRQ message do not travel too far.
> 
> Jianlin

---

From: Jianlin Guo <[email-masked]>
Date: Tue, 30 Oct 2012 18:09:15 -0400

It is local in the sense that repair does not propagate far away from 
initiation node. It also depends on the definition of "local', 1 hop 
only or 2 hop still considered as local.

Consider a case where a node N's parent node becomes unreachable. Ranks 
of all reachable neighbors are greater than node N's rank. Using DIS, 
node N has to increase its rank greater than its old rank. With this 
increased rank, node N needs to transmit a DIO. If any of node N's 
children does not receive this DIO (which is typical in lossy network), 
a loop may be created. Even though all children receive this DIO, this 
DIO may result in entire sub-tree to increase their ranks. DRQ/DRP 
repair does not increase rank of any node, therefore it is loop free.

Jianlin