Subject: [Roll] [roll] #60: More text to be added to no-path DAO and fan out

From: "roll issue tracker" <[email-masked]>
Date: Tue, 13 Jul 2010 17:44:43 -0000

#60: More text to be added to no-path DAO and fan out
-----------------------------+----------------------------------------------
 Reporter:  jpv@…            |       Owner:  wintert@…      
     Type:  enhancement      |      Status:  new            
 Priority:  major            |   Milestone:                 
Component:  rpl              |     Version:                 
 Severity:  In WG Last Call  |    Keywords:                 
-----------------------------+----------------------------------------------
 Below a discussion on the mailing list, leading to more explanation on no
 path DAO operation and fan-out for revision -11.

 Hi Alexander:
 Thanks a lot for the detailed explanation...appreciate it...this helps
 clears the path control operation.

 I think it would be good if some additional text related to below is added
 to the RFC.

 Some comments:

 1.  "Correspondingly, only new or changed routing/path information that
 originates from the Prefix owner and hence indicated by an incremented
 Path Sequence number must always be passed along to the root."
 I guess this should apply to all DAOs (Path as well as no-Path). I do see
 some issues when a node has multiple DAO parents and they are received and
 processed at a common ancestor.
 2. On a related topic, since there is a preference associated with each
 path for a prefix, a node does not allow for loadbalancing if there are
 multiple paths reported for a prefix. Right?

 Thx

 Regards,
 Navneet

 From: Alexander, Roger [mailto:[email-masked]]
 Sent: Tuesday, July 13, 2010 8:25 AM
 To: Navneet Agarwal (navagar); ROLL WG
 Subject: RE: [Roll] no-Path DAO and fan-out

 Hi Navneet,

 Thanks for the scenario examples which provide a good opportunity to
 highlight/clarify the role of the Path Sequence in the DAO exchanges.
 Below is an explanation of how I envisaged it would/should operate and
 would also be interested in the WG's feedback. (Note: I am assuming your
 reference to Prefix is as used in the generic RPL sense of identifying an
 IPv6 destination address, prefix, or multicast group).

 One advantage accruing to storing nodes, in addition to DAO aggregation,
 is the ability to further reduce routing overhead by removing the
 requirement for sub-DAG changes to always be conveyed all the way to the
 root. In all of the scenarios you have defined, when a common ancestor
 receives a no-Path DAO that is not originated by the Prefix owner (and
 hence should not carry an incremented Path Sequence), there is no
 requirement for that information to be conveyed beyond the common ancestor
 (node C in your examples). Loss of downward path diversity below the
 common ancestor does not mean that path diversity above needs to be
 eliminated. Since the common ancestor still has a downward table entry to
 the Prefix via alternate path(s), its ancestors do not need to be further
 updated. With the maintained Path Sequence in the no-Path DAO, only nodes
 that have a singular downward route to the affected Prefix need to update
 their individual DAO Parent(s). Correspondingly, only new or changed
 routing/path information that originates from the Prefix owner and hence
 indicated by an incremented Path Sequence number must always be passed
 along to the root.

 Note: The implementation option of limiting when the Path Sequence number
 is incremented by a Prefix owner provides a capability to further reduce
 routing overhead for storing nodes - though the few bits needed to fully
 support incremental/partial updates within the DAO would be still needed.

 Where the transmission of the no-Path DAO is being proactively initiated
 by a DAO Parent or other intermediate ancestor node that discovers the
 loss of connectivity (neighbor unreachability detection, NUD) to the node
 that owns the Prefix, the Path Sequence used in the no-Path DAO will be
 the one maintained by the ancestor node (only the owner of the Prefix can
 increment the Path Sequence for that Prefix). This would be the same as
 the Path Sequence maintained by all nodes along the path to the common
 ancestor. The first common ancestor receiving such a no-Path DAO should
 mark the affected downward path for deletion and should take no further
 action with regard to upward forwarding of the DAO.

 If the owner of the Prefix discovers the loss of connection to an existing
 DAO Parent and wishes to update its path connections, including
 potentially re-selecting a different preference set of DAO Parents, the
 node must increment the Path Sequence and transmit DAOs to new desired DAO
 Parents - a no-Path DAO is not required. The incremented Path Sequence
 will necessitate that the updated DAOs be conveyed all the way to the root
 - in the process updating routing tables at intermediate nodes. Where new
 downward paths are established as a result of the updated DAOs, existing
 intermediate routing tables are directly updated. Routing table entries
 that are no longer on the re-established downward paths will be purged
 through the normal expiration of the associated downward route entries.

 Note: If the node that owns the Prefix chooses to maintain its existing
 DAO Parents and preferences (even with the lost connectivity to, or
 desired removal of, a single DAO Parent), it can do so by sending normal
 periodic or triggered DAO updates to the connected DAO Parents without
 incrementing the Path Sequence in the DAO updates. Where connectivity
 exists, the owner of the Prefix may also send a no-Path DAO to delete the
 path through a given DAO Parent. By not incrementing the Path Sequence the
 path through the particular DAO Parent will be removed only to the first
 common ancestor.

 To redefine DAO Parents and preferences (including where necessary to
 maintain fan-out limits), DAOs must be sent with an incremented Path
 Sequence number to the newly desired/re-ordered DAO Parents. The
 incremented Path Sequence DAOs will ensure that the routing change is
 conveyed to the root and recognized by ancestor nodes that can delete
 downward path entries. Where the updated DAOs are received at nodes that
 do not currently have routing entries for the particular Prefix, the
 information is cached and the new DAO information conveyed towards the
 root.

 Based on the above defined operation there is no benefit to the node owner
 of the Prefix sending a no-Path DAO with an incremented Path Sequence.
 This will travel all the way to the root and will have the effect of
 outdating and marking for deletion all existing downward routes for that
 Prefix. Instead, to re-establish desired downward paths, DAOs with
 incremented Path Sequences should be sent to the desired/maintained DAO
 Parents.

 There would be some benefit to being able to send a no-Path DAO to delete
 a single DAO Parent path all the way to the root but the incremented Path
 Sequence will make stale all other valid routing paths (as well as
 introduce the difficulties raised in your assessments). Note once again
 that multiple DAO Parents guarantee only local diversity. Therefore the
 fact that deleting a single DAO Parent using an un-incremented Path
 Sequence removes diversity only to a common ancestor should be seen in the
 context of the local guarantees that are provided.

 SUMMARY: If a no-Path DAO is sent by the Prefix owner to a connected DAO
 Parent to delete the single downward path while maintaining the others,
 the Path Sequence should be maintained (not incremented) indicating that
 all established paths (and preferences) with the exception of the
 identified DAO Parent path is being maintained. The path through the
 particular DAO Parent, only to the first common ancestor, will be deleted.
 Where the no-Path DAO is being proactively sent by an ancestor node due to
 recognition of NUD, the same would apply as the Path Sequence number will
 be the one currently maintained by the ancestor node. The prefix owner
 should never send a no-Path DAO with an incremented Path Sequence but
 should instead send updated DAOs with incremented Path Sequence to re-
 establish or re-order DAO Parents and downward paths.

 The operation for non-storing nodes would be the same. However, in the
 case of non-storing nodes the first common ancestor is always the root
 node. If in the non-storing case a no-path DAO is issued by the owner of
 the Prefix or by a DAO Parent (due to proactive response to NUD), the no-
 Path DAO with an un-incremented Path Sequence will directly allow the root
 to update existing downward paths (removing the identified DAO Parent
 while maintaining ordering of remaining DAO Parents). As in the storing
 case, a no-Path DAO with an incremented Path Sequence would mark all other
 downward paths from the root as potentially outdated (and marked for
 deletion) and so should similarly not be issued.

 This is the operation as I believe it should work but I look forward to
 understanding whether this envisaged operation can fit within the model
 given in -10.

 Make sense? See also a specific related comment below.

 Regards,

 Roger

 From: [email-masked] [mailto:[email-masked]] On Behalf Of
 Navneet Agarwal (navagar)
 Sent: Friday, July 09, 2010 1:26 PM
 To: ROLL WG
 Subject: [Roll] no-Path DAO and fan-out

 Hi WG:
 I am trying to get some clarifications on expected behavior. Have read the
 Path Control document on path ctl field usage (attached). I have put
 several setups and flows, assuming storing nodes but should apply for non-
 storing scenario as well. I could not figure out from the reading the doc
 or the RFC.

 Scenario-1:

 A     B

 \      /

  \   /

    C

   /  \

  /    \

 D     E

 A, B - DAO Parents.....C - Node........D,E- nodes in subdag.

 Assume path control allows two paths.

 D and E have learnt a common prefix for a node below them, Pfx

 D will set x10 in Path control of DAO sent to C

 E will set x01 in Path control of DAO sent to C

 C will set x10 in Path control of DAO sent to A

 C will set x01 in Path control of DAO sent to B

 Suppose E sends a no-Path DAO to C for Pfx with path control x01. What
 does C do? I would think that C will need to send a no-Path. But it has to
 remember that it had sent a DAO with path control x01 to B. If this has to
 happen then C would have to remember for each prefix what path control was
 sent to which parent, which does not seem correct as it would not scale as
 the prefixes at C scale, each having its own path control settings.

 Scenario-2:

 F     G

 \    /

  \  /

    A

     |

     |

    C

   /  \

  /    \

 D     E

 D will set x10 in Path control of DAO sent to C

 E will set x01 in Path control of DAO sent to C

 C will send a DAO with path control x11 to A

 A will send a DAO with path control x01 to F

 A will send a DAO with path control x10 to G

 Suppose E sends a no-Path to C (path control x01). What does C do? It will
 likely send a DAO to A with path control x10. What will A do when it
 receives a DAO with this path control when its previous path control was
 x11?

 I see couple of other flows where path control settings may change due to
 sub-nodes going away and coming back up...for example:

 Scenario-3

 F     G

 \    /

  \  /

    A

     |

     |

    C

   /  \

  /    \

 D     E

 Suppose G is preferred over F.

 Suppose path from E to D is down.

 D sends DAO with path control x10 to C

 C sends DAO with path control x10 to A

 A sends DAO with path control x10 to G

 After some time E comes up and sends a DAO with path control x01 (higher
 path preference than D to C) to C.

 C merges this and sends a DAO with path control x11 to A. What does A do
 since is has indicated a path control of x10 to G. In normal terms, if A
 had received a DAO with path control x11 from C, it would have notified
 DAO to F with path control x10 and DAO to G with path control x01 but due
 to transient conditions it could be reversed.

 [RA] In the case of receipt of the first updated DAO (with incremented
 Path Sequence) only the new information with single path control should be
 forwarded since all prior path information is effectively obsolete by the
 incremented Path Sequence. When subsequent DAO updates are received with
 the new, incremented Path Sequence, only then can the combined path
 control information be forwarded.

 Will appreciate if it can be clarified if the above flows are reasonable
 and what should happen...in general I dont think path control should
 mandate which path control bits are tied to which DAO parent etc...

 [RA] Hopefully the above discussion supports the view that Path Control
 can operate as specified without the need to maintain state on which DAO
 with which Path Control was sent to which DAO Parent.

 Thanks

 Regards,

 Navneet

