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

From: Mukul Goyal <[email-masked]>
Date: Sun, 27 Sep 2009 20:26:27 -0500 (CDT)

Hi Richard,

>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.

Could you please point me to the right place in RPL draft where this alternate method is described.

My understanding is that any increase in DAG rank requires a node to do the following:

1) detach from the DAG, 
2) generate new RA-DIO to tell sub-DAG about the detachment 
3) wait for RA-DIOs from neighbor nodes carrying new sequence number (hence these neighbors are guaranteed to be not in the sub-DAG)
4) starting DAG hop timers as these RA-DIOs are received
5) joining the DAG again via the neighbor for whom the DAG hop timer fires first.

Please let me know if this understanding is not correct.

Thanks
Mukul

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 28 Sep 2009 10:18:36 -0400

Hi Mukul,

   Date: Sun, 27 Sep 2009 20:26:27 -0500 (CDT)
   From: Mukul Goyal <[email-masked]>

   >certainly be improved on, but it does work.

   Could you please point me to the right place in RPL draft where this
   alternate method is described.

   My understanding is that any increase in DAG rank requires a node to
   do the following:

   1) detach from the DAG, 

I think that is correct as far as it goes, but there is
an alternate criteria for rejoining a DAG.

The draft is not as clear as it might be, but my reading of
rule 7 in section 5.3.1 is that a device may detach and
reattach immediately to a parent or parents that advertise a
more recent DAG sequence number.  The relevent sentences
are:

 A node SHOULD NOT join a previous DAG (identified by its DAGID)
 unless the sequence number in the RA-DIO message has incremented
 since the node left that DAG.  A newer sequence number indicates
 that the candidate parents were not attached behind this node, as
 they kept getting subsequent RA-DIO messages with new sequence
 numbers from the same DAG.

Saying that a node SHOULD NOT rejoin a DAG if the sequence
number has not changed implies that it is permissable to
rejoin if the sequence number has changed.  In particular, a
node that sees a neighbor with a more recent sequence number
than itself is free to leave the DAG and immediately rejoin
it with that neighbor as its new parent.  As the second
quoted sentence indicates, this cannot introduce a loop.

I believe that this is the intended behavior.

The phrase 'incremented since the node left that DAG' is
vague, because incrementing the sequence number is not an
atomic event for a DAG.  Different nodes update their copy
of the sequence number at different times.  What matters is
the sequence numbers held by the reattaching device and that
of its new parent(s).

                              -Richard Kelsey

---

From: Thomas Watteyne <[email-masked]>
Date: Mon, 28 Sep 2009 07:39:18 -0700

Hi Rickard, Mukul,

Thank you for the very interesting discussion. Of course we should RIP 
count-to-infinity problem. That being said, DAG inconsistencies will 
appear in LLNs due the amount of nodes sharing state, so RPL should in 
my opinion have some mechanism to deal with this (in a fashion similar 
to CTP?). I think we all agree on this.

Thank you for pointing rule 7, which I did not get this way. I'm sure 
this will be made clearer in the next version.

Thomas

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

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 28 Sep 2009 21:49:37 +0200

Hi Thomas.

Indeed. I'll make sure to have some slideware that discusses the Loops
that we know of with the current draft so we can more appropriately
discuss loop detection mechanisms. Each time we simplify the protocol we
might have to deal with more detection. Or people could take the problem
from the other end. Given a loop detection mechanism, what loops can we
afford now in the protocol? Ends should meet at some point.

Pascal

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Thomas Watteyne
>Sent: lundi 28 septembre 2009 16:39
>To: IETF ROLL
>Subject: Re: [Roll] Simplifying RPL: (2) relax loop avoidance
>
>Hi Rickard, Mukul,
>
>>    3) wait for RA-DIOs from neighbor nodes carrying new sequence
number (hence these neighbors are
>guaranteed to be not in the sub-DAG)

---

From: <[email-masked]>
Date: Mon, 28 Sep 2009 23:36:20 +0200

Hello all,

Talking about routing loops, the use of siblings for routing mandates a loop detection and abortion mechanism.

