idnits 2.17.1 draft-ietf-roll-rpl-07.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 (March 8, 2010) is 5156 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 (-15) exists of draft-ietf-manet-nhdp-11 == Outdated reference: A later version (-20) exists of draft-ietf-roll-of0-01 == 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 (~~), 6 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: September 9, 2010 Cisco Systems 6 ROLL Design Team 7 IETF ROLL WG 8 March 8, 2010 10 RPL: IPv6 Routing Protocol for Low power and Lossy Networks 11 draft-ietf-roll-rpl-07 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 September 9, 2010. 55 Copyright Notice 57 Copyright (c) 2010 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 . . . . . . . . . . . . . . . . . . . . . . . . . 6 73 1.1. Design Principles . . . . . . . . . . . . . . . . . . . . 6 74 1.2. Expectations of Link Layer Type . . . . . . . . . . . . . 7 75 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 7 76 3. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 9 77 3.1. Topology . . . . . . . . . . . . . . . . . . . . . . . . . 9 78 3.1.1. Topology Identifiers . . . . . . . . . . . . . . . . . 9 79 3.1.2. DODAG Information . . . . . . . . . . . . . . . . . . 10 80 3.2. Instances, DODAGs, and DODAG Iterations . . . . . . . . . 11 81 3.3. Traffic Flows . . . . . . . . . . . . . . . . . . . . . . 13 82 3.3.1. Multipoint-to-Point Traffic . . . . . . . . . . . . . 13 83 3.3.2. Point-to-Multipoint Traffic . . . . . . . . . . . . . 13 84 3.3.3. Point-to-Point Traffic . . . . . . . . . . . . . . . . 13 85 3.4. Upward Routes and DODAG Construction . . . . . . . . . . . 13 86 3.4.1. DODAG Information Object (DIO) . . . . . . . . . . . . 14 87 3.4.2. DAG Repair . . . . . . . . . . . . . . . . . . . . . . 14 88 3.4.3. Grounded and Floating DODAGs . . . . . . . . . . . . . 15 89 3.4.4. Administrative Preference . . . . . . . . . . . . . . 15 90 3.4.5. Objective Function (OF) . . . . . . . . . . . . . . . 15 91 3.4.6. Distributed Algorithm Operation . . . . . . . . . . . 15 92 3.5. Downward Routes and Destination Advertisement . . . . . . 16 93 3.5.1. Destination Advertisement Object (DAO) . . . . . . . . 16 94 3.6. Routing Metrics and Constraints Used By RPL . . . . . . . 17 95 3.6.1. Loop Avoidance . . . . . . . . . . . . . . . . . . . . 18 96 3.6.2. Rank Properties . . . . . . . . . . . . . . . . . . . 19 97 4. ICMPv6 RPL Control Message . . . . . . . . . . . . . . . . . . 21 98 5. Upward Routes . . . . . . . . . . . . . . . . . . . . . . . . 22 99 5.1. DODAG Information Object (DIO) . . . . . . . . . . . . . . 22 100 5.1.1. DIO Base Format . . . . . . . . . . . . . . . . . . . 22 101 5.1.2. DIO Base Rules . . . . . . . . . . . . . . . . . . . . 24 102 5.1.3. DIO Suboptions . . . . . . . . . . . . . . . . . . . . 25 103 5.2. DODAG Information Solicitation (DIS) . . . . . . . . . . . 30 104 5.3. Upward Route Discovery and Maintenance . . . . . . . . . . 30 105 5.3.1. RPL Instance . . . . . . . . . . . . . . . . . . . . . 30 106 5.3.2. Neighbors and Parents within a DODAG Iteration . . . . 30 107 5.3.3. Neighbors and Parents across DODAG Iterations . . . . 31 108 5.3.4. DIO Message Communication . . . . . . . . . . . . . . 36 109 5.3.5. DIO Transmission . . . . . . . . . . . . . . . . . . . 36 110 5.3.6. DODAG Selection . . . . . . . . . . . . . . . . . . . 39 111 5.4. Operation as a Leaf Node . . . . . . . . . . . . . . . . . 39 112 5.5. Administrative Rank . . . . . . . . . . . . . . . . . . . 40 113 5.6. Collision . . . . . . . . . . . . . . . . . . . . . . . . 40 114 6. Downward Routes . . . . . . . . . . . . . . . . . . . . . . . 40 115 6.1. Destination Advertisement Object (DAO) . . . . . . . . . . 41 116 6.1.1. DAO Suboptions . . . . . . . . . . . . . . . . . . . . 42 117 6.2. Downward Route Discovery and Maintenance . . . . . . . . . 43 118 6.2.1. Overview . . . . . . . . . . . . . . . . . . . . . . . 43 119 6.2.2. Mode of Operation . . . . . . . . . . . . . . . . . . 44 120 6.2.3. Destination Advertisement Parents . . . . . . . . . . 44 121 6.2.4. Operation of DAO Storing Nodes . . . . . . . . . . . . 45 122 6.2.5. Operation of DAO Non-storing Nodes . . . . . . . . . . 48 123 6.2.6. Scheduling to Send DAO (or no-DAO) . . . . . . . . . . 49 124 6.2.7. Triggering DAO Message from the Sub-DODAG . . . . . . 49 125 6.2.8. Sending DAO Messages to DAO Parents . . . . . . . . . 51 126 6.2.9. Multicast Destination Advertisement Messages . . . . . 52 127 7. Packet Forwarding and Loop Avoidance/Detection . . . . . . . . 52 128 7.1. Suggestions for Packet Forwarding . . . . . . . . . . . . 53 129 7.2. Loop Avoidance and Detection . . . . . . . . . . . . . . . 54 130 7.2.1. Source Node Operation . . . . . . . . . . . . . . . . 55 131 7.2.2. Router Operation . . . . . . . . . . . . . . . . . . . 55 132 8. Multicast Operation . . . . . . . . . . . . . . . . . . . . . 57 133 9. Maintenance of Routing Adjacency . . . . . . . . . . . . . . . 58 134 10. Guidelines for Objective Functions . . . . . . . . . . . . . . 59 135 11. RPL Constants and Variables . . . . . . . . . . . . . . . . . 61 136 12. Manageability Considerations . . . . . . . . . . . . . . . . . 62 137 12.1. Control of Function and Policy . . . . . . . . . . . . . . 62 138 12.1.1. Initialization Mode . . . . . . . . . . . . . . . . . 62 139 12.1.2. DIO Base option . . . . . . . . . . . . . . . . . . . 63 140 12.1.3. Trickle Timers . . . . . . . . . . . . . . . . . . . . 63 141 12.1.4. DAG Sequence Number Increment . . . . . . . . . . . . 64 142 12.1.5. Destination Advertisement Timers . . . . . . . . . . . 64 143 12.1.6. Policy Control . . . . . . . . . . . . . . . . . . . . 64 144 12.1.7. Data Structures . . . . . . . . . . . . . . . . . . . 65 145 12.2. Information and Data Models . . . . . . . . . . . . . . . 65 146 12.3. Liveness Detection and Monitoring . . . . . . . . . . . . 65 147 12.3.1. Candidate Neighbor Data Structure . . . . . . . . . . 65 148 12.3.2. Directed Acyclic Graph (DAG) Table . . . . . . . . . . 65 149 12.3.3. Routing Table . . . . . . . . . . . . . . . . . . . . 66 150 12.3.4. Other RPL Monitoring Parameters . . . . . . . . . . . 67 151 12.3.5. RPL Trickle Timers . . . . . . . . . . . . . . . . . . 67 152 12.4. Verifying Correct Operation . . . . . . . . . . . . . . . 67 153 12.5. Requirements on Other Protocols and Functional 154 Components . . . . . . . . . . . . . . . . . . . . . . . . 67 155 12.6. Impact on Network Operation . . . . . . . . . . . . . . . 67 156 13. Security Considerations . . . . . . . . . . . . . . . . . . . 67 157 14. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 67 158 14.1. RPL Control Message . . . . . . . . . . . . . . . . . . . 68 159 14.2. New Registry for RPL Control Codes . . . . . . . . . . . . 68 160 14.3. New Registry for the Control Field of the DIO Base . . . . 68 161 14.4. DODAG Information Object (DIO) Suboption . . . . . . . . . 69 162 15. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 69 163 16. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 70 164 17. References . . . . . . . . . . . . . . . . . . . . . . . . . . 71 165 17.1. Normative References . . . . . . . . . . . . . . . . . . . 71 166 17.2. Informative References . . . . . . . . . . . . . . . . . . 72 167 Appendix A. Requirements . . . . . . . . . . . . . . . . . . . . 74 168 A.1. Protocol Properties Overview . . . . . . . . . . . . . . . 74 169 A.1.1. IPv6 Architecture . . . . . . . . . . . . . . . . . . 74 170 A.1.2. Typical LLN Traffic Patterns . . . . . . . . . . . . . 74 171 A.1.3. Constraint Based Routing . . . . . . . . . . . . . . . 74 172 A.2. Deferred Requirements . . . . . . . . . . . . . . . . . . 75 173 Appendix B. Examples . . . . . . . . . . . . . . . . . . . . . . 75 174 B.1. DAO Operation When Only the Root Node Stores DAO 175 Information . . . . . . . . . . . . . . . . . . . . . . . 75 176 B.2. DAO Operation When All Nodes Fully Store DAO 177 Information . . . . . . . . . . . . . . . . . . . . . . . 77 178 B.3. DAO Operation When Nodes Have Mixed Capabilities . . . . . 79 179 Appendix C. Outstanding Issues . . . . . . . . . . . . . . . . . 81 180 C.1. Additional Support for P2P Routing . . . . . . . . . . . . 81 181 C.2. Destination Advertisement / DAO Fan-out . . . . . . . . . 81 182 C.3. Source Routing . . . . . . . . . . . . . . . . . . . . . . 81 183 C.4. Address / Header Compression . . . . . . . . . . . . . . . 81 184 C.5. Managing Multiple Instances . . . . . . . . . . . . . . . 82 185 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 82 187 1. Introduction 189 Low power and Lossy Networks (LLNs) consist of largely of constrained 190 nodes (with limited processing power, memory, and sometimes energy 191 when they are battery operated). These routers are interconnected by 192 lossy links, typically supporting only low data rates, that are 193 usually unstable with relatively low packet delivery rates. Another 194 characteristic of such networks is that the traffic patterns are not 195 simply unicast, but in many cases point-to-multipoint or multipoint- 196 to-point. Furthermore such networks may potentially comprise up to 197 thousands of nodes. These characteristics offer unique challenges to 198 a routing solution: the IETF ROLL Working Group has defined 199 application-specific routing requirements for a Low power and Lossy 200 Network (LLN) routing protocol, specified in 201 [I-D.ietf-roll-building-routing-reqs], 202 [I-D.ietf-roll-home-routing-reqs], [RFC5673], and [RFC5548]. This 203 document specifies the IPv6 Routing Protocol for Low power and lossy 204 networks (RPL). 206 1.1. Design Principles 208 RPL was designed with the objective to meet the requirements spelled 209 out in [I-D.ietf-roll-building-routing-reqs], 210 [I-D.ietf-roll-home-routing-reqs], [RFC5673], and [RFC5548]. Because 211 those requirements are heterogeneous and sometimes incompatible in 212 nature, the approach is first taken to design a protocol capable of 213 supporting a core set of functionalities corresponding to the 214 intersection of the requirements. As the RPL design evolves optional 215 features may be added to address some application specific 216 requirements. This is a key protocol design decision providing a 217 granular approach in order to restrict the core of the protocol to a 218 minimal set of functionalities, and to allow each implementation of 219 the protocol to be optimized differently. All "MUST" application 220 requirements that cannot be satisfied by RPL will be specifically 221 listed in the Appendix A, accompanied by a justification. 223 A network may run multiple instances of RPL concurrently. Each such 224 instance may serve different and potentially antagonistic constraints 225 or performance criteria. This document defines how a single instance 226 operates. 228 RPL is a generic protocol that is to be deployed by instantiating the 229 generic operation described in this document with a specific 230 objective function (OF) (which ties together metrics, constraints, 231 and an optimization objective) to realize a desired objective in a 232 given environment. 234 A set of companion documents to this specification will provide 235 further guidance in the form of applicability statements specifying a 236 set of operating points appropriate to the Building Automation, Home 237 Automation, Industrial, and Urban application scenarios. 239 1.2. Expectations of Link Layer Type 241 RPL does not rely on any particular features of a specific link layer 242 technology. RPL is designed to be able to operate over a variety of 243 different link layers, including but not limited to, low power 244 wireless or PLC (Power Line Communication) technologies. 246 Implementers may find RFC 3819 [RFC3819] a useful reference when 247 designing a link layer interface between RPL and a particular link 248 layer technology. 250 2. Terminology 252 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 253 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 254 "OPTIONAL" in this document are to be interpreted as described in RFC 255 2119 [RFC2119]. 257 Additionally, this document uses terminology from 258 [I-D.ietf-roll-terminology], and introduces the following 259 terminology: 261 DAG: Directed Acyclic Graph. A directed graph having the property 262 that all edges are oriented in such a way that no cycles exist. 263 All edges are contained in paths oriented toward and 264 terminating at one or more root nodes. 266 DAG root: A DAG root is a node within the DAG that has no outgoing 267 edges. Because the graph is acyclic, by definition all DAGs 268 must have at least one DAG root and all paths terminate at a 269 DAG root. 271 Destination Oriented DAG (DODAG): A DAG rooted at a single 272 destination, i.e. at a single DAG root (the DODAG root) with no 273 outgoing edges. 275 DODAG root: A DODAG root is the DAG root of a DODAG. 277 Rank: The rank of a node in a DAG identifies the nodes position with 278 respect to a DODAG root. The farther away a node is from a 279 DODAG root, the higher is the rank of that node. The rank of a 280 node may be a simple topological distance, or may more commonly 281 be calculated as a function of other properties as described 282 later. 284 DODAG parent: A parent of a node within a DODAG is one of the 285 immediate successors of the node on a path towards the DODAG 286 root. The DODAG parent of a node will have a lower rank than 287 the node itself. (See Section 3.6.2.1). 289 DODAG sibling: A sibling of a node within a DODAG is defined in this 290 specification to be any neighboring node which is located at 291 the same rank within a DODAG. Note that siblings defined in 292 this manner do not necessarily share a common DODAG parent. 293 (See Section 3.6.2.1). 295 Sub-DODAG The sub-DODAG of a node is the set of other nodes in the 296 DODAG that might use a path towards the DODAG root that 297 contains that node. Nodes in the sub-DODAG of a node have a 298 greater rank than that node itself (although not all nodes of 299 greater rank are necessarily in the sub-DODAG of that node). 300 (See Section 3.6.2.1). 302 DODAGID: The identifier of a DODAG root. The DODAGID must be unique 303 within the scope of a RPL Instance in the LLN. 305 DODAG Iteration: A specific sequence number iteration ("version") of 306 a DODAG with a given DODAGID. 308 RPL Instance: A set of possibly multiple DODAGs. A network may have 309 more than one RPL Instance, and a RPL node can participate in 310 multiple RPL Instances. Each RPL Instance operates 311 independently of other RPL Instances. This document describes 312 operation within a single RPL Instance. In RPL, a node can 313 belong to at most one DODAG per RPL Instance. The tuple 314 (RPLInstanceID, DODAGID) uniquely identifies a DODAG. 316 RPLInstanceID: Unique identifier of a RPL Instance. 318 DODAGSequenceNumber: A sequential counter that is incremented by the 319 root to form a new Iteration of a DODAG. A DODAG Iteration is 320 identified uniquely by the (RPLInstanceID, DODAGID, 321 DODAGSequenceNumber) tuple. 323 Up: Up refers to the direction from leaf nodes towards DODAG roots, 324 following the orientation of the edges within the DODAG. 326 Down: Down refers to the direction from DODAG roots towards leaf 327 nodes, going against the orientation of the edges within the 328 DODAG. 330 Objective Code Point (OCP): An identifier, used to indicate which 331 Objective Function is in use for forming a DODAG. The 332 Objective Code Point is further described in 333 [I-D.ietf-roll-routing-metrics]. 335 Objective Function (OF): Defines which routing metrics, optimization 336 objectives, and related functions are in use in a DODAG. The 337 Objective Function is further described in 338 [I-D.ietf-roll-routing-metrics]. 340 Goal: The Goal is a host or set of hosts that satisfy a particular 341 application objective / OF. Whether or not a DODAG can provide 342 connectivity to a goal is a property of the DODAG. For 343 example, a goal might be a host serving as a data collection 344 point, or a gateway providing connectivity to an external 345 infrastructure. 347 Grounded: A DODAG is said to be grounded, when the root can reach 348 the Goal of the objective function. 350 Floating: A DODAG is floating if is not Grounded. A floating DODAG 351 is not expected to reach the Goal defined for the OF. 353 As they form networks, LLN devices often mix the roles of 'host' and 354 'router' when compared to traditional IP networks. In this document, 355 'host' refers to an LLN device that can generate but does not forward 356 RPL traffic, 'router' refers to an LLN device that can forward as 357 well as generate RPL traffic, and 'node' refers to any RPL device, 358 either a host or a router. 360 3. Protocol Overview 362 The aim of this section is to describe RPL in the spirit of 363 [RFC4101]. Protocol details can be found in further sections. 365 3.1. Topology 367 This section describes how the basic RPL topologies, and the rules by 368 which these are constructed, i.e. the rules governing DODAG 369 formation. 371 3.1.1. Topology Identifiers 373 RPL uses four identifiers to track and control the topology: 375 o The first is a RPLInstanceID. A RPLInstanceID identifies a set of 376 one or more DODAGs. All DODAGs in the same RPL Instance use the 377 same OF. A network may have multiple RPLInstanceIDs, each of 378 which defines an independent set of DODAGs, which may be optimized 379 for different OFs and/or applications. The set of DODAGs 380 identified by a RPLInstanceID is called a RPL Instance. 382 o The second is a DODAGID. The scope of a DODAGID is a RPL 383 Instance. The combination of RPLInstanceID and DODAGID uniquely 384 identifies a single DODAG in the network. A RPL Instance may have 385 multiple DODAGs, each of which has an unique DODAGID. 387 o The third is a DODAGSequenceNumber. The scope of a 388 DODAGSequenceNumber is a DODAG. A DODAG is sometimes 389 reconstructed from the DODAG root, by incrementing the 390 DODAGSequenceNumber. The combination of RPLInstanceID, DODAGID, 391 and DODAGSequenceNumber uniquely identifies a DODAG Iteration. 393 o The fourth is rank. The scope of rank is a DODAG Iteration. Rank 394 establishes a partial order over a DODAG Iteration, defining 395 individual node positions with respect to the DODAG root. 397 3.1.2. DODAG Information 399 For each DODAG that a node is, or may become, a member of, the 400 implementation should conceptually keep track of the following 401 information. The data structures described in this section are 402 intended to illustrate a possible implementation to aid in the 403 description of the protocol, but are not intended to be normative. 405 o RPLInstanceID 407 o DODAGID 409 o DODAGSequenceNumber 411 o DAG Metric Container, including DAGObjectiveCodePoint 413 o A set of Destination Prefixes offered by the DODAG root and 414 available via paths upwards along the DODAG 416 o A set of DODAG parents 418 o A set of DODAG siblings 420 o A timer to govern the sending of RPL control messages 422 3.2. Instances, DODAGs, and DODAG Iterations 424 Each RPL Instance constructs a routing topology optimized for a 425 certain Objective Function (OF). A RPL Instance may provide routes 426 to certain destination prefixes, reachable via the DODAG roots. A 427 single RPL Instance contains one or more Destination Oriented DAG 428 (DODAG) roots. These roots may operate independently, or may 429 coordinate over a non-LLN backchannel. 431 Each root has a unique identifier, the DODAGID. 433 A RPL Instance may comprise: 435 o a single DODAG with a single root 437 * For example, a DODAG optimized to minimize latency rooted at a 438 single centralized lighting controller in a home automation 439 application. 441 o multiple uncoordinated DODAGs with independent roots (differing 442 DODAGIDs) 444 * For example, multiple data collection points in an urban data 445 collection application that do not have an always-on backbone 446 suitable to coordinate to form a single DODAG, and further use 447 the formation of multiple DODAGs as a means to dynamically and 448 autonomously partition the network. 450 o a single DODAG with a single virtual root coordinating LLN sinks 451 (with the same DODAGID) over some non-LLN backbone 453 * For example, multiple border routers operating with a reliable 454 backbone, e.g. in support of a 6LowPAN application, that are 455 capable to act as logically equivalent sinks to the same DODAG. 457 o a combination of the above as suited to some application scenario. 459 Traffic is bound to a specific RPL Instance by a marking in the flow 460 label of the IPv6 header. Traffic originating in support of a 461 particular application may be tagged to follow an appropriate RPL 462 instance which enables certain (path) properties, for example to 463 follow paths optimized for low latency or low energy. The 464 provisioning or automated discovery of a mapping between a 465 RPLInstanceID and a type or service of application traffic is beyond 466 the scope of this specification. 468 An example of a RPL Instance comprising a number of DODAGs is 469 depicted in Figure 1. A DODAG Iteration (two "versions" of the same 470 DODAG) is depicted in Figure 2. 472 +----------------------------------------------------------------+ 473 | | 474 | +--------------+ | 475 | | | | 476 | | (R1) | (R2) (Rn) | 477 | | / \ | /| \ / | \ | 478 | | / \ | / | \ / | \ | 479 | | (A) (B) | (C) | (D) ... (F) (G) (H) | 480 | | /|\ |\ | / | |\ | | | | 481 | | : : : : : | : (E) : : : : : | 482 | | | / \ | 483 | +--------------+ : : | 484 | DODAG | 485 | | 486 +----------------------------------------------------------------+ 487 RPL Instance 489 Figure 1: RPL Instance 491 +----------------+ +----------------+ 492 | | | | 493 | (R1) | | (R1) | 494 | / \ | | / | 495 | / \ | | / | 496 | (A) (B) | \ | (A) | 497 | /|\ |\ | ------\ | /|\ | 498 | : : (C) : : | \ | : : (C) | 499 | | / | \ | 500 | | ------/ | \ | 501 | | / | (B) | 502 | | | |\ | 503 | | | : : | 504 | | | | 505 +----------------+ +----------------+ 506 Sequence N Sequence N+1 508 Figure 2: DODAG Iteration 510 3.3. Traffic Flows 512 3.3.1. Multipoint-to-Point Traffic 514 Multipoint-to-Point (MP2P) is a dominant traffic flow in many LLN 515 applications ([I-D.ietf-roll-building-routing-reqs], 516 [I-D.ietf-roll-home-routing-reqs], [RFC5673], [RFC5548]). The 517 destinations of MP2P flows are designated nodes that have some 518 application significance, such as providing connectivity to the 519 larger Internet or core private IP network. RPL supports MP2P 520 traffic by allowing MP2P destinations to be reached via DODAG roots. 522 3.3.2. Point-to-Multipoint Traffic 524 Point-to-multipoint (P2MP) is a traffic pattern required by several 525 LLN applications ([I-D.ietf-roll-building-routing-reqs], 526 [I-D.ietf-roll-home-routing-reqs], [RFC5673], [RFC5548]). RPL 527 supports P2MP traffic by using a destination advertisement mechanism 528 that provisions routes toward destination prefixes and away from 529 roots. Destination advertisements can update routing tables as the 530 underlying DODAG topology changes. 532 3.3.3. Point-to-Point Traffic 534 RPL DODAGs provide a basic structure for point-to-point (P2P) 535 traffic. For a RPL network to support P2P traffic, a root must be 536 able to route packets to a destination. Nodes within the network may 537 also have routing tables to destinations. A packet flows towards a 538 root until it reaches an ancestor that has a known route to the 539 destination. 541 RPL also supports the case where a P2P destination is a 'one-hop' 542 neighbor. 544 RPL neither specifies nor precludes additional mechanisms for 545 computing and installing more optimal routes to support arbitrary P2P 546 traffic. 548 3.4. Upward Routes and DODAG Construction 550 RPL provisions routes up towards DODAG roots, forming a DODAG 551 optimized according to the Objective Function (OF) in use. RPL nodes 552 construct and maintain these DODAGs through exchange of DODAG 553 Information Object (DIO) messages. Undirected links between siblings 554 are also identified during this process, which can be used to provide 555 additional diversity. 557 3.4.1. DODAG Information Object (DIO) 559 A DIO identifies the RPL Instance, the DODAGID, the values used to 560 compute the RPL Instance's objective function, and the present DODAG 561 Sequence Number. It can also include additional routing and 562 configuration information. The DIO includes a measure derived from 563 the position of the node within the DODAG, the rank, which is used 564 for nodes to determine their positions relative to each other and to 565 inform loop avoidance/detection procedures. RPL exchanges DIO 566 messages to establish and maintain routes. 568 RPL adapts the rate at which nodes send DIO messages. When a DODAG 569 is detected to be inconsistent or needs repair, RPL sends DIO 570 messages more frequently. As the DODAG stabilizes, the DIO message 571 rate tapers off, reducing the maintenance cost of a steady and well- 572 working DODAG. 574 This document defines an ICMPv6 Message Type "RPL Control Message", 575 which is capable of carrying a DIO. 577 3.4.2. DAG Repair 579 RPL supports global repair over the DODAG. A DODAG Root may 580 increment the DODAG Sequence Number, thereby initiating a new DODAG 581 iteration. This institutes a global repair operation, revising the 582 DODAG and allowing nodes to choose an arbitrary new position within 583 the new DODAG iteration. 585 RPL supports mechanisms which may be used for local repair within the 586 DODAG iteration. The DIO message specifies the necessary parameters 587 as configured from the DODAG root. Local repair options include the 588 allowing a node, upon detecting a loss of connectivity to a DODAG it 589 is a member of, to: 591 o Poison its sub-DODAG by advertising an effective rank of INFINITY 592 to its sub-DODAG, OR detach and form a floating DODAG in order to 593 preserve inner connectivity within its sub-DODAG. 595 o Move down within the DODAG iteration (i.e. increase its rank) in a 596 limited manner, no further than a bound configured by the DODAG 597 root via the DIO so as not to count all the way to infinity. Such 598 a move may be undertaken after waiting an appropriate poisoning 599 interval, and should allow the node to restore connectivity to the 600 DODAG Iteration, if at all possible. 602 3.4.3. Grounded and Floating DODAGs 604 DODAGs can be grounded or floating. A grounded DODAG offers 605 connectivity to to a goal. A floating DODAG offers no such 606 connectivity, and provides routes only to nodes within the DODAG. 607 Floating DODAGs may be used, for example, to preserve inner 608 connectivity during repair. 610 3.4.4. Administrative Preference 612 An implementation/deployment may specify that some DODAG roots should 613 be used over others through an administrative preference. 614 Administrative preference offers a way to control traffic and 615 engineer DODAG formation in order to better support application 616 requirements or needs. 618 3.4.5. Objective Function (OF) 620 The Objective Function (OF) implements the optimization objectives of 621 route selection within the RPL Instance. The OF is identified by an 622 Objective Code Point (OCP) within the DIO, and its specification also 623 indicates the metrics and constraints in use. The OF also specifies 624 the procedure used to compute rank within a DODAG iteration. Further 625 details may be found in [I-D.ietf-roll-routing-metrics], 626 [I-D.ietf-roll-of0], and related companion specifications. 628 By using defined OFs that are understood by all nodes in a particular 629 deployment, and by referencing these in the DIO message, RPL nodes 630 may work to build optimized LLN routes using a variety of application 631 and implementation specific metrics and goals. 633 In the case where a node is unable to encounter a suitable RPL 634 Instance using a known Objective Function, it may be configured to 635 join a RPL Instance using an unknown Objective Function - but in that 636 case only acting as a leaf node. 638 3.4.6. Distributed Algorithm Operation 640 A high level overview of the distributed algorithm which constructs 641 the DODAG is as follows: 643 o Some nodes are configured to be DODAG roots, with associated DODAG 644 configuration. 646 o Nodes advertise their presence, affiliation with a DODAG, routing 647 cost, and related metrics by sending link-local multicast DIO 648 messages. 650 o Nodes may adjust the rate at which DIO messages are sent in 651 response to stability or detection of routing inconsistencies. 653 o Nodes listen for DIOs and use their information to join a new 654 DODAG, or to maintain an existing DODAG, as according to the 655 specified Objective Function and rank-based loop avoidance rules. 657 o Nodes provision routing table entries, for the destinations 658 specified by the DIO, via their DODAG parents in the DODAG 659 iteration. Nodes may provision a DODAG parent as a default 660 gateway. 662 o Nodes may identify DODAG siblings within the DODAG iteration to 663 increase path diversity. 665 o Using DIOs, and possibly information in data packets, RPL nodes 666 detect possible routing loops. When a RPL node detects a possible 667 routing loop, it may adapt its DIO transmission rate to apply a 668 local repair to the topology. 670 3.5. Downward Routes and Destination Advertisement 672 RPL constructs and maintains DODAGs with DIO messages to establish 673 upward routes: it uses Destination Advertisement Object (DAO) 674 messages to establish downward routes along the DODAG as well as 675 other routes. DAO messages are an optional feature for applications 676 that require P2MP or P2P traffic. DIO messages advertise whether 677 destination advertisements are enabled within a given DODAG. 679 3.5.1. Destination Advertisement Object (DAO) 681 A Destination Advertisement Object (DAO) conveys destination 682 information upwards along the DODAG so that a DODAG root (and other 683 intermediate nodes) can provision downward routes. A DAO message 684 includes prefix information to identify destinations, a capability to 685 record routes in support of source routing, and information to 686 determine the freshness of a particular advertisement. 688 Nodes that are capable of maintaining routing state may aggregate 689 routes from DAO messages that they receive before transmitting a DAO 690 message. Nodes that are not capable of maintaining routing state may 691 attach a next-hop address to the Reverse Route Stack contained within 692 the DAO message. The Reverse Route Stack is subsequently used to 693 generate piecewise source routes over regions of the LLN that are 694 incapable of storing downward routing state. 696 A special case of the DAO message, termed a no-DAO, is used to clear 697 downward routing state that has been provisioned through DAO 698 operation. 700 This document defines an ICMPv6 Message Type "RPL Control Message", 701 which is capable of carrying a DAO. 703 3.5.1.1. 'One-Hop' Neighbors 705 In addition to sending DAOs toward DODAG roots, RPL nodes may 706 occasionally emit a link-local multicast DAO message advertising 707 available destination prefixes. This mechanism allow provisioning a 708 trivial 'one-hop' route to local neighbors. 710 3.6. Routing Metrics and Constraints Used By RPL 712 Routing metrics are used by routing protocols to compute shortest 713 paths. Interior Gateway Protocols (IGPs) such as IS-IS ([RFC5120]) 714 and OSPF ([RFC4915]) use static link metrics. Such link metrics can 715 simply reflect the bandwidth or can also be computed according to a 716 polynomial function of several metrics defining different link 717 characteristics; in all cases they are static metrics. Some routing 718 protocols support more than one metric: in the vast majority of the 719 cases, one metric is used per (sub)topology. Less often, a second 720 metric may be used as a tie-breaker in the presence of Equal Cost 721 Multiple Paths (ECMP). The optimization of multiple metrics is known 722 as an NP complete problem and is sometimes supported by some 723 centralized path computation engine. 725 In contrast, LLNs do require the support of both static and dynamic 726 metrics. Furthermore, both link and node metrics are required. In 727 the case of RPL, it is virtually impossible to define one metric, or 728 even a composite metric, that will satisfy all use cases. 730 In addition, RPL supports constrained-based routing where constraints 731 may be applied to both link and nodes. If a link or a node does not 732 satisfy a required constraint, it is 'pruned' from the candidate 733 list, thus leading to a constrained shortest path. 735 The set of supported link/node constraints and metrics is specified 736 in [I-D.ietf-roll-routing-metrics]. 738 The role of the Objective Function is to specify which routing 739 metrics and constraints are in use, and how these are used, in 740 addition to the objectives used to compute the (constrained) shortest 741 path. 743 Example 1: Shortest path: path offering the shortest end-to-end delay 745 Example 2: Constrained shortest path: the path that does not traverse 746 any battery-operated node and that optimizes the path 747 reliability 749 3.6.1. Loop Avoidance 751 RPL guarantees neither loop free path selection nor strong global 752 convergence. In order to reduce control overhead, however, such as 753 the cost of the count-to-infinity problem, RPL avoids creating loops 754 when undergoing topology changes. Furthermore, RPL includes rank- 755 based mechanisms for detecting loops when they do occur. RPL uses 756 this loop detection to ensure that packets make forward progress 757 within the DODAG iteration and trigger repairs when necessary. 759 3.6.1.1. Greediness and Rank-based Instabilities 761 Once a node has joined a DODAG iteration, RPL disallows certain 762 behaviors, including greediness, in order to prevent resulting 763 instabilities in the DODAG iteration. 765 If a node is allowed to be greedy and attempts to move deeper in the 766 DODAG iteration, beyond its most preferred parent, in order to 767 increase the size of the parent set, then an instability can result. 769 Suppose a node is willing to receive and process a DIO messages from 770 a node in its own sub-DODAG, and in general a node deeper than 771 itself. In this case, a possibility exists that a feedback loop is 772 created, wherein two or more nodes continue to try and move in the 773 DODAG iteration while attempting to optimize against each other. In 774 some cases, this will result in instability. It is for this reason 775 that RPL limits the cases where a node may process DIO messages from 776 deeper nodes to some forms of local repair. This approach creates an 777 'event horizon', whereby a node cannot be influenced beyond some 778 limit into an instability by the action of nodes that may be in its 779 own sub-DODAG. 781 3.6.1.2. DODAG Loops 783 A DODAG loop may occur when a node detaches from the DODAG and 784 reattaches to a device in its prior sub-DODAG. This may happen in 785 particular when DIO messages are missed. Strict use of the DAG 786 sequence number can eliminate this type of loop, but this type of 787 loop may possibly be encountered when using some local repair 788 mechanisms. 790 3.6.1.3. DAO Loops 792 A DAO loop may occur when the parent has a route installed upon 793 receiving and processing a DAO message from a child, but the child 794 has subsequently cleaned up the related DAO state. This loop happens 795 when a no-DAO was missed and persists until all state has been 796 cleaned up. RPL includes loop detection mechanisms that may mitigate 797 the impact of DAO loops and trigger their repair. 799 In the case where stateless DAO operation is used, i.e. source 800 routing specifies the down routes, then DAO Loops should not occur on 801 the stateless portions of the path. 803 3.6.1.4. Sibling Loops 805 Sibling loops could occur if a group of siblings kept choosing 806 amongst themselves as successors such that a packet does not make 807 forward progress. This specification limits the number of times that 808 sibling forwarding may be used at a given rank, in order to prevent 809 sibling loops. 811 3.6.2. Rank Properties 813 The rank of a node is a scalar representation of the location of that 814 node within a DODAG iteration. The rank is used to avoid and detect 815 loops, and as such must demonstrate certain properties. The exact 816 calculation of the rank is left to the Objective Function, and may 817 depend on parents, link metrics, and the node configuration and 818 policies. 820 The rank is not a cost metric, although its value can be derived from 821 and influenced by metrics. The rank has properties of its own that 822 are not necessarily those of all metrics: 824 Type: Rank is an abstract scalar. Some metrics are boolean (e.g. 825 grounded), others are statistical and better expressed as a 826 tuple like an expected value and a variance. Some OCPs use 827 not one but a set of metrics bound by a piece of logic. 829 Function: Rank is the expression of a relative position within a 830 DODAG iteration with regard to neighbors and is not 831 necessarily a good indication or a proper expression of a 832 distance or a cost to the root. 834 Stability: The stability of the rank determines the stability of the 835 routing topology. Some dampening or filtering might be 836 applied to keep the topology stable, and thus the rank does 837 not necessarily change as fast as some physical metrics 838 would. A new DODAG iteration would be a good opportunity to 839 reconcile the discrepancies that might form over time between 840 metrics and ranks within a DODAG iteration. 842 Granularity: Rank is coarse grained. A fine granularity would 843 prevent the selection of siblings. 845 Properties: Rank is strictly monotonic, and can be used to validate 846 a progression from or towards the root. A metric, like 847 bandwidth or jitter, does not necessarily exhibit this 848 property. 850 Abstract: Rank does not have a physical unit, but rather a range of 851 increment per hop, where the assignment of each increment is 852 to be determined by the implementation. 854 The rank value feeds into DODAG parent selection, according to the 855 RPL loop-avoidance strategy. Once a parent has been added, and a 856 rank value for the node within the DODAG has been advertised, the 857 nodes further options with regard to DODAG parent selection and 858 movement within the DODAG are restricted in favor of loop avoidance. 860 3.6.2.1. Rank Comparison (DAGRank()) 862 Rank may be thought of as a fixed point number, where the position of 863 the decimal point between the integer part and the fractional part is 864 determined by MinHopRankIncrease. MinHopRankIncrease is the minimum 865 increase in rank between a node and any of its DODAG parents. When 866 an objective function computes rank, the objective function operates 867 on the entire (i.e. 16-bit) rank quantity. When rank is compared, 868 e.g. for determination of parent/sibling relationships or loop 869 detection, the integer portion of the rank is to be used. The 870 integer portion of the Rank is computed by the DAGRank() macro as 871 follows: 873 DAGRank(rank) = floor(rank/MinHopRankIncrease) 875 MinHopRankIncrease is provisioned at the DODAG Root and propagated in 876 the DIO message. For efficient implementation the MinHopRankIncrease 877 SHOULD be a power of 2. An implementation may configure a value 878 MinHopRankIncrease as appropriate to balance between the loop 879 avoidance logic of RPL (i.e. selection of eligible parents and 880 siblings) and the metrics in use. 882 By convention in this document, using the macro DAGRank(node) may be 883 interpreted as DAGRank(node.rank), where node.rank is the rank value 884 as maintained by the node. 886 A node A has a rank less than the rank of a node B if DAGRank(A) is 887 less than DAGRank(B). 889 A node A has a rank equal to the rank of a node B if DAGRank(A) is 890 equal to DAGRank(B). 892 A node A has a rank greater than the rank of a node B if DAGRank(A) 893 is greater than DAGRank(B). 895 3.6.2.2. Rank Relationships 897 The computation of the rank MUST be done in such a way so as to 898 maintain the following properties for any nodes M and N that are 899 neighbors in the LLN: 901 DAGRank(M) is less than DAGRank(N): In this case, the position of M 902 is closer to the DODAG root than the position of N. Node M 903 may safely be a DODAG parent for Node N without risk of 904 creating a loop. Further, for a node N, all parents in the 905 DODAG parent set must be of rank less than DAGRank(N). In 906 other words, the rank presented by a node N MUST be greater 907 than that presented by any of its parents. 909 DAGRank(M) equals DAGRank(N): In this case the positions of M and N 910 within the DODAG and with respect to the DODAG root are 911 similar (identical). In some cases, Node M may be used as a 912 successor by Node N, which however entails the chance of 913 creating a loop (which must be detected and resolved by some 914 other means). 916 DAGRank(M) is greater than DAGRank(N): In this case, the position of 917 M is farther from the DODAG root than the position of N. 918 Further, Node M may in fact be in the sub-DODAG of Node N. If 919 node N selects node M as DODAG parent there is a risk to 920 create a loop. 922 As an example, the rank could be computed in such a way so as to 923 closely track ETX when the objective function is to minimize ETX, or 924 latency when the objective function is to minimize latency, or in a 925 more complicated way as appropriate to the objective function being 926 used within the DODAG. 928 4. ICMPv6 RPL Control Message 930 This document defines the RPL Control Message, a new ICMPv6 message. 932 In accordance with [RFC4443], the RPL Control Message has the 933 following format: 935 0 1 2 3 936 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 937 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 938 | Type | Code | Checksum | 939 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 940 | | 941 + Message Body + 942 | | 944 Figure 3: RPL Control Message 946 The RPL Control message is an ICMPv6 information message with a 947 requested Type of 155. 949 The Code field identifies the type of RPL Control Message. This 950 document defines three codes for the following RPL Control Message 951 types: 953 o 0x01: DODAG Information Solicitation (Section 5.2) 955 o 0x02: DODAG Information Object (Section 5.1) 957 o 0x04: Destination Advertisement Object (Section 6.1) 959 5. Upward Routes 961 This section describes how RPL discovers and maintains upward routes. 962 It describes DODAG Information Objects (DIOs), the messages used to 963 discover and maintain these routes. It specifies how RPL generates 964 and responds to DIOs. It also describes DODAG Information 965 Solicitation (DIS) messages, which are used to trigger DIO 966 transmissions. 968 5.1. DODAG Information Object (DIO) 970 The DODAG Information Object carries information that allows a node 971 to discover a RPL Instance, learn its configuration parameters, 972 select a DODAG parent set, and maintain the upward routing topology. 974 5.1.1. DIO Base Format 976 DIO Base is an always-present container option in a DIO message. 977 Every DIO MUST include a DIO Base. 979 0 1 2 3 980 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 981 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 982 |G|A|T|S|0| Prf | Sequence | Rank | 983 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 984 | RPLInstanceID | DTSN | | 985 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 986 | | 987 + + 988 | DODAGID | 989 + + 990 | | 991 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 992 | | sub-option(s)... 993 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 995 Figure 4: DIO Base 997 Control Field: The DAG Control Field has three flags and one field: 999 Grounded (G): The Grounded (G) flag indicates whether the 1000 upward routes this node advertises provide connectivity 1001 to the set of addresses which are application-defined 1002 goals. If the flag is set, the DODAG is grounded and 1003 provides such connectivity. If the flag is cleared, the 1004 DODAG is floating and may not provide such connectivity. 1006 Destination Advertisement Supported (A): The Destination 1007 Advertisement Supported (A) flag indicates whether the 1008 root of this DODAG can collect and use downward route 1009 state. If the flag is set, nodes in the network are 1010 enabled to exchange destination advertisements messages 1011 to build downward routes (Section 6). If the flag is 1012 cleared, destination advertisement messages are disabled 1013 and the DODAG maintains only upward routes. 1015 Destination Advertisement Trigger (T): The Destination 1016 Advertisement Trigger (T) flag indicates a complete 1017 refresh of downward routes. If the flag is set, then a 1018 refresh of downward route state is to take place over the 1019 entire DODAG. If the flag is cleared, the downward route 1020 maintenance is in its normal mode of operation. The 1021 further details of this process are described in 1022 Section 6. 1024 Destination Advertisements Stored (S): The Destination 1025 Advertisements Stored (S) flag is used to indicate that a 1026 non-root ancestor is storing routing table entries 1027 learned from DAO messaging. If the flag is set, then a 1028 non-root ancestor is known to be storing routing table 1029 entries learned from DAO messages. If the flag is 1030 cleared, only the root node may be storing routing table 1031 entries learned from DAO messaging. This flag is further 1032 described in Section 6. 1034 DODAGPreference (Prf): A 3-bit unsigned integer that defines 1035 how preferable the root of this DODAG is compared to 1036 other DODAG roots within the instance. DAGPreference 1037 ranges from 0x00 (least preferred) to 0x07 (most 1038 preferred). The default is 0 (least preferred). 1039 Section 5.3 describes how DAGPreference affects DIO 1040 processing. 1042 Unassigned bits of the Control Field are reserved. They MUST 1043 be set to zero on transmission and MUST be ignored on 1044 reception. 1046 Sequence Number: 8-bit unsigned integer set by the DODAG root. 1047 Section 5.3 describes the rules for sequence numbers and how 1048 they affect DIO processing. 1050 Rank: 16-bit unsigned integer indicating the DODAG rank of the node 1051 sending the DIO message. Section 5.3 describes how Rank is set 1052 and how it affects DIO processing. 1054 RPLInstanceID: 8-bit field set by the DODAG root that indicates 1055 which RPL Instance the DODAG is part of. 1057 Destination Advertisement Trigger Sequence Number (DTSN): 8-bit 1058 unsigned integer set by the node issuing the DIO message. The 1059 Destination Advertisement Trigger Sequence Number (DTSN) flag 1060 is used as part of the procedure to maintain downward routes. 1061 The details of this process are described in Section 6. 1063 DODAGID: 128-bit unsigned integer set by a DODAG root which uniquely 1064 identifies a DODAG. Possibly derived from the IPv6 address of 1065 the DODAG root. 1067 5.1.2. DIO Base Rules 1069 1. If the 'A' flag of a DIO Base is cleared, the 'T' flag MUST also 1070 be cleared. 1072 2. For the following DIO Base fields, a node that is not a DODAG 1073 root MUST advertise the same values as its preferred DODAG parent 1074 (defined in Section 5.3.2). Therefore, if a DODAG root does not 1075 change these values, every node in a route to that DODAG root 1076 eventually advertises the same values for these fields. These 1077 fields are: 1078 1. Grounded (G) 1079 2. Destination Advertisement Supported (A) 1080 3. Destination Advertisement Trigger (T) 1081 4. DAGPreference (Prf) 1082 5. Sequence 1083 6. RPLInstanceID 1084 7. DODAGID 1086 3. A node MAY update the following fields at each hop: 1087 1. Destination Advertisements Stored (S) 1088 2. DAGRank 1089 3. DTSN 1091 4. The DODAGID field each root sets MUST be unique within the RPL 1092 Instance. 1094 5.1.3. DIO Suboptions 1096 This section describes the format of DIO suboptions and the five 1097 suboptions this document defines: Pad 1, Pad N, DAG Metric Container, 1098 DAG Destination Prefix, and DAG Configuration. 1100 5.1.3.1. DIO Suboption Format 1102 The Pad N, DAG Metric Container, DAG Destination Prefix, and DAG 1103 Configuration suboptions all follow this format: 1105 0 1 2 1106 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 1107 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 1108 | Subopt. Type | Suboption Length | Suboption Data 1109 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 1111 Figure 5: DIO Suboption Generic Format 1113 Suboption Type: 8-bit identifier of the type of suboption. 1115 Suboption Length: 16-bit unsigned integer, representing the length 1116 in octets of the suboption, not including the suboption Type 1117 and Length fields. 1119 Suboption Data: A variable length field that contains data specific 1120 to the option. 1122 The following subsections specify the DIO message suboptions which 1123 are currently defined for use in the DODAG Information Object. 1125 When processing a DIO message containing a suboption for which the 1126 Suboption Type value is not recognized by the receiver, the receiver 1127 MUST silently ignore the unrecognized option and continue to process 1128 the following suboption, correctly handling any remaining options in 1129 the message. 1131 DIO message suboptions may have alignment requirements. Following 1132 the convention in IPv6, options with alignment requirements are 1133 aligned in a packet such that multi-octet values within the Option 1134 Data field of each option fall on natural boundaries (i.e., fields of 1135 width n octets are placed at an integer multiple of n octets from the 1136 start of the header, for n = 1, 2, 4, or 8). 1138 5.1.3.2. Pad1 1140 The Pad1 suboption format is as follows: 1142 0 1143 0 1 2 3 4 5 6 7 1144 +-+-+-+-+-+-+-+-+ 1145 | Type = 0 | 1146 +-+-+-+-+-+-+-+-+ 1148 Figure 6: Pad 1 1150 NOTE! the format of the Pad1 option is a special case - it has 1151 neither Option Length nor Option Data fields. 1153 The Pad1 option is used to insert one or two octets of padding in the 1154 DIO message to enable suboptions alignment. If more than two octets 1155 of padding is required, the PadN option, described next, should be 1156 used rather than multiple Pad1 options. 1158 5.1.3.3. PadN 1160 The PadN suboption format is as follows: 1162 0 1 2 1163 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 1164 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 1165 | Type = 1 | Suboption Length | Suboption Data 1166 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 1168 Figure 7: Pad N 1170 The PadN suboption is used to insert three or more octets of padding 1171 in the DIO message to enable suboptions alignment. For N (N > 2) 1172 octets of padding, the Suboption Length field contains the value N-3, 1173 and the Option Data consists of N-3 zero-valued octets. PadN Option 1174 data MUST be ignored by the receiver. 1176 5.1.3.4. Metric Container 1178 The Metric Container suboption format is as follows: 1180 0 1 2 1181 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 1182 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 1183 | Type = 2 | Suboption Length | Metric Data 1184 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 1186 Figure 8: Metric Container 1188 The Metric Container is used to report metrics along the DODAG. The 1189 Metric Container may contain a number of discrete node, link, and 1190 aggregate path metrics as chosen by the implementer. The Suboption 1191 Length field contains the length in octets of the Metric Data. The 1192 order, content, and coding of the Metric Container data is as 1193 specified in [I-D.ietf-roll-routing-metrics]. 1195 The processing and propagation of the Metric Container is governed by 1196 implementation specific policy functions. 1198 5.1.3.5. Destination Prefix 1200 The Destination Prefix suboption format is as follows: 1202 0 1 2 3 1203 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 1204 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1205 | Type = 3 | Suboption Length |Resvd|Prf|Resvd| 1206 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1207 | Prefix Lifetime | 1208 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1209 | Prefix Length | | 1210 +-+-+-+-+-+-+-+-+ | 1211 | Destination Prefix (Variable Length) | 1212 . . 1213 . . 1214 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1216 Figure 9: DAG Destination Prefix 1218 The Destination Prefix suboption is used to indicate that 1219 connectivity to the specified destination prefix is available from 1220 the DODAG root, or from another node located upwards along the DODAG 1221 on the path to the DODAG root. This may be useful in cases where 1222 more than one LBR is operating within the LLN and offering 1223 connectivity to different administrative domains, e.g. a home network 1224 and a utility network. In such cases, upon observing the Destination 1225 Prefixes offered by a particular DODAG, a node MAY decide to join 1226 multiple DODAGs in support of a particular application. 1228 The Suboption Length is coded as the length of the suboption in 1229 octets, excluding the Type and Length fields. 1231 Prf is the Route Preference as in [RFC4191]. The reserved fields 1232 MUST be set to zero on transmission and MUST be ignored on receipt. 1234 The Prefix Lifetime is a 32-bit unsigned integer representing the 1235 length of time in seconds (relative to the time the packet is sent) 1236 that the Destination Prefix is valid for route determination. The 1237 lifetime is initially set by the node that owns the prefix and 1238 denotes the valid lifetime for that prefix (similar to 1239 AdvValidLifetime [RFC4861]). The value might be reduced by the 1240 originator and/or en-route nodes that will not provide connectivity 1241 for the whole valid lifetime. A value of all one bits (0xFFFFFFFF) 1242 represents infinity. A value of all zero bits (0x00000000) indicates 1243 a loss of reachability. 1245 The Prefix Length is an 8-bit unsigned integer that indicates the 1246 number of leading bits in the destination prefix. 1248 The Destination Prefix contains Prefix Length significant bits of the 1249 destination prefix. The remaining bits of the Destination Prefix, as 1250 required to complete the trailing octet, are set to 0. 1252 In the event that a DIO message may need to specify connectivity to 1253 more than one destination, the Destination Prefix suboption may be 1254 repeated. 1256 5.1.3.6. DODAG Configuration 1258 The DODAG Configuration suboption format is as follows: 1260 0 1 2 3 1261 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 1262 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1263 | Type = 4 | Length | DIOIntDoubl. | 1264 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1265 | DIOIntMin. | DIORedun. | MaxRankInc | MinHopRankInc | 1266 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1268 Figure 10: DODAG Configuration 1270 The DODAG Configuration suboption is used to distribute configuration 1271 information for DODAG Operation through the DODAG. The information 1272 communicated in this suboption is generally static and unchanging 1273 within the DODAG, therefore it is not necessary to include in every 1274 DIO. This suboption MAY be included occasionally by the DODAG Root, 1275 and MUST be included in response to a unicast request, e.g. a unicast 1276 DODAG Information Solicitation (DIS) message. 1278 The Length is coded as 5. 1280 DIOIntervalDoublings is an 8-bit unsigned integer, configured on the 1281 DODAG root and used to configure the trickle timer (see 1282 Section 5.3.5.1 for details on trickle timers) governing when DIO 1283 message should be sent within the DODAG. DIOIntervalDoublings is the 1284 number of times that the DIOIntervalMin is allowed to be doubled 1285 during the trickle timer operation. 1287 DIOIntervalMin is an 8-bit unsigned integer, configured on the DODAG 1288 root and used to configure the trickle timer governing when DIO 1289 message should be sent within the DODAG. The minimum configured 1290 interval for the DIO trickle timer in units of ms is 1291 2^DIOIntervalMin. For example, a DIOIntervalMin value of 16ms is 1292 expressed as 4. 1294 DIORedundancyConstant is an 8-bit unsigned integer used to configure 1295 suppression of DIO transmissions. DIORedundancyConstant is the 1296 minimum number of relevant incoming DIOs required to suppress a DIO 1297 transmission. If the value is 0xFF then the suppression mechanism is 1298 disabled. 1300 MaxRankInc, 8-bit unsigned integer, is the DAGMaxRankIncrease. This 1301 is the allowable increase in rank in support of local repair. If 1302 DAGMaxRankIncrease is 0 then this mechanism is disabled. 1304 MinHopRankInc, 8-bit unsigned integer, is the MinHopRankIncrease as 1305 described in Section 3.6.2.1. 1307 5.2. DODAG Information Solicitation (DIS) 1309 The DODAG Information Solicitation (DIS) message may be used to 1310 solicit a DODAG Information Object from a RPL node. Its use is 1311 analogous to that of a Router Solicitation; a node may use DIS to 1312 probe its neighborhood for nearby DODAGs. The DODAG Information 1313 Solicitation carries no additional message body. Section 5.3.5 1314 describes how nodes respond to a DIS. 1316 5.3. Upward Route Discovery and Maintenance 1318 Upward route discovery allows a node to join a DODAG by discovering 1319 neighbors that are members of the DODAG and identifying a set of 1320 parents. The exact policies for selecting neighbors and parents is 1321 implementation-dependent. This section specifies the set of rules 1322 those policies must follow for interoperability. 1324 5.3.1. RPL Instance 1326 A RPLInstanceID MUST be unique across an LLN. 1328 A node MAY belong to multiple RPL Instances. 1330 Within a given LLN, there may be multiple, logically independent RPL 1331 instances. This document describes how a single instance behaves. 1333 5.3.2. Neighbors and Parents within a DODAG Iteration 1335 RPL's upward route discovery algorithms and processing are in terms 1336 of three logical sets of link-local nodes. First, the candidate 1337 neighbor set is a subset of the nodes that can be reached via link- 1338 local multicast. The selection of this set is implementation- 1339 dependent and OF-dependent. Second, the parent set is a restricted 1340 subset of the candidate neighbor set. Finally, the preferred parent, 1341 a set of size one, is an element of the parent set that is the 1342 preferred next hop in upward routes. 1344 More precisely: 1346 1. The DODAG parent set MUST be a subset of the candidate neighbor 1347 set. 1349 2. A DODAG root MUST have a DODAG parent set of size zero. 1351 3. A node that is not a DODAG root MAY maintain a DODAG parent set 1352 of size greater than or equal to one. 1354 4. A node's preferred DODAG parent MUST be a member of its DODAG 1355 parent set. 1357 5. A node's rank MUST be greater than all elements of its DODAG 1358 parent set. 1360 6. When Neighbor Unreachability Detection (NUD), or an equivalent 1361 mechanism, determines that a neighbor is no longer reachable, a 1362 RPL node MUST NOT consider this node in the candidate neighbor 1363 set when calculating and advertising routes until it determines 1364 that it is again reachable. Routes through an unreachable 1365 neighbor MUST be eliminated from the routing table. 1367 These rules ensure that there is a consistent partial order on nodes 1368 within the DODAG. As long as node ranks do not change, following the 1369 above rules ensures that every node's route to a DODAG root is loop- 1370 free, as rank decreases on each hop to the root. The OF can guide 1371 candidate neighbor set and parent set selection, as discussed in 1372 [I-D.ietf-roll-routing-metrics]. 1374 5.3.3. Neighbors and Parents across DODAG Iterations 1376 The above rules govern a single DODAG iteration. The rules in this 1377 section define how RPL operates when there are multiple DODAG 1378 iterations: 1380 5.3.3.1. DODAG Iteration 1382 1. The tuple (RPLInstanceID, DODAGID, DODAGSequenceNumber) uniquely 1383 defines a DODAG Iteration. Every element of a node's DODAG 1384 parent set, as conveyed by the last heard DIO from each DODAG 1385 parent, MUST belong to the same DODAG iteration. Elements of a 1386 node's candidate neighbor set MAY belong to different DODAG 1387 Iterations. 1389 2. A node is a member of a DODAG iteration if every element of its 1390 DODAG parent set belongs to that DODAG iteration, or if that node 1391 is the root of the corresponding DODAG. 1393 3. A node MUST NOT send DIOs for DODAG iterations of which it is not 1394 a member. 1396 4. DODAG roots MAY increment the DODAGSequenceNumber that they 1397 advertise and thus move to a new DODAG iteration. When a DODAG 1398 root increments its DODAGSequenceNumber, it MUST follow the 1399 conventions of Serial Number Arithmetic as described in 1400 [RFC1982]. 1402 5. Within a given DODAG, a node that is a not a root MUST NOT 1403 advertise a DODAGSequenceNumber higher than the highest 1404 DODAGSequenceNumber it has heard. Higher is defined as the 1405 greater-than operator in [RFC1982]. 1407 6. Once a node has advertised a DODAG iteration by sending a DIO, it 1408 MUST NOT be member of a previous DODAG iteration of the same 1409 DODAG (i.e. with the same RPLInstanceID, the same DODAGID, and a 1410 lower DODAGSequenceNumber). Lower is defined as the less-than 1411 operator in [RFC1982]. 1413 Within a particular implementation, a DODAG root may increment the 1414 DODAGSequenceNumber periodically, at a rate that depends on the 1415 deployment. In other implementations, loop detection may be 1416 considered sufficient to solve routing issues, and the DODAG root may 1417 increment the DODAGSequenceNumber only upon administrative 1418 intervention. Another possibility is that nodes within the LLN have 1419 some means by which they can signal detected routing inconsistencies 1420 or suboptimalities to the DODAG root, in order to request an on- 1421 demand DODAGSequenceNumber increment (i.e. request a global repair of 1422 the DODAG). 1424 When the DODAG parent set becomes empty on a node that is not a root, 1425 (i.e. the last parent has been removed, causing the node to no longer 1426 be associated with that DODAG), then the DODAG information should not 1427 be suppressed until after the expiration of an implementation- 1428 specific local timer in order to observe if the DODAGSequenceNumber 1429 has been incremented, should any new parents appear for the DODAG. 1431 As the DODAGSequenceNumber is incremented, a new DODAG Iteration 1432 spreads outward from the DODAG root. Thus a parent that advertises 1433 the new DODAGSequenceNumber can not possibly belong to the sub-DODAG 1434 of a node that still advertises an older DODAGSequenceNumber. A node 1435 may safely add such a parent, without risk of forming a loop, without 1436 regard to its relative rank in the prior DODAG Iteration. This is 1437 equivalent to jumping to a different DODAG. 1439 As a node transitions to new DODAG Iterations as a consequence of 1440 following these rules, the node will be unable to advertise the 1441 previous DODAG Iteration (prior DODAGSequenceNumber) once it has 1442 committed to advertising the new DODAG Iteration. 1444 During transition to a new DODAG Iteration, a node may decide to 1445 forward packets via 'future parents' that belong to the same DODAG 1446 (same RPLInstanceID and DODAGID), but are observed to advertise a 1447 more recent (incremented) DODAGSequenceNumber. 1449 5.3.3.2. DODAG Roots 1451 1. A DODAG root that does not have connectivity to the set of 1452 addresses described as application-level goals, MUST NOT set the 1453 Grounded bit. 1455 2. A DODAG root MUST advertise a rank of ROOT_RANK. 1457 3. A node whose DODAG parent set is empty MAY become the DODAG root 1458 of a floating DODAG. It MAY also set its DAGPreference such that 1459 it is less preferred. 1461 An LLN node that is a goal for the Objective Function is the root of 1462 its own grounded DODAG, at rank ROOT_RANK. 1464 In a deployment that uses a backbone link to federate a number of LLN 1465 roots, it is possible to run RPL over that backbone and use one 1466 router as a "backbone root". The backbone root is the virtual root 1467 of the DODAG, and exposes a rank of BASE_RANK over the backbone. All 1468 the LLN roots that are parented to that backbone root, including the 1469 backbone root if it also serves as LLN root itself, expose a rank of 1470 ROOT_RANK to the LLN, and are part of the same DODAG, coordinating 1471 DODAGSequenceNumber and other DODAG root determined parameters with 1472 the virtual root over the backbone. 1474 5.3.3.3. DODAG Selection 1476 The DODAGPreference (Prf) provides an administrative mechanism to 1477 engineer the self-organization of the LLN, for example indicating the 1478 most preferred LBR. If a node has the option to join a more 1479 preferred DODAG while still meeting other optimization objectives, 1480 then the node will generally seek to join the more preferred DODAG as 1481 determined by the OF. All else being equal, it is left to the 1482 implementation to determine which DODAG is most preferred, possibly 1483 based on additional criteria beyond Prf and the OF. 1485 5.3.3.4. Rank and Movement within a DODAG Iteration 1486 1. A node MUST NOT advertise a rank less than or equal to any member 1487 of its parent set within the DODAG Iteration. 1489 2. A node MAY advertise a rank lower than its prior advertisement 1490 within the DODAG Iteration. 1492 3. Let L be the lowest rank within a DODAG iteration that a given 1493 node has advertised. Within the same DODAG Iteration, that node 1494 MUST NOT advertise an effective rank higher than L + 1495 DAGMaxRankIncrease. INFINITE_RANK is an exception to this rule: 1496 a node MAY advertise an INFINITE_RANK at any time. (This 1497 corresponds to a limited rank increase for the purpose of local 1498 repair within the DODAG Iteration.) 1500 4. A node MAY, at any time, choose to join a different DODAG within 1501 a RPL Instance. Such a join has no rank restrictions, unless 1502 that different DODAG is a DODAG Iteration of which that node has 1503 previously been a member, in which case the rule of the previous 1504 bullet (3) must be observed. Until a node transmits a DIO 1505 indicating its new DODAG membership, it MUST forward packets 1506 along the previous DODAG. 1508 5. A node MAY, at any time after hearing the next 1509 DODAGSequenceNumber Iteration advertised from suitable DODAG 1510 parents, choose to migrate to the next DODAG Iteration within the 1511 DODAG. 1513 Conceptually, an implementation is maintaining a DODAG parent set 1514 within the DODAG Iteration. Movement entails changes to the DODAG 1515 parent set. Moving up does not present the risk to create a loop but 1516 moving down might, so that operation is subject to additional 1517 constraints. 1519 When a node migrates to the next DODAG Iteration, the DODAG parent 1520 and sibling sets need to be rebuilt for the new iteration. An 1521 implementation could defer to migrate for some reasonable amount of 1522 time, to see if some other neighbors with potentially better metrics 1523 but higher rank announce themselves. Similarly, when a node jumps 1524 into a new DODAG it needs to construct new DODAG parent/sibling sets 1525 for this new DODAG. 1527 When a node moves to improve its position, it must conceptually 1528 abandon all DODAG parents and siblings with a rank larger than 1529 itself. As a consequence of the movement it may also add new 1530 siblings. Such a movement may occur at any time to decrease the 1531 rank, as per the calculation indicated by the OF. Maintenance of the 1532 parent and sibling sets occurs as the rank of candidate neighbors is 1533 observed as reported in their DIOs. 1535 If a node needs to move down a DODAG that it is attached to, causing 1536 the rank to increase, then it MAY poison its routes and delay before 1537 moving as described in Section 5.3.3.5. 1539 5.3.3.5. Poisoning a Broken Path 1541 1. A node MAY poison, in order to avoid being used as an ancestor by 1542 the nodes in its sub-DODAG, by advertising an effective rank of 1543 INFINITE_RANK and resetting the associated DIO trickle timer to 1544 cause this INFINITE_RANK to be announced promptly. 1546 2. The node MAY advertise an effective rank of INFINITE_RANK for an 1547 arbitrary number of DIO timer events, before announcing a new 1548 rank. 1550 3. As per Section 5.3.3.4, the node MUST advertise INFINITE_RANK 1551 within the DODAG iteration in which it participates, if its 1552 revision in rank would exceed the maximum rank increase. 1554 An implementation may choose to employ this poisoning mechanism when 1555 a node loses all of its current parents, i.e. the set of DODAG 1556 parents becomes depleted, and it can not jump to an alternate DODAG. 1557 An alternate mechanism is to form a floating DODAG. 1559 The motivation for delaying announcement of the revised route through 1560 multiple DIO events is to (i) increase tolerance to DIO loss, (ii) 1561 allow time for the poisoning action to propagate, and (iii) to 1562 develop an accurate assessment of its new rank. Such gains are 1563 obtained at the expense of potentially increasing the delay before 1564 portions of the network are able to re-establish upwards routes. 1565 Path redundancy in the DODAG reduces the significance of either 1566 effect, since children with alternate parents should be able to 1567 utilize those alternates and retain their rank while the detached 1568 parent re-establishes its rank. 1570 Although an implementation may advertise INFINITE_RANK for the 1571 purposes of poisoning, it is not expected to be equivalent to setting 1572 the rank to INFINITE_RANK, and an implementation would likely retain 1573 its rank value prior to the poisoning in some form, for purpose of 1574 maintaining its effective position within (L + DAGMaxRankIncrease). 1576 5.3.3.6. Detaching 1578 1. A node unable to stay connected to a DODAG within a given DODAG 1579 iteration MAY detach from this DODAG iteration. A node that 1580 detaches becomes root of its own floating DODAG and SHOULD 1581 immediately advertise this new situation in a DIO as an alternate 1582 to poisoning. 1584 5.3.3.7. Following a Parent 1586 1. If a node receives a DIO from one of its DODAG parents, 1587 indicating that the parent has left the DODAG, that node SHOULD 1588 stay in its current DODAG through an alternative DODAG parent, if 1589 possible. It MAY follow the leaving parent. 1591 A DODAG parent may have moved, migrated to the next DODAG Iteration, 1592 or jumped to a different DODAG. A node should give some preference 1593 to remaining in the current DODAG, if possible, but ought to follow 1594 the parent if there are no other options. 1596 5.3.4. DIO Message Communication 1598 When an DIO message is received, the receiving node must first 1599 determine whether or not the DIO message should be accepted for 1600 further processing, and subsequently present the DIO message for 1601 further processing if eligible. 1603 1. If the DIO message is malformed, then the DIO message is not 1604 eligible for further processing and is silently discarded. A RPL 1605 implementation MAY log the reception of a malformed DIO message. 1607 2. If the sender of the DIO message is a member of the candidate 1608 neighbor set, then the DIO is eligible for further processing. 1610 5.3.4.1. DIO Message Processing 1612 As DIO messages are received from candidate neighbors, the neighbors 1613 may be promoted to DODAG parents by following the rules of DODAG 1614 discovery as described in Section 5.3. When a node places a neighbor 1615 into the DODAG parent set, the node becomes attached to the DODAG 1616 through the new DODAG parent node. 1618 The most preferred parent should be used to restrict which other 1619 nodes may become DODAG parents. Some nodes in the DODAG parent set 1620 may be of a rank less than or equal to the most preferred DODAG 1621 parent. (This case may occur, for example, if an energy constrained 1622 device is at a lesser rank but should be avoided as per an 1623 optimization objective, resulting in a more preferred parent at a 1624 greater rank). 1626 5.3.5. DIO Transmission 1628 Each node maintains a timer, that governs when to multicast DIO 1629 messages. This timer is a trickle timer, as detailed in 1630 Section 5.3.5.1. The DIO Configuration Option includes the 1631 configuration of a RPL Instance's trickle timer. 1633 o When a node detects or causes an inconsistency, it MUST reset the 1634 trickle timer. 1636 o When a node migrates to a new DODAG Iteration it MUST reset the 1637 trickle timer to its minimum value 1639 o When a node detects an inconsistency when forwarding a packet, as 1640 detailed in Section 7.2, the node MUST reset the trickle timer. 1642 o When a node receives a multicast DIS message, it MUST reset the 1643 trickle timer to its minimum value. 1645 o When a node receives a unicast DIS message, it MUST unicast a DIO 1646 message in response, and the response MUST include the DODAG 1647 Configuration Object. This provides a means that an interrogating 1648 node may be guaranteed to receive the DODAG Configuration Object, 1649 which otherwise might not be included at the option of the sender. 1650 In this case the node SHOULD NOT reset the trickle timer. 1652 o If a node is not a member of a DODAG, it MUST suppress 1653 transmission of DIO messages. 1655 o When a node is initialized, it MAY be configured to remain silent 1656 and not multicast any DIO messages until it has encountered and 1657 joined a DODAG (perhaps initially probing for a nearby DODAG with 1658 an DIS message). Alternately, it MAY choose to root its own 1659 floating DODAG and begin multicasting DIO messages using a default 1660 trickle configuration. The second case may be advantageous if it 1661 is desired for independent nodes to begin aggregating into 1662 scattered floating DODAGs, in the absence of a grounded node, for 1663 example in support of LLN installation and commissioning. 1665 5.3.5.1. Trickle Timer for DIO Transmission 1667 RPL treats the construction of a DODAG as a consistency problem, and 1668 uses a trickle timer [Levis08] to control the rate of control 1669 broadcasts. 1671 For each DODAG that a node is part of (i.e. one DODAG per RPL 1672 Instance), the node must maintain a single trickle timer. The 1673 required state contains the following conceptual items: 1675 I: The current length of the communication interval 1677 T: A timer with a duration set to a random value in the range 1678 [I/2, I] 1680 C: Redundancy Counter 1682 I_min: The smallest communication interval in milliseconds. This 1683 value is learned from the DIO message as (2^DIOIntervalMin)ms. 1684 The default value is DEFAULT_DIO_INTERVAL_MIN. 1686 I_doublings: The number of times I_min should be doubled before 1687 maintaining a constant rate, i.e. I_max = I_min * 1688 2^I_doublings. This value is learned from the DIO message as 1689 DIOIntervalDoublings. The default value is 1690 DEFAULT_DIO_INTERVAL_DOUBLINGS. 1692 5.3.5.1.1. Resetting the Trickle Timer 1694 The trickle timer for a DODAG is reset by: 1696 1. Setting I_min and I_doublings to the values learned from the 1697 DODAG root via a received DIO message. 1699 2. Setting C to zero. 1701 3. If I is not equal to I_min: 1703 1. Setting I to I_min. 1705 2. Setting T to a random value as described above. 1707 3. Restarting the trickle timer to expire after a duration T 1709 When a node learns about a DODAG through a DIO message, and makes the 1710 decision to join this DODAG, it initializes the state of the trickle 1711 timer by resetting the trickle timer and listening. Each time it 1712 hears a redundant DIO message for this DODAG, it MAY increment C. The 1713 exact determination of what constitutes a redundant DIO message is 1714 left to an implementation; it could for example include DIOs that 1715 advertise the same rank. 1717 When the timer fires at time T, the node compares C to the redundancy 1718 constant, DIORedundancyConstant. If C is less than that value, or if 1719 the DIORedundancyConstant value is 0xFF, the node generates a new DIO 1720 message and multicasts it. When the communication interval I 1721 expires, the node doubles the interval I so long as it has previously 1722 doubled it fewer than I_doubling times, resets C, and chooses a new T 1723 value. 1725 5.3.5.1.2. Determination of Inconsistency 1727 The trickle timer is reset whenever an inconsistency is detected 1728 within the DODAG, for example: 1730 o The node joins a new DODAG 1732 o The node moves within a DODAG 1734 o The node receives a DIO message from a DODAG parent that updates 1735 the information learned from a prior DIO message for that DODAG 1736 Parent 1738 o A DODAG parent forwards a packet intended to move up, indicating 1739 an inconsistency and possible loop. 1741 o A metric communicated in the DIO message is determined to be 1742 inconsistent, as according to a implementation specific path 1743 metric selection engine. 1745 o The rank of a DODAG parent has changed. 1747 5.3.6. DODAG Selection 1749 The DODAG selection is implementation and algorithm dependent. Nodes 1750 SHOULD prefer to join DODAGs for RPLInstanceIDs advertising OCPs and 1751 destinations compatible with their implementation specific 1752 objectives. In order to limit erratic movements, and all metrics 1753 being equal, nodes SHOULD keep their previous selection. Also, nodes 1754 SHOULD provide a means to filter out a parent whose availability is 1755 detected as fluctuating, at least when more stable choices are 1756 available. 1758 When connection to a fixed network is not possible or preferable for 1759 security or other reasons, scattered DODAGs MAY aggregate as much as 1760 possible into larger DODAGs in order to allow connectivity within the 1761 LLN. 1763 A node SHOULD verify that bidirectional connectivity and adequate 1764 link quality is available with a candidate neighbor before it 1765 considers that candidate as a DODAG parent. 1767 5.4. Operation as a Leaf Node 1769 In some cases a RPL node may attach to a DODAG as a leaf node only. 1770 One example of such a case is when a node does not understand the RPL 1771 Instance's OF. A leaf node does not extend DODAG connectivity but 1772 still needs to advertise its presence using DIOs. A node operating 1773 as a leaf node must obey the following rules: 1775 1. It MUST NOT transmit DIOs containing the DAG Metric Container. 1777 2. Its DIOs must advertise a DAGRank of INFINITE_RANK. 1779 3. It MAY transmit unicast DAOs as described in Section 6.2. 1781 4. It MAY transmit multicast DAOs to the '1 hop' neighborhood as 1782 described in Section 6.2.9. 1784 5.5. Administrative Rank 1786 In some cases it might be beneficial to adjust the rank advertised by 1787 a node beyond that computed by the OF based on some implementation 1788 specific policy and properties of the node. For example, a node that 1789 has limited battery should be a leaf unless there is no other choice, 1790 and may then augment the rank computation specified by the OF in 1791 order to expose an exaggerated rank. 1793 5.6. Collision 1795 A race condition occurs if 2 nodes send DIO messages at the same time 1796 and then attempt to join each other. This might happen, for example, 1797 between nodes which act as DODAG root of their own DODAGs. In order 1798 to detect the situation, LLN Nodes time stamp the sending of DIO 1799 message. Any DIO message received within a short link-layer- 1800 dependent period introduces a risk. It left to the implementation to 1801 define the duration of the risk window. 1803 There is risk of a collision when a node receives and processes a DIO 1804 within the risk window. For example, it may occur that two nodes are 1805 associated with different DODAGs and near-simultaneously send DIO 1806 messages, which are received and processed by both, and possibly 1807 result in both nodes simultaneously deciding to attach to each other. 1808 As a remedy, in the face of a potential collision, as determined by 1809 receiving a DIO within the risk window, the DIO message is not 1810 processed. It is expected that subsequent DIOs would not cross. 1812 6. Downward Routes 1814 This section describes how RPL discovers and maintains downward 1815 routes. Messages containing the Destination Advertisement Object 1816 (DAO), used to construct downward routes, are described. The 1817 downward routes are necessary in support of P2MP flows, from the 1818 DODAG roots toward the leaves. It specifies non-storing and storing 1819 behavior of nodes with respect to DAO messaging and DAO routing table 1820 entries. Nodes, as according to their resources and the 1821 implementation, may selectively store routing table entries learned 1822 from DAO messages, or may instead propagate the DAO information 1823 upwards while adding source routing information. A further 1824 optimization is described whereby DAO messages may be used to 1825 populate routing table entries for the '1-hop' neighbors, which may 1826 be useful in some cases as a shortcut for P2P flows. 1828 6.1. Destination Advertisement Object (DAO) 1830 The Destination Advertisement Object (DAO) is used to propagate 1831 destination information upwards along the DODAG. 1833 0 1 2 3 1834 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 1835 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1836 | DAO Sequence | DAO Rank | 1837 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1838 | RPLInstanceID | Route Tag | Prefix Length | RRCount | 1839 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1840 | DAO Lifetime | 1841 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1842 | Destination Prefix (Variable Length) | 1843 . . 1844 . . 1845 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1846 | Reverse Route Stack (Variable Length) | 1847 . . 1848 . . 1849 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1850 | sub-option(s)... 1851 +-+-+-+-+-+-+-+-+ 1853 Figure 11: The Destination Advertisement Object (DAO) 1855 DAO Sequence: 16-bit unsigned integer. Incremented by the node that 1856 owns the prefix for each new DAO message for that prefix. 1858 DAO Rank: 16-bit unsigned integer indicating the DAO Rank associated 1859 with the advertised Destination Prefix. The DAO Rank is 1860 analogous to the Rank in the DIO message in that it may be used 1861 to convey a relative distance to the Destination Prefix as 1862 computed by the Objective Function in use over the DODAG. It 1863 serves as a mechanism by which an ancestor node may order 1864 alternate DAO paths. 1866 RPLInstanceID: 8-bit field indicating the topology instance 1867 associated with the DODAG, as learned from the DIO. 1869 Route Tag: 8-bit unsigned integer. The Route Tag may be used to 1870 give a priority to prefixes that should be stored. This may be 1871 useful in cases where intermediate nodes are capable of storing 1872 a limited amount of routing state. The further specification 1873 of this field and its use is under investigation. 1875 Prefix Length: 8-bit unsigned integer. Number of valid leading bits 1876 in the IPv6 Prefix. 1878 RRCount: 8-bit unsigned integer. This counter is used to count the 1879 number of entries in the Reverse Route Stack. A value of '0' 1880 indicates that no Reverse Route Stack is present. 1882 DAO Lifetime: 32-bit unsigned integer. The length of time in 1883 seconds (relative to the time the packet is sent) that the 1884 prefix is valid for route determination. A value of all one 1885 bits (0xFFFFFFFF) represents infinity. A value of all zero 1886 bits (0x00000000) indicates a loss of reachability. 1888 Destination Prefix: Variable-length field identifying an IPv6 1889 destination address, prefix, or multicast group. The Prefix 1890 Length field contains the number of valid leading bits in the 1891 prefix. The bits in the prefix after the prefix length (if 1892 any) are reserved and MUST be set to zero on transmission and 1893 MUST be ignored on receipt. 1895 Reverse Route Stack: Variable-length field containing a sequence of 1896 RRCount (possibly compressed) IPv6 addresses. A node that adds 1897 on to the Reverse Route Stack will append to the list and 1898 increment the RRCount. 1900 6.1.1. DAO Suboptions 1902 The DAO message may optionally include a number of suboptions. 1904 The DAO suboptions are in the same format as the DIO Suboptions 1905 described in Section 6.1.1. 1907 In particular, a DAO message may include a DAG Metric Container 1908 suboption as described in Section 5.1.3.4. This suboption may be 1909 present in implementations where the DAO Rank is insufficient to 1910 optimize a path to the DAO Destination Prefix. 1912 6.2. Downward Route Discovery and Maintenance 1914 6.2.1. Overview 1916 Destination Advertisement operation produces DAO messages that flow 1917 up the DODAG, provisioning downward routing state for destination 1918 prefixes available in the sub-DODAG of the DODAG root, and possibly 1919 other nodes. The routing state provisioned with this mechanism is in 1920 the form of soft-state routing table entries. DAO messages are able 1921 to record loose source routing information as by propagate up the 1922 DODAG. This mechanism is flexible to support the provisioning of 1923 paths which consist of fully specified source routes, piecewise 1924 source routes, or hop-by-hop routes as according to the 1925 implementation and the capabilities of the nodes. 1927 Destination Advertisement may or may not be enabled over a DODAG 1928 rooted at a DODAG root. This is an a priori configuration determined 1929 by the implementation/deployment and not generally changed during the 1930 operation of the RPL LLN. 1932 When Destination Advertisement is enabled: 1934 1. Some nodes in the LLN MAY store at least one routing table entry 1935 for a particular destination learned from a DAO. Such a node is 1936 termed a 'storing node', with respect to that particular 1937 destination. 1939 2. Some nodes are capable to store at least one routing table entry 1940 for every unique destination observed from all DAOs that pass 1941 through. Such a node is termed a 'fully storing node'. 1943 3. DODAG roots nodes SHOULD be fully-storing nodes. 1945 4. Other nodes in the DODAG are not required to store routing table 1946 entries for any particular destinations observed in DAOs. Nodes 1947 that do not store routing table entries from DAOs are termed 1948 'non-storing nodes', with respect to a particular destination. 1950 5. Non-storing nodes MUST participate in the construction of 1951 piecewise source routes as they propagate the DAO message, as 1952 described in Section 6.2.5. 1954 6. Storing nodes MUST store any source route information received 1955 from the DAO (RRStack) in the routing table entry entry. If a 1956 node is not capable to do this then it must act as a non-storing 1957 node with respect to that particular destination. 1959 7. Storing nodes MUST use piecewise source routes in order to 1960 forward data across a non-storing region of the LLN. The source 1961 routing mechanism is to be described in a companion 1962 specification. (If a node is not capable to do this, then that 1963 node MUST NOT operate as a storing node). 1965 6.2.2. Mode of Operation 1967 o DAO Operation may not be required for all use cases. 1969 o Some applications may only need support for collection/upward/MP2P 1970 flow with no acknowledgement/reciprocal traffic. 1972 o Some DODAGs may not support DAO Operation, which could mean that 1973 DAO Operation is wasteful overhead. 1975 o As a special case, multicast DAO operation may be used to populate 1976 'one-hop' neighborhood routing table entries, and is distinct from 1977 the unicast DAO operation used to establish downward routes along 1978 the DODAG. 1980 1. The 'A' flag in the DIO as conveyed from the DODAG root serves to 1981 enable/disable DAO operation over the entire DODAG. This flag 1982 should be administratively provisioned a priori at the DODAG root 1983 as a function of the implementation/deployment and not tend to 1984 change. 1986 2. When DAO Operation is disabled, a node SHOULD NOT emit DAOs. 1988 3. When DAO Operation is disabled, a node MAY ignore received DAOs. 1990 6.2.3. Destination Advertisement Parents 1992 o Nodes will select a subset of their DODAG Parents to whom DAOs 1993 will be sent 1995 * This subset is the set of 'DAO Parents' 1997 * Each DAO parent MUST be a DODAG Parent. (Not all DODAG parents 1998 need to be DAO parents). 2000 * Operation with more than DAO Parent requires consideration of 2001 such issues as DAO fan-out and path diversity, to be elaborated 2002 in a future version of this specification. 2004 o The selection of DAO parents is implementation specific and may be 2005 based on selecting the DODAG Parents that offer the best upwards 2006 cost (as opposed to downwards or mixed), as determined by the 2007 metrics in use and the Objective Function. 2009 o When DAO messages are unicast to the DAO Parent, the identity of 2010 the DAO Parent (DODAGID x DAGSequenceNumber) combined with the 2011 RPLInstanceID in the DAO message unambiguously associates the DAO 2012 message, and thus the particular destination prefix, with a DODAG 2013 Iteration. 2015 o When DAO messages are unicast to the DAO Parent, the DAO Rank may 2016 be updated as according to the implementation and Objective 2017 Function in use to reflect the relative (aggregated) cost of 2018 reaching the Destination Prefix through that DAO parent. As a 2019 further extension, a DAO Suboption for the Metric Container may be 2020 included. 2022 6.2.4. Operation of DAO Storing Nodes 2024 6.2.4.1. DAO Routing Table Entry 2026 A DAO Routing Table Entry conceptually contains the following 2027 elements: 2029 o Advertising Neighbor Information 2030 * IPv6 Addr 2031 * Interface ID 2032 o To which DAO Parents has this entry been reported 2033 o Retry Counter 2034 o Logical equivalent of DAO Content: 2035 * DAO Sequence 2036 * DAO Rank 2037 * DAO Lifetime 2038 * Route tag (used to prioritize which destination entries should 2039 be stored) 2040 * Destination Prefix (or Address or Mcast Group) 2041 * RR Stack* 2043 The DAO Routing Table Entry is logically associated with the 2044 following states: 2046 CONNECTED This entry is 'owned' by the node - it is manually 2047 configured and is considered as a 'self' entry for DAO 2048 Operation 2050 REACHABLE This entry has been reported from a neighbor of the node. 2051 This state includes the following substates: 2053 CONFIRMED This entry is active, newly validated, and 2054 usable 2056 PENDING This entry is active, awaiting validation, and 2057 usable. A Retry Counter is associated with 2058 this substate 2060 UNREACHABLE This entry is being cleaned up. This entry may be 2061 suppressed when the cleanup process is complete. 2063 When an attempt is to be made to report the DAO entry to DAO Parents, 2064 the DAO Entry record is logically marked to indicate that an attempt 2065 has not yet been made for each parent. As the unicast attempts are 2066 completed for each parent, this mark may be cleared. This mechanism 2067 may serve to limit DAO entry updates for each parent to a subset that 2068 needs to be reported. 2070 6.2.4.1.1. DAO Routing Table Entry Management 2072 +---------------------------------+ 2073 | | 2074 | REACHABLE | +-------------+ 2075 | | | | 2076 | +-----------+ | | CONNECTED | 2077 (*)----------->| |-------+ | | | 2078 | | Confirmed | | | +-------------+ 2079 | +-->| |---+ | | 2080 | | +-----------+ | | | 2081 | | | | | 2082 | | | | | 2083 | | | | | 2084 | | +-----------+ | | | +-------------+ 2085 | | | |<--+ +-------->| | 2086 | +---| Pending | | | UNREACHABLE | 2087 | | |---------------->| |--->(*) 2088 | +-----------+ | +-------------+ 2089 | | 2090 +---------------------------------+ 2092 DAO Routing Table Entry FSM 2094 6.2.4.1.1.1. Operation in the CONNECTED state 2096 1. CONNECTED DAO entries are to be provisioned outside of the 2097 context of RPL, e.g. through a management API. An implementation 2098 SHOULD provide a means to provision/manage CONNECTED DAO entries, 2099 including whether they are to be redistributed in RPL. 2101 6.2.4.1.1.2. Operation in the REACHABLE state 2103 1. When a REACHABLE(*) entry times out, i.e. the DAO Lifetime has 2104 elapsed, the entry MUST be placed into the UNREACHABLE state and 2105 no-DAO SHOULD be scheduled to send to the node's DAO Parents. 2107 2. When a no-DAO for a REACHABLE(*) entry is received with a newer 2108 DAO Sequence Number, the entry MUST be placed into the 2109 UNREACHABLE state and no-DAO SHOULD be scheduled to send to the 2110 node's DAO Parents. 2112 3. When a REACHABLE(*) entry is to be removed because NUD or 2113 equivalent has determined that the next-hop neighbor is no longer 2114 reachable, the entry MUST be placed into the UNREACHABLE state 2115 and no-DAO SHOULD be scheduled to send to the node's DAO Parents. 2117 4. When a REACHABLE(*) entry is to be removed because an associated 2118 Forwarding Error has been returned by the next-hop neighbor, the 2119 entry MUST be placed into the UNREACHABLE state and no-DAO SHOULD 2120 be scheduled to send to the node's DAO Parents. 2122 5. When a DAO (or no-DAO) for a REACHABLE(*) entry is received with 2123 an older or unchanged DAO Sequence Number, then the DAO (or no- 2124 DAO) SHOULD be ignored and the associated entry MUST NOT be 2125 updated with the stale information. 2127 6.2.4.1.1.2.1. REACHABLE(Confirmed) 2129 1. When a DAO for a previously unknown (or UNREACHABLE) destination 2130 is received and is to be stored, it MUST be entered into the 2131 routing table in the REACHABLE(Confirmed) state, and a DAO SHOULD 2132 be scheduled to send to the node's DAO Parents. Alternately the 2133 node may behave as a non-storing node with respect to this 2134 destination. 2136 2. When a DAO for a REACHABLE(Confirmed) entry is received with a 2137 newer DAO Sequence Number, the entry MUST be updated with the 2138 logical equivalent of the DAO contents and a DAO SHOULD be 2139 scheduled to send to the node's DAO Parents. 2141 3. When a DAO for a REACHABLE(Confirmed) entry is expected, e.g. 2142 because a DIO to request a DAO refresh is sent, then the DAO 2143 entry MUST be placed in the REACHABLE(Pending) state and the 2144 associated Retry Counter MUST be set to 0. 2146 6.2.4.1.1.2.2. REACHABLE(Pending) 2148 1. When a DAO for a REACHABLE(Pending) entry is received with a 2149 newer DAO Sequence Number, the entry MUST be updated with the 2150 logical equivalent of the DAO contents and the entry MUST be 2151 placed in the REACHABLE(Confirmed) state. 2153 2. When a DAO for a REACHABLE(Pending) entry is expected, e.g. 2154 because DAO has (again) been triggered with respect to that 2155 neighbor, then the associated Retry Counter MUST be incremented. 2157 3. When the associated Retry Counter for a REACHABLE(Pending) entry 2158 reaches a maximum threshold, the entry MUST be placed into the 2159 UNREACHABLE state and no-DAO SHOULD be scheduled to send to the 2160 node's DAO Parents. 2162 6.2.4.1.1.3. Operation in the UNREACHABLE state 2164 1. An implementation SHOULD bound the time that the entry is 2165 allocated in the UNREACHABLE state. Upon the equivalent expiry 2166 of the related timer (RemoveTimer), the entry SHOULD be 2167 suppressed. 2169 2. While the entry is in the UNREACHABLE state a node SHOULD make a 2170 reasonable attempt to report a no-DAO to each of the DAO parents. 2172 3. When the node has completed an attempt to report a no-DAO to each 2173 of the DAO parents, the entry SHOULD be suppressed. 2175 6.2.5. Operation of DAO Non-storing Nodes 2177 1. When a DAO is received from a child by a node who will not store 2178 a routing table entry for the DAO, the node MUST schedule to pass 2179 the DAO contents along to its DAO parents. Prior to passing the 2180 DAO along, the node MUST process the DAO as follows, in order 2181 that information necessary to construct a loose source route may 2182 be accumulated within the DAO payload as it moves up the DODAG: 2184 1. The most recent addition to the RRStack (the 'next waypoint') 2185 is investigated to determine if the node already has a route 2186 provisioned to the waypoint. If the node already has such a 2187 route, then it is not necessary to add additional information 2188 to the RRStack. The node SHOULD NOT modify the RRStack 2189 further. 2191 2. If the node does not have a route provisioned to the next 2192 waypoint, then the node MUST append the address of the child 2193 to the RRStack, and increment RRCount. 2195 6.2.6. Scheduling to Send DAO (or no-DAO) 2197 1. An implementation SHOULD arrange to rate-limit the sending of 2198 DAOs. 2200 2. When scheduling to send a DAO, an implementation SHOULD 2201 equivalently start a timer (DelayDAO) to delay sending the DAO. 2202 If the DelayDAO timer is already running then the DAO may be 2203 considered as already scheduled, and implementation SHOULD leave 2204 the timer running at its present duration. 2206 o When computing the delay before sending a DAO, in order to 2207 increase the effectiveness of aggregation, an implementation MAY 2208 allow time to receive DAOs from its sub-DODAG prior to emitting 2209 DAOs to its DAO Parents. 2211 * The scheduled delay in such cases may be, for example, such 2212 that DAO_LATENCY/DAGRank(self_rank) <= DelayDAO < DAO_LATENCY/ 2213 DAGRank(parent_rank), where DAGRank() is defined as in 2214 Section 3.6.2, such that nodes deeper in the DODAG may tend to 2215 report DAO messages first before their parent nodes will report 2216 DAO messages. Note that this suggestion is intended as an 2217 optimization to allow efficient aggregation -- it is not 2218 required for correct operation in the general case. 2220 6.2.7. Triggering DAO Message from the Sub-DODAG 2222 Triggering DAO messages from the Sub-DODAG occurs by using the 2223 following control fields with the rules described below: 2225 The DTSN field from the DIO is a sequence number that is part of the 2226 mechanism to trigger DAO messages. The motivation to use a sequence 2227 number is to provide some means of reliable signaling to the sub- 2228 DODAG-- whereas a control flag that is activated for a short time may 2229 be unobserved by the sub-DODAG if the triggering DIO messages are 2230 lost, the DTSN increment may be observed later even if some DIO 2231 messages have been lost since the sequence number increment. 2233 The 'T' flag provides a way to signal the refresh of DAO information 2234 over the entire DODAG iteration. Whereas a DTSN increment may only 2235 trigger a DAO refresh as far as the nearest storing node (because a 2236 storing node will not increment its own DTSN in response, as 2237 described in the rules below), the assertion of the 'T' flag in 2238 conjunction with an incremented DTSN will 'punch through' storing 2239 nodes to elicit a DAO refresh from the entire DODAG Iteration. 2241 The 'S' flag provides a way to signal to a sub-DODAG that there is at 2242 least one non-root node somewhere in the set of DODAG ancestors, 2243 where that non-root node is a storing node. This allows for an 2244 optimization-- when it is clear to a non-storing node that the root 2245 node can be the only storing ancestor, then that node does not 2246 necessarily need to trigger updates from its sub-DODAG when it 2247 modifies its DAO parent set. The motivation here is that the root 2248 node should be able to update its stored source routing information 2249 for the affected sub-DODAG based only on receiving DAO information 2250 concerning the link that changed. In the other case, when the 'S' 2251 flag is set, the non-storing node does not have a means to determine 2252 which DAO information may (or may not) need to be updated in the 2253 intermediate storing node so it must trigger DAO messages in order to 2254 update the intermediate storing node. Please note that some aspects 2255 of the proper use of the 'S' flag remain under investigation. 2257 Further examples of triggering DAO messages are contained in 2258 Appendix B. 2260 The control fields are used to trigger DAO messages as follows: 2262 1. The DODAG root MUST clear the 'S' flag when it emits DIO 2263 messages. 2265 2. Non-root nodes that store routing table entries learned from 2266 DAOs MUST set the 'S' flag when they emit DIO messages. 2268 3. A node that has any DAO Parent with the 'S' flag set MUST also 2269 set the 'S' flag when it emits DIO messages. 2271 4. A node that has all DAO Parents with cleared 'S' flags, and does 2272 not store routing table entries learned from DAOs, MUST clear 2273 the 'S' flag when it emits DIO messages. 2275 5. A DAO Trigger Sequence Number (DTSN) MUST be maintained by each 2276 node per RPL Instance. The DTSN, in conjunction with the 'T' 2277 flag from the DIO message, provides a means by which DAO 2278 messages may be reliably triggered in the event of topology 2279 change. 2281 6. The DTSN MUST be advertised by the node in the DIO message. 2283 7. A node keeps track of the DTSN that it has heard from the last 2284 DIO from each of its DAO Parents. Note that there is one DTSN 2285 maintained per DAO Parent- each DAO Parent may independently 2286 increment it at will. 2288 8. A node that is not a fully-storing node SHOULD increment its own 2289 DTSN when it adds a new parent, that parent having the 'S' flag 2290 set, to its DAO Parent set. It MAY defer advertising the 2291 increment as long as it has a DAO parent that already provides 2292 adequate connectivity. 2294 9. A node that is not a fully-storing node MUST increment its own 2295 DTSN when it receives a DIO from a DAO Parent that contains a 2296 newly incremented DTSN. (The newly incremented DTSN is detected 2297 by comparing the value received in the DIO with the value last 2298 recorded for that DAO parent). 2300 10. A fully-storing node MUST increment its own DTSN when it 2301 receives a DIO from a DAO Parent that contains a newly 2302 incremented DTSN and a set 'T' flag. 2304 11. When a storing or non-storing node joins a new DODAG iteration, 2305 it SHOULD increment its DTSN as if the 'T' flag has been set. 2307 12. DAO Transmission SHOULD be scheduled when a new parent is added 2308 to the DAO Parent set. 2310 13. A node that receives a newly incremented DTSN from a DAO Parent 2311 MUST schedule a DAO transmission. 2313 o When a node that is not fully-storing sees a DTSN increment, it 2314 will increment its own DTSN. This will cause the DTSN increment 2315 to extend down the DODAG to the first fully-storing node, which 2316 will send its DAOs back up, rebuilding source routes information 2317 along the way to the first node that incremented the DTSN, who 2318 then may report the new DAO information to its new parent. 2320 o When a fully-storing node sees a DTSN increment, it is caused to 2321 reissue its entire set of routing table entries learned from DAOs 2322 (or an aggregated subset thereof), but will not need to increment 2323 its own DTSN. The 'DTSN increment wave' stops when it encounters 2324 fully-storing nodes. 2326 o When a fully-storing node sees a DTSN increment AND the 'T' flag 2327 is set, it does increment its own DTSN as well. The 'T' flag 2328 'punches through' all nodes, causing all routing tables in the 2329 entire sub-DODAG to be refreshed. 2331 6.2.8. Sending DAO Messages to DAO Parents 2333 1. When storing nodes send DAO messages for stored entries the 2334 RRStack SHOULD be cleared in the DAO message. 2336 2. DAO Messages sent to DAO Parents MUST be unicast. 2338 * The IPv6 Source Address is the node sending the DAO message. 2340 * The IPv6 Destination Address is DAO parent. 2342 3. When the appointed time arrives (DelayDAO) for the transmission 2343 of DAO messages (with jitter as appropriate) for the requested 2344 entries, the implementation MAY aggregate the the entries into a 2345 reduced numbers of DAOs to be reported to each parent, and 2346 perform compression if possible. 2348 4. Note: it is NOT RECOMMENDED that a DAO Transmission (No-DAO) be 2349 scheduled when a DAO Parent is removed from the DAO Parent set. 2351 6.2.9. Multicast Destination Advertisement Messages 2353 A special case of DAO operation, distinct from unicast DAO operation, 2354 is multicast DAO operation which may be used to populate '1-hop' 2355 routing table entries. 2357 1. A node MAY multicast a DAO message to the link-local scope all- 2358 nodes multicast address FF02::1. 2360 2. A multicast DAO message MUST be used only to advertise 2361 information about self, i.e. prefixes directly connected to or 2362 owned by this node, such as a multicast group that the node is 2363 subscribed to or a global address owned by the node. 2365 3. A multicast DAO message MUST NOT be used to relay connectivity 2366 information learned (e.g. through unicast DAO) from another node. 2368 4. Information obtained from a multicast DAO MAY be installed in the 2369 routing table and MAY be propagated by a node in unicast DAOs. 2371 5. A node MUST NOT perform any other DAO related processing on a 2372 received multicast DAO, in particular a node MUST NOT perform the 2373 actions of a DAO parent upon receipt of a multicast DAO. 2375 o The multicast DAO may be used to enable direct P2P communication, 2376 without needing the RPL routing structure to relay the packets. 2378 o The multicast DAO does not presume any DODAG relationship between 2379 the emitter and the receiver. 2381 7. Packet Forwarding and Loop Avoidance/Detection 2382 7.1. Suggestions for Packet Forwarding 2384 When forwarding a packet to a destination, precedence is given to 2385 selection of a next-hop successor as follows: 2387 1. In the scope of this specification, it is preferred to select a 2388 successor from a DODAG iteration that matches the RPLInstanceID 2389 marked in the IPv6 header of the packet being forwarded. 2391 2. If a local administrative preference favors a route that has been 2392 learned from a different routing protocol than RPL, then use that 2393 successor. 2395 3. If there is an entry in the routing table matching the 2396 destination that has been learned from a multicast destination 2397 advertisement (e.g. the destination is a one-hop neighbor), then 2398 use that successor. 2400 4. If there is an entry in the routing table matching the 2401 destination that has been learned from a unicast destination 2402 advertisement (e.g. the destination is located down the sub- 2403 DODAG), then use that successor. 2405 5. If there is a DODAG iteration offering a route to a prefix 2406 matching the destination, then select one of those DODAG parents 2407 as a successor. 2409 6. If there is a DODAG parent offering a default route then select 2410 that DODAG parent as a successor. 2412 7. If there is a DODAG iteration offering a route to a prefix 2413 matching the destination, but all DODAG parents have been tried 2414 and are temporarily unavailable (as determined by the forwarding 2415 procedure), then select a DODAG sibling as a successor. 2417 8. Finally, if no DODAG siblings are available, the packet is 2418 dropped. ICMP Destination Unreachable may be invoked. An 2419 inconsistency is detected. 2421 TTL MUST be decremented when forwarding. If the packet is being 2422 forwarded via a sibling, then the TTL MAY be decremented more 2423 aggressively (by more than one) to limit the impact of possible 2424 loops. 2426 Note that the chosen successor MUST NOT be the neighbor that was the 2427 predecessor of the packet (split horizon), except in the case where 2428 it is intended for the packet to change from an up to an down flow, 2429 such as switching from DIO routes to DAO routes as the destination is 2430 neared. 2432 7.2. Loop Avoidance and Detection 2434 RPL loop avoidance mechanisms are kept simple and designed to 2435 minimize churn and states. Loops may form for a number of reasons, 2436 from control packet loss to sibling forwarding. RPL includes a 2437 reactive loop detection technique that protects from meltdown and 2438 triggers repair of broken paths. 2440 RPL loop detection uses information that is placed into the packet in 2441 the IPv6 flow label. The IPv6 flow label is defined in [RFC2460] and 2442 its operation is further specified in [RFC3697]. For the purpose of 2443 RPL operations, the flow label is constructed as follows: 2445 0 1 2 2446 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 2447 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2448 |O|S|R|F| SenderRank | RPLInstanceID | 2449 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2451 Figure 12: RPL Flow Label 2453 Down 'O' bit: 1-bit flag indicating whether the packet is expected 2454 to progress up or down. A router sets the 'O' bit when the 2455 packet is expect to progress down (using DAO routes), and 2456 resets it when forwarding towards the root of the DODAG 2457 iteration. A host MUST set the bit to 0. 2459 Sibling 'S' bit: 1-bit flag indicating whether the packet has been 2460 forwarded via a sibling at the present rank, and denotes a risk 2461 of a sibling loop. A host sets the bit to 0. 2463 Rank-Error 'R' bit: 1-bit flag indicating whether a rank error was 2464 detected. A rank error is detected when there is a mismatch in 2465 the relative ranks and the direction as indicated in the 'O' 2466 bit. A host MUST set the bit to 0. 2468 Forwarding-Error 'F' bit: 1-bit flag indicating that this node can 2469 not forward the packet further towards the destination. The 2470 'F' bit might be set by sibling that can not forward to a 2471 parent a packet with the Sibling 'S' bit set, or by a child 2472 node that does not have a route to destination for a packet 2473 with the down 'O' bit set. A host MUST set the bit to 0. 2475 SenderRank: 8-bit field set to zero by the source and to 2476 DAGRank(rank) by a router that forwards inside the RPL network. 2477 (Note that the case where DAGRank(rank) does not fit into 8 2478 bits is under investigation.) 2480 RPLInstanceID: 8-bit field indicating the DODAG instance along which 2481 the packet is sent. 2483 7.2.1. Source Node Operation 2485 A packet that is sourced at a node connected to a RPL network or 2486 destined to a node connected to a RPL network MUST be issued with the 2487 flow label zeroed out, but for the RPLInstanceID field. 2489 If the source is aware of the RPLInstanceID that is preferred for the 2490 flow, then it MUST set the RPLInstanceID field in the flow label 2491 accordingly, otherwise it MUST set it to the RPL_DEFAULT_INSTANCE. 2493 If a compression mechanism such as 6LoWPAN is applied to the packet, 2494 the flow label MUST NOT be compressed even if it is set to all 2495 zeroes. 2497 7.2.2. Router Operation 2499 7.2.2.1. Conformance to RFC 3697 2501 [RFC3697] mandates that the Flow Label value set by the source MUST 2502 be delivered unchanged to the destination node(s). 2504 In order to restore the flow label to its original value, an RPL 2505 router that delivers a packet to a destination connected to a RPL 2506 network or that routes a packet outside the RPL network MUST zero out 2507 all the fields but the RPLInstanceID field that must be delivered 2508 without a change. 2510 7.2.2.2. Instance Forwarding 2512 Instance IDs are used to avoid loops between DODAGs from different 2513 origins. DODAGs that constructed for antagonistic constraints might 2514 contain paths that, if mixed together, would yield loops. Those 2515 loops are avoided by forwarding a packet along the DODAG that is 2516 associated to a given instance. 2518 The RPLInstanceID is placed by the source in the flow label. This 2519 RPLInstanceID MUST match the RPL Instance onto which the packet is 2520 placed by any node, be it a host or router. 2522 When a router receives a packet that specifies a given RPLInstanceID 2523 and the node can forward the packet along the DODAG associated to 2524 that instance, then the router MUST do so and leave the RPLInstanceID 2525 flag unchanged. 2527 If any node can not forward a packet along the DODAG associated to 2528 the RPLInstanceID in the flow label, then the node SHOULD discard the 2529 packet. 2531 7.2.2.3. DAG Inconsistency Loop Detection 2533 The DODAG is inconsistent if the direction of a packet does not match 2534 the rank relationship. A receiver detects an inconsistency if it 2535 receives a packet with either: 2537 the 'O' bit set (to down) from a node of a higher rank. 2539 the 'O' bit reset (for up) from a node of a lesser rank. 2541 the 'S' bit set (to sibling) from a node of a different rank. 2543 When the DODAG root increments the DODAGSequenceNumber a temporary 2544 rank discontinuity may form between the next iteration and the prior 2545 iteration, in particular if nodes are adjusting their rank in the 2546 next iteration and deferring their migration into the next iteration. 2547 A router that is still a member of the prior iteration may choose to 2548 forward a packet to a (future) parent that is in the next iteration. 2549 In some cases this could cause the parent to detect an inconsistency 2550 because the rank-ordering in the prior iteration is not necessarily 2551 the same as in the next iteration and the packet may be judged to not 2552 be making forward progress. If the sending router is aware that the 2553 chosen successor has already joined the next iteration, then the 2554 sending router MUST update the SenderRank to INFINITE_RANK as it 2555 forwards the packets across the discontinuity into the next DODAG 2556 iteration in order to avoid a false detection of rank inconsistency. 2558 One inconsistency along the path is not considered as a critical 2559 error and the packet may continue. But a second detection along the 2560 path of a same packet should not occur and the packet is dropped. 2562 This process is controlled by the Rank-Error bit in the Flow Label. 2563 When an inconsistency, is detected on a packet, if the Rank-Error bit 2564 was not set then the Rank-Error bit is set. If it was set the packet 2565 is discarded and the trickle timer is reset. 2567 7.2.2.4. Sibling Loop Avoidance 2569 When a packet is forwarded along siblings, it cannot be checked for 2570 forward progress and may loop between siblings. Experimental 2571 evidence has shown that one sibling hop can be very useful but is 2572 generally sufficient to avoid loops. Based on that evidence, this 2573 specification enforces the simple rule that a packet may not make 2 2574 sibling hops in a row. 2576 When a host issues a packet or when a router forwards a packet to a 2577 non-sibling, the Sibling bit in the packet must be reset. When a 2578 router forwards to a sibling: if the Sibling bit was not set then the 2579 Sibling bit is set. If the Sibling bit was set then then the router 2580 SHOULD return the packet to the sibling that that passed it with the 2581 Forwarding-Error 'F' bit set. 2583 7.2.2.5. DAO Inconsistency Loop Detection and Recovery 2585 A DAO inconsistency happens when router that has an down DAO route 2586 via a child that is a remnant from an obsolete state that is not 2587 matched in the child. With DAO inconsistency loop recovery, a packet 2588 can be used to recursively explore and cleanup the obsolete DAO 2589 states along a sub-DODAG. 2591 In a general manner, a packet that goes down should never go up 2592 again. If DAO inconsistency loop recovery is applied, then the 2593 router SHOULD send the packet to the parent that passed it with the 2594 Forwarding-Error 'F' bit set. Otherwise the router MUST silently 2595 discard the packet. 2597 7.2.2.6. Forward Path Recovery 2599 Upon receiving a packet with a Forwarding-Error bit set, the node 2600 MUST remove the routing states that caused forwarding to that 2601 neighbor, clear the Forwarding-Error bit and attempt to send the 2602 packet again. The packet may its way to an alternate neighbor. If 2603 that alternate neighbor still has an inconsistent DAO state via this 2604 node, the process will recurse, this node will set the Forwarding- 2605 Error 'F' bit and the routing state in the alternate neighbor will be 2606 cleaned up as well. 2608 8. Multicast Operation 2610 This section describes further the multicast routing operations over 2611 an IPv6 RPL network, and specifically how unicast DAOs can be used to 2612 relay group registrations up. Wherever the following text mentions 2613 Multicast Listener Discovery (MLD), one can read MLDv2 ([RFC3810]) or 2614 v3. 2616 As is traditional, a listener uses a protocol such as MLD with a 2617 router to register to a multicast group. 2619 Along the path between the router and the DODAG root, MLD requests 2620 are mapped and transported as DAO messages within the RPL protocol; 2621 each hop coalesces the multiple requests for a same group as a single 2622 DAO message to the parent(s), in a fashion similar to proxy IGMP, but 2623 recursively between child router and parent up to the root. 2625 A router might select to pass a listener registration DAO message to 2626 its preferred parent only, in which case multicast packets coming 2627 back might be lost for all of its sub-DODAG if the transmission fails 2628 over that link. Alternatively the router might select to copy 2629 additional parents as it would do for DAO messages advertising 2630 unicast destinations, in which case there might be duplicates that 2631 the router will need to prune. 2633 As a result, multicast routing states are installed in each router on 2634 the way from the listeners to the root, enabling the root to copy a 2635 multicast packet to all its children routers that had issued a DAO 2636 message including a DAO for that multicast group, as well as all the 2637 attached nodes that registered over MLD. 2639 For unicast traffic, it is expected that the grounded root of an 2640 DODAG terminates RPL and MAY redistribute the RPL routes over the 2641 external infrastructure using whatever routing protocol is used 2642 there. For multicast traffic, the root MAY proxy MLD for all the 2643 nodes attached to the RPL routers (this would be needed if the 2644 multicast source is located in the external infrastructure). For 2645 such a source, the packet will be replicated as it flows down the 2646 DODAG based on the multicast routing table entries installed from the 2647 DAO message. 2649 For a source inside the DODAG, the packet is passed to the preferred 2650 parents, and if that fails then to the alternates in the DODAG. The 2651 packet is also copied to all the registered children, except for the 2652 one that passed the packet. Finally, if there is a listener in the 2653 external infrastructure then the DODAG root has to further propagate 2654 the packet into the external infrastructure. 2656 As a result, the DODAG Root acts as an automatic proxy Rendezvous 2657 Point for the RPL network, and as source towards the Internet for all 2658 multicast flows started in the RPL LLN. So regardless of whether the 2659 root is actually attached to the Internet, and regardless of whether 2660 the DODAG is grounded or floating, the root can serve inner multicast 2661 streams at all times. 2663 9. Maintenance of Routing Adjacency 2665 The selection of successors, along the default paths up along the 2666 DODAG, or along the paths learned from destination advertisements 2667 down along the DODAG, leads to the formation of routing adjacencies 2668 that require maintenance. 2670 In IGPs such as OSPF [RFC4915] or IS-IS [RFC5120], the maintenance of 2671 a routing adjacency involves the use of Keepalive mechanisms (Hellos) 2672 or other protocols such as BFD ([I-D.ietf-bfd-base]) and MANET 2673 Neighborhood Discovery Protocol (NHDP [I-D.ietf-manet-nhdp]). 2674 Unfortunately, such an approach is not desirable in constrained 2675 environments such as LLN and would lead to excessive control traffic 2676 in light of the data traffic with a negative impact on both link 2677 loads and nodes resources. Overhead to maintain the routing 2678 adjacency should be minimized. Furthermore, it is not always 2679 possible to rely on the link or transport layer to provide 2680 information of the associated link state. The network layer needs to 2681 fall back on its own mechanism. 2683 Thus RPL makes use of a different approach consisting of probing the 2684 neighbor using a Neighbor Solicitation message (see [RFC4861]). The 2685 reception of a Neighbor Advertisement (NA) message with the 2686 "Solicited Flag" set is used to verify the validity of the routing 2687 adjacency. Such mechanism MAY be used prior to sending a data 2688 packet. This allows for detecting whether or not the routing 2689 adjacency is still valid, and should it not be the case, select 2690 another feasible successor to forward the packet. 2692 10. Guidelines for Objective Functions 2694 An Objective Function (OF) allows for the selection of a DODAG to 2695 join, and a number of peers in that DODAG as parents. The OF is used 2696 to compute an ordered list of parents. The OF is also responsible to 2697 compute the rank of the device within the DODAG iteration. 2699 The Objective Function is indicated in the DIO message using an 2700 Objective Code Point (OCP), as specified in 2701 [I-D.ietf-roll-routing-metrics], and indicates the method that must 2702 be used to construct the DODAG (e.g. "minimize the path cost using 2703 the ETX metric and avoid 'Blue' links"). The Objective Code Points 2704 are specified in [I-D.ietf-roll-routing-metrics], 2705 [I-D.ietf-roll-of0], and related companion specifications. 2707 Most Objective Functions are expected to follow the same abstract 2708 behavior: 2710 o The parent selection is triggered each time an event indicates 2711 that a potential next hop information is updated. This might 2712 happen upon the reception of a DIO message, a timer elapse, or a 2713 trigger indicating that the state of a candidate neighbor has 2714 changed. 2716 o An OF scans all the interfaces on the device. Although there may 2717 typically be only one interface in most application scenarios, 2718 there might be multiple of them and an interface might be 2719 configured to be usable or not for RPL operation. An interface 2720 can also be configured with a preference or dynamically learned to 2721 be better than another by some heuristics that might be link-layer 2722 dependent and are out of scope. Finally an interface might or not 2723 match a required criterion for an Objective Function, for instance 2724 a degree of security. As a result some interfaces might be 2725 completely excluded from the computation, while others might be 2726 more or less preferred. 2728 o An OF scans all the candidate neighbors on the possible interfaces 2729 to check whether they can act as a router for a DODAG. There 2730 might be multiple of them and a candidate neighbor might need to 2731 pass some validation tests before it can be used. In particular, 2732 some link layers require experience on the activity with a router 2733 to enable the router as a next hop. 2735 o An OF computes self's rank by adding to the rank of the candidate 2736 a value representing the relative locations of self and the 2737 candidate in the DODAG iteration. 2739 * The increase in rank must be at least MinHopRankIncrease. 2740 (This prevents the creation of a path of sibling links 2741 connecting a child with its parent.) 2743 * To keep loop avoidance and metric optimization in alignment, 2744 the increase in rank should reflect any increase in the metric 2745 value. For example, with a purely additive metric such as ETX, 2746 the increase in rank can be made proportional to the increase 2747 in the metric. 2749 * Candidate neighbors that would cause self's rank to increase 2750 are not considered for parent selection 2752 o Candidate neighbors that advertise an OF incompatible with the set 2753 of OF specified by the policy functions are ignored. 2755 o As it scans all the candidate neighbors, the OF keeps the current 2756 best parent and compares its capabilities with the current 2757 candidate neighbor. The OF defines a number of tests that are 2758 critical to reach the objective. A test between the routers 2759 determines an order relation. 2761 * If the routers are roughly equal for that relation then the 2762 next test is attempted between the routers, 2764 * Else the best of the 2 becomes the current best parent and the 2765 scan continues with the next candidate neighbor 2767 * Some OFs may include a test to compare the ranks that would 2768 result if the node joined either router 2770 o When the scan is complete, the preferred parent is elected and 2771 self's rank is computed as the preferred parent rank plus the step 2772 in rank with that parent. 2774 o Other rounds of scans might be necessary to elect alternate 2775 parents and siblings. In the next rounds: 2777 * Candidate neighbors that are not in the same DODAG are ignored 2779 * Candidate neighbors that are of greater rank than self are 2780 ignored 2782 * Candidate neighbors of an equal rank to self (siblings) are 2783 ignored for parent selection 2785 * Candidate neighbors of a lesser rank than self (non-siblings) 2786 are preferred 2788 11. RPL Constants and Variables 2790 Following is a summary of RPL constants and variables. 2792 BASE_RANK This is the rank for a virtual root that might be used to 2793 coordinate multiple roots. BASE_RANK has a value of 0. 2795 ROOT_RANK This is the rank for a DODAG root. ROOT_RANK has a value 2796 of 1. 2798 INFINITE_RANK This is the constant maximum for the rank. 2799 INFINITE_RANK has a value of 0xFFFF. 2801 RPL_DEFAULT_INSTANCE This is the RPLInstanceID that is used by this 2802 protocol by a node without any overriding policy. 2803 RPL_DEFAULT_INSTANCE has a value of 0. 2805 DEFAULT_DIO_INTERVAL_MIN TBD (To be determined) 2807 DEFAULT_DIO_INTERVAL_DOUBLINGS TBD (To be determined) 2809 DEFAULT_DIO_REDUNDANCY_CONSTANT TBD (To be determined) 2811 DIO Timer One instance per DODAG that a node is a member of. Expiry 2812 triggers DIO message transmission. Trickle timer with variable 2813 interval in [0, DIOIntervalMin..2^DIOIntervalDoublings]. See 2814 Section 5.3.5.1 2816 DAG Sequence Number Increment Timer Up to one instance per DODAG 2817 that the node is acting as DODAG root of. May not be supported 2818 in all implementations. Expiry triggers revision of 2819 DODAGSequenceNumber, causing a new series of updated DIO 2820 message to be sent. Interval should be chosen appropriate to 2821 propagation time of DODAG and as appropriate to application 2822 requirements (e.g. response time vs. overhead). 2824 DelayDAO Timer Up to one instance per DAO parent (the subset of 2825 DODAG parents chosen to receive destination advertisements) per 2826 DODAG. Expiry triggers sending of DAO message to the DAO 2827 parent. See Section 6.2.6 2829 RemoveTimer Up to one instance per DAO entry per neighbor (i.e. 2830 those neighbors that have given DAO messages to this node as a 2831 DODAG parent) Expiry triggers a change in state for the DAO 2832 entry, setting up to do unreachable (No-DAO) advertisements or 2833 immediately deallocating the DAO entry if there are no DAO 2834 parents. See Section 6.2.4.1.1.3 2836 12. Manageability Considerations 2838 The aim of this section is to give consideration to the manageability 2839 of RPL, and how RPL will be operated in LLN beyond the use of a MIB 2840 module. The scope of this section is to consider the following 2841 aspects of manageability: fault management, configuration, accounting 2842 and performance. 2844 12.1. Control of Function and Policy 2846 12.1.1. Initialization Mode 2848 When a node is first powered up, it may either choose to stay silent 2849 and not send any multicast DIO message until it has joined a DODAG, 2850 or to immediately root a transient DODAG and start sending multicast 2851 DIO messages. A RPL implementation SHOULD allow configuring whether 2852 the node should stay silent or should start advertising DIO messages. 2854 Furthermore, the implementation SHOULD to allow configuring whether 2855 or not the node should start sending an DIS message as an initial 2856 probe for nearby DODAGs, or should simply wait until it received DIO 2857 messages from other nodes that are part of existing DODAGs. 2859 12.1.2. DIO Base option 2861 RPL specifies a number of protocol parameters. 2863 A RPL implementation SHOULD allow configuring the following routing 2864 protocol parameters, which are further described in Section 5.1.1: 2866 DAGPreference 2867 RPLInstanceID 2868 DAGObjectiveCodePoint 2869 DODAGID 2870 Destination Prefixes 2871 DIOIntervalDoublings 2872 DIOIntervalMin 2873 DIORedundancyConstant 2875 DAG Root behavior: In some cases, a node may not want to permanently 2876 act as a DODAG root if it cannot join a grounded DODAG. For 2877 example a battery-operated node may not want to act as a DODAG 2878 root for a long period of time. Thus a RPL implementation MAY 2879 support the ability to configure whether or not a node could 2880 act as a DODAG root for a configured period of time. 2882 DODAG Table Entry Suppression A RPL implementation SHOULD provide 2883 the ability to configure a timer after the expiration of which 2884 logical equivalent of the DODAG table that contains all the 2885 records about a DODAG is suppressed, to be invoked if the DODAG 2886 parent set becomes empty. 2888 12.1.3. Trickle Timers 2890 A RPL implementation makes use of trickle timer to govern the sending 2891 of DIO message. Such an algorithm is determined a by a set of 2892 configurable parameters that are then advertised by the DODAG root 2893 along the DODAG in DIO messages. 2895 For each DODAG, a RPL implementation MUST allow for the monitoring of 2896 the following parameters, further described in Section 5.3.5.1: 2898 I 2899 T 2900 C 2901 I_min 2902 I_doublings 2904 A RPL implementation SHOULD provide a command (for example via API, 2905 CLI, or SNMP MIB) whereby any procedure that detects an inconsistency 2906 may cause the trickle timer to reset. 2908 12.1.4. DAG Sequence Number Increment 2910 A RPL implementation may allow by configuration at the DODAG root to 2911 refresh the DODAG states by updating the DODAGSequenceNumber. A RPL 2912 implementation SHOULD allow configuring whether or not periodic or 2913 event triggered mechanism are used by the DODAG root to control 2914 DODAGSequenceNumber change. 2916 12.1.5. Destination Advertisement Timers 2918 The following set of parameters of the DAO messages SHOULD be 2919 configurable: 2921 o The DelayDAO timer 2923 o The Remove timer 2925 12.1.6. Policy Control 2927 DAG discovery enables nodes to implement different policies for 2928 selecting their DODAG parents. 2930 A RPL implementation SHOULD allow configuring the set of acceptable 2931 or preferred Objective Functions (OF) referenced by their Objective 2932 Codepoints (OCPs) for a node to join a DODAG, and what action should 2933 be taken if none of a node's candidate neighbors advertise one of the 2934 configured allowable Objective Functions. 2936 A node in an LLN may learn routing information from different routing 2937 protocols including RPL. It is in this case desirable to control via 2938 administrative preference which route should be favored. An 2939 implementation SHOULD allow for specifying an administrative 2940 preference for the routing protocol from which the route was learned. 2942 A RPL implementation SHOULD allow for the configuration of the "Route 2943 Tag" field of the DAO messages according to a set of rules defined by 2944 policy. 2946 12.1.7. Data Structures 2948 Some RPL implementation may limit the size of the candidate neighbor 2949 list in order to bound the memory usage, in which case some otherwise 2950 viable candidate neighbors may not be considered and simply dropped 2951 from the candidate neighbor list. 2953 A RPL implementation MAY provide an indicator on the size of the 2954 candidate neighbor list. 2956 12.2. Information and Data Models 2958 The information and data models necessary for the operation of RPL 2959 will be defined in a separate document specifying the RPL SNMP MIB. 2961 12.3. Liveness Detection and Monitoring 2963 The aim of this section is to describe the various RPL mechanisms 2964 specified to monitor the protocol. 2966 As specified in Section 3.1, an implementation is expected to 2967 maintain a set of data structures in support of DODAG discovery: 2969 o The candidate neighbors data structure 2971 o For each DODAG: 2973 * A set of DODAG parents 2975 12.3.1. Candidate Neighbor Data Structure 2977 A node in the candidate neighbor list is a node discovered by the 2978 some means and qualified to potentially become of neighbor or a 2979 sibling (with high enough local confidence). A RPL implementation 2980 SHOULD provide a way monitor the candidate neighbors list with some 2981 metric reflecting local confidence (the degree of stability of the 2982 neighbors) measured by some metrics. 2984 A RPL implementation MAY provide a counter reporting the number of 2985 times a candidate neighbor has been ignored, should the number of 2986 candidate neighbors exceeds the maximum authorized value. 2988 12.3.2. Directed Acyclic Graph (DAG) Table 2990 For each DAG, a RPL implementation is expected to keep track of the 2991 following DODAG table values: 2993 o DODAGID 2995 o DAGObjectiveCodePoint 2997 o A set of Destination Prefixes offered upwards along the DODAG 2999 o A set of DODAG Parents 3001 o timer to govern the sending of DIO messages for the DODAG 3003 o DODAGSequenceNumber 3005 The set of DODAG parents structure is itself a table with the 3006 following entries: 3008 o A reference to the neighboring device which is the DAG parent 3010 o A record of most recent information taken from the DAG Information 3011 Object last processed from the DODAG Parent 3013 o A flag reporting if the Parent is a DAO Parent as described in 3014 Section 6 3016 12.3.3. Routing Table 3018 For each route provisioned by RPL operation, a RPL implementation 3019 MUST keep track of the following: 3021 o Destination Prefix 3023 o Destination Prefix Length 3025 o Lifetime Timer 3027 o Next Hop 3029 o Next Hop Interface 3031 o Flag indicating that the route was provisioned from one of: 3033 * Unicast DAO message 3035 * DIO message 3037 * Multicast DAO message 3039 12.3.4. Other RPL Monitoring Parameters 3041 A RPL implementation SHOULD provide a counter reporting the number of 3042 a times the node has detected an inconsistency with respect to a 3043 DODAG parent, e.g. if the DODAGID has changed. 3045 A RPL implementation MAY log the reception of a malformed DIO message 3046 along with the neighbor identification if avialable. 3048 12.3.5. RPL Trickle Timers 3050 A RPL implementation operating on a DODAG root MUST allow for the 3051 configuration of the following trickle parameters: 3053 o The DIOIntervalMin expressed in ms 3055 o The DIOIntervalDoublings 3057 o The DIORedundancyConstant 3059 A RPL implementation MAY provide a counter reporting the number of 3060 times an inconsistency (and thus the trickle timer has been reset). 3062 12.4. Verifying Correct Operation 3064 This section has to be completed in further revision of this document 3065 to list potential Operations and Management (OAM) tools that could be 3066 used for verifying the correct operation of RPL. 3068 12.5. Requirements on Other Protocols and Functional Components 3070 RPL does not have any impact on the operation of existing protocols. 3072 12.6. Impact on Network Operation 3074 To be completed. 3076 13. Security Considerations 3078 Security Considerations for RPL are to be developed in accordance 3079 with recommendations laid out in, for example, 3080 [I-D.tsao-roll-security-framework]. 3082 14. IANA Considerations 3083 14.1. RPL Control Message 3085 The RPL Control Message is an ICMP information message type that is 3086 to be used carry DODAG Information Objects, DODAG Information 3087 Solicitations, and Destination Advertisement Objects in support of 3088 RPL operation. 3090 IANA has defined a ICMPv6 Type Number Registry. The suggested type 3091 value for the RPL Control Message is 155, to be confirmed by IANA. 3093 14.2. New Registry for RPL Control Codes 3095 IANA is requested to create a registry, RPL Control Codes, for the 3096 Code field of the ICMPv6 RPL Control Message. 3098 New codes may be allocated only by an IETF Consensus action. Each 3099 code should be tracked with the following qualities: 3101 o Code 3103 o Description 3105 o Defining RFC 3107 Three codes are currently defined: 3109 +------+----------------------------------+---------------+ 3110 | Code | Description | Reference | 3111 +------+----------------------------------+---------------+ 3112 | 0x01 | DODAG Information Solicitation | This document | 3113 | 0x02 | DODAG Information Object | This document | 3114 | 0x04 | Destination Advertisement Object | This document | 3115 +------+----------------------------------+---------------+ 3117 RPL Control Codes 3119 14.3. New Registry for the Control Field of the DIO Base 3121 IANA is requested to create a registry for the Control field of the 3122 DIO Base. 3124 New fields may be allocated only by an IETF Consensus action. Each 3125 field should be tracked with the following qualities: 3127 o Bit number (counting from bit 0 as the most significant bit) 3129 o Capability description 3130 o Defining RFC 3132 Four groups are currently defined: 3134 +-------+-----------------------------------------+---------------+ 3135 | Bit | Description | Reference | 3136 +-------+-----------------------------------------+---------------+ 3137 | 0 | Grounded DODAG (G) | This document | 3138 | 1 | Destination Advertisement Supported (A) | This document | 3139 | 2 | Destination Advertisement Trigger (T) | This document | 3140 | 3 | Destination Advertisements Stored (S) | This document | 3141 | 5,6,7 | DODAG Preference (Prf) | This document | 3142 +-------+-----------------------------------------+---------------+ 3144 DIO Base Flags 3146 14.4. DODAG Information Object (DIO) Suboption 3148 IANA is requested to create a registry for the DIO Base Suboptions 3150 +-------+------------------------------+---------------+ 3151 | Value | Meaning | Reference | 3152 +-------+------------------------------+---------------+ 3153 | 0 | Pad1 - DIO Padding | This document | 3154 | 1 | PadN - DIO suboption padding | This document | 3155 | 2 | DAG Metric Container | This Document | 3156 | 3 | Destination Prefix | This Document | 3157 | 4 | DAG Timer Configuration | This Document | 3158 +-------+------------------------------+---------------+ 3160 DODAG Information Option (DIO) Base Suboptions 3162 15. Acknowledgements 3164 The authors would like to acknowledge the review, feedback, and 3165 comments from Emmanuel Baccelli, Dominique Barthel, Yusuf Bashir, 3166 Phoebus Chen, Mathilde Durvy, Manhar Goindi, Mukul Goyal, Anders 3167 Jagd, Quentin Lampin, Jerry Martocci, Alexandru Petrescu, and Don 3168 Sturek. 3170 The authors would like to acknowledge the guidance and input provided 3171 by the ROLL Chairs, David Culler and JP Vasseur. 3173 The authors would like to acknowledge prior contributions of Robert 3174 Assimiti, Mischa Dohler, Julien Abeille, Ryuji Wakikawa, Teco Boot, 3175 Patrick Wetterwald, Bryan Mclaughlin, Carlos J. Bernardos, Thomas 3176 Watteyne, Zach Shelby, Caroline Bontoux, Marco Molteni, Billy Moon, 3177 and Arsalan Tavakoli, which have provided useful design 3178 considerations to RPL. 3180 16. Contributors 3182 RPL is the result of the contribution of the following members of the 3183 ROLL Design Team, including the editors, and additional contributors 3184 as listed below: 3186 JP Vasseur 3187 Cisco Systems, Inc 3188 11, Rue Camille Desmoulins 3189 Issy Les Moulineaux, 92782 3190 France 3192 Email: jpv@cisco.com 3194 Thomas Heide Clausen 3195 LIX, Ecole Polytechnique, France 3197 Phone: +33 6 6058 9349 3198 EMail: T.Clausen@computer.org 3199 URI: http://www.ThomasClausen.org/ 3201 Philip Levis 3202 Stanford University 3203 358 Gates Hall, Stanford University 3204 Stanford, CA 94305-9030 3205 USA 3207 Email: pal@cs.stanford.edu 3209 Richard Kelsey 3210 Ember Corporation 3211 Boston, MA 3212 USA 3214 Phone: +1 617 951 1225 3215 Email: kelsey@ember.com 3217 Jonathan W. Hui 3218 Arch Rock Corporation 3219 501 2nd St. Ste. 410 3220 San Francisco, CA 94107 3221 USA 3223 Email: jhui@archrock.com 3225 Kris Pister 3226 Dust Networks 3227 30695 Huntwood Ave. 3228 Hayward, 94544 3229 USA 3231 Email: kpister@dustnetworks.com 3233 Anders Brandt 3234 Zensys, Inc. 3235 Emdrupvej 26 3236 Copenhagen, DK-2100 3237 Denmark 3239 Email: abr@zen-sys.com 3241 Stephen Dawson-Haggerty 3242 UC Berkeley 3243 Soda Hall, UC Berkeley 3244 Berkeley, CA 94720 3245 USA 3247 Email: stevedh@cs.berkeley.edu 3249 17. References 3251 17.1. Normative References 3253 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 3254 Requirement Levels", BCP 14, RFC 2119, March 1997. 3256 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 3257 (IPv6) Specification", RFC 2460, December 1998. 3259 17.2. Informative References 3261 [I-D.ietf-bfd-base] 3262 Katz, D. and D. Ward, "Bidirectional Forwarding 3263 Detection", draft-ietf-bfd-base-11 (work in progress), 3264 January 2010. 3266 [I-D.ietf-manet-nhdp] 3267 Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 3268 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 3269 draft-ietf-manet-nhdp-11 (work in progress), October 2009. 3271 [I-D.ietf-roll-building-routing-reqs] 3272 Martocci, J., Riou, N., Mil, P., and W. Vermeylen, 3273 "Building Automation Routing Requirements in Low Power and 3274 Lossy Networks", draft-ietf-roll-building-routing-reqs-09 3275 (work in progress), January 2010. 3277 [I-D.ietf-roll-home-routing-reqs] 3278 Brandt, A. and J. Buron, "Home Automation Routing 3279 Requirements in Low Power and Lossy Networks", 3280 draft-ietf-roll-home-routing-reqs-11 (work in progress), 3281 January 2010. 3283 [I-D.ietf-roll-of0] 3284 Thubert, P., "RPL Objective Function 0", 3285 draft-ietf-roll-of0-01 (work in progress), February 2010. 3287 [I-D.ietf-roll-routing-metrics] 3288 Vasseur, J. and D. Networks, "Routing Metrics used for 3289 Path Calculation in Low Power and Lossy Networks", 3290 draft-ietf-roll-routing-metrics-04 (work in progress), 3291 December 2009. 3293 [I-D.ietf-roll-terminology] 3294 Vasseur, J., "Terminology in Low power And Lossy 3295 Networks", draft-ietf-roll-terminology-02 (work in 3296 progress), October 2009. 3298 [I-D.tsao-roll-security-framework] 3299 Tsao, T., Alexander, R., Dohler, M., Daza, V., and A. 3300 Lozano, "A Security Framework for Routing over Low Power 3301 and Lossy Networks", draft-tsao-roll-security-framework-01 3302 (work in progress), September 2009. 3304 [Levis08] Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S., 3305 Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and A. 3306 Woo, "The Emergence of a Networking Primitive in Wireless 3307 Sensor Networks", Communications of the ACM, v.51 n.7, 3308 July 2008, 3309 . 3311 [RFC1982] Elz, R. and R. Bush, "Serial Number Arithmetic", RFC 1982, 3312 August 1996. 3314 [RFC3697] Rajahalme, J., Conta, A., Carpenter, B., and S. Deering, 3315 "IPv6 Flow Label Specification", RFC 3697, March 2004. 3317 [RFC3810] Vida, R. and L. Costa, "Multicast Listener Discovery 3318 Version 2 (MLDv2) for IPv6", RFC 3810, June 2004. 3320 [RFC3819] Karn, P., Bormann, C., Fairhurst, G., Grossman, D., 3321 Ludwig, R., Mahdavi, J., Montenegro, G., Touch, J., and L. 3322 Wood, "Advice for Internet Subnetwork Designers", BCP 89, 3323 RFC 3819, July 2004. 3325 [RFC4101] Rescorla, E. and IAB, "Writing Protocol Models", RFC 4101, 3326 June 2005. 3328 [RFC4191] Draves, R. and D. Thaler, "Default Router Preferences and 3329 More-Specific Routes", RFC 4191, November 2005. 3331 [RFC4443] Conta, A., Deering, S., and M. Gupta, "Internet Control 3332 Message Protocol (ICMPv6) for the Internet Protocol 3333 Version 6 (IPv6) Specification", RFC 4443, March 2006. 3335 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 3336 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 3337 September 2007. 3339 [RFC4915] Psenak, P., Mirtorabi, S., Roy, A., Nguyen, L., and P. 3340 Pillay-Esnault, "Multi-Topology (MT) Routing in OSPF", 3341 RFC 4915, June 2007. 3343 [RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi 3344 Topology (MT) Routing in Intermediate System to 3345 Intermediate Systems (IS-ISs)", RFC 5120, February 2008. 3347 [RFC5548] Dohler, M., Watteyne, T., Winter, T., and D. Barthel, 3348 "Routing Requirements for Urban Low-Power and Lossy 3349 Networks", RFC 5548, May 2009. 3351 [RFC5673] Pister, K., Thubert, P., Dwars, S., and T. Phinney, 3352 "Industrial Routing Requirements in Low-Power and Lossy 3353 Networks", RFC 5673, October 2009. 3355 Appendix A. Requirements 3357 A.1. Protocol Properties Overview 3359 RPL demonstrates the following properties, consistent with the 3360 requirements specified by the application-specific requirements 3361 documents. 3363 A.1.1. IPv6 Architecture 3365 RPL is strictly compliant with layered IPv6 architecture. 3367 Further, RPL is designed with consideration to the practical support 3368 and implementation of IPv6 architecture on devices which may operate 3369 under severe resource constraints, including but not limited to 3370 memory, processing power, energy, and communication. The RPL design 3371 does not presume high quality reliable links, and operates over lossy 3372 links (usually low bandwidth with low packet delivery success rate). 3374 A.1.2. Typical LLN Traffic Patterns 3376 Multipoint-to-Point (MP2P) and Point-to-multipoint (P2MP) traffic 3377 flows from nodes within the LLN from and to egress points are very 3378 common in LLNs. Low power and lossy network Border Router (LBR) 3379 nodes may typically be at the root of such flows, although such flows 3380 are not exclusively rooted at LBRs as determined on an application- 3381 specific basis. In particular, several applications such as building 3382 or home automation do require P2P (Point-to-Point) communication. 3384 As required by the aforementioned routing requirements documents, RPL 3385 supports the installation of multiple paths. The use of multiple 3386 paths include sending duplicated traffic along diverse paths, as well 3387 as to support advanced features such as Class of Service (CoS) based 3388 routing, or simple load balancing among a set of paths (which could 3389 be useful for the LLN to spread traffic load and avoid fast energy 3390 depletion on some, e.g. battery powered, nodes). Conceptually, 3391 multiple instances of RPL can be used to send traffic along different 3392 topology instances, the construction of which is governed by 3393 different Objective Functions (OF). Details of RPL operation in 3394 support of multiple instances are beyond the scope of the present 3395 specification. 3397 A.1.3. Constraint Based Routing 3399 The RPL design supports constraint based routing, based on a set of 3400 routing metrics and constraints. The routing metrics and constraints 3401 for links and nodes with capabilities supported by RPL are specified 3402 in a companion document to this specification, 3404 [I-D.ietf-roll-routing-metrics]. RPL signals the metrics, 3405 constraints, and related Objective Functions (OFs) in use in a 3406 particular implementation by means of an Objective Code Point (OCP). 3407 Both the routing metrics, constraints, and the OF help determine the 3408 construction of the Directed Acyclic Graphs (DAG) using a distributed 3409 path computation algorithm. 3411 A.2. Deferred Requirements 3413 NOTE: RPL is still a work in progress. At this time there remain 3414 several unsatisfied application requirements, but these are to be 3415 addressed as RPL is further specified. 3417 Appendix B. Examples 3419 B.1. DAO Operation When Only the Root Node Stores DAO Information 3421 Consider the example of Figure 13. In this example only the root 3422 node, (LBR*), will store DAO information. This is not known, nor is 3423 it required to be known, to all nodes a priori. Rather, each node is 3424 able to observe from the state of the 'S' flag that no ancestor, with 3425 the exception of the root node, stores DAO information. 3427 (LBR*) 3428 / \ 3429 / \ 3430 / \ 3431 (11) (12) 3432 | | 3433 | | 3434 | | 3435 (21) (22) 3436 \ 3437 \ 3438 \ 3439 (31) 3440 / \ 3441 / \ 3442 / \ 3443 (41) (42) 3444 : : 3446 Figure 13: Only Root Node Stores DAOs 3448 In this example: 3450 o The 'S' flag is cleared in DIO messages emitted by (LBR*), because 3451 (LBR*) is the DODAG root. 3453 o The 'S' flag is cleared in all DIO messages emitted by all other 3454 nodes, because no other node stores DAO information. 3456 o (LBR*) has learned from DAO messages how to reach node (31) with a 3457 source route via {(11) (21)}. 3459 o All source routes to nodes in the sub-DODAG of node (31), 3460 including nodes (41), (42), and others will include the prefix 3461 {(11) (21) (31)} 3463 o Node (31) maintains a DTSN, (31).DTSN, that it will advertise in 3464 DIO messages. 3466 Suppose now that there is a topology change within the same DODAG 3467 iteration, causing node (31) to evict node (21) as a DAO parent and 3468 add node (22) as a DAO parent: 3470 1. Node (31) will schedule a DAO transmission because it has added a 3471 new node (22) to its DAO parent set. 3473 2. Node (31) need not increment (31).DTSN at this event, because in 3474 this example no DAO parents have the 'S' flag set. Specifically 3475 this indicates to Node (31) that there are no intermediate 3476 storing nodes that may need to be explicitly updated with DAO 3477 information from it's sub-DODAG. Hence nodes (41), (42), and by 3478 extension the sub-DODAG of node (31) will not subsequently 3479 observe an incremented (31).DTSN and the sub-DODAG will not emit 3480 DAOs. 3482 3. A new flow of DAOs for node (31) reaches the (LBR*), updating the 3483 source route information for node (31) to include the new path 3484 {(12) (22)}. 3486 4. (LBR*) may implicitly update all source routes that must transit 3487 node (31), i.e. the sub-DODAG of node (31), to use the updated 3488 source route prefix {(12) (22)} instead of {(11) (21)}. 3490 Thus the use of the 'S' flag in the case where only the root node 3491 stores DAO information has allowed an optimization whereby only a DAO 3492 update for the node that changed its DAO parent set, (31), needs to 3493 be sent to the DODAG root. 3495 B.2. DAO Operation When All Nodes Fully Store DAO Information 3497 Consider the example of Figure 14. In this example all nodes will 3498 fully store DAO information. 3500 (LBR*) 3501 / \ 3502 / \ 3503 / \ 3504 (11*) (12*) 3505 | | 3506 | | 3507 | | 3508 (21*) (22*) 3509 \ 3510 \ 3511 \ 3512 (31*) 3513 / \ 3514 / \ 3515 / \ 3516 (41*) (42*) 3517 : : 3519 Figure 14: All Nodes Store DAOs 3521 In this example: 3523 o The 'S' flag is cleared in DIO messages emitted by (LBR*), because 3524 (LBR*) is the DODAG root. 3526 o The 'S' flag is set in DIO messages emitted by all non-root nodes 3527 because each non-root node stores DAO information. 3529 o Source routing state is effectively not provisioned in this 3530 example, because each node has been able to store hop-by-hop 3531 routing state for each destination, possibly aggregated, as 3532 learned from DAOs. For example, node (11*) will have learned and 3533 stored information from a DAO to the effect that node (41*) is 3534 routable through a next hop of node (21*). Node (12*) on the 3535 other hand does not necessarily have a route provisioned to node 3536 (41*). 3538 Suppose now that there is a topology change within the same DODAG 3539 iteration, causing node (31*) to evict node (21*) as a DAO parent and 3540 add node (22*) as a DAO parent: 3542 1. Node (31*) will schedule a DAO transmission because it has added 3543 a new node (22*) to its DAO parent set. 3545 2. Node (31) need not increment (31).DTSN, because it is a fully 3546 storing node and does not need to trigger DAO information from 3547 its sub-DODAG. 3549 3. Node (31) gives a DAO Update to node (22*). Presuming that node 3550 (22*) has received the update, node (22*) will store the new 3551 entries for routes including the sub-DODAG of node (31*), 3552 including nodes (41*) and (42*). Node (22*) will schedule a DAO 3553 transmission for the new entries. 3555 4. Similarly, node (22*) updates node (12*) and node (12*) updates 3556 (LBR*). Hop-by-hop routing state for the sub-DODAG of node (31*) 3557 is now provisioned at nodes (12*) and (22*). 3559 Thus the addition to the DAO Parent set at the fully storing node 3560 (31*) does not elicit additional DAO-related traffic from its sub- 3561 DODAG. The intermediate nodes along the 'new' downward path are 3562 updated by DAO messages along the new path. 3564 Suppose next that the DODAG root triggers a refresh of DAO 3565 information over the same DODAG Iteration. (Note that the DODAG root 3566 might also trigger a DAO refresh but allow other topology changes at 3567 the same time by incrementing the DODAG Sequence Number to cause a 3568 move to the next DODAG Iteration).: 3570 1. (LBR*) will increment its DTSN and issue a DIO with the 'T' flag 3571 set. 3573 2. Nodes (11*) and (12*) will increment their own DTSNs in response 3574 to observing in the DIO from LBR a new DTSN and the 'T' flag 3575 being set. They will reset their trickle timers to cause the 3576 issue of new DIOs with the 'T' flag set. These nodes will also 3577 schedule a DAO transmission in response to observing a new DTSN 3578 from their DAO Parent, (LBR*). (This DAO transmission may be 3579 scheduled with a sufficient delay computed based on rank to allow 3580 a chance for the sub-DODAGs of the nodes to report DAO messages 3581 prior to the nodes reporting their own DAO information to (LBR*). 3582 This is implementation specific and may allow a chance for DAO 3583 aggregation.). 3585 3. Node (21*) receives a DIO from node (11*) and observes the new 3586 (11*).DTSN as well as the set 'T' flag. Node (21*) increments 3587 its own DTSN, resets the trickle timer, and schedules a DAO 3588 transmission. 3590 4. Similarly, as each node observes the incremented DTSN with the 3591 'T' flag set from each of its parents, each node will increment 3592 its own DTSN, reset the DIO trickle timer, and schedule a DAO 3593 transmission. 3595 Thus the entire DODAG iteration has been re-armed to send DAO 3596 messages based on the (LBR*)'s assertion of the 'T' flag. Note that 3597 normally a DTSN increment would cause no further action in a sub- 3598 DODAG beyond the first fully storing node that is encountered, but 3599 that in this case the 'T' flag effectively provides a means to 'punch 3600 through' all fully storing nodes. 3602 B.3. DAO Operation When Nodes Have Mixed Capabilities 3604 Consider the example of Figure 15. In this example some nodes are 3605 capable of storing DAO information and some are not. 3607 (LBR*) 3608 / \ 3609 / \ 3610 / \ 3611 (11) (12*) 3612 | | 3613 | | 3614 | | 3615 (21) (22) 3616 \ 3617 \ 3618 \ 3619 (31) 3620 / \ 3621 / \ 3622 / \ 3623 (41) (42*) 3624 : : 3626 Figure 15: Mixed Capability DAO Operation 3628 In this example: 3630 o The 'S' flag is cleared in DIO messages emitted by (LBR*), because 3631 (LBR*) is the DODAG root. 3633 o The 'S' flag is set in DIO messages emitted by (12*), because it 3634 is a storing node. 3636 o The 'S' flag will be set in DIO messages emitted by nodes that 3637 contain node (12*) (or more generally any non-root storing node) 3638 as a DAO parent/ancestor. This indicates that somewhere along the 3639 DAO path there is a non-root storing node that may need to have 3640 its state updated (by a DAO refresh) in certain conditions. 3642 Suppose that there is a topology change within the same DODAG 3643 iteration, causing node (31) to add node (22) as a DAO parent: 3645 1. Node (31) will schedule a DAO transmission because it has added a 3646 new node (22) to its DAO parent set. Node (31) will increment 3647 (31).DTSN because node (22) has set the 'S' flag in its DIO 3648 messages. Node (31) will reset its DIO trickle timer. 3650 2. Node (31)'s trickle timer will then expire and a DIO is issued 3651 and received by node's (41) and (42*). 3653 3. Node (41) is a non-storing node. It will increment (41).DTSN in 3654 response to observing the increment in (31).DTSN, and reset its 3655 trickle timer. This results finally in the reliable (thanks to 3656 the DTSN) triggering of a DAO update from node (41)'s sub-DODAG. 3658 4. As node (41) receives DAO updates from its sub-DODAG it updates 3659 the DAOs with source routing information as necessary and passes 3660 them on to node (31), along with its own (node (41)) DAO update. 3662 5. Meanwhile, node (42*) is a fully storing node. It observes the 3663 increment to (31).DTSN and schedules a DAO update. Node (42*) 3664 does not need to increment (42*).DTSN, since it is a fully 3665 storing node it does not need to solicit DAO updates from its 3666 sub-DODAG in this case. At the scheduled time Node (42*) 3667 reissues its DAO information to node (31). 3669 6. Node (31) receives the DAO messages from its sub-DODAG, adds 3670 source routing information as necessary, and issues DAO updates 3671 to node (22). 3673 7. Node (22) similarly receives DAO messages from node (31), updates 3674 source routing information as necessary, and issues DAO updates 3675 to node (12*). 3677 8. The intermediate storing node (12*) has now received from DAO 3678 messages the information necessary to provision routing state for 3679 node (31) and its sub-DODAG. As downwards traffic is routed 3680 through node (12*) it is able to consult source routing 3681 information that was learned from the DAO messages as needed to 3682 specify routes down the DAG across the non-storing nodes (22), 3683 (31), ... 3685 Appendix C. Outstanding Issues 3687 This section enumerates some outstanding issues that are to be 3688 addressed in future revisions of the RPL specification. 3690 C.1. Additional Support for P2P Routing 3692 In some situations the baseline mechanism to support arbitrary P2P 3693 traffic, by flowing upwards along the DODAG until a common ancestor 3694 is reached and then flowing down, may not be suitable for all 3695 application scenarios. A related scenario may occur when the down 3696 paths setup along the DODAG by the destination advertisement 3697 mechanism are not the most desirable downward paths for the specific 3698 application scenario (in part because the DODAG links may not be 3699 symmetric). It may be desired to support within RPL the discovery 3700 and installation of more direct routes 'across' the DAG. Such 3701 mechanisms need to be investigated. 3703 C.2. Destination Advertisement / DAO Fan-out 3705 When DAO messages are relayed to more than one DODAG parent, in some 3706 cases a situation may be created where a large number of DAO messages 3707 conveying information about the same destination flow upwards along 3708 the DAG. It is desirable to bound/limit the multiplication/fan-out 3709 of DAO messages in this manner. Some aspects of the Destination 3710 Advertisement mechanism remain under investigation, such as behavior 3711 in the face of links that may not be symmetric. 3713 In general, the utility of providing redundancy along downwards 3714 routes by sending DAO messages to more than one parent is under 3715 investigation. 3717 C.3. Source Routing 3719 In support of nodes that maintain minimal routing state, and to make 3720 use of the collection of piecewise source routes from the destination 3721 advertisement mechanism, there needs to be some investigation of a 3722 mechanism to specify, attach, and follow source routes for packets 3723 traversing the LLN. 3725 C.4. Address / Header Compression 3727 In order to minimize overhead within the LLN it is desirable to 3728 perform some sort of address and/or header compression, perhaps via 3729 labels, addresses aggregation, or some other means. This is still 3730 under investigation. 3732 C.5. Managing Multiple Instances 3734 A network may run multiple instances of RPL concurrently. Such a 3735 network will require methods for assigning and otherwise managing 3736 RPLInstanceIDs. This will likely be addressed in a separate 3737 document. 3739 Authors' Addresses 3741 Tim Winter (editor) 3743 Email: wintert@acm.org 3745 Pascal Thubert (editor) 3746 Cisco Systems 3747 Village d'Entreprises Green Side 3748 400, Avenue de Roumanille 3749 Batiment T3 3750 Biot - Sophia Antipolis 06410 3751 FRANCE 3753 Phone: +33 497 23 26 34 3754 Email: pthubert@cisco.com 3756 ROLL Design Team 3757 IETF ROLL WG 3759 Email: rpl-authors@external.cisco.com