Re: [Roll] Loop free local DODAG repair solution

[Philip Levis <[e-mail]>]

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: 
> 
> 1) Start its own floating DODAG 
> 2) Poison the broken path 
> 3) Trigger a local repair 
> 
> 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:
>> 
>> Le 26 oct. 2012 à 17:36, Jianlin Guo a écrit :
>> 
>>> We compared performance metrics such as packet delivery rate.
>> 
>> 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.
>> 
>>> On 10/26/2012 11:21 AM, C Chauvenet wrote:
>>>> Hi,
>>>> Thank you for your answer.
>>>> See inline.
>>>> 
>>>> Le 26 oct. 2012 à 15:27, Jianlin Guo a écrit :
>>>> 
>>>>> On 10/25/2012 12:06 PM, C Chauvenet wrote:
>>>>>> 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 ? 
>>>>> 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.
>>>>>> 
>>>>>>> 
>>>>>>> For your second question, further investigation and experiments are needed.
>>>>>>> 
>>>>>>> Jianlin
>>>>>>> 
>>>>>>> On 10/25/2012 8:08 AM, Michael Richardson wrote:
>>>>>>>> Jianlin Guo <[e-mail]>
>>>>>>>>  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.
>>>>>>>> 
>>>>>>>> 
>>>>>>> 
>>>>>>> _______________________________________________
>>>>>>> Roll mailing list
>>>>>>> [e-mail]
>>>>>>> https://www.ietf.org/mailman/listinfo/roll
>>>>>> 
>>>>> 
>>>> 
>>> 
>> 
> 
> _______________________________________________
> Roll mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/roll