--- 1/draft-ietf-roll-rpl-02.txt 2009-10-06 03:12:11.000000000 +0200 +++ 2/draft-ietf-roll-rpl-03.txt 2009-10-06 03:12:11.000000000 +0200 @@ -1,21 +1,21 @@ Networking Working Group T. Winter, Ed. Internet-Draft Intended status: Standards Track P. Thubert, Ed. -Expires: March 27, 2010 Cisco Systems +Expires: April 7, 2010 Cisco Systems ROLL Design Team IETF ROLL WG - September 23, 2009 + October 4, 2009 RPL: Routing Protocol for Low Power and Lossy Networks - draft-ietf-roll-rpl-02 + draft-ietf-roll-rpl-03 Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. @@ -24,21 +24,21 @@ and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. - This Internet-Draft will expire on March 27, 2010. + This Internet-Draft will expire on April 7, 2010. Copyright Notice Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights @@ -72,110 +72,116 @@ 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1. Design Principles . . . . . . . . . . . . . . . . . . . . 6 1.2. Expectations of Link Layer Behavior . . . . . . . . . . . 7 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 7 3. Protocol Model . . . . . . . . . . . . . . . . . . . . . . . . 9 3.1. Protocol Properties Overview . . . . . . . . . . . . . . . 9 3.1.1. IPv6 Architecture . . . . . . . . . . . . . . . . . . 9 3.1.2. Typical LLN Traffic Patterns . . . . . . . . . . . . . 10 3.1.3. Constraint Based Routing . . . . . . . . . . . . . . . 10 3.2. Protocol Operation . . . . . . . . . . . . . . . . . . . . 10 - 3.2.1. DAG Construction . . . . . . . . . . . . . . . . . . . 11 - 3.2.2. Destination Advertisement . . . . . . . . . . . . . . 21 - 3.3. Other Considerations . . . . . . . . . . . . . . . . . . . 23 - 3.3.1. DAG Rank and Loop Avoidance . . . . . . . . . . . . . 23 - 3.3.2. DAG Parent Selection, Stability, and Greediness . . . 27 - 3.3.3. Merging DAGs . . . . . . . . . . . . . . . . . . . . . 29 - 3.4. Local and Temporary Routing Decision . . . . . . . . . . . 32 - 3.5. Maintenance of Routing Adjacency . . . . . . . . . . . . . 32 - 4. Constraint Based Routing in LLNs . . . . . . . . . . . . . . . 33 - 4.1. Routing Metrics . . . . . . . . . . . . . . . . . . . . . 33 - 4.2. Routing Constraints . . . . . . . . . . . . . . . . . . . 34 - 4.3. Constraint Based Routing . . . . . . . . . . . . . . . . . 34 - 5. RPL Protocol Specification . . . . . . . . . . . . . . . . . . 35 - 5.1. DAG Information Option . . . . . . . . . . . . . . . . . . 35 - 5.1.1. DAG Information Option (DIO) base option . . . . . . . 35 - 5.2. Conceptual Data Structures . . . . . . . . . . . . . . . . 42 - 5.2.1. Candidate Neighbors Data Structure . . . . . . . . . . 42 - 5.2.2. Directed Acyclic Graphs (DAGs) Data Structure . . . . 43 - 5.3. DAG Discovery and Maintenance . . . . . . . . . . . . . . 44 - 5.3.1. DAG Discovery Rules . . . . . . . . . . . . . . . . . 45 - 5.3.2. Reception and Processing of RA-DIO messages . . . . . 47 - 5.3.3. RA-DIO Transmission . . . . . . . . . . . . . . . . . 49 - 5.3.4. Trickle Timer for RA Transmission . . . . . . . . . . 50 - 5.4. DAG Heartbeat . . . . . . . . . . . . . . . . . . . . . . 52 - 5.5. DAG Selection . . . . . . . . . . . . . . . . . . . . . . 52 - 5.6. Administrative rank . . . . . . . . . . . . . . . . . . . 53 - 5.7. Candidate DAG Parent States and Stability . . . . . . . . 53 - 5.7.1. Held-Up . . . . . . . . . . . . . . . . . . . . . . . 53 - 5.7.2. Held-Down . . . . . . . . . . . . . . . . . . . . . . 54 - 5.7.3. Collision . . . . . . . . . . . . . . . . . . . . . . 54 - 5.7.4. Instability . . . . . . . . . . . . . . . . . . . . . 55 - 5.8. Guidelines for Objective Code Points . . . . . . . . . . . 56 - 5.8.1. Objective Function . . . . . . . . . . . . . . . . . . 56 - 5.8.2. Objective Code Point 0 (OCP 0) . . . . . . . . . . . . 58 - 5.9. Establishing Routing State Outward Along the DAG . . . . . 60 - 5.9.1. Destination Advertisement Message Formats . . . . . . 61 - 5.9.2. Destination Advertisement Operation . . . . . . . . . 63 - 5.10. Multicast Operation . . . . . . . . . . . . . . . . . . . 70 - 5.11. Maintenance of Routing Adjacency . . . . . . . . . . . . . 71 - 5.12. Packet Forwarding . . . . . . . . . . . . . . . . . . . . 72 - 5.12.1. Loop Taxonomy . . . . . . . . . . . . . . . . . . . . 73 - 6. RPL Variables . . . . . . . . . . . . . . . . . . . . . . . . 74 - 7. Manageability Considerations . . . . . . . . . . . . . . . . . 75 - 7.1. Control of Function and Policy . . . . . . . . . . . . . . 75 - 7.1.1. Initialization Mode . . . . . . . . . . . . . . . . . 75 - 7.1.2. DIO Base option . . . . . . . . . . . . . . . . . . . 76 - 7.1.3. Trickle Timers . . . . . . . . . . . . . . . . . . . . 77 - 7.1.4. DAG Heartbeat . . . . . . . . . . . . . . . . . . . . 77 - 7.1.5. The Destination Advertisement Option . . . . . . . . . 78 - 7.1.6. Policy Control . . . . . . . . . . . . . . . . . . . . 78 - 7.1.7. Data Structures . . . . . . . . . . . . . . . . . . . 78 - 7.2. Information and Data Models . . . . . . . . . . . . . . . 78 - 7.3. Liveness Detection and Monitoring . . . . . . . . . . . . 79 - 7.3.1. Candidate Neighbor Data Structure . . . . . . . . . . 79 - 7.3.2. Directed Acyclic Graph (DAG) Table . . . . . . . . . . 79 - 7.3.3. Routing Table . . . . . . . . . . . . . . . . . . . . 80 - 7.3.4. Other RPL Monitoring Parameters . . . . . . . . . . . 80 - 7.3.5. RPL Trickle Timers . . . . . . . . . . . . . . . . . . 80 - 7.4. Verifying Correct Operation . . . . . . . . . . . . . . . 80 + 3.2.1. DAG Construction . . . . . . . . . . . . . . . . . . . 12 + 3.2.2. Destination Advertisement . . . . . . . . . . . . . . 19 + 3.3. Loop Avoidance and Stability . . . . . . . . . . . . . . . 21 + 3.3.1. Greediness and Rank-based Instabilities . . . . . . . 22 + 3.3.2. Merging DAGs . . . . . . . . . . . . . . . . . . . . . 22 + 3.3.3. DAG Loops . . . . . . . . . . . . . . . . . . . . . . 23 + 3.3.4. DAO Loops . . . . . . . . . . . . . . . . . . . . . . 23 + 3.3.5. Sibling Loops . . . . . . . . . . . . . . . . . . . . 23 + 3.4. Local and Temporary Routing Decision . . . . . . . . . . . 24 + 3.5. Maintenance of Routing Adjacency . . . . . . . . . . . . . 25 + 4. Constraint Based Routing in LLNs . . . . . . . . . . . . . . . 25 + 4.1. Routing Metrics . . . . . . . . . . . . . . . . . . . . . 25 + 4.2. Routing Constraints . . . . . . . . . . . . . . . . . . . 26 + 4.3. Constraint Based Routing . . . . . . . . . . . . . . . . . 26 + 5. RPL Protocol Specification . . . . . . . . . . . . . . . . . . 27 + 5.1. DAG Information Option . . . . . . . . . . . . . . . . . . 27 + 5.1.1. DAG Information Option (DIO) base option . . . . . . . 27 + 5.2. Conceptual Data Structures . . . . . . . . . . . . . . . . 34 + 5.2.1. Candidate Neighbors Data Structure . . . . . . . . . . 34 + 5.2.2. Directed Acyclic Graphs (DAGs) Data Structure . . . . 35 + 5.3. DAG Discovery and Maintenance . . . . . . . . . . . . . . 36 + 5.3.1. DAG Discovery Rules . . . . . . . . . . . . . . . . . 37 + 5.3.2. Reception and Processing of RA-DIO messages . . . . . 39 + 5.3.3. RA-DIO Transmission . . . . . . . . . . . . . . . . . 41 + 5.3.4. Trickle Timer for RA Transmission . . . . . . . . . . 42 + 5.4. DAG Heartbeat . . . . . . . . . . . . . . . . . . . . . . 44 + 5.5. DAG Selection . . . . . . . . . . . . . . . . . . . . . . 44 + 5.6. Administrative rank . . . . . . . . . . . . . . . . . . . 45 + 5.7. Candidate DAG Parent States and Stability . . . . . . . . 45 + 5.7.1. Held-Up . . . . . . . . . . . . . . . . . . . . . . . 45 + 5.7.2. Held-Down . . . . . . . . . . . . . . . . . . . . . . 46 + 5.7.3. Collision . . . . . . . . . . . . . . . . . . . . . . 46 + 5.7.4. Instability . . . . . . . . . . . . . . . . . . . . . 47 + 5.8. Guidelines for Objective Code Points . . . . . . . . . . . 48 + 5.8.1. Objective Function . . . . . . . . . . . . . . . . . . 48 + 5.8.2. Objective Code Point 0 (OCP 0) . . . . . . . . . . . . 50 + + 5.9. Establishing Routing State Outward Along the DAG . . . . . 52 + 5.9.1. Destination Advertisement Message Formats . . . . . . 53 + 5.9.2. Destination Advertisement Operation . . . . . . . . . 55 + 5.10. Multicast Operation . . . . . . . . . . . . . . . . . . . 62 + 5.11. Maintenance of Routing Adjacency . . . . . . . . . . . . . 63 + 5.12. Packet Forwarding . . . . . . . . . . . . . . . . . . . . 64 + 6. RPL Variables . . . . . . . . . . . . . . . . . . . . . . . . 65 + 7. Manageability Considerations . . . . . . . . . . . . . . . . . 66 + 7.1. Control of Function and Policy . . . . . . . . . . . . . . 66 + 7.1.1. Initialization Mode . . . . . . . . . . . . . . . . . 66 + 7.1.2. DIO Base option . . . . . . . . . . . . . . . . . . . 66 + 7.1.3. Trickle Timers . . . . . . . . . . . . . . . . . . . . 67 + 7.1.4. DAG Heartbeat . . . . . . . . . . . . . . . . . . . . 68 + 7.1.5. The Destination Advertisement Option . . . . . . . . . 68 + 7.1.6. Policy Control . . . . . . . . . . . . . . . . . . . . 68 + 7.1.7. Data Structures . . . . . . . . . . . . . . . . . . . 68 + 7.2. Information and Data Models . . . . . . . . . . . . . . . 69 + 7.3. Liveness Detection and Monitoring . . . . . . . . . . . . 69 + 7.3.1. Candidate Neighbor Data Structure . . . . . . . . . . 69 + 7.3.2. Directed Acyclic Graph (DAG) Table . . . . . . . . . . 69 + 7.3.3. Routing Table . . . . . . . . . . . . . . . . . . . . 70 + 7.3.4. Other RPL Monitoring Parameters . . . . . . . . . . . 70 + 7.3.5. RPL Trickle Timers . . . . . . . . . . . . . . . . . . 70 + 7.4. Verifying Correct Operation . . . . . . . . . . . . . . . 71 7.5. Requirements on Other Protocols and Functional - Components . . . . . . . . . . . . . . . . . . . . . . . . 81 - 7.6. Impact on Network Operation . . . . . . . . . . . . . . . 81 - 8. Security Considerations . . . . . . . . . . . . . . . . . . . 81 - 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 81 - 9.1. DAG Information Option (DIO) Base Option . . . . . . . . . 81 - 9.2. New Registry for the Flag Field of the DIO Base Option . . 81 - 9.3. DAG Information Option (DIO) Suboption . . . . . . . . . . 82 - 9.4. Destination Advertisement Option (DAO) Option . . . . . . 82 - 9.5. Objective Code Point . . . . . . . . . . . . . . . . . . . 82 - 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 83 - 11. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 83 - 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 84 - 12.1. Normative References . . . . . . . . . . . . . . . . . . . 84 - 12.2. Informative References . . . . . . . . . . . . . . . . . . 84 - Appendix A. Deferred Requirements . . . . . . . . . . . . . . . . 86 - Appendix B. Examples . . . . . . . . . . . . . . . . . . . . . . 87 - B.1. Moving Down a DAG . . . . . . . . . . . . . . . . . . . . 88 - B.2. Link Removed . . . . . . . . . . . . . . . . . . . . . . . 89 - B.3. Link Added . . . . . . . . . . . . . . . . . . . . . . . . 89 - B.4. Node Removed . . . . . . . . . . . . . . . . . . . . . . . 90 - B.5. New LBR Added . . . . . . . . . . . . . . . . . . . . . . 90 - B.6. Destination Advertisement . . . . . . . . . . . . . . . . 91 - Appendix C. Additional Examples . . . . . . . . . . . . . . . . . 92 - Appendix D. Outstanding Issues . . . . . . . . . . . . . . . . . 96 - D.1. Additional Support for P2P Routing . . . . . . . . . . . . 96 - D.2. Loop Detection . . . . . . . . . . . . . . . . . . . . . . 96 - D.3. Destination Advertisement / DAO Fan-out . . . . . . . . . 96 - D.4. Source Routing . . . . . . . . . . . . . . . . . . . . . . 96 - D.5. Address / Header Compression . . . . . . . . . . . . . . . 97 - Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 97 + Components . . . . . . . . . . . . . . . . . . . . . . . . 71 + 7.6. Impact on Network Operation . . . . . . . . . . . . . . . 71 + 8. Security Considerations . . . . . . . . . . . . . . . . . . . 71 + 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 71 + 9.1. DAG Information Option (DIO) Base Option . . . . . . . . . 71 + 9.2. New Registry for the Flag Field of the DIO Base Option . . 71 + 9.3. DAG Information Option (DIO) Suboption . . . . . . . . . . 72 + 9.4. Destination Advertisement Option (DAO) Option . . . . . . 72 + 9.5. Objective Code Point . . . . . . . . . . . . . . . . . . . 72 + 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 73 + 11. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 73 + 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 74 + 12.1. Normative References . . . . . . . . . . . . . . . . . . . 74 + 12.2. Informative References . . . . . . . . . . . . . . . . . . 74 + Appendix A. Deferred Requirements . . . . . . . . . . . . . . . . 76 + Appendix B. Examples . . . . . . . . . . . . . . . . . . . . . . 77 + B.1. Moving Down a DAG . . . . . . . . . . . . . . . . . . . . 78 + B.2. Link Removed . . . . . . . . . . . . . . . . . . . . . . . 79 + B.3. Link Added . . . . . . . . . . . . . . . . . . . . . . . . 79 + B.4. Node Removed . . . . . . . . . . . . . . . . . . . . . . . 80 + B.5. New LBR Added . . . . . . . . . . . . . . . . . . . . . . 80 + B.6. Destination Advertisement . . . . . . . . . . . . . . . . 81 + B.7. Example: DAG Parent Selection . . . . . . . . . . . . . . 82 + B.8. Example: DAG Maintenance . . . . . . . . . . . . . . . . . 83 + B.9. Example: Greedy Parent Selection and Instability . . . . . 84 + B.10. Example: DAG Merge . . . . . . . . . . . . . . . . . . . . 86 + Appendix C. Additional Examples . . . . . . . . . . . . . . . . . 88 + Appendix D. Outstanding Issues . . . . . . . . . . . . . . . . . 92 + D.1. Additional Support for P2P Routing . . . . . . . . . . . . 92 + D.2. Loop Detection . . . . . . . . . . . . . . . . . . . . . . 92 + D.3. Destination Advertisement / DAO Fan-out . . . . . . . . . 92 + D.4. Source Routing . . . . . . . . . . . . . . . . . . . . . . 92 + D.5. Address / Header Compression . . . . . . . . . . . . . . . 93 + Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 93 1. Introduction Low Power and Lossy Networks (LLNs) are made largely of constrained nodes (with limited processing power, memory, and sometimes energy when they are battery operated). These routers are interconnected by lossy links, most of the time supporting only low data rates, that are usually fairly unstable with relatively low packet delivery rates. Another characteristic of such networks is that the traffic patterns are not simply unicast, but in many cases point-to- @@ -347,21 +353,21 @@ Further, RPL is designed with consideration to the practical support and implementation of IPv6 architecture on devices which may operate under severe resource constraints, including but not limited to memory, processing power, energy, and communication. The RPL design does not presume high quality reliable links, and operates over lossy links (usually low bandwidth with low packet delivery success rate). 3.1.2. Typical LLN Traffic Patterns - Multipoint-to-point (MP2P) and Point-to-multipoint (P2MP) traffic + Multipoint-to-Point (MP2P) and Point-to-multipoint (P2MP) traffic flows from nodes within the LLN from and to egress points are very common in LLNs. Low power and lossy network Border Router (LBR) nodes may typically be at the root of such flows, although such flows are not exclusively rooted at LBRs as determined on an application- specific basis. In particular, several applications such as building or home automation do require P2P (Point-to-Point) communication. As required by the aforementioned routing requirements documents, RPL supports the installation of multiple paths. The use of multiple paths include sending duplicated traffic along diverse paths, as well @@ -384,535 +390,447 @@ RPL supports the computation and installation of different paths in support of and optimized for a set of application and implementation specific constraints, as guided by an OCP. Traffic may subsequently be directed along the appropriate constrained path based on traffic marking within the IPv6 header. For more details on the approach towards constraint-based routing, see Section 4. 3.2. Protocol Operation + A LLN deployment will consist of a number of nodes and a number of + edges (links) between them, whose characteristics will depend on + implementation and link layer (L2) specifics. Due to the nature of + the LLN environment the L2 links are expected to demonstrate a large + degree of variance as to their availability, quality, and other + related parameters. Certain links, demonstrating a viability above a + confidence threshold for particular node and link metrics, as based + on guidelines from [I-D.ietf-roll-routing-metrics], will be extracted + from the L2 graph, and the resulting graph will be used as the basis + on which to operate the routing protocol. Note that as the + characteristics of the L2 topology vary over time the set of viable + links is to be updated and the routing protocol thus continues to + evaluate the LLN. In RPL this process happens in a distributed + manner, and from the perspective of a single node running RPL this + process results in a set of candidate neighbors, with associated node + and link metrics as well as confidence values. + + Many of the dominant traffic flows in support of the LLN application + scenarios are MP2P flows ([I-D.ietf-roll-building-routing-reqs], + [I-D.ietf-roll-home-routing-reqs], + [I-D.ietf-roll-indus-routing-reqs], and [RFC5548]). These flows are + rooted at designated nodes that have some application significance, + such as providing connectivity to an external routed infrastructure. + The term "external" is used top refer to the public Internet or a + core private (non-LLN) IP network. In support of this dominant flow + RPL constructs Directed Acyclic Graphs (DAGs) on top of the viable + LLN topology, selecting and orienting links among candidate neighbors + toward DAG roots which root the MP2P flows. + LLN nodes running RPL will construct Directed Acyclic Graphs (DAGs) rooted at designated nodes that generally have some application significance, such as providing connectivity to an external routed infrastructure. The term "external" is used top refer to the public - Internet or a core private (non-LLN) IP network. The DAG is - sufficient to support inward MP2P traffic flows, flowing inward along - the LLN towards a sink (DAG root), which is one of the dominant - traffic flows described in the requirements documents - ([I-D.ietf-roll-building-routing-reqs], - - [I-D.ietf-roll-home-routing-reqs], - [I-D.ietf-roll-indus-routing-reqs], and [RFC5548]). - - By utilizing a DAG for dominant MP2P flows, RPL allows each node to - select and maintain potentially multiple successors capable of - forwarding traffic inwards towards the root. The DAG does not - present as many single points of failure as a tree, and in addition - can offer a node a set of pre-computed successors in support of, e.g. - local route repair in case of a temporary failure, load balancing, or - short term fluctuations in link characteristics. + Internet or a core private (non-LLN) IP network. This structure + provides the routing solution for the dominant MP2P traffic flows. + The DAG structure further provides each node potentially multiple + successors for MP2P flows, which may be used for, e.g., local route + repair or load balancing. - A DAG also serves to restrict the routing problem on the nodes when - it is used as a reference topology. This allows nodes to determine - their positions in a DAG relative to each other and provides a means - to coordinate route repair in a way that endeavors to avoid loops. - These mechanisms will be described in more detail later in this - specification. + Nodes running RPL are able to further restrict the scope of the + routing problem by using the DAG as a reference topology. By + referencing a rank property that is related to the positions in the + DAG, nodes are able to determine their positions in a DAG relative to + each other. This information is used by RPL in part to construct + rules for movement relative to the DAG that endeavor to avoid loops. + It is important to note that the rank property is derived from + metrics, and not directly from the position in the DAG, as will be + discussed further. As DAGs are organized, RPL will use a destination advertisement mechanism to build up routing tables in support of outward P2MP traffic flows. This mechanism, using the DAG as a reference, distributes routing information across intermediate nodes (between the DAG leaves and the root), guided along the DAG, such that the routes toward destination prefixes in the outward direction may be set up. As the DAG undergoes modification during DAG maintenance, the destination advertisement mechanism can be triggered to update the outward routing state. - Arbitrary P2P traffic may flow inward along the DAG until a common - parent is reached who has stored an entry for the destination in its - routing table and is capable of directing the traffic outward along - the correct outward path. In the present specification RPL does not - specify nor preclude any additional mechanisms that may be capable to - compute and install more optimal routes into LLN nodes in support of - arbitrary P2P traffic according to some routing metric. + A baseline support for P2P traffic in RPL is provided by the DAG, as + P2P traffic may flow inward along the DAG until a common parent is + reached who has stored an entry for the destination in its routing + table and is capable of directing the traffic outward along the + correct outward path. RPL also provides support for the trivial case + where a P2P destination may be a `one-hop' neighbor. In the present + specification RPL does not specify nor preclude any additional + mechanisms that may be capable to compute and install more optimal + routes into LLN nodes in support of arbitrary P2P traffic according + to some routing metric. 3.2.1. DAG Construction -3.2.1.1. Overview of a Typical Case - RPL constructs one or more DAGs, over gradients defined by optimizing cost metrics along paths rooted at designated nodes. - DAGs may be grounded, in which case the DAG root (e.g. an LBR) is - offering connectivity to an external routed infrastructure such as - the public Internet or a private core (non-LLN) IP network. A - typical goal for a node participating in DAG construction may be to - find and join a grounded DAG. Any DAG which is not grounded is - floating, and routes may still be provisioned toward the DAG root - although with no expectations of reaching an external infrastructure. - - In the context of a particular LLN application one or more nodes will - be capable of, e.g. serving as an LBR or acting as a data collection - point, and thus be provisioned to act as the most preferred DAG - roots. These nodes will initiate and continue the process of - constructing a DAG by occasionally emitting IPv6 Router Advertisement - (RA) messages containing the necessary information for neighboring - nodes to evaluate the DAG root as a potential DAG parent. This - information will include at least a DAGID, an administrative - preference, and an Objective Code Point (OCP). The DAGID is an - identifier unique to the DAG. The administrative preference offers a - way to engineer the formation of the DAG in support of the - application, by providing a mechanism by which the DAG may look more - or less attractive for other nodes to join. The OCP provides - information as to which metrics and optimization goals are being - employed across the DAG. - - Nodes who hear RA messages, advertising a specific DAGID, will take - into consideration several criteria when processing the extracted DAG - information. A node may seek a DAG advertising a specific OCP, - reflecting the implementation specific routing constraints understood - by the node. In particular, a node will be seeking to find a least - cost path satisfying some objective function as indicated by the OCP - according to some routing metrics defined in - [I-D.ietf-roll-routing-metrics]. For example, the least cost path - may be determined in part by minimizing energy along a path, or - latency, or avoiding the use of battery powered nodes. A node may be - seeking to explicitly join a grounded DAG. Further, a node may seek - the most desirable administrative preference when selecting a DAG, - all else being equal. Based on the evaluation of such criteria, a - node may determine if the node who emitted the RA message should be - considered as a potential DAG parent. If so, then the node may add - the advertising node to its set of candidate DAG parents for the - advertised DAGID, and after waiting for a designated delay, the node - may follow the procedures to activate the advertising node as a DAG - parent and may then be considered to have joined the DAG designated - by DAGID. - - When a node adds the first DAG parent to the set of DAG parents for a - particular DAGID, the node is said to have joined, or attached to, - the DAG designated by DAGID. Adding additional DAG parents beyond - the first simply increases path diversity inwards toward the DAG - root. When a node removes the last DAG parent from the set of DAG - parents for a particular DAGID, the node is said to have left, or - detached from, the DAG designated by DAGID. RPL will coordinate the - joining, leaving, and movement of nodes within a DAGID in such a way - so as to avoid the formation of loops, as described further below. - - As nodes join the DAG they are able advertise the fact by - multicasting the DAG information in RA messages (to neighbors with a - link-local scope). In this way, nodes are able to join the DAG at - ever-increasing rank outward from the DAG root. As nodes continue to - receive DAG multicasts they may continue to expand their set of DAG - parents, while employing loop avoidance strategies as described - below, in order to build path diversity inwards toward the DAG root. - - Using the information conveyed in the metrics of its most preferred - DAG parent, its own metrics, and the conventions and functions - indicated by the OCP, a node is able to compute a rank value within - the DAG which it will use to coordinate its DAG maintenance. - - Once a preferred parent is selected, the node can compute its own - rank in the DAG and determine alternate parents. Any node inwards - from this node, that is with a lower rank than this node, can be used - as an alternate parent for forwarding. - - In addition to identifying DAG parents, a node also may hear the RA - messages of other neighboring nodes at the same rank within the DAG. - In this way a node can discover DAG siblings. As it selects its - initial position within a DAG, a node MAY increment its rank it order - to have at least one sibling but it SHOULD NOT increase it as to - obtain more parents. - - A node may order its set of DAG parents according to some - implementation specific preference, and it SHOULD install a DAG - parent as a default gateway. To this list the node may also append a - similarly ordered set of DAG siblings. By forwarding traffic - intended for the default destination towards the DAG parents, the - node is able to support the main Multipoint-to-point (MP2P) traffic - flows required by a typical LLN application. By using the ordered - set of DAG parents and DAG siblings the node is able to take - advantage of path diversity. For example, preferring to forward - traffic towards parents guarantees to get the traffic inwards, closer - to the DAG root, by definition, regardless of which parent is - selected. In this example, if forwarding towards parents is not - possible, perhaps due to a transient phenomena, then a node may then - choose to forward traffic towards siblings, moving across the DAG at - the same level (neither inwards or outwards). When receiving traffic - forwarded from a sibling, the traffic should not be forwarded back to - the same sibling in order to avoid a 2-node loop. - - By employing this procedure, the LLN is able to set up a path- - constrained DAG, rooted at designated nodes, with other nodes - organized along paths leading inward toward the DAG root. MP2P - traffic intended for the destinations available to or through the DAG - root, e.g. the default destination or other advertised prefixes, - flows inward along the DAG towards the root, and nodes forwarding - traffic are able to leverage the path diversity of the DAG as - necessary. - - Further mechanisms described below will populate the routing tables - along the DAG in support of P2MP and P2P traffic. - -3.2.1.2. Further Operation - - The sub-DAG of a node is the set of other nodes of greater rank in - the DAG that might use a path towards the DAG root that contains this - node. Rank in the DAG is defined such that nodes contained in the - sub-DAG of a specific node should have a greater rank than the node. - This is an important property that is leveraged for loop avoidance- - if a node has lesser rank then it is not in the sub-DAG. (An - arbitrary node with greater rank may or may not be contained in the - sub-DAG). Paths through siblings are not contained in this set. - - As a further illustration, consider the DAG examples in Appendix B. - Consider Node (24) in the DAG Example depicted in Figure 12. In this - example, the sub-DAG of Node (24) is comprised of Nodes (34), (44), - and (45). - - A DAG may also be floating. Floating DAGs may be encountered, for - example, during coordinated reconfigurations of the network topology - wherein a node and its sub-DAG breaks off the DAG, temporarily - becomes a floating DAG, and reattaches to a grounded DAG at a - different (more optimal) location. (Such coordination endeavors to - avoid the construction of transient loops in the LLN). A DAG, or a - sub-DAG, may also become floating because of a network element - failure. Note that in the case where a floating DAG exists as a - consequence of DAG repair, the floating DAG is also intended to be - transient and carries a marking to make it less attractive. Some - specific application scenarios may employ permanent floating DAGs, - e.g. DAGs without connectivity to an external routed infrastructure, - as a matter of normal operation. In such cases the floating DAG is - likely to have been provisioned by the application with an - administrative preference which will make it more attractive. - - A node will generally join at least one DAG, typically (but not - necessarily) to or through a grounded DAG rooted at an LBR. In some - cases, as suitable to the application scenario, a DAG may still - provision the DAG parents as default gateways and not be connected to - a non-LLN infrastructure such as the public Internet or a private IP - network. - - This specification does not preclude a node from joining multiple - DAGs. In one such case, a particular application may require the - node to maintain membership in multiple DAGs in order to satisfy - competing constraints, for example to support different types of - traffic, similar to the concept of MTR (Multi-topology routing) as - supported by other routing protocols such as IS-IS [RFC5120] or OSPF - [RFC4915], although the RPL mechanisms will significantly differ from - the ones specified for these protocols. (Note that not all - constrained traffic cases may require multiple DAGs). In support of - such cases the RPL implementation must independently maintain - requisite information and state for each DAG in parallel. In cases - where a competing constraints must be satisfied toward the same DAG - root, the OCP should differ by definition and may serve to coordinate - the maintenance of the multiple DAGs. Further, additional - recommendations for the operation of loop avoidance/loop detection - mechanisms in the presence of multiple DAGs are under investigation. - - An administrative preference, the DAG preference, shall be associated - with each DAG. In cases where a RPL node has a choice of joining - more than one DAG to satisfy a particular constraint, and all else - being equal, the node will seek to join the most preferred DAG as - indicated by the administrative preference. In practice this - mechanism may be assist in engineering the construction of a DAG as - appropriate to an application. For example, nodes that are to become - DAG roots in support of a particular application role, e.g. as a data - sink or a controller, may be provisioned such that they have are more - preferred. Nodes who are serving as the DAG root of a transient DAG, - e.g. for DAG repair, may take on a less desirable preference value. - Nodes will then be able to yield their transient DAGs to join the - DAGs that are more preferred. + The DAG construction algorithm is distributed; each node running RPL + invokes a set of DAG construction rules and objective functions when + considering its role with respect to neighboring nodes such that the + DAG structure emerges. -3.2.1.3. IP Router Advertisement - DAG Information Option (RA-DIO) +3.2.1.1. IP Router Advertisement - DAG Information Option (RA-DIO) The IPv6 Router Advertisement (RA) mechanism (as specified in [RFC4861]) is used by RPL in order to build and maintain a DAG. The IPv6 RA message is augmented with a DAG Information Option (DIO), - forming an RA-DIO message, in order to facilitate the formation and - maintenance of DAGs. The information conveyed in the RA-DIO message - includes the following: + forming an RA-DIO message, to convey information about the DAG + including: o A DAGID used to identify the DAG as sourced from the DAG root. - Typically the (potentially compressed) IPv6 address of the DAG - root. The DAGID must be unique to a single DAG in the scope of - the LLN. If the DAG root is rooting multiple DAGs, each DAG must - be provisioned with their own IPv6 address and thus derive unique - DAGIDs. + The DAGID must be unique to a single DAG in the scope of the LLN. o Objective Code Point (OCP) as described below. - o Rank information used by nodes to determine their relationships in - the DAG relative to each other, i.e. parents, siblings, or - children. This is not a metric, although its derivation is - typically closely related to one or more metrics as specified by - the OCP. The rank information is used to support loop avoidance - strategies and in support of ordering alternate successors when - engaged in path maintenance. + o Rank information used by nodes to determine their positions in the + DAG relative to each other. This is not a metric, although its + derivation is typically closely related to one or more metrics as + specified by the OCP. The rank information is used to support + loop avoidance strategies and in support of ordering alternate + successors when engaged in path maintenance. o Sequence number originated from the DAG root, used to aid in identification of dependent sub-DAGs and coordinate topology changes in a manner so as to avoid loops. - o Indications for the DAG, e.g. grounded or floating. - - o DAG configuration parameters. + o Indications and configuration for the DAG, e.g. grounded or + floating, administrative preference, ... - o A vector of path metrics. As discussed in - [I-D.ietf-roll-routing-metrics] such metrics may be cumulative, - may report a maximum, minimum, or average scalar value, or a link - property. + o A vector of path metrics, as further described in + [I-D.ietf-roll-routing-metrics]. - o List of additional destination prefixes reachable via the DAG - root. + o List of additional destination prefixes reachable inwards along + the DAG. The RA messages are issued whenever a change is detected to the DAG such that a node is able to determine that a region of the DAG has become inconsistent. As the DAG stabilizes the period at which RA messages occur is configured to taper off, reducing the steady-state overhead of DAG maintenance. The periodic issue of RA messages, along with the triggered RA messages in response to inconsistency, is one feature that enables RPL to operate in the presence of unreliable links. - The RA-DIO and related mechanisms are described in more detail in - Section 5. +3.2.1.2. DAG Identification -3.2.1.4. Objective Code Point (OCP) + Each DAG is identified by a particular identifier (DAGID) as well as + its supported optimization objectives and available destination + prefixes. The optimization objectives are conveyed as an Objective + Code Point (OCP) as described further below. Available destination + prefixes, which may include destinations available beyond the DAG + root, multicast destinations, or IPv6 node addresses, are advertised + outwards along the DAG and recipient nodes may then provision routing + tables with entries inwards towards the destinations. The RPL + implementation at each node will be provisioned by the application + with sufficient information to determine which objectives and + destinations are required, and thus the RPL implementation may + determine which DAG to join. - The OCP is seeded by the DAG root and serves to convey and control - the optimization functions used within the DAG. The OCP is further - specified in [I-D.ietf-roll-routing-metrics]. Each instance of an - allocated OCP indicates: + The decision for a node to join a DAG may be optimized according to + implementation specific policy functions on the node as indicated by + one or more specific OCP values. For example, a node may be + configured for one goal to optimize a bandwidth metric (OCP-1), and + with a parallel goal to optimize for a reliability metric (OCP-2). + Thus two DAGs, with two unique DAGIDs, may be constructed and + maintained in the LLN: DAG-1 would be optimized according to OCP-1, + whereas DAG-2 would be optimized according to OCP-2. A node may then + maintain independent sets of DAG parents and related data structures + for each DAG. Note that in such a case traffic may directed along + the appropriate constrained DAG based on traffic marking within the + IPv6 header. This specification will focus on the case where the + node only joins one DAG; further elaboration on the proper operation + of RPL in the presence of multiple DAGs, including traffic marking + and related rules, are to be specified further in future revisions of + this or companion specifications. + +3.2.1.3. Grounded and Floating DAGs + + Certain LLN nodes may offer connectivity to an external routed + infrastructure in support of an application scenario. These nodes + are designated `grounded', and may serve as the DAG roots of a + grounded DAG. DAGs that do not have a grounded DAG root are floating + DAGs. In either case routes may be provisioned toward the DAG root, + although in the floating case there is no expectation to reach an + external infrastructure. Some applications will include permanent + floating DAGs. + +3.2.1.4. Administrative Preference + + An administrative preference may be associated with each DAG root, + and thereby each DAG, in order that some DAGs in the LLN may be more + preferred over other DAGs. For example, a DAG root that is sinking + traffic in support of a data collection application may be configured + by the application to be very preferred. A transient DAG, e.g. a DAG + that is only existing in support of DAG repair until a permanent DAG + is found, may be configured to be less preferred. The administrative + preference offers a way to engineer the formation of the DAG in + support of the application. + +3.2.1.5. Objective Code Point (OCP) + + The OCP serves to convey and control the optimization objectives in + use within the DAG. The OCP is further specified in + [I-D.ietf-roll-routing-metrics]. Each instance of an allocated OCP + indicates: o The set of metrics used within the DAG - o The objective functions used to determine the least cost - constrained paths in order to optimize the DAG + + o The objective functions used for least cost path determination. o The function used to compute DAG Rank - o The functions used to construct derived metrics for propagation - within a RA-DIO message + o The functions used to accumulate metrics for propagation within a + RA-DIO message For example, an objective code point might indicate that the DAG is using the Expected Number of Transmissions (ETX) as a metric, that the optimization goal is to minimize ETX, that DAG Rank is equivalent to ETX, and that RA-DIO propagation entails adding the advertised ETX of the most preferred parent to the ETX of the link to the most preferred parent. By using defined OCPs that are understood by all nodes in a particular implementation, and by conveying them in the RA-DIO message, RPL nodes may work to build optimized LLN using a variety of application and implementation specific metrics and goals. A default OCP, OCP 0, is specified with a well-defined default behavior. OCP 0 is used to define RPL behaviors in the case where a node encounters a RA-DIO message containing a code point that it does not support. -3.2.1.5. Selection of Feasible DAG Parents - - The decision for a node to join a DAG may be optimized according to - implementation specific policy functions on the node as indicated by - one or more specific OCP values. For example, a node may be - configured for one goal to optimize a bandwidth metric (OCP-1), and - with a parallel goal to optimize for a reliability metric (OCP-2). - Thus two DAGs, with two unique DAGIDs, may be constructed and - maintained in the LLN: DAG-1 would be optimized according to OCP-1, - whereas DAG-2 would be optimized according to OCP-2. A node may then - maintain two parallel sets of DAG parents and related data - structures. Note that in such a case traffic may directed along the - appropriate constrained DAG based on traffic marking within the IPv6 - header. - - As a node hears RA messages from its neighbors it may process their - attached DIO messages. At this time the node may be able to take - into consideration, for example, the following: +3.2.1.6. Distributed Algorithm Operation - o Is the neighboring node heard reliably enough, and are the metrics - stable enough, that a local degree of confidence may be - established with respect to the neighboring node? Should the - neighboring node be considered in the set of candidate neighbors? + o Some nodes may be initially provisioned to act as DAG roots, + either permanent or transient, with associated preferences. - o In consultation with implementation specific policy (OCP goal), is - the neighboring node a feasible parent from a constrained-path - perspective? + o Nodes will maintain a data structure containing their candidate + (viable) neighbors, as based on guidelines in + [I-D.ietf-roll-routing-metrics] This data structure will also + track DAG information as learned from and associated with each + neighbor. - o According to the implementation specific policy (OCP), does the - neighboring node offer a better optimized position into the DAG? + o Nodes who are members of a DAG, including DAG roots, will + multicast RA-DIO messages as needed (when inconsistency is + detected), to their link-local neighbors. Nodes will also respond + to Router Solicitation (RS) messages. - o Does the neighboring node offer a DAG with a more desirable - administrative preference for an otherwise currently satisfied - optimization objective, all else being equal? + o Nodes who receive RA-DIO messages will take into consideration + several criteria when processing the extracted DAG information. + The node may discount the RA-DIO according to loop avoidance rules + based on rank as described further below. Nodes will consider the + information in the RA-DIO in order to determine whether or not + that candidate neighbor offers a better attachment point to a DAG + (which the node may or may not be a member of) according to the + implementation specific optimization goals, OCP, and current + metrics. - o Is the neighboring node a peer (sibling) within the DAG? + o Nodes may join a new DAG or move within the current DAG, in + response to the information contained in the RA-DIO message, and + in accordance with loop avoidance rules described further in this + specification. For the successors within the DAG, a node manages + a set of DAG Parents. Joining, moving within, and leaving the DAG + is accomplished through managing this set according to the rules + specified by RPL. - Based on such considerations, the node may incorporate the - neighboring node into the set of DAG parents. When the node inserts - the first DAG parent into the empty DAG parent set, it is able to - join the DAG. As the DAG parent set is updated, the node will - consult a rank computation function indicated by the OCP for the DAG - in order to determine its own rank value, which it will subsequently - advertise when it emits its own RA-DIO messages. + o As nodes join, move within, and leave DAGs they emit updated RA- + DIOs which are received and acted on by neighboring nodes. When + inconsistencies (such as caused by movement or link loss) are + detected within the DAG structure, RA-DIO messages are emitted + more frequently. When the DAG structure becomes consistent, RA- + DIO messages taper off. - Following is an overview of the rules used to select a parent (the - detailed mode of operation for the selection of the candidate DAG - parent(s) is described in Section 5.3. First, it is important to - note that the rank of the node is not directly used as a selection - criteria. The metric of choice as indicated by the OCP advertised by - the candidate parents is used to select the parent, although the use - of a cumulative metric to reflect the rank is not precluded. + o As less preferred DAGs encounter more preferred DAGs that offer + equivalent or better optimization objectives, the nodes in the + less preferred DAGs may leave to join the more preferred DAGs, + finally leaving only the more preferred DAGs. This is an + illustration of the mechanism by which an application may engineer + DAG construction. - Consider an example where a node N receives two RAs from node A and B - with (rank, metric) equal to (2,4) and (5,3) respectively. Node N - may chose B as its parent (higher rank but smaller metric). Once the - parent, B, is selected, the node computes its own rank according to - the OCP. + o As the DAG construction operation proceeds, nodes accumulate onto + the DAG in progressively outward tiers, centered around the DAG + root. - If the node receives other RA messages it cannot attach to other - parents if choosing that parent would cause the nodes own rank to - increase. Back to the previous example, suppose that a node C - appears with a (rank, metric) equal to (5,1). By selecting C as the - new parent, N would have a rank of 6 (making the assumption that the - rank is increased by a value of 1 according to the OCP). Although - the path metric would be lower, this may lead to a DAG Loop should C - belong to the sub-DAG of N as further discussed in Section 3.3.1. + o The nodes provision routing table entries for the destinations + specified by the RA-DIO towards their DAG Parents. Nodes may + provision a DAG Parent as a default gateway. - All reliable neighboring nodes of a lesser rank than the node may be - considered as potential DAG parents (Note that, as in the above - example, as a consequence of satisfying a particular OCP goal, the - most preferred parent may not necessarily be the potential parent of - least rank, for example a potential parent of lesser rank may also be - an energy constrained device that is to generally be avoided and thus - not the most preferred). No nodes of greater rank than self may be - in the DAG parent set; to allow such nodes will introduce a - possibility to create loops (by potentially allowing a packet to make - backwards progress as it is forwarded in the DAG). All neighboring - nodes of equal rank may be considered as siblings within the DAG - (even though they may not have parents in common, they may still - provide path diversity towards the DAG root). +3.2.1.7. DAG Rank - The computation of rank, and related properties, are further - described in Section 3.3.1. + When nodes select DAG parents, they will select the most preferred + parent according to their implementation specific objectives, using + the cost metrics conveyed in the RA-DIO messages along the DAG in + conjunction with the related objective functions as specified by the + OCP. -3.2.1.5.1. Example + Based on this selection, the metrics conveyed by the most preferred + DAG parent, the nodes own metrics and configuration, and a related + function defined by the OCP, a node will be able to compute a value + for its rank as a consequence of selecting a most preferred DAG + parent. - For example, suppose that a node (N) is not attached to any DAG, and - that it is in range of nodes (A), (B), (C), (D), and (E). Let all - nodes be configured to use an OCP which defines a policy such that - ETX is to be minimized and paths with the attribute `Blue' should be - avoided. Let the rank computation indicated by the OCP simply - reflect the ETX aggregated along the path. Let the links between - node (N) and its neighbors (A-E) all have an ETX of 1 (which is - learned by node (N) through some implementation specific method). - Let node (N) be configured to send IPv6 Router Solicitation (RS) - messages to probe for nearby DAGs. + The rank value feeds back into the DAG parent selection according to + a loop-avoidance strategy. Once a DAG parent has been added, and a + rank value for the node within the DAG has been computed, the nodes + further options with regard to DAG parent selection and movement + within the DAG are restricted in favor of loop avoidance. - o Node (N) transmits a Router Solicitation. + It is important to note that the DAG Rank is not itself a metric, + although its value is derived from and influenced by the use of + metrics to select DAG parents and take up a position in the DAG. In + other words, routing metrics and OCP (not rank directly) are used to + determine the DAG structure and consequently the path cost. The only + aim of the rank is to inform loop avoidance as explained hereafter. + The computation of the DAG Rank MUST be done in such a way so as to + maintain the following properties for any nodes M and N who are + neighbors in the LLN: - o Node (B) responds. Node (N) investigates the RA-DIO message, and - learns that Node (B) is a member of DAGID 1 at rank 4, and not - `Blue'. Node (N) takes note of this, but is not yet confident. + For a node N, and its most preferred parent M, DAGRank(N) > + DAGRank(M) must hold. Further, all parents in the DAG parent set + must be of a rank less than self's DAGRank(N). In other words, + the rank presented by a node N MUST be greater (deeper) than that + presented by any of its parents. - o Similarly, Node (N) hears from Node (A) at rank 9, Node (C) at - rank 5, and Node (E) at rank 4. + If DAGRank(M) < DAGRank(N), then M is probably located in a more + preferred position than N in the DAG with respect to the metrics + and optimizations defined by the objective code point. In any + fashion, Node M may safely be a DAG parent for Node N without risk + of creating a loop. - o Node (D) responds. Node (D) has a RA-DIO message that indicates - that it is a member of DAGID 1 at rank 2, but it carries the - attribute `Blue'. Node (N)'s policy function rejects Node (D), - and no further consideration is given. + For example, a Node M of rank 3 is likely located in a more + optimum position than a Node N of rank 5. A packet directed + inwards and forwarded from Node N to Node M will always make + forward progress with respect to the DAG organization on that + link; there is no risk of Node M at rank 3 forwarding the + packet back into Node N's sub-DAG at rank of 5 or greater + (which would be a sufficient condition for a loop to occur). - o This process continues until Node (N), based on implementation - specific policy, builds up enough confidence to trigger a decision - to join DAGID 1. Let Node (N) determine its most preferred parent - to be Node (E). + If DAGRank(M) == DAGRank(N), then M and N are located positions of + relatively the same optimality within the DAG. In some cases, + Node M may be used as a successor by Node N, but with related + chance of creating a loop that must be detected and broken by some + other means. - o Node (N) adds Node (E) (rank 4) to its set of DAG parents for - DAGID 1. Following the mechanisms specified by the OCP, and given - that the ETX is 1 for the link between (N) and (E), Node (N) is - now at rank 5 in DAGID 1. + If Node M is at rank 3 and node N is at rank 3, then they are + siblings; by definition Node M and N cannot be in each others + sub-DAG. They may then forward to each other failing + serviceable parents, making `sideways' progress (but not + reverse progress). If another sibling or more gets involved + there may then be some chance for 3 or more way loops, which is + the risk of sibling forwarding. - o Node (N) adds Node (B) (rank 4) to its set of DAG parents for - DAGID 1. + If DAGRank(M) > DAGRank(N), then node M is located in a less + preferred position than N in the DAG with respect to the metrics + and optimizations defined by the objective code point. Further, + Node (M) may in fact be in Node (N)'s sub-DAG. There is no + advantage to Node (N) selecting Node (M) as a DAG parent, and such + a selection may create a loop. - o Node (N) is a sibling of Node (C), both are at rank 5. + For example, if Node M is of rank 3 and Node N is of rank 5, + then by definition Node N is in a less optimum position than + Node N. Further, Node N at rank 5 may in fact be in Node M's + own sub-DAG, and forwarding a packet directed inwards towards + the DAG root from M to N will result in backwards progress and + possibly a loop. - o Node (N) may now forward traffic intended for the default - destination inward along DAGID 1 via nodes (B) and (E). In some - cases, e.g. if nodes (B) and (E) are tried and fail, node (N) may - also choose to forward traffic to its sibling node (C), without - making inward progress but with the intention that node (C) or a - following successor can make inward progress. Should Node (C) not - have a viable parent, it should never send the packet back to Node - (N) (to avoid a 2-node loop). + As an example, the DAG Rank could be computed in such a way so as to + closely track ETX when the objective function is to minimize ETX, or + latency when the objective function is to minimize latency, or in a + more complicated way as appropriate to the objective code point being + used within the DAG. -3.2.1.6. DAG Maintenance + The DAG rank is subsequently used to restrict the options a node has + for movement within the DAG and to coordinate movements in order to + avoid the creation of loops. - When a node moves within a DAG, the move is defined as updating the - set of DAG parents for a particular DAGID, i.e. adding or deleting - DAG parents. Not all moves entail changes in rank. +3.2.1.8. Sub-DAG - A jump from one DAG to another DAG is attaching to a new DAGID, in - such a way that an old DAGID is replaced by the new DAGID. In - particular, when an old DAGID is left, all associated parents are no - longer feasible, and a new DAGID is joined. + The sub-DAG of a node is the set of other nodes of greater rank in + the DAG, and thus might use a path towards the DAG root that contains + this node. This is an important property that is leveraged for loop + avoidance- if a node has lesser rank then it is not in the sub-DAG. + (An arbitrary node with greater rank may or may not be contained in + the sub-DAG). Paths through siblings are not contained in this set. - When a node in a DAG follows a DAG parent, it means that the DAG - parent has changed its DAGID (e.g. by joining a new DAG) and that the - node updates its own DAGID in order to keep the DAG parent. + As a further illustration, consider the DAG examples in Appendix B. + Consider Node (24) in the DAG Example depicted in Figure 9. In this + example, the sub-DAG of Node (24) is comprised of Nodes (34), (44), + and (45). A frozen sub-DAG is a subset of nodes in the sub-DAG of a node who have been informed of a change to the node, and choose to follow the node in a manner consistent with the change, for example in preparation for a coordinated move. Nodes in the sub-DAG who hear of a change and have other options than to follow the node do not have to become part of the frozen sub-DAG, for example such a node may be able to remain attached to the original DAG through a different DAG - parent. A further example may be found in Section 3.3.1.1. + parent. A further example may be found in Appendix B.8. - When the node encounters new candidate neighbors that offer higher - positions in the DAG, it may incorporate them directly into its set - of DAG parents. In this case the node may update its choice of most - preferred parent, possibly causing its own advertised rank to - decrease, and discarding any former parents now of a deeper rank. - This case is `moving inwards along the DAG' and does not require any - additional coordination for loop avoidance. +3.2.1.9. Moving up in a DAG - If the DAG parent set of the node becomes completely depleted, the - node will have detached from the DAG, and may, if so configured, - become the root of its own transient floating DAG with a less - desirable administrative preference (thus beginning the process of - establishing the frozen sub-DAG), and then may reattach to the - original DAG at a lower point if it is able (after hearing RA-DIO - messages from alternate attachment points). + A node may safely move `up' in the DAG, causing its DAG rank to + decrease and moving closer to the DAG root without risking the + formation of a loop. - When the node encounters candidate parents that are in a different - DAG, and decides to leave the current DAG in order to join the - different DAG (thus doing a jump), it may do so safely without regard - to loop avoidance. However, it may not return immediately to the - current DAG as such movement may result in the creation of a DAG - Loop, in particular if it reattaches back into its own former sub-DAG - in an uncoordinated manner. +3.2.1.10. Moving down in a DAG - When a node, and perhaps a related frozen sub-DAG, jumps to a - different DAG, the move is coordinated by a DAG Hop timer. The DAG - Hop timer allows the nodes who will attach closer to the sink of the - new DAG to `jump' first, and then drag dependent nodes behind them, - thus endeavoring to efficiently coordinate the attachment of the - frozen sub-DAG into the new DAG. A further illustration of this - mechanism may be found in Section 3.3.3. + A node may not consider to move `down' the DAG, causing its DAG rank + to increase and moving further from the DAG root. In the case where + a node looses connectivity to the DAG, it must first leave the DAG + before it may then rejoin at a deeper point. This allows for the + node to coordinate moving down, freezing its own sub-DAG and + poisoning stale routes to the DAG, and minimizing the chances of re- + attaching to its own sub-DAG thinking that it has found the original + DAG again. If a node where allowed to re-attach into its own sub-DAG + a loop would most certainly occur, and may not be broken until a + count-to-infinity process elapses. The procedure of detaching before + moving down eliminates the need to count-to-infinity. - Appendix B provides additional examples of DAG discovery and - maintenance. +3.2.1.11. DAG Jumps + + A jump from one DAG to another DAG is attaching to a new DAGID, in + such a way that an old DAGID is replaced by the new DAGID. In + particular, when an old DAGID is left, all associated parents are no + longer feasible, and a new DAGID is joined. + + When a node in a DAG follows a DAG parent, it means that the DAG + parent has changed its DAGID (e.g. by joining a new DAG) and that the + node updates its own DAGID in order to keep the DAG parent. + +3.2.1.12. Floating DAGs for DAG Repair + + A DAG may also be floating. Floating DAGs may be encountered, for + example, during coordinated reconfigurations of the network topology + wherein a node and its sub-DAG breaks off the DAG, temporarily + becomes a floating DAG, and reattaches to a grounded DAG. (Such + coordination endeavors to avoid the construction of transient loops + in the LLN). + + A DAG, or a sub-DAG temporarily promoted to a DAG, may also become + floating because of a network element failure. If the DAG parent set + of the node becomes completely depleted, the node will have detached + from the DAG, and may, if so configured, become the root of its own + transient floating DAG with a less desirable administrative + preference (thus beginning the process of establishing the frozen + sub-DAG), and then may reattach to the original DAG at a lower point + if it is able (after hearing RA-DIO messages from alternate + attachment points). 3.2.2. Destination Advertisement As RPL constructs DAGs, nodes may provision routes toward destinations advertised through RA-DIO messages through their selected parents, and are thus able to send traffic inward along the DAG by forwarding to their selected parents. However, this mechanism alone is not sufficient to support P2MP traffic flowing outward along the DAG from the DAG root toward nodes. A destination advertisement mechanism is employed by RPL to build up routing state in support of @@ -996,401 +914,136 @@ along the DAG, and as according to the available resources in the network. Further aggregations of NA-DAO messages prefix reachability information by destinations are possible in order to support additional scalability. A further example of the operation of the destination advertisement mechanism is available in Appendix B.6 -3.3. Other Considerations - -3.3.1. DAG Rank and Loop Avoidance - - When nodes select DAG parents, they should select the most preferred - parent according to their implementation specific objectives, using - the cost metrics conveyed in the RA-DIO messages along the DAG in - conjunction with the related objective functions as specified by the - OCP. - - Based on this selection, the metrics conveyed by the most preferred - DAG parent, the nodes own metrics and configuration, and a related - function defined by the objective code point, a node will be able to - compute a value for its rank as a consequence of selecting a most - preferred DAG parent. - - It is important to note that the DAG Rank is not itself a metric, - although its value is derived from and influenced by the use of - metrics to select DAG parents and take up a position in the DAG. In - other words, routing metrics and OCP (not rank directly) are used to - determine the DAG structure and consequently the path cost. The only - aim of the rank is to inform loop avoidance as explained hereafter. - The computation of the DAG Rank MUST be done in such a way so as to - maintain the following properties for any nodes M and N who are - neighbors in the LLN: - - For a node N, and its most preferred parent M, DAGRank(N) > - DAGRank(M) must hold. Further, all parents in the DAG parent set - must be of a rank less than self's DAGRank(N). In other words, - the rank presented by a node N MUST be greater (deeper) than that - presented by any of its parents. (This mechanism serves to avoid - loops in the case where an alternate parent is used- if no - alternate parent is deeper than the preferred parent then loops - are avoided. The risk of loops occurs if there is a chance for an - alternate parent to forward traffic to a deeper successor, which - may be in the sub-DAG, and traffic then makes backwards progress - and comes back to the node again). - - If DAGRank(M) < DAGRank(N), then M is probably located in a more - optimum position than N in the DAG with respect to the metrics and - optimizations defined by the objective code point. In any - fashion, Node M may safely be a DAG parent for Node N without risk - of creating a loop. For example, a Node M of rank 3 is located in - a more optimum position than a Node N of rank 5. A packet - directed inwards and forwarded from Node N to Node M will always - make forward progress with respect to the DAG organization on that - link; there is no risk of Node M at rank 3 forwarding the packet - back into Node N's sub-DAG at rank of 5 or greater (which would be - a sufficient condition for a loop to occur). - - If DAGRank(M) == DAGRank(N), then M and N are located positions of - relatively the same optimality within the DAG. In some cases, - Node M may be used as a successor by Node N, but with related - chance of creating a loop that must be detected and broken by some - other means. If Node M is at rank 3 and node N is at rank 3, then - they are siblings; by definition Node M and N cannot be in each - others sub-DAG. They may then forward to each other failing - serviceable parents, making `sideways' progress (but not reverse - progress). If another sibling or more gets involved there may - then be some chance for 3 or more way loops, which is the risk of - sibling forwarding. - - If DAGRank(M) > DAGRank(N), then node M is located in a less - optimum position than N in the DAG with respect to the metrics and - optimizations defined by the objective code point. Further, Node - (M) may in fact be in Node (N)'s sub-DAG. There is no advantage - to Node (N) selecting Node (M) as a DAG parent, and such a - selection may create a loop. For example, if Node M is of rank 3 - and Node N is of rank 5, then by definition Node N is in a less - optimum position than Node N. Further, Node N at rank 5 may in - fact be in Node M's own sub-DAG, and forwarding a packet directed - inwards towards the DAG root from M to N will result in backwards - progress and possibly a loop. - - For example, the DAG Rank could be computed in such a way so as to - closely track ETX when the objective function is to minimize ETX, or - latency when the objective function is to minimize latency, or in a - more complicated way as appropriate to the objective code point being - used within the DAG. - - The DAG rank is subsequently used to restrict the options a node has - for movement within the DAG and to coordinate movements in order to - avoid the creation of loops. - - A node may safely move `up' in the DAG, causing its DAG rank to - decrease and moving closer to the DAG root without risking the - formation of a loop. - - A node may not consider to move `down' the DAG, causing its DAG rank - to increase and moving further from the DAG root. Such a move will - entail moving to a less optimum position in the DAG in all cases, as - defined by the objective code point. In the case where a node looses - connectivity to the DAG, it must first leave the DAG before it may - then rejoin at a deeper point. This allows for the node to - coordinate moving down, freezing its own sub-DAG and poisoning stale - routes to the DAG, and minimizing the chances of re-attaching to its - own sub-DAG thinking that it has found the original DAG again. If a - node where allowed to re-attach into its own sub-DAG a loop would - most certainly occur, and may not be broken until a count-to-infinity - process elapses. The procedure of detaching before moving down - eliminates the need to count-to-infinity. - - Any neighboring nodes of lesser rank than self are eligible to be - considered as alternate DAG parents for forwarding. But this node - may only adopt such a parent as new preferred parent if that does not - cause the resulting rank for this node to increase. +3.3. Loop Avoidance and Stability The goal of a guaranteed consistent and loop free global routing solution for an LLN may not be practically achieved given the real behavior and volatility of the underlying metrics. The trade offs to achieve a stable approximation of global convergence may be too restrictive with respect to the need of the LLN to react quickly in response to the lossy environment. Globally the LLN may be able to achieve a weak convergence, in particular as link changes are able to be handled locally and result in minimal changes to global topology. RPL does not aim to guarantee loop free path selection, or strong global convergence. In order to reduce control overhead, in particular the expense of mechanisms such as count-to-infinity, RPL does try to avoid the creation of loops when undergoing topology changes. Further mechanisms to mitigate the impact of loops, such as loop detection when forwarding, are under investigation. -3.3.1.1. Example - - : : : - : : : - (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 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 - -3.3.2. DAG Parent Selection, Stability, and Greediness +3.3.1. Greediness and Rank-based Instabilities If a node is greedy and attempts to move deeper in the DAG, beyond its most preferred parent, in order to increase the size of the DAG parent set, then an instability can result. This is illustrated in - Figure 2. + Figure 11. Suppose a node is willing to receive and process a RA-DIO messages from a node in its own sub-DAG, and in general a node deeper than it. In such cases a chance exists to create a feedback loop, wherein two or more nodes continue to try and move in the DAG in order to optimize against each other. In some cases this will result in an instability. It is for this reason that RPL mandates that a node never receive and process RA-DIO messages from deeper nodes. This rule creates an `event horizon', whereby a node cannot be influenced into an instability by the action of nodes that may be in its own sub-DAG. -3.3.2.1. Example - - (A) (A) (A) - |\ |\ |\ - | `-----. | `-----. | `-----. - | \ | \ | \ - (B) (C) (B) \ | (C) - \ | | / - `-----. | | .-----` - \| |/ - (C) (B) - - -1- -2- -3- - - Figure 2: Greedy DAG Parent Selection - - Consider the example depicted in Figure 2. A DAG is depicted in 3 - different configurations. A usable link between (B) and (C) exists - in all 3 configurations. In Figure 2-1, Node (A) is a DAG parent for - Nodes (B) and (C), and (B)--(C) is a sibling link. In Figure 2-2, - Node (A) is a DAG parent for Nodes (B) and (C), and Node (B) is also - a DAG parent for Node (C). In Figure 2-3, Node (A) is a DAG parent - for Nodes (B) and (C), and Node (C) is also a DAG parent for Node - (B). - - If a RPL node is too greedy, in that it attempts to optimize for an - additional number of parents beyond its preferred parent, then an - instability can result. Consider the DAG illustrated in Figure 2-1. - In this example, Nodes (B) and (C) may most prefer Node (A) as a DAG - parent, but are operating under the greedy condition that will try to - optimize for 2 parents. - - When the preferred parent selection causes a node to have only one - parent and no siblings, the node may decide to insert itself at a - slightly higher rank in order to have at least one sibling and thus - an alternate forwarding solution. This does not deprive other nodes - of a forwarding solution and this is considered acceptable - greediness. - - o Let Figure 2-1 be the initial condition. - - o Suppose Node (C) first is able to leave the DAG and rejoin at a - lower rank, taking both Nodes (A) and (B) as DAG parents as - depicted in Figure 2-2. Now Node (C) is deeper than both Nodes - (A) and (B), and Node (C) is satisfied to have 2 DAG parents. - - o Suppose Node (B), in its greediness, is willing to receive and - process a RA-DIO message from Node (C) (against the rules of RPL), - and then Node (B) leaves the DAG and rejoins at a lower rank, - taking both Nodes (A) and (C) as DAG parents. Now Node (B) is - deeper than both Nodes (A) and (C) and is satisfied with 2 DAG - parents. - - o Then Node (C), because it is also greedy, will leave and rejoin - deeper, to again get 2 parents and have a lower rank then both of - them. - - o Next Node (B) will again leave and rejoin deeper, to again get 2 - parents - - o And again Node (C) leaves and rejoins deeper... - - o The process will repeat, and the DAG will oscillate between - Figure 2-2 and Figure 2-3 until the nodes count to infinity and - restart the cycle again. - - o This cycle can be averted through mechanisms in RPL: - - * Nodes (B) and (C) stay at a rank sufficient to attach to their - most preferred parent (A) and don't go for any deeper (worse) - alternate parents (Nodes are not greedy) - - * Nodes (B) and (C) do not process RA-DIO messages from nodes - deeper than themselves (because such nodes are possibly in - their own sub-DAGs) + A further example of the consequences of greedy operation, and + instability related to processing RA-DIO messages from nodes of + greater rank, may be found in Appendix B.9 -3.3.3. Merging DAGs +3.3.2. Merging DAGs The merging of DAGs is coordinated in a way such as to try and merge two DAGs cleanly, preserving as much DAG structure as possible, and in the process effecting a clean merge with minimal likelihood of forming transient DAG loops. The coordinated merge is also intended to minimize the related control cost. -3.3.3.1. Example - - : - : - (A) (D) - | | - | | - | | - (B) (E) - | | - | | - | | - (C) (F) - - Figure 3: Merging DAGs - - Consider the example depicted in Figure 3. Nodes (A), (B), and (C) - are part of some larger grounded DAG, where Node (A) is at a rank of - d, Node (B) at d+1, and Node (C) at d+2. The DAG comprised of Nodes - (D), (E), and (F) is a floating, less preferred, DAG, with Node (D) - as the DAG root. This floating DAG may have been formed, for - example, in the absence of a grounded DAG or when Node (D) had to - detach from a grounded DAG and (E) and (F) followed. All nodes are - using compatible objective code points. + When a node, and perhaps a related frozen sub-DAG, jumps to a + different DAG, the move is coordinated by a set of timers (DAG Hop + timers). The DAG Hop timers allow the nodes who will attach closer + to the sink of the new DAG to `jump' first, and then drag dependent + nodes behind them, thus endeavoring to efficiently coordinate the + attachment of the frozen sub-DAG into the new DAG. - Nodes (D), (E), and (F) would rather join the more preferred grounded - DAG if they are able than to remain in the less preferred floating - DAG. + A further example of a DAG Merge operation may be found in + Appendix B.10 - Next, let links (C)--(D) and (A)--(E) become viable. The following - sequence of events may then occur in a typical case: +3.3.3. DAG Loops - o Node (D) will receive and process a RA-DIO message from Node (C) - on link (C)--(D). Node (D) will consider Node (C) a candidate - neighbor and process the RA-DIO message since Node (C) belongs to - a different DAG (different DAGID) than Node (D). Node (D) will - note that Node (C) is in a grounded DAG at rank d+2, and will - begin the process to join the grounded DAG at rank d+3. Node (D) - will start a DAG Hop timer, logically associated with the grounded - DAG at Node (C), to coordinate the jump. The DAG Hop timer will - have a duration proportional to d+2. + A DAG loop may occur when a node detaches from the DAG and reattaches + to a device in its prior sub-DAG that has missed the whole detachment + sequence and kept advertising the original DAG. This may happen in + particular when RA-DIO messages are missed. Use of the DAG sequence + number can eliminate this type of loop. If the DAG sequence number + is not in use, the protection is limited (it depends on propagation + of RA-DIO messages during DAG hop timer), and temporary loops might + occur. RPL will move to eliminate such a loop as soon as a RA-DIO + message is received from a parent that appears to be going down, as + the child has to detach from it immediately. (The alternate choice + of staying attached and following the parent in its fall would have + counted to infinity and led to detach as well). - o Similarly, Node (E) will receive and process a RA-DIO message from - Node (A) on link (A)--(E). Node (E) will consider Node (A) a - candidate neighbor, will note that Node (A) is in a grounded DAG - at rank d, and will begin the process to join the grounded DAG at - rank d+1. Node (E) will start a DAG Hop timer, logically - associated with the grounded DAG at Node (A), to coordinate the - jump. The DAG Hop timer will have a duration proportional to d. + Consider node (24) in the DAG Example depicted in Figure 9, and its + sub-DAG nodes (34), (44), and (45). An example of a DAG loop would + be if node (24) were to detach from the DAG rooted at (LBR), and + nodes (34) and (45) were to miss the detachment sequence. + Subsequently, if the link (24)--(45) were to become viable and node + (24) heard node (45) advertising the DAG rooted at (LBR), a DAG loop + (45->34->24->45) may form if node (24) attaches to node (45). - o Node (F) takes no action, for Node (F) has observed nothing new to - act on. +3.3.4. DAO Loops - o Node (E)'s DAG Hop timer for the grounded DAG at Node (A) expires - first. Node (E), upon the DAG Hop timer expiry, removes Node (D) - as its parent, thus emptying the DAG parent set for the floating - DAG, and leaving the floating DAG. Node (E) then jumps to the - grounded DAG by entering Node (A) into the set of DAG parents for - the grounded DAG. Node (E) is now in the grounded DAG at rank - d+1. Node (E), by jumping into the grounded DAG, has created an - inconsistency by changing its DAGID, and will begin to emit RA-DIO - messages more frequently. + A DAO loop may occur when the parent has a route installed upon + receiving and processing a NA-DAO message from a child, but the child + has subsequently cleaned up the state. This loop happens when a no- + DAO was missed till a heartbeat cleans up all states. The DAO loop + is not explicitly handled by the current specification. Split + horizon, not forwarding a packet back to the node it came from, may + mitigate the DAO loop in some cases, but does not eliminate it. - o Node (F) will receive and process a RA-DIO message from Node (E). - Node (F) will observe that Node (E) has changed its DAGID and will - directly follow Node (E) into the grounded DAG. Node (F) is now a - member of the grounded DAG at rank d+2. Note that any additional - sub-DAG of Node (E) would continue to join into the grounded DAG - in this coordinated manner. + Consider node (24) in the DAG Example depicted in Figure 9. Suppose + node (24) has received a DA from node (34) advertising a destination + at node (45). Subsequently, if node (34) tears down the routing + state for the destination and node (24) did not hear a no-DAO message + to clean up the routing state, a DAO loop may exist. node (24) will + forward traffic destined for node (45) to node (34), who may then + naively return it into a loop (if split horizon is not in place). A + more complicated DAO loop may result if node (34) instead passes the + traffic to it's sibling, node (33), potentially resulting in a + (24->34->33->23->13->24) loop. - o Node (D) will receive a RA-DIO message from Node (E). Since Node - (E) is now in a different DAG, Node (D) may process the RA-DIO - message from Node (E). Node (D) will observe that, via node (E), - it could attach to the grounded DAG at rank d+2. Node (D) will - start another DAG Hop timer, logically associated with the - grounded DAG at Node (E), with a duration proportional to d+1. - Node (D) now is running two DAG hop timers, one which was started - with duration proportional to d+1 and one proportional to d+2. +3.3.5. Sibling Loops - o Generally, Node (D) will expire the timer associated with the jump - to the grounded DAG at node (E) first. Node (D) may then jump to - the grounded DAG by entering Node (E) into its DAG parent set for - the grounded DAG. Node (D) is now in the grounded DAG at rank - d+2. + Sibling loops occur when a group of siblings keep choosing amongst + themselves as successors such that a packet does not make forward + progress. The current draft limits those loops to some degree by + split horizon (do not send back to the same sibling) and parent + preference (always prefer parents vs. siblings). - o In this way RPL has coordinated a merge between the more preferred - grounded DAG and the less preferred floating DAG, such that the - nodes within the two DAGs come together in a generally ordered - manner, avoiding the formation of loops in the process. + Consider the DAG Example depicted in Figure 9. Suppose that Node + (32) and (34) are reliable neighbors, and thus are siblings. Then, + in the case where Nodes (22), (23), and (24) are transiently + unavailable, and with no other guiding strategy, a sibling loop may + exist, e.g. (33->34->32->33) as the siblings keep choosing amongst + each other in an uncoordinated manner. 3.4. Local and Temporary Routing Decision Although implementation specific, it is worth noting that a node may decide to implement some local routing decision based on some metrics, as observed locally or reported in the RA-DIO message. For example, the routing may reflect a set of successors (next-hop), along with various aggregated metrics used to load balance the traffic according to some local policy. Such decisions are local and implementation specific. @@ -1571,21 +1224,21 @@ + + | DAGID | + + | | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | sub-option(s)... +-+-+-+-+-+-+-+-+-+-+-+-+-+ - Figure 4: DIO Base Option + Figure 1: DIO Base Option Type: 8-bit unsigned identifying the DIO base option. The suggested value is 140 to be confirmed by the IANA. Length: 8-bit unsigned integer set to 4 when there is no suboption. The length of the option (including the type and length fields and the suboptions) in units of 8 octets. Flag Field: Three flags are currently defined: @@ -1694,21 +1347,21 @@ In addition to the minimum options presented in the base option, several suboptions are defined for the RA-DIO message: 5.1.1.1.1. Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Subopt. Type | Subopt Length | Suboption Data... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - Figure 5: DIO Suboption Generic Format + Figure 2: DIO Suboption Generic Format Suboption Type: 8-bit identifier of the type of suboption. When processing a RA-DIO message containing a suboption for which the Suboption Type value is not recognized by the receiver, the receiver MUST silently ignore the unrecognized option, continue to process the following suboption, correctly handling any remaining options in the message. Suboption Length: 8-bit unsigned integer, representing the length in octets of the suboption, not including the suboption Type and @@ -1734,61 +1387,61 @@ The Pad1 suboption does not have any alignment requirements. Its format is as follows: 0 0 1 2 3 4 5 6 7 +-+-+-+-+-+-+-+-+ | Type = 0 | +-+-+-+-+-+-+-+-+ - Figure 6: Pad 1 + Figure 3: Pad 1 NOTE! the format of the Pad1 option is a special case - it has neither Option Length nor Option Data fields. The Pad1 option is used to insert one octet of padding in the RA-DIO message to enable suboptions alignment. If more than one octet of padding is required, the PadN option, described next, should be used rather than multiple Pad1 options. 5.1.1.1.3. PadN The PadN option does not have any alignment requirements. Its format is as follows: 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - | Type = 1 | Subopt Length | Subopt Data +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - Figure 7: Pad N + Figure 4: Pad N The PadN option is used to insert two or more octets of padding in the RA-DIO message to enable suboptions alignment. For N (N > 1) octets of padding, the Option Length field contains the value N-2, and the Option Data consists of N-2 zero-valued octets. PadN Option data MUST be ignored by the receiver. 5.1.1.1.4. DAG Metric Container The DAG Metric Container suboption may be aligned as necessary to support its contents. Its format is as follows: 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - | Type = 2 | Container Len | DAG Metric Data +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - - Figure 8: DAG Metric Container + Figure 5: DAG Metric Container The DAG Metric Container is used to report aggregated path metrics along the DAG. The DAG Metric Container may contain a number of discrete node, link, and aggregate path metrics as chosen by the implementer. The Container Length field contains the length in octets of the DAG Metric Data. The order, content, and coding of the DAG Metric Container data is as specified in [I-D.ietf-roll-routing-metrics]. @@ -1805,21 +1458,21 @@ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type = 3 | Length | Prefix Length |Resvd|Prf|Resvd| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Prefix Lifetime | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Prefix (Variable Length) | . . . . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - Figure 9: DAG Destination Prefix + Figure 6: DAG Destination Prefix The Destination Prefix suboption is used when the DAG root, or another node located inwards along the DAG on the path to the DAG root, needs to indicate that it offers connectivity to destination prefixes other than the default. This may be useful in cases where more than one LBR is operating within the LLN and offering connectivity to different administrative domains, e.g. a home network and a utility network. In such cases, upon observing the Destination Prefixes offered by a particular DAG, a node MAY decide to join multiple DAGs in support of a particular application. @@ -1970,21 +1623,21 @@ their DAG parents in the DAG by using implementation specific policy functions. DAG discovery specifies a set of rules to be followed by all implementations in order to ensure interoperation. DAG discovery also standardizes the format that is used to advertise the most common information that is used in order to select DAG parents. One of these information, the DAG rank, is used by DAG discovery to provide loop avoidance even if nodes implement different policies. The DAG Rank is computed as specified by the Objective Code Point in use by the DAG, demonstrating the properties described in - Section 3.3.1. The rank should be computed in such a way so as to + Section 3.2.1.7. The rank should be computed in such a way so as to provide a comparable basis with other nodes which may not use the same metric at all. The DAG discovery procedures take into account a number of factors, including: o RPL rules for loop avoidance based on rank o The OCP function @@ -2278,24 +1931,24 @@ DIO message. 2. Setting C to zero. 3. Setting I to I_min. 4. Setting T to a random value as described above. 5. Restarting the trickle timer to expire after a duration T - When an LLN learns about a DAG through a RA-DIO message and makes the + When node learns about a DAG through a RA-DIO message and makes the decision to join it, it initializes the state of the trickle timer by resetting the trickle timer and listening. Each time it hears a - consistent RA for this DAG from a DAG parent, it increments C. + consistent RA for this DAG from a DAG parent, it MAY increment C. When the timer fires at time T, the node compares C to the redundancy constant, DEFAULT_DIO_REDUNDANCY_CONSTANT. If C is less than that value, the node generates a new RA and broadcasts it. When the communication interval I expires, the node doubles the interval I so long as it has previously doubled it fewer than I_doubling times, resets C, and chooses a new T value. 5.3.4.2. Determination of Inconsistency @@ -2796,21 +2449,21 @@ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Prefix (Variable Length) | . . . . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reverse Route Stack (Variable Length) | . . . . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - Figure 10: The Destination Advertisement Option (DAO) + Figure 7: The Destination Advertisement Option (DAO) Type: 8-bit unsigned identifying the Destination Advertisement option. IANA had defined the IPv6 Neighbor Discovery Option Formats registry. The suggested type value for the Destination Advertisement Option carried within a NA message is 141, to be confirmed by IANA. Length: 8-bit unsigned integer. The length of the option (including the Type and Length fields) in units of 8 octets. @@ -3305,85 +2958,20 @@ forwarded via a sibling, then the TTL MAY be decremented more aggressively (by more than one) to limit the impact of possible loops. Note that the chosen successor MUST NOT be the neighbor who was the predecessor of the packet (split horizon), except in the case where it is intended for the packet to change from an inward to an outward flow, such as switching from DIO routes to DAO routes as the destination is neared. -5.12.1. Loop Taxonomy - - The following is a summary of the sort of loops that may occur within - RPL. This is provided in part as a basis for discussion of loop - detection at forwarding. - -5.12.1.1. DAG Loops - - A DAG loop may occur when a node detaches from the DAG and reattaches - to a device in its prior sub-DAG that has missed the whole detachment - sequence and kept advertising the original DAG. This may happen in - particular when RA-DIO messages are missed. Use of the DAG sequence - number can eliminate this type of loop. If the DAG sequence number - is not in use, the protection is limited (it depends on propagation - of RA-DIO messages during DAG hop timer), and temporary loops might - occur. RPL will move to eliminate such a loop as soon as a RA-DIO - message is received from a parent that appears to be going down, as - the child has to detach from it immediately. (The alternate choice - of staying attached and following the parent in its fall would have - counted to infinity and led to detach as well). - - Consider node (24) in the DAG Example depicted in Figure 12, and its - sub-DAG nodes (34), (44), and (45). An example of a DAG loop would - be if node (24) were to detach from the DAG rooted at (LBR), and - nodes (34) and (45) were to miss the detachment sequence. - Subsequently, if the link (24)--(45) were to become viable and node - (24) heard node (45) advertising the DAG rooted at (LBR), a DAG loop - (45->34->24->45) may form if node (24) attaches to node (45). - -5.12.1.2. DAO Loops - - A DAO loop may occur when the parent has a route installed upon - receiving and processing a NA-DAO message from a child, but the child - has subsequently cleaned up the state. This loop happens when a no- - DAO was missed till a heartbeat cleans up all states. The DAO loop - is not explicitly handled by the current specification. Split - horizon, not forwarding a packet back to the node it came from, may - mitigate the DAO loop in some cases, but does not eliminate it. - - Consider node (24) in the DAG Example depicted in Figure 12. Suppose - node (24) has received a DA from node (34) advertising a destination - at node (45). Subsequently, if node (34) tears down the routing - state for the destination and node (24) did not hear a no-DAO message - to clean up the routing state, a DAO loop may exist. node (24) will - forward traffic destined for node (45) to node (34), who may then - naively return it into a loop (if split horizon is not in place). A - more complicated DAO loop may result if node (34) instead passes the - traffic to it's sibling, node (33), potentially resulting in a - (24->34->33->23->13->24) loop. - -5.12.1.3. Sibling Loops - - Sibling loops occur when a group of siblings keep choosing amongst - themselves as successors such that a packet does not make forward - progress. The current draft limits those loops to some degree by - split horizon (do not send back to the same sibling) and parent - preference (always prefer parents vs. siblings). - - Consider the DAG Example depicted in Figure 12. Suppose that Node - (32) and (34) are reliable neighbors, and thus are siblings. Then, - in the case where Nodes (22), (23), and (24) are transiently - unavailable, and with no other guiding strategy, a sibling loop may - exist, e.g. (33->34->32->33) as the siblings keep choosing amongst - each other in an uncoordinated manner. - 6. RPL Variables DIO Timer One instance per DAG that a node is a member of. Expiry triggers RA-DIO message transmission. Trickle timer with variable interval in [0, DIOIntervalMin..2^DIOIntervalDoublings]. See Section 5.3.4 DAG Hop Timer Up to one instance per candidate DAG parent in the `Held-Up' state per DAG that a node is going to jump to. Expiry triggers candidate DAG parent to become a DAG parent in @@ -3448,57 +3036,39 @@ Furthermore, the implementation SHOULD to allow configuring whether or not the node should start sending an RS message as an initial probe for nearby DAGs, or should simply wait until it received RA messages from other nodes that are part of existing DAGs. 7.1.2. DIO Base option RPL specifies a number of protocol parameters. A RPL implementation SHOULD allow configuring the following routing - protocol parameters: + protocol parameters, which are further described in Section 5.1.1: - DAGPreference: 8-bit unsigned integer set by the DAG root to its - preference and unchanged at propagation. + DAGPreference - NodePreference: The administrative preference of that LLN Node. + NodePreference - DAGDelay: 16-bit unsigned integer set by the DAG root indicating the - delay before changing the DAG configuration, + DAGDelay - DIOIntervalDoublings: 8-bit unsigned integer. Configured on the DAG - root and used to configure the trickle timer governing when RA- - DIO messages should be sent within the DAG. + DIOIntervalDoublings - DIOIntervalMin: 8-bit unsigned integer. Configured on the DAG root - and used to configure the trickle timer governing when RA-DIO - messages should be sent within the DAG. The minimum configured - interval for the RA-DIO trickle timer in units of ms is - 2^DIOIntervalMin (e.g. a DIOIntervalMin value of 16ms is - expressed as 4). + DIOIntervalMin: - DAGObjectiveCodePoint The DAG Objective Code Point is used to - indicate the cost metrics, objective functions, and methods of - computation and comparison for DAGRank in use in the DAG. The - DAG OCP is set by the DAG root. + DAGObjectiveCodePoint - PathDigest: 32-bit unsigned integer CRC, updated by each LLN Node. - This is the result of a CRC-32c computation on a bit string - obtained by appending the received value and the ordered set of - DAG parents at the LLN Node. DAG roots use a 'previous value' - of zeroes to initially set the PathDigest. + PathDigest - DAGID: 128-bit unsigned integer which uniquely identify a DAG. This - value is set by the DAG root. The global IPv6 address of the - DAG root can be used. + DAGID - Destination Prefixes List of advertised destinations + Destination Prefixes DAG Root behavior: In some cases, a node may not want to permanently act as a DAG root if it cannot join a grounded DAG. For example a battery-operated node may not want to act as a DAG root for a long period of time. Thus a RPL implementation MAY support the ability to configure whether or not a node could act as a DAG root for a configured period of time. DAG Hop Timer: A RPL implementation MUST provide the ability to configure the value of the DAG Hop Timer, expressed in ms. @@ -3509,39 +3079,31 @@ suppressed, to be invoked if the DAG parent set becomes empty. 7.1.3. Trickle Timers A RPL implementation makes use of trickle timer to govern the sending of RA-DIO message. Such an algorithm is determined a by a set of configurable parameters that are then advertised by the DAG root along the DAG in RA-DIO messages. For each DAG, a RPL implementation MUST allow for the monitoring of - the following parameters: + the following parameters, further described in Section 5.3.4: - I: The current length of the communication interval + I - T: A timer with a duration set to a random value in the range - [I/2, I] + T - C: Redundancy Counter + C - I_min: The smallest communication interval in milliseconds. This - value is learned from the RA-DIO message as - (2^DIOIntervalMin)ms. The default value is - DEFAULT_DIO_INTERVAL_MIN. + I_min - I_doublings: The number of times I_min should be doubled before - maintaining a constant rate, i.e. I_max = I_min * - 2^I_doublings. This value is learned from the RA-DIO message - as DIOIntervalDoublings. The default value is - DEFAULT_DIO_INTERVAL_DOUBLINGS. + I_doublings: A RPL implementation SHOULD provide a command (for example via API, CLI, or SNMP MIB) whereby any procedure that detects an inconsistency may cause the trickle timer to reset. 7.1.4. DAG Heartbeat A RPL implementation may allow by configuration at the DAG root to refresh the DAG states by updating the DAGSequenceNumber. A RPL implementation SHOULD allow configuring whether or not periodic or @@ -3954,33 +3513,33 @@ Networks", RFC 5548, May 2009. Appendix A. Deferred Requirements NOTE: RPL is still a work in progress. At this time there remain several unsatisfied application requirements, but these are to be addressed as RPL is further specified. Appendix B. Examples - Consider the example LLN physical topology in Figure 11. In this + Consider the example LLN physical topology in Figure 8. In this example the links depicted are all usable L2 links. Suppose that all links are equally usable, and that the implementation specific policy function is simply to minimize hops. This LLN physical topology then - yields the DAG depicted in Figure 12, where the links depicted are - the edges toward DAG parents. This topology includes one DAG, rooted - by an LBR node (LBR) at rank 1. The LBR node will issue RAs - containing DIO, as governed by a trickle timer. Nodes (11), (12), - (13), have selected (LBR) as their only parent, attached to the DAG - at rank 2, and periodically advertise RA-DIO multicasts. Node (22) - has selected (11) and (12) in its DAG parent set, and advertises - itself at rank 3. Node (22) thus has a set of DAG parents {(11), - (12)} and siblings {((21), (23)}. + yields the DAG depicted in Figure 9, where the links depicted are the + edges toward DAG parents. This topology includes one DAG, rooted by + an LBR node (LBR) at rank 1. The LBR node will issue RAs containing + DIO, as governed by a trickle timer. Nodes (11), (12), (13), have + selected (LBR) as their only parent, attached to the DAG at rank 2, + and periodically advertise RA-DIO multicasts. Node (22) has selected + (11) and (12) in its DAG parent set, and advertises itself at rank 3. + Node (22) thus has a set of DAG parents {(11), (12)} and siblings + {((21), (23)}. (LBR) / | \ .---` | `----. / | \ (11)------(12)------(13) | \ | \ | \ | `----. | `----. | `----. | \| \| \ (21)------(22)------(23) (24) @@ -3997,21 +3556,21 @@ / / / | \| \ (51)------(52)------(53)------(54)------(55)------(56) Note that the links depicted represent the usable L2 connectivity available in the LLN. For example, Node (31) can communicate directly with its neighbors, Nodes (21), (22), (32), and (41). Node (31) cannot communicate directly with any other nodes, e.g. (33), (23), (42). In this example these links offer bidirectional communication, and `bad' links are not depicted. - Figure 11: Example LLN Topology + Figure 8: Example LLN Topology (LBR) / | \ .---` | `----. / | \ (11) (12) (13) | \ | \ | \ | `----. | `----. | `----. | \| \| \ (21) (22) (23) (24) | /| /| | @@ -4021,52 +3580,52 @@ | /| \ | \ | \ | .----` | `----. | `----. | `----. | / | \| \| \ .--------(41) (42) (43) (44) (45) / / /| \ | \ .----` .----` .----` | `----. | `----. / / / | \| \ (51) (52) (53) (54) (55) (56) Note that the links depicted represent directed links in the DAG - overlaid on top of the physical topology depicted in Figure 11. As + overlaid on top of the physical topology depicted in Figure 8. As such, the depicted edges represent the relationship between nodes and their DAG parents, wherein all depicted edges are directed and oriented `up' on the page toward the DAG root (LBR). The DAG may provide default routes within the LLN, and serves as the foundation on which RPL builds further routing structure, e.g. through the destination advertisement mechanism. - Figure 12: Example DAG + Figure 9: Example DAG B.1. Moving Down a DAG - Consider node (56) in the example of Figure 11. In the unmodified + Consider node (56) in the example of Figure 8. In the unmodified example, node (56) is at rank 6 with one DAG parent, {(43)}, and one sibling (55). Suppose, for example, that node (56) wished to expand its DAG parent set to contain node (55), as {(43), (55)}. Such a change would require node (56) to detach from the DAG, to defer reattachment until a loop avoidance algorithm has completed, and to then reattach to the DAG with {(43), (55)} as it's DAG parents. When node (56) detaches from the DAG, it is able to act as the root of its own floating DAG and establish its frozen sub-DAG (which is empty). Node (56) can then observe that Node (55) is still attached to the original DAG, that its sequence number is able to increment, and deduce that Node (55) is safely not behind Node (56). There is then little change for a loop, and Node (56) may safely reattach to the DAG, with parents {(43), (55)}. At reattachment time, node (56) would present itself with a rank deeper than that of its deepest DAG parent (node (55) at rank 6), rank 7. B.2. Link Removed - Consider the example of Figure 11 when link (13)-(24) goes down. + Consider the example of Figure 8 when link (13)-(24) goes down. o Node (24) will detach and become the root of its own floating DAG o Node (34) will learn that its DAG parent is now part of its own floating DAG, will consider that it can remain a part of the DAG rooted at node (LBR) via node (33), and will initiate procedures to detach from DAG (LBR) in order to re-attach at a lower rank. o Node (45) will similarly make preparations to remain attached to the DAG rooted at (LBR) by detaching from Node (34) and re- @@ -4081,56 +3640,56 @@ o Node (45) may now anyway add node (44) to its set of DAG parents, as such an addition does not require any modification to its own rank. o Node (24) will observe that it may reattach to the DAG rooted at node (LBR) by selecting node (34) as its DAG parent, thus reversing the relationship that existed in the initial state. B.3. Link Added - Consider the example of Figure 11 when link (12)-(42) appears. + Consider the example of Figure 8 when link (12)-(42) appears. o Node (42) will see a chance to get closer to the LBR by adding (12) to its set of DAG parents, {(32), (12)} o Node (42) may be content to leave its advertised rank at 5, reflecting a rank deeper than its deepest parent (32). o Node (42) may now choose to remain where it is, with two parents {(12), (32)}. Should there be a reason for Node (42) to evict Node (32) from its set of DAG parents, Node (42) would then advertise itself at rank 2, thus moving up the DAG. In this case, Node (53), (54), and (55) may similarly follow and advertise themselves at rank 3. B.4. Node Removed - Consider the example of Figure 11 when node (41) disappears. + Consider the example of Figure 8 when node (41) disappears. o Node (51) and (52) will now have empty DAG parent sets and be detached from the DAG rooted by (LBR), advertising themselves as the root of their own floating DAGs. o Node (52) would observe a chance to reattach to the DAG rooted at (LBR) by adding Node (53) to its set of DAG parents, after an appropriate delay to avoid creating loops. Node (52) will then advertise itself in the DAG rooted at (LBR) at rank 7. o Node (51) will then be able to reattach to the DAG rooted at (LBR) by adding Node (52) to its set of DAG parents and advertising itself at rank 8. B.5. New LBR Added - Consider the example of Figure 11 when a new LBR, (LBR2) appears, - with connectivity (LBR2)-(52), (LBR2)-(53). + Consider the example of Figure 8 when a new LBR, (LBR2) appears, with + connectivity (LBR2)-(52), (LBR2)-(53). o Nodes (52) and Node (53) will see a chance to join a new DAG rooted at (LBR2) with a rank of 2. Node (52) and (53) may take this chance immediately, as there is no risk of forming loops when joining a DAG that has never before been encountered. Note that the nodes may choose to join the new DAG rooted at (LBR2) if and only if (LBR2) offers more optimum properties in line with the implementation specific local policy. o Nodes (52) and (53) begin to send RA-DIO messages advertising @@ -4144,21 +3703,21 @@ o Node (55) may then join the new DAG at rank 4, possibly to get closer to the DAG root. o The remaining nodes may choose to remain in their current positions within the DAG rooted at node (LBR), since there is no clear advantage to be gained by moving to DAG (LBR2). B.6. Destination Advertisement - Consider the example DAG depicted in Figure 12. Suppose that Nodes + Consider the example DAG depicted in Figure 9. Suppose that Nodes (22) and (32) are unable to record routing state. Suppose that Node (42) is able to perform prefix aggregation on behalf of Nodes (53), (54), and (55). o Node (53) would send a NA-DAO message to Node (42), indicating the availability of destination (53). o Node (54) and Node (55) would similarly send NA-DAO messages to Node (42) indicating their own destinations. @@ -4190,20 +3749,304 @@ source route to (32) * Destination (42') is available via Node (22) and the piecewise source route to (32), (42'). o Node (12) sends NA-DAO messages to (LBR), allowing (LBR) to learn routes to the destinations (12), (22), (32), and (42'). (42), (53), (54), and (55) are available via the aggregation (42'). It is not necessary for Node (12) to propagate the piecewise source routes to (LBR). +B.7. Example: DAG Parent Selection + + For example, suppose that a node (N) is not attached to any DAG, and + that it is in range of nodes (A), (B), (C), (D), and (E). Let all + nodes be configured to use an OCP which defines a policy such that + ETX is to be minimized and paths with the attribute `Blue' should be + avoided. Let the rank computation indicated by the OCP simply + reflect the ETX aggregated along the path. Let the links between + node (N) and its neighbors (A-E) all have an ETX of 1 (which is + learned by node (N) through some implementation specific method). + Let node (N) be configured to send IPv6 Router Solicitation (RS) + messages to probe for nearby DAGs. + + o Node (N) transmits a Router Solicitation. + + o Node (B) responds. Node (N) investigates the RA-DIO message, and + learns that Node (B) is a member of DAGID 1 at rank 4, and not + `Blue'. Node (N) takes note of this, but is not yet confident. + + o Similarly, Node (N) hears from Node (A) at rank 9, Node (C) at + rank 5, and Node (E) at rank 4. + + o Node (D) responds. Node (D) has a RA-DIO message that indicates + that it is a member of DAGID 1 at rank 2, but it carries the + attribute `Blue'. Node (N)'s policy function rejects Node (D), + and no further consideration is given. + + o This process continues until Node (N), based on implementation + specific policy, builds up enough confidence to trigger a decision + to join DAGID 1. Let Node (N) determine its most preferred parent + to be Node (E). + + o Node (N) adds Node (E) (rank 4) to its set of DAG parents for + DAGID 1. Following the mechanisms specified by the OCP, and given + that the ETX is 1 for the link between (N) and (E), Node (N) is + now at rank 5 in DAGID 1. + + o Node (N) adds Node (B) (rank 4) to its set of DAG parents for + DAGID 1. + + o Node (N) is a sibling of Node (C), both are at rank 5. + + o Node (N) may now forward traffic intended for the default + destination inward along DAGID 1 via nodes (B) and (E). In some + cases, e.g. if nodes (B) and (E) are tried and fail, node (N) may + also choose to forward traffic to its sibling node (C), without + making inward progress but with the intention that node (C) or a + following successor can make inward progress. Should Node (C) not + have a viable parent, it should never send the packet back to Node + (N) (to avoid a 2-node loop). + +B.8. Example: DAG Maintenance + + : : : + : : : + (A) (A) (A) + |\ | | + | `-----. | | + | \ | | + (B) (C) (B) (C) (B) + | | \ + | | `-----. + | | \ + (D) (D) (C) + | + | + | + (D) + + -1- -2- -3- + + Figure 10: DAG Maintenance + + Consider the example depicted in Figure 10-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 10-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 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 10-3 + +B.9. Example: Greedy Parent Selection and Instability + + (A) (A) (A) + |\ |\ |\ + | `-----. | `-----. | `-----. + | \ | \ | \ + (B) (C) (B) \ | (C) + \ | | / + `-----. | | .-----` + \| |/ + (C) (B) + + -1- -2- -3- + + Figure 11: Greedy DAG Parent Selection + + Consider the example depicted in Figure 11. A DAG is depicted in 3 + different configurations. A usable link between (B) and (C) exists + in all 3 configurations. In Figure 11-1, Node (A) is a DAG parent + for Nodes (B) and (C), and (B)--(C) is a sibling link. In + Figure 11-2, Node (A) is a DAG parent for Nodes (B) and (C), and Node + (B) is also a DAG parent for Node (C). In Figure 11-3, Node (A) is a + DAG parent for Nodes (B) and (C), and Node (C) is also a DAG parent + for Node (B). + + If a RPL node is too greedy, in that it attempts to optimize for an + additional number of parents beyond its preferred parent, then an + instability can result. Consider the DAG illustrated in Figure 11-1. + In this example, Nodes (B) and (C) may most prefer Node (A) as a DAG + parent, but are operating under the greedy condition that will try to + optimize for 2 parents. + + When the preferred parent selection causes a node to have only one + parent and no siblings, the node may decide to insert itself at a + slightly higher rank in order to have at least one sibling and thus + an alternate forwarding solution. This does not deprive other nodes + of a forwarding solution and this is considered acceptable + greediness. + + o Let Figure 11-1 be the initial condition. + + o Suppose Node (C) first is able to leave the DAG and rejoin at a + lower rank, taking both Nodes (A) and (B) as DAG parents as + depicted in Figure 11-2. Now Node (C) is deeper than both Nodes + (A) and (B), and Node (C) is satisfied to have 2 DAG parents. + + o Suppose Node (B), in its greediness, is willing to receive and + process a RA-DIO message from Node (C) (against the rules of RPL), + and then Node (B) leaves the DAG and rejoins at a lower rank, + taking both Nodes (A) and (C) as DAG parents. Now Node (B) is + deeper than both Nodes (A) and (C) and is satisfied with 2 DAG + parents. + + o Then Node (C), because it is also greedy, will leave and rejoin + deeper, to again get 2 parents and have a lower rank then both of + them. + + o Next Node (B) will again leave and rejoin deeper, to again get 2 + parents + + o And again Node (C) leaves and rejoins deeper... + + o The process will repeat, and the DAG will oscillate between + Figure 11-2 and Figure 11-3 until the nodes count to infinity and + restart the cycle again. + + o This cycle can be averted through mechanisms in RPL: + + * Nodes (B) and (C) stay at a rank sufficient to attach to their + most preferred parent (A) and don't go for any deeper (worse) + alternate parents (Nodes are not greedy) + + * Nodes (B) and (C) do not process RA-DIO messages from nodes + deeper than themselves (because such nodes are possibly in + their own sub-DAGs) + +B.10. Example: DAG Merge + + : + : + (A) (D) + | | + | | + | | + (B) (E) + | | + | | + | | + (C) (F) + + Figure 12: Merging DAGs + + Consider the example depicted in Figure 12. Nodes (A), (B), and (C) + are part of some larger grounded DAG, where Node (A) is at a rank of + d, Node (B) at d+1, and Node (C) at d+2. The DAG comprised of Nodes + (D), (E), and (F) is a floating, less preferred, DAG, with Node (D) + as the DAG root. This floating DAG may have been formed, for + example, in the absence of a grounded DAG or when Node (D) had to + detach from a grounded DAG and (E) and (F) followed. All nodes are + using compatible objective code points. + + Nodes (D), (E), and (F) would rather join the more preferred grounded + DAG if they are able than to remain in the less preferred floating + DAG. + + Next, let links (C)--(D) and (A)--(E) become viable. The following + sequence of events may then occur in a typical case: + + o Node (D) will receive and process a RA-DIO message from Node (C) + on link (C)--(D). Node (D) will consider Node (C) a candidate + neighbor and process the RA-DIO message since Node (C) belongs to + a different DAG (different DAGID) than Node (D). Node (D) will + note that Node (C) is in a grounded DAG at rank d+2, and will + begin the process to join the grounded DAG at rank d+3. Node (D) + will start a DAG Hop timer, logically associated with the grounded + DAG at Node (C), to coordinate the jump. The DAG Hop timer will + have a duration proportional to d+2. + + o Similarly, Node (E) will receive and process a RA-DIO message from + Node (A) on link (A)--(E). Node (E) will consider Node (A) a + candidate neighbor, will note that Node (A) is in a grounded DAG + at rank d, and will begin the process to join the grounded DAG at + rank d+1. Node (E) will start a DAG Hop timer, logically + associated with the grounded DAG at Node (A), to coordinate the + jump. The DAG Hop timer will have a duration proportional to d. + + o Node (F) takes no action, for Node (F) has observed nothing new to + act on. + + o Node (E)'s DAG Hop timer for the grounded DAG at Node (A) expires + first. Node (E), upon the DAG Hop timer expiry, removes Node (D) + as its parent, thus emptying the DAG parent set for the floating + DAG, and leaving the floating DAG. Node (E) then jumps to the + grounded DAG by entering Node (A) into the set of DAG parents for + the grounded DAG. Node (E) is now in the grounded DAG at rank + d+1. Node (E), by jumping into the grounded DAG, has created an + inconsistency by changing its DAGID, and will begin to emit RA-DIO + messages more frequently. + + o Node (F) will receive and process a RA-DIO message from Node (E). + Node (F) will observe that Node (E) has changed its DAGID and will + directly follow Node (E) into the grounded DAG. Node (F) is now a + member of the grounded DAG at rank d+2. Note that any additional + sub-DAG of Node (E) would continue to join into the grounded DAG + in this coordinated manner. + + o Node (D) will receive a RA-DIO message from Node (E). Since Node + (E) is now in a different DAG, Node (D) may process the RA-DIO + message from Node (E). Node (D) will observe that, via node (E), + it could attach to the grounded DAG at rank d+2. Node (D) will + start another DAG Hop timer, logically associated with the + grounded DAG at Node (E), with a duration proportional to d+1. + Node (D) now is running two DAG hop timers, one which was started + with duration proportional to d+1 and one proportional to d+2. + + o Generally, Node (D) will expire the timer associated with the jump + to the grounded DAG at node (E) first. Node (D) may then jump to + the grounded DAG by entering Node (E) into its DAG parent set for + the grounded DAG. Node (D) is now in the grounded DAG at rank + d+2. + + o In this way RPL has coordinated a merge between the more preferred + grounded DAG and the less preferred floating DAG, such that the + nodes within the two DAGs come together in a generally ordered + manner, avoiding the formation of loops in the process. + Appendix C. Additional Examples Consider the expanded example LLN physical topology in Figure 13. In this example an additional LBR is added. Suppose that all nodes are configured with an implementation specific policy function that aims to minimize the number of hops, and that both LBRs are configured to root different DAGIDs. We may now walk through the formation of the two DAGs. (LBR) (LBR2)