Trying to define a rank computation function for RPL, Quentin and myself have been fiddling with parents vs. siblings tradeoffs for a while, and also trying some ideas with data extracted from a test network.
We first wondered if a path redundancy equivalent to that provided by siblings could be obtained through more parents instead. We are now convinced it cannot: parents only benefit the child, while siblings benefit one another.
However, our first findings indicate that, for MP2P traffic, routing through no more than one sibling per DAG rank provides most of the benefit of routing through siblings at large, while implementing an obvious loop prevention mechanism as a side effect.
Since we are looking for simplifications, I wanted to run this idea by the WG, and I'll show a few slide on Wednesday to that effect.
Unless DAGs and siblings go down the sink ;-) by then...

Dominique

-----Message d'origine-----
De : [email-masked] [mailto:[email-masked]] De la part de Pascal Thubert (pthubert)
Envoyé : lundi 28 septembre 2009 21:50
À : Thomas Watteyne; IETF ROLL
Objet : Re: [Roll] Simplifying RPL: (2) relax loop avoidance

Hi Thomas.

Indeed. I'll make sure to have some slideware that discusses the Loops that we know of with the current draft so we can more appropriately discuss loop detection mechanisms. Each time we simplify the protocol we might have to deal with more detection. Or people could take the problem from the other end. Given a loop detection mechanism, what loops can we afford now in the protocol? Ends should meet at some point.

Pascal

Thomas Watteyne
>> I think that is correct as far as it goes, but there is an alternate 
>> criteria for rejoining a DAG.
>>
>> The draft is not as clear as it might be, but my reading of rule 7 in 
>> section 5.3.1 is that a device may detach and reattach immediately to 
>> a parent or parents that advertise a more recent DAG sequence number.  
>> The relevent sentences
>> are:
>>
>> Saying that a node SHOULD NOT rejoin a DAG if the sequence number has 
>> not changed implies that it is permissable to rejoin if the sequence 
>> number has changed.  In particular, a node that sees a neighbor with 
>> a more recent sequence number than itself is free to leave the DAG 
>> and immediately rejoin it with that neighbor as its new parent.  As 
>> the second quoted sentence indicates, this cannot introduce a loop.
>>
>> The phrase 'incremented since the node left that DAG' is vague, 
>> because incrementing the sequence number is not an atomic event for a 
>> DAG.  Different nodes update their copy of the sequence number at 
>> different times.  What matters is the sequence numbers held by the 
>> reattaching device and that of its new parent(s).
>>
>>                               -Richard Kelsey

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 29 Sep 2009 08:06:15 +0200

Excellent! Thanks Dominique.

Pascal

>From: [email-masked] [mailto:[email-masked]] On Behalf Of [email-masked]
>Sent: lundi 28 septembre 2009 23:36
>To: [email-masked]
>Subject: Re: [Roll] Simplifying RPL: loops through siblings
>
>Hello all,
>
>Trying to define a rank computation function for RPL, Quentin and myself have been fiddling with parents vs.
>siblings tradeoffs for a while, and also trying some ideas with data extracted from a test network.
>We first wondered if a path redundancy equivalent to that provided by siblings could be obtained through more
>parents instead. We are now convinced it cannot: parents only benefit the child, while siblings benefit one
>another.
>However, our first findings indicate that, for MP2P traffic, routing through no more than one sibling per DAG
>rank provides most of the benefit of routing through siblings at large, while implementing an obvious loop
>prevention mechanism as a side effect.
>
>Indeed. I'll make sure to have some slideware that discusses the Loops that we know of with the current draft
>so we can more appropriately discuss loop detection mechanisms. Each time we simplify the protocol we might
>have to deal with more detection. Or people could take the problem from the other end. Given a loop detection
>mechanism, what loops can we afford now in the protocol? Ends should meet at some point.
>
>Pascal
>

---

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

Hi Richard and Mukul

>I believe that this is the intended behavior.

That is correct. And I think we owe you for this...

We have to refine the text on this. The sequence processing is simple
with a tree but with a DAG, we have to decide when a node jumps to the
new sequence and whether it should abandon the parents with the old
sequence. For instance should we wait for the preferred parent to
advertise the new sequence? How long? What do we do on time out?

I think you already explained in this list that a new sequence draws a
new DAG and this is how I understood your words.

Pascal