Subject: Re: [Roll] RPL Design Questions

From: Mukul Goyal <[email-masked]>
Date: Wed, 7 Oct 2009 21:16:08 -0500 (CDT)

I would like to make the following comments:

1) Dag hop timer is just a way to avoid reducing the rank frequently. Frequent reduction of rank is bad if it means frequent generation of RA-DIO. It is not a loop avoidance mechanism.

2) Now, dag hop time can be used as a loop "avoidance" mechanism if it is used as a wait time that is long enough to allow hopefully all the nodes in my sub-dag to leave my sub-dag knowing  that I am leaving the DAG. So at the end of the wait time, if a neighbor still claims to be on the DAG, it is "hopefully" (but not "certainly") not in my sub-dag. So, the correct way to use dag hop time would be:
a) wait for the dag hop time and ignore the RA-DIOs from the neighbors during this time;
b) when wait time is over, I can choose any neighbor that still is in the DAG as my parent

Whether the dag hop timer is used as current RPL specs say or in the manner described above, their use should be optional.

3) increasing the rank only on receiving a new seq_no from root prevents loops. Now, the problem is that a node may have to wait for an nondeterministic long time before receiving a new seq_no and increasing its rank. I think this problem is best left unsolved in the base specs. Here are some possible solutions though:  

a) One solution would be to propagate info about any link_loss event in the DAG back to the root so that it can increment the seq_no. This solution fails the scalability test. As the DAG size increases, too many control packets would be generated to let the root know about the link_loss events and subsequent generation of new RA-DIOs by all the nodes in the DAG. It may be failing one of the criteria mentioned in the survey ID since a local event needs to be flooded globally (to the roots of all the DAGs that may be affected).

b) Another simple solution would be to require (fixed) periodic update of seq_no by the DAG root. This solution gives a better upper bound on the delay in increasing the rank but may also result in generation of too many RA-DIOs (or even RA-DIO storms).

Thanks
Mukul

