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

[Philip Levis <pal at cs.stanford.edu>]

On Nov 5, 2009, at 10:48 AM, Jonathan Hui wrote:

> >
>
>
> I agree that Rule 2 of 5.4.2 is problematic.  Though, after your  
> proposed fix, I'm not sure Rule 2 provides any value.  I would  
> propose to simply strike Rule 2 from 5.4.2.
>
> I think the real issue is with the "candidate neighbor"  
> abstraction.  Currently, as specified, candidate neighbor and DAG  
> parent selection are independent processes.  These processes should  
> be more coupled.  For example, it is useful to also consider routing  
> information contained within the DIO to determine if a neighbor  
> should be a candidate neighbor.

I agree.

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.

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.

 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.

 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.

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.

 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.

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.