Subject: [Roll] RPL Design Questions

From: Tim Winter <[email-masked]>
Date: Wed, 7 Oct 2009 15:43:56 -0700 (PDT)

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

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

---

From: Philip Levis <[email-masked]>
Date: Wed, 14 Oct 2009 18:15:54 -0700

>         the use of DAG Sequence Number; the related mechanisms are to

YES.

>         implementation (perhaps w/ Optional hold-up mechanism)].

NO.

>         specification/implementation (perhaps w/ Optional hold-down

NO.

In my opinion, currently the draft specifies too many mechanisms  
designed to improve efficiency, with little experimental evidence on  
their comparative tradeoffs or value (if any). They are based on a  
conceptual model of wireless that may or may not hold. I think the  
specification should focus on the requirements for interoperability  
between different implementations, not perceived optimizations. Just  
my 2c.

Phil