-- 
Ticket URL: <https://svn.tools.ietf.org/wg/roll/trac/ticket/60>
roll <http://tools.ietf.org/wg/roll/>

---

From: "roll issue tracker" <[email-masked]>
Date: Sun, 25 Jul 2010 08:13:32 -0000

#60: More text to be added to no-path DAO and fan out
-----------------------------+----------------------------------------------
 Reporter:  jpv@…            |        Owner:  wintert@…      
     Type:  enhancement      |       Status:  closed         
 Priority:  major            |    Milestone:                 
Component:  rpl              |      Version:                 
 Severity:  In WG Last Call  |   Resolution:  fixed          
 Keywords:                   |  
-----------------------------+----------------------------------------------
Changes (by jpv@…):

  * status:  new => closed
  * resolution:  => fixed

Comment:

 Text solving the issue to be incorporated in revision -11:

 RPL-11 will be updated as follows:

   Path Control:  8-bit bitfield.  The Path Control field limits the
         number of DAO-Parents to which a DAO message advertising
         connectivity to a specific destination may be sent, as well as
         providing some indication of relative preference.  The limit
         provides some bound on overall DAO message fan-out in the LLN.
         The assignment and ordering of the bits in the path control
         also serves to communicate preference.  Not all of these bits
         may be enabled as according the the PCS in the DODAG
         Configuration.  The Path Control field is divided into four
         subfields which contain two bits each: PC1, PC2, PC3, and PC4,
         as illustrated in Figure 27.  The subfields are ordered by
         preference, with PC1 being the most preferred and PC4 being the
         least preferred.  Within a subfield there is no order of
         preference.  By grouping the parents (as in ECMP) and ordering
         them, the parents may be associated with specific bits in the
         Path Control field in a way that communicates preference.

                                    0 1 2 3 4 5 6 7
                                   +-+-+-+-+-+-+-+-+
                                   |PC1|PC2|PC3|PC4|
                                   +-+-+-+-+-+-+-+-+

              Figure 27: Path Control Preference Sub-field Encoding

  -----

   Generation of DAO Messages

   A node might send DAO messages when it receives DAO messages, as a
   result of changes in its DAO parent set, or in response to another
   event such as the expiry of a related prefix lifetime.  In the case
   of receiving DAOs, it matters whether the DAO message is "new," or
   contains new information.  In non-storing mode, every DAO message a
   node receives is "new."  In storing mode, a DAO message is "new" if
   it satisfies any of these criteria for a contained Target:

   1.  it has a newer Path Sequence number,

   2.  it has additional Path Control bits, or

   3.  is a No-Path DAO message that removes the last downward route to
       a prefix.

   A node that receives a DAO message from its sub-DODAG MAY suppress
   scheduling a DAO message transmission if that DAO message is not new.

  -----

 9.X  Path Control

   A DAO message from a node contains one or more Target Options.  Each
   Target Option specifies either the node's prefix, a prefix of
   addresses reachable outside the LLN, or a destination in the node's
   sub-DODAG.  The Path Control field of the Transit Information option
   allows nodes to request or allow for multiple downward routes.  A
   node constructs the Path Control field of a Transit Information
   option as follows:

   1.  The bit width of the path control field MUST be equal to the
       value (PCS + 1), where PCS is specified in the control field of
       the DODAG Configuration Option.  Bits greater than or equal to
       the value (PCS + 1) MUST be cleared on transmission and MUST be
       ignored on reception.  Bits below that value are considered
       "active" bits.

   2.  The node MUST logically construct groupings of its DAO parents
       while populating the Path Control field, where each group
       consists of DAO parents of equal preference.  Those groups MUST
       then be ordered according to preference, which allows for a
       logical mapping of DAO parents onto Path Control subfields (See
       Figure 27).  Groups MAY be repeated in order to extend over the
       entire bit width of the patch control field, but the order,
       including repeated groups, MUST be retained so that preference is
       properly communicated.

   3.  For a RPL Target option describing a node's own address or a
       prefix outside the LLN, at least one active bit of the Path
       Control field MUST be set.  More active bits of the Path Control
       field MAY be set.

   4.  If a node receives multiple DAOs with the same RPL Target option,
       it MUST bitwise-OR the Path Control fields it receives.  This
       aggregated bitwise-OR represents the number of downward routes
       the prefix requests.

   5.  When a node sends a DAO message to one of its DAO parents, it
       MUST select one or more of the bits that are set active in the
       subfield that is mapped to the group containing that DAO parent
       from the aggregated Path Control field.  A given bit can only be
       presented as active to one parent.  The DAO message it transmits
       to its parent MUST have these active bits set and all other
       active bits cleared.

   6.  For the RPL Target option and DAOSequence number, the DAOs a node
       sends to different DAO parents MUST have disjoint sets of active
       Path Control bits.  A node MUST NOT set the same active bit on
       DAOs to two different DAO parents.

   7.  Path control bits SHOULD be allocated according to the preference
       mapping of DAO parents onto Path Control subfields, such that the
       active Path Control bits, or groupings of bits, that belong to a
       particular Path Control subfield are allocated to DAO parents
       within the group that was mapped to that subfield.

   8.  In a non-storing mode of operation, a node MAY pass DAOs through
       without performing any further processing on the Path Control
       field.

   9.  A node MUST NOT unicast a DAO message that has no active bits in
       the Path Control field set.  It is possible that, for a given
       Target option, that a node does not have enough aggregate Path
       Control bits to send a DAO message containing that Target to each
       of its DAO Parents, in which case those least preferred DAO
       Parents may not get a DAO message for that Target.

   The Path Control field allows a node to bound how many downward
   routes will be generated to it.  It sets a number of bits in the Path
   Control field equal to the maximum number of downward routes it
   prefers.  Each bit is sent to at most one DAO parent; clusters of
   bits can be sent to a single DAO parent for it to divide among its
   own DAO parents.

   A node that provisions a DAO route for a Target that has an associate
   Path Control field SHOULD use content of that Path Control field in
   order to determine an order of preference among multiple alternative
   DAO routes for that Target.  The Path Control field assignment is
   derived from preference (of the DAO parents), as determined on the
   basis of this node's best knowledge of the "end-to-end" aggregated
   metrics in the "downward" direction as per the objective function.
   In non-storing mode the root can determine the downward route by
   recursively selecting the best preference 1 hop-route.

 9.X.1.  Path Control Example

   Suppose that there is an LLN operating in storing mode that contains
   a Node N with four parents, P1, P2, P3, and P4.  Let N have three
   children, C1, C2, and C3 in its sub-DODAG.  Let PCS be 7, such that
   there will be 8 active bits in the Path Control field: 11111111b.
   Consider the following example:

   The Path Control field is split into 4 subfields, PC1 (11000000b),
   PC2 (00110000b), PC3 (00001100b), and PC4 (00000011b), such that
   those 4 subfields represent 4 different levels of preference as per
   Figure 27.  The implementation at Node N, in this example, groups
   {P1, P2} to be of equal preference to each other, and the most
   preferred group overall. {P3} is less preferred to {P1, P2}, and more
   preferred to {P4}.  Let Node N then perform its path control mapping
   such that:
              {P1, P2} -> PC1 (11000000b) in the Path Control field
              {P3}     -> PC2 (00110000b) in the Path Control field
              {P4}     -> PC3 (00001100b) in the Path Control field
              {P4}     -> PC4 (00000011b) in the Path Control field

   Note that the implementation repeated {P4} in order to get complete
   coverage of the Path Control field.

   1.   Let C1 send a DAO containing a Target T with a Path Control
        10000000b.  Node N stores an entry associating 10000000b with
        the Path Control field for C1 and Target T.

   2.   Let C2 send a DAO containing a Target T with a Path Control
        00010000b.  Node N stores an entry associating 00010000b with
        the Path Control field for C1 and Target T.

   3.   Let C3 send a DAO containing a Target T with a Path Control
        00001100b.  Node N stores an entry associating 00001100b with
        the Path Control field for C1 and Target T.

   4.   At some later time, Node N generates a DAO for Target T. Node N
        will construct an aggregate Path Control field by ORing together
        the contribution from each of its children that have given a DAO
        for Target T. The aggregate Path Control field thus has the
        active bits set as: 10011100b.

   5.   Node N then distributes the aggregate Path Control bits among
        its parents P1, P2, P3, and P4 in order to prepare the DAO
        messages.

   6.   P1 and P2 are eligible to receive active bits from the most
        preferred subfield (11000000b).  Those bits are 10000000b in the
        aggregate Path Control field.  Node N must the bit to one of the
        two parents only.  In this case, Node P1 is allocated the bit,
        and gets the Path Control field 10000000b for its DAO.  There
        are no bits left to allocate to Node P2, thus Node P2 would have
        a Path Control field of 00000000b and a DAO cannot be generated
        to Node P2 since there are no active bits.

   7.   The second-most preferred subfield (00110000b) has the active
        bits 00010000b.  Node N has mapped P3 to this subfield.  Node N
        may allocates the active bit to P3, constructing a DAO for P3
        containing Target T with a Path Control of 00010000b.

   8.   The third-most preferred subfield (00001100b) has the active
        bits 00001100b.  Node N has mapped P4 to this subfield.  Node N
        may allocate both bits to P4, constructing a DAO for P4
        containing Target T with a Path Control of 00001100b.

   9.   The least preferred subfield (00000011b) has no active bits.
        Had there been active bits, those bits would have been added to
        the Path Control field of the DAO constructed for P4.

   10.  The process of populating the DAO messages destined for P1, P2,
        P3, P4 with other targets (other than T) proceeds as according
        the aggregate path control fields collected for those targets.

-- 
Ticket URL: <https://svn.tools.ietf.org/wg/roll/trac/ticket/60#comment:1>
roll <http://tools.ietf.org/wg/roll/>