Re: [Roll] [roll] #7: RPL bootstrap question: neighbor cache and DIOs dependency

[Jonathan Hui <jhui at archrock.com>]

On Nov 5, 2009, at 11:24 AM, Philip Levis wrote:

> Here's my suggested rewrite for 5.2, 5.3, and 5.4. Would love to  
> know if implementers feel this makes things clearer. In this text,  
> the neighbor set is an unconstrained set of L2 neighbors, the parent  
> set is a subset of the neighbor set and is the set of candidate  
> parents, and the parent is the element of the parent set that is the  
> current next hop towards the DAG root. Note that this text discards  
> the sibling notion for the simpler notion of limited local repair.

This text is definitely moving in the right direction.

> 5.2 Neighbors, Parents, and Rank
>
> If Neighbor Unreachability Detection (NUD) determines that a
> neighbor is no longer reachable, then a RPL node
> MUST NOT consider this node a neighbor when calculating and
> advertising routes until the node determines it is reachable again.
>
> Unless it is a DAG root, a node MUST NOT advertise a DAG ID unless
> it has  neighbors who have advertised that DAG ID.
>
> A RPL node that has issued a DIO for a DAGID I, DAG Instance N,
> and sequence number S MUST NOT consider neighbors for I,N whose
> last heard DIO for I,N had a sequence number < S.

I'd change "MUST NOT consider neighbors" to "MUST NOT consider nodes  
as neighbors", or some other wording that cannot be misinterpreted as  
"MUST NOT process messages from neighbors".

> 5.2.1 Parents
>
> By definition, DAG Roots do not have any DAG parents.
>
> RPL nodes that are not roots MAY maintain multiple candidate
> DAG parents for a single DAG Instance. The set of candidate DAG
> parents MUST be a subset of the set of neighbors. At any given
> moment, a node has a single DAG Parent, selected from the set
> of candidate DAG parents.

Not sure why we have to single out THE DAG parent.  The DAG is a DAG  
because a node can maintain more than one candidate parent.  Choosing  
a candidate parent is what defines the forwarding (not routing)  
topology.  More related to this subject below.

> 5.2.2  DAG Rank
>
> DAG Rank is not a cost metric, although its value is derived from
> and influenced by route cost metrics. Rank is used to avoid and
> detect loops. A node's Rank MUST be higher than the Rank of its DAG
> Parent. The exact calculation of the Rank may depend on the set of
> candidate DAG parents, link metrics, node configuration, and the DAG
> Instance OF.

I'd say that the advertised Rank MUST be higher than the Rank of its  
candidate DAG parents, not just the a chosen DAG parent.  We use the  
DAG to identify assign nodes relative position within the network.  It  
doesn't make sense to have a candidate DAG parent that has a higher  
Rank.

> 5.3.  DAG Discovery and Maintenance
>
> DAG discovery forms a Directed Acyclic Graph towards a DAG Root
> by identifying a set of candidate DAG parents and selecting a member
> of the set as its DAG parent. DAG discovery also discovers neighbors,
> which may be used to provide additional path diversity when a node
> needs to move downward in the DAG. DAG discovery avoids
> loops by constraining when and how nodes can increase their Rank.
> RPL uses an IPv6 optional header in data packets to detect loops.
>
> 5.3.1.  DAGs
>
> 1.  A node MAY belong to multiple DAG Instances.
>
> 2.  A DAGID, InstanceID, and DAGSequence number uniquely defines
>     a DAG iteration. All of a node's candidate parents within a DAG
>     instance MUST belong to the same DAG iteration: the last heard
>     DIO from candidate parents must be for the same DAG iteration.

Why not allow a node advertising DAG sequence N forward to a node with  
DAG sequence N+1?  Communication delays means that we can't guarantee  
that this won't happen.  So why restrict it even when we know this is  
true?

