idnits 2.17.1 draft-ietf-roll-rpl-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Sep 2009 rather than the newer Notice from 28 Dec 2009. (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 (December 7, 2009) is 5251 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) ** Obsolete normative reference: RFC 2460 (Obsoleted by RFC 8200) == 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-11 == Outdated reference: A later version (-09) exists of draft-ietf-roll-building-routing-reqs-08 == Outdated reference: A later version (-11) exists of draft-ietf-roll-home-routing-reqs-09 == Outdated reference: A later version (-19) exists of draft-ietf-roll-routing-metrics-04 == 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 -- Obsolete informational reference (is this intentional?): RFC 3697 (Obsoleted by RFC 6437) Summary: 2 errors (**), 0 flaws (~~), 8 warnings (==), 2 comments (--). 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: June 10, 2010 Cisco Systems 6 ROLL Design Team 7 IETF ROLL WG 8 December 7, 2009 10 RPL: IPv6 Routing Protocol for Low power and Lossy Networks 11 draft-ietf-roll-rpl-05 13 Abstract 15 Low power and Lossy Networks (LLNs) are a class of network in which 16 both the routers and their interconnect are constrained: LLN routers 17 typically operate with constraints on (any subset of) processing 18 power, memory and energy (battery), and their interconnects are 19 characterized by (any subset of) high loss rates, low data rates and 20 instability. LLNs are comprised of anything from a few dozen and up 21 to thousands of LLN routers, and support point-to-point traffic 22 (between devices inside the LLN), point-to-multipoint traffic (from a 23 central control point to a subset of devices inside the LLN) and 24 multipoint-to-point traffic (from devices inside the LLN towards a 25 central control point). This document specifies the IPv6 Routing 26 Protocol for LLNs (RPL), which provides a mechanism whereby 27 multipoint-to-point traffic from devices inside the LLN towards a 28 central control point, as well as point-to-multipoint traffic from 29 the central control point to the devices inside the LLN, is 30 supported. Support for point-to-point traffic is also available. 32 Status of this Memo 34 This Internet-Draft is submitted to IETF in full conformance with the 35 provisions of BCP 78 and BCP 79. 37 Internet-Drafts are working documents of the Internet Engineering 38 Task Force (IETF), its areas, and its working groups. Note that 39 other groups may also distribute working documents as Internet- 40 Drafts. 42 Internet-Drafts are draft documents valid for a maximum of six months 43 and may be updated, replaced, or obsoleted by other documents at any 44 time. It is inappropriate to use Internet-Drafts as reference 45 material or to cite them other than as "work in progress." 47 The list of current Internet-Drafts can be accessed at 48 http://www.ietf.org/ietf/1id-abstracts.txt. 50 The list of Internet-Draft Shadow Directories can be accessed at 51 http://www.ietf.org/shadow.html. 53 This Internet-Draft will expire on June 10, 2010. 55 Copyright Notice 57 Copyright (c) 2009 IETF Trust and the persons identified as the 58 document authors. All rights reserved. 60 This document is subject to BCP 78 and the IETF Trust's Legal 61 Provisions Relating to IETF Documents 62 (http://trustee.ietf.org/license-info) in effect on the date of 63 publication of this document. Please review these documents 64 carefully, as they describe your rights and restrictions with respect 65 to this document. Code Components extracted from this document must 66 include Simplified BSD License text as described in Section 4.e of 67 the Trust Legal Provisions and are provided without warranty as 68 described in the BSD License. 70 Table of Contents 72 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 73 1.1. Design Principles . . . . . . . . . . . . . . . . . . . . 5 74 1.2. Expectations of Link Layer Type . . . . . . . . . . . . . 6 75 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 6 76 3. Protocol Model . . . . . . . . . . . . . . . . . . . . . . . . 8 77 3.1. Instances, DODAGs, and DODAG Iterations . . . . . . . . . 8 78 3.2. Traffic Flows . . . . . . . . . . . . . . . . . . . . . . 10 79 3.2.1. Multipoint-to-Point Traffic . . . . . . . . . . . . . 10 80 3.2.2. Point-to-Multipoint Traffic . . . . . . . . . . . . . 10 81 3.2.3. Point-to-Point Traffic . . . . . . . . . . . . . . . . 10 82 3.3. DODAG Construction . . . . . . . . . . . . . . . . . . . . 11 83 3.3.1. DAG Information Object (DIO) . . . . . . . . . . . . . 11 84 3.3.2. DAG Repair . . . . . . . . . . . . . . . . . . . . . . 11 85 3.3.3. Grounded and Floating DODAGs . . . . . . . . . . . . . 12 86 3.3.4. Administrative Preference . . . . . . . . . . . . . . 12 87 3.3.5. Objective Function (OF) . . . . . . . . . . . . . . . 12 88 3.3.6. Distributed Algorithm Operation . . . . . . . . . . . 13 89 3.4. Destination Advertisement . . . . . . . . . . . . . . . . 13 90 3.4.1. Destination Advertisement Object (DAO) . . . . . . . . 13 91 4. Routing Metrics and Constraints Used By RPL . . . . . . . . . 14 92 5. Rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 93 5.1. Loop Avoidance . . . . . . . . . . . . . . . . . . . . . . 15 94 5.1.1. Greediness and Rank-based Instabilities . . . . . . . 15 95 5.1.2. DODAG Loops . . . . . . . . . . . . . . . . . . . . . 16 96 5.1.3. DAO Loops . . . . . . . . . . . . . . . . . . . . . . 16 97 5.1.4. Sibling Loops . . . . . . . . . . . . . . . . . . . . 16 98 5.2. Rank Properties . . . . . . . . . . . . . . . . . . . . . 16 99 6. RPL Protocol Specification . . . . . . . . . . . . . . . . . . 18 100 6.1. RPL Messages . . . . . . . . . . . . . . . . . . . . . . . 18 101 6.1.1. ICMPv6 RPL Control Message . . . . . . . . . . . . . . 18 102 6.1.2. DAG Information Solicitation (DIS) . . . . . . . . . . 19 103 6.1.3. DAG Information Object (DIO) . . . . . . . . . . . . . 19 104 6.1.4. Destination Advertisement Object (DAO) . . . . . . . . 26 105 6.2. Protocol Elements . . . . . . . . . . . . . . . . . . . . 28 106 6.2.1. Topological Elements . . . . . . . . . . . . . . . . . 28 107 6.2.2. Neighbors, Parents, and Siblings . . . . . . . . . . . 28 108 6.2.3. DODAG Information . . . . . . . . . . . . . . . . . . 29 109 6.3. DAG Discovery and Maintenance . . . . . . . . . . . . . . 30 110 6.3.1. DAG Discovery Rules . . . . . . . . . . . . . . . . . 31 111 6.3.2. DIO Message Communication . . . . . . . . . . . . . . 35 112 6.3.3. DIO Transmission . . . . . . . . . . . . . . . . . . . 36 113 6.3.4. Trickle Timer for DIO Transmission . . . . . . . . . . 37 114 6.4. DAG Selection . . . . . . . . . . . . . . . . . . . . . . 38 115 6.5. Operation as a Leaf Node . . . . . . . . . . . . . . . . . 39 116 6.6. Administrative rank . . . . . . . . . . . . . . . . . . . 39 117 6.7. Collision . . . . . . . . . . . . . . . . . . . . . . . . 39 118 6.8. Establishing Routing State Down the DODAG . . . . . . . . 40 119 6.8.1. Destination Advertisement Operation . . . . . . . . . 41 120 6.9. Loop Detection . . . . . . . . . . . . . . . . . . . . . . 48 121 6.9.1. Source Node Operation . . . . . . . . . . . . . . . . 49 122 6.9.2. Router Operation . . . . . . . . . . . . . . . . . . . 49 123 6.10. Multicast Operation . . . . . . . . . . . . . . . . . . . 51 124 6.11. Maintenance of Routing Adjacency . . . . . . . . . . . . . 52 125 7. Suggestions for Packet Forwarding . . . . . . . . . . . . . . 53 126 8. Guidelines for Objective Functions . . . . . . . . . . . . . . 54 127 9. RPL Constants and Variables . . . . . . . . . . . . . . . . . 56 128 10. Manageability Considerations . . . . . . . . . . . . . . . . . 58 129 10.1. Control of Function and Policy . . . . . . . . . . . . . . 58 130 10.1.1. Initialization Mode . . . . . . . . . . . . . . . . . 58 131 10.1.2. DIO Base option . . . . . . . . . . . . . . . . . . . 58 132 10.1.3. Trickle Timers . . . . . . . . . . . . . . . . . . . . 59 133 10.1.4. DAG Sequence Number Increment . . . . . . . . . . . . 59 134 10.1.5. Destination Advertisement Timers . . . . . . . . . . . 59 135 10.1.6. Policy Control . . . . . . . . . . . . . . . . . . . . 59 136 10.1.7. Data Structures . . . . . . . . . . . . . . . . . . . 60 137 10.2. Information and Data Models . . . . . . . . . . . . . . . 60 138 10.3. Liveness Detection and Monitoring . . . . . . . . . . . . 60 139 10.3.1. Candidate Neighbor Data Structure . . . . . . . . . . 61 140 10.3.2. Directed Acyclic Graph (DAG) Table . . . . . . . . . . 61 141 10.3.3. Routing Table . . . . . . . . . . . . . . . . . . . . 61 142 10.3.4. Other RPL Monitoring Parameters . . . . . . . . . . . 62 143 10.3.5. RPL Trickle Timers . . . . . . . . . . . . . . . . . . 62 144 10.4. Verifying Correct Operation . . . . . . . . . . . . . . . 62 145 10.5. Requirements on Other Protocols and Functional 146 Components . . . . . . . . . . . . . . . . . . . . . . . . 63 147 10.6. Impact on Network Operation . . . . . . . . . . . . . . . 63 148 11. Security Considerations . . . . . . . . . . . . . . . . . . . 63 149 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 63 150 12.1. RPL Control Message . . . . . . . . . . . . . . . . . . . 63 151 12.2. New Registry for RPL Control Codes . . . . . . . . . . . . 63 152 12.3. New Registry for the Control Field of the DIO Base . . . . 64 153 12.4. DAG Information Object (DIO) Suboption . . . . . . . . . . 64 154 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 65 155 14. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 65 156 15. References . . . . . . . . . . . . . . . . . . . . . . . . . . 67 157 15.1. Normative References . . . . . . . . . . . . . . . . . . . 67 158 15.2. Informative References . . . . . . . . . . . . . . . . . . 67 159 Appendix A. Requirements . . . . . . . . . . . . . . . . . . . . 69 160 A.1. Protocol Properties Overview . . . . . . . . . . . . . . . 69 161 A.1.1. IPv6 Architecture . . . . . . . . . . . . . . . . . . 69 162 A.1.2. Typical LLN Traffic Patterns . . . . . . . . . . . . . 69 163 A.1.3. Constraint Based Routing . . . . . . . . . . . . . . . 70 164 A.2. Deferred Requirements . . . . . . . . . . . . . . . . . . 70 165 Appendix B. Examples . . . . . . . . . . . . . . . . . . . . . . 70 166 B.1. Destination Advertisement . . . . . . . . . . . . . . . . 72 167 B.2. Example: DAG Parent Selection . . . . . . . . . . . . . . 73 168 B.3. Example: DAG Maintenance . . . . . . . . . . . . . . . . . 75 169 B.4. Example: Greedy Parent Selection and Instability . . . . . 76 170 Appendix C. Outstanding Issues . . . . . . . . . . . . . . . . . 78 171 C.1. Additional Support for P2P Routing . . . . . . . . . . . . 78 172 C.2. Loop Detection . . . . . . . . . . . . . . . . . . . . . . 78 173 C.3. Destination Advertisement / DAO Fan-out . . . . . . . . . 78 174 C.4. Source Routing . . . . . . . . . . . . . . . . . . . . . . 79 175 C.5. Address / Header Compression . . . . . . . . . . . . . . . 79 176 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 79 178 1. Introduction 180 Low power and Lossy Networks (LLNs) are made largely of constrained 181 nodes (with limited processing power, memory, and sometimes energy 182 when they are battery operated). These routers are interconnected by 183 lossy links, typically supporting only low data rates, that are 184 usually unstable with relatively low packet delivery rates. Another 185 characteristic of such networks is that the traffic patterns are not 186 simply unicast, but in many cases point-to-multipoint or multipoint- 187 to-point. Furthermore such networks may potentially comprise up to 188 thousands of nodes. These characteristics offer unique challenges to 189 a routing solution: the IETF ROLL Working Group has defined 190 application-specific routing requirements for a Low power and Lossy 191 Network (LLN) routing protocol, specified in 192 [I-D.ietf-roll-building-routing-reqs], 193 [I-D.ietf-roll-home-routing-reqs], [RFC5673], and [RFC5548]. This 194 document specifies the IPv6 Routing Protocol for Low power and Lossy 195 Networks (RPL). 197 1.1. Design Principles 199 RPL was designed with the objective to meet the requirements spelled 200 out in [I-D.ietf-roll-building-routing-reqs], 201 [I-D.ietf-roll-home-routing-reqs], [RFC5673], and [RFC5548]. Because 202 those requirements are heterogeneous and sometimes incompatible in 203 nature, the approach is first taken to design a protocol capable of 204 supporting a core set of functionalities corresponding to the 205 intersection of the requirements. As the RPL design evolves optional 206 features may be added to address some application specific 207 requirements. This is a key protocol design decision providing a 208 granular approach in order to restrict the core of the protocol to a 209 minimal set of functionalities, and to allow each implementation of 210 the protocol to be optimized differently. All "MUST" application 211 requirements that cannot be satisfied by RPL will be specifically 212 listed in the Appendix A, accompanied by a justification. 214 A network may run multiple instances of RPL concurrently. Each such 215 instance may serve different and potentially antagonistic constraints 216 or performance criteria. This document defines how a single instance 217 operates. 219 RPL is a generic protocol that is to be deployed by instantiating the 220 generic operation described in this document with a specific 221 objective function (OF) (which ties together metrics, constraints, 222 and an optimization objective) to realize a desired objective in a 223 given environment. 225 A set of companion documents to this specification will provide 226 further guidance in the form of applicability statements specifying a 227 set of operating points appropriate to the Building Automation, Home 228 Automation, Industrial, and Urban application scenarios. 230 1.2. Expectations of Link Layer Type 232 As RPL is a routing protocol, it of course does not rely on any 233 particular features of a specific link layer technology. RPL should 234 be able to operate over a variety of different link layers, including 235 but not limited to low power wireless or PLC (Power Line 236 Communication) technologies. 238 Implementers may find RFC 3819 [RFC3819] a useful reference when 239 designing a link layer interface between RPL and a particular link 240 layer technology. 242 2. Terminology 244 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 245 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 246 "OPTIONAL" in this document are to be interpreted as described in RFC 247 2119 [RFC2119]. 249 This document requires readers to be familiar with the terminology 250 described in `Terminology in Low power And Lossy Networks' 251 [I-D.ietf-roll-terminology]. 253 DAG: Directed Acyclic Graph. A directed graph having the property 254 that all edges are oriented in such a way that no cycles exist. 255 All edges are contained in paths oriented toward and 256 terminating at one or more root nodes. 258 DAG Instance: A DAG Instance is a set of possibly multiple 259 Destination Oriented DAGs. A network may have more than one 260 DAG Instance, and a RPL router can participate to multiple DAG 261 instances. Each DAG Instance operates independently of other 262 DAG Instances. This document describes operation within a 263 single DAG instance. 265 InstanceID: Unique identifier of a DAG Instance. 267 Destination Oriented DAG (DODAG): A DAG rooted at a single 268 destination, which is a node with no outgoing edges. The tuple 269 (InstanceID, DAGID) uniquely identifies a Destination Oriented 270 DAG (DODAG). In the RPL context, a router can can belong to at 271 most one DODAG per DAG Instance. 273 DAGID: The identifier of a DODAG root. The DAGID must be unique 274 within the scope of a DAG Instance in the LLN. 276 DODAG Iteration: A specific sequence number iteration of a DODAG. 278 DAGSequenceNumber: A sequential counter that is incremented by the 279 root to form a new Iteration of a DODAG. A DODAG Iteration is 280 identified uniquely by the (InstanceID, DAGID, 281 DAGSequenceNumber) tuple. 283 DAG parent: A parent of a node within a DAG is one of the immediate 284 successors of the node on a path towards the DAG root. 286 DAG sibling: A sibling of a node within a DAG is defined in this 287 specification to be any neighboring node which is located at 288 the same rank within a DAG. Note that siblings defined in this 289 manner do not necessarily share a common parent. 291 DAG root: A DAG root is a node within the DAG that has no outgoing 292 edges. Because the graph is acyclic, by definition all DAGs 293 must have at least one DAG root and all paths terminate at a 294 DAG root. 296 Sub-DAG The sub-DAG of a node is the set of other nodes in the DAG 297 that might use a path towards the DAG root that contains the 298 node. Nodes in the sub-DAG of a node have a greater rank 299 (although not all nodes of greater rank are in the sub-DAG). 301 Up: Up refers to the direction from leaf nodes towards DODAG roots, 302 following the orientation of the edges within the DODAG. 304 Down: Down refers to the direction from DODAG roots towards leaf 305 nodes, going against the orientation of the edges within the 306 DODAG. 308 OCP: Objective Code Point. The Objective Code Point is used to 309 indicate which Objective Function is in use in a DODAG. The 310 Objective Code Point is further described in 311 [I-D.ietf-roll-routing-metrics]. 313 OF: Objective Function. The Objective Function (OF) defines which 314 routing metrics, optimization objectives, and related functions 315 are in use in a DODAG. The Objective Function is further 316 described in [I-D.ietf-roll-routing-metrics]. 318 Goal: The Goal is a host or set of hosts that satisfy a particular 319 application objective / OF. Whether or not a DODAG can provide 320 connectivity to a goal is a property of the DODAG. For 321 example, a goal might be a host serving as a data collection 322 point, or a gateway providing connectivity to an external 323 infrastructure. 325 Grounded: A DAG is grounded when the root can reach the Goal of the 326 objective function. 328 Floating: A DAG is floating if is not Grounded. A floating DAG is 329 not expected to reach the Goal defined for the OF. 331 As they form networks, LLN devices often mix the roles of `host' and 332 `router' when compared to traditional IP networks. In this document, 333 `host' refers to an LLN device that can generate but does not forward 334 RPL traffic, `router' refers to an LLN device that can forward as 335 well as generate RPL traffic, and `node' refers to any RPL device, 336 either a host or a router. 338 3. Protocol Model 340 The aim of this section is to describe RPL in the spirit of 341 [RFC4101]. Protocol details can be found in further sections. 343 3.1. Instances, DODAGs, and DODAG Iterations 345 Each DAG instance constructs a routing topology optimized for a 346 certain Objective Function (OF). A DAG instance may provide routes 347 to certain destination prefixes. A single DAG instance contains one 348 or more Destination Oriented DAG (DODAG) roots. These roots may 349 operate independently, or may coordinate over a non-LLN backchannel. 351 Each root has a unique identifier, the DAGID, such that nodes can 352 identify the DODAG root. 354 A DAG instance may comprise: 356 o a single DODAG with a single root 358 * For example, a DODAG optimized to minimize latency rooted at a 359 single centralized lighting controller in a home automation 360 application. 362 o multiple uncoordinated DODAGs with independent roots (differing 363 DAGIDs) 364 * For example, multiple data collection points in an urban data 365 collection application that do not have an always-on backbone 366 suitable to coordinate to form a single DODAG, and further use 367 the formation of multiple DODAGs as a means to dynamically and 368 autonomously partition the network. 370 o a single DODAG with a single virtual root coordinating LLN sinks 371 (with the same DAGID) over some non-LLN backbone 373 * For example, multiple border routers operating with a reliable 374 backbone, e.g. in support of a 6LowPAN application, that are 375 capable to act as logically equivalent sinks to the same DODAG. 377 o a combination of one of the above as suited to some application 378 scenario. 380 Traffic is bound to a specific DODAG Instance by a marking in the 381 flow label of the IPv6 header. Traffic originating in support of a 382 particular application may be tagged to follow an appropriate DAG 383 instance, for example to follow paths optimized for low latency or 384 low energy. The provisioning or automated discovery of a mapping 385 between an InstanceID and a type or service of application traffic is 386 beyond the scope of this specification. 388 An example of a DAG Instance comprising a number of DODAGs is 389 depicted in Figure 1. A DODAG Iteration is depicted in Figure 2. 391 +----------------------------------------------------------------+ 392 | | 393 | +--------------+ | 394 | | | | 395 | | (R1) | (R2) (Rn) | 396 | | / \ | /| \ / | \ | 397 | | / \ | / | \ / | \ | 398 | | (A) (B) | (C) | (D) ... (F) (G) (H) | 399 | | /|\ |\ | / | |\ | | | | 400 | | : : : : : | : (E) : : : : : | 401 | | | / \ | 402 | +--------------+ : : | 403 | DODAG | 404 | | 405 +----------------------------------------------------------------+ 406 DAG Instance 408 Figure 1: DAG Instance 410 +----------------+ +----------------+ 411 | | | | 412 | (R1) | | (R1) | 413 | / \ | | / | 414 | / \ | | / | 415 | (A) (B) | \ | (A) | 416 | /|\ |\ | ------\ | /|\ | 417 | : : (C) : : | \ | : : (C) | 418 | | / | \ | 419 | | ------/ | \ | 420 | | / | (B) | 421 | | | |\ | 422 | | | : : | 423 | | | | 424 +----------------+ +----------------+ 425 Sequence N Sequence N+1 427 Figure 2: DODAG Iteration 429 3.2. Traffic Flows 431 3.2.1. Multipoint-to-Point Traffic 433 Multipoint-to-Point (MP2P) is a dominant traffic flow in many LLN 434 applications ([I-D.ietf-roll-building-routing-reqs], 435 [I-D.ietf-roll-home-routing-reqs], [RFC5673], [RFC5548]). The 436 destinations of MP2P flows are designated nodes that have some 437 application significance, such as providing connectivity to the 438 larger Internet or core private IP network. RPL supports MP2P 439 traffic by allowing MP2P destinations to be reached via DODAG roots. 441 3.2.2. Point-to-Multipoint Traffic 443 Point-to-multipoint (P2MP) is a traffic pattern required by several 444 LLN applications ([I-D.ietf-roll-building-routing-reqs], 445 [I-D.ietf-roll-home-routing-reqs], [RFC5673], [RFC5548]). RPL 446 supports P2MP traffic by using a destination advertisement mechanism 447 that provisions routes toward destination prefixes and away from 448 roots. Destination advertisements can update routing tables as the 449 underlying DODAG topology changes. 451 3.2.3. Point-to-Point Traffic 453 RPL DODAGs provide a basic structure for point-to-point (P2P) 454 traffic. For a RPL network to support P2P traffic, a root must be 455 able to route packets to a destination. Nodes within the network may 456 also have routing tables to destinations. A packet flows towards a 457 root until it reaches an ancestor that has a known route to the 458 destination. 460 RPL also supports the case where a P2P destination is a `one-hop' 461 neighbor. 463 RPL neither specifies nor precludes additional mechanisms for 464 computing and installing more optimal routes to support arbitrary P2P 465 traffic. 467 3.3. DODAG Construction 469 RPL provisions routes up towards DODAG roots, forming a DODAG 470 optimized according to the Objective Function (OF) in use. RPL nodes 471 construct and maintain these DODAGs through exchange of DAG 472 Information Object (DIO) messages. Undirected links between siblings 473 are also identified during this process, which are used to provide 474 additional diversity. 476 3.3.1. DAG Information Object (DIO) 478 A DIO identifies the DAG Instance, the DAGID, the values used to 479 compute the DAG Instance's objective function, and the present DODAG 480 Sequence Number. It can also include additional routing and 481 configuration information. The DIO includes a measure derived from 482 the position of the node within the DODAG, the rank, which is used 483 for nodes to determine their positions relative to each other and to 484 inform loop avoidance/detection procedures. RPL exchanges DIO 485 messages to establish and maintain routes. 487 RPL adapts the rate at which nodes send DIO messages. When a DODAG 488 is detected to be inconsistent or needs repair, RPL sends DIO 489 messages more frequently. As the DODAG stabilizes, the DIO message 490 rate tapers off, reducing the maintenance cost of a steady and well- 491 working DODAG. 493 This document defines an ICMPv6 Message Type RPL Control Message, 494 which is capable of carrying a DIO. 496 3.3.2. DAG Repair 498 RPL supports global repair over the DODAG. A DODAG Root may 499 increment the DODAG Sequence Number to institute a global repair, 500 revising the DODAG and allowing nodes to choose an arbitrary new 501 position within the new DODAG iteration. 503 RPL may support mechanisms for local repair within the DODAG 504 iteration. The DIO message will specify the necessary parameters as 505 configured from the DODAG root. Local repair options include the 506 allowing a node, upon detecting a loss of connectivity to a DODAG it 507 is a member of, to: 509 o Poison its sub-DAG by advertising an effective rank of INFINITY, 510 OR detach and form a floating DODAG in order to preserve inner 511 connectivity within its sub-DAG. 513 o Move down the DODAG iteration in a limited manner, no further than 514 a bound configured via the DIO so as not to count all the way to 515 infinity. Such a move may be undertaken after waiting an 516 appropriate poisoning interval, and should allow the node to 517 restore connectivity to the DODAG Iteration if possible. 519 3.3.3. Grounded and Floating DODAGs 521 DODAGs can be grounded or floating. A grounded DODAG offers 522 connectivity to to a goal. A floating DODAG offers no such 523 connectivity, and provides routes only to nodes within the DODAG. 524 Floating DODAGs may be used, for example, to preserve inner 525 connectivity during repair. 527 3.3.4. Administrative Preference 529 An implementation/deployment may specify that some DODAG roots should 530 be used over others through an administrative preference. 531 Administrative preference offers a way to control traffic and 532 engineer DODAG formation in order to better support application 533 requirements or needs. 535 3.3.5. Objective Function (OF) 537 The Objective Function (OF) implements the optimization objectives of 538 route selection within the DAG Instance. The OF is identified by an 539 Objective Code Point (OCP) within the DIO, and its specification also 540 indicates the metrics and constraints in use. The OF also specifies 541 the procedure used to compute rank within a DODAG iteration. Further 542 details may be found in [I-D.ietf-roll-routing-metrics] and related 543 companion specifications. 545 By using defined OFs that are understood by all nodes in a particular 546 implementation, and by referencing them in the DIO message, RPL nodes 547 may work to build optimized LLN routes using a variety of application 548 and implementation specific metrics and goals. 550 In the case where a node is unable to encounter a suitable DAG 551 Instance using a known Objective Function, it may be configured to 552 join DAG Instance using and unknown Objective Function but only 553 acting as a leaf node. 555 3.3.6. Distributed Algorithm Operation 557 A high level overview of the distributed algorithm which constructs 558 the DODAG is as follows: 560 o Some nodes are configured to be DODAG roots, with associated DODAG 561 configuration. 563 o Nodes advertise their presence, affiliation with a DODAG, routing 564 cost, and related metrics by sending link-local multicast DIO 565 messages. 567 o Nodes may adjust the rate at which DIO messages are sent in 568 response to stability or detection of routing inconsistencies. 570 o Nodes listen for DIOs and use their information to join a new 571 DODAG, or to maintain an existing DODAG, as according to the 572 specified Objective Function and rank-based loop avoidance rules. 574 o The nodes provision routing table entries for the destinations 575 specified by the DIO towards their parents in the DODAG iteration. 576 Nodes may provision a parent as a default gateway. 578 o Nodes may identify siblings within the DODAG iteration to increase 579 path diversity. 581 o Using both DIOs and possibly information in data packets, RPL 582 nodes detect possible routing loops. When a RPL node detects a 583 possible routing loop, it may adapt its DIO transmission rate to 584 apply a local repair to the topology. This process and its 585 limitations is discussed in greater detail in 3.4. 587 3.4. Destination Advertisement 589 As RPL constructs and maintains DODAGs with DIO messages to establish 590 upward routes, it may use Destination Advertisement Object (DAO) 591 messages to establish downward routes along the DODAG. DAO messages 592 and support for downward routes are an optional feature for 593 applications that require P2MP or P2P traffic. DIO messages 594 advertise whether the destination advertisement mechanism is enabled. 596 3.4.1. Destination Advertisement Object (DAO) 598 A Destination Advertisement Object (DAO) conveys destination 599 information upwards along the DODAG so that a DODAG root (an other 600 intermediate nodes) can provision downward routes. A DAO message 601 includes prefix information to identify destinations, a capability to 602 record routes in support of source routing, and information to 603 determine the freshness of a particular advertisement. 605 Nodes that are capable of maintaining routing state may aggregate 606 routes from DAO messages that they receive before transmitting a DAO 607 message. Nodes that are not capable to maintain routing state may 608 attach a next-hop address to the Reverse Route Stack contained within 609 the DAO message. The Reverse Route Stack is subsequently used to 610 generate piecewise source routes over regions of the LLN that are 611 incapable of storing downward routing state. 613 A special case of the DAO message, termed a no-DAO, is used to clear 614 downward routing state that has been provisioned through DAO 615 operation. 617 This document defines an ICMPv6 Message Type RPL Control Message, 618 which is capable to carry the DAO. 620 3.4.1.1. `One-Hop' Neighbors 622 In addition to sending DAOs toward DODAG roots, RPL nodes may 623 occasionally emit a link-local multicast DAO message advertising 624 available destination prefixes. This mechanism allow provisioning a 625 trivial `one-hop' route to local neighbors. 627 4. Routing Metrics and Constraints Used By RPL 629 Routing metrics are used by routing protocols to compute the shortest 630 paths. Interior Gateway Protocols (IGPs) such as IS-IS ([RFC5120]) 631 and OSPF ([RFC4915]) use static link metrics. Such link metrics can 632 simply reflect the bandwidth or can also be computed according to a 633 polynomial function of several metrics defining different link 634 characteristics; in all cases they are static metrics. Some routing 635 protocols support more than one metric: in the vast majority of the 636 cases, one metric is used per (sub)topology. Less often, a second 637 metric may be used as a tie-breaker in the presence of Equal Cost 638 Multiple Paths (ECMP). The optimization of multiple metrics is known 639 as an NP complete problem and is sometimes supported by some 640 centralized path computation engine. 642 In contrast, LLNs do require the support of both static and dynamic 643 metrics. Furthermore, both link and node metrics are required. In 644 the case of RPL, it is virtually impossible to define one metric, or 645 even a composite, that will satisfy all use cases. 647 In addition, RPL supports constrained-based routing where constraints 648 may be applied to link and nodes. If a link or a node does not 649 satisfy a required constraint, it is `pruned' from the candidate list 650 thus leading to a constrained shortest path. 652 The set of supported link/node constraints and metrics is specified 653 in [I-D.ietf-roll-routing-metrics]. 655 The role of the Objective Function is to advertise routing metrics 656 and constraints in addition to the objectives used to compute the 657 (constrained) shortest path. 659 Example 1: Shortest path: path offering the shortest end-to-end delay 661 Example 2: Constrained shortest path: the path that does not traverse 662 any battery-operated node and that optimizes the path 663 reliability 665 5. Rank 667 5.1. Loop Avoidance 669 RPL guarantees neither loop free path selection nor strong global 670 convergence. In order to reduce control overhead, however, such as 671 the cost of the count-to-infinity problem, RPL avoids creating loops 672 when undergoing topology changes. Furthermore, RPL includes rank- 673 based mechanisms for detecting loops when they do occur. RPL uses 674 this loop detection to ensure that packets make forward progress 675 within the DODAG iteration and trigger repairs when necessary. 677 5.1.1. Greediness and Rank-based Instabilities 679 Once a node has joined a DODAG, RPL disallows certain behaviors, 680 including greediness, in order to prevent resulting instabilities in 681 the DODAG. 683 If a node is allowed to be greedy and attempts to move deeper in the 684 DODAG, beyond its most preferred parent, in order to increase the 685 size of the parent set, then an instability can result. This is 686 illustrated in Figure 16. 688 Suppose a node is willing to receive and process a DIO messages from 689 a node in its own sub-DAG, and in general a node deeper than it. In 690 such cases a chance exists to create a feedback loop, wherein two or 691 more nodes continue to try and move in the DODAG in order to optimize 692 against each other. In some cases this will result in an 693 instability. It is for this reason that RPL limits the cases where a 694 node may process DIO messages from deeper nodes to some forms of 695 local repair. This approach creates an `event horizon', whereby a 696 node cannot be influenced beyond some limit into an instability by 697 the action of nodes that may be in its own sub-DAG. 699 A further example of the consequences of greedy operation, and 700 instability related to processing DIO messages from nodes of greater 701 rank, may be found in Appendix B.4 703 5.1.2. DODAG Loops 705 A DODAG loop may occur when a node detaches from the DODAG and 706 reattaches to a device in its prior sub-DAG. This may happen in 707 particular when DIO messages are missed. Strict use of the DAG 708 sequence number can eliminate this type of loop, but this type of 709 loop may possibly be encountered when using some local repair 710 mechanisms. 712 5.1.3. DAO Loops 714 A DAO loop may occur when the parent has a route installed upon 715 receiving and processing a DAO message from a child, but the child 716 has subsequently cleaned up the state. This loop happens when a no- 717 DAO was missed until a heartbeat cleans up all states. RPL includes 718 loop detection mechanisms that may mitigate the impact of DAO loops 719 and trigger their repair. 721 In the case where stateless DAO operation is used, i.e. source 722 routing specifies the down routes, then DAO Loops should not occur on 723 the stateless portions of the path. 725 5.1.4. Sibling Loops 727 Sibling loops could occur if a group of siblings kept choosing 728 amongst themselves as successors such that a packet does not make 729 forward progress. This specification limits the number of times that 730 sibling forwarding may be used at a given rank to prevent sibling 731 loops. 733 5.2. Rank Properties 735 The rank of a node is a scalar representation of the location of that 736 node within a DODAG iteration. The rank is used to avoid and detect 737 loops, and as such must demonstrate certain properties. The exact 738 calculation of the rank is left to the Objective Function, and may 739 depend on parents, link metrics, and the node configuration and 740 policies. 742 The rank is not a cost metric, although its value can be derived from 743 and influenced by metrics. The rank has properties of its own that 744 are not necessarily that of all metrics: 746 Type: Rank is an abstract scalar. Some metrics are boolean (e.g. 747 grounded), others are statistical and better expressed as a 748 tuple like an expected value and a variance. Some OCPs use 749 not one but a set of metrics bound by a piece of logic. 751 Function: Rank is the expression of a relative position within a 752 DODAG iteration with regard to neighbors and, not necessarily 753 a good indication or a proper expression of a distance or a 754 cost to the root. 756 Stability: The stability of the rank determines that of the routing 757 topology. Some dampening or filtering might be applied to 758 keep the topology stable and the rank does not necessarily 759 change as fast as some physical metrics would. A new 760 iteration is a good opportunity to reconcile the 761 discrepancies that might form over time between the metrics 762 and the ranks. 764 Granularity: Rank is coarse grained. A fine granularity would 765 prevent the selection of siblings. 767 Properties: Rank is strictly monotonic and can be used to validate a 768 progression from or towards the root. A metric like 769 bandwidth or jitter does not necessarily exhibit such 770 property. 772 Abstract: Rank does not have a physical unit, but rather a range of 773 increment per hop that varies from 1 (best) to 16 (worst), 774 where the assignment of each value is to be determined by the 775 implementation. 777 The rank value feeds back into the DAG parent selection according to 778 the RPL loop-avoidance strategy. Once a parent has been added, and a 779 rank value for the node within the DODAG has been advertised, the 780 nodes further options with regard to DAG parent selection and 781 movement within the DODAG are restricted in favor of loop avoidance. 783 The computation of the DAG rank MUST be done in such a way so as to 784 maintain the following properties for any nodes M and N that are 785 neighbors in the LLN: 787 DAGRank(M) is less than DAGRank(N): In this case, M is probably 788 located in a more preferred position than N in the DODAG with 789 respect to the metrics and optimizations defined by the 790 objective code point. In any fashion, Node M may safely be a 791 DAG parent for Node N without risk of creating a loop. 792 Further, for a node N, all parents in the DAG parent set must 793 be of rank less than self's DAGRank(N). In other words, the 794 rank presented by a node N MUST be greater (deeper) than that 795 presented by any of its parents. 797 DAGRank(M) equals DAGRank(N): In this case M and N are located 798 positions of relatively the same optimality within the DODAG. 799 In some cases, Node M may be used as a successor by Node N, 800 but with related chance of creating a loop that must be 801 detected and broken by some other means. 803 DAGRank(M) is greater than DAGRank(N): In this case, then node M is 804 located in a less preferred position than N in the DODAG with 805 respect to the metrics and optimizations defined by the 806 objective code point. Further, Node (M) may in fact be in 807 Node (N)'s sub-DAG. There is a higher risk to Node (N) 808 selecting Node (M) as a DAG parent, as such a selection may 809 create a loop. 811 As an example, the DAG rank could be computed in such a way so as to 812 closely track ETX when the objective function is to minimize ETX, or 813 latency when the objective function is to minimize latency, or in a 814 more complicated way as appropriate to the objective code point being 815 used within the DODAG. 817 6. RPL Protocol Specification 819 6.1. RPL Messages 821 6.1.1. ICMPv6 RPL Control Message 823 This document defines the RPL Control Message, a new ICMPv6 message. 824 The RPL Control Message has the following general format, in 825 accordance with [RFC4443]: 827 0 1 2 3 828 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 829 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 830 | Type | Code | Checksum | 831 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 832 | | 833 + Message Body + 834 | | 836 Figure 3: RPL Control Message 838 The RPL Control message is an ICMPv6 information message with a 839 requested Type of 155. 841 The Code will be used to identify RPL Control Messages as follows: 843 o 0x01: DAG Information Solicitation (Section 6.1.2) 845 o 0x02: DAG Information Object (Section 6.1.3) 847 o 0x04: Destination Advertisement Object (Section 6.1.4) 849 6.1.2. DAG Information Solicitation (DIS) 851 The DAG Information Solicitation (DIS) message may be used to solicit 852 a DAG Information Object from a RPL node. Its use is analogous to 853 that of a Router Solicitation; a node may use DIS to probe its 854 neighborhood for nearby DAGs. The DAG Information Solicitation 855 carries no additional message body. 857 6.1.3. DAG Information Object (DIO) 859 The DAG Information Object carries a number of metrics and other 860 information that allows a node to discover a DAG Instance, select its 861 DAG parents, and identify its siblings while employing loop avoidance 862 strategies. 864 6.1.3.1. DIO Base 866 The DIO Base is a container option, which is always present, and 867 might contain a number of suboptions. The base option regroups the 868 minimum information set that is mandatory in all cases. 870 0 1 2 3 871 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 872 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 873 |G|D|A|0|0| Prf | Sequence | InstanceID | DAGRank | 874 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 875 | | 876 + + 877 | DAGID | 878 + + 879 | | 880 + + 881 | | 882 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 883 | sub-option(s)... 884 +-+-+-+-+-+-+-+-+-+-+-+-+-+ 886 Figure 4: DIO Base 888 Control Field: The DAG Control Field is currently allocated as 889 follows: 891 Grounded (G): The Grounded (G) flag is set when the DODAG root 892 is a Goal for the OF. 894 Destination Advertisement Trigger (D): The Destination 895 Advertisement Trigger (D) flag is set when the DODAG root 896 or another node in the successor chain decides to trigger 897 the sending of destination advertisements in order to 898 update routing state for the down direction along the 899 DODAG, as further detailed in Section 6.8. Note that the 900 use and semantics of this flag are still under 901 investigation. 903 Destination Advertisement Supported (A): The Destination 904 Supported (A) bit is set when the DODAG root is capable 905 to support the collection of destination advertisement 906 related routing state and enables the operation of the 907 destination advertisement mechanism within the DODAG. 909 DAGPreference (Prf): 3-bit unsigned integer set by the DODAG 910 root to its preference and unchanged at propagation. 911 DAGPreference ranges from 0x00 (least preferred) to 0x07 912 (most preferred). The default is 0 (least preferred). 913 The DAG preference provides an administrative mechanism 914 to engineer the self-organization of the LLN, for example 915 indicating the most preferred LBR. If a node has the 916 option to join a more preferred DODAG while still meeting 917 other optimization objectives, then the node will 918 generally seek to join the more preferred DODAG as 919 determined by the OF. 921 Unassigned bits of the Control Field are considered as 922 reserved. They MUST be set to zero on transmission and MUST be 923 ignored on receipt. 925 Sequence Number: 8-bit unsigned integer set by the DODAG root, 926 incremented according to a policy provisioned at the DODAG 927 root, and propagated with no change down the DODAG. Each 928 increment SHOULD have a value of 1 and may cause a wrap back to 929 zero. 931 InstanceID: 8-bit field indicating the topology instance associated 932 with the DODAG, as provisioned at the DODAG root. 934 DAGRank: 8-bit unsigned integer indicating the DAG rank of the node 935 sending the DIO message. The DAGRank of the DODAG root is 936 ROOT_RANK. DAGRank is further described in Section 6.3. 938 DAGID: 128-bit unsigned integer which uniquely identify a DODAG. 939 This value is set by the DODAG root. The global IPv6 address 940 of the DODAG root can be used. the DAGID MUST be unique per DAG 941 Instance within the scope of the LLN. 943 The following values MUST NOT change during the propagation of DIO 944 messages down the DAG: 945 Grounded (G) 946 Destination Advertisement Supported (A) 947 DAGPreference (Prf) 948 Sequence 949 InstanceID 950 DAGID 951 All other fields of the DIO message may be updated at each hop of the 952 propagation. 954 6.1.3.1.1. DIO Suboptions 956 In addition to the minimum options presented in the base option, 957 several suboptions are defined for the DIO message: 959 6.1.3.1.1.1. Format 960 0 1 2 961 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 962 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 963 | Subopt. Type | Subopt Length | Subopt Data 964 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 966 Figure 5: DIO Suboption Generic Format 968 Suboption Type: 8-bit identifier of the type of suboption. When 969 processing a DIO message containing a suboption for which the 970 Suboption Type value is not recognized by the receiver, the 971 receiver MUST silently ignore the unrecognized option, continue 972 to process the following suboption, correctly handling any 973 remaining options in the message. 975 Suboption Length: 16-bit unsigned integer, representing the length 976 in octets of the suboption, not including the suboption Type 977 and Length fields. 979 Suboption Data: A variable length field that contains data specific 980 to the option. 982 The following subsections specify the DIO message suboptions which 983 are currently defined for use in the DAG Information Object. 985 Implementations MUST silently ignore any DIO message suboptions 986 options that they do not understand. 988 DIO message suboptions may have alignment requirements. Following 989 the convention in IPv6, these options are aligned in a packet such 990 that multi-octet values within the Option Data field of each option 991 fall on natural boundaries (i.e., fields of width n octets are placed 992 at an integer multiple of n octets from the start of the header, for 993 n = 1, 2, 4, or 8). 995 6.1.3.1.1.2. Pad1 997 The Pad1 suboption does not have any alignment requirements. Its 998 format is as follows: 1000 0 1001 0 1 2 3 4 5 6 7 1002 +-+-+-+-+-+-+-+-+ 1003 | Type = 0 | 1004 +-+-+-+-+-+-+-+-+ 1006 Figure 6: Pad 1 1008 NOTE! the format of the Pad1 option is a special case - it has 1009 neither Option Length nor Option Data fields. 1011 The Pad1 option is used to insert one or two octets of padding in the 1012 DIO message to enable suboptions alignment. If more than two octets 1013 of padding is required, the PadN option, described next, should be 1014 used rather than multiple Pad1 options. 1016 6.1.3.1.1.3. PadN 1018 The PadN option does not have any alignment requirements. Its format 1019 is as follows: 1021 0 1 2 1022 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 1023 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 1024 | Type = 1 | Subopt Length | Subopt Data 1025 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 1027 Figure 7: Pad N 1029 The PadN option is used to insert three or more octets of padding in 1030 the DIO message to enable suboptions alignment. For N (N > 2) octets 1031 of padding, the Option Length field contains the value N-3, and the 1032 Option Data consists of N-3 zero-valued octets. PadN Option data 1033 MUST be ignored by the receiver. 1035 6.1.3.1.1.4. DAG Metric Container 1037 The DAG Metric Container suboption may be aligned as necessary to 1038 support its contents. Its format is as follows: 1040 0 1 2 1041 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 1042 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 1043 | Type = 2 | Container Length | DAG Metric Data 1044 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 1046 Figure 8: DAG Metric Container 1048 The DAG Metric Container is used to report aggregated path metrics 1049 along the DODAG. The DAG Metric Container may contain a number of 1050 discrete node, link, and aggregate path metrics as chosen by the 1051 implementer. The Container Length field contains the length in 1052 octets of the DAG Metric Data. The order, content, and coding of the 1053 DAG Metric Container data is as specified in 1055 [I-D.ietf-roll-routing-metrics]. 1057 The DAG Metric Container MUST include the value for the DAG Objective 1058 Code Point. 1060 The processing and propagation of the DAG Metric Container is 1061 governed by implementation specific policy functions. 1063 6.1.3.1.1.5. Destination Prefix 1065 The Destination Prefix suboption does not have any alignment 1066 requirements. Its format is as follows: 1068 0 1 2 3 1069 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 1070 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1071 | Type = 3 | Length |Resvd|Prf|Resvd| 1072 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1073 | Prefix Lifetime | 1074 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1075 | Prefix Length | | 1076 +-+-+-+-+-+-+-+-+ | 1077 | Destination Prefix (Variable Length) | 1078 . . 1079 . . 1080 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1082 Figure 9: DAG Destination Prefix 1084 The Destination Prefix suboption is used when the DODAG root, or 1085 another node located upwards along the DODAG on the path to the DODAG 1086 root, needs to indicate that it offers connectivity to destination 1087 prefixes other than the default. This may be useful in cases where 1088 more than one LBR is operating within the LLN and offering 1089 connectivity to different administrative domains, e.g. a home network 1090 and a utility network. In such cases, upon observing the Destination 1091 Prefixes offered by a particular DODAG, a node MAY decide to join 1092 multiple DODAGs in support of a particular application. 1094 The Length is coded as the length of the suboption in octets, 1095 excluding the Type and Length fields. 1097 Prf is the Route Preference as in [RFC4191]. The reserved fields 1098 MUST be set to zero on transmission and MUST be ignored on receipt. 1100 The Prefix Lifetime is a 32-bit unsigned integer representing the 1101 length of time in seconds (relative to the time the packet is sent) 1102 that the Destination Prefix is valid for route determination. The 1103 lifetime is initially set by the node that owns the prefix and 1104 denotes the valid lifetime for that prefix (similar to 1105 AdvValidLifetime [RFC4861]). The value might be reduced by the 1106 originator and/or en-route nodes that will not provide connectivity 1107 for the whole valid lifetime. A value of all one bits (0xFFFFFFFF) 1108 represents infinity. A value of all zero bits (0x00000000) indicates 1109 a loss of reachability. 1111 The Prefix Length is an 8-bit unsigned integer that indicates the 1112 number of leading bits in the destination prefix. 1114 The Destination Prefix contains Prefix Length significant bits of the 1115 destination prefix. The remaining bits of the Destination Prefix, as 1116 required to complete the trailing octet, are set to 0. 1118 In the event that a DIO message may need to specify connectivity to 1119 more than one destination, the Destination Prefix suboption may be 1120 repeated. 1122 6.1.3.1.1.6. DAG Configuration 1124 The DAG Configuration suboption does not have any alignment 1125 requirements. Its format is as follows: 1127 0 1 2 3 1128 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 1129 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1130 | Type = 4 | Length | DIOIntDoubl. | 1131 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1132 | DIOIntMin. | DIORedun. | MaxRankInc | 1133 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1135 Figure 10: DAG Configuration 1137 The DAG Configuration suboption is used to distribute configuration 1138 information for DAG Operation through the DODAG. The information 1139 communicated in this suboption is generally static and unchanging 1140 within the DODAG, therefore it is not necessary to include in every 1141 DIO. This suboption MAY be included occasionally by the DODAG Root, 1142 and MUST be included in response to a unicast request, e.g. a DAG 1143 Information Solicitation (DIS) message. 1145 The Length is coded as 5. 1147 DIOIntervalDoublings is an 8-bit unsigned integer, configured on the 1148 DODAG root and used to configure the trickle timer governing when DIO 1149 message should be sent within the DODAG. DIOIntervalDoublings is the 1150 number of times that the DIOIntervalMin is allowed to be doubled 1151 during the trickle timer operation. 1153 DIOIntervalMin is an 8-bit unsigned integer, configured on the DODAG 1154 root and used to configure the trickle timer governing when DIO 1155 message should be sent within the DODAG. The minimum configured 1156 interval for the DIO trickle timer in units of ms is 1157 2^DIOIntervalMin. For example, a DIOIntervalMin value of 16ms is 1158 expressed as 4. 1160 DIORedundancyConstant is an 8-bit unsigned integer used to configure 1161 suppression of DIO transmissions. DIORedundancyConstant is the 1162 minimum number of relevant incoming DIOs required to suppress a DIO 1163 transmission. If the value is 0xFF then the suppression mechanism is 1164 disabled. 1166 MaxRankInc, 8-bit unsigned integer, is the DAGMaxRankIncrease. This 1167 is the allowable increase in rank in support of local repair. If 1168 DAGMaxRankIncrease is 0 then this mechanism is disabled. 1170 6.1.4. Destination Advertisement Object (DAO) 1172 The Destination Advertisement Object (DAO) is used to propagate 1173 destination information upwards along the DODAG. The RPL use of the 1174 DAO allows the nodes in the DODAG to provision routing state for 1175 nodes contained in the sub-DAG in support of traffic flowing down 1176 along the DODAG. 1178 0 1 2 3 1179 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 1180 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1181 | DAO Sequence | InstanceID | DAO Rank | 1182 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1183 | DAO Lifetime | 1184 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1185 | Route Tag | 1186 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1187 | Prefix Length | RRCount | | 1188 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 1189 | Prefix (Variable Length) | 1190 . . 1191 . . 1192 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1193 | Reverse Route Stack (Variable Length) | 1194 . . 1195 . . 1196 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1198 Figure 11: The Destination Advertisement Object (DAO) 1200 DAO Sequence: Incremented by the node that owns the prefix for each 1201 new DAO message for that prefix. 1203 InstanceID: 8-bit field indicating the topology instance associated 1204 with the DODAG, as learned from the DIO. 1206 DAO Rank: Set by the node that owns the prefix and first issues the 1207 DAO message to its rank. 1209 DAO Lifetime: 32-bit unsigned integer. The length of time in 1210 seconds (relative to the time the packet is sent) that the 1211 prefix is valid for route determination. A value of all one 1212 bits (0xFFFFFFFF) represents infinity. A value of all zero 1213 bits (0x00000000) indicates a loss of reachability. 1215 Route Tag: 32-bit unsigned integer. The Route Tag may be used to 1216 give a priority to prefixes that should be stored. This may be 1217 useful in cases where intermediate nodes are capable of storing 1218 a limited amount of routing state. The further specification 1219 of this field and its use is under investigation. 1221 Prefix Length: 8-bit unsigned integer. Number of valid leading bits 1222 in the IPv6 Prefix. 1224 RRCount: 8-bit unsigned integer. This counter is used to count the 1225 number of entries in the Reverse Route Stack. A value of `0' 1226 indicates that no Reverse Route Stack is present. 1228 Prefix: Variable-length field containing an IPv6 address or a prefix 1229 of an IPv6 address. The Prefix Length field contains the 1230 number of valid leading bits in the prefix. The bits in the 1231 prefix after the prefix length (if any) are reserved and MUST 1232 be set to zero on transmission and MUST be ignored on receipt. 1234 Reverse Route Stack: Variable-length field containing a sequence of 1235 RRCount (possibly compressed) IPv6 addresses. A node that adds 1236 on to the Reverse Route Stack will append to the list and 1237 increment the RRCount. 1239 6.2. Protocol Elements 1241 6.2.1. Topological Elements 1243 RPL uses four identifiers to track and control the routing topology 1245 o The first is an InstanceID. An InstanceID defines what OF a DAG 1246 uses and may also indicate what destinations are offered. A 1247 network may have multiple InstanceIDs, each of which defines an 1248 independent DAG optimized for a different OF and/or application. 1249 The DAG defined by an InstanceID is called a DAG Instance. 1251 o The second is a DAGID. The scope of a DAGID is a DAG Instance. A 1252 combination of InstanceID and DAGID defines a DODAG. A DAG 1253 Instance may have multiple DODAGs. 1255 o The third value is a DAG Sequence Number. The scope of a DAG 1256 Sequence Number is a DODAG. A DODAG is sometimes reconstructed 1257 from the root, by incrementing the DAGSequenceNumber. A 1258 combination of InstanceID, DAGID, and DAG Sequence Number defines 1259 a DODAG Iteration. 1261 o The fourth value is rank. The scope of rank is a DODAG Iteration. 1262 Rank establishes a partial order over a DODAG Iteration, defining 1263 individual node positions. 1265 6.2.2. Neighbors, Parents, and Siblings 1267 1. A node that is not a DODAG root MAY maintain multiple DAG parents 1268 for a single DAG Instance. 1270 2. The set of DAG parents MUST be a conceptual subset of the set of 1271 candidate neighbors. (This does not dictate implementation, 1272 e.g., to use a certain data structure). 1274 3. If Neighbor Unreachability Detection (NUD), or an equivalent 1275 mechanism, determines that a neighbor is no longer reachable, 1276 then a RPL node MUST NOT consider this node in the neighbor set 1277 when calculating and advertising routes until the node determines 1278 it is reachable again. 1280 4. Routes via that unreachable neighbor MUST be eliminated from the 1281 routing table, and the node SHOULD poison using no-DAO all DAO 1282 routes that it has advertised via DAO and that it can reach only 1283 via that neighbor. 1285 A node's neighbor set is an unconstrained subset of the nodes that it 1286 can reach with a link-local multicast. 1288 The OF guides in the selection and maintains a number of neighbors to 1289 interact with, which neighbors being qualified as statistically 1290 stable and presenting adequate properties as per the the OF logic, 1291 for instance following mechanisms discussed in 1292 [I-D.ietf-roll-routing-metrics]. Those neighbors are referred to as 1293 candidate neighbors. 1295 Candidate neighbors may take the role of Parent or Siblings, in part 1296 as determined by rank. 1298 For the purpose of inheriting metrics and computing rank, the OF 1299 might select one preferred parent. In that case, the rank of this 1300 node is computed as the rank of the preferred parent plus a rank 1301 increment as determined by the OF. 1303 6.2.3. DODAG Information 1305 For each DODAG that a node is, or may become, a member of, the 1306 implementation should conceptually keep track of the following 1307 information for each DODAG. The data structures described in this 1308 section are intended to illustrate a possible implementation to aid 1309 in the description of the protocol, but are not intended to be 1310 normative. 1312 o InstanceID 1314 o DAGID 1316 o DAGSequenceNumber 1318 o DAG Metric Container, including DAGObjectiveCodePoint 1319 o A set of Destination Prefixes offered upwards along the DODAG 1321 o A set of DAG parents 1323 o A set of DAG siblings 1325 o A timer to govern the sending of DIO messages 1327 When the DAG parent set is depleted on a node that is not a root, 1328 (i.e. the last parent is removed), then the DAG information should 1329 not be suppressed until after the expiration of an implementation- 1330 specific local timer in order to observe that the DAGSequenceNumber 1331 has incremented should any new parents appear for the DODAG. 1333 6.2.3.1. DAG Parents/Siblings Structure 1335 When the DODAG is self-rooted, the set of DAG parents is empty. 1337 For each node in a DAG parent/sibling set, the implementation should 1338 conceptually keep track of: 1340 o a reference to the neighboring device which is the DAG parent/ 1341 sibling 1343 o a record of most recent information taken from the DAG Information 1344 Object last processed in the case where the neighboring device is 1345 a DAG parent 1347 DAG parents may be ordered, according to the OF. When ordering DAG 1348 parents, in consultation with the OF, the most preferred DAG parent 1349 may be identified. All current DAG parents must have a rank less 1350 than self. All current DAG siblings must have a rank equal to self. 1352 When nodes are added to or removed from the DAG parent/sibling sets 1353 the most preferred DAG parent may have changed. The role of all the 1354 nodes in the list should be reevaluated. In particular, any nodes 1355 having a rank greater than self after such a change must be evicted 1356 from the set. 1358 6.3. DAG Discovery and Maintenance 1360 DAG discovery allows a node to join a DODAG rooted at a DODAG root by 1361 discovering neighbors that are members of the DODAG, and identifying 1362 a set of parents. DAG discovery also identifies siblings, which may 1363 be used later to provide additional path diversity towards the DODAG 1364 root. 1366 DODAG discovery may avoid loops by constraining how and when nodes 1367 can increase their rank, and by statistically poisoning the nodes 1368 that present the highest risk. 1370 DAG discovery enables nodes to implement different policies for 1371 selecting their DAG parents in the DODAG by using implementation 1372 specific policy functions. DAG discovery specifies a set of rules to 1373 be followed by all implementations to enable interoperation. 1375 6.3.1. DAG Discovery Rules 1377 The following rules define the RPL DAG Discovery procedures: 1379 6.3.1.1. DODAG Iteration 1381 1. An InstanceID SHOULD be administratively provisioned on a DODAG 1382 root that is significant RPL objective. The InstanceID MUST be 1383 unique to that purpose across the scope of the LLN. 1385 2. A DAGID MUST be unique within the scope of the InstanceID. It 1386 MAY be derived from the IPv6 address of the DODAG root. 1388 3. A node MAY belong to multiple DAG instances. The related 1389 details of operation are outside the scope of this 1390 specification. 1392 4. DODAG roots MAY increment the DAGSequenceNumber that they 1393 advertise. 1395 5. When a DODAG root increments its DAGSequenceNumber, it MUST 1396 follow the conventions of Serial Number Arithmetic as described 1397 in [RFC1982]. 1399 6. The tuple (InstanceID, DAGID, DAGSequenceNumber) uniquely 1400 defines a DODAG Iteration. All of a node's parents within a 1401 DODAG MUST belong to the same DODAG iteration, as conveyed by 1402 the last heard DIO from each parent. 1404 7. A node MUST NOT propagate DIOs for a DODAG Iteration unless it 1405 is the DODAG root of the DODAG iteration or has selected DODAG 1406 parents in that DODAG iteration. 1408 8. A node acting as a leaf SHOULD NOT propagate DIOs for a DODAG 1409 Iteration. 1411 9. A node MUST belong at most to one DODAG Iteration per 1412 InstanceID. 1414 10. Within a given DODAG, a node that is a not a root MUST NOT 1415 advertise a DAGSequenceNumber higher than the highest 1416 DAGSequenceNumber it has heard. 1418 Within a particular implementation, a DODAG root may increment the 1419 DAGSequenceNumber periodically, at a rate that depends on the 1420 deployment. In other implementations loop detection may be 1421 considered sufficient to solve the routing issues, and the DODAG root 1422 may increment the DAGSequenceNumber only upon administrative 1423 intervention. Another possibility is that nodes within the LLN have 1424 some means to signal the DODAG root in order to request an on-demand 1425 increment when routing issues are detected. 1427 As the DAGSequenceNumber is incremented, a new DODAG Iteration 1428 spreads outward from the DODAG root. Thus a parent that advertises 1429 the new DAGSequenceNumber can not possibly belong to the sub-DAG of a 1430 node that still advertises an older DAGSequenceNumber. A node may 1431 safely add such a parent, without risk of forming a loop, without 1432 regard to its relative rank in the prior DODAG Iteration. This is 1433 equivalent to jumping to a different DODAG. 1435 As a node transitions to new DODAG Iterations as a consequence of 1436 following these rules, the node will be unable to advertise the 1437 previous DODAG Iteration (prior DAGSequenceNumber) once it has 1438 committed to advertising the new DODAG Iteration. 1440 During a transition to a new DODAG Iteration, a node may decide to 1441 forward packets via 'future parents' that belong to the same DODAG 1442 (same InstanceID and DAGID), but are observed to advertise a more 1443 recent (incremented) DAGSequenceNumber. 1445 6.3.1.2. DODAG Roots 1447 1. A DODAG root that does not have connectivity to a network outside 1448 of the LLN MUST NOT set the Grounded bit. 1450 2. A DODAG root MUST advertise a rank of ROOT_RANK. 1452 3. A node that does not have any DODAG parent MAY become the DODAG 1453 root of a floating DODAG. It MAY also set its DAGPreference such 1454 that it is less preferred. This behavior may be a desired 1455 alternate to poisoning. 1457 An LLN node that is a Goal for the Objective Function is the root of 1458 its own grounded DODAG, at rank ROOT_RANK. 1460 In a deployment that uses a backbone link to federate a number of LLN 1461 roots, it is possible to run RPL over the backbone and use one router 1462 as a backbone root. The backbone root is the virtual root of the 1463 DODAG and exposes a rank of BASE_RANK over the backbone. All the LLN 1464 roots that are parented to that backbone root, including the backbone 1465 root if it also serves as LLN root, expose a rank of ROOT_RANK over 1466 the LLN and are part of the same DODAG, coordinated with the virtual 1467 root over the backbone. 1469 6.3.1.3. Rank and Movement within a DODAG Iteration 1471 1. A node MUST NOT advertise a rank less than or equal to any member 1472 of its parent set within the DODAG Iteration. 1474 2. A node MAY advertise a rank lower than its prior advertisement 1475 within the DODAG Iteration. (This corresponds to a node moving 1476 up within the DODAG Iteration). 1478 3. Let L be the lowest rank within a DODAG iteration that a given 1479 node has advertised. Within a DODAG Iteration, that node MUST 1480 NOT advertise an effective rank deeper than L + 1481 DAGMaxRankIncrease. INFINITE_RANK is an exception to this rule: 1482 a node MAY advertise an INFINITE_RANK at any time. (This 1483 corresponds to a limited rank increase for the purpose of local 1484 repair within the DODAG Iteration.) 1486 4. A node MAY, at any time, choose to join a different DODAG within 1487 a DAG Instance. Such a join has no rank restrictions, unless 1488 that different DODAG is a DODAG Iteration that the node has been 1489 a prior member of, in which case the rule of the previous bullet 1490 (3) must be observed. Until a node transmits a DIO indicating 1491 its new DODAG membership, it MUST forward packets along the 1492 previous DODAG. 1494 5. A node MAY, at any time after hearing the next DAGSequenceNumber 1495 Iteration advertised from suitable parents, choose to migrate up 1496 to the next DODAG Iteration within the DODAG. 1498 Conceptually, an implementation is maintaining a parent set within 1499 the DODAG Iteration. Movement entails changes to the parent set. 1500 Moving up does not present the risk to create a loop but moving down 1501 might, so that operation is subject to additional constraints. 1503 When a node migrates into the next DODAG Iteration, the parent and 1504 sibling sets need to be rebuilt for the new iteration. An 1505 implementation could defer to migrate until for some reasonable time 1506 to see if some other neighbors with potentially better metrics but 1507 higher rank announce themselves. Similarly, when a node jumps into a 1508 new DODAG it needs to construct new parent/sibling sets for the new 1509 DODAG. 1511 When a node moves to improve its position, it must conceptually 1512 abandon all parents and siblings with a rank larger than itself. As 1513 a consequence of the movement it may also add new siblings. Such a 1514 movement may occur at any time to decrease the rank, as per the 1515 calculation indicated by the OF. Maintenance of the parent and 1516 sibling sets occurs as the rank of candidate neighbors is observed as 1517 reported in their DIOs. 1519 If a node needs to move down a DODAG that it is attached to, causing 1520 the DAG rank to increase, then it MAY poison its routes and delay 1521 before moving as described in Section 6.3.1.4. 1523 6.3.1.4. Poisoning a Broken Path 1525 1. A node MAY poison, in order to avoid being used as an ancestor by 1526 the nodes in its sub-DAG, by advertising an effective rank of 1527 INFINITE_RANK and resetting the associated DIO trickle timer to 1528 cause the INFINITE_RANK to be announced promptly. 1530 2. The node MAY advertise an effective rank of INFINITE_RANK for an 1531 arbitrary number of DIO timer events before announcing a new 1532 rank. 1534 3. As per Section 6.3.1.3, the node MUST advertise INFINITE_RANK 1535 within the DODAG iteration if its revised rank would exceed the 1536 maximum DAG rank increase. 1538 An implementation may choose to employ this poisoning mechanism when 1539 a node that loses all of its current parents, i.e. the set of DAG 1540 parents becomes depleted, and it can not jump onto an alternate DODAG 1541 An alternate mechanism is to form a floating DODAG. 1543 The motivation for delaying announcement of the revised route through 1544 multiple DIO events is to (i) increase tolerance to DIO loss, (ii) 1545 allow time for the poisoning action to propagate, and (iii) to 1546 develop an accurate assessment of its new rank. Such gains are 1547 obtained at the expense of potentially increasing the delay before 1548 lower portions of the network are able to re-establish up routes. 1549 Path redundancy in the DAG reduces the significance of either effect, 1550 since children with alternate parents should be able to utilize those 1551 alternates and retain rank while the detached parent re-establishes 1552 its rank. 1554 Although an implementation may advertise INFINITE_RANK for the 1555 purposes of poisoning, it is not expected to be equivalent to setting 1556 the rank to INFINITE_RANK, and an implementation would likely retain 1557 its rank value prior to the poisoning in some form, for purpose of 1558 maintaining its effective position within (L + DAGMaxRankIncrease). 1560 6.3.1.5. Detaching 1562 1. A node that does not have a solution to stay connected to a DODAG 1563 within a given iteration MAY detach from its current DODAG 1564 iteration. A node that detaches becomes root of its own floating 1565 DODAG and SHOULD immediately advertise its new situation in a DIO 1566 as an alternate to poisoning. 1568 6.3.1.6. Following a Parent 1570 1. If a node receives a DIO from one of its parents indicating that 1571 the parent has left the DODAG, it SHOULD stay in its current 1572 DODAG through an alternate DAG parent if that is possible. It 1573 MAY follow that parent. 1575 A DAG parent may have moved, migrated forward into the next DODAG 1576 Iteration, or jumped to a different DODAG. A node should give some 1577 preference to remaining in the current DODAG if possible, but ought 1578 to follow the parent if there are no other options. 1580 6.3.2. DIO Message Communication 1582 When an DIO message is received from a source device named SRC, the 1583 receiving node must first determine whether or not the DIO message 1584 should be accepted for further processing, and subsequently present 1585 the DIO message for further processing if eligible. 1587 1. If the DIO message is malformed, then the DIO message is not 1588 eligible for further processing and is silently discarded. A RPL 1589 implementation MAY log the reception of a malformed DIO message. 1591 2. If SRC is a member of the candidate neighbor set, then the DIO is 1592 eligible for further processing. 1594 6.3.2.1. DIO Message Processing 1596 If the node has sent an DIO message within the risk window as 1597 described in Section 6.7 then a collision has occurred; do not 1598 process the DIO message any further. 1600 Process the DIO message as per the rules in Section 6.3 1602 As DIO messages are received from candidate neighbors, the neighbors 1603 may be promoted to DAG parents by following the rules of DAG 1604 discovery as described in Section 6.3. When a node places a neighbor 1605 into the DAG Parent set, the node becomes attached to the DODAG 1606 through the new parent node. 1608 In the DAG discovery implementation, the most preferred parent should 1609 be used to restrict which other nodes may become DAG parents. Some 1610 nodes in the DAG parent set may be of a rank less than or equal to 1611 the most preferred DAG parent. (This case may occur, for example, if 1612 an energy constrained device is at a lesser rank but should be 1613 avoided as per an optimization objective, resulting in a more 1614 preferred parent at a greater rank). 1616 6.3.3. DIO Transmission 1618 Each node maintains a timer that governs when to multicast DIO 1619 messages. This timer is a trickle timer, as detailed in 1620 Section 6.3.4. The DIO Configuration Option includes the 1621 configuration of a DAG Instance's trickle timer. 1623 o When a node detects or causes an inconsistency, it MUST reset the 1624 interval of the trickle timer to a minimum value. 1626 o When a node migrates to a new DODAG Iteration it MUST reset the 1627 trickle timer to its minimum value 1629 o When a node detects an inconsistency when forwarding a packet, as 1630 detailed in Section 6.9, the node MUST reset the trickle timer to 1631 its minimum value. 1633 o When a node receives a multicast DIS message, it MUST reset the 1634 trickle timer to the minimum value. 1636 o When a node receives a unicast DIS message, it MUST unicast a DIO 1637 message in response, and include the DAG Configuration Object. In 1638 this case the node SHOULD NOT reset the trickle timer. 1640 o If a node is not a member of a DODAG, it MUST suppress 1641 transmitting DIO messages. 1643 o When a node is initialized, it MAY be configured to remain silent 1644 and not multicast any DIO messages until it has encountered and 1645 joined a DODAG (perhaps initially probing for a nearby DODAG with 1646 an DIS message). Alternately, it may choose to root its own 1647 floating DODAG and begin multicasting DIO messages using a default 1648 trickle configuration. The second case may be advantageous if it 1649 is desired for independent nodes to begin aggregating into 1650 scattered floating DODAGs in the absence of a grounded node, for 1651 example in support of LLN installation and commissioning. 1653 6.3.4. Trickle Timer for DIO Transmission 1655 RPL treats the construction of a DODAG as a consistency problem, and 1656 uses a trickle timer [Levis08] to control the rate of control 1657 broadcasts. 1659 For each DODAG that a node is part of, the node must maintain a 1660 single trickle timer. The required state contains the following 1661 conceptual items: 1663 I: The current length of the communication interval 1665 T: A timer with a duration set to a random value in the range 1666 [I/2, I] 1668 C: Redundancy Counter 1670 I_min: The smallest communication interval in milliseconds. This 1671 value is learned from the DIO message as (2^DIOIntervalMin)ms. 1672 The default value is DEFAULT_DIO_INTERVAL_MIN. 1674 I_doublings: The number of times I_min should be doubled before 1675 maintaining a constant rate, i.e. I_max = I_min * 1676 2^I_doublings. This value is learned from the DIO message as 1677 DIOIntervalDoublings. The default value is 1678 DEFAULT_DIO_INTERVAL_DOUBLINGS. 1680 6.3.4.1. Resetting the Trickle Timer 1682 The trickle timer for a DODAG is reset by: 1684 1. Setting I_min and I_doublings to the values learned from the DIO 1685 message. 1687 2. Setting C to zero. 1689 3. Setting I to I_min. 1691 4. Setting T to a random value as described above. 1693 5. Restarting the trickle timer to expire after a duration T 1695 When a node learns about a DODAG through a DIO message and makes the 1696 decision to join it, it initializes the state of the trickle timer by 1697 resetting the trickle timer and listening. Each time it hears a 1698 redundant DIO message for this DODAG, it MAY increment C. The exact 1699 determination of redundant is left to an implementation; it could 1700 include DIOs that advertise the same rank. 1702 When the timer fires at time T, the node compares C to the redundancy 1703 constant, DIORedundancyConstant. If C is less than that value, or if 1704 the DIORedundancyConstant value is 0xFF, the node generates a new DIO 1705 message and multicasts it. When the communication interval I 1706 expires, the node doubles the interval I so long as it has previously 1707 doubled it fewer than I_doubling times, resets C, and chooses a new T 1708 value. 1710 6.3.4.2. Determination of Inconsistency 1712 The trickle timer is reset whenever an inconsistency is detected 1713 within the DODAG, for example: 1715 o The node joins a new DODAG 1717 o The node moves within a DODAG 1719 o The node receives a modified DIO message from a DAG parent 1721 o A DAG parent forwards a packet intended to move up, indicating an 1722 inconsistency and possible loop. 1724 o A metric communicated in the DIO message is determined to be 1725 inconsistent, as according to a implementation specific path 1726 metric selection engine. 1728 o The rank of a DAG parent has changed. 1730 6.4. DAG Selection 1732 The DAG selection is implementation and algorithm dependent. Nodes 1733 SHOULD prefer to join DODAGs for InstanceIDs advertising OCPs and 1734 destinations compatible with their implementation specific 1735 objectives. In order to limit erratic movements, and all metrics 1736 being equal, nodes SHOULD keep their previous selection. Also, nodes 1737 SHOULD provide a means to filter out a parent whose availability is 1738 detected as fluctuating, at least when more stable choices are 1739 available. 1741 When connection to a fixed network is not possible or preferable for 1742 security or other reasons, scattered DODAGs MAY aggregate as much as 1743 possible into larger DODAGs in order to allow connectivity within the 1744 LLN. 1746 A node SHOULD verify that bidirectional connectivity and adequate 1747 link quality is available with a candidate neighbor before it 1748 considers that candidate as a DAG parent. 1750 6.5. Operation as a Leaf Node 1752 In some cases it a RPL node may attach to a DODAG for DAG Instance as 1753 a leaf node only; the node in this case is not to extend connectivity 1754 to the DODAG to other nodes under any circumstances. Such a case may 1755 occur, for example, when a node is attaching to a DODAG that is using 1756 an unknown Objective Function. When operating as a leaf node, a 1757 node: 1759 1. MAY receive and process DIOs for that DODAG 1761 2. SHOULD NOT transmit DIOs for that DODAG 1763 3. MUST NOT transmit DIOs containing the DAG Metric Container for 1764 that DODAG 1766 4. MAY transmit unicast DAOs to the chosen parents for that DODAG 1768 5. MAY transmit multicast DAOs to the `1 hop' neighborhood. 1770 6.6. Administrative rank 1772 When the DODAG is formed under a common administration, or when a 1773 node performs a certain role within a community, it might be 1774 beneficial to associate a range of acceptable rank with that node. 1775 For instance, a node that has limited battery should be a leaf unless 1776 there is no other choice, and may then augment the rank computation 1777 specified by the OF in order to expose an exaggerated rank. 1779 6.7. Collision 1781 A race condition occurs if 2 nodes send DIO messages at the same time 1782 and then attempt to join each other. This might happen, for example, 1783 between nodes which act as DAG root of their own DODAGs. In order to 1784 detect the situation, LLN Nodes time stamp the sending of DIO 1785 message. Any DIO message received within a short link-layer- 1786 dependent period introduces a risk. It left to the implementation to 1787 define the duration of the risk window. 1789 There is risk of a collision when a node receives and processes a DIO 1790 within the risk window. For example, it may occur that two nodes are 1791 associated with different DODAGs and near-simultaneously send DIO 1792 messages, which are received and processed by both, and possibly 1793 result in both nodes simultaneously deciding to attach to each other. 1794 As a remedy, in the face of a potential collision, as determined by 1795 receiving a DIO within the risk window, the DIO message is not 1796 processed. It is expected that subsequent DIOs would not cross. 1798 6.8. Establishing Routing State Down the DODAG 1800 The destination advertisement mechanism supports the dissemination of 1801 routing state required to support traffic flows down along the DODAG, 1802 from the DODAG root toward nodes. 1804 As a result of destination advertisement operation: 1806 o Destination advertisement establishes down routes along the DODAG. 1807 Such paths consist of: 1808 * Hop-By-Hop routing state within islands of `stateful' nodes. 1809 * Source Routing `bridges' across nodes that do not retain state. 1811 Destinations disseminated with the destination advertisement 1812 mechanism may be prefixes, individual hosts, or multicast listeners. 1813 The mechanism supports nodes of varying capabilities as follows: 1815 o When nodes are capable of storing routing state, they may inspect 1816 destination advertisements and learn hop-by-hop routing state 1817 toward destinations by populating their routing tables with the 1818 routes learned from nodes in their sub-DAG. In this process they 1819 may also learn necessary piecewise source routes to traverse 1820 regions of the LLN that do not maintain routing state. They may 1821 perform route aggregation on known destinations before emitting 1822 Destination Advertisements. 1824 o When nodes are incapable of storing routing state, they may 1825 forward destination advertisements, recording the reverse route as 1826 the go in order to support the construction of piecewise source 1827 routes. 1829 Nodes that are capable of storing routing state, and finally the 1830 DODAG roots, are able to learn which destinations are contained in 1831 the sub-DAG below the node, and via which next-hop neighbors. The 1832 dissemination and installation of this routing state into nodes 1833 allows for Hop-By-Hop routing from the DODAG root down the DODAG. 1834 The mechanism is further enhance by supporting the construction of 1835 source routes across stateless `gaps' in the DODAG, where nodes are 1836 incapable of storing additional routing state. An adaptation of this 1837 mechanism allows for the implementation of loose-source routing. 1839 A special case, the reception of a destination advertisement 1840 addressed to a link-local multicast address, allows for a node to 1841 learn destinations directly available from its one-hop neighbors. 1843 A design choice behind advertising routes via destination 1844 advertisements is not to synchronize the parent and children 1845 databases along the DODAG, but instead to update them regularly to 1846 recover from the loss of packets. The rationale for that choice is 1847 time variations in connectivity across unreliable links. If the 1848 topology can be expected to change frequently, synchronization might 1849 be an excessive goal in terms of exchanges and protocol complexity. 1850 The approach used here results in a simple protocol with no real 1851 peering. The destination advertisement mechanism hence provides for 1852 periodic updates of the routing state, similarly to other protocols 1853 such as RIP [RFC2453]. 1855 6.8.1. Destination Advertisement Operation 1857 6.8.1.1. Overview 1859 According to implementation specific policy, a subset or all of the 1860 feasible parents in the DODAG may be selected to receive prefix 1861 information from the destination advertisement mechanism. This 1862 subset of DAG parents shall be designated the set of DA parents. 1864 As DAO messages for particular destinations move up the DODAG, a 1865 sequence counter is used to guarantee their freshness. The sequence 1866 counter is incremented by the source of the DAO message (the node 1867 that owns the prefix, or learned the prefix via some other means), 1868 each time it issues a DAO message for its prefix. Nodes that receive 1869 the DAO message and, if scope allows, will be forwarding a DAO 1870 message for the unmodified destination up the DODAG, will leave the 1871 sequence number unchanged. Intermediate nodes will check the 1872 sequence counter before processing a DAO message, and if the DAO is 1873 unchanged (the sequence counter has not changed), then the DAO 1874 message will be discarded without additional processing. Further, if 1875 the DAO message appears to be out of synch (the sequence counter is 2 1876 or more behind the present value) then the DAO state is considered to 1877 be stale and may be purged, and the DAO message is discarded. The 1878 rank is also added for tracking purposes; nodes that are storing 1879 routing state may use it to determine which possible next-hops for 1880 the destination are more optimal. 1882 If destination advertisements are activated in the DIO message as 1883 indicated by the `D' bit, the node sends unicast destination 1884 advertisements to one of its DA parents, that is selected as most 1885 favored for incoming down traffic. The node only accepts unicast 1886 destination advertisements from any nodes but those contained in the 1887 DA parent subset. 1889 Receiving a DIO message with the `D' destination advertisement bit 1890 set from a DAG parent stimulates the sending of a delayed destination 1891 advertisement back, with the collection of all known prefixes (that 1892 is the prefixes learned via destination advertisements for nodes 1893 lower in the DODAG, and any connected prefixes). If the Destination 1894 Advertisement Supported (A) bit is set in the DIO message for the 1895 DODAG, then a destination advertisement is also sent to a DAG parent 1896 once it has been added to the DA parent set after a movement, or when 1897 the list of advertised prefixes has changed. 1899 A node that modifies its DAG Parent set may set the `D' bit in 1900 subsequent DIO propagation in order to trigger destination 1901 advertisements to be updated to its DAG Parents and other ancestors 1902 on the DODAG. Additional recommendations and guidelines regarding 1903 the use of this mechanism are still under consideration and will be 1904 elaborated in a future revision of this specification. 1906 Destination advertisements may advertise positive (prefix is present) 1907 or negative (removed) DAO messages, termed as no-DAOs. A no-DAO is 1908 stimulated by the disappearance of a prefix below. This is 1909 discovered by timing out after a request (a DIO message) or by 1910 receiving a no-DAO. A no-DAO is a conveyed as a DAO message with a 1911 DAO Lifetime of ZERO_LIFETIME. 1913 A node that is capable of recording the state information conveyed in 1914 a unicast DAO message will do so upon receiving and processing the 1915 DAO message, thus provisioning routing state concerning destinations 1916 located downwards along the DODAG. If a node capable of recording 1917 state information receives a DAO message containing a Reverse Route 1918 Stack, then the node knows that the DAO message has traversed one or 1919 more nodes that did not retain any routing state as it traversed the 1920 path from the DAO source to the node. The node may then extract the 1921 Reverse Route Stack and retain the included state in order to specify 1922 Source Routing instructions along the return path towards the 1923 destination. The node MUST set the RRCount back to zero and clear 1924 the Reverse Route Stack prior to passing the DAO message information 1925 on. 1927 A node that is unable to record the state information conveyed in the 1928 DAO message will append the next-hop address to the Reverse Route 1929 Stack, increment the RRCount, and then pass the destination 1930 advertisement on without recording any additional state. In this way 1931 the Reverse Route Stack will contain a vector of next hops that must 1932 be traversed along the reverse path that the DAO message has 1933 traveled. The vector will be ordered such that the node closest to 1934 the destination will appear first in the list. In such cases, if it 1935 is useful to the implementation to try and provision redundant paths, 1936 the node may choose to convey the destination advertisement to one or 1937 more DAG parents in order of preference as guided by an 1938 implementation specific policy. 1940 In certain cases (called hybrid cases), some nodes along the path a 1941 destination advertisement follows up the DODAG may store state and 1942 some may not. The destination advertisement mechanism allows for the 1943 provisioning of routing state such that when a packet is traversing 1944 down the DODAG, some nodes may be able to directly forward to the 1945 next hop, and other nodes may be able to specify a piecewise source 1946 route in order to bridge spans of stateless nodes within the path on 1947 the way to the desired destination. 1949 In the case where no node is able to store any routing state as 1950 destination advertisements pass by, and the DAG root ends up with DAO 1951 messages that contain a completely specified route back to the 1952 originating node in the form of the inverted Reverse Route Stack. A 1953 DAG root should not request (Destination Advertisement Trigger) nor 1954 indicate support (Destination Advertisement Supported) for 1955 destination advertisements if it is not able to store the Reverse 1956 Route Stack information in this case. 1958 The destination advertisement mechanism requires stateful nodes to 1959 maintain lists of known prefixes. A prefix entry contains the 1960 following abstract information: 1962 o A reference to the ND entry that was created for the advertising 1963 neighbor. 1965 o The IPv6 address and interface for the advertising neighbor. 1967 o The logical equivalent of the full destination advertisement 1968 information (including the prefixes, depth, and Reverse Route 1969 Stack, if any). 1971 o A 'reported' Boolean to keep track whether this prefix was 1972 reported already, and to which of the DA parents. 1974 o A counter of retries to count how many DIO messages were sent on 1975 the interface to the advertising neighbor without reachability 1976 confirmation for the prefix. 1978 Note that nodes may receive multiple information from different 1979 neighbors for a specific destination, as different paths through the 1980 DODAG may be propagating information up the DODAG for the same 1981 destination. A node that is recording routing state will keep track 1982 of the information from each neighbor independently, and when it 1983 comes time to propagate the DAO message for a particular prefix to 1984 the DA parents, then the DAO information will be selected from among 1985 the advertising neighbors who offer the least depth to the 1986 destination. 1988 When a node loses connectivity to a child that is used as next hop 1989 for a route learned from a DAO, the node should cleanup all routes 1990 and DAO states that are related to that child. If the lost child was 1991 the only adjacency leading to the DAO prefix, the node should poison 1992 the route by sending no-DAOs to the parents to which it has 1993 advertised the DAO prefixes. 1995 The destination advertisement mechanism stores the prefix entries in 1996 one of 3 abstract lists; the Connected, the Reachable and the 1997 Unreachable lists. 1999 The Connected list corresponds to the prefixes owned and managed by 2000 the local node. 2002 The Reachable list contains prefixes for which the node keeps 2003 receiving DAO messages, and for those prefixes which have not yet 2004 timed out. 2006 The Unreachable list keeps track of prefixes which are no longer 2007 valid and in the process of being deleted, in order to send DAO 2008 messages with zero lifetime (also called no-DAO) to the DA parents. 2010 6.8.1.1.1. Destination Advertisement Timers 2012 The destination advertisement mechanism requires 2 timers; the 2013 DelayDAO timer and the RemoveTimer. 2015 o The DelayDAO timer is armed upon a stimulation to send a 2016 destination advertisement (such as a DIO message from a DA 2017 parent). When the timer is armed, all entries in the Reachable 2018 list as well as all entries for Connected list are set to not be 2019 reported yet for that particular DA parent. 2021 o For a root, the DIO timer has a duration of DEF_DAO_LATENCY. For 2022 a node in a DODAG iteration, the DelayDAO timer has a duration 2023 that is randomized between (DEF_DAO_LATENCY divided by the Rank of 2024 the node) and (DEF_DAO_LATENCY divided by the Rank of the parent). 2025 The intention is that nodes located deeper in the DODAG iteration 2026 should have a shorter DelayDAO timer, allowing DAO messages a 2027 chance to be reported from deeper in the DODAG and potentially 2028 aggregated along sub-DAGs before propagating further up. 2030 o The RemoveTimer is used to clean up entries for which DAO messages 2031 are no longer being received from the sub-DAG. 2033 * When a DIO message is sent that is requesting destination 2034 advertisements, a flag is set for all DAO entries in the 2035 routing table. 2037 * If the flag has already been set for a DAO entry, the retry 2038 count is incremented. 2040 * If a DAO message is received to confirm the entry, the entry is 2041 refreshed and the flag and count may be cleared. 2043 * If at least one entry has reached a threshold value and the 2044 RemoveTimer is not running, the entry is considered to be 2045 probably gone and the RemoveTimer is started. 2047 * When the RemoveTimer elapse, DAO messages with lifetime 0, i.e. 2048 no-DAOs, are sent to explicitly inform DA parents that the 2049 entries which have reached the threshold are no longer 2050 available, and the related routing states may be propagated and 2051 cleaned up. 2053 o The RemoveTimer has a duration of min (MAX_DESTROY_INTERVAL, 2054 TBD(DIO Trickle Timer Interval)). 2056 6.8.1.2. Multicast Destination Advertisement Messages 2058 It is also possible for a node to multicast a DAO message to the 2059 link-local scope all-nodes multicast address FF02::1. This message 2060 will be received by all node listening in range of the emitting node. 2061 The objective is to enable direct P2P communication, between 2062 destinations directly supported by neighboring nodes, without needing 2063 the RPL routing structure to relay the packets. 2065 A multicast DAO message MUST be used only to advertise information 2066 about self, i.e. prefixes in the Connected list or addresses owned by 2067 this node. This would typically be a multicast group that this node 2068 is listening to or a global address owned by this node, though it can 2069 be used to advertise any prefix owned by this node as well. A 2070 multicast DAO message is not used for routing and does not presume 2071 any DODAG relationship between the emitter and the receiver; it MUST 2072 NOT be used to relay information learned (e.g. information in the 2073 Reachable list) from another node; information obtained from a 2074 multicast DAO MAY be installed in the routing table and MAY be 2075 propagated by a router in unicast DAOs. 2077 A node receiving a multicast DAO message addressed to FF02::1 MAY 2078 install prefixes contained in the DAO message in the routing table 2079 for local use. Such a node MUST NOT perform any other processing on 2080 the DAO message (i.e. such a node does not presume it is a DA 2081 parent). 2083 6.8.1.3. Unicast Destination Advertisement Messages from Child to 2084 Parent 2086 When sending a destination advertisement to a DA parent, a node 2087 includes the DAOs for prefix entries not already reported (since the 2088 last DA Trigger from an DIO message) in the Reachable and Connected 2089 lists, as well as no-DAOs for all the entries in the Unreachable 2090 list. Depending on its policy and ability to retain routing state, 2091 the receiving node SHOULD keep a record of the reported DAO message. 2092 If the DAO message offers the best route to the prefix as determined 2093 by policy and other prefix records, the node SHOULD install a route 2094 to the prefix reported in the DAO message via the link local address 2095 of the reporting neighbor and it SHOULD further propagate the 2096 information in a DAO message. 2098 The DIO message from the DODAG root is used to synchronize the whole 2099 DODAG iteration, including the periodic reporting of destination 2100 advertisements back up the DODAG. Its period is expected to vary, 2101 depending on the configuration of the DIO trickle timer. 2103 When a node receives a DIO message over an LLN interface from a DA 2104 parent, the DelayDAO is armed to force a full update. 2106 When the node broadcasts a DIO message on an LLN interface, for all 2107 entries on that interface: 2109 o If the entry is CONFIRMED, it goes PENDING with the retry count 2110 set to 0. 2112 o If the entry is PENDING, the retry count is incremented. If it 2113 reaches a maximum threshold, the entry goes ELAPSED If at least 2114 one entry is ELAPSED at the end of the process: if the RemoveTimer 2115 is not running then it is armed with a jitter. 2117 Since the DelayDAO timer has a duration that decreases with the 2118 depth, it is expected to receive all DAO messages from all children 2119 before the timer elapses and the full update is sent to the DA 2120 parents. 2122 Once the RemoveTimer is elapsed, the prefix entry is scheduled to be 2123 removed and moved to the Unreachable list if there are any DA parents 2124 that need to be informed of the change in status for the prefix, 2125 otherwise the prefix entry is cleaned up right away. The prefix 2126 entry is removed from the Unreachable list when no more DA parents 2127 need to be informed. This condition may be satisfied when a no-DAO 2128 is sent to all current DA parents indicating the loss of the prefix, 2129 and noting that in some cases parents may have been removed from the 2130 set of DA parents. 2132 6.8.1.4. Other Events 2134 Finally, the destination advertisement mechanism responds to a series 2135 of events, such as: 2137 o Destination advertisement operation stopped: All entries in the 2138 abstract lists are freed. All the routes learned from DAO 2139 messages are removed. 2141 o Interface going down: for all entries in the Reachable list on 2142 that interface, the associated route is removed, and the entry is 2143 scheduled to be removed. 2145 o Loss of routing adjacency: When the routing adjacency for a 2146 neighbor is lost, as per the procedures described in Section 6.11, 2147 and if the associated entries are in the Reachable list, the 2148 associated routes are removed, and the entries are scheduled to be 2149 destroyed. 2151 o Changes to DA parent set: all entries in the Reachable list are 2152 set to not 'reported' and DelayDAO is armed. 2154 6.8.1.5. Aggregation of Prefixes by a Node 2156 There may be number of cases where a aggregation may be shared within 2157 a group of nodes. In such a case, it is possible to use aggregation 2158 techniques with destination advertisements and improve scalability. 2160 Other cases might occur for which additional support is required: 2162 1. The aggregating node is attached within the sub-DAG of the nodes 2163 it is aggregating for. 2165 2. A node that is to be aggregated for is located somewhere else 2166 within the DODAG iteration, not in the sub-DAG of the aggregating 2167 node. 2169 3. A node that is to be aggregated for is located somewhere else in 2170 the LLN. 2172 Consider a node M that is performing an aggregation, and a node N 2173 that is to be a member of the aggregation group. A node Z situated 2174 above the node M in the DODAG, but not above node N, will see the 2175 advertisements for the aggregation owned by M but not that of the 2176 individual prefix for N. Such a node Z will route all the packets for 2177 node N towards node M, but node M will have no route to the node N 2178 and will fail to forward. 2180 Additional protocols may be applied beyond the scope of this 2181 specification to dynamically elect/provision an aggregating node and 2182 groups of nodes eligible to be aggregated in order to provide route 2183 summarization for a sub-DAG. 2185 6.9. Loop Detection 2187 RPL loop avoidance mechanisms are kept simple and designed to 2188 minimize churn and states. Loops may form for a number of reasons, 2189 from control packet loss to sibling forwarding. RPL includes a 2190 reactive loop detection technique that protects from meltdown and 2191 triggers repair of broken paths. 2193 RPL loop detection uses information that is placed into the packet in 2194 the IPv6 flow label. The IPv6 flow label is defined in [RFC2460] and 2195 its operation is further specified in [RFC3697]. For the purpose of 2196 RPL operations, the flow label is constructed as follows: 2198 0 1 2 2199 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 2200 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2201 |O|S|R|F| SenderRank | InstanceID | 2202 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2204 Figure 12: RPL Flow Label 2206 Down 'O' bit: 1-bit flag indicating whether the packet is expected 2207 to progress up or down. A router sets the 'O' bit when the 2208 packet is expect to progress down (using DAO routes), and 2209 resets it when forwarding towards the root of the DODAG 2210 iteration. A host MUST set the bit to 0. 2212 Sibling 'S' bit: 1-bit flag indicating whether the packet has been 2213 forwarded via a sibling at the present rank, and denotes a risk 2214 of a sibling loop. A host sets the bit to 0. 2216 Rank-Error 'R' bit: 1-bit flag indicating whether a rank error was 2217 detected. A rank error is detected when there is a mismatch in 2218 the relative ranks and the direction as indicated in the 'O' 2219 bit. A host MUST set the bit to 0. 2221 Forwarding-Error 'F' bit: 1-bit flag indicating that this node can 2222 not forward the packet further towards the destination. The 2223 'F' bit might be set by sibling that can not forward to a 2224 parent a packet with the Sibling 'S' bit set, or by a child 2225 node that does not have a route to destination for a packet 2226 with the down 'O' bit set. A host MUST set the bit to 0. 2228 SenderRank: 8-bit field set to zero by the source and to its rank by 2229 a router that forwards inside the RPL network. 2231 InstanceID: 8-bit field indicating the DODAG instance along which 2232 the packet is sent. 2234 6.9.1. Source Node Operation 2236 A packet that is sourced at a node connected to a RPL network or 2237 destined to a node connected to a RPL network MUST be issued with the 2238 flow label zeroed out, but for the InstanceID field. 2240 If the source is aware of the InstanceID that is preferred for the 2241 flow, then it MUST set the InstanceID field in the flow label 2242 accordingly, otherwise it MUST set it to the RPL_DEFAULT_INSTANCE. 2244 If a compression mechanism such as 6LoWPAN is applied to the packet, 2245 the flow label MUST NOT be compressed even if it is set to all 2246 zeroes. 2248 6.9.2. Router Operation 2250 6.9.2.1. Conformance to RFC 3697 2252 [RFC3697] mandates that the Flow Label value set by the source MUST 2253 be delivered unchanged to the destination node(s). 2255 In order to restore the flow label to its original value, an RPL 2256 router that delivers a packet to a destination connected to a RPL 2257 network or that routes a packet outside the RPL network MUST zero out 2258 all the fields but the InstanceID field that must be delivered 2259 without a change. 2261 6.9.2.2. Instance Forwarding 2263 Instance IDs are used to avoid loops between DODAGs from different 2264 origins. DODAGs that constructed for antagonistic constraints might 2265 contain paths that, if mixed together, would yield loops. Those 2266 loops are avoided by forwarding a packet along the DODAG that is 2267 associated to a given instance. 2269 The InstanceID is placed by the source in the flow label. This 2270 InstanceID MUST match the DODAG instance onto which the packet is 2271 placed by any node, be it a host or router. 2273 When a router receives a packet that is flagged with a given 2274 InstanceID and the node can forward the packet along the DODAG 2275 associated to that instance, then the router MUST do so and leave the 2276 InstanceID flag unchanged. 2278 If any node can not forward a packet along the DODAG associated to 2279 the InstanceID in the flow label, then the node SHOULD discard the 2280 packet. 2282 6.9.2.3. DAG Inconsistency Loop Detection 2284 The DODAG is inconsistent if the direction of a packet does not match 2285 the rank relationship. A receiver detects an inconsistency if it 2286 receives a packet with either: 2288 the 'O' bit set (to down) from a node of a higher rank. 2290 the 'O' bit reset (for up) from a node of a lesser rank. 2292 the 'S' bit set (to sibling) from a node of a different rank. 2294 When the DODAG root increments the DAG Sequence Number a temporary 2295 rank discontinuity may form between the next iteration and the prior 2296 iteration, in particular if nodes are adjusting their rank in the 2297 next iteration and deferring their migration into the next iteration. 2298 A router that is still a member of the prior iteration may choose to 2299 forward a packet to a (future) parent that is in the next iteration. 2300 In some cases this could cause the parent to detect an inconsistency 2301 because the rank-ordering in the prior iteration is not necessarily 2302 the same as in the next iteration and the packet may be judged to not 2303 be making forward progress. If the sending router is aware that the 2304 chosen successor has already joined the next iteration, then the 2305 sending router MUST update the SenderRank to INFINITE_RANK as it 2306 forwards the packets across the discontinuity into the next DODAG 2307 iteration in order to avoid a false detection of rank inconsistency. 2309 One inconsistency along the path is not considered as a critical 2310 error and the packet may continue. But a second detection along the 2311 path of a same packet should not occur and the packet is dropped. 2313 This process is controlled by the Rank-Error bit in the Flow Label. 2314 When an inconsistency, is detected on a packet, if the Rank-Error bit 2315 was not set then the Rank-Error bit is set. If it was set the packet 2316 is discarded and the trickle timer is reset. 2318 6.9.2.4. Sibling Loop Avoidance 2320 When a packet is forwarded along siblings, it cannot be checked for 2321 forward progress and may loop between siblings. Experimental 2322 evidence has shown that one sibling hop can be very useful but is 2323 generally sufficient to avoid loops. Based on that evidence, this 2324 specification enforces the simple rule that a packet may not make 2 2325 sibling hops in a row. 2327 When a host issues a packet or when a router forwards a packet to a 2328 non-sibling, the Sibling bit in the packet must be reset. When a 2329 router forwards to a sibling: if the Sibling bit was not set then the 2330 Sibling bit is set. If the Sibling bit was set then then the router 2331 SHOULD return the packet to the sibling that that passed it with the 2332 Forwarding-Error 'F' bit set. 2334 6.9.2.5. DAO Inconsistency Loop Detection and Recovery 2336 A DAO inconsistency happens when router that has an down DAO route 2337 via a child that is a remnant from an obsolete state that is not 2338 matched in the child. With DAO inconsistency loop recovery, a packet 2339 can be used to recursively explore and cleanup the obsolete DAO 2340 states along a sub-DAG. 2342 In a general manner, a packet that goes down should never go up 2343 again. So rather than routing up a packet with the down bit set, the 2344 router MUST discard the packet. If DAO inconsistency loop recovery 2345 is applied, then the router SHOULD send the packet to the parent that 2346 passed it with the Forwarding-Error 'F' bit set. 2348 6.9.2.6. Forward Path Recovery 2350 Upon receiving a packet with a Forwarding-Error bit set, the node 2351 MUST remove the routing states that caused forwarding to that 2352 neighbor, clear the Forwarding-Error bit and attempt to send the 2353 packet again. The packet may its way to an alternate neighbor. If 2354 that alternate neighbor still has an inconsistent DAO state via this 2355 node, the process will recurse, this node will set the Forwarding- 2356 Error 'F' bit and the routing state in the alternate neighbor will be 2357 cleaned up as well. 2359 6.10. Multicast Operation 2361 This section describes further the multicast routing operations over 2362 an IPv6 RPL network, and specifically how unicast DAOs can be used to 2363 relay group registrations up. Wherever the following text mentions 2364 MLD, one can read MLDv2 or v3. 2366 As is traditional, a listener uses a protocol such as MLD with a 2367 router to register to a multicast group. 2369 Along the path between the router and the DODAG root, MLD requests 2370 are mapped and transported as DAO messages within the RPL protocol; 2371 each hop coalesces the multiple requests for a same group as a single 2372 DAO message to the parent(s), in a fashion similar to proxy IGMP, but 2373 recursively between child router and parent up to the root. 2375 A router might select to pass a listener registration DAO message to 2376 its preferred parent only, in which case multicast packets coming 2377 back might be lost for all of its sub-DAG if the transmission fails 2378 over that link. Alternatively the router might select to copy 2379 additional parents as it would do for DAO messages advertising 2380 unicast destinations, in which case there might be duplicates that 2381 the router will need to prune. 2383 As a result, multicast routing states are installed in each router on 2384 the way from the listeners to the root, enabling the root to copy a 2385 multicast packet to all its children routers that had issued a DAO 2386 message including a DAO for that multicast group, as well as all the 2387 attached nodes that registered over MLD. 2389 For unicast traffic, it is expected that the grounded root of an 2390 DODAG terminates RPL and MAY redistribute the RPL routes over the 2391 external infrastructure using whatever routing protocol is used 2392 there. For multicast traffic, the root MAY proxy MLD for all the 2393 nodes attached to the RPL routers (this would be needed if the 2394 multicast source is located in the external infrastructure). For 2395 such a source, the packet will be replicated as it flows down the 2396 DODAG based on the multicast routing table entries installed from the 2397 DAO message. 2399 For a source inside the DODAG, the packet is passed to the preferred 2400 parents, and if that fails then to the alternates in the DODAG. The 2401 packet is also copied to all the registered children, except for the 2402 one that passed the packet. Finally, if there is a listener in the 2403 external infrastructure then the DODAG root has to further propagate 2404 the packet into the external infrastructure. 2406 As a result, the DODAG Root acts as an automatic proxy Rendezvous 2407 Point for the RPL network, and as source towards the Internet for all 2408 multicast flows started in the RPL LLN. So regardless of whether the 2409 root is actually attached to the Internet, and regardless of whether 2410 the DODAG is grounded or floating, the root can serve inner multicast 2411 streams at all times. 2413 6.11. Maintenance of Routing Adjacency 2415 The selection of successors, along the default paths up along the 2416 DODAG, or along the paths learned from destination advertisements 2417 down along the DODAG, leads to the formation of routing adjacencies 2418 that require maintenance. 2420 In IGPs such as OSPF [RFC4915] or IS-IS [RFC5120], the maintenance of 2421 a routing adjacency involves the use of Keepalive mechanisms (Hellos) 2422 or other protocols such as BFD ([I-D.ietf-bfd-base]) and MANET 2423 Neighborhood Discovery Protocol (NHDP [I-D.ietf-manet-nhdp]). 2424 Unfortunately, such an approach is not desirable in constrained 2425 environments such as LLN and would lead to excessive control traffic 2426 in light of the data traffic with a negative impact on both link 2427 loads and nodes resources. Overhead to maintain the routing 2428 adjacency should be minimized. Furthermore, it is not always 2429 possible to rely on the link or transport layer to provide 2430 information of the associated link state. The network layer needs to 2431 fall back on its own mechanism. 2433 Thus RPL makes use of a different approach consisting of probing the 2434 neighbor using a Neighbor Solicitation message (see [RFC4861]). The 2435 reception of a Neighbor Advertisement (NA) message with the 2436 "Solicited Flag" set is used to verify the validity of the routing 2437 adjacency. Such mechanism MAY be used prior to sending a data 2438 packet. This allows for detecting whether or not the routing 2439 adjacency is still valid, and should it not be the case, select 2440 another feasible successor to forward the packet. 2442 7. Suggestions for Packet Forwarding 2444 When forwarding a packet to a destination, precedence is given to 2445 selection of a next-hop successor as follows: 2447 1. In the scope of this specification, it is preferred to select a 2448 successor from a DODAG iteration that matches the InstanceID 2449 marked in the IPv6 header of the packet being forwarded. 2451 2. If a local administrative preference favors a route that has been 2452 learned from a different routing protocol than RPL, then use that 2453 successor. 2455 3. If there is an entry in the routing table matching the 2456 destination that has been learned from a multicast destination 2457 advertisement (e.g. the destination is a one-hop neighbor), then 2458 use that successor. 2460 4. If there is an entry in the routing table matching the 2461 destination that has been learned from a unicast destination 2462 advertisement (e.g. the destination is located down the sub-DAG), 2463 then use that successor. 2465 5. If there is a DODAG iteration offering a route to a prefix 2466 matching the destination, then select one of those DODAG parents 2467 as a successor. 2469 6. If there is a DAG parent offering a default route then select 2470 that DAG parent as a successor. 2472 7. If there is a DODAG iteration offering a route to a prefix 2473 matching the destination, but all DAG parents have been tried and 2474 are temporarily unavailable (as determined by the forwarding 2475 procedure), then select a DAG sibling as a successor. 2477 8. Finally, if no DAG siblings are available, the packet is dropped. 2478 ICMP Destination Unreachable may be invoked. An inconsistency is 2479 detected. 2481 TTL MUST be decremented when forwarding. If the packet is being 2482 forwarded via a sibling, then the TTL MAY be decremented more 2483 aggressively (by more than one) to limit the impact of possible 2484 loops. 2486 Note that the chosen successor MUST NOT be the neighbor that was the 2487 predecessor of the packet (split horizon), except in the case where 2488 it is intended for the packet to change from an up to an down flow, 2489 such as switching from DIO routes to DAO routes as the destination is 2490 neared. 2492 8. Guidelines for Objective Functions 2494 An Objective Function (OF) allows for the selection of a DODAG to 2495 join, and a number of peers in that DAG as parents. The OF is used 2496 to compute an ordered list of parents. The OF is also responsible to 2497 compute the rank of the device within the DODAG iteration. 2499 The Objective Function is indicated in the DIO message using an 2500 Objective Code Point (OCP), as specified in 2501 [I-D.ietf-roll-routing-metrics], and indicates the method that must 2502 be used to compute the DODAG (e.g. "minimize the path cost using the 2503 ETX metric and avoid `Blue' links"). The Objective Code Points are 2504 specified in [I-D.ietf-roll-routing-metrics] and related companion 2505 specifications. 2507 Most Objective Functions are expected to follow the same abstract 2508 behavior: 2510 o The parent selection is triggered each time an event indicates 2511 that a potential next hop information is updated. This might 2512 happen upon the reception of a DIO message, a timer elapse, or a 2513 trigger indicating that the state of a candidate neighbor has 2514 changed. 2516 o An OF scans all the interfaces on the device. Although there may 2517 typically be only one interface in most application scenarios, 2518 there might be multiple of them and an interface might be 2519 configured to be usable or not for RPL operation. An interface 2520 can also be configured with a preference or dynamically learned to 2521 be better than another by some heuristics that might be link-layer 2522 dependent and are out of scope. Finally an interface might or not 2523 match a required criterion for an Objective Function, for instance 2524 a degree of security. As a result some interfaces might be 2525 completely excluded from the computation, while others might be 2526 more or less preferred. 2528 o An OF scans all the candidate neighbors on the possible interfaces 2529 to check whether they can act as a router for a DODAG. There 2530 might be multiple of them and a candidate neighbor might need to 2531 pass some validation tests before it can be used. In particular, 2532 some link layers require experience on the activity with a router 2533 to enable the router as a next hop. 2535 o An OF computes self's rank by adding the step of rank to that 2536 candidate to the rank of that candidate. The step of rank is 2537 computed by estimating the link as follows: 2539 * The step of rank might vary from 1 to 16. 2541 + 1 indicates a unusually good link, for instance a link 2542 between powered devices in a mostly battery operated 2543 environment. 2545 + 4 indicates a `normal'/typical link, as qualified by the 2546 implementation. 2548 + 16 indicates a link that can hardly be used to forward any 2549 packet, for instance a radio link with quality indicator or 2550 expected transmission count that is close to the acceptable 2551 threshold. 2553 * Candidate neighbors that would cause self's rank to increase 2554 are ignored 2556 o Candidate neighbors that advertise an OF incompatible with the set 2557 of OF specified by the policy functions are ignored. 2559 o As it scans all the candidate neighbors, the OF keeps the current 2560 best parent and compares its capabilities with the current 2561 candidate neighbor. The OF defines a number of tests that are 2562 critical to reach the objective. A test between the routers 2563 determines an order relation. 2565 * If the routers are roughly equal for that relation then the 2566 next test is attempted between the routers, 2568 * Else the best of the 2 becomes the current best parent and the 2569 scan continues with the next candidate neighbor 2571 * Some OFs may include a test to compare the ranks that would 2572 result if the node joined either router 2574 o When the scan is complete, the preferred parent is elected and 2575 self's rank is computed as the preferred parent rank plus the step 2576 in rank with that parent. 2578 o Other rounds of scans might be necessary to elect alternate 2579 parents and siblings. In the next rounds: 2581 * Candidate neighbors that are not in the same DODAG are ignored 2583 * Candidate neighbors that are of greater rank than self are 2584 ignored 2586 * Candidate neighbors of an equal rank to self (siblings) are 2587 ignored 2589 * Candidate neighbors of a lesser rank than self (non-siblings) 2590 are preferred 2592 9. RPL Constants and Variables 2594 Following is a summary of RPL constants and variables. Some default 2595 values are to be determined in companion applicability statements. 2597 ZERO_LIFETIME This is the special value of a lifetime that indicates 2598 immediate death and removal. ZERO_LIFETIME has a value of 0. 2600 BASE_RANK This is the rank for a virtual root that might be used to 2601 coordinate multiple roots. BASE_RANK has a value of 0. 2603 ROOT_RANK This is the rank for a DAG root. ROOT_RANK has a value of 2604 1. 2606 INFINITE_RANK This is the constant maximum for the rank. 2607 INFINITE_RANK has a value of 0xFF. 2609 RPL_DEFAULT_INSTANCE This is the InstanceID that is used by this 2610 protocol by a node without any overriding policy. 2611 RPL_DEFAULT_INSTANCE has a value of 0. 2613 DEFAULT_DIO_INTERVAL_MIN To be determined 2615 DEFAULT_DIO_INTERVAL_DOUBLINGS To be determined 2617 DEFAULT_DIO_REDUNDANCY_CONSTANT To be determined 2619 DEF_DAO_LATENCY To be determined 2621 MAX_DESTROY_INTERVAL To be determined 2623 DIO Timer One instance per DODAG that a node is a member of. Expiry 2624 triggers DIO message transmission. Trickle timer with variable 2625 interval in [0, DIOIntervalMin..2^DIOIntervalDoublings]. See 2626 Section 6.3.4 2628 DAG Sequence Number Increment Timer Up to one instance per DODAG 2629 that the node is acting as DAG root of. May not be supported 2630 in all implementations. Expiry triggers revision of 2631 DAGSequenceNumber, causing a new series of updated DIO message 2632 to be sent. Interval should be chosen appropriate to 2633 propagation time of DODAG and as appropriate to application 2634 requirements (e.g. response time vs. overhead). 2636 DelayDAO Timer Up to one instance per DA parent (the subset of DAG 2637 parents chosen to receive destination advertisements) per 2638 DODAG. Expiry triggers sending of DAO message to the DA 2639 parent. The interval is to be proportional to DEF_DAO_LATENCY/ 2640 (node rank), such that nodes of greater rank (further down 2641 along the DODAG) expire first, coordinating the sending of DAO 2642 messages to allow for a chance of aggregation. See 2643 Section 6.8.1.1.1 2645 RemoveTimer Up to one instance per DA entry per neighbor (i.e. those 2646 neighbors that have given DAO messages to this node as a DAG 2647 parent) Expiry triggers a change in state for the DA entry, 2648 setting up to do unreachable (No-DAO) advertisements or 2649 immediately deallocating the DA entry if there are no DA 2650 parents. The interval is min(MAX_DESTROY_INTERVAL, TBD(DIO 2651 Trickle Timer Interval)). See Section 6.8.1.1.1 2653 10. Manageability Considerations 2655 The aim of this section is to give consideration to the manageability 2656 of RPL, and how RPL will be operated in LLN beyond the use of a MIB 2657 module. The scope of this section is to consider the following 2658 aspects of manageability: fault management, configuration, accounting 2659 and performance. 2661 10.1. Control of Function and Policy 2663 10.1.1. Initialization Mode 2665 When a node is first powered up, it may either choose to stay silent 2666 and not send any multicast DIO message until it has joined a DODAG, 2667 or to immediately root a transient DODAG and start sending multicast 2668 DIO messages. A RPL implementation SHOULD allow configuring whether 2669 the node should stay silent or should start advertising DIO messages. 2671 Furthermore, the implementation SHOULD to allow configuring whether 2672 or not the node should start sending an DIS message as an initial 2673 probe for nearby DODAGs, or should simply wait until it received DIO 2674 messages from other nodes that are part of existing DODAGs. 2676 10.1.2. DIO Base option 2678 RPL specifies a number of protocol parameters. 2680 A RPL implementation SHOULD allow configuring the following routing 2681 protocol parameters, which are further described in Section 6.1.3.1: 2683 DAGPreference 2684 InstanceID 2685 DAGObjectiveCodePoint 2686 DAGID 2687 Destination Prefixes 2688 DIOIntervalDoublings 2689 DIOIntervalMin 2690 DIORedundancyConstant 2692 DAG Root behavior: In some cases, a node may not want to permanently 2693 act as a DAG root if it cannot join a grounded DODAG. For 2694 example a battery-operated node may not want to act as a DAG 2695 root for a long period of time. Thus a RPL implementation MAY 2696 support the ability to configure whether or not a node could 2697 act as a DAG root for a configured period of time. 2699 DAG Table Entry Suppression A RPL implementation SHOULD provide the 2700 ability to configure a timer after the expiration of which the 2701 DAG table that contains all the records about a DAG is 2702 suppressed, to be invoked if the DAG parent set becomes empty. 2704 10.1.3. Trickle Timers 2706 A RPL implementation makes use of trickle timer to govern the sending 2707 of DIO message. Such an algorithm is determined a by a set of 2708 configurable parameters that are then advertised by the DAG root 2709 along the DODAG in DIO messages. 2711 For each DODAG, a RPL implementation MUST allow for the monitoring of 2712 the following parameters, further described in Section 6.3.4: 2714 I 2715 T 2716 C 2717 I_min 2718 I_doublings 2720 A RPL implementation SHOULD provide a command (for example via API, 2721 CLI, or SNMP MIB) whereby any procedure that detects an inconsistency 2722 may cause the trickle timer to reset. 2724 10.1.4. DAG Sequence Number Increment 2726 A RPL implementation may allow by configuration at the DAG root to 2727 refresh the DODAG states by updating the DAGSequenceNumber. A RPL 2728 implementation SHOULD allow configuring whether or not periodic or 2729 event triggered mechanism are used by the DAG root to control 2730 DAGSequenceNumber change. 2732 10.1.5. Destination Advertisement Timers 2734 The following set of parameters of the DAO messages SHOULD be 2735 configurable: 2737 o The DelayDAO timer 2739 o The Remove timer 2741 10.1.6. Policy Control 2743 DAG discovery enables nodes to implement different policies for 2744 selecting their DAG parents. 2746 A RPL implementation SHOULD allow configuring the set of acceptable 2747 or preferred Objective Functions (OF) referenced by their Objective 2748 Codepoints (OCPs) for a node to join a DODAG, and what action should 2749 be taken if none of a node's candidate neighbors advertise one of the 2750 configured allowable Objective Functions. 2752 A node in an LLN may learn routing information from different routing 2753 protocols including RPL. It is in this case desirable to control via 2754 administrative preference which route should be favored. An 2755 implementation SHOULD allow for specifying an administrative 2756 preference for the routing protocol from which the route was learned. 2758 A RPL implementation SHOULD allow for the configuration of the "Route 2759 Tag" field of the DAO messages according to a set of rules defined by 2760 policy. 2762 10.1.7. Data Structures 2764 Some RPL implementation may limit the size of the candidate neighbor 2765 list in order to bound the memory usage, in which case some otherwise 2766 viable candidate neighbors may not be considered and simply dropped 2767 from the candidate neighbor list. 2769 A RPL implementation MAY provide an indicator on the size of the 2770 candidate neighbor list. 2772 10.2. Information and Data Models 2774 The information and data models necessary for the operation of RPL 2775 will be defined in a separate document specifying the RPL SNMP MIB. 2777 10.3. Liveness Detection and Monitoring 2779 The aim of this section is to describe the various RPL mechanisms 2780 specified to monitor the protocol. 2782 As specified in Section 6.2, an implementation is expected to 2783 maintain a set of data structures in support of DAG discovery: 2785 o The candidate neighbors data structure 2787 o For each DODAG: 2789 * A set of DAG parents 2791 10.3.1. Candidate Neighbor Data Structure 2793 A node in the candidate neighbor list is a node discovered by the 2794 some means and qualified to potentially become of neighbor or a 2795 sibling (with high enough local confidence). A RPL implementation 2796 SHOULD provide a way monitor the candidate neighbors list with some 2797 metric reflecting local confidence (the degree of stability of the 2798 neighbors) measured by some metrics. 2800 A RPL implementation MAY provide a counter reporting the number of 2801 times a candidate neighbor has been ignored, should the number of 2802 candidate neighbors exceeds the maximum authorized value. 2804 10.3.2. Directed Acyclic Graph (DAG) Table 2806 For each DAG, a RPL implementation is expected to keep track of the 2807 following DODAG table values: 2809 o DAGID 2811 o DAGObjectiveCodePoint 2813 o A set of Destination Prefixes offered upwards along the DODAG 2815 o A set of DAG Parents 2817 o timer to govern the sending of DIO messages for the DODAG 2819 o DAGSequenceNumber 2821 The set of DAG parents structure is itself a table with the following 2822 entries: 2824 o A reference to the neighboring device which is the DAG parent 2826 o A record of most recent information taken from the DAG Information 2827 Object last processed from the DAG Parent 2829 o A flag reporting if the Parent is a DA Parent as described in 2830 Section 6.8 2832 10.3.3. Routing Table 2834 For each route provisioned by RPL operation, a RPL implementation 2835 MUST keep track of the following: 2837 o Destination Prefix 2839 o Destination Prefix Length 2841 o Lifetime Timer 2843 o Next Hop 2845 o Next Hop Interface 2847 o Flag indicating that the route was provisioned from one of: 2849 * Unicast DAO message 2851 * DIO message 2853 * Multicast DAO message 2855 10.3.4. Other RPL Monitoring Parameters 2857 A RPL implementation SHOULD provide a counter reporting the number of 2858 a times the node has detected an inconsistency with respect to a DAG 2859 parent, e.g. if the DAGID has changed. 2861 A RPL implementation MAY log the reception of a malformed DIO message 2862 along with the neighbor identification if avialable. 2864 10.3.5. RPL Trickle Timers 2866 A RPL implementation operating on a DAG root MUST allow for the 2867 configuration of the following trickle parameters: 2869 o The DIOIntervalMin expressed in ms 2871 o The DIOIntervalDoublings 2873 o The DIORedundancyConstant 2875 A RPL implementation MAY provide a counter reporting the number of 2876 times an inconsistency (and thus the trickle timer has been reset). 2878 10.4. Verifying Correct Operation 2880 This section has to be completed in further revision of this document 2881 to list potential Operations and Management (OAM) tools that could be 2882 used for verifying the correct operation of RPL. 2884 10.5. Requirements on Other Protocols and Functional Components 2886 RPL does not have any impact on the operation of existing protocols. 2888 10.6. Impact on Network Operation 2890 To be completed. 2892 11. Security Considerations 2894 Security Considerations for RPL are to be developed in accordance 2895 with recommendations laid out in, for example, 2896 [I-D.tsao-roll-security-framework]. 2898 12. IANA Considerations 2900 12.1. RPL Control Message 2902 The RPL Control Message is an ICMP information message type that is 2903 to be used carry DAG Information Objects, DAG Information 2904 Solicitations, and Destination Advertisement Objects in support of 2905 RPL operation. 2907 IANA has defined a ICMPv6 Type Number Registry. The suggested type 2908 value for the RPL Control Message is 155, to be confirmed by IANA. 2910 12.2. New Registry for RPL Control Codes 2912 IANA is requested to create a registry, RPL Control Codes, for the 2913 Code field of the ICMPv6 RPL Control Message. 2915 New codes may be allocated only by an IETF Consensus action. Each 2916 code should be tracked with the following qualities: 2918 o Code 2920 o Description 2922 o Defining RFC 2924 Three codes are currently defined: 2926 +------+----------------------------------+---------------+ 2927 | Code | Description | Reference | 2928 +------+----------------------------------+---------------+ 2929 | 0x01 | DAG Information Solicitation | This document | 2930 | 0x02 | DAG Information Object | This document | 2931 | 0x04 | Destination Advertisement Object | This document | 2932 +------+----------------------------------+---------------+ 2934 RPL Control Codes 2936 12.3. New Registry for the Control Field of the DIO Base 2938 IANA is requested to create a registry for the Control field of the 2939 DIO Base. 2941 New bit numbers may be allocated only by an IETF Consensus action. 2942 Each bit should be tracked with the following qualities: 2944 o Bit number (counting from bit 0 as the most significant bit) 2946 o Capability description 2948 o Defining RFC 2950 Four groups are currently defined: 2952 +-------+-------------------------------------+---------------+ 2953 | Bit | Description | Reference | 2954 +-------+-------------------------------------+---------------+ 2955 | 0 | Grounded DODAG | This document | 2956 | 1 | Destination Advertisement Trigger | This document | 2957 | 2 | Destination Advertisement Supported | This document | 2958 | 5,6,7 | DAG Preference | This document | 2959 +-------+-------------------------------------+---------------+ 2961 DIO Base Flags 2963 12.4. DAG Information Object (DIO) Suboption 2965 IANA is requested to create a registry for the DIO Base Suboptions 2966 +-------+------------------------------+---------------+ 2967 | Value | Meaning | Reference | 2968 +-------+------------------------------+---------------+ 2969 | 0 | Pad1 - DIO Padding | This document | 2970 | 1 | PadN - DIO suboption padding | This document | 2971 | 2 | DAG Metric Container | This Document | 2972 | 3 | Destination Prefix | This Document | 2973 | 4 | DAG Timer Configuration | This Document | 2974 +-------+------------------------------+---------------+ 2976 DAG Information Option (DIO) Base Suboptions 2978 13. Acknowledgements 2980 The authors would like to acknowledge the review, feedback, and 2981 comments from Emmanuel Baccelli, Dominique Barthel, Yusuf Bashir, 2982 Mathilde Durvy, Manhar Goindi, Mukul Goyal, Anders Jagd, Quentin 2983 Lampin, Jerry Martocci, Alexandru Petrescu, and Don Sturek. 2985 The authors would like to acknowledge the guidance and input provided 2986 by the ROLL Chairs, David Culler and JP Vasseur. 2988 The authors would like to acknowledge prior contributions of Robert 2989 Assimiti, Mischa Dohler, Julien Abeille, Ryuji Wakikawa, Teco Boot, 2990 Patrick Wetterwald, Bryan Mclaughlin, Carlos J. Bernardos, Thomas 2991 Watteyne, Zach Shelby, Caroline Bontoux, Marco Molteni, Billy Moon, 2992 and Arsalan Tavakoli, which have provided useful design 2993 considerations to RPL. 2995 14. Contributors 2997 RPL is the result of the contribution of the following members of the 2998 ROLL Design Team, including the editors, and additional contributors 2999 as listed below: 3001 JP Vasseur 3002 Cisco Systems, Inc 3003 11, Rue Camille Desmoulins 3004 Issy Les Moulineaux, 92782 3005 France 3007 Email: jpv@cisco.com 3009 Jonathan W. Hui 3010 Arch Rock Corporation 3011 501 2nd St. Ste. 410 3012 San Francisco, CA 94107 3013 USA 3015 Email: jhui@archrock.com 3017 Thomas Heide Clausen 3018 LIX, Ecole Polytechnique, France 3020 Phone: +33 6 6058 9349 3021 EMail: T.Clausen@computer.org 3022 URI: http://www.ThomasClausen.org/ 3024 Philip Levis 3025 Stanford University 3026 358 Gates Hall, Stanford University 3027 Stanford, CA 94305-9030 3028 USA 3030 Email: pal@cs.stanford.edu 3032 Richard Kelsey 3033 Ember Corporation 3034 Boston, MA 3035 USA 3037 Phone: +1 617 951 1225 3038 Email: kelsey@ember.com 3040 Stephen Dawson-Haggerty 3041 UC Berkeley 3042 Soda Hall, UC Berkeley 3043 Berkeley, CA 94720 3044 USA 3046 Email: stevedh@cs.berkeley.edu 3048 Kris Pister 3049 Dust Networks 3050 30695 Huntwood Ave. 3051 Hayward, 94544 3052 USA 3053 Email: kpister@dustnetworks.com 3055 Anders Brandt 3056 Zensys, Inc. 3057 Emdrupvej 26 3058 Copenhagen, DK-2100 3059 Denmark 3061 Email: abr@zen-sys.com 3063 15. References 3065 15.1. Normative References 3067 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 3068 Requirement Levels", BCP 14, RFC 2119, March 1997. 3070 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 3071 (IPv6) Specification", RFC 2460, December 1998. 3073 15.2. Informative References 3075 [I-D.ietf-bfd-base] 3076 Katz, D. and D. Ward, "Bidirectional Forwarding 3077 Detection", draft-ietf-bfd-base-09 (work in progress), 3078 February 2009. 3080 [I-D.ietf-manet-nhdp] 3081 Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 3082 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 3083 draft-ietf-manet-nhdp-11 (work in progress), October 2009. 3085 [I-D.ietf-roll-building-routing-reqs] 3086 Martocci, J., Riou, N., Mil, P., and W. Vermeylen, 3087 "Building Automation Routing Requirements in Low Power and 3088 Lossy Networks", draft-ietf-roll-building-routing-reqs-08 3089 (work in progress), December 2009. 3091 [I-D.ietf-roll-home-routing-reqs] 3092 Brandt, A. and J. Buron, "Home Automation Routing 3093 Requirements in Low Power and Lossy Networks", 3094 draft-ietf-roll-home-routing-reqs-09 (work in progress), 3095 November 2009. 3097 [I-D.ietf-roll-routing-metrics] 3098 Vasseur, J. and D. Networks, "Routing Metrics used for 3099 Path Calculation in Low Power and Lossy Networks", 3100 draft-ietf-roll-routing-metrics-04 (work in progress), 3101 December 2009. 3103 [I-D.ietf-roll-terminology] 3104 Vasseur, J., "Terminology in Low power And Lossy 3105 Networks", draft-ietf-roll-terminology-02 (work in 3106 progress), October 2009. 3108 [I-D.tsao-roll-security-framework] 3109 Tsao, T., Alexander, R., Dohler, M., Daza, V., and A. 3110 Lozano, "A Security Framework for Routing over Low Power 3111 and Lossy Networks", draft-tsao-roll-security-framework-01 3112 (work in progress), September 2009. 3114 [Levis08] Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S., 3115 Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and A. 3116 Woo, "The Emergence of a Networking Primitive in Wireless 3117 Sensor Networks", Communications of the ACM, v.51 n.7, 3118 July 2008, 3119 . 3121 [RFC1982] Elz, R. and R. Bush, "Serial Number Arithmetic", RFC 1982, 3122 August 1996. 3124 [RFC2453] Malkin, G., "RIP Version 2", STD 56, RFC 2453, 3125 November 1998. 3127 [RFC3697] Rajahalme, J., Conta, A., Carpenter, B., and S. Deering, 3128 "IPv6 Flow Label Specification", RFC 3697, March 2004. 3130 [RFC3819] Karn, P., Bormann, C., Fairhurst, G., Grossman, D., 3131 Ludwig, R., Mahdavi, J., Montenegro, G., Touch, J., and L. 3132 Wood, "Advice for Internet Subnetwork Designers", BCP 89, 3133 RFC 3819, July 2004. 3135 [RFC4101] Rescorla, E. and IAB, "Writing Protocol Models", RFC 4101, 3136 June 2005. 3138 [RFC4191] Draves, R. and D. Thaler, "Default Router Preferences and 3139 More-Specific Routes", RFC 4191, November 2005. 3141 [RFC4443] Conta, A., Deering, S., and M. Gupta, "Internet Control 3142 Message Protocol (ICMPv6) for the Internet Protocol 3143 Version 6 (IPv6) Specification", RFC 4443, March 2006. 3145 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 3146 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 3147 September 2007. 3149 [RFC4915] Psenak, P., Mirtorabi, S., Roy, A., Nguyen, L., and P. 3150 Pillay-Esnault, "Multi-Topology (MT) Routing in OSPF", 3151 RFC 4915, June 2007. 3153 [RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi 3154 Topology (MT) Routing in Intermediate System to 3155 Intermediate Systems (IS-ISs)", RFC 5120, February 2008. 3157 [RFC5548] Dohler, M., Watteyne, T., Winter, T., and D. Barthel, 3158 "Routing Requirements for Urban Low-Power and Lossy 3159 Networks", RFC 5548, May 2009. 3161 [RFC5673] Pister, K., Thubert, P., Dwars, S., and T. Phinney, 3162 "Industrial Routing Requirements in Low-Power and Lossy 3163 Networks", RFC 5673, October 2009. 3165 Appendix A. Requirements 3167 A.1. Protocol Properties Overview 3169 RPL demonstrates the following properties, consistent with the 3170 requirements specified by the application-specific requirements 3171 documents. 3173 A.1.1. IPv6 Architecture 3175 RPL is strictly compliant with layered IPv6 architecture. 3177 Further, RPL is designed with consideration to the practical support 3178 and implementation of IPv6 architecture on devices which may operate 3179 under severe resource constraints, including but not limited to 3180 memory, processing power, energy, and communication. The RPL design 3181 does not presume high quality reliable links, and operates over lossy 3182 links (usually low bandwidth with low packet delivery success rate). 3184 A.1.2. Typical LLN Traffic Patterns 3186 Multipoint-to-Point (MP2P) and Point-to-multipoint (P2MP) traffic 3187 flows from nodes within the LLN from and to egress points are very 3188 common in LLNs. Low power and lossy network Border Router (LBR) 3189 nodes may typically be at the root of such flows, although such flows 3190 are not exclusively rooted at LBRs as determined on an application- 3191 specific basis. In particular, several applications such as building 3192 or home automation do require P2P (Point-to-Point) communication. 3194 As required by the aforementioned routing requirements documents, RPL 3195 supports the installation of multiple paths. The use of multiple 3196 paths include sending duplicated traffic along diverse paths, as well 3197 as to support advanced features such as Class of Service (CoS) based 3198 routing, or simple load balancing among a set of paths (which could 3199 be useful for the LLN to spread traffic load and avoid fast energy 3200 depletion on some, e.g. battery powered, nodes). Conceptually, 3201 multiple instances of RPL can be used to send traffic along different 3202 topology instances, the construction of which is governed by 3203 different Objective Functions (OF). Details of RPL operation in 3204 support of multiple instances are beyond the scope of the present 3205 specification. 3207 A.1.3. Constraint Based Routing 3209 The RPL design supports constraint based routing, based on a set of 3210 routing metrics and constraints. The routing metrics and constraints 3211 for links and nodes with capabilities supported by RPL are specified 3212 in a companion document to this specification, 3213 [I-D.ietf-roll-routing-metrics]. RPL signals the metrics, 3214 constraints, and related Objective Functions (OFs) in use in a 3215 particular implementation by means of an Objective Code Point (OCP). 3216 Both the routing metrics, constraints, and the OF help determine the 3217 construction of the Directed Acyclic Graphs (DAG) using a distributed 3218 path computation algorithm. 3220 A.2. Deferred Requirements 3222 NOTE: RPL is still a work in progress. At this time there remain 3223 several unsatisfied application requirements, but these are to be 3224 addressed as RPL is further specified. 3226 Appendix B. Examples 3228 Consider the example LLN physical topology in Figure 13. In this 3229 example the links depicted are all usable L2 links. Suppose that all 3230 links are equally usable, and that the implementation specific policy 3231 function is simply to minimize hops. This LLN physical topology then 3232 yields the DAG depicted in Figure 14, where the links depicted are 3233 the edges toward DAG parents. This topology includes one DAG, rooted 3234 by an LBR node (LBR) at rank 1. The LBR node will issue DIO 3235 messages, as governed by a trickle timer. Nodes (11), (12), (13), 3236 have selected (LBR) as their only parent, attached to the DAG at rank 3237 2, and periodically multicast DIOs. Node (22) has selected (11) and 3238 (12) in its DAG parent set, and advertises itself at rank 3. Node 3239 (22) thus has a set of DAG parents {(11), (12)} and siblings {((21), 3240 (23)}. 3242 (LBR) 3243 / | \ 3244 .---` | `----. 3245 / | \ 3246 (11)------(12)------(13) 3247 | \ | \ | \ 3248 | `----. | `----. | `----. 3249 | \| \| \ 3250 (21)------(22)------(23) (24) 3251 | /| /| | 3252 | .----` | .----` | | 3253 | / | / | | 3254 (31)------(32)------(33)------(34) 3255 | /| \ | \ | \ 3256 | .----` | `----. | `----. | `----. 3257 | / | \| \| \ 3258 .--------(41) (42) (43)------(44)------(45) 3259 / / /| \ | \ 3260 .----` .----` .----` | `----. | `----. 3261 / / / | \| \ 3262 (51)------(52)------(53)------(54)------(55)------(56) 3264 Note that the links depicted represent the usable L2 connectivity 3265 available in the LLN. For example, Node (31) can communicate 3266 directly with its neighbors, Nodes (21), (22), (32), and (41). Node 3267 (31) cannot communicate directly with any other nodes, e.g. (33), 3268 (23), (42). In this example these links offer bidirectional 3269 communication, and `bad' links are not depicted. 3271 Figure 13: Example LLN Topology 3272 (LBR) 3273 / | \ 3274 .---` | `----. 3275 / | \ 3276 (11) (12) (13) 3277 | \ | \ | \ 3278 | `----. | `----. | `----. 3279 | \| \| \ 3280 (21) (22) (23) (24) 3281 | /| /| | 3282 | .----` | .----` | | 3283 | / | / | | 3284 (31) (32) (33) (34) 3285 | /| \ | \ | \ 3286 | .----` | `----. | `----. | `----. 3287 | / | \| \| \ 3288 .--------(41) (42) (43) (44) (45) 3289 / / /| \ | \ 3290 .----` .----` .----` | `----. | `----. 3291 / / / | \| \ 3292 (51) (52) (53) (54) (55) (56) 3294 Note that the links depicted represent directed links in the DAG 3295 overlaid on top of the physical topology depicted in Figure 13. As 3296 such, the depicted edges represent the relationship between nodes and 3297 their DAG parents, wherein all depicted edges are directed and 3298 oriented `up' on the page toward the DAG root (LBR). The DAG may 3299 provide default routes within the LLN, and serves as the foundation 3300 on which RPL builds further routing structure, e.g. through the 3301 destination advertisement mechanism. 3303 Figure 14: Example DAG 3305 B.1. Destination Advertisement 3307 Consider the example DAG depicted in Figure 14. Suppose that Nodes 3308 (22) and (32) are unable to record routing state. Suppose that Node 3309 (42) is able to perform prefix aggregation on behalf of Nodes (53), 3310 (54), and (55). 3312 o Node (53) would send a DAO message to Node (42), indicating the 3313 availability of destination (53). 3315 o Node (54) and Node (55) would similarly send DAO messages to Node 3316 (42) indicating their own destinations. 3318 o Node (42) would collect and store the routing state for 3319 destinations (53), (54), and (55). 3321 o In this example, Node (42) may then be capable of representing 3322 destinations (42), (53), (54), and (55) in the aggregation (42'). 3324 o Node (42) sends a DAO message advertising destination (42') to 3325 Node 32. 3327 o Node (32) does not want to maintain any routing state, so it adds 3328 onto to the Reverse Route Stack in the DAO message and passes it 3329 on to Node (22) as (42'):[(42)]. It may send a separate DAO 3330 message to indicate destination (32). 3332 o Node (22) does not want to maintain any routing state, so it adds 3333 on to the Reverse Route Stack in the DAO message and passes it on 3334 to Node (12) as (42'):[(42), (32)]. It also relays the DAO 3335 message containing destination (32) to Node 12 as (32):[(32)], and 3336 finally may send a DAO message for itself indicating destination 3337 (22). 3339 o Node (12) is capable to maintain routing state again, and receives 3340 the DAO messages from Node (22). Node (12) then learns: 3341 * Destination (22) is available via Node (22) 3342 * Destination (32) is available via Node (22) and the piecewise 3343 source route to (32) 3344 * Destination (42') is available via Node (22) and the piecewise 3345 source route to (32), (42'). 3347 o Node (12) sends DAO messages to (LBR), allowing (LBR) to learn 3348 routes to the destinations (12), (22), (32), and (42'). (42), 3349 (53), (54), and (55) are available via the aggregation (42'). It 3350 is not necessary for Node (12) to propagate the piecewise source 3351 routes to (LBR). 3353 B.2. Example: DAG Parent Selection 3355 For example, suppose that a node (N) is not attached to any DAG, and 3356 that it is in range of nodes (A), (B), (C), (D), and (E). Let all 3357 nodes be configured to use an OCP which defines a policy such that 3358 ETX is to be minimized and paths with the attribute `Blue' should be 3359 avoided. Let the rank computation indicated by the OCP simply 3360 reflect the ETX aggregated along the path. Let the links between 3361 node (N) and its neighbors (A-E) all have an ETX of 1 (which is 3362 learned by node (N) through some implementation specific method). 3363 Let node (N) be configured to send RPL DIS messages to probe for 3364 nearby DAGs. 3366 o Node (N) transmits a RPL DIS message. 3368 o Node (B) responds. Node (N) investigates the DIO message, and 3369 learns that Node (B) is a member of DAGID 1 at rank 4, and not 3370 `Blue'. Node (N) takes note of this, but is not yet confident. 3372 o Similarly, Node (N) hears from Node (A) at rank 9, Node (C) at 3373 rank 5, and Node (E) at rank 4. 3375 o Node (D) responds. Node (D) has a DIO message that indicates that 3376 it is a member of DAGID 1 at rank 2, but it carries the attribute 3377 `Blue'. Node (N)'s policy function rejects Node (D), and no 3378 further consideration is given. 3380 o This process continues until Node (N), based on implementation 3381 specific policy, builds enough confidence to trigger a decision to 3382 join DAGID 1. Let Node (N) determine its most preferred parent to 3383 be Node (E). 3385 o Node (N) adds Node (E) (rank 4) to its set of DAG parents for 3386 DAGID 1. Following the mechanisms specified by the OCP, and given 3387 that the ETX is 1 for the link between (N) and (E), Node (N) is 3388 now at rank 5 in DAGID 1. 3390 o Node (N) adds Node (B) (rank 4) to its set of DAG parents for 3391 DAGID 1. 3393 o Node (N) is a sibling of Node (C), both are at rank 5. 3395 o Node (N) may now forward traffic intended for the default 3396 destination upwards along DAGID 1 via nodes (B) and (E). In some 3397 cases, e.g. if nodes (B) and (E) are tried and fail, node (N) may 3398 also choose to forward traffic to its sibling node (C), without 3399 making upwards progress but with the intention that node (C) or a 3400 following successor can make upwards progress. Should Node (C) 3401 not have a viable parent, it should never send the packet back to 3402 Node (N) (to avoid a 2-node loop). 3404 B.3. Example: DAG Maintenance 3406 : : : 3407 : : : 3408 (A) (A) (A) 3409 |\ | | 3410 | `-----. | | 3411 | \ | | 3412 (B) (C) (B) (C) (B) 3413 | | \ 3414 | | `-----. 3415 | | \ 3416 (D) (D) (C) 3417 | 3418 | 3419 | 3420 (D) 3422 -1- -2- -3- 3424 Figure 15: DAG Maintenance 3426 Consider the example depicted in Figure 15-1. In this example, Node 3427 (A) is attached to a DAG at some rank d. Node (A) is a DAG parent of 3428 Nodes (B) and (C). Node (C) is a DAG parent of Node (D). There is 3429 also an undirected sibling link between Nodes (B) and (C). 3431 In this example, Node (C) may safely forward to Node (A) without 3432 creating a loop. Node (C) may not safely forward to Node (D), 3433 contained within it's own sub-DAG, without creating a loop. Node (C) 3434 may forward to Node (B) in some cases, e.g. the link (C)->(A) is 3435 temporarily unavailable, but with some chance of creating a loop 3436 (e.g. if multiple nodes in a set of siblings start forwarding 3437 `sideways' in a cycle) and requiring the intervention of additional 3438 mechanisms to detect and break the loop. 3440 Consider the case where Node (C) hears a DIO message from a Node (Z) 3441 at a lesser rank and superior position in the DAG than node (A). 3442 Node (C) may safely undergo the process to evict node (A) from its 3443 DAG parent set and attach directly to Node (Z) without creating a 3444 loop, because its rank will decrease. 3446 Now consider the case where the link (C)->(A) becomes nonviable, and 3447 node (C) must move to a deeper rank within the DAG: 3449 o Node (C) must first detach from the DAG by removing Node (A) from 3450 its DAG parent set, leaving an empty DAG parent set. Node (C) may 3451 become the root of its own floating, less preferred, DAG. 3453 o Node (D), hearing a modified DIO message from Node (C), follows 3454 Node (C) into the floating DAG. This is depicted in Figure 15-2. 3455 In general, any node with no other options in the sub-DAG of Node 3456 (C) will follow Node (C) into the floating DAG, maintaining the 3457 structure of the sub-DAG. 3459 o Node (C) hears a DIO message with an incremented DAGSequenceNumber 3460 from Node (B) and determines it is able to rejoin the grounded DAG 3461 by reattaching at a deeper rank to Node (B). Node (C) adds Node 3462 (B) to its DAG parent set. Node (C) has now safely moved deeper 3463 within the grounded DAG without creating any loops. 3465 o Node (D), and any other sub-DAG of Node (C), will hear the 3466 modified DIO message sourced from Node (C) and follow Node (C) in 3467 a coordinated manner to reattach to the grounded DAG. The final 3468 DAG is depicted in Figure 15-3 3470 B.4. Example: Greedy Parent Selection and Instability 3472 (A) (A) (A) 3473 |\ |\ |\ 3474 | `-----. | `-----. | `-----. 3475 | \ | \ | \ 3476 (B) (C) (B) \ | (C) 3477 \ | | / 3478 `-----. | | .-----` 3479 \| |/ 3480 (C) (B) 3482 -1- -2- -3- 3484 Figure 16: Greedy DAG Parent Selection 3486 Consider the example depicted in Figure 16. A DAG is depicted in 3 3487 different configurations. A usable link between (B) and (C) exists 3488 in all 3 configurations. In Figure 16-1, Node (A) is a DAG parent 3489 for Nodes (B) and (C), and (B)--(C) is a sibling link. In 3490 Figure 16-2, Node (A) is a DAG parent for Nodes (B) and (C), and Node 3491 (B) is also a DAG parent for Node (C). In Figure 16-3, Node (A) is a 3492 DAG parent for Nodes (B) and (C), and Node (C) is also a DAG parent 3493 for Node (B). 3495 If a RPL node is too greedy, in that it attempts to optimize for an 3496 additional number of parents beyond its preferred parent, then an 3497 instability can result. Consider the DAG illustrated in Figure 16-1. 3498 In this example, Nodes (B) and (C) may most prefer Node (A) as a DAG 3499 parent, but are operating under the greedy condition that will try to 3500 optimize for 2 parents. 3502 When the preferred parent selection causes a node to have only one 3503 parent and no siblings, the node may decide to insert itself at a 3504 slightly higher rank in order to have at least one sibling and thus 3505 an alternate forwarding solution. This does not deprive other nodes 3506 of a forwarding solution and this is considered acceptable 3507 greediness. 3509 o Let Figure 16-1 be the initial condition. 3511 o Suppose Node (C) first is able to leave the DAG and rejoin at a 3512 lower rank, taking both Nodes (A) and (B) as DAG parents as 3513 depicted in Figure 16-2. Now Node (C) is deeper than both Nodes 3514 (A) and (B), and Node (C) is satisfied to have 2 DAG parents. 3516 o Suppose Node (B), in its greediness, is willing to receive and 3517 process a DIO message from Node (C) (against the rules of RPL), 3518 and then Node (B) leaves the DAG and rejoins at a lower rank, 3519 taking both Nodes (A) and (C) as DAG parents. Now Node (B) is 3520 deeper than both Nodes (A) and (C) and is satisfied with 2 DAG 3521 parents. 3523 o Then Node (C), because it is also greedy, will leave and rejoin 3524 deeper, to again get 2 parents and have a lower rank then both of 3525 them. 3527 o Next Node (B) will again leave and rejoin deeper, to again get 2 3528 parents 3530 o And again Node (C) leaves and rejoins deeper... 3532 o The process will repeat, and the DAG will oscillate between 3533 Figure 16-2 and Figure 16-3 until the nodes count to infinity and 3534 restart the cycle again. 3536 o This cycle can be averted through mechanisms in RPL: 3538 * Nodes (B) and (C) stay at a rank sufficient to attach to their 3539 most preferred parent (A) and don't go for any deeper (worse) 3540 alternate parents (Nodes are not greedy) 3542 * Nodes (B) and (C) do not process DIO messages from nodes deeper 3543 than themselves (because such nodes are possibly in their own 3544 sub-DAGs) 3546 Appendix C. Outstanding Issues 3548 This section enumerates some outstanding issues that are to be 3549 addressed in future revisions of the RPL specification. 3551 C.1. Additional Support for P2P Routing 3553 In some situations the baseline mechanism to support arbitrary P2P 3554 traffic, by flowing upwards along the DAG until a common ancestor is 3555 reached and then flowing down, may not be suitable for all 3556 application scenarios. A related scenario may occur when the down 3557 paths setup along the DAG by the destination advertisement mechanism 3558 are not be the most desirable downward paths for the specific 3559 application scenario (in part because the DAG links may not be 3560 symmetric). It may be desired to support within RPL the discovery 3561 and installation of more direct routes `across' the DAG. Such 3562 mechanisms need to be investigated. 3564 C.2. Loop Detection 3566 It is under investigation to complement the loop avoidance strategies 3567 provided by RPL with a loop detection mechanism that may be employed 3568 when traffic is forwarded. 3570 C.3. Destination Advertisement / DAO Fan-out 3572 When DAO messages are relayed to more than one DAG parent, in some 3573 cases a situation may be created where a large number of DAO messages 3574 conveying information about the same destination flow upwards along 3575 the DAG. It is desirable to bound/limit the multiplication/fan-out 3576 of DAO messages in this manner. Some aspects of the Destination 3577 Advertisement mechanism remain under investigation, such as behavior 3578 in the face of links that may not be symmetric. 3580 In general, the utility of providing redundancy along downwards 3581 routes by sending DAO messages to more than one parent is under 3582 investigation. 3584 The use of suitable triggers, such as the `D' bit, to trigger DA 3585 operation within an affected sub-DAG, is under investigation. 3586 Further, the ability to limit scope of the affected depth within the 3587 sub-DAG is under investigation (e.g. if a stateful node can proxy for 3588 all nodes `behind' it, then there may be no need to propagate the 3589 triggered `D' bit further). 3591 C.4. Source Routing 3593 In support of nodes that maintain minimal routing state, and to make 3594 use of the collection of piecewise source routes from the destination 3595 advertisement mechanism, there needs to be some investigation of a 3596 mechanism to specify, attach, and follow source routes for packets 3597 traversing the LLN. 3599 C.5. Address / Header Compression 3601 In order to minimize overhead within the LLN it is desirable to 3602 perform some sort of address and/or header compression, perhaps via 3603 labels, addresses aggregation, or some other means. This is still 3604 under investigation. 3606 Authors' Addresses 3608 Tim Winter (editor) 3610 Email: wintert@acm.org 3612 Pascal Thubert (editor) 3613 Cisco Systems 3614 Village d'Entreprises Green Side 3615 400, Avenue de Roumanille 3616 Batiment T3 3617 Biot - Sophia Antipolis 06410 3618 FRANCE 3620 Phone: +33 497 23 26 34 3621 Email: pthubert@cisco.com 3623 ROLL Design Team 3624 IETF ROLL WG 3626 Email: rpl-authors@external.cisco.com