Subject: [Roll] RPL Design Questions

From: Tim Winter <[email-masked]>
Date: Mon, 12 Oct 2009 23:16:18 -0400

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

   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: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 13 Oct 2009 09:16:29 +0200

Hi:

I think Tim did a great job at keeping the question text simple.
Thinking about his own answer on this, one might wonder what the actual
cost of things is and how things are related.

The good news is that as far as I can see, the 3 items of the poll are
not related:

- one could bypass the DAG hop Timer mechanism and still allow the
split/merge mechanism that is used for loop avoidance. The result will
probably be more runtime churn and more battery consumption.
- Alternatively one could ignore the split/merge and stay there, simply
advertising infinity to poison the broken path, and yet, the DAG hop
timer would be useful to avoid churn as the new DAG is constructed to
restore connectivity.
- and the hold down is orthogonal, rather related of the validation
process that takes place before a parent can be used at all.

Even better, it appears that a network that incorporates mixed behaviors
still works correctly. If I'm correct on that, then it could be possible
to make those things optional, like having a fully capable node and a
more constrained node's behavior, and then enable a policies in the
former to more or less act as the latter.

The other aspect of the question is the real cost associated to the
listed items.

Question A: 
------------
Feature benefit:
When this mechanism is in place, a DAG can detach and still enable local
(P2P) connectivity. There are use cases for that, though not really
obvious in our requirement drafts. So obviously we'd be losing that sort
of connectivity if the mechanism

Implementation cost:
When a node detaches, it should in theory keep some history of its
previous DAGs as long as those DAGs live, so as to never jump back in
the same DAG, same sequence but at a higher rank. That would be perfect
loop avoidance. But that's not what the spec does. The spec attempts to
mark the wrong landing sites by route poisoning and then allows any jump
after a reasonable time. So the implementation cost at the end of the
day is one timer, and a bit of logic to decide whether that timer should
be armed at all. The current text allows overloading the DAG Hop Timer
for that purpose (that's Q 2).

Question B:
Feature benefit:
This is all about churn. There are occasions like a new sequence or a
DAG accident (new root inserted or removed, split/merge...) where a DAG
and sometimes neighboring nodes are impacted. If we leave it to chance,
nodes will reposition a number of times before things settle, causing
churn and battery depletion. This timer delays things and forces the
changes to spread like a wave in one pass from the root out.

Implementation cost:
In theory that's one timer per parent that this node wants to jump to.
In terms of implementation, this can be reduced to one timer per DAG
that the node might want to jump to, and even further reduced to one
timer at all if the implementation only keeps track of the most
preferred DAG onto which it could jump. Note that the doc allows the
node to use the same timer for Q A). The feature also requires to pass
the DAG base period in the DIO.

Question C) 
Feature benefit:
A node that has poor history is blacklisted. This prevents it to be
reconsidered as a parent for a configurable period of time. This method
avoid periodic churn and black out, or at least makes that period a lot
longer.

Implementation cost:
In theory one timer per blacklisted node, and some data structure per
blacklisted node. In practice, an implementation can use a single
periodic timer and a list of the blacklisted nodes. It can for instance
maintain a counter per listed node that is incremented at each tick.
When the increment reaches a threshold, the node is removed from the
blasklist.

My vote is YES to all the questions. Keep them in the base spec. 
And allow for a fallback behavior in the real constrained devices if
that can cohabit as I think it does.

Pascal

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Tim Winter
>Sent: mardi 13 octobre 2009 05:16
>To: ROLL WG
>Subject: [Roll] RPL Design Questions
>
>WG,
>

---

From: Tim Winter <[email-masked]>
Date: Fri, 23 Oct 2009 13:33:23 -0400

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

---

From: Mukul Goyal <[email-masked]>
Date: Fri, 23 Oct 2009 22:05:54 -0500 (CDT)

Tim

I think this is a wise approach. I support these changes to the core protocol.

Regards
Mukul
----- Original Message -----
From: "Tim Winter" <[email-masked]>
To: "ROLL WG" <[email-masked]>
Sent: Friday, October 23, 2009 12:33:23 PM GMT -06:00 US/Canada Central
Subject: Re: [Roll] RPL Design Questions

WG,

Thanks,

-RPL Authors

---

From: "Mathilde Durvy (mdurvy)" <[email-masked]>
Date: Mon, 26 Oct 2009 11:45:17 +0100

Hi Tim, All,

I support the proposals made in your email. I think they are a key step
in reducing the complexity of RPL.

Some comments on the "Example: Global Repair with Sequence Number / No
Held-Up State" as it is directly related to what the design team
proposes.

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

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

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.

Thanks,

-RPL Authors

Tim Winter wrote:
> 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
> 
> 
>

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 26 Oct 2009 15:01:04 +0100

Hi Mathilde:

At some point, people get what they ask for. There was a not so
overwhelming request to remove the Hold up and hold down states and
timers so we experienced it. And yes, we have given you apparent
simplicity but then, consequences arise.

>this period. This allows to keep less state but is probably not quite
as

Please see 'implementation cost' sections in the attached mail RPL
design question. (mostly Q.A)

You're right the node has to keep states. In practice, the next version
of the draft also introduces:

- long periods of black hole (till next sequence)
- overstretched routes (nodes jump too fast onto the first guy with the
new sequence)

Unless of course a clever implementation adds special sauce that would
be toying with what's allowed and what's not.

Like introduce a timer that allows to get rid of past DAG states so that
the node which lost memory can faithfully jump anywhere.

Is that safe? 

-Not really, but if that timer is an order of magnitude longer than DIO
propagation, well, that's certainly better than jumping anywhere
blindly, because a number of the wrong targets will be eliminated by the
route poisoning.

-And considering that we have loop detection on the spec now, I'd assume
that yes, it would be a very acceptable behavior.

Guess what. I think that was what the DAG Hop Timer was doing for us.
Hum.

Anyway, nothing is cast in stone at this point, and we might reintroduce
some timers when people realize what they really lost.

Pascal

Pascal

>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Mathilde Durvy (mdurvy)
>Sent: lundi 26 octobre 2009 11:45
>To: Tim Winter; ROLL WG
----------------------------------------------------------------------
>> --
----------------------------------------------------------------------
>> --
----------------------------------------------------------------------
>> --

Subject: Re: [Roll] RPL Design Questions
From: "Pascal Thubert (pthubert)" <[email-masked]>
To: "Tim Winter" <[email-masked]>, "ROLL WG" <[email-masked]>
Date: Tue, 13 Oct 2009 08:16:29 +0100

Hi:

Question A: 
------------
Feature benefit:

Implementation cost:

Question B:
Feature benefit:

Implementation cost:

Question C) 
Feature benefit:

Implementation cost:

Pascal

Tim Winter
>Questions A, B, & C below.  We hope to include your feedback into the
next

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 26 Oct 2009 10:16:40 -0400

Date: Mon, 26 Oct 2009 15:01:04 +0100
   From: "Pascal Thubert (pthubert)" <[email-masked]>

   [...]

Pascal, I agree with you.  I still think we are taking the
right approach.  Cutting back early and then adding features
back in as necessary has two big advantages.  It speeds up
testing by reducing the initial effort required.  It is also
likely to lead to a simpler final result.  The only sure way
to tell if something is not needed is to try running without
it.
                              -Richard Kelsey