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

[Stephen Dawson-Haggerty <stevedh at eecs.berkeley.edu>]

In general it's a lot shorter and easier to understand, which is
great.  Was is this a replacement or an addition?  A lot of mechanical
text was removed and I don't know if it's intentional (like in 5.4.2,
when it enumerated when you would discard a message)-- the new one
seems a little more vague about who I'm supposed to store in my
candidate parent sets (5.2)

Also, we lost some of the text explaining why you might want to
increment the dag sequence number (it's split between 5.4.3, 5.3.3,
and 5.3.1).  I would have appreciated a sentence towards the beginning
something like "The effect of incrementing the DAG sequence number is
to trigger additional DIO transmissions.  This serves as an
implementation-controlled mechanism to rebuild forwarding tables among
members of a DAG instance".

Neither document does a great job of explaining the role of the
neighbor set in forwarding, in particular I couldn't find a place
where it said that you might try multiple parents for the same packet.

Thanks,
Steve

On Thu, Nov 5, 2009 at 11:24 AM, Philip Levis <pal at cs.stanford.edu> wrote:
> 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.
>
> _______________________________________________
> Roll mailing list
> Roll at ietf.org
> https://www.ietf.org/mailman/listinfo/roll
>



-- 
stephen dawson-haggerty
http://cs.berkeley.edu/~stevedh
uc berkeley wireless and embedded systems lab
berkeley, ca 94720