Subject: [Roll] How does RPL disallow greediness? What is local repair?

From: Alexandru Petrescu <[email-masked]>
Date: Sun, 25 Jul 2010 01:12:25 +0200

> Once a node has joined a DODAG version, RPL disallows certain
> behaviors, including greediness, in order to prevent resulting
> instabilities in the DODAG version.

How?  I searched for greed further down the text and it does not appear.

This phrase sounds as if there is a bit set on/off called 'greed', or
similar.

I may be wrong.

> It is for this reason that RPL limits the cases where a node may
> process DIO messages from deeper nodes to some forms of local
> repair.

Which forms?

'local repair' procedure is mentioned several times in the draft:

> On receiving such a packet, a node institutes a local repair
> operation.
[...]
> Strict use of the DODAG Version Number can eliminate this type of
> loop, but this type of loop may possibly be encountered when using
> some local repair mechanisms.
>
[...]
> MaxRankIncrease:  16-bit unsigned integer used to configure
> DAGMaxRankIncrease, the allowable increase in rank in support of
> local repair.
[...]
> o  Trigger a local repair
[...]
> o  Number of times a local repair procedure was triggered

These are all the occurences of "local repair".  It reads as an
operation, mechanism, procedure.  It is some form, some.

But what is a local repair?

Probably it is another term explained elsewhere that I can't find while
searching in this draft, sorry if so.

Alex

---

From: JP Vasseur <[email-masked]>
Date: Sun, 25 Jul 2010 11:27:44 +0200

To explain "geediness" we have added an example (see below).
Local repair is by contrast with global repair where the DODAG  
increments
the DODAG version and the DODAG is being "Rebuit", which may or may
not lead to a different DODAG shape. With local repair, the DODAG is
repaired "locally" to restore connectivity without rebuilding the  
entire DODAG.

Example that will be added about "greediness"

3.8.1.1.  Example: Greedy Parent Selection and Instability

          (A)                    (A)                    (A)
           |\                     |\                     |\
           | `-----.              | `-----.              | `-----.
           |        \             |        \             |        \
          (B)       (C)          (B)        \            |        (C)
                                   \        |            |        /
                                    `-----. |            | .-----'
                                           \|            |/
                                           (C)          (B)

               -1-                    -2-                    -3-

                   Figure 3: Greedy DODAG Parent Selection

    Figure 3 depicts a DODAG in 3 different configurations.  A usable
    link between (B) and (C) exists in all 3 configurations.  In
    Figure 3-1, Node (A) is a DODAG parent for Nodes (B) and (C).  In
    Figure 3-2, Node (A) is a DODAG parent for Nodes (B) and (C), and
    Node (B) is also a DODAG parent for Node (C).  In Figure 3-3, Node
    (A) is a DODAG parent for Nodes (B) and (C), and Node (C) is also a
    DODAG parent for Node (B).

    If a RPL node is too greedy, in that it attempts to optimize for an
    additional number of parents beyond its most preferred parents, then
    an instability can result.  Consider the DODAG illustrated in
    Figure 3-1.  In this example, Nodes (B) and (C) may most prefer Node
    (A) as a DODAG parent, but we will consider the case when they are
    operating under the greedy condition that will try to optimize for 2

Winter, et al.          Expires January 16, 2011               [Page 22]