> 3.  Within a given DAG instance, a node that is a not a root MUST NOT
>     advertise a DAGSequenceNumber higher than the highest
>     DAGSequenceNumber it has heard.
>
> 4.  The DAGSequenceNumbers a node advertises for a DAG instance MUST
>     monotonically increase, barring wrap-around as covered in X.
>
> 5.  DAG Roots MAY increment the sequence number they advertise.
>
> 6.  A node MUST advertise the same DAGSequenceNumber as its
>     DAG Parent.

Or at least what it thinks the DAGSequenceNumber is for its DAG  
Parent.  This comes back to my previous point - when a new sequence  
number is propagating, nodes will (temporarily) have parents in one  
iteration, and others in another iteration.  I don't think we should  
restrict implementations from waiting for some time to wait for its  
DAG parents to catch up to the current iteration - but I don't think  
we should recommend it either.

The rest looks good to me.

--
Jonathan Hui

> 5.3.2.  DAG Roots
>
> 1.  A DAG Root that does not have Internet connectivity to nodes
>     outside the DAG MUST NOT set the Grounded bit.
>
> 2.  A DAG Root MUST advertise a rank of ROOT_RANK.
>
> 5.3.3.  Rank and DAG Movement
>
> 1.  A node MUST NOT advertise a Rank less than or equal to
>     its DAG parent.
>
> 2.  A node MAY advertise a Rank lower than its prior advertisement.
>
> 3.  A node MAY advertise a Rank higher than its prior advertisement.
>     If the lowest prior Rank advertised for a DAG iteration is L, a
>     node MUST NOT advertise a Rank > L + DAGMaxRankIncrease.
>
> 4.  A node MAY, at any time, choose to join a different DAG within
>     a DAG Instance. Such a join has no Rank restrictions. Until a
>     node transmits a DIO indicating its new position, it MUST forward
>     packets along the previous DAG.
>
> 5.  Joining different DAGs does not preclude rule 3. A node that  
> leaves
>     a DAG iteration and rejoins it later must still obey rule 3 for  
> that
>     DAG iteration.
>
> 5.3.4 Parent Set Depletion
>
> 1.  If a node has no candidate parents, it MAY leave the DAG  
> iteration and
>     advertise itself as the root of a floating DAG. Such a DIO
>     MUST have the same DAG InstanceID as the DAG iteration and a  
> cleared
>     Grounded flag.
>
> 2.  If a node does not form a floating DAG, then the node MUST  
> advertise
>     a rank of INFINITE_RANK within the DAG iteration.
>
> 3.  If a node that receives a DIO from one of its DAG parents
>     indicating that the parent has left the DAG, it may either follow
>     that parent or stay in its current DAG through an alternate DAG
>     parent if that is possible.
>
>
> 5.4.  DIO Message Communication
>
> When an DIO message is received from a source device named SRC, the
> receiving node must first determine whether or not the DIO message
> should be accepted for further processing, and subsequently present
> the DIO message for further processing if eligible.
>
> 5.4.1.  Determination of Eligibility for DIO Processing
>
> If the DIO source is a member of the candidate neighbor set,
> the node MUST process it.
>
> 5.4.2.  DIO Message Processing
>
> When a node processes a DIO from a member of its candidate neighbor
> set, it MUST update all relevant state maintained on that neighbor.
> For example, if a node receives a DIO advertising a different Rank,
> it must update its state to denote the neighbor's new Rank.
>
> 5.4.3.  DIO Transmission
>
> Each node maintains a timer that governs when to multicast DIO
> messages.  This timer is a trickle timer, as detailed in Section 5.X.
> The DIO Configuration Option describes the configuration of a DAG  
> Instance's
> trickle timer.
>
> o  When a node chooses a DAG parent that changes its DAG iteration,
>    it MUST reset the trickle timer to its minimum value.
>
> o  When a node receives a packet to forward from a node with a lower  
> or
>    equal rank, it has detected an inconsistency in the DAG. In this
>    case, the node MUST reset the trickle timer to its minimum value.
>    Section Y describes how a node can detect this.
>
> o  When a node receives a DIS, it MUST reset the trickle timer to
>    the minimum value.
>
> o  If a node is not a member of a DAG, it MAY suppress transmitting
>    DIO messages.