idnits 2.17.1 draft-ietf-roll-rpl-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.i or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? (You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Feb 2009 rather than one of the newer Notices. See https://trustee.ietf.org/license-info/.) Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 26, 2009) is 5296 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Outdated reference: A later version (-11) exists of draft-ietf-bfd-base-09 == Outdated reference: A later version (-15) exists of draft-ietf-manet-nhdp-10 == Outdated reference: A later version (-09) exists of draft-ietf-roll-building-routing-reqs-07 == Outdated reference: A later version (-11) exists of draft-ietf-roll-home-routing-reqs-08 == Outdated reference: A later version (-19) exists of draft-ietf-roll-routing-metrics-01 == Outdated reference: A later version (-13) exists of draft-ietf-roll-terminology-02 == Outdated reference: A later version (-02) exists of draft-tsao-roll-security-framework-01 Summary: 1 error (**), 0 flaws (~~), 8 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Networking Working Group T. Winter, Ed. 3 Internet-Draft 4 Intended status: Standards Track P. Thubert, Ed. 5 Expires: April 29, 2010 Cisco Systems 6 ROLL Design Team 7 IETF ROLL WG 8 October 26, 2009 10 RPL: IPv6 Routing Protocol for Low power and Lossy Networks 11 draft-ietf-roll-rpl-04 13 Status of this Memo 15 This Internet-Draft is submitted to IETF in full conformance with the 16 provisions of BCP 78 and BCP 79. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt. 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 This Internet-Draft will expire on April 29, 2010. 36 Copyright Notice 38 Copyright (c) 2009 IETF Trust and the persons identified as the 39 document authors. All rights reserved. 41 This document is subject to BCP 78 and the IETF Trust's Legal 42 Provisions Relating to IETF Documents in effect on the date of 43 publication of this document (http://trustee.ietf.org/license-info). 44 Please review these documents carefully, as they describe your rights 45 and restrictions with respect to this document. 47 Abstract 49 Low power and Lossy Networks (LLNs) are a class of network in which 50 both the routers and their interconnect are constrained: LLN routers 51 typically operate with constraints on (any subset of) processing 52 power, memory and energy (battery), and their interconnects are 53 characterized by (any subset of) high loss rates, low data rates and 54 instability. LLNs are comprised of anything from a few dozen and up 55 to thousands of LLN routers, and support point-to- point traffic 56 (between devices inside the LLN), point-to-multipoint traffic (from a 57 central control point to a subset of devices inside the LLN) and 58 multipoint-to- point traffic (from devices inside the LLN towards a 59 central control point). This document specifies the IPv6 Routing 60 Protocol for LLNs (RPL), which provides a mechanism whereby 61 multipoint-to-point traffic from devices inside the LLN towards a 62 central control point, as well as point-to-multipoint traffic from 63 the central control point to the devices inside the LLN, is 64 supported. Support for point-to-point traffic is also available. 66 Table of Contents 68 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 6 69 1.1. Design Principles . . . . . . . . . . . . . . . . . . . . 6 70 1.2. Expectations of Link Layer Type . . . . . . . . . . . . . 7 71 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 7 72 3. Protocol Model . . . . . . . . . . . . . . . . . . . . . . . . 9 73 3.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . 9 74 3.1.1. Topology Instance and Objectives . . . . . . . . . . . 9 75 3.1.2. Multipoint-to-Point Traffic Flows and DAGs . . . . . . 11 76 3.1.3. Point-to-Multipoint Traffic Flows . . . . . . . . . . 11 77 3.1.4. Point-to-Point Traffic Flows . . . . . . . . . . . . . 12 78 3.2. Protocol Operation . . . . . . . . . . . . . . . . . . . . 12 79 3.2.1. DAG Construction . . . . . . . . . . . . . . . . . . . 12 80 3.2.2. Destination Advertisement . . . . . . . . . . . . . . 15 81 3.3. Loop Avoidance and Stability . . . . . . . . . . . . . . . 17 82 3.3.1. Greediness and Rank-based Instabilities . . . . . . . 17 83 3.3.2. DAG Loops . . . . . . . . . . . . . . . . . . . . . . 18 84 3.3.3. DAO Loops . . . . . . . . . . . . . . . . . . . . . . 18 85 3.3.4. Sibling Loops . . . . . . . . . . . . . . . . . . . . 18 86 4. Routing Metrics and Constraints Used By RPL . . . . . . . . . 18 87 5. RPL Protocol Specification . . . . . . . . . . . . . . . . . . 19 88 5.1. RPL Messages . . . . . . . . . . . . . . . . . . . . . . . 19 89 5.1.1. ICMPv6 RPL Control Message . . . . . . . . . . . . . . 19 90 5.1.2. DAG Information Solicitation (DIS) . . . . . . . . . . 20 91 5.1.3. DAG Information Object (DIO) . . . . . . . . . . . . . 20 92 5.1.4. Destination Advertisement Object (DAO) . . . . . . . . 27 93 5.2. Conceptual Data Structures . . . . . . . . . . . . . . . . 28 94 5.2.1. Candidate Neighbors Data Structure . . . . . . . . . . 28 95 5.2.2. Directed Acyclic Graphs (DAGs) Data Structure . . . . 29 96 5.3. DAG Rank . . . . . . . . . . . . . . . . . . . . . . . . . 30 97 5.4. DAG Discovery and Maintenance . . . . . . . . . . . . . . 31 98 5.4.1. DAG Discovery Rules . . . . . . . . . . . . . . . . . 32 99 5.4.2. Reception and Processing of DIO messages . . . . . . . 36 100 5.4.3. DIO Transmission . . . . . . . . . . . . . . . . . . . 38 101 5.4.4. Trickle Timer for DIO Transmission . . . . . . . . . . 39 102 5.5. DAG Sequence Number Increment . . . . . . . . . . . . . . 40 103 5.6. DAG Selection . . . . . . . . . . . . . . . . . . . . . . 41 104 5.7. Administrative rank . . . . . . . . . . . . . . . . . . . 41 105 5.8. Collision . . . . . . . . . . . . . . . . . . . . . . . . 42 106 5.9. Guidelines for Objective Functions . . . . . . . . . . . . 42 107 5.9.1. Objective Function . . . . . . . . . . . . . . . . . . 42 108 5.9.2. Objective Function 0 (OF0) . . . . . . . . . . . . . . 44 109 5.10. Establishing Routing State Outward Along the DAG . . . . . 46 110 5.10.1. Destination Advertisement Operation . . . . . . . . . 47 111 5.11. Loop Detection . . . . . . . . . . . . . . . . . . . . . . 54 112 5.11.1. Host Basic Operation . . . . . . . . . . . . . . . . . 55 113 5.11.2. Instance Forwarding . . . . . . . . . . . . . . . . . 55 114 5.11.3. DAG Inconsistency Loop Detection . . . . . . . . . . . 56 115 5.11.4. Sibling Loop Avoidance . . . . . . . . . . . . . . . . 56 116 5.11.5. DAO Inconsistency Loop Detection and Recovery . . . . 57 117 5.12. Multicast Operation . . . . . . . . . . . . . . . . . . . 57 118 5.13. Maintenance of Routing Adjacency . . . . . . . . . . . . . 58 119 5.14. Packet Forwarding . . . . . . . . . . . . . . . . . . . . 59 120 6. RPL Constants and Variables . . . . . . . . . . . . . . . . . 60 121 7. Manageability Considerations . . . . . . . . . . . . . . . . . 61 122 7.1. Control of Function and Policy . . . . . . . . . . . . . . 61 123 7.1.1. Initialization Mode . . . . . . . . . . . . . . . . . 61 124 7.1.2. DIO Base option . . . . . . . . . . . . . . . . . . . 61 125 7.1.3. Trickle Timers . . . . . . . . . . . . . . . . . . . . 62 126 7.1.4. DAG Sequence Number Increment . . . . . . . . . . . . 63 127 7.1.5. Destination Advertisement Timers . . . . . . . . . . . 63 128 7.1.6. Policy Control . . . . . . . . . . . . . . . . . . . . 63 129 7.1.7. Data Structures . . . . . . . . . . . . . . . . . . . 63 130 7.2. Information and Data Models . . . . . . . . . . . . . . . 64 131 7.3. Liveness Detection and Monitoring . . . . . . . . . . . . 64 132 7.3.1. Candidate Neighbor Data Structure . . . . . . . . . . 64 133 7.3.2. Directed Acyclic Graph (DAG) Table . . . . . . . . . . 64 134 7.3.3. Routing Table . . . . . . . . . . . . . . . . . . . . 65 135 7.3.4. Other RPL Monitoring Parameters . . . . . . . . . . . 65 136 7.3.5. RPL Trickle Timers . . . . . . . . . . . . . . . . . . 66 137 7.4. Verifying Correct Operation . . . . . . . . . . . . . . . 66 138 7.5. Requirements on Other Protocols and Functional 139 Components . . . . . . . . . . . . . . . . . . . . . . . . 66 140 7.6. Impact on Network Operation . . . . . . . . . . . . . . . 66 141 8. Security Considerations . . . . . . . . . . . . . . . . . . . 66 142 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 66 143 9.1. RPL Control Message . . . . . . . . . . . . . . . . . . . 66 144 9.2. New Registry for RPL Control Codes . . . . . . . . . . . . 67 145 9.3. New Registry for the Control Field of the DIO Base 146 Option . . . . . . . . . . . . . . . . . . . . . . . . . . 67 147 9.4. DAG Information Object (DIO) Suboption . . . . . . . . . . 68 148 9.5. Objective Code Point for the Default Objective 149 Function OF0 . . . . . . . . . . . . . . . . . . . . . . . 68 150 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 68 151 11. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 69 152 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 70 153 12.1. Normative References . . . . . . . . . . . . . . . . . . . 70 154 12.2. Informative References . . . . . . . . . . . . . . . . . . 71 155 Appendix A. Requirements . . . . . . . . . . . . . . . . . . . . 72 156 A.1. Protocol Properties Overview . . . . . . . . . . . . . . . 72 157 A.1.1. IPv6 Architecture . . . . . . . . . . . . . . . . . . 73 158 A.1.2. Typical LLN Traffic Patterns . . . . . . . . . . . . . 73 159 A.1.3. Constraint Based Routing . . . . . . . . . . . . . . . 73 160 A.2. Deferred Requirements . . . . . . . . . . . . . . . . . . 74 161 Appendix B. Examples . . . . . . . . . . . . . . . . . . . . . . 74 162 B.1. Destination Advertisement . . . . . . . . . . . . . . . . 76 163 B.2. Example: DAG Parent Selection . . . . . . . . . . . . . . 77 164 B.3. Example: DAG Maintenance . . . . . . . . . . . . . . . . . 78 165 B.4. Example: Greedy Parent Selection and Instability . . . . . 79 166 Appendix C. Outstanding Issues . . . . . . . . . . . . . . . . . 81 167 C.1. Additional Support for P2P Routing . . . . . . . . . . . . 81 168 C.2. Loop Detection . . . . . . . . . . . . . . . . . . . . . . 81 169 C.3. Destination Advertisement / DAO Fan-out . . . . . . . . . 81 170 C.4. Source Routing . . . . . . . . . . . . . . . . . . . . . . 82 171 C.5. Address / Header Compression . . . . . . . . . . . . . . . 82 172 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 82 174 1. Introduction 176 Low power and Lossy Networks (LLNs) are made largely of constrained 177 nodes (with limited processing power, memory, and sometimes energy 178 when they are battery operated). These routers are interconnected by 179 lossy links, typically time supporting only low data rates, that are 180 usually unstable with relatively low packet delivery rates. Another 181 characteristic of such networks is that the traffic patterns are not 182 simply unicast, but in many cases point-to-multipoint or multipoint- 183 to-point. Furthermore such networks may potentially comprise up to 184 thousands of nodes. These characteristics offer unique challenges to 185 a routing solution: the IETF ROLL Working Group has defined 186 application-specific routing requirements for a Low power and Lossy 187 Network (LLN) routing protocol, specified in 188 [I-D.ietf-roll-building-routing-reqs], 189 [I-D.ietf-roll-home-routing-reqs], [RFC5673], and [RFC5548]. This 190 document specifies the IPv6 Routing Protocol for Low power and Lossy 191 Networks (RPL). 193 1.1. Design Principles 195 RPL was designed with the objective to meet the requirements spelled 196 out in [I-D.ietf-roll-building-routing-reqs], 197 [I-D.ietf-roll-home-routing-reqs], [RFC5673], and [RFC5548]. Because 198 those requirements are heterogeneous and sometimes incompatible in 199 nature, the approach is first taken to design a protocol capable of 200 supporting a core set of functionalities corresponding to the 201 intersection of the requirements. (Note: it is intended that as this 202 design evolves optional features may be added to address some 203 application specific requirements). This is a key protocol design 204 decision providing a granular approach in order to restrict the core 205 of the protocol to a minimal set of functionalities, and to allow 206 each implementation of the protocol to be optimized in terms of, 207 e.g., minimizing required code space and use of limited computation 208 resources. 210 Multiple instances of the protocol can be operated at the same time 211 in order to serve different and potentially antagonistic constraints. 212 Instances run independently of one another with no required 213 interaction. A node might participate to multiple instances and 214 route independently along the associated topologies. This 215 specification defines only the protocol operation for the node within 216 one instance. Consideration is given to default behavior that 217 enables future extensions for the multiple instances and related 218 policies. 220 It must be noted that RPL is not restricted to the aforementioned 221 applications and is expected to be used in other environments. All 222 "MUST" application requirements that cannot be satisfied by RPL will 223 be specifically listed in the Appendix A, accompanied by a 224 justification. 226 The core set of functionalities is to be capable of operating in the 227 most severely constrained environments, with minimal requirements for 228 memory, energy, processing, communication, and other consumption of 229 limited resources from nodes. Trade-offs inherent in the 230 provisioning of protocol features will be exposed to the implementer 231 in the form of configurable parameters, such that the implementer can 232 further tweak and optimize the operation of RPL as appropriate to a 233 specific application and implementation. Finally, RPL is designed to 234 consult implementation specific policies to determine, for example, 235 the evaluation of routing metrics. 237 A set of companion documents to this specification will provide 238 further guidance in the form of applicability statements specifying a 239 set of operating points appropriate to the Building Automation, Home 240 Automation, Industrial, and Urban application scenarios. 242 1.2. Expectations of Link Layer Type 244 This specification does not rely on any particular features of a 245 specific link layer technologies. It is anticipated that an 246 implementer should be able to operate RPL over a variety of different 247 link layers, including but not limited to low power wireless or PLC 248 (Power Line Communication) technologies. 250 Implementers may find RFC 3819 [RFC3819] a useful reference when 251 designing a link layer interface between RPL and a particular link 252 layer technology. 254 2. Terminology 256 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 257 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 258 "OPTIONAL" in this document are to be interpreted as described in RFC 259 2119 [RFC2119]. 261 This document requires readers to be familiar with the terminology 262 described in `Terminology in Low power And Lossy Networks' 263 [I-D.ietf-roll-terminology]. 265 DAG: Directed Acyclic Graph. A directed graph having the property 266 that all edges are oriented in such a way that no cycles exist. 267 In the RPL context, all edges are contained in paths oriented 268 toward and terminating at one or more root nodes (a DAG root, 269 or sink- typically a Low power and Lossy Network Border Router 270 (LBR)). For the purpose of this document, the term DAG is 271 often used to refer to a DAG Iteration as defined below. 273 DAG Instance: A DAG Instance is a set of possibly multiple 274 Destination Oriented DAGs. A network may have more than one 275 DAG Instance, and a RPL router can participate to multiple DAG 276 instances. Each DAG Instance operates independently of other 277 DAG Instances. This document describes operation within a 278 single DAG instance. 280 InstanceID: Unique identifier of a DAG Instance. 282 Destination Oriented DAG: A DAG rooted at a single destination, 283 which is a node with no outgoing edges. The tuple (InstanceID, 284 DAGID) uniquely identifies a Destination Oriented DAG. In the 285 RPL context, a router can can belong to at most one Destination 286 Oriented DAG per DAG Instance. 288 DAGID: The identifier of a DAG root. The DAGID must be unique 289 within the scope of a DAG Instance in the LLN. 291 DAG Iteration: The DAG that results from the iterative process that 292 reshapes the Destination Oriented DAG upon a stimulation by the 293 root. 295 DAGSequenceNumber: A sequential counter that is incremented by the 296 root to form a new Iteration of a DAG. A DAG Iteration is 297 identified uniquely by the (InstanceID, DAGID, 298 DAGSequenceNumber) tuple. 300 DAG parent: A parent of a node within a DAG is one of the immediate 301 successors of the node on a path towards the DAG root. 303 DAG sibling: A sibling of a node within a DAG is defined in this 304 specification to be any neighboring node which is located at 305 the same rank within a DAG. Note that siblings defined in this 306 manner do not necessarily share a common parent. 308 DAG root: A DAG root is a node within the DAG that has no outgoing 309 edges. Because the graph is acyclic, by definition all DAGs 310 must have at least one DAG root and all paths terminate at a 311 DAG root. 313 Sub-DAG The sub-DAG of a node is the set of other nodes in the DAG 314 that might use a path towards the DAG root that contains the 315 node. Nodes in the sub-DAG of a node have a greater rank 316 (although not all nodes of greater rank are in the sub-DAG). 318 Grounded: A DAG is grounded if it contains a DAG root offering 319 connectivity to an external routed infrastructure such as the 320 public Internet or a private core (non-LLN) IP network. 322 Floating: A DAG is floating if is not grounded. A floating DAG is 323 not expected to reach any additional external routed 324 infrastructure such as the public Internet or a private core 325 (non-LLN) IP network. 327 Inward: Inward refers to the direction from leaf nodes towards DAG 328 roots, following the orientation of the edges within the DAG. 330 Outward: Outward refers to the direction from DAG roots towards leaf 331 nodes, going against the orientation of the edges within the 332 DAG. 334 OCP: Objective Code Point. The Objective Code Point is used to 335 indicate which Objective Function is in use in a DAG. The 336 Objective Code Point is further described in 337 [I-D.ietf-roll-routing-metrics]. 339 OF: Objective Function. The Objective Function (OF) defines which 340 routing metrics, optimization objectives, and related functions 341 are in use in a DAG. The Objective Function is further 342 described in [I-D.ietf-roll-routing-metrics]. 344 Note that in this document, the terms `node' and `LLN router' are 345 used interchangeably. 347 3. Protocol Model 349 The aim of this section is to describe RPL in the spirit of 350 [RFC4101]. Protocol details can be found in further sections. 352 3.1. Overview 354 3.1.1. Topology Instance and Objectives 356 A topology instance of RPL exists over the scope of an LLN in support 357 of a particular application, or service, and is optimized according 358 to a certain objective, as determined by an Objective Function (OF), 359 and may be characterized by certain destination prefixes as well. A 360 topology instance, or DAG Instance, may be administratively 361 associated with an InstanceID. 363 A single topology instance may comprise: 365 o a single Destination Oriented DAG with a single DAG root 367 * For example, a DAG optimized to minimize latency rooted at a 368 single centralized lighting controller in a home automation 369 application. 371 o multiple uncoordinated Destination Oriented DAGs with independent 372 DAG roots (differing DAGIDs) 374 * For example, multiple data collection points in an urban data 375 collection application that do not have an always-on backbone 376 suitable to coordinate to form a single DAG, and further use 377 the formation of multiple DAGs as a means to dynamically and 378 autonomously partition the network. 380 o a single Destination Oriented DAG with multiple DAG roots 381 coordinating over some backbone 383 * For example, multiple border routers operating with a reliable 384 backbone, e.g. in support of a 6LowPAN application, that are 385 capable to act as logically equivalent sinks to the same DAG. 387 o a combination of one of the above as suited to some application 388 scenario 390 The exact deployment scenario is determined as appropriate to the 391 application and capabilities of the LLN nodes. What is suitable for 392 one deployment may not be possible or necessary for another. 394 Traffic is bound to a specific DAG Instance by a marking in the flow 395 label of the IPv6 header. Traffic originating in support of a 396 particular application may be tagged to follow an appropriate 397 instance, for example to follow paths optimized for low latency or 398 low energy. The provisioning or automated discovery of a mapping 399 between an InstanceID and a type or service of application traffic is 400 beyond the scope of this specification. 402 Conceptually a node running RPL may capable to maintain a membership 403 in multiple DAG Instances in support of different application 404 services and/or optimization objectives. For example, one instance 405 may optimize for minimizing latency and a separate orthogonal 406 instance may optimize for minimizing energy. This scenario does 407 introduce some additional considerations, for example loop avoidance 408 and default routing behavior. These considerations are beyond the 409 scope of this specification and are intended to be elaborated on in a 410 future revision of this or a companion specification. As such, this 411 specification will deal exclusively with the scenario where a node 412 implements RPL in support of a single DAG Instance. 414 3.1.2. Multipoint-to-Point Traffic Flows and DAGs 416 Many of the dominant traffic flows in support of the LLN application 417 scenarios are MP2P flows ([I-D.ietf-roll-building-routing-reqs], 418 [I-D.ietf-roll-home-routing-reqs], [RFC5673], and [RFC5548]). These 419 flows are rooted at designated nodes that have some application 420 significance, such as providing connectivity to an external routed 421 infrastructure. The term "external" is used to refer to the public 422 Internet or a core private (non-LLN) IP network. 424 LLN nodes running RPL will construct Directed Acyclic Graphs (DAGs) 425 rooted at DAG roots, which may be naturally designated according to 426 their application significance. This structure provides the routing 427 solution for the dominant MP2P traffic flows. The DAG structure 428 further provides each node potentially multiple successors for MP2P 429 flows, which may be used for, e.g., local route repair or load 430 balancing. 432 Nodes running RPL are able to further restrict the scope of the 433 routing problem by using the DAG as a reference topology. By 434 referencing a rank property that is related to the positions in the 435 DAG, nodes are able to determine their positions in a DAG relative to 436 each other. This information is used by RPL in part to construct 437 rules for movement relative to the DAG that endeavor to avoid loops. 438 It is important to note that the rank property is derived from 439 metrics, and not directly from the position in the DAG (Section 5.3). 441 3.1.3. Point-to-Multipoint Traffic Flows 443 As DAGs are organized, RPL will use a destination advertisement 444 mechanism to build up routing tables in support of outward P2MP 445 traffic flows. This mechanism, using the DAG as a reference, 446 distributes routing information across intermediate nodes (between 447 the DAG leaves and the root), guided along the DAG, such that the 448 routes toward destination prefixes in the outward direction may be 449 set up. As the DAG undergoes modification during DAG maintenance, 450 the destination advertisement mechanism can be triggered to update 451 the outward routing state. 453 3.1.4. Point-to-Point Traffic Flows 455 A baseline support for P2P traffic in RPL is provided by the DAG, as 456 P2P traffic may flow inward along the DAG until a common parent is 457 reached that has stored an entry for the destination in its routing 458 table and is capable of directing the traffic outward along the 459 correct outward path. RPL also provides support for the trivial case 460 where a P2P destination may be a `one-hop' neighbor. In the present 461 document RPL does not specify nor preclude any additional mechanisms 462 that may be capable to compute and install more optimal routes into 463 LLN nodes in support of arbitrary P2P traffic according to some 464 routing metric. 466 3.2. Protocol Operation 468 3.2.1. DAG Construction 470 3.2.1.1. DAG Information Object (DIO) 472 A DAG Information Object is defined and used by RPL in order to build 473 and maintain a DAG. This document defines an ICMPv6 Message Type RPL 474 Control Message, which is capable to carry the DIO. The DIO message 475 conveys information about the DAG, including: 477 o A DAGID used to identify the DAG as sourced from the DAG root. 478 The DAGID must be unique to a single DAG in the scope of the LLN. 480 o Objective Function identified by an Objective Code Point (OCP) as 481 described below. 483 o Rank information used by nodes to determine their positions in the 484 DAG relative to each other. 486 o Sequence number originated from the DAG root, used to aid in 487 identification of dependent sub-DAGs and coordinate topology 488 changes in a manner so as to avoid loops. 490 o Indications and configuration for the DAG, e.g. grounded or 491 floating, administrative preference, ... 493 o A set of path metrics and constraints, as further described in 494 [I-D.ietf-roll-routing-metrics]. 496 o List of additional destination prefixes reachable inwards along 497 the DAG. 499 The DIO messages are issued whenever a change is detected to the DAG 500 such that a node is able to determine that a region of the DAG has 501 become inconsistent. As the DAG stabilizes the period at which RA 502 messages occur is configured to taper off, reducing the steady-state 503 overhead of DAG maintenance. The periodic issue of DIO messages, 504 along with the triggered DIO messages in response to inconsistency, 505 is one feature that enables RPL to operate in the presence of 506 unreliable links. 508 3.2.1.2. Grounded and Floating DAGs 510 Certain LLN nodes may offer connectivity to an external routed 511 infrastructure in support of an application scenario. These nodes 512 are designated `grounded', and may serve as the DAG roots of a 513 grounded DAG. DAGs that do not have a grounded DAG root are floating 514 DAGs. In either case routes may be provisioned toward the DAG root, 515 although in the floating case there is no expectation to reach an 516 external infrastructure. Some applications will include permanent 517 floating DAGs. 519 3.2.1.3. Administrative Preference 521 An administrative preference may be associated with each DAG root, 522 and thereby each DAG, in order that some DAGs in the LLN may be more 523 preferred over other DAGs. For example, a DAG root that is sinking 524 traffic in support of a data collection application may be configured 525 by the application to be very preferred. A transient DAG, e.g. a DAG 526 that is only existing until a permanent DAG is found, may be 527 configured to be less preferred. The administrative preference 528 offers a way to engineer the formation of the DAG in support of the 529 application. 531 3.2.1.4. Objective Function (OF) 533 The Objective Function (OF) conveys and controls the optimization 534 objectives in use within the DAG. The Objective Function is 535 indicated by an Objective Code Point (OCP), and is further specified 536 in [I-D.ietf-roll-routing-metrics]. Each instance of an allocated OF 537 indicates: 539 o The set of metrics used within the DAG 541 o The method used for least cost path determination. 543 o The method used to compute DAG Rank 545 o The methods used to prepare metrics for propagation within a DIO 546 message 548 By using defined OCPs that are understood by all nodes in a 549 particular implementation, and by conveying them in the DIO message, 550 RPL nodes may work to build optimized LLN using a variety of 551 application and implementation specific metrics and goals. 553 A default OF, OF0 (designated by OCP value of 0x0000), is specified 554 with a well-defined default behavior. OF0 may be used to define RPL 555 behaviors in the case where a node encounters a DIO message 556 containing a code point that it does not support, if allowed by 557 policy. 559 3.2.1.5. Distributed Algorithm Operation 561 A high level overview of the distributed algorithm which constructs 562 the DAG is as follows: 564 o Some nodes may be initially provisioned to act as DAG roots, 565 either permanent or transient, with associated preferences. 567 o Nodes will maintain a data structure containing their candidate 568 (viable) neighbors, as determined by the implementation. This 569 data structure will also track DAG information as learned from and 570 associated with each neighbor. 572 o Nodes that are members of a DAG, including DAG roots, will 573 multicast DIO messages as needed (when inconsistency is detected), 574 to their link-local neighbors. Nodes will also respond to DIS 575 messages. 577 o Nodes that receive DIO messages may either discard the DIO based 578 on several criteria, including rank-based loop avoidance rules, or 579 process the DIO to maintain a position in an existing DAG or 580 improve a position as according to an Objective Function (OF) and 581 current path cost. 583 o Nodes manage a set of DAG Parents according to the rules specified 584 by RPL. This set is also augmented to include DAG siblings. 586 o DIO messages may be emitted more or less frequently as a function 587 of DAG consistency. 589 o As less preferred DAGs encounter more preferred DAGs that offer 590 equivalent or better optimization objectives for the same 591 InstanceID, the nodes in the less preferred DAGs may leave to join 592 the more preferred DAGs, finally leaving only the more preferred 593 DAGs. This is an illustration of the mechanism by which an 594 application may engineer DAG construction. 596 o The nodes provision routing table entries for the destinations 597 specified by the DIO towards their DAG Parents. Nodes may 598 provision a DAG Parent as a default gateway. 600 3.2.2. Destination Advertisement 602 As RPL constructs DAGs, nodes may provision routes toward 603 destinations advertised through DIO messages through their selected 604 parents, and are thus able to send traffic inward along the DAG by 605 forwarding to their selected parents. However, this mechanism alone 606 is not sufficient to support P2MP traffic flowing outward along the 607 DAG from the DAG root toward nodes. A destination advertisement 608 mechanism is employed by RPL to build up routing state in support of 609 these outward flows. The destination advertisement mechanism may not 610 be supported in all implementations, as appropriate to the 611 application requirements. A DAG root that supports using the 612 destination advertisement mechanism to build up routing state will 613 indicate such in the DIO message. A DAG root that supports using the 614 destination advertisement mechanism must be capable of allocating 615 enough state to store the routing state received from the LLN. 617 3.2.2.1. Destination Advertisement Object (DAO) 619 A Destination Advertisement Object is defined and used by RPL in 620 order to convey the destination information inward along the DAG 621 toward the DAG root. This document defines an ICMPv6 Message Type 622 RPL Control Message, which is capable to carry the DAO. The 623 information conveyed in the DAO message includes the following: 625 o A lifetime and sequence counter to determine the freshness of the 626 destination advertisement. 628 o Depth information used by nodes to determine how far away the 629 destination (the source of the destination advertisement) is 631 o Prefix information to identify the destination, which may be a 632 prefix, an individual host, or multicast listeners 634 o Reverse Route information to record the nodes visited (along the 635 outward path) when the intermediate nodes along the path cannot 636 support storing state for Hop-By-Hop routing. 638 3.2.2.2. Destination Advertisement Operation 640 As the DAG is constructed and maintained, nodes are capable to emit 641 DAO messages to a subset of their DAG parents. 643 3.2.2.2.1. `One-Hop' Neighbors 645 As a special case, a node may periodically emit a link-local 646 multicast IPv6 DAO message advertising its locally available 647 destination prefixes. This mechanism allows for the one-hop 648 neighbors of a node to learn explicitly of the prefixes on the node, 649 and in some application specific scenarios this is desirable in 650 support of provisioning a trivial `one-hop' route. In this case, 651 nodes that receive the multicast destination advertisement may use it 652 to provision the one-hop route only, and not engage in any additional 653 processing (so as not to engage the mechanisms used by a DAG parent). 655 3.2.2.2.2. Operation in Support of Stateful Nodes 657 When a (unicast) DAO message reaches a node capable of storing 658 routing state, the node extracts information from the DAO message and 659 updates its local database with a record of the DAO message and the 660 neighbor that it was received from. When the node later propagates 661 DAO messages, it selects the best (least depth) information for each 662 destination and conveys this information again in the form of DAO 663 messages to a subset of its own DAG parents. At this time the node 664 may perform route aggregation if it is able, thus reducing the 665 overall number of DAO messages. 667 3.2.2.2.3. Operation in Support of Stateless Nodes 669 When a (unicast) DAO message reaches a node incapable of storing 670 additional state, the node must append the next-hop address (from 671 which neighbor the DAO message was received) to a Reverse Route Stack 672 carried within the DAO message. The node then passes the DAO message 673 on to one or more of its DAG parents without storing any additional 674 state. 676 When a node that is capable of storing routing state encounters a 677 (unicast) DAO message with a Reverse Route Stack that has been 678 populated, the node knows that the DAO message has traversed a region 679 of nodes that did not record any routing state. The node is able to 680 detach and store the Reverse Route State and associate it with the 681 destination described by the DAO message. Subsequently the node may 682 use this information to construct a source route in order to bridge 683 the region of nodes that are unable to support Hop-By-Hop routing to 684 reach the destination. 686 3.2.2.2.4. Additional Considerations 688 Further aggregations of DAO messages prefix reachability information 689 by destinations are possible in order to support additional 690 scalability. 692 A special case of an DAO message, termed a `no-DAO', may be used to 693 tear down the routing state that has been established by the 694 destination advertisement mechanism in case of, e.g., unreachability 695 or other events that affect the outward routing state. 697 A further example of the operation of the destination advertisement 698 mechanism is available in Appendix B.1 700 3.3. Loop Avoidance and Stability 702 The goal of a guaranteed consistent and loop free global routing 703 solution for an LLN may not be practically achieved given the real 704 behavior and volatility of the underlying metrics. The trade offs to 705 achieve a stable approximation of global convergence may be too 706 restrictive with respect to the need of the LLN to react quickly in 707 response to the lossy environment. Globally the LLN may be able to 708 achieve a weak convergence, in particular as link changes are able to 709 be handled locally and result in minimal changes to global topology. 711 RPL does not aim to guarantee loop free path selection, or strong 712 global convergence. In order to reduce control overhead, in 713 particular the expense of mechanisms such as count-to-infinity, RPL 714 does try to avoid the creation of loops when undergoing topology 715 changes. 717 RPL includes rank-based mechanisms for detecting loops to ensure that 718 packets make forward progress within the DAG and trigger DAG repair 719 if necessary. 721 3.3.1. Greediness and Rank-based Instabilities 723 Once a node has joined a DAG, RPL disallows certain behaviors, 724 including greediness, in order to prevent resulting instabilities in 725 the DAG. 727 If a node is allowed to be greedy and attempts to move deeper in the 728 DAG, beyond its most preferred parent, in order to increase the size 729 of the DAG parent set, then an instability can result. This is 730 illustrated in Figure 14. 732 Suppose a node is willing to receive and process a DIO messages from 733 a node in its own sub-DAG, and in general a node deeper than it. In 734 such cases a chance exists to create a feedback loop, wherein two or 735 more nodes continue to try and move in the DAG in order to optimize 736 against each other. In some cases this will result in an 737 instability. It is for this reason that RPL mandates that a node 738 never receive and process DIO messages from deeper nodes. This rule 739 creates an `event horizon', whereby a node cannot be influenced into 740 an instability by the action of nodes that may be in its own sub-DAG. 742 A further example of the consequences of greedy operation, and 743 instability related to processing DIO messages from nodes of greater 744 rank, may be found in Appendix B.4 746 3.3.2. DAG Loops 748 A DAG loop may occur when a node detaches from the DAG and reattaches 749 to a device in its prior sub-DAG. This may happen in particular when 750 DIO messages are missed. Strict use of the DAG sequence number can 751 eliminate this type of loop. 753 3.3.3. DAO Loops 755 A DAO loop may occur when the parent has a route installed upon 756 receiving and processing a DAO message from a child, but the child 757 has subsequently cleaned up the state. This loop happens when a no- 758 DAO was missed till a heartbeat cleans up all states. RPL includes 759 loop detection mechanisms that may mitigate the impact of DAO loops 760 and trigger their repair. 762 In the case where stateless DAO operation is used, i.e. source 763 routing specifies the outwards routes, then DAO Loops should not 764 occur on the stateless portions of the path. 766 3.3.4. Sibling Loops 768 Sibling loops could occur if a group of siblings kept choosing 769 amongst themselves as successors such that a packet does not make 770 forward progress. This specification limits the number of times that 771 sibling forwarding may be used at a given rank to prevent sibling 772 loops. 774 4. Routing Metrics and Constraints Used By RPL 776 Routing metrics are used by routing protocols to compute the shortest 777 paths. Interior Gateway Protocols (IGPs) such as IS-IS ([RFC5120]) 778 and OSPF ([RFC4915]) use static link metrics. Such link metrics can 779 simply reflect the bandwidth or can also be computed according to a 780 polynomial function of several metrics defining different link 781 characteristics; in all cases they are static metrics. Some routing 782 protocols support more than one metric: in the vast majority of the 783 cases, one metric is used per (sub)topology. Less often, a second 784 metric may be used as a tie-breaker in the presence of Equal Cost 785 Multiple Paths (ECMP). The optimization of multiple metrics is known 786 as an NP complete problem and is sometimes supported by some 787 centralized path computation engine. 789 In contrast, LLNs do require the support of both static and dynamic 790 metrics. Furthermore, both link and node metrics are required. In 791 the case of RPL, it is virtually impossible to define one metric, or 792 even a composite, that will satisfy all use cases. 794 In addition, RPL supports constrained-based routing where constraints 795 may be applied to link and nodes. If a link or a node does not 796 satisfy a required constraint, it is `pruned' from the candidate list 797 thus leading to a constrained shortest path. 799 The set of supported link/node constraints and metrics is specified 800 in [I-D.ietf-roll-routing-metrics]. 802 The role of the Objective Function is to advertise routing metrics 803 and constraints in addition to the objectives used to compute the 804 (constrained) shortest path. 806 Example 1: Shortest path: path offering the shortest end-to-end delay 808 Example 2: Constrained shortest path: the path that does traverse any 809 battery-operated node and that optimizes the path 810 reliability 812 5. RPL Protocol Specification 814 5.1. RPL Messages 816 5.1.1. ICMPv6 RPL Control Message 818 This document defines the RPL Control Message, a new ICMPv6 message. 819 The RPL Control Message has the following general format, in 820 accordance with [RFC4443]: 822 0 1 2 3 823 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 824 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 825 | Type | Code | Checksum | 826 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 827 | | 828 + Message Body + 829 | | 831 Figure 1: RPL Control Message 833 The RPL Control message is an ICMPv6 information message with a 834 requested Type of 155. 836 The Code will be used to identify RPL Control Messages as follows: 838 o 0x01: DAG Information Solicitation (Section 5.1.2) 840 o 0x02: DAG Information Object (Section 5.1.3) 842 o 0x04: Destination Advertisement Object (Section 5.1.4) 844 5.1.2. DAG Information Solicitation (DIS) 846 The DAG Information Solicitation (DIS) message may be used to solicit 847 a DAG Information Object from a RPL node. Its use is analogous to 848 that of a Router Solicitation; a node may use DIS to probe its 849 neighborhood for nearby DAGs. The DAG Information Solicitation 850 carries no additional message body. 852 5.1.3. DAG Information Object (DIO) 854 The DAG Information Object carries a number of metrics and other 855 information that allows a node to discover a DAG, select its DAG 856 parents, and identify its siblings while employing loop avoidance 857 strategies. 859 5.1.3.1. DIO Base Option 861 The DIO Base Option is a container option, which is always present, 862 and might contain a number of suboptions. The base option regroups 863 the minimum information set that is mandatory in all cases. 865 0 1 2 3 866 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 867 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 868 |G|D|A|0|0| Prf | Sequence | InstanceID | DAGRank | 869 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 870 | | 871 + + 872 | DAGID | 873 + + 874 | | 875 + + 876 | | 877 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 878 | sub-option(s)... 879 +-+-+-+-+-+-+-+-+-+-+-+-+-+ 881 Figure 2: DIO Base Option 883 Control Field: The DAG Control Field is currently allocated as 884 follows: 886 Grounded (G): The Grounded (G) flag is set when the DAG root 887 is offering connectivity to an external routed 888 infrastructure such as the Internet. 890 Destination Advertisement Trigger (D): The Destination 891 Advertisement Trigger (D) flag is set when the DAG root 892 or another node in the successor chain decides to trigger 893 the sending of destination advertisements in order to 894 update routing state for the outward direction along the 895 DAG, as further detailed in Section 5.10. Note that the 896 use and semantics of this flag are still under 897 investigation. 899 Destination Advertisement Supported (A): The Destination 900 Supported (A) bit is set when the DAG root is capable to 901 support the collection of destination advertisement 902 related routing state and enables the operation of the 903 destination advertisement mechanism within the DAG. 905 DAGPreference (Prf): 3-bit unsigned integer set by the DAG 906 root to its preference and unchanged at propagation. 907 DAGPreference ranges from 0x00 (least preferred) to 0x07 908 (most preferred). The default is 0 (least preferred). 909 The DAG preference provides an administrative mechanism 910 to engineer the self-organization of the LLN, for example 911 indicating the most preferred LBR. If a node has the 912 option to join a more preferred DAG while still meeting 913 other optimization objectives, then the node will 914 generally seek to join the more preferred DAG as 915 determined by the OF. 917 Unassigned bits of the Control Field are considered as 918 reserved. They MUST be set to zero on transmission and MUST be 919 ignored on receipt. 921 Sequence Number: 8-bit unsigned integer set by the DAG root, 922 incremented according to a policy provisioned at the DAG root, 923 and propagated with no change outwards along the DAG. Each 924 increment SHOULD have a value of 1 and may cause a wrap back to 925 zero. 927 InstanceID: 8-bit field indicating the topology instance associated 928 with the DAG, as provisioned at the DAG root. 930 DAGRank: 8-bit unsigned integer indicating the DAG rank of the node 931 sending the DIO message. The DAGRank of the DAG root is 932 ROOT_RANK. DAGRank is further described in Section 5.4. 934 DAGID: 128-bit unsigned integer which uniquely identify a DAG. This 935 value is set by the DAG root. The global IPv6 address of the 936 DAG root can be used, however. the DAGID MUST be unique per DAG 937 within the scope of the LLN. In the case where a DAG root is 938 rooting multiple DAGs the DAGID MUST be unique for each DAG 939 rooted at a specific DAG root. 941 The following values MUST NOT change during the propagation of DIO 942 messages outwards along the DAG: 943 Grounded (G) 944 Destination Advertisement Supported (A) 945 DAGPreference (Prf) 946 Sequence 947 InstanceID 948 DAGID 949 All other fields of the DIO message may be updated at each hop of the 950 propagation. 952 5.1.3.1.1. DIO Suboptions 954 In addition to the minimum options presented in the base option, 955 several suboptions are defined for the DIO message: 957 5.1.3.1.1.1. Format 958 0 1 2 959 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 960 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 961 | Subopt. Type | Subopt Length | Subopt Data 962 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 964 Figure 3: DIO Suboption Generic Format 966 Suboption Type: 8-bit identifier of the type of suboption. When 967 processing a DIO message containing a suboption for which the 968 Suboption Type value is not recognized by the receiver, the 969 receiver MUST silently ignore the unrecognized option, continue 970 to process the following suboption, correctly handling any 971 remaining options in the message. 973 Suboption Length: 16-bit unsigned integer, representing the length 974 in octets of the suboption, not including the suboption Type 975 and Length fields. 977 Suboption Data: A variable length field that contains data specific 978 to the option. 980 The following subsections specify the DIO message suboptions which 981 are currently defined for use in the DAG Information Object. 983 Implementations MUST silently ignore any DIO message suboptions 984 options that they do not understand. 986 DIO message suboptions may have alignment requirements. Following 987 the convention in IPv6, these options are aligned in a packet such 988 that multi-octet values within the Option Data field of each option 989 fall on natural boundaries (i.e., fields of width n octets are placed 990 at an integer multiple of n octets from the start of the header, for 991 n = 1, 2, 4, or 8). 993 5.1.3.1.1.2. Pad1 995 The Pad1 suboption does not have any alignment requirements. Its 996 format is as follows: 998 0 999 0 1 2 3 4 5 6 7 1000 +-+-+-+-+-+-+-+-+ 1001 | Type = 0 | 1002 +-+-+-+-+-+-+-+-+ 1004 Figure 4: Pad 1 1006 NOTE! the format of the Pad1 option is a special case - it has 1007 neither Option Length nor Option Data fields. 1009 The Pad1 option is used to insert one or two octets of padding in the 1010 DIO message to enable suboptions alignment. If more than two octets 1011 of padding is required, the PadN option, described next, should be 1012 used rather than multiple Pad1 options. 1014 5.1.3.1.1.3. PadN 1016 The PadN option does not have any alignment requirements. Its format 1017 is as follows: 1019 0 1 2 1020 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 1021 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 1022 | Type = 1 | Subopt Length | Subopt Data 1023 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 1025 Figure 5: Pad N 1027 The PadN option is used to insert three or more octets of padding in 1028 the DIO message to enable suboptions alignment. For N (N > 2) octets 1029 of padding, the Option Length field contains the value N-3, and the 1030 Option Data consists of N-3 zero-valued octets. PadN Option data 1031 MUST be ignored by the receiver. 1033 5.1.3.1.1.4. DAG Metric Container 1035 The DAG Metric Container suboption may be aligned as necessary to 1036 support its contents. Its format is as follows: 1038 0 1 2 1039 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 1040 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 1041 | Type = 2 | Container Length | DAG Metric Data 1042 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 1044 Figure 6: DAG Metric Container 1046 The DAG Metric Container is used to report aggregated path metrics 1047 along the DAG. The DAG Metric Container may contain a number of 1048 discrete node, link, and aggregate path metrics as chosen by the 1049 implementer. The Container Length field contains the length in 1050 octets of the DAG Metric Data. The order, content, and coding of the 1051 DAG Metric Container data is as specified in 1053 [I-D.ietf-roll-routing-metrics]. 1055 The processing and propagation of the DAG Metric Container is 1056 governed by implementation specific policy functions. 1058 5.1.3.1.1.5. Destination Prefix 1060 The Destination Prefix suboption does not have any alignment 1061 requirements. Its format is as follows: 1063 0 1 2 3 1064 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 1065 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1066 | Type = 3 | Length |Resvd|Prf|Resvd| 1067 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1068 | Prefix Lifetime | 1069 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1070 | Prefix Length | | 1071 +-+-+-+-+-+-+-+-+ | 1072 | Destination Prefix (Variable Length) | 1073 . . 1074 . . 1075 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1077 Figure 7: DAG Destination Prefix 1079 The Destination Prefix suboption is used when the DAG root, or 1080 another node located inwards along the DAG on the path to the DAG 1081 root, needs to indicate that it offers connectivity to destination 1082 prefixes other than the default. This may be useful in cases where 1083 more than one LBR is operating within the LLN and offering 1084 connectivity to different administrative domains, e.g. a home network 1085 and a utility network. In such cases, upon observing the Destination 1086 Prefixes offered by a particular DAG, a node MAY decide to join 1087 multiple DAGs in support of a particular application. 1089 The Length is coded as the length of the suboption in octets, 1090 excluding the Type and Length fields. 1092 Prf is the Route Preference as in [RFC4191]. The reserved fields 1093 MUST be set to zero on transmission and MUST be ignored on receipt. 1095 The Prefix Lifetime is a 32-bit unsigned integer representing the 1096 length of time in seconds (relative to the time the packet is sent) 1097 that the Destination Prefix is valid for route determination. A 1098 value of all one bits (0xFFFFFFFF) represents infinity. A value of 1099 all zero bits (0x00000000) indicates a loss of reachability. 1101 The Prefix Length is an 16-bit unsigned integer that indicates the 1102 number of leading bits in the destination prefix. 1104 The Destination Prefix contains Prefix Length significant bits of the 1105 destination prefix. The remaining bits of the Destination Prefix, as 1106 required to complete the trailing octet, are set to 0. 1108 In the event that a DIO message may need to specify connectivity to 1109 more than one destination, the Destination Prefix suboption may be 1110 repeated. 1112 5.1.3.1.1.6. DAG Timer Configuration 1114 The DAG Timer Configuration suboption does not have any alignment 1115 requirements. Its format is as follows: 1117 0 1 2 3 1118 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 1119 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1120 | Type = 4 | Length | DIOIntDoubl. | 1121 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1122 | DIOIntMin. | 1123 +-+-+-+-+-+-+-+-+ 1125 Figure 8: DAG Timer Configuration 1127 The DAG Timer Configuration suboption is used to distribute 1128 configuration information for DAG Timer Operation through the DAG. 1129 The information communicated in this suboption is generally static 1130 and unchanging within the DAG, therefore it is not necessary to 1131 include in every DIO. This suboption MAY be included periodically by 1132 the DAG Root, and SHOULD be included in response to a unicast 1133 request, e.g. a DAG Information Solicitation (DIS) message. 1135 The Length is coded as 2. 1137 DIOIntervalDoublings is an 8-bit unsigned integer. Configured on the 1138 DAG root and used to configure the trickle timer governing when DIO 1139 message should be sent within the DAG. DIOIntervalDoublings is the 1140 number of times that the DIOIntervalMin is allowed to be doubled 1141 during the trickle timer operation. 1143 DIOIntervalMin is an 8-bit unsigned integer. Configured on the DAG 1144 root and used to configure the trickle timer governing when DIO 1145 message should be sent within the DAG. The minimum configured 1146 interval for the DIO trickle timer in units of ms is 1147 2^DIOIntervalMin. For example, a DIOIntervalMin value of 16ms is 1148 expressed as 4. 1150 5.1.4. Destination Advertisement Object (DAO) 1152 The Destination Advertisement Object (DAO) is used to propagate 1153 destination information inwards along the DAG. The RPL use of the 1154 DAO allows the nodes in the DAG to build up routing state for nodes 1155 contained in the sub-DAG in support of traffic flowing outward along 1156 the DAG. 1158 0 1 2 3 1159 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 1160 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1161 | DAO Sequence | InstanceID | DAO Rank | 1162 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1163 | DAO Lifetime | 1164 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1165 | Route Tag | 1166 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1167 | Prefix Length | RRCount | | 1168 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1169 | Prefix (Variable Length) | 1170 . . 1171 . . 1172 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1173 | Reverse Route Stack (Variable Length) | 1174 . . 1175 . . 1176 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1178 Figure 9: The Destination Advertisement Object (DAO) 1180 DAO Sequence: Incremented by the node that owns the prefix for each 1181 new DAO message for that prefix. 1183 InstanceID: 8-bit field indicating the topology instance associated 1184 with the DAG, as learned from the DIO. 1186 DAO Rank: Set by the node that owns the prefix and first issues the 1187 DAO message to its rank. 1189 DAO Lifetime: 32-bit unsigned integer. The length of time in 1190 seconds (relative to the time the packet is sent) that the 1191 prefix is valid for route determination. A value of all one 1192 bits (0xFFFFFFFF) represents infinity. A value of all zero 1193 bits (0x00000000) indicates a loss of reachability. 1195 Route Tag: 32-bit unsigned integer. The Route Tag may be used to 1196 give a priority to prefixes that should be stored. This may be 1197 useful in cases where intermediate nodes are capable of storing 1198 a limited amount of routing state. The further specification 1199 of this field and its use is under investigation. 1201 Prefix Length: Number of valid leading bits in the IPv6 Prefix. 1203 RRCount: 8-bit unsigned integer. This counter is used to count the 1204 number of entries in the Reverse Route Stack. A value of `0' 1205 indicates that no Reverse Route Stack is present. 1207 Prefix: Variable-length field containing an IPv6 address or a prefix 1208 of an IPv6 address. The Prefix Length field contains the 1209 number of valid leading bits in the prefix. The bits in the 1210 prefix after the prefix length (if any) are reserved and MUST 1211 be set to zero on transmission and MUST be ignored on receipt. 1213 Reverse Route Stack: Variable-length field containing a sequence of 1214 RRCount (possibly compressed) IPv6 addresses. A node that adds 1215 on to the Reverse Route Stack will append to the list and 1216 increment the RRCount. 1218 5.2. Conceptual Data Structures 1220 The RPL implementation MUST maintain the following conceptual data 1221 structures in support of DAG discovery: 1223 o A set of candidate neighbors 1225 o For each DAG: 1227 * A set of DAG parents and siblings 1229 5.2.1. Candidate Neighbors Data Structure 1231 The set of candidate neighbors is to be populated by neighbors that 1232 are discovered by the neighbor discovery mechanism and further 1233 qualified as statistically stable as per the mechanisms discussed in 1234 [I-D.ietf-roll-routing-metrics]. The candidate neighbors, and 1235 related metrics, should demonstrate stability/reliability beyond a 1236 certain threshold, and it is recommended that a local confidence 1237 value be maintained with respect to the neighbor in order to track 1238 this. Implementations MAY choose to bound the maximum size of the 1239 candidate neighbor set, in which case a local confidence value will 1240 assist in ordering neighbors to determine which ones should remain in 1241 the candidate neighbor set and which should be evicted. 1243 If Neighbor Unreachability Detection (NUD) determines that a 1244 candidate neighbor is no longer reachable, then it shall be removed 1245 from the candidate neighbor set. In the case that the candidate 1246 neighbor has associated states in the DAG parent set or active DA 1247 entries, then the removal of the candidate neighbor shall be 1248 coordinated with tearing down these states. All provisioned routes 1249 associated with the candidate neighbor should be removed. 1251 5.2.2. Directed Acyclic Graphs (DAGs) Data Structure 1253 At a given point of time, a DAG Iteration is uniquely identified by 1254 the tuple (DagID, InstanceID, DAGSequenceNumber) where a change in 1255 the sequence denotes the iteration of a given DAG over time. When a 1256 single device is capable to root multiple DAGs in support of an 1257 application need for multiple optimization objectives it MUST produce 1258 a different and unique (DagID, InstanceID) pair for each of the 1259 multiple DAGs. 1261 For each DAG that a node is, or may become, a member of, the 1262 implementation MUST keep a DAG table with the following entries: 1264 o InstanceID 1266 o DAGID 1268 o DAGSequenceNumber 1270 o DAG Metric Container, including DAGObjectiveCodePoint 1272 o A set of Destination Prefixes offered inwards along the DAG 1274 o A set of DAG parents and siblings 1276 o A timer to govern the sending of DIO messages for the DAG 1278 When a DAG is discovered for which no DAG data structure is 1279 instantiated, and the node wants to join, then the DAG data structure 1280 is instantiated. 1282 When the DAG parent set is depleted (i.e. the last DAG is removed), 1283 then the DAG data structure SHOULD be suppressed after the expiration 1284 of an implementation-specific local timer. An implementation SHOULD 1285 delay before deallocating the DAG data structure in order to observe 1286 that the DAGSequenceNumber has incremented should any new DAG parents 1287 appear for the DAG. 1289 5.2.2.1. DAG Parents/Siblings Structure 1291 When the DAG is self-rooted, the set of DAG parents/siblings is 1292 empty. 1294 In all other cases, for each node in the set, the implementation MUST 1295 keep a record of: 1297 o a reference to the neighboring device which is the DAG parent or 1298 sibling 1300 o a record of most recent information taken from the DAG Information 1301 Object last processed from the DAG parent 1303 DAG parents may be ordered, according to the OF. When ordering DAG 1304 parents, in consultation with the OF, the most preferred DAG parent 1305 may be identified. All current DAG parents must have a rank less 1306 than self. All current DAG siblings must have a rank equal to self. 1308 When nodes are added to or removed from the DAG set the most 1309 preferred DAG parent may have changed. The role of all the nodes in 1310 the list should be reevaluated. In particular, any nodes having a 1311 rank greater than self after such a change must be evicted from the 1312 set. 1314 An implementation may choose to keep these records as an extension of 1315 the Default Router List (DRL). 1317 5.3. DAG Rank 1319 Based on the selection of DAG Parents, the metrics conveyed by the 1320 most preferred DAG parent, the nodes own metrics and configuration, 1321 and a related function defined by the OF, a node will be able to 1322 compute a value for its rank as a consequence of selecting a most 1323 preferred DAG parent. 1325 The rank value feeds back into the DAG parent selection according to 1326 a loop-avoidance strategy. Once a DAG parent has been added, and a 1327 rank value for the node within the DAG has been computed, the nodes 1328 further options with regard to DAG parent selection and movement 1329 within the DAG are restricted in favor of loop avoidance. 1331 It is important to note that the DAG Rank is not itself a metric, 1332 although its value is derived from and influenced by the use of 1333 metrics to select DAG parents and take up a position in the DAG. The 1334 only aim of the rank is to inform loop avoidance and detection. 1336 The computation of the DAG Rank MUST be done in such a way so as to 1337 maintain the following properties for any nodes M and N that are 1338 neighbors in the LLN: 1340 DAGRank(M) is less than DAGRank(N): In this case, M is probably 1341 located in a more preferred position than N in the DAG with 1342 respect to the metrics and optimizations defined by the 1343 objective code point. In any fashion, Node M may safely be a 1344 DAG parent for Node N without risk of creating a loop. 1345 Further, for a node N, all parents in the DAG parent set must 1346 be of rank less than self's DAGRank(N). In other words, the 1347 rank presented by a node N MUST be greater (deeper) than that 1348 presented by any of its parents. 1350 DAGRank(M) equals DAGRank(N): In this case M and N are located 1351 positions of relatively the same optimality within the DAG. 1352 In some cases, Node M may be used as a successor by Node N, 1353 but with related chance of creating a loop that must be 1354 detected and broken by some other means. 1356 DAGRank(M) is greater than DAGRank(N): In this case, then node M is 1357 located in a less preferred position than N in the DAG with 1358 respect to the metrics and optimizations defined by the 1359 objective code point. Further, Node (M) may in fact be in 1360 Node (N)'s sub-DAG. There is a higher risk to Node (N) 1361 selecting Node (M) as a DAG parent, as such a selection may 1362 create a loop. 1364 As an example, the DAG Rank could be computed in such a way so as to 1365 closely track ETX when the objective function is to minimize ETX, or 1366 latency when the objective function is to minimize latency, or in a 1367 more complicated way as appropriate to the objective code point being 1368 used within the DAG. 1370 5.4. DAG Discovery and Maintenance 1372 DAG discovery locates the nearest sink (aka root), as determined 1373 according to some metrics and constraints, and forms a Directed 1374 Acyclic Graph towards that sink, by identifying a set of DAG parents. 1375 During this process DAG discovery also identifies siblings, which may 1376 be used later to provide additional path diversity towards the DAG 1377 root. DAG discovery enables nodes to implement different policies 1378 for selecting their DAG parents in the DAG by using implementation 1379 specific policy functions. DAG discovery specifies a set of rules to 1380 be followed by all implementations in order to ensure interoperation. 1381 DAG discovery also standardizes the format that is used to advertise 1382 the most common information that is used in order to select DAG 1383 parents. 1385 One of these information, the DAG rank, is used by DAG discovery to 1386 provide loop avoidance even if nodes implement different policies. 1387 The DAG Rank is computed as specified by the OF in use by the DAG, 1388 demonstrating the properties described in Section 5.3. The rank 1389 should be computed in such a way so as to provide a comparable basis 1390 with other nodes which may not use the same metric at all. 1392 The DAG discovery procedures take into account a number of factors, 1393 including: 1395 o RPL rules for loop avoidance based on DAGs and ranks 1397 o The Objective Function 1399 o The advertised metrics 1401 o Local policy functions (e.g. a bounded number of candidate 1402 neighbors). 1404 5.4.1. DAG Discovery Rules 1406 In order to organize and maintain loopless structure, the DAG 1407 discovery implementation in the nodes MUST obey to the following 1408 rules and definitions: 1410 5.4.1.1. DAGs 1412 1. DAG discovery instantiates LLN topologies that are each optimized 1413 for specific constraints and goals. A topology assumes the shape 1414 of a DAG, and a DAG Instance is uniquely identified by its 1415 instanceID. 1417 2. For reasons of scalability and operations of the protocol, a DAG 1418 Instance is partitioned into a set of DAGs rooted at a 1419 destination, aka Destination Oriented DAGs. A destination is 1420 uniquely identified by a DAGID so a DAG rooted at a destination 1421 is uniquely identified by the pair (InstanceID, DAGID). 1423 3. A Destination Oriented DAG is periodically reconstructed from the 1424 root, by incrementing a DAGSequenceNumber. An Iteration of a 1425 Destination Oriented DAG is thus uniquely identified by the tuple 1426 (InstanceID, DAGID, DAGSequenceNumber). Through this document, 1427 the graph formed by this iterative process is referred to as the 1428 DAG Iteration, or in short, the DAG. 1430 4. The rank is defined within the scope of a DAG Iteration as an 1431 abstract coordinate to compare the relative position of nodes and 1432 ensure forward progress of the traffic. 1434 5. A node MUST belong at most to one DAG Iteration per InstanceID 1435 and MUST select all its parents and siblings within that same DAG 1436 Iteration. 1438 5.4.1.2. DAG Sequence Number 1440 1. The DAGSequenceNumber is incremented by the root and flooded 1441 through DIOs. 1443 2. The root floods a new DAGSequenceNumber periodically, at a rate 1444 that depends on the deployment. This rate can be set to 0 if 1445 other methods such as loop detection are considered sufficient to 1446 solve the routing issues in that deployment. 1448 3. The root MAY also flood a new DAGSequenceNumber on-demand. The 1449 details of the mechanism to signal the root to do so are to be 1450 specified in a future revision of this document. 1452 4. A parent that advertises the new DAGSequenceNumber can not 1453 possibly belong to the sub-DAG of a node that still advertises an 1454 older DAGSequenceNumber. The node MAY thus attach to that parent 1455 regardless of the relative rank, and this situation is equivalent 1456 to jumping onto a different Destination Oriented DAG. 1458 5. Thus, as a new DAGSequenceNumber spreads, a new DAG Iteration 1459 forms that supersedes the previous one. During a 1460 DAGSequenceNumber transition, a node MAY decide to forward 1461 packets via 'future parents' that belong to the same Destination 1462 Oriented DAG (same InstanceID and DagID), but a more recent 1463 (incremented) DAGSequenceNumber. 1465 5.4.1.3. DAG Root 1467 1. A node that does not have any DAG parent MAY become the root of 1468 its own floating DAG. It's rank is ROOT_RANK. 1470 2. A (non-LLN) router is considered connected to a grounded 1471 infrastructure at rank BASE_RANK. A LLN node that is attached to 1472 such an infrastructure router is the DAG root of its own grounded 1473 DAG. It's rank is ROOT_RANK. 1475 3. In a deployment that uses a backbone link to federate a number of 1476 LLN roots, it is possible to run RPL over the backbone and use 1477 one router as a backbone root. The backbone root exposes a rank 1478 of BASE_RANK over the backbone. All the LLN roots that are 1479 parented to that backbone root, including the backbone root if it 1480 also serves as LLN root, expose a rank of ROOT_RANK over the LLN 1481 and act as multiple roots for a same DAG, coordinated by the 1482 backbone root. 1484 4. The DAG root exposes the DAG in the DIO message and LLN nodes 1485 propagate the DIO message outwards along the DAG. 1487 5.4.1.4. Moving Inside a DAG 1489 1. A node moves when it changes its parent selection within the same 1490 DAG Iteration. When a node moves (within its DAG) in a fashion 1491 that cause its rank to decrease, the node MUST abandon all 1492 parents and siblings with a rank larger than self, and MAY adopt 1493 as siblings nodes with the same rank. 1495 2. A node MAY move at any time, with no delay, within its DAG when 1496 the move does not cause the node to increase its own DAG rank, as 1497 per the rank calculation indicated by the OF. 1499 3. A node MUST NOT move outwards along a DAG that it is attached to, 1500 causing the DAG rank to increase. If a node cannot stay within 1501 the DAG without a rank increase, then it MUST poison its routes 1502 as described in Section 5.4.1.6. 1504 4. When DIO messages are received from other routers located at 1505 lesser rank in the same DAG, those routers are eligible for 1506 consideration as DAG parents. DIO messages received from other 1507 routers located at the same rank in the same DAG may be 1508 considered as coming from siblings. DIO messages that are 1509 received from other routers located at greater rank within the 1510 same DAG might cause greedy behaviors and loops; such a DIO is 1511 ignored unless: 1513 1. The DIO comes from an existing parent or sibling; in which 1514 case that parent must be removed. 1516 2. The DIO comes from a node that has better OF ratings than any 1517 parent known at this point; in that case, this potential 1518 parent MAY be remembered in order to jump at a better 1519 position when the next sequence is flooded. 1521 5.4.1.5. Jumping Onto Another DAG 1523 1. A node jumps when it performs a new parent selection whereby its 1524 DAG Iteration changes within the same DAG Instance. When a node 1525 jumps onto a new DAG Iteration, it MUST abandon all parents and 1526 siblings from its previous position. 1528 2. A node MAY jump from its current DAG onto any other DAG that 1529 provides service for the same InstanceID if it is preferred by 1530 the OF, for example for reasons such as connectivity, configured 1531 preference, free medium time, size, security, bandwidth, DAG 1532 rank, or whatever metrics the LLN uses. This is allowed 1533 regardless of the rank that the node reaches in the new DAG. 1535 3. A node that jumps should attempt to transmit all the packets 1536 received as part of the previous DAG along the previous DAG. In 1537 other words, it should switch the parent set only after the 1538 outstanding packet queue of packets received prior to announcing 1539 the jump is exhausted. 1541 4. Jumping back onto a previous DAG is equivalent to moving inside 1542 that DAG and obeys the same rules. To satisfy this, a node 1543 detaching from a DAG SHOULD remember its DAG as identified by the 1544 tuple (InstanceID, DagID, DAGSequenceNumber) as well as its rank 1545 within that DAG for long as that DAG exists. 1547 5.4.1.6. Poisoning a Broken Path 1549 1. A node SHOULD poison its inwards routes when it looses all of its 1550 current feasible parents, i.e. the set of DAG parents becomes 1551 depleted, and it can not jump onto an alternate DAG. 1553 2. In order to poison its inwards routes, a node MAY stay at its 1554 position within its DAG (that is maintain its InstanceID, DagID, 1555 DAGSequenceNumber and Rank) but it SHOULD immediately advertise a 1556 rank of INFINITE_RANK in a DIO so as to force all its children to 1557 remove it from their parent list and try an alternate path. The 1558 node SHOULD then wait for a new DAG Iteration (DAGSequenceNumber 1559 increment) before resuming its operation in the same Destination 1560 Oriented DAG. 1562 3. Alternatively, a node MAY detach from its DAG. A node that 1563 detaches becomes root of its own floating DAG and MUST 1564 immediately advertise its new situation in a DIO. 1566 4. Either way, the route poisoning will recursively be flooded 1567 throughout the impacted sub-DAG as children lose their last 1568 parent in the original DAG. 1570 5. The loss of a DIO message may interrupt the flooding. This can 1571 be compensated by cheer repetition through the trickle algorithm. 1572 If that also fails, packet loops will be prevented by the 1573 detection mechanism described in Section 5.11. 1575 5.4.1.7. Following a Parent 1577 1. If a node that receives a DIO from one of its DAG parents 1578 indicating that the parent has left the DAG, it may either follow 1579 that parent or stay in its current DAG through an alternate DAG 1580 parent if that is possible. 1582 2. If a DAG parent increases its rank such that the node rank would 1583 have to change, and if the node does not wish to follow (e.g. it 1584 has alternate options), then the DAG parent SHOULD be evicted 1585 from the DAG parent set. If the DAG parent is the last in the 1586 DAG parent set, then the node SHOULD chose to follow it. 1588 5.4.1.8. DAG Inconsistency 1590 1. When a node detects or causes a DAG inconsistency, as described 1591 in Section 5.4.4.2, then the node SHOULD send an unsolicited DIO 1592 message to its one-hop neighbors. The DIO is updated to 1593 propagate the new DAG information. Such an event MUST also cause 1594 the trickle timer governing the periodic sending of DIO messages 1595 to be reset. 1597 5.4.2. Reception and Processing of DIO messages 1599 When an DIO message is received from a source device named SRC, the 1600 receiving node must first determine whether or not the DIO message 1601 should be accepted for further processing, and subsequently present 1602 the DIO message for further processing if eligible. 1604 1. If the DIO message is malformed, then the DIO message is not 1605 eligible for further processing and is silently discarded. A RPL 1606 implementation MAY log the reception of a malformed DIO message. 1608 2. If SRC is not a member of the candidate neighbor set, then the 1609 DIO is not eligible for further processing. (Further evaluation/ 1610 confidence of this neighbor is necessary) 1612 3. If the DIO message advertises a DAG that the node is already a 1613 member of, then: 1615 * If the rank of SRC as reported in the DIO message is lesser 1616 than that of the node within the DAG, then the DIO message 1617 MUST be considered for further processing. 1619 * If the rank of SRC as reported in the DIO message is equal to 1620 that of the node within the DAG, then SRC is marked as a 1621 sibling and the DIO message is not eligible for further 1622 processing. 1624 * If the rank of SRC as reported in the DIO message is higher 1625 than that of the node within the DAG, and SRC is not a DAG 1626 parent, then the DIO message MUST NOT be considered for 1627 further processing 1629 4. Even if not processed further, information from a DIO might be 1630 remembered for instance if SRC is preferable to the current 1631 parents per the OF selection process. 1633 5. If SRC is a DAG parent for any other DAG that the node is 1634 attached to, then the DIO message MUST be considered for further 1635 processing (the DAG parent may have jumped). 1637 6. If the DIO message advertises a DAG that offers a better (new or 1638 alternate) solution to an optimization objective desired by the 1639 node, then the DIO message MUST be considered for further 1640 processing. 1642 5.4.2.1. Overview of DIO Message Processing 1644 If the received DIO message is for a new/alternate DAG: 1646 If the node has sent an DIO message within the risk window as 1647 described in Section 5.8 then a collision has occurred; do not 1648 process the DIO message any further. 1650 If the SRC node is also a DAG parent for another DAG that the 1651 node is a member of, and if the new/alternate DAG is the same 1652 InstanceID as the other DAG, then the DAG parent is known to 1653 have jumped. 1655 Remove SRC as a DAG parent from the other DAG 1657 If the other DAG is now empty of candidate parents, then 1658 prepare to directly follow SRC into the new DAG by adding it 1659 as a DAG parent for the new DAG, else ignore the DIO message 1660 (do not follow the parent). 1662 Instantiate a data structure for the new/alternate DAG if 1663 necessary 1665 If the new/alternate DAG offers a better solution to the 1666 optimization objectives, then jump: copy the DIO information 1667 place the neighbor into the DAG parent set. 1669 If the DIO message is for a known/existing DAG: 1671 Process the DIO message as per the rules in Section 5.4 1673 As DIO messages are received from candidate neighbors, the neighbors 1674 may be promoted to DAG parents by following the rules of DAG 1675 discovery as described in Section 5.4. When a node places a neighbor 1676 into the DAG Parent set, the node becomes attached to the DAG through 1677 the new parent node. 1679 In the DAG discovery implementation, the most preferred parent should 1680 be used to restrict which other nodes may become DAG parents. Some 1681 nodes in the DAG parent set may be of a rank less than or equal to 1682 the most preferred DAG parent. (This case may occur, for example, if 1683 an energy constrained device is at a lesser rank but should be 1684 avoided as per an optimization objective, resulting in a more 1685 preferred parent at a greater rank). 1687 5.4.3. DIO Transmission 1689 Each node maintains a timer that governs when to multicast DIO 1690 messages. This timer is implemented as a trickle timer operating 1691 over a variable interval. Trickle timers are further detailed in 1692 Section 5.4.4. The governing parameters for the timer should be 1693 configured consistently across the DAG, and are provided by the DAG 1694 root in the DIO message. In addition to periodic DIO messages, each 1695 node may respond to a DIS message with a DIO message. 1697 o When a node detects an inconsistency, it SHOULD reset the interval 1698 of the trickle timer to a minimum value, causing DIO messages to 1699 be emitted more frequently as part of a strategy to quickly 1700 correct the inconsistency. Such inconsistencies may be, for 1701 example, an update to a key parameter (e.g. sequence number) in 1702 the DIO message or a loop detected when a node located inwards 1703 along the DAG forwards traffic outwards. Inconsistencies are 1704 further detailed in Section 5.4.4.2. 1706 o When a node enters a mode of consistent operation within a DAG, 1707 i.e. DIO messages from its DAG parents are consistent and no 1708 other inconsistencies are detected, it may begin to open up the 1709 interval of the trickle timer towards a maximum value, causing DIO 1710 messages to be emitted less frequently, thus reducing network 1711 maintenance overhead and saving energy consumption. 1713 o When a node is initialized, it MAY be configured to remain silent 1714 and not multicast any DIO messages until it has encountered and 1715 joined a DAG (perhaps initially probing for a nearby DAG with an 1716 DIS message). Alternately, it may choose to root its own floating 1717 DAG and begin multicasting DIO messages using a default trickle 1718 configuration. The second case may be advantageous if it is 1719 desired for independent nodes to begin aggregating into scattered 1720 floating DAGs in the absence of a grounded node, for example in 1721 support of LLN installation and commissioning. 1723 Note that if multiple DAG roots are participating in the same DAG, 1724 i.e. offering DIO messages with the same DAGID, then they must 1725 coordinate with each other to ensure that their DIO messages are 1726 consistent when they emit DIO messages. In particular the Sequence 1727 number must be identical from each DAG root, regardless of which of 1728 the multiple DAG roots issues the DIO message, and changes to the 1729 Sequence number should be issued at the same time. The specific 1730 mechanism of this coordination, e.g. along a non-LLN network between 1731 DAG roots, is beyond the scope of this specification. 1733 5.4.4. Trickle Timer for DIO Transmission 1735 RPL treats the construction of a DAG as a consistency problem, and 1736 uses a trickle timer [Levis08] to control the rate of control 1737 broadcasts. 1739 For each DAG that a node is part of, the node must maintain a single 1740 trickle timer. The required state contains the following conceptual 1741 items: 1743 I: The current length of the communication interval 1745 T: A timer with a duration set to a random value in the range 1746 [I/2, I] 1748 C: Redundancy Counter 1750 I_min: The smallest communication interval in milliseconds. This 1751 value is learned from the DIO message as (2^DIOIntervalMin)ms. 1752 The default value is DEFAULT_DIO_INTERVAL_MIN. 1754 I_doublings: The number of times I_min should be doubled before 1755 maintaining a constant rate, i.e. I_max = I_min * 1756 2^I_doublings. This value is learned from the DIO message as 1757 DIOIntervalDoublings. The default value is 1758 DEFAULT_DIO_INTERVAL_DOUBLINGS. 1760 5.4.4.1. Resetting the Trickle Timer 1762 The trickle timer for a DAGID is reset by: 1764 1. Setting I_min and I_doublings to the values learned from the DIO 1765 message. 1767 2. Setting C to zero. 1769 3. Setting I to I_min. 1771 4. Setting T to a random value as described above. 1773 5. Restarting the trickle timer to expire after a duration T 1775 When node learns about a DAG through a DIO message and makes the 1776 decision to join it, it initializes the state of the trickle timer by 1777 resetting the trickle timer and listening. Each time it hears a 1778 consistent DIO message for this DAG from a DAG parent, it MAY 1779 increment C. 1781 When the timer fires at time T, the node compares C to the redundancy 1782 constant, DEFAULT_DIO_REDUNDANCY_CONSTANT. If C is less than that 1783 value, the node generates a new DIO message and multicasts it. When 1784 the communication interval I expires, the node doubles the interval I 1785 so long as it has previously doubled it fewer than I_doubling times, 1786 resets C, and chooses a new T value. 1788 5.4.4.2. Determination of Inconsistency 1790 The trickle timer is reset whenever an inconsistency is detected 1791 within the DAG, for example: 1793 o The node joins a new DAGID 1795 o The node moves within a DAGID 1797 o The node receives a modified DIO message from a DAG parent 1799 o A DAG parent forwards a packet intended to move inwards, 1800 indicating an inconsistency and possible loop. 1802 o A metric communicated in the DIO message is determined to be 1803 inconsistent, as according to a implementation specific path 1804 metric selection engine. 1806 o The rank of a DAG parent has changed. 1808 5.5. DAG Sequence Number Increment 1810 The DAG root makes the sole determination of when to revise the 1811 DAGSequenceNumber by incrementing it upwards. When the 1812 DAGSequenceNumber is increased an inconsistency results, causing DIO 1813 messages to be sent back outwards along the DAG to convey the change. 1814 The degree to which this mechanism is relied on may be determined by 1815 the implementation- on one hand it may serve as a periodic heartbeat, 1816 refreshing the DAG states, and on the other hand it may result in a 1817 constant steady-state control cost overhead which is not desirable. 1819 Some implementations may provide an administrative interface, such as 1820 a command line, at the DAG root whereby the DAGSequenceNumber may be 1821 caused to increment in response to some policy outside of the scope 1822 of RPL. 1824 Other implementations may make use of a periodic timer to 1825 automatically increment the DAGSequenceNumber, resulting in a 1826 periodic DAG iteration at a rate appropriate to the application and 1827 implementation. Other automated mechanisms to determine 1828 DAGSequenceNumber increments are also possible as appropriate to a 1829 deployment. 1831 5.6. DAG Selection 1833 The DAG selection is implementation and algorithm dependent. Nodes 1834 SHOULD prefer to join DAGs for InstanceIDs advertising OCPs and 1835 destinations compatible with their implementation specific 1836 objectives. In order to limit erratic movements, and all metrics 1837 being equal, nodes SHOULD keep their previous selection. Also, nodes 1838 SHOULD provide a means to filter out a candidate parent whose 1839 availability is detected as fluctuating, at least when more stable 1840 choices are available. 1842 When connection to a fixed network is not possible or preferable for 1843 security or other reasons, scattered DAGs MAY aggregate as much as 1844 possible into larger DAGs in order to allow connectivity within the 1845 LLN. 1847 A node SHOULD verify that bidirectional connectivity and adequate 1848 link quality is available with a candidate neighbor before it 1849 considers that candidate as a DAG parent. 1851 5.7. Administrative rank 1853 When the DAG is formed under a common administration, or when a node 1854 performs a certain role within a community, it might be beneficial to 1855 associate a range of acceptable rank with that node. For instance, a 1856 node that has limited battery should be a leaf unless there is no 1857 other choice, and may then augment the rank computation specified by 1858 the OF in order to expose an exaggerated rank. 1860 5.8. Collision 1862 A race condition occurs if 2 nodes send DIO messages at the same time 1863 and then attempt to join each other. This might happen, for example, 1864 between nodes which act as DAG root of their own DAGs. In order to 1865 detect the situation, LLN Nodes time stamp the sending of DIO 1866 message. Any DIO message received within a short link-layer- 1867 dependent period introduces a risk. It is up to the implementation 1868 to define the duration of the risk window. 1870 There is risk of a collision when a node receives and processes a DIO 1871 within the risk window. For example, it may occur that two nodes are 1872 associated with different DAGs and near-simultaneously send DIO 1873 messages, which are received and processed by both, and possibly 1874 result in both nodes simultaneously deciding to attach to each other. 1875 As a remedy, in the face of a potential collision, as determined by 1876 receiving a DIO within the risk window, the DIO message is not 1877 processed. It is expected that subsequent DIOs would not cross. 1879 5.9. Guidelines for Objective Functions 1881 5.9.1. Objective Function 1883 An Objective Function (OF) allows for the selection of a DAG to join, 1884 and a number of peers in that DAG as parents. The OF is used to 1885 compute an ordered list of parents. The OF is also responsible to 1886 compute the rank of the device within the DAG. 1888 The Objective Function is specified in the DIO message within a DAG 1889 Metric Container using an Objective Code Point (OCP), as specified in 1890 [I-D.ietf-roll-routing-metrics], and indicates the method that must 1891 be used to compute the DAG (e.g. "minimize the path cost using the 1892 ETX metric and avoid `Blue' links"). The Objective Code Points are 1893 specified in [I-D.ietf-roll-routing-metrics]. This document 1894 specifies an Objective Function, OF0, in support of default 1895 operation. In the case where the DIO does not include an OCP 1896 specification in the DAG Metric Container, OF0 MAY be presumed. 1898 Most Objective Functions are expected to follow the same abstract 1899 behavior: 1901 o The parent selection is triggered each time an event indicates 1902 that a potential next hop information is updated. This might 1903 happen upon the reception of a DIO message, a timer elapse, or a 1904 trigger indicating that the state of a candidate neighbor has 1905 changed. 1907 o An OF scans all the interfaces on the device. Although there may 1908 typically be only one interface in most application scenarios, 1909 there might be multiple of them and an interface might be 1910 configured to be usable or not for RPL operation. An interface 1911 can also be configured with a preference or dynamically learned to 1912 be better than another by some heuristics that might be link-layer 1913 dependent and are out of scope. Finally an interface might or not 1914 match a required criterion for an Objective Function, for instance 1915 a degree of security. As a result some interfaces might be 1916 completely excluded from the computation, while others might be 1917 more or less preferred. 1919 o An OF scans all the candidate neighbors on the possible interfaces 1920 to check whether they can act as a router for a DAG. There might 1921 be multiple of them and a candidate neighbor might need to pass 1922 some validation tests before it can be used. In particular, some 1923 link layers require experience on the activity with a router to 1924 enable the router as a next hop. 1926 o An OF computes self's rank by adding the step of rank to that 1927 candidate to the rank of that candidate. The step of rank is 1928 computed by estimating the link as follows: 1930 * The step of rank might vary from 1 to 16. 1932 + 1 indicates a unusually good link, for instance a link 1933 between powered devices in a mostly battery operated 1934 environment. 1936 + 4 indicates a `normal'/typical link, as qualified by the 1937 implementation. 1939 + 16 indicates a link that can hardly be used to forward any 1940 packet, for instance a radio link with quality indicator or 1941 expected transmission count that is close to the acceptable 1942 threshold. 1944 * Candidate neighbors that would cause self's rank to increase 1945 are ignored 1947 o Candidate neighbors that advertise an OF incompatible with the set 1948 of OF specified by the policy functions are ignored. 1950 o As it scans all the candidate neighbors, the OF keeps the current 1951 best parent and compares its capabilities with the current 1952 candidate neighbor. The OF defines a number of tests that are 1953 critical to reach the objective. A test between the routers 1954 determines an order relation. 1956 * If the routers are roughly equal for that relation then the 1957 next test is attempted between the routers, 1959 * Else the best of the 2 becomes the current best parent and the 1960 scan continues with the next candidate neighbor 1962 * Some OFs may include a test to compare the ranks that would 1963 result if the node joined either router 1965 o When the scan is complete, the preferred parent is elected and 1966 self's rank is computed as the preferred parent rank plus the step 1967 in rank with that parent. 1969 o Other rounds of scans might be necessary to elect alternate 1970 parents and siblings. In the next rounds: 1972 * Candidate neighbors that are not in the same DAG are ignored 1974 * Candidate neighbors that are of greater rank than self are 1975 ignored 1977 * Candidate neighbors of an equal rank to self (siblings) are 1978 ignored 1980 * Candidate neighbors of a lesser rank than self (non-siblings) 1981 are preferred 1983 5.9.2. Objective Function 0 (OF0) 1985 This document specifies a default objective function, called OF0, 1986 indicated by an OCP value of 0x0000. OF0 is the default objective 1987 function of RPL, and can be used if allowed by the policy of the 1988 processing node when the OF indicated in the DIO message is unknown 1989 to the node. If not allowed, then the DIO message is simply ignored 1990 and not processed by the node. OF0 is notable in that it does not 1991 use physical metrics as described in [I-D.ietf-roll-routing-metrics], 1992 but is only based on abstract information from the DIO message such 1993 as rank and administrative preference. 1995 OF0 favors connectivity. That is, the Objective Function is designed 1996 to find the nearest sink into a 'grounded' topology, and if there is 1997 none then join any network per order of administrative preference. 1998 The metric in use is the rank. 2000 OF0 selects a preferred parent and a backup next hop if one is 2001 available. The backup next hop might be a parent or a sibling. All 2002 the traffic is routed via the preferred parent. When the link 2003 conditions do not let a packet through to the preferred parent, the 2004 packet is passed to the backup next hop. 2006 The step of rank is 4 for each hop. 2008 5.9.2.1. Selection of the Preferred Parent 2010 As it scans all the candidate neighbors, OF0 keeps the parent that is 2011 the best for the following criteria (in order): 2013 1. The interface must be usable and any administrative preference 2014 associated with the interface applies first. 2016 2. A candidate that would cause the node to augment the rank in the 2017 current DAG is not considered. 2019 3. A router that has been validated as usable, e.g. with a local 2020 confidence that has exceeded some pre-configured threshold, is 2021 better. 2023 4. If none are grounded then a DAG with a more preferred 2024 administrative preference (DAGPreference) is better. 2026 5. A router that offers connectivity to a grounded DAG is better. 2028 6. A lesser resulting rank is better. 2030 7. A DAG for which there is an alternate parent is better. This 2031 check is optional. It is performed by computing the backup next 2032 hop while assuming that this router won. 2034 8. The DAG that was in use already is preferred. 2036 9. The preferred parent that was in use already is better. 2038 10. A router that has announced a DIO message more recently is 2039 preferred. 2041 5.9.2.2. Selection of the Backup Next Hop 2043 o The interface must be usable and the administrative preference (if 2044 any) applies first. 2046 o The preferred parent is ignored. 2048 o Candidate neighbors that are not in the same DAG are ignored. 2050 o Candidate neighbors with a higher rank are ignored. 2052 o Candidate neighbors of a better rank than self (non-siblings) are 2053 preferred. 2055 o A router that has been validated as usable, e.g. with a local 2056 confidence that has exceeded some pre-configured threshold, is 2057 better. 2059 o The router with a better router preference wins. 2061 o The backup next hop that was in use already is better. 2063 5.10. Establishing Routing State Outward Along the DAG 2065 The destination advertisement mechanism supports the dissemination of 2066 routing state required to support traffic flows outward along the 2067 DAG, from the DAG root toward nodes. 2069 As a result of destination advertisement operation: 2071 o DAG discovery establishes a DAG oriented toward a DAG root along 2072 which inward routes toward the DAG root are set up. 2074 o Destination advertisement establishes outward routes along the 2075 DAG. Such paths consist of: 2076 * Hop-By-Hop routing state within islands of `stateful' nodes. 2077 * Source Routing `bridges' across nodes that do not retain state. 2079 Destinations disseminated with the destination advertisement 2080 mechanism may be prefixes, individual hosts, or multicast listeners. 2081 The mechanism supports nodes of varying capabilities as follows: 2083 o When nodes are capable of storing routing state, they may inspect 2084 destination advertisements and learn hop-by-hop routing state 2085 toward destinations by populating their routing tables with the 2086 routes learned from nodes in their sub-DAG. In this process they 2087 may also learn necessary piecewise source routes to traverse 2088 regions of the LLN that do not maintain routing state. They may 2089 perform route aggregation on known destinations before emitting 2090 Destination Advertisements. 2092 o When nodes are incapable of storing routing state, they may 2093 forward destination advertisements, recording the reverse route as 2094 the go in order to support the construction of piecewise source 2095 routes. 2097 Nodes that are capable of storing routing state, and finally the DAG 2098 roots, are able to learn which destinations are contained in the sub- 2099 DAG below the node, and via which next-hop neighbors. The 2100 dissemination and installation of this routing state into nodes 2101 allows for Hop-By-Hop routing from the DAG root outwards along the 2102 DAG. The mechanism is further enhance by supporting the construction 2103 of source routes across stateless `gaps' in the DAG, where nodes are 2104 incapable of storing additional routing state. An adaptation of this 2105 mechanism allows for the implementation of loose-source routing. 2107 A special case, the reception of a destination advertisement 2108 addressed to a link-local multicast address, allows for a node to 2109 learn destinations directly available from its one-hop neighbors. 2111 A design choice behind advertising routes via destination 2112 advertisements is not to synchronize the parent and children 2113 databases along the DAG, but instead to update them regularly to 2114 recover from the loss of packets. The rationale for that choice is 2115 time variations in connectivity across unreliable links. If the 2116 topology can be expected to change frequently, synchronization might 2117 be an excessive goal in terms of exchanges and protocol complexity. 2118 The approach used here results in a simple protocol with no real 2119 peering. The destination advertisement mechanism hence provides for 2120 periodic updates of the routing state, as cued by occasional RAs and 2121 other mechanisms, similarly to other protocols such as RIP [RFC2453]. 2123 5.10.1. Destination Advertisement Operation 2125 5.10.1.1. Overview 2127 According to implementation specific policy, a subset or all of the 2128 feasible parents in the DAG may be selected to receive prefix 2129 information from the destination advertisement mechanism. This 2130 subset of DAG parents shall be designated the set of DA parents. 2132 As DAO messages for particular destinations move inwards along the 2133 DAG, a sequence counter is used to guarantee their freshness. The 2134 sequence counter is incremented by the source of the DAO message (the 2135 node that owns the prefix, or learned the prefix via some other 2136 means), each time it issues a DAO message for its prefix. Nodes that 2137 receive the DAO message and, if scope allows, will be forwarding a 2138 DAO message for the unmodified destination inwards along the DAG, 2139 will leave the sequence number unchanged. Intermediate nodes will 2140 check the sequence counter before processing a DAO message, and if 2141 the DAO is unchanged (the sequence counter has not changed), then the 2142 DAO message will be discarded without additional processing. 2143 Further, if the DAO message appears to be out of synch (the sequence 2144 counter is 2 or more behind the present value) then the DAO state is 2145 considered to be stale and may be purged, and the DAO message is 2146 discarded. A depth is also added for tracking purposes; the depth is 2147 incremented at each hop as the DAO message is propagated up the DAG. 2149 Nodes that are storing routing state may use the depth to determine 2150 which possible next-hops for the destination are more optimal. 2152 If destination advertisements are activated in the DIO message as 2153 indicated by the `D' bit, the node sends unicast destination 2154 advertisements to one of its DA parents, that is selected as most 2155 favored for incoming outwards traffic. The node only accepts unicast 2156 destination advertisements from any nodes but those contained in the 2157 DA parent subset. 2159 Receiving a DIO message with the `D' destination advertisement bit 2160 set from a DAG parent stimulates the sending of a delayed destination 2161 advertisement back, with the collection of all known prefixes (that 2162 is the prefixes learned via destination advertisements for nodes 2163 lower in the DAG, and any connected prefixes). If the Destination 2164 Advertisement Supported (A) bit is set in the DIO message for the 2165 DAG, then a destination advertisement is also sent to a DAG parent 2166 once it has been added to the DA parent set after a movement, or when 2167 the list of advertised prefixes has changed. 2169 A node that modifies its DAG Parent set may set the `D' bit in 2170 subsequent DIO propagation in order to trigger destination 2171 advertisements to be updated to its DAG Parents and other inward 2172 nodes on the DAG. Additional recommendations and guidelines 2173 regarding the use of this mechanism are still under consideration and 2174 will be elaborated in a future revision of this specification. 2176 Destination advertisements may advertise positive (prefix is present) 2177 or negative (removed) DAO messages, termed as no-DAOs. A no-DAO is 2178 stimulated by the disappearance of a prefix below. This is 2179 discovered by timing out after a request (a DIO message) or by 2180 receiving a no-DAO. A no-DAO is a conveyed as a DAO message with a 2181 DAO Lifetime of ZERO_LIFETIME. 2183 A node that is capable of recording the state information conveyed in 2184 a unicast DAO message will do so upon receiving and processing the 2185 DAO message, thus building up routing state concerning destinations 2186 below it in the DAG. If a node capable of recording state 2187 information receives a DAO message containing a Reverse Route Stack, 2188 then the node knows that the DAO message has traversed one or more 2189 nodes that did not retain any routing state as it traversed the path 2190 from the DAO source to the node. The node may then extract the 2191 Reverse Route Stack and retain the included state in order to specify 2192 Source Routing instructions along the return path towards the 2193 destination. The node MUST set the RRCount back to zero and clear 2194 the Reverse Route Stack prior to passing the DAO message information 2195 on. 2197 A node that is unable to record the state information conveyed in the 2198 DAO message will append the next-hop address to the Reverse Route 2199 Stack, increment the RRCount, and then pass the destination 2200 advertisement on without recording any additional state. In this way 2201 the Reverse Route Stack will contain a vector of next hops that must 2202 be traversed along the reverse path that the DAO message has 2203 traveled. The vector will be ordered such that the node closest to 2204 the destination will appear first in the list. In such cases, if it 2205 is useful to the implementation to try and build up redundant paths, 2206 the node may choose to convey the destination advertisement to one or 2207 more DAG parents in order of preference as guided by an 2208 implementation specific policy. 2210 In some cases (called hybrid cases), some nodes along the path a 2211 destination advertisement follows inward along the DAG may store 2212 state and some may not. The destination advertisement mechanism 2213 allows for the provisioning of routing state such that when a packet 2214 is traversing outwards along the DAG, some nodes may be able to 2215 directly forward to the next hop, and other nodes may be able to 2216 specify a piecewise source route in order to bridge spans of 2217 stateless nodes within the path on the way to the desired 2218 destination. 2220 In the case where no node is able to store any routing state as 2221 destination advertisements pass by, and the DAG root ends up with DAO 2222 messages that contain a completely specified route back to the 2223 originating node in the form of the inverted Reverse Route Stack. A 2224 DAG root should not request (Destination Advertisement Trigger) nor 2225 indicate support (Destination Advertisement Supported) for 2226 destination advertisements if it is not able to store the Reverse 2227 Route Stack information in this case. 2229 The destination advertisement mechanism requires stateful nodes to 2230 maintain lists of known prefixes. A prefix entry contains the 2231 following abstract information: 2233 o A reference to the ND entry that was created for the advertising 2234 neighbor. 2236 o The IPv6 address and interface for the advertising neighbor. 2238 o The logical equivalent of the full destination advertisement 2239 information (including the prefixes, depth, and Reverse Route 2240 Stack, if any). 2242 o A 'reported' Boolean to keep track whether this prefix was 2243 reported already, and to which of the DA parents. 2245 o A counter of retries to count how many DIO messages were sent on 2246 the interface to the advertising neighbor without reachability 2247 confirmation for the prefix. 2249 Note that nodes may receive multiple information from different 2250 neighbors for a specific destination, as different paths through the 2251 DAG may be propagating information inwards along the DAG for the same 2252 destination. A node that is recording routing state will keep track 2253 of the information from each neighbor independently, and when it 2254 comes time to propagate the DAO message for a particular prefix to 2255 the DA parents, then the DAO information will be selected from among 2256 the advertising neighbors who offer the least depth to the 2257 destination. 2259 The destination advertisement mechanism stores the prefix entries in 2260 one of 3 abstract lists; the Connected, the Reachable and the 2261 Unreachable lists. 2263 The Connected list corresponds to the prefixes owned and managed by 2264 the local node. 2266 The Reachable list contains prefixes for which the node keeps 2267 receiving DAO messages, and for those prefixes which have not yet 2268 timed out. 2270 The Unreachable list keeps track of prefixes which are no longer 2271 valid and in the process of being deleted, in order to send DAO 2272 messages with zero lifetime (also called no-DAO) to the DA parents. 2274 5.10.1.1.1. Destination Advertisement Timers 2276 The destination advertisement mechanism requires 2 timers; the 2277 DelayDAO timer and the RemoveTimer. 2279 o The DelayDAO timer is armed upon a stimulation to send a 2280 destination advertisement (such as a DIO message from a DA 2281 parent). When the timer is armed, all entries in the Reachable 2282 list as well as all entries for Connected list are set to not be 2283 reported yet for that particular DA parent. 2285 o The DelayDAO timer has a duration that is DEF_DAO_LATENCY divided 2286 by a multiple of the DAG rank of the node. The intention is that 2287 nodes located deeper in the DAG should have a shorter DelayDAO 2288 timer, allowing DAO messages a chance to be reported from deeper 2289 in the DAG and potentially aggregated along sub-DAGs before 2290 propagating further inwards. 2292 o The RemoveTimer is used to clean up entries for which DAO messages 2293 are no longer being received from the sub-DAG. 2295 * When a DIO message is sent that is requesting destination 2296 advertisements, a flag is set for all DAO entries in the 2297 routing table. 2299 * If the flag has already been set for a DAO entry, the retry 2300 count is incremented. 2302 * If a DAO message is received to confirm the entry, the entry is 2303 refreshed and the flag and count may be cleared. 2305 * If at least one entry has reached a threshold value and the 2306 RemoveTimer is not running, the entry is considered to be 2307 probably gone and the RemoveTimer is started. 2309 * When the RemoveTimer elapse, DAO messages with lifetime 0, i.e. 2310 no-DAOs, are sent to explicitly inform DA parents that the 2311 entries which have reached the threshold are no longer 2312 available, and the related routing states may be propagated and 2313 cleaned up. 2315 o The RemoveTimer has a duration of min (MAX_DESTROY_INTERVAL, 2316 TBD(DIO Trickle Timer Interval)). 2318 5.10.1.2. Multicast Destination Advertisement Messages 2320 It is also possible for a node to multicast a DAO message to the 2321 link-local scope all-nodes multicast address FF02::1. This message 2322 will be received by all node listening in range of the emitting node. 2323 The objective is to enable direct P2P communication, between 2324 destinations directly supported by neighboring nodes, without needing 2325 the RPL routing structure to relay the packets. 2327 A multicast DAO message MUST be used only to advertise information 2328 about self, i.e. prefixes in the Connected list or addresses owned by 2329 this node. This would typically be a multicast group that this node 2330 is listening to or a global address owned by this node, though it can 2331 be used to advertise any prefix owned by this node as well. A 2332 multicast DAO message is not used for routing and does not presume 2333 any DAG relationship between the emitter and the receiver; it MUST 2334 NOT be used to relay information learned (e.g. information in the 2335 Reachable list) from another node; information obtained from a 2336 multicast DAO MAY be installed in the routing table and MAY be 2337 propagated by a router in unicast DAOs. 2339 A node receiving a multicast DAO message addressed to FF02::1 MAY 2340 install prefixes contained in the DAO message in the routing table 2341 for local use. Such a node MUST NOT perform any other processing on 2342 the DAO message (i.e. such a node does not presume it is a DA 2343 parent). 2345 5.10.1.3. Unicast Destination Advertisement Messages from Child to 2346 Parent 2348 When sending a destination advertisement to a DA parent, a node 2349 includes the DAOs for prefix entries not already reported (since the 2350 last DA Trigger from an DIO message) in the Reachable and Connected 2351 lists, as well as no-DAOs for all the entries in the Unreachable 2352 list. Depending on its policy and ability to retain routing state, 2353 the receiving node SHOULD keep a record of the reported DAO message. 2354 If the DAO message offers the best route to the prefix as determined 2355 by policy and other prefix records, the node SHOULD install a route 2356 to the prefix reported in the DAO message via the link local address 2357 of the reporting neighbor and it SHOULD further propagate the 2358 information in a DAO message. 2360 The DIO message from the DAG root is used to synchronize the whole 2361 DAG, including the periodic reporting of destination advertisements 2362 back up the DAG. Its period is expected to vary, depending on the 2363 configuration of the trickle timer that governs the RAs. 2365 When a node receives a DIO message over an LLN interface from a DA 2366 parent, the DelayDAO is armed to force a full update. 2368 When the node broadcasts a DIO message on an LLN interface, for all 2369 entries on that interface: 2371 o If the entry is CONFIRMED, it goes PENDING with the retry count 2372 set to 0. 2374 o If the entry is PENDING, the retry count is incremented. If it 2375 reaches a maximum threshold, the entry goes ELAPSED If at least 2376 one entry is ELAPSED at the end of the process: if the RemoveTimer 2377 is not running then it is armed with a jitter. 2379 Since the DelayDAO timer has a duration that decreases with the 2380 depth, it is expected to receive all DAO messages from all children 2381 before the timer elapses and the full update is sent to the DA 2382 parents. 2384 Once the RemoveTimer is elapsed, the prefix entry is scheduled to be 2385 removed and moved to the Unreachable list if there are any DA parents 2386 that need to be informed of the change in status for the prefix, 2387 otherwise the prefix entry is cleaned up right away. The prefix 2388 entry is removed from the Unreachable list when no more DA parents 2389 need to be informed. This condition may be satisfied when a no-DAO 2390 is sent to all current DA parents indicating the loss of the prefix, 2391 and noting that in some cases parents may have been removed from the 2392 set of DA parents. 2394 5.10.1.4. Other Events 2396 Finally, the destination advertisement mechanism responds to a series 2397 of events, such as: 2399 o Destination advertisement operation stopped: All entries in the 2400 abstract lists are freed. All the routes learned from DAO 2401 messages are removed. 2403 o Interface going down: for all entries in the Reachable list on 2404 that interface, the associated route is removed, and the entry is 2405 scheduled to be removed. 2407 o Loss of routing adjacency: When the routing adjacency for a 2408 neighbor is lost, as per the procedures described in Section 5.13, 2409 and if the associated entries are in the Reachable list, the 2410 associated routes are removed, and the entries are scheduled to be 2411 destroyed. 2413 o Changes to DA parent set: all entries in the Reachable list are 2414 set to not 'reported' and DelayDAO is armed. 2416 5.10.1.5. Aggregation of Prefixes by a Node 2418 There may be number of cases where a aggregation may be shared within 2419 a group of nodes. In such a case, it is possible to use aggregation 2420 techniques with destination advertisements and improve scalability. 2422 Other cases might occur for which additional support is required: 2424 1. The aggregating node is attached within the sub-DAG of the nodes 2425 it is aggregating for. 2427 2. A node that is to be aggregated for is located somewhere else 2428 within the DAG, not in the sub-DAG of the aggregating node. 2430 3. A node that is to be aggregated for is located somewhere else in 2431 the LLN. 2433 Consider a node M that is performing an aggregation, and a node N 2434 that is to be a member of the aggregation group. A node Z situated 2435 above the node M in the DAG, but not above node N, will see the 2436 advertisements for the aggregation owned by M but not that of the 2437 individual prefix for N. Such a node Z will route all the packets for 2438 node N towards node M, but node M will have no route to the node N 2439 and will fail to forward. 2441 Additional protocols may be applied beyond the scope of this 2442 specification to dynamically elect/provision an aggregating node and 2443 groups of nodes eligible to be aggregated in order to provide route 2444 summarization for a sub-DAG. 2446 5.11. Loop Detection 2448 RPL loop avoidance mechanisms are kept simple and designed to 2449 minimize churn and states. Loops may form for a number of reasons, 2450 from control packet loss to sibling forwarding. RPL includes a 2451 reactive loop detection technique that protects from meltdown and 2452 triggers repair of broken paths. 2454 RPL loop detection uses information that is placed into the packet in 2455 the flow label. It assumes that the flow label may be overloaded for 2456 this purpose. The flow label is constructed as follows: 2458 0 1 2 3 2459 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 2460 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2461 |O|S|R|D| SenderRank | InstanceID | 2462 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2464 Figure 10: RPL Flow Label 2466 Outwards 'O' bit: 1-bit flag indicating whether the packet is 2467 expected to progress inwards or outwards. A router sets the 2468 'O' bit when the packet is expect to progress outwards (using 2469 DAO routes), and resets it when forwarding towards the root of 2470 the DAG. A host MUST set the bit to 0. 2472 Sibling 'S' bit: 1-bit flag indicating whether the packet has been 2473 forwarded via a sibling at the present rank, and denotes a risk 2474 of a sibling loop. A host sets the bit to 0. 2476 Rank-Error 'R' bit: 1-bit flag indicating whether a rank error was 2477 detected. A rank error is detected when there is a mismatch in 2478 the relative ranks and the direction as indicated in the 'O' 2479 bit. A host MUST set the bit to 0. 2481 DAO-Error 'D' bit: 1-bit flag indicating whether a DAO error was 2482 detected. An undetected DAO error would have resulted in an 2483 inward to outward transition that is not expected with this 2484 spec. A host MUST set the bit to 0. 2486 SenderRank: 8-bit field indicating the rank of the sender. A host 2487 MUST set the rank to INFINITE_RANK. A router MUST place its 2488 own rank in the flow label when forwarding. 2490 InstanceID: 8-bit field indicating the DAG instance along which the 2491 packet is sent. 2493 5.11.1. Host Basic Operation 2495 It is expected that a host that does not participate to RPL in any 2496 fashion is configured to set the flow label to all zeroes in its 2497 outgoing packets. The host MAY send a packet to any router 2498 regardless of the DAG and RPL operations at large. 2500 A host that participates to RPL SHOULD zero out all the flags, and it 2501 MUST set the sender rank to INFINITE_RANK. If the host can map a 2502 flow to a given InstanceID then it MUST set the flow label 2503 accordingly. Forwarding rules are the same for this host and a 2504 router, and are described in the next section. 2506 5.11.2. Instance Forwarding 2508 Instance IDs is used to avoid loops between DAGs from different 2509 origins. DAGs that constructed for antagonistic constraints might 2510 contain paths that, if mixed together, would yield loops. Those 2511 loops are avoided by forwarding a packet along the DAG that is 2512 associated to a given instance. 2514 The InstanceID is placed by the source in the flow label. It is not 2515 meaningful if the packet has the flow label set to all zeroes. 2516 Otherwise it MUST match the DAG instance onto which the packet is 2517 placed by any node, be it a host or router. 2519 When a router receives a packet that is flagged with a given instance 2520 ID and the node can forward the packet along the DAG associated to 2521 that instance, then the router MUST do so and leave the instance ID 2522 flag unchanged. 2524 If any node can not forward a packet along the DAG associated to the 2525 instance ID in the flow label, then the node MAY either change the 2526 InstanceID to match a DAG that it is using for this packet or discard 2527 the packet. That decision is based on a policy. 2529 The default policy is as follows: if the node can forward along the 2530 DAG associated to the instance RPL_DEFAULT_INSTANCE then it should do 2531 so. Otherwise it should drop the packet. 2533 5.11.3. DAG Inconsistency Loop Detection 2535 The DAG is inconsistent is the direction of a packet does not match 2536 the rank relationship. A receiver detects an inconsistency if it 2537 receives a packet with either: 2539 the 'O' bit set (to outwards) from a node of a higher rank. 2541 the 'O' bit reset (for inwards) from a node of a lesser rank. 2543 the 'S' bit set (to sibling) from a node of a different rank. 2545 The propagation of a new sequence creates local inconsistencies. In 2546 particular, it is possible for a router to forward a packet to a 2547 future parent (same instance, same DAGID, higher sequence) without a 2548 loop, regardless of the rank of that parent. In that case, the 2549 sending router MUST present itself as a host on the future DAG and 2550 use a rank of INFINITE_RANK as it forwards the packets via a future 2551 parent to avoid a false positive. 2553 One inconsistency along the path is not considered as a critical 2554 error and the packet may continue. But a second detection along the 2555 path of a same packet should not occur and the packet is dropped. 2557 This process is controlled by the Rank-Error bit in the Flow Label. 2558 When an inconsistency, is detected on a packet, if the Rank-Error bit 2559 was not set then the Rank-Error bit is set. If it was set the packet 2560 is discarded and the trickle timer is reset. 2562 5.11.4. Sibling Loop Avoidance 2564 When a packet is forwarded along siblings, it cannot be checked for 2565 forward progress and may loop between siblings. Experimental 2566 evidence has shown that one sibling hop can be very useful but is 2567 generally sufficient to avoid loops. Based on that evidence, this 2568 specification enforces the simple rule that a packet may not make 2 2569 sibling hops in a row. 2571 When a host issues a packet or when a router forwards a packet to a 2572 non sibling, the Sibling bit in the packet must be reset. When a 2573 router forwards to a sibling: if the Sibling bit was not set then the 2574 Sibling bit is set. If the Sibling bit was set then the packet is 2575 discarded. This does not denote a graph inconsistency but indicates 2576 that a new graph should probably be formed with a new sequence. 2578 5.11.5. DAO Inconsistency Loop Detection and Recovery 2580 A DAO inconsistency happens when router that has an outwards DAO 2581 route via a child that is a remnant from an obsolete state that is 2582 not matched in the child. With DAO inconsistency loop recovery, a 2583 packet can be used to recursively explore and cleanup the obsolete 2584 DAO states along a sub-DAG. 2586 In a general manner, a packet that goes outwards should never go 2587 inwards again. So rather than routing inwards a packet with the 2588 Outwards bit set, the router MUST discard the packet. If DAO 2589 inconsistency loop recovery is applied, then the router SHOULD send 2590 the packet to the parent that passed it with the DAO-Error bit set. 2592 Upon a packet with a DAO bit set, the parent MUST remove the routing 2593 states that caused forwarding to that child, clear DAO-Error bit and 2594 send the packet again. The packet will make its way either to an 2595 alternate child or inwards to a parent. If that parent still has an 2596 inconsistent DAO state via self, the process will recurse and that 2597 state will be cleaned up as well. 2599 5.12. Multicast Operation 2601 This section describes further the multicast routing operations over 2602 an IPv6 RPL network, and specifically how unicast DAOs can be used to 2603 relay group registrations inwards. Wherever the following text 2604 mentions MLD, one can read MLDv2 or v3. 2606 As is traditional, a listener uses a protocol such as MLD with a 2607 router to register to a multicast group. 2609 Along the path between the router and the root of the DAG, MLD 2610 requests are mapped and transported as DAO messages within the RPL 2611 protocol; each hop coalesces the multiple requests for a same group 2612 as a single DAO message to the parent(s), in a fashion similar to 2613 proxy IGMP, but recursively between child router and parent up to the 2614 root. 2616 A router might select to pass a listener registration DAO message to 2617 its preferred parent only, in which case multicast packets coming 2618 back might be lost for all of its sub-DAG if the transmission fails 2619 over that link. Alternatively the router might select to copy 2620 additional parents as it would do for DAO messages advertising 2621 unicast destinations, in which case there might be duplicates that 2622 the router will need to prune. 2624 As a result, multicast routing states are installed in each router on 2625 the way from the listeners to the root, enabling the root to copy a 2626 multicast packet to all its children routers that had issued a DAO 2627 message including a DAO for that multicast group, as well as all the 2628 attached nodes that registered over MLD. 2630 For unicast traffic, it is expected that the grounded root of an RPL 2631 DAG terminates RPL and MAY redistribute the RPL routes over the 2632 external infrastructure using whatever routing protocol is used 2633 there. For multicast traffic, the root MAY proxy MLD for all the 2634 nodes attached to the RPL routers (this would be needed if the 2635 multicast source is located in the external infrastructure). For 2636 such a source, the packet will be replicated as it flows outwards 2637 along the DAG based on the multicast routing table entries installed 2638 from the DAO message. 2640 For a source inside the DAG, the packet is passed to the preferred 2641 parents, and if that fails then to the alternates in the DAG. The 2642 packet is also copied to all the registered children, except for the 2643 one that passed the packet. Finally, if there is a listener in the 2644 external infrastructure then the DAG root has to further propagate 2645 the packet into the external infrastructure. 2647 As a result, the DAG Root acts as an automatic proxy Rendezvous Point 2648 for the RPL network, and as source towards the Internet for all 2649 multicast flows started in the RPL LLN. So regardless of whether the 2650 root is actually attached to the Internet, and regardless of whether 2651 the DAG is grounded or floating, the root can serve inner multicast 2652 streams at all times. 2654 5.13. Maintenance of Routing Adjacency 2656 The selection of successors, along the default paths inward along the 2657 DAG, or along the paths learned from destination advertisements 2658 outward along the DAG, leads to the formation of routing adjacencies 2659 that require maintenance. 2661 In IGPs such as OSPF [RFC4915] or IS-IS [RFC5120], the maintenance of 2662 a routing adjacency involves the use of Keepalive mechanisms (Hellos) 2663 or other protocols such as BFD ([I-D.ietf-bfd-base]) and MANET 2664 Neighborhood Discovery Protocol (NHDP [I-D.ietf-manet-nhdp]). 2665 Unfortunately, such an approach is not desirable in constrained 2666 environments such as LLN and would lead to excessive control traffic 2667 in light of the data traffic with a negative impact on both link 2668 loads and nodes resources. Overhead to maintain the routing 2669 adjacency should be minimized. Furthermore, it is not always 2670 possible to rely on the link or transport layer to provide 2671 information of the associated link state. The network layer needs to 2672 fall back on its own mechanism. 2674 Thus RPL makes use of a different approach consisting of probing the 2675 neighbor using a Neighbor Solicitation message (see [RFC4861]). The 2676 reception of a Neighbor Advertisement (NA) message with the 2677 "Solicited Flag" set is used to verify the validity of the routing 2678 adjacency. Such mechanism MAY be used prior to sending a data 2679 packet. This allows for detecting whether or not the routing 2680 adjacency is still valid, and should it not be the case, select 2681 another feasible successor to forward the packet. 2683 5.14. Packet Forwarding 2685 When forwarding a packet to a destination, precedence is given to 2686 selection of a next-hop successor as follows: 2688 1. In the scope of this specification, it is preferred to select a 2689 successor from a DAG that matches the InstanceID marked in the 2690 IPv6 header of the packet being forwarded. 2692 2. If a local administrative preference favors a route that has been 2693 learned from a different routing protocol than RPL, then use that 2694 successor. 2696 3. If there is an entry in the routing table matching the 2697 destination that has been learned from a multicast destination 2698 advertisement (e.g. the destination is a one-hop neighbor), then 2699 use that successor. 2701 4. If there is an entry in the routing table matching the 2702 destination that has been learned from a unicast destination 2703 advertisement (e.g. the destination is located outwards along the 2704 sub-DAG), then use that successor. 2706 5. If there is a DAG offering a route to a prefix matching the 2707 destination, then select one of those DAG parents as a successor. 2709 6. If there is a DAG parent offering a default route then select 2710 that DAG parent as a successor. 2712 7. If there is a DAG offering a route to a prefix matching the 2713 destination, but all DAG parents have been tried and are 2714 temporarily unavailable (as determined by the forwarding 2715 procedure), then select a DAG sibling as a successor. 2717 8. Finally, if no DAG siblings are available, the packet is dropped. 2718 ICMP Destination Unreachable may be invoked. An inconsistency is 2719 detected. 2721 TTL MUST be decremented when forwarding. If the packet is being 2722 forwarded via a sibling, then the TTL MAY be decremented more 2723 aggressively (by more than one) to limit the impact of possible 2724 loops. 2726 Note that the chosen successor MUST NOT be the neighbor that was the 2727 predecessor of the packet (split horizon), except in the case where 2728 it is intended for the packet to change from an inward to an outward 2729 flow, such as switching from DIO routes to DAO routes as the 2730 destination is neared. 2732 6. RPL Constants and Variables 2734 ZERO_LIFETIME This is the special value of a lifetime that indicates 2735 immediate death and removal. ZERO_LIFETIME has a value of 0. 2737 BASE_RANK This is the rank for a virtual root that might be used to 2738 coordinate multiple roots. BASE_RANK has a value of 0. 2740 ROOT_RANK This is the rank for a DAG root. ROOT_RANK has a value of 2741 1. 2743 INFINITE_RANK This is the constant maximum for the rank. 2744 INFINITE_RANK has a value of 0xFF. 2746 RPL_DEFAULT_INSTANCE This is the instance ID that is used by this 2747 protocol by a node without a policy to know any better. 2748 RPL_DEFAULT_INSTANCE has a value of 0. 2750 DEFAULT_DIO_INTERVAL_MIN To be determined 2752 DEFAULT_DIO_INTERVAL_DOUBLINGS To be determined 2754 DEF_DAO_LATENCY To be determined 2756 MAX_DESTROY_INTERVAL To be determined 2758 DIO Timer One instance per DAG that a node is a member of. Expiry 2759 triggers DIO message transmission. Trickle timer with variable 2760 interval in [0, DIOIntervalMin..2^DIOIntervalDoublings]. See 2761 Section 5.4.4 2763 DAG Sequence Number Increment Timer Up to one instance per DAG that 2764 the node is acting as DAG root of. May not be supported in all 2765 implementations. Expiry triggers revision of 2766 DAGSequenceNumber, causing a new series of updated DIO message 2767 to be sent. Interval should be chosen appropriate to 2768 propagation time of DAG and as appropriate to application 2769 requirements (e.g. response time vs. overhead). See 2770 Section 5.5 2772 DelayDAO Timer Up to one instance per DA parent (the subset of DAG 2773 parents chosen to receive destination advertisements) per DAG. 2774 Expiry triggers sending of DAO message to the DA parent. The 2775 interval is to be proportional to DEF_DAO_LATENCY/(node rank), 2776 such that nodes of greater rank (further outward along the DAG) 2777 expire first, coordinating the sending of DAO messages to allow 2778 for a chance of aggregation. See Section 5.10.1.1.1 2780 RemoveTimer Up to one instance per DA entry per neighbor (i.e. those 2781 neighbors that have given DAO messages to this node as a DAG 2782 parent) Expiry triggers a change in state for the DA entry, 2783 setting up to do unreachable (No-DAO) advertisements or 2784 immediately deallocating the DA entry if there are no DA 2785 parents. The interval is min(MAX_DESTROY_INTERVAL, TBD(DIO 2786 Trickle Timer Interval)). See Section 5.10.1.1.1 2788 7. Manageability Considerations 2790 The aim of this section is to give consideration to the manageability 2791 of RPL, and how RPL will be operated in LLN beyond the use of a MIB 2792 module. The scope of this section is to consider the following 2793 aspects of manageability: fault management, configuration, accounting 2794 and performance. 2796 7.1. Control of Function and Policy 2798 7.1.1. Initialization Mode 2800 When a node is first powered up, it may either choose to stay silent 2801 and not send any multicast DIO message until it has joined a DAG, or 2802 to immediately root a transient DAG and start sending multicast DIO 2803 messages. A RPL implementation SHOULD allow configuring whether the 2804 node should stay silent or should start advertising DIO messages. 2806 Furthermore, the implementation SHOULD to allow configuring whether 2807 or not the node should start sending an DIS message as an initial 2808 probe for nearby DAGs, or should simply wait until it received RA 2809 messages from other nodes that are part of existing DAGs. 2811 7.1.2. DIO Base option 2813 RPL specifies a number of protocol parameters. 2815 A RPL implementation SHOULD allow configuring the following routing 2816 protocol parameters, which are further described in Section 5.1.3.1: 2818 DAGPreference 2819 InstanceID 2820 DAGObjectiveCodePoint 2821 DAGID 2822 Destination Prefixes 2823 DIOIntervalDoublings 2824 DIOIntervalMin 2826 DAG Root behavior: In some cases, a node may not want to permanently 2827 act as a DAG root if it cannot join a grounded DAG. For 2828 example a battery-operated node may not want to act as a DAG 2829 root for a long period of time. Thus a RPL implementation MAY 2830 support the ability to configure whether or not a node could 2831 act as a DAG root for a configured period of time. 2833 DAG Table Entry Suppression A RPL implementation SHOULD provide the 2834 ability to configure a timer after the expiration of which the 2835 DAG table that contains all the records about a DAG is 2836 suppressed, to be invoked if the DAG parent set becomes empty. 2838 7.1.3. Trickle Timers 2840 A RPL implementation makes use of trickle timer to govern the sending 2841 of DIO message. Such an algorithm is determined a by a set of 2842 configurable parameters that are then advertised by the DAG root 2843 along the DAG in DIO messages. 2845 For each DAG, a RPL implementation MUST allow for the monitoring of 2846 the following parameters, further described in Section 5.4.4: 2848 I 2850 T 2852 C 2854 I_min 2856 I_doublings: 2858 A RPL implementation SHOULD provide a command (for example via API, 2859 CLI, or SNMP MIB) whereby any procedure that detects an inconsistency 2860 may cause the trickle timer to reset. 2862 7.1.4. DAG Sequence Number Increment 2864 A RPL implementation may allow by configuration at the DAG root to 2865 refresh the DAG states by updating the DAGSequenceNumber. A RPL 2866 implementation SHOULD allow configuring whether or not periodic or 2867 event triggered mechanism are used by the DAG root to control 2868 DAGSequenceNumber change. 2870 7.1.5. Destination Advertisement Timers 2872 The following set of parameters of the DAO messages SHOULD be 2873 configurable: 2875 o The DelayDAO timer 2877 o The Remove timer 2879 7.1.6. Policy Control 2881 DAG discovery enables nodes to implement different policies for 2882 selecting their DAG parents. 2884 A RPL implementation SHOULD allow configuring the set of acceptable 2885 or preferred Objective Functions (OF) referenced by their Objective 2886 Codepoints (OCPs) for a node to join a DAG, and what action should be 2887 taken if none of a node's candidate neighbors advertise one of the 2888 configured allowable Objective Functions. 2890 A node in an LLN may learn routing information from different routing 2891 protocols including RPL. It is in this case desirable to control via 2892 administrative preference which route should be favored. An 2893 implementation SHOULD allow for specifying an administrative 2894 preference for the routing protocol from which the route was learned. 2896 A RPL implementation SHOULD allow for the configuration of the "Route 2897 Tag" field of the DAO messages according to a set of rules defined by 2898 policy. 2900 7.1.7. Data Structures 2902 Some RPL implementation may limit the size of the candidate neighbor 2903 list in order to bound the memory usage, in which case some otherwise 2904 viable candidate neighbors may not be considered and simply dropped 2905 from the candidate neighbor list. 2907 A RPL implementation MAY provide an indicator on the size of the 2908 candidate neighbor list. 2910 7.2. Information and Data Models 2912 The information and data models necessary for the operation of RPL 2913 will be defined in a separate document specifying the RPL SNMP MIB. 2915 7.3. Liveness Detection and Monitoring 2917 The aim of this section is to describe the various RPL mechanisms 2918 specified to monitor the protocol. 2920 As specified in Section 5.2, an implementation must maintain a set of 2921 data structures in support of DAG discovery: 2923 o The candidate neighbors data structure 2925 o For each DAG: 2927 * A set of DAG parents 2929 7.3.1. Candidate Neighbor Data Structure 2931 A node in the candidate neighbor list is a node discovered by the 2932 some means and qualified to potentially become of neighbor or a 2933 sibling (with high enough local confidence). A RPL implementation 2934 SHOULD provide a way monitor the candidate neighbors list with some 2935 metric reflecting local confidence (the degree of stability of the 2936 neighbors) measured by some metrics. 2938 A RPL implementation MAY provide a counter reporting the number of 2939 times a candidate neighbor has been ignored, should the number of 2940 candidate neighbors exceeds the maximum authorized value. 2942 7.3.2. Directed Acyclic Graph (DAG) Table 2944 For each DAG, a RPL implementation MUST keep track of the following 2945 DAG table values: 2947 o DAGID 2949 o DAGObjectiveCodePoint 2951 o A set of Destination Prefixes offered inwards along the DAG 2953 o A set of DAG Parents 2955 o timer to govern the sending of DIO messages for the DAG 2956 o DAGSequenceNumber 2958 The set of DAG parents structure is itself a table with the following 2959 entries: 2961 o A reference to the neighboring device which is the DAG parent 2963 o A record of most recent information taken from the DAG Information 2964 Object last processed from the DAG Parent 2966 o A flag reporting if the Parent is a DA Parent as described in 2967 Section 5.10 2969 7.3.3. Routing Table 2971 For each route provisioned by RPL operation, a RPL implementation 2972 MUST keep track of the following: 2974 o Destination Prefix 2976 o Destination Prefix Length 2978 o Lifetime Timer 2980 o Next Hop 2982 o Next Hop Interface 2984 o Flag indicating that the route was provisioned from one of: 2986 * Unicast DAO message 2988 * DIO message 2990 * Multicast DAO message 2992 7.3.4. Other RPL Monitoring Parameters 2994 A RPL implementation SHOULD provide a counter reporting the number of 2995 a times the node has detected an inconsistency with respect to a DAG 2996 parent, e.g. if the DAGID has changed. 2998 A RPL implementation MAY log the reception of a malformed DIO message 2999 along with the neighbor identification if avialable. 3001 7.3.5. RPL Trickle Timers 3003 A RPL implementation operating on a DAG root MUST allow for the 3004 configuration of the following trickle parameters: 3006 o The DIOIntervalMin expressed in ms 3008 o The DIOIntervalDoublings 3010 A RPL implementation MAY provide a counter reporting the number of 3011 times an inconsistency (and thus the trickle timer has been reset). 3013 7.4. Verifying Correct Operation 3015 This section has to be completed in further revision of this document 3016 to list potential Operations and Management (OAM) tools that could be 3017 used for verifying the correct operation of RPL. 3019 7.5. Requirements on Other Protocols and Functional Components 3021 RPL does not have any impact on the operation of existing protocols. 3023 7.6. Impact on Network Operation 3025 To be completed. 3027 8. Security Considerations 3029 Security Considerations for RPL are to be developed in accordance 3030 with recommendations laid out in, for example, 3031 [I-D.tsao-roll-security-framework]. 3033 9. IANA Considerations 3035 9.1. RPL Control Message 3037 The RPL Control Message is an ICMP information message type that is 3038 to be used carry DAG Information Objects, DAG Information 3039 Solicitations, and Destination Advertisement Objects in support of 3040 RPL operation. 3042 IANA has defined a ICMPv6 Type Number Registry. The suggested type 3043 value for the RPL Control Message is 155, to be confirmed by IANA. 3045 9.2. New Registry for RPL Control Codes 3047 IANA is requested to create a registry, RPL Control Codes, for the 3048 Code field of the ICMPv6 RPL Control Message. 3050 New codes may be allocated only by an IETF Consensus action. Each 3051 code should be tracked with the following qualities: 3053 o Code 3055 o Description 3057 o Defining RFC 3059 Three codes are currently defined: 3061 +------+----------------------------------+---------------+ 3062 | Code | Description | Reference | 3063 +------+----------------------------------+---------------+ 3064 | 0x01 | DAG Information Solicitation | This document | 3065 | 0x02 | DAG Information Object | This document | 3066 | 0x04 | Destination Advertisement Object | This document | 3067 +------+----------------------------------+---------------+ 3069 RPL Control Codes 3071 9.3. New Registry for the Control Field of the DIO Base Option 3073 IANA is requested to create a registry for the Control field of the 3074 DIO Base Option. 3076 New bit numbers may be allocated only by an IETF Consensus action. 3077 Each bit should be tracked with the following qualities: 3079 o Bit number (counting from bit 0 as the most significant bit) 3081 o Capability description 3083 o Defining RFC 3085 Four groups are currently defined: 3087 +-------+-------------------------------------+---------------+ 3088 | Bit | Description | Reference | 3089 +-------+-------------------------------------+---------------+ 3090 | 0 | Grounded DAG | This document | 3091 | 1 | Destination Advertisement Trigger | This document | 3092 | 2 | Destination Advertisement Supported | This document | 3093 | 5,6,7 | DAG Preference | This document | 3094 +-------+-------------------------------------+---------------+ 3096 DIO Base Option Flags 3098 9.4. DAG Information Object (DIO) Suboption 3100 IANA is requested to create a registry for the DIO Base Option 3101 Suboptions 3103 +-------+------------------------------+---------------+ 3104 | Value | Meaning | Reference | 3105 +-------+------------------------------+---------------+ 3106 | 0 | Pad1 - DIO Padding | This document | 3107 | 1 | PadN - DIO suboption padding | This document | 3108 | 2 | DAG Metric Container | This Document | 3109 | 3 | Destination Prefix | This Document | 3110 | 4 | DAG Timer Configuration | This Document | 3111 +-------+------------------------------+---------------+ 3113 DAG Information Option (DIO) Base Option Suboptions 3115 9.5. Objective Code Point for the Default Objective Function OF0 3117 This specification specifies the Default Objective Function (called 3118 OF0) for which the OCP field of the OF object, as defined in 3119 [I-D.ietf-roll-routing-metrics], is equal to 0x0000 3121 +-------+---------+---------------+ 3122 | Value | Meaning | Reference | 3123 +-------+---------+---------------+ 3124 | 0 | OF0 | This document | 3125 +-------+---------+---------------+ 3127 OCP Allocation 3129 10. Acknowledgements 3131 The authors would like to acknowledge the review, feedback, and 3132 comments from Emmanuel Baccelli, Dominique Barthel, Yusuf Bashir, 3133 Mathilde Durvy, Manhar Goindi, Mukul Goyal, Anders Jagd, Quentin 3134 Lampin, Jerry Martocci, Alexandru Petrescu, and Don Sturek. 3136 The authors would like to acknowledge the guidance and input provided 3137 by the ROLL Chairs, David Culler and JP Vasseur. 3139 The authors would like to acknowledge prior contributions of Robert 3140 Assimiti, Mischa Dohler, Julien Abeille, Ryuji Wakikawa, Teco Boot, 3141 Patrick Wetterwald, Bryan Mclaughlin, Carlos J. Bernardos, Thomas 3142 Watteyne, Zach Shelby, Caroline Bontoux, Marco Molteni, Billy Moon, 3143 and Arsalan Tavakoli, which have provided useful design 3144 considerations to RPL. 3146 11. Contributors 3148 RPL is the result of the contribution of the following members of the 3149 ROLL Design Team, including the editors, and additional contributors 3150 as listed below: 3152 JP Vasseur 3153 Cisco Systems, Inc 3154 11, Rue Camille Desmoulins 3155 Issy Les Moulineaux, 92782 3156 France 3158 Email: jpv@cisco.com 3160 Jonathan W. Hui 3161 Arch Rock Corporation 3162 501 2nd St. Ste. 410 3163 San Francisco, CA 94107 3164 USA 3166 Email: jhui@archrock.com 3168 Thomas Heide Clausen 3169 LIX, Ecole Polytechnique, France 3171 Phone: +33 6 6058 9349 3172 EMail: T.Clausen@computer.org 3173 URI: http://www.ThomasClausen.org/ 3175 Richard Kelsey 3176 Ember Corporation 3177 Boston, MA 3178 USA 3180 Phone: +1 617 951 1225 3181 Email: kelsey@ember.com 3183 Philip Levis 3184 Stanford University 3185 358 Gates Hall, Stanford University 3186 Stanford, CA 94305-9030 3187 USA 3189 Email: pal@cs.stanford.edu 3191 Stephen Dawson-Haggerty 3192 UC Berkeley 3193 Soda Hall, UC Berkeley 3194 Berkeley, CA 94720 3195 USA 3197 Email: stevedh@cs.berkeley.edu 3199 Kris Pister 3200 Dust Networks 3201 30695 Huntwood Ave. 3202 Hayward, 94544 3203 USA 3205 Email: kpister@dustnetworks.com 3207 Anders Brandt 3208 Zensys, Inc. 3209 Emdrupvej 26 3210 Copenhagen, DK-2100 3211 Denmark 3213 Email: abr@zen-sys.com 3215 12. References 3217 12.1. Normative References 3219 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 3220 Requirement Levels", BCP 14, RFC 2119, March 1997. 3222 12.2. Informative References 3224 [I-D.ietf-bfd-base] 3225 Katz, D. and D. Ward, "Bidirectional Forwarding 3226 Detection", draft-ietf-bfd-base-09 (work in progress), 3227 February 2009. 3229 [I-D.ietf-manet-nhdp] 3230 Clausen, T., Dearlove, C., and J. Dean, "MANET 3231 Neighborhood Discovery Protocol (NHDP)", 3232 draft-ietf-manet-nhdp-10 (work in progress), July 2009. 3234 [I-D.ietf-roll-building-routing-reqs] 3235 Martocci, J., Riou, N., Mil, P., and W. Vermeylen, 3236 "Building Automation Routing Requirements in Low Power and 3237 Lossy Networks", draft-ietf-roll-building-routing-reqs-07 3238 (work in progress), September 2009. 3240 [I-D.ietf-roll-home-routing-reqs] 3241 Brandt, A., Buron, J., and G. Porcu, "Home Automation 3242 Routing Requirements in Low Power and Lossy Networks", 3243 draft-ietf-roll-home-routing-reqs-08 (work in progress), 3244 September 2009. 3246 [I-D.ietf-roll-routing-metrics] 3247 Vasseur, J. and D. Networks, "Routing Metrics used for 3248 Path Calculation in Low Power and Lossy Networks", 3249 draft-ietf-roll-routing-metrics-01 (work in progress), 3250 October 2009. 3252 [I-D.ietf-roll-terminology] 3253 Vasseur, J., "Terminology in Low power And Lossy 3254 Networks", draft-ietf-roll-terminology-02 (work in 3255 progress), October 2009. 3257 [I-D.tsao-roll-security-framework] 3258 Tsao, T., Alexander, R., Dohler, M., Daza, V., and A. 3259 Lozano, "A Security Framework for Routing over Low Power 3260 and Lossy Networks", draft-tsao-roll-security-framework-01 3261 (work in progress), September 2009. 3263 [Levis08] Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S., 3264 Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and A. 3265 Woo, "The Emergence of a Networking Primitive in Wireless 3266 Sensor Networks", Communications of the ACM, v.51 n.7, 3267 July 2008, 3268 . 3270 [RFC2453] Malkin, G., "RIP Version 2", STD 56, RFC 2453, 3271 November 1998. 3273 [RFC3819] Karn, P., Bormann, C., Fairhurst, G., Grossman, D., 3274 Ludwig, R., Mahdavi, J., Montenegro, G., Touch, J., and L. 3275 Wood, "Advice for Internet Subnetwork Designers", BCP 89, 3276 RFC 3819, July 2004. 3278 [RFC4101] Rescorla, E. and IAB, "Writing Protocol Models", RFC 4101, 3279 June 2005. 3281 [RFC4191] Draves, R. and D. Thaler, "Default Router Preferences and 3282 More-Specific Routes", RFC 4191, November 2005. 3284 [RFC4443] Conta, A., Deering, S., and M. Gupta, "Internet Control 3285 Message Protocol (ICMPv6) for the Internet Protocol 3286 Version 6 (IPv6) Specification", RFC 4443, March 2006. 3288 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 3289 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 3290 September 2007. 3292 [RFC4915] Psenak, P., Mirtorabi, S., Roy, A., Nguyen, L., and P. 3293 Pillay-Esnault, "Multi-Topology (MT) Routing in OSPF", 3294 RFC 4915, June 2007. 3296 [RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi 3297 Topology (MT) Routing in Intermediate System to 3298 Intermediate Systems (IS-ISs)", RFC 5120, February 2008. 3300 [RFC5548] Dohler, M., Watteyne, T., Winter, T., and D. Barthel, 3301 "Routing Requirements for Urban Low-Power and Lossy 3302 Networks", RFC 5548, May 2009. 3304 [RFC5673] Pister, K., Thubert, P., Dwars, S., and T. Phinney, 3305 "Industrial Routing Requirements in Low-Power and Lossy 3306 Networks", RFC 5673, October 2009. 3308 Appendix A. Requirements 3310 A.1. Protocol Properties Overview 3312 RPL demonstrates the following properties, consistent with the 3313 requirements specified by the application-specific requirements 3314 documents. 3316 A.1.1. IPv6 Architecture 3318 RPL is strictly compliant with layered IPv6 architecture. 3320 Further, RPL is designed with consideration to the practical support 3321 and implementation of IPv6 architecture on devices which may operate 3322 under severe resource constraints, including but not limited to 3323 memory, processing power, energy, and communication. The RPL design 3324 does not presume high quality reliable links, and operates over lossy 3325 links (usually low bandwidth with low packet delivery success rate). 3327 A.1.2. Typical LLN Traffic Patterns 3329 Multipoint-to-Point (MP2P) and Point-to-multipoint (P2MP) traffic 3330 flows from nodes within the LLN from and to egress points are very 3331 common in LLNs. Low power and lossy network Border Router (LBR) 3332 nodes may typically be at the root of such flows, although such flows 3333 are not exclusively rooted at LBRs as determined on an application- 3334 specific basis. In particular, several applications such as building 3335 or home automation do require P2P (Point-to-Point) communication. 3337 As required by the aforementioned routing requirements documents, RPL 3338 supports the installation of multiple paths. The use of multiple 3339 paths include sending duplicated traffic along diverse paths, as well 3340 as to support advanced features such as Class of Service (CoS) based 3341 routing, or simple load balancing among a set of paths (which could 3342 be useful for the LLN to spread traffic load and avoid fast energy 3343 depletion on some, e.g. battery powered, nodes). Conceptually, 3344 multiple instances of RPL can be used to send traffic along different 3345 topology instances, the construction of which is governed by 3346 different Objective Functions (OF). Details of RPL operation in 3347 support of multiple instances are beyond the scope of the present 3348 specification. 3350 A.1.3. Constraint Based Routing 3352 The RPL design supports constraint based routing, based on a set of 3353 routing metrics and constraints. The routing metrics and constraints 3354 for links and nodes with capabilities supported by RPL are specified 3355 in a companion document to this specification, 3356 [I-D.ietf-roll-routing-metrics]. RPL signals the metrics, 3357 constraints, and related Objective Functions (OFs) in use in a 3358 particular implementation by means of an Objective Code Point (OCP). 3359 Both the routing metrics, constraints, and the OF help determine the 3360 construction of the Directed Acyclic Graphs (DAG) using a distributed 3361 path computation algorithm. 3363 A.2. Deferred Requirements 3365 NOTE: RPL is still a work in progress. At this time there remain 3366 several unsatisfied application requirements, but these are to be 3367 addressed as RPL is further specified. 3369 Appendix B. Examples 3371 Consider the example LLN physical topology in Figure 11. In this 3372 example the links depicted are all usable L2 links. Suppose that all 3373 links are equally usable, and that the implementation specific policy 3374 function is simply to minimize hops. This LLN physical topology then 3375 yields the DAG depicted in Figure 12, where the links depicted are 3376 the edges toward DAG parents. This topology includes one DAG, rooted 3377 by an LBR node (LBR) at rank 1. The LBR node will issue DIO 3378 messages, as governed by a trickle timer. Nodes (11), (12), (13), 3379 have selected (LBR) as their only parent, attached to the DAG at rank 3380 2, and periodically multicast DIOs. Node (22) has selected (11) and 3381 (12) in its DAG parent set, and advertises itself at rank 3. Node 3382 (22) thus has a set of DAG parents {(11), (12)} and siblings {((21), 3383 (23)}. 3385 (LBR) 3386 / | \ 3387 .---` | `----. 3388 / | \ 3389 (11)------(12)------(13) 3390 | \ | \ | \ 3391 | `----. | `----. | `----. 3392 | \| \| \ 3393 (21)------(22)------(23) (24) 3394 | /| /| | 3395 | .----` | .----` | | 3396 | / | / | | 3397 (31)------(32)------(33)------(34) 3398 | /| \ | \ | \ 3399 | .----` | `----. | `----. | `----. 3400 | / | \| \| \ 3401 .--------(41) (42) (43)------(44)------(45) 3402 / / /| \ | \ 3403 .----` .----` .----` | `----. | `----. 3404 / / / | \| \ 3405 (51)------(52)------(53)------(54)------(55)------(56) 3407 Note that the links depicted represent the usable L2 connectivity 3408 available in the LLN. For example, Node (31) can communicate 3409 directly with its neighbors, Nodes (21), (22), (32), and (41). Node 3410 (31) cannot communicate directly with any other nodes, e.g. (33), 3411 (23), (42). In this example these links offer bidirectional 3412 communication, and `bad' links are not depicted. 3414 Figure 11: Example LLN Topology 3416 (LBR) 3417 / | \ 3418 .---` | `----. 3419 / | \ 3420 (11) (12) (13) 3421 | \ | \ | \ 3422 | `----. | `----. | `----. 3423 | \| \| \ 3424 (21) (22) (23) (24) 3425 | /| /| | 3426 | .----` | .----` | | 3427 | / | / | | 3428 (31) (32) (33) (34) 3429 | /| \ | \ | \ 3430 | .----` | `----. | `----. | `----. 3431 | / | \| \| \ 3432 .--------(41) (42) (43) (44) (45) 3433 / / /| \ | \ 3434 .----` .----` .----` | `----. | `----. 3435 / / / | \| \ 3436 (51) (52) (53) (54) (55) (56) 3438 Note that the links depicted represent directed links in the DAG 3439 overlaid on top of the physical topology depicted in Figure 11. As 3440 such, the depicted edges represent the relationship between nodes and 3441 their DAG parents, wherein all depicted edges are directed and 3442 oriented `up' on the page toward the DAG root (LBR). The DAG may 3443 provide default routes within the LLN, and serves as the foundation 3444 on which RPL builds further routing structure, e.g. through the 3445 destination advertisement mechanism. 3447 Figure 12: Example DAG 3449 B.1. Destination Advertisement 3451 Consider the example DAG depicted in Figure 12. Suppose that Nodes 3452 (22) and (32) are unable to record routing state. Suppose that Node 3453 (42) is able to perform prefix aggregation on behalf of Nodes (53), 3454 (54), and (55). 3456 o Node (53) would send a DAO message to Node (42), indicating the 3457 availability of destination (53). 3459 o Node (54) and Node (55) would similarly send DAO messages to Node 3460 (42) indicating their own destinations. 3462 o Node (42) would collect and store the routing state for 3463 destinations (53), (54), and (55). 3465 o In this example, Node (42) may then be capable of representing 3466 destinations (42), (53), (54), and (55) in the aggregation (42'). 3468 o Node (42) sends a DAO message advertising destination (42') to 3469 Node 32. 3471 o Node (32) does not want to maintain any routing state, so it adds 3472 onto to the Reverse Route Stack in the DAO message and passes it 3473 on to Node (22) as (42'):[(42)]. It may send a separate DAO 3474 message to indicate destination (32). 3476 o Node (22) does not want to maintain any routing state, so it adds 3477 on to the Reverse Route Stack in the DAO message and passes it on 3478 to Node (12) as (42'):[(42), (32)]. It also relays the DAO 3479 message containing destination (32) to Node 12 as (32):[(32)], and 3480 finally may send a DAO message for itself indicating destination 3481 (22). 3483 o Node (12) is capable to maintain routing state again, and receives 3484 the DAO messages from Node (22). Node (12) then learns: 3485 * Destination (22) is available via Node (22) 3486 * Destination (32) is available via Node (22) and the piecewise 3487 source route to (32) 3488 * Destination (42') is available via Node (22) and the piecewise 3489 source route to (32), (42'). 3491 o Node (12) sends DAO messages to (LBR), allowing (LBR) to learn 3492 routes to the destinations (12), (22), (32), and (42'). (42), 3493 (53), (54), and (55) are available via the aggregation (42'). It 3494 is not necessary for Node (12) to propagate the piecewise source 3495 routes to (LBR). 3497 B.2. Example: DAG Parent Selection 3499 For example, suppose that a node (N) is not attached to any DAG, and 3500 that it is in range of nodes (A), (B), (C), (D), and (E). Let all 3501 nodes be configured to use an OCP which defines a policy such that 3502 ETX is to be minimized and paths with the attribute `Blue' should be 3503 avoided. Let the rank computation indicated by the OCP simply 3504 reflect the ETX aggregated along the path. Let the links between 3505 node (N) and its neighbors (A-E) all have an ETX of 1 (which is 3506 learned by node (N) through some implementation specific method). 3507 Let node (N) be configured to send RPL DIS messages to probe for 3508 nearby DAGs. 3510 o Node (N) transmits a RPL DIS message. 3512 o Node (B) responds. Node (N) investigates the DIO message, and 3513 learns that Node (B) is a member of DAGID 1 at rank 4, and not 3514 `Blue'. Node (N) takes note of this, but is not yet confident. 3516 o Similarly, Node (N) hears from Node (A) at rank 9, Node (C) at 3517 rank 5, and Node (E) at rank 4. 3519 o Node (D) responds. Node (D) has a DIO message that indicates that 3520 it is a member of DAGID 1 at rank 2, but it carries the attribute 3521 `Blue'. Node (N)'s policy function rejects Node (D), and no 3522 further consideration is given. 3524 o This process continues until Node (N), based on implementation 3525 specific policy, builds up enough confidence to trigger a decision 3526 to join DAGID 1. Let Node (N) determine its most preferred parent 3527 to be Node (E). 3529 o Node (N) adds Node (E) (rank 4) to its set of DAG parents for 3530 DAGID 1. Following the mechanisms specified by the OCP, and given 3531 that the ETX is 1 for the link between (N) and (E), Node (N) is 3532 now at rank 5 in DAGID 1. 3534 o Node (N) adds Node (B) (rank 4) to its set of DAG parents for 3535 DAGID 1. 3537 o Node (N) is a sibling of Node (C), both are at rank 5. 3539 o Node (N) may now forward traffic intended for the default 3540 destination inward along DAGID 1 via nodes (B) and (E). In some 3541 cases, e.g. if nodes (B) and (E) are tried and fail, node (N) may 3542 also choose to forward traffic to its sibling node (C), without 3543 making inward progress but with the intention that node (C) or a 3544 following successor can make inward progress. Should Node (C) not 3545 have a viable parent, it should never send the packet back to Node 3546 (N) (to avoid a 2-node loop). 3548 B.3. Example: DAG Maintenance 3550 : : : 3551 : : : 3552 (A) (A) (A) 3553 |\ | | 3554 | `-----. | | 3555 | \ | | 3556 (B) (C) (B) (C) (B) 3557 | | \ 3558 | | `-----. 3559 | | \ 3560 (D) (D) (C) 3561 | 3562 | 3563 | 3564 (D) 3566 -1- -2- -3- 3568 Figure 13: DAG Maintenance 3570 Consider the example depicted in Figure 13-1. In this example, Node 3571 (A) is attached to a DAG at some rank d. Node (A) is a DAG parent of 3572 Nodes (B) and (C). Node (C) is a DAG parent of Node (D). There is 3573 also an undirected sibling link between Nodes (B) and (C). 3575 In this example, Node (C) may safely forward to Node (A) without 3576 creating a loop. Node (C) may not safely forward to Node (D), 3577 contained within it's own sub-DAG, without creating a loop. Node (C) 3578 may forward to Node (B) in some cases, e.g. the link (C)->(A) is 3579 temporarily unavailable, but with some chance of creating a loop 3580 (e.g. if multiple nodes in a set of siblings start forwarding 3581 `sideways' in a cycle) and requiring the intervention of additional 3582 mechanisms to detect and break the loop. 3584 Consider the case where Node (C) hears a DIO message from a Node (Z) 3585 at a lesser rank and superior position in the DAG than node (A). 3586 Node (C) may safely undergo the process to evict node (A) from its 3587 DAG parent set and attach directly to Node (Z) without creating a 3588 loop, because its rank will decrease. 3590 Now consider the case where the link (C)->(A) becomes nonviable, and 3591 node (C) must move to a deeper rank within the DAG: 3593 o Node (C) must first detach from the DAG by removing Node (A) from 3594 its DAG parent set, leaving an empty DAG parent set. Node (C) may 3595 become the root of its own floating, less preferred, DAG. 3597 o Node (D), hearing a modified DIO message from Node (C), follows 3598 Node (C) into the floating DAG. This is depicted in Figure 13-2. 3599 In general, any node with no other options in the sub-DAG of Node 3600 (C) will follow Node (C) into the floating DAG, maintaining the 3601 structure of the sub-DAG. 3603 o Node (C) hears a DIO message with an incremented DAGSequenceNumber 3604 from Node (B) and determines it is able to rejoin the grounded DAG 3605 by reattaching at a deeper rank to Node (B). Node (C) adds Node 3606 (B) to its DAG parent set. Node (C) has now safely moved deeper 3607 within the grounded DAG without creating any loops. 3609 o Node (D), and any other sub-DAG of Node (C), will hear the 3610 modified DIO message sourced from Node (C) and follow Node (C) in 3611 a coordinated manner to reattach to the grounded DAG. The final 3612 DAG is depicted in Figure 13-3 3614 B.4. Example: Greedy Parent Selection and Instability 3616 (A) (A) (A) 3617 |\ |\ |\ 3618 | `-----. | `-----. | `-----. 3619 | \ | \ | \ 3620 (B) (C) (B) \ | (C) 3621 \ | | / 3622 `-----. | | .-----` 3623 \| |/ 3624 (C) (B) 3626 -1- -2- -3- 3628 Figure 14: Greedy DAG Parent Selection 3630 Consider the example depicted in Figure 14. A DAG is depicted in 3 3631 different configurations. A usable link between (B) and (C) exists 3632 in all 3 configurations. In Figure 14-1, Node (A) is a DAG parent 3633 for Nodes (B) and (C), and (B)--(C) is a sibling link. In 3634 Figure 14-2, Node (A) is a DAG parent for Nodes (B) and (C), and Node 3635 (B) is also a DAG parent for Node (C). In Figure 14-3, Node (A) is a 3636 DAG parent for Nodes (B) and (C), and Node (C) is also a DAG parent 3637 for Node (B). 3639 If a RPL node is too greedy, in that it attempts to optimize for an 3640 additional number of parents beyond its preferred parent, then an 3641 instability can result. Consider the DAG illustrated in Figure 14-1. 3642 In this example, Nodes (B) and (C) may most prefer Node (A) as a DAG 3643 parent, but are operating under the greedy condition that will try to 3644 optimize for 2 parents. 3646 When the preferred parent selection causes a node to have only one 3647 parent and no siblings, the node may decide to insert itself at a 3648 slightly higher rank in order to have at least one sibling and thus 3649 an alternate forwarding solution. This does not deprive other nodes 3650 of a forwarding solution and this is considered acceptable 3651 greediness. 3653 o Let Figure 14-1 be the initial condition. 3655 o Suppose Node (C) first is able to leave the DAG and rejoin at a 3656 lower rank, taking both Nodes (A) and (B) as DAG parents as 3657 depicted in Figure 14-2. Now Node (C) is deeper than both Nodes 3658 (A) and (B), and Node (C) is satisfied to have 2 DAG parents. 3660 o Suppose Node (B), in its greediness, is willing to receive and 3661 process a DIO message from Node (C) (against the rules of RPL), 3662 and then Node (B) leaves the DAG and rejoins at a lower rank, 3663 taking both Nodes (A) and (C) as DAG parents. Now Node (B) is 3664 deeper than both Nodes (A) and (C) and is satisfied with 2 DAG 3665 parents. 3667 o Then Node (C), because it is also greedy, will leave and rejoin 3668 deeper, to again get 2 parents and have a lower rank then both of 3669 them. 3671 o Next Node (B) will again leave and rejoin deeper, to again get 2 3672 parents 3674 o And again Node (C) leaves and rejoins deeper... 3676 o The process will repeat, and the DAG will oscillate between 3677 Figure 14-2 and Figure 14-3 until the nodes count to infinity and 3678 restart the cycle again. 3680 o This cycle can be averted through mechanisms in RPL: 3682 * Nodes (B) and (C) stay at a rank sufficient to attach to their 3683 most preferred parent (A) and don't go for any deeper (worse) 3684 alternate parents (Nodes are not greedy) 3686 * Nodes (B) and (C) do not process DIO messages from nodes deeper 3687 than themselves (because such nodes are possibly in their own 3688 sub-DAGs) 3690 Appendix C. Outstanding Issues 3692 This section enumerates some outstanding issues that are to be 3693 addressed in future revisions of the RPL specification. 3695 C.1. Additional Support for P2P Routing 3697 In some situations the baseline mechanism to support arbitrary P2P 3698 traffic, by flowing inward along the DAG until a common parent is 3699 reached and then flowing outward, may not be suitable for all 3700 application scenarios. A related scenario may occur when the outward 3701 paths setup along the DAG by the destination advertisement mechanism 3702 are not be the most desirable outward paths for the specific 3703 application scenario (in part because the DAG links may not be 3704 symmetric). It may be desired to support within RPL the discovery 3705 and installation of more direct routes `across' the DAG. Such 3706 mechanisms need to be investigated. 3708 C.2. Loop Detection 3710 It is under investigation to complement the loop avoidance strategies 3711 provided by RPL with a loop detection mechanism that may be employed 3712 when traffic is forwarded. 3714 C.3. Destination Advertisement / DAO Fan-out 3716 When DAO messages are relayed to more than one DAG parent, in some 3717 cases a situation may be created where a large number of DAO messages 3718 conveying information about the same destination flow inward along 3719 the DAG. It is desirable to bound/limit the multiplication/fan-out 3720 of DAO messages in this manner. Some aspects of the Destination 3721 Advertisement mechanism remain under investigation, such as behavior 3722 in the face of links that may not be symmetric. 3724 In general, the utility of providing redundancy along outwards routes 3725 by sending DAO messages to more than one parent is under 3726 investigation. 3728 The use of suitable triggers, such as the `D' bit, to trigger DA 3729 operation within an affected sub-DAG, is under investigation. 3730 Further, the ability to limit scope of the affected depth within the 3731 sub-DAG is under investigation (e.g. if a stateful node can proxy for 3732 all nodes `behind' it, then there may be no need to propagate the 3733 triggered `D' bit further). 3735 C.4. Source Routing 3737 In support of nodes that maintain minimal routing state, and to make 3738 use of the collection of piecewise source routes from the destination 3739 advertisement mechanism, there needs to be some investigation of a 3740 mechanism to specify, attach, and follow source routes for packets 3741 traversing the LLN. 3743 C.5. Address / Header Compression 3745 In order to minimize overhead within the LLN it is desirable to 3746 perform some sort of address and/or header compression, perhaps via 3747 labels, addresses aggregation, or some other means. This is still 3748 under investigation. 3750 Authors' Addresses 3752 Tim Winter (editor) 3754 Email: wintert@acm.org 3756 Pascal Thubert (editor) 3757 Cisco Systems 3758 Village d'Entreprises Green Side 3759 400, Avenue de Roumanille 3760 Batiment T3 3761 Biot - Sophia Antipolis 06410 3762 FRANCE 3764 Phone: +33 497 23 26 34 3765 Email: pthubert@cisco.com 3767 ROLL Design Team 3768 IETF ROLL WG 3770 Email: rpl-authors@external.cisco.com