Internet-Draft           draft-ietf-roll-rpl-11                July 2010

    parents.

    o  Let Figure 3-1 be the initial condition.

    o  Suppose Node (C) first is able to leave the DODAG and rejoin at a
       lower rank, taking both Nodes (A) and (B) as DODAG parents as
       depicted in Figure 3-2.  Now Node (C) is deeper than both Nodes
       (A) and (B), and Node (C) is satisfied to have 2 DODAG parents.

    o  Suppose Node (B), in its greediness, is willing to receive and
       process a DIO message from Node (C) (against the rules of RPL),
       and then Node (B) leaves the DODAG and rejoins at a lower rank,
       taking both Nodes (A) and (C) as DODAG parents.  Now Node (B) is
       deeper than both Nodes (A) and (C) and is satisfied with 2 DAG
       parents.

    o  Then Node (C), because it is also greedy, will leave and rejoin
       deeper, to again get 2 parents and have a lower rank then both of
       them.

    o  Next Node (B) will again leave and rejoin deeper, to again get 2
       parents

    o  And again Node (C) leaves and rejoins deeper...

    o  The process will repeat, and the DODAG will oscillate between
       Figure 3-2 and Figure 3-3 until the nodes count to infinity and
       restart the cycle again.

    o  This cycle can be averted through mechanisms in RPL:

       *  Nodes (B) and (C) stay at a rank sufficient to attach to their
          most preferred parent (A) and don't go for any deeper (worse)
          alternate parents (Nodes are not greedy)

       *  Nodes (B) and (C) do not process DIO messages from nodes  
deeper
          than themselves (because such nodes are possibly in their own
          sub-DODAGs)

On Jul 25, 2010, at 1:12 AM, Alexandru Petrescu wrote:

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

---

From: Alexandru Petrescu <[email-masked]>
Date: Sun, 25 Jul 2010 11:33:37 +0200

[...]
> Internet-Draft           draft-ietf-roll-rpl-11                July 2010

11?  I thought it was 10?

Am I looking at the right document?

This is a moving target - I do not like to work that way, sorry.  Please 
post drafts publicly and only then ask for review.

Can't work this way: private documents, fuzzy authorship.

It's a waste of time from my part.

Yes, procedure is important.

Alex

>        *  Nodes (B) and (C) do not process DIO messages from nodes deeper
>> [email-masked] <mailto:[email-masked]>

---

From: JP Vasseur <[email-masked]>
Date: Sun, 25 Jul 2010 11:39:59 +0200

>> Internet-Draft           draft-ietf-roll-rpl-11                July  

It is 10 right now. The author team has been working hard to  
incorporate all the comments,
ticket resolutions in the (to be posted) revision 11. I gave you some  
new text that will be
incorporated to answer your question.

> This is a moving target - I do not like to work that way, sorry.   
> Please post drafts publicly and only then ask for review.
>

Alex, we are in WG LC. We have received a number of comments, open a  
number of tickets, proposed
solutions, ... this cannot be more transparent. Resolution text are  
being worked out and I gave you
extracts. That's it.

JP.

---

From: Alexandru Petrescu <[email-masked]>
Date: Sun, 25 Jul 2010 11:46:54 +0200

Le 25/07/2010 11:39, JP Vasseur a écrit :
> incorporate all the comments, ticket resolutions in the (to be
> posted) revision 11. I gave you some new text that will be
>  number of tickets, proposed solutions, ... this cannot be more
> transparent. Resolution text are being worked out and I gave you
> extracts. That's it.

JP - thanks for explanation.  This is a management problem.  YOu have a 
100 page document, 100wise tickets and a WG LC which you seem to want to 
  solve in one IETF meeting.  I think it is too much work...

Yes, this is procedure, not technical, but without good procedure I 
can't talk technical.

Alex

>>> o Suppose Node (C) first is able to leave the DODAG and rejoin at
>>> a lower rank, taking both Nodes (A) and (B) as DODAG parents as
>>> o Then Node (C), because it is also greedy, will leave and
>>> rejoin deeper, to again get 2 parents and have a lower rank then
>>> both of them.
>>>
>>> o Next Node (B) will again leave and rejoin deeper, to again get
>>> 2 parents
>>>
>>> deeper than themselves (because such nodes are possibly in their
>>> own sub-DODAGs)
>>>
>>>
>>>
>>>
>>>
>>>>> Once a node has joined a DODAG version, RPL disallows
>>>>> certain behaviors, including greediness, in order to prevent
>>>>> resulting instabilities in the DODAG version.
>>>>
>>>> This phrase sounds as if there is a bit set on/off called
>>>> 'greed', or similar.
>>>>
>>>> I may be wrong.
>>>>
>>>>> It is for this reason that RPL limits the cases where a node
>>>>> may process DIO messages from deeper nodes to some forms of
>>>>> local repair.
>>>>
>>>> Which forms?
>>>>
>>>>> Strict use of the DODAG Version Number can eliminate this
>>>>> type of loop, but this type of loop may possibly be
>>>>> encountered when using some local repair mechanisms.
>>>>>
>>>> [...]
>>>>> DAGMaxRankIncrease, the allowable increase in rank in support
>>>>> of local repair.
>>>> [...]
>>>>> o Trigger a local repair
>>>> [...]
>>>> Probably it is another term explained elsewhere that I can't
>>>> find while searching in this draft, sorry if so.
>>>>
>>>> Alex _______________________________________________ Roll
>>>> mailing list [email-masked] <mailto:[email-masked]>

