Re: [Roll] Loop free local DODAG repair solution

Jianlin Guo <> Tue, 30 October 2012 16:01 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id B2F8721F85F0 for <>; Tue, 30 Oct 2012 09:01:36 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.599
X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599]
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 7M7X7Qce9ZaV for <>; Tue, 30 Oct 2012 09:01:34 -0700 (PDT)
Received: from ( []) by (Postfix) with ESMTP id 8C85621F85A0 for <>; Tue, 30 Oct 2012 09:01:34 -0700 (PDT)
Received: from ( []) by (8.13.8/8.12.10) with ESMTP id q9UG1SAA013286; Tue, 30 Oct 2012 12:01:28 -0400
Received: from [] ( []) by (8.12.10/8.12.10) with ESMTP id q9UG1NrV003184; Tue, 30 Oct 2012 12:01:28 -0400
Message-ID: <>
Date: Tue, 30 Oct 2012 12:01:23 -0400
From: Jianlin Guo <>
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:16.0) Gecko/20121010 Thunderbird/16.0.1
MIME-Version: 1.0
To: Philip Levis <>
References: <> <> <> <> <> <> <> <> <> <> <> <>
In-Reply-To: <>
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
Content-Transfer-Encoding: 8bit
Cc: "<>" <>
Subject: Re: [Roll] Loop free local DODAG repair solution
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Routing Over Low power and Lossy networks <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 30 Oct 2012 16:01:36 -0000

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.

On 10/29/2012 6:09 PM, Philip Levis wrote:
> 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 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, 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] :
>>> 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 <>
>>>>>>>>>   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
>> _______________________________________________
>> Roll mailing list