----- Original Message -----
From: "Tim Winter" <[email-masked]>
To: [email-masked]
Sent: Wednesday, October 7, 2009 5:43:56 PM GMT -06:00 US/Canada Central
Subject: [Roll] RPL Design Questions

   WG,

   As discussed at the interim meeting, implementer feedback has
   indicated that the RPL protocol as proposed appears complex, both in
   description and actual FSM.

   Our plan of action is to, by end of month, deliver a -04 that will
   contain actual (non-editorial) changes.  The intent of this mail is 
   a poll over a period of 2 weeks, to help design the functional 
   changes.

   In this spirit, we would like the WG to work on the following
   questions:

   Question A:  Should RPL make use of the currently proposed local
      repair mechanism (DAG splitting and merging)?

         [NO implies that DAG repairs shall be coordinated globally with
         the use of DAG Sequence Number; the related mechanisms are to
         be expanded for -04]

   Question B:  Should RPL make use of a hold-up timer and related
      states/procedures to reduce churn by coordinating the DAG merge?

         [NO implies RPL allows nodes to move (jump) between DAGs with
         little coordination to reduce complexity of specification/
         implementation (perhaps w/ Optional hold-up mechanism)].

   Question C:  Should RPL make use of a hold-down timer and related
      states/procedures to limit flapping when removing DAG Parents /
      leaving DAGs

         [NO implies RPL allows nodes to freely remove/add DAG Parents
         as and when they are able in order to reduce complexity of
         specification/implementation (perhaps w/ Optional hold-down
         mechanism).

   WG, we expect that this thread will contain a lot of interesting
   related discussion, but in your comments please do also be sure to
   try and address the initial questions A, B, and C so as to help us
   better capture the WG position on these issues.  Please note that A,
   B, and C are to some degree orthogonal, e.g. `No Local Repair' to
   Question A does not necessarily imply a particular disposition toward
   the Hold-Up mechanism in Question B.

   Thanks,

   RPL Authors

   Some examples, derived from the present draft, are provided below:

   ------------------------------------------------------------------------

      Example: Local Repair with Hold-Up state

          :                      :                      :
          :                      :                      :
         (A)                    (A)                    (A)
          |\                     |                      |
          | `-----.              |                      |
          |        \             |                      |
         (B)       (C)          (B)       (C)          (B)
                    |                      |             \
                    |                      |              `-----.
                    |                      |                     \
                   (D)                    (D)                    (C)
                                                                  |
                                                                  |
                                                                  |
                                                                 (D)

              -1-                    -2-                    -3-

                         Figure 1: DAG Maintenance

   Consider the example depicted in Figure 1-1.  In this example, Node
   (A) is attached to a DAG at some rank d.  Node (A) is a DAG parent of
   Nodes (B) and (C).  Node (C) is a DAG parent of Node (D).  There is
   also an undirected sibling link between Nodes (B) and (C).

   In this example, Node (C) may safely forward to Node (A) without
   creating a loop.  Node (C) may not safely forward to Node (D),
   contained within it's own sub-DAG, without creating a loop.  Node (C)
   may forward to Node (B) in some cases, e.g. the link (C)->(A) is
   temporarily unavailable, but with some chance of creating a loop
   (e.g. if multiple nodes in a set of siblings start forwarding
   `sideways' in a cycle) and requiring the intervention of additional
   mechanisms to detect and break the loop.

   Consider the case where Node (C) hears a RA-DIO message from a Node
   (Z) at a lesser rank and superior position in the DAG than node (A).
   Node (C) may safely undergo the process to evict node (A) from its
   DAG parent set and attach directly to Node (Z) without creating a
   loop, because its rank will decrease.

   Now consider the case where the link (C)->(A) becomes nonviable, and
   node (C) must move to a deeper rank within the DAG:

   o  Node (C) must first detach from the DAG by removing Node (A) from
      its DAG parent set, leaving an empty DAG parent set.  Node (C)
      becomes the root of its own floating, less preferred, DAG.

   o  Node (D), hearing a modified RA-DIO message from Node (C), follows
      Node (C) into the floating DAG.  This is depicted in Figure 1-2.
      In general, any node with no other options in the sub-DAG of Node
      (C) will follow Node (C) into the floating DAG, maintaining the
      structure of the sub-DAG.

   o  Node (C) hears a RA-DIO message from Node (B) and determines it is
      able to rejoin the grounded DAG by reattaching at a deeper rank to
      Node (B).  Node (C) starts a DAG Hop timer (putting Node (B) in
      the Hold-Up state) to coordinate this move.

   o  The timer expires and Node (C) adds Node (B) to its DAG parent
      set.  Node (C) has now safely moved deeper within the grounded DAG
      without creating any loops.  Node (D), and any other sub-DAG of
      Node (C), will hear the modified RA-DIO message sourced from Node
      (C) and follow Node (C) in a coordinated manner to reattach to the
      grounded DAG.  The final DAG is depicted in Figure 1-3

   ------------------------------------------------------------------------

      Example: Global Repair with Sequence Number / No Held-Up State

          :                      :                      :
          :                      :                      :
         (A)                    (A)                    (A)
          |\                     |                      |
          | `-----.              |                      |
          |        \             |                      |
         (B)       (C)          (B)       (C)          (B)
                    |                                    \
                    |                                     `-----.
                    |                                            \
                   (D)                    (D)                    (C)

                                                                 (D)

              -1-                    -2-                    -3-

                         Figure 2: DAG Maintenance

   Consider the example depicted in Figure 2-1, similar to that depicted
   in Figure 1.  Let there be a sequence number associated with the DAG,
   as originated from the DAG root, with value N. Initially all nodes
   have received DAG Sequence Number N. The following example offers one
   possible Global Repair scenario to give a high level idea, please
   note that there are details that would remain to be worked out if the
   WG heads in this direction.

   Now consider the case where the link (C)->(A) becomes nonviable, and
   node (C) must move to a deeper rank within the DAG:

   o  Node (C) must first detach from the DAG by removing Node (A) from
      its DAG parent set, leaving an empty DAG parent set.  At this
      point Node (C) is not associated with any DAG [TBD -- Alternately
      Node (C) remains associated with the DAG at rank infinity].

   o  Node (D) may possibly learn that Node (C) is no longer associated
      with any DAG and itself becomes unassociated [TBD Node (D) may
      also retain a sub-DAG relationship with Node (C)].  Let Node (C)
      and (D) both be free from any DAG, but remember the Sequence
      Number N associated with their original DAG.  This is depicted in
      Figure 2-2.

   o  Node (C) and (D) will now be willing to reattach to the original
      DAG at IMMEDIATELY (no hold-up mechanism) at ANY node offering
      connectivity to the original DAG and advertising a sequence number
      N+1.  Since Node (C) and (D) are no longer members of the original
      DAG, only a node who is still a member of the original DAG may
      possibly present the sequence number N+1.  Such a node who
      presents N+1 must clearly have another path to the DAG root other
      than via (C) and (D) and thus may offer a loop-avoiding attachment
      point.

   o  [TBD] The DAG Root may periodically issue sequence number
      increments, causing the issue of N+1

   o  [TBD] The broken link (C)->(A) may be detected through some other
      means, and signalled to or cause a trigger at the DAG Root,
      causing the issue of N+1

   o  Let Node (C) hears a RA-DIO message with N+1 from Node (B) and
      determine it is able to rejoin the original DAG by immediately
      reattaching j to Node (B) (No hold-up state in this example.  The
      DAG is now as depicted in Figure 2-3

   o  Node (C) may then subsequently send RA-DIO with DAG Sequence
      number N+1, allowing Node (D) to reattach (not depicted).

   ------------------------------------------------------------------------

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

---

From: Mukul Goyal <[email-masked]>
Date: Mon, 26 Oct 2009 06:18:28 -0500 (CDT)

Hi Mathilde,

>>       Node (C) remains associated with the DAG at rank infinity].
[Mathilde] Why couldn't Node (C) become the root of its own floating
DAG? I don't think it adds in complexity and it would allow Node (C)
sub-dag to remain connected providing some 'local' connectivity. In
general I don't like the idea of maintaining nodes in an unassociated
state for a potentially unbounded time period.

My understanding is that floating DAGs will be available as an optional feature; they are just not going to be a part of the core specs.

>>       than via (C) and (D) and thus may offer a loop-avoiding
attachment
[Mathilde] This approach is safe but it means that the node needs to
remember the initial DAG id and sequence number, i.e. keep some states
about a DAG it is not part of anymore. What happens if the node joins
other DAGs before going back to the original one? Does it mean you have
to remember all DAGs you ever joined... Maybe an alternative would be to
mandate that the DAG root increments the sequence number periodically
and consider it safe to join a new DAG after waiting for (a multiple of)
this period. This allows to keep less state but is probably not quite as
safe.

Periodic update of seqno by the DAG root may not be desirable in many situations. Such an update forces a new DAG structure to be formed from scratch and may generate significant churn before things stablize.

Would it be sufficient for a node to just consider the highest seqno DIOs received so far as fresh and all other (current and future) DIOs with smaller seqno as stale.

Thanks
Mukul
Best,
Mathilde

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Tim Winter
Sent: vendredi, 23. octobre 2009 19:33
To: ROLL WG
Subject: Re: [Roll] RPL Design Questions

WG,

We are working towards the -04 revision, and in consideration of WG
feedback on these questions have also taken into account the following:
        - The WG has given a clear mandate to reduce complexity
        - Many of these features are related to optimizations, but do
not appear strictly required to operate the core protocol

The mandate to reduce complexity is very clear, the feedback on the list
in support of these features is less so.  Therefore we do propose to
take the following approach proceeding into -04:
        - Recommendations for DAG Splitting and Merging (Detach/Form
transient floating DAG/Reattach) will be removed (loss of
connectivity/sub-DAG poisoning may effectively occur by advertising rank
of infinity)
        - Hold-Up Timer and related states/procedures will be removed
        - Hold-Down Timer and related states/procedures will be removed

It is the objective that by removing these protocol features we are able
to let the basic mechanisms of the core protocol be clear without
additional complexity.  We do not wish to introduce complexity by
including perceived optimizations, but also realize that as the WG
effort proceeds we may find it necessary to reintroduce some part of
these features in some form.  But for now they do not seem strictly
necessary, and it is the hope that by keeping them back the WG may focus
more on the core protocol.

Please let us know your comments/feedback- what do you think?

Thanks,

-RPL Authors

Tim Winter wrote:
> WG,
> 
> Please do let us know what you are thinking w/ regard to the design 
> Questions A, B, & C below.  We hope to include your feedback into the 
> next revision of the document, with FSM descriptions as well.
> 
> Thanks,
> 
> - RPL Authors
> 
> 
>