---

From: JP Vasseur <[email-masked]>
Date: Sun, 25 Jul 2010 12:10:54 +0200

On Jul 25, 2010, at 11:46 AM, Alexandru Petrescu wrote:

> JP - thanks for explanation.  This is a management problem.  YOu  
> have a 100 page document, 100wise tickets and a WG LC which you seem  
> to want to  solve in one IETF meeting.  I think it is too much work...

Last email on the subject matter from my side. David may want to chime  
in as document shepherd.
If you carefully look at the mailing list, you will find out that a  
number of people provided comments that helped
to collectively build RPL. You are referring to the 100wise tickets  
(actually 73), that were opened and a 100
page document to solve in one IETF. I have no idea of why you are  
referring to "Solving in one IETF meeting".
The first ticket was opened 1 year ago, we have 3 IETF meetings and  
two interim meetings. Tickets have been
discussed, solved and closed on the mailing in total transparency.

I'll stop there. David may want to say a few words too.

JP.

---

From: David Culler <[email-masked]>
Date: Mon, 26 Jul 2010 03:35:51 -0700

Alex,
   We are not solving 100 tickets in one IETF.  We have been steadily resolving issues.  In the early stage, you address a small number of large issues.  It does not make sense to polish all the little ones until the large ones have settled.  In the final stages you end up with numerous small issues to polish.  That process is going along very nicely.  The WG include numerous people who have implemented variants of the these protocols and have extensive experience.  They have brought that to bear on the problem.  Where we encountered issues that do not have a huge body of established evidence to guide, we have simplified the approach to where it remained extremely well grounded.  The proposed protocol rests on a substantial body of knowledge and fact.  The issues at this stage are cleaning up details and improving consistency.  This allows the WG to complete the core spec and serious implementation to proceed.  From that experience over time there is likely to be addition small improvements.  In particular, we have set aside major optimizations that did not yet have sufficient body of evidence to support introduction of additional complexity.
   At this point you seem to be tossing our long scattered messages on everything that comes to your mind.  That is permitted under IETF rules, but it is not very useful.  It will be much more useful if you will read the draft, try to think through the concern that you have, and then if it remains significant pose a focused question to the mailing list.

On Jul 25, 2010, at 3:10 AM, JP Vasseur wrote:

>> JP - thanks for explanation.  This is a management problem.  YOu have a 100 page document, 100wise tickets and a WG LC which you seem to want to  solve in one IETF meeting.  I think it is too much work...
> 
> Last email on the subject matter from my side. David may want to chime in as document shepherd. 
> If you carefully look at the mailing list, you will find out that a number of people provided comments that helped
> to collectively build RPL. You are referring to the 100wise tickets (actually 73), that were opened and a 100
> page document to solve in one IETF. I have no idea of why you are referring to "Solving in one IETF meeting".
> The first ticket was opened 1 year ago, we have 3 IETF meetings and two interim meetings. Tickets have been
>> Yes, this is procedure, not technical, but without good procedure I can't talk technical.
>> 
>> Alex
>> 
>>> 
>>> JP.
>>> 
>>>> Alex
>>>> 
>>>>> 
>>>>> 
>>>>> parents.
>>>>>