idnits 2.17.1 draft-guo-roll-loop-free-rpl-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. 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 : ---------------------------------------------------------------------------- ** There are 2 instances of lines with control characters in the document. ** The abstract seems to contain references ([RFC6550], [RFC6551]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (June 26, 2013) is 3955 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) == Unused Reference: 'RFC4443' is defined on line 817, but no explicit reference was found in the text Summary: 2 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 ROLL J. Guo 3 Internet-Draft P. Orlik 4 Intended status: Standards Track Mitsubishi Electric Research Labs 5 Expires: December 28, 2013 June 26, 2013 7 Loop Free RPL 8 draft-guo-roll-loop-free-rpl-02 10 Abstract 12 The IETF has developed the IPv6 based standards for Low-power and 13 Lossy Networks (LLNs) to meet requirements of constrained 14 applications, such as field monitoring, inventory control and so on. 15 The IPv6 Routing Protocol for LLNs (RPL) was published as [RFC6550] 16 in March 2012. Based on routing metrics and constraints [RFC6551], 17 RPL builds Directed Acyclic Graph (DAG) topology to establish 18 bidirectional routes for LLNs for traffic types of multipoint-to- 19 point, point-to-multipoint, and point-to-point. RPL routes are 20 optimized for traffic to or from one or more roots that act as sinks. 21 As a result, a DAG is partitioned into one or more Destination 22 Oriented DAGs (DODAGs), one DODAG per sink. RPL is widely considered 23 as a feasible routing protocol for LLNs. However, DODAG loops and 24 lack of a loop free DODAG local repair mechanism are two open issues 25 to be addressed. This draft introduces an alternative rank and an 26 Objective Function to eliminate DODAG loops in RPL. Based on the 27 proposed rank and Objective Function, this draft introduces a loop 28 free RPL. 30 Status of this Memo 32 This Internet-Draft is submitted in full conformance with the 33 provisions of BCP 78 and BCP 79. 35 Internet-Drafts are working documents of the Internet Engineering 36 Task Force (IETF). Note that other groups may also distribute 37 working documents as Internet-Drafts. The list of current Internet- 38 Drafts is at http://datatracker.ietf.org/drafts/current/. 40 Internet-Drafts are draft documents valid for a maximum of six months 41 and may be updated, replaced, or obsoleted by other documents at any 42 time. It is inappropriate to use Internet-Drafts as reference 43 material or to cite them other than as "work in progress." 45 This Internet-Draft will expire on December 28, 2013. 47 Copyright Notice 49 Copyright (c) 2013 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents 54 (http://trustee.ietf.org/license-info) in effect on the date of 55 publication of this document. Please review these documents 56 carefully, as they describe your rights and restrictions with respect 57 to this document. Code Components extracted from this document must 58 include Simplified BSD License text as described in Section 4.e of 59 the Trust Legal Provisions and are provided without warranty as 60 described in the Simplified BSD License. 62 Table of Contents 64 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 4 65 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 5 66 3. Alternative Rank . . . . . . . . . . . . . . . . . . . . . . . . 6 67 3.1. Alternative Rank Definition . . . . . . . . . . . . . . . . 6 68 3.2. Rank Split Operation . . . . . . . . . . . . . . . . . . . 7 69 4. ICMPv6 RPL Control Message Extension . . . . . . . . . . . . . . 7 70 4.1. Format of the Modified DIO Base Object . . . . . . . . . . 7 71 4.2. DODAG Repair Request (DRQ) . . . . . . . . . . . . . . . . 8 72 4.2.1. Format of the DRQ Base Object . . . . . . . . . . . 8 73 4.2.2. Secure DRQ . . . . . . . . . . . . . . . . . . . . . 9 74 4.2.3. DRQ Options . . . . . . . . . . . . . . . . . . . . 9 75 4.3. DODAG Repair Reply (DRP) . . . . . . . . . . . . . . . . . 10 76 4.3.1. Format of the DRP Base Object . . . . . . . . . . . 10 77 4.3.2. Secure DRP . . . . . . . . . . . . . . . . . . . . 11 78 4.3.3. DRP Options . . . . . . . . . . . . . . . . . . . . 11 79 4.4. Format of the Path Option . . . . . . . . . . . . . . . . 11 80 5. DODAG Construction . . . . . . . . . . . . . . . . . . . . . . 12 81 6. DODAG Local Repair . . . . . . . . . . . . . . . . . . . . . . 13 82 6.1. DODAG Local Repair in Storing Mode . . . . . . . . . . . . 14 83 6.1.1. DRQ Message Processing . . . . . . . . . . . . . . 14 84 6.1.2. DRP Message Processing . . . . . . . . . . . . . . 15 85 6.2. DODAG Local Repair in Non-Storing Mode . . . . . . . . . . 16 86 6.2.1. DRQ Message Processing . . . . . . . . . . . . . . . 16 87 6.2.2. DRP Message Processing . . . . . . . . . . . . . . . 17 88 7. Security Considerations . . . . . . . . . . . . . . . . . . . . 18 89 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 18 90 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 18 91 9.1. Normative References . . . . . . . . . . . . . . . . . . . 18 92 9.2. Informative References . . . . . . . . . . . . . . . . . . 19 93 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 19 95 1. Introduction 97 Low-power and Lossy Networks (LLNs) are a class of networks in which 98 nodes and their communication links are constrained. LLN nodes 99 typically operate with constrains on processing power, physical size, 100 memory, power consumption, lifetime, and rate of activity. Their 101 communication links are characterized by high loss rate, low data 102 rate, instability, low transmission power, and short transmission 103 range. There can be from a few dozen up to thousands of nodes within 104 a LLN. Routing in LLNs is different from routing in mobile ad-hoc 105 networks. The IETF has developed an IPv6 Routing Protocol for LLNs 106 (RPL) published in [RFC6550]. RPL supports multipoint-to-point 107 traffic and point-to-multipoint traffic. The support for point-to- 108 point traffic is also available. 110 RPL builds Directed Acyclic Graph (DAG) topology, which is 111 partitioned into one or more Destination Oriented DAGs (DODAGs). 112 DODAG is basic logical structure in RPL. RPL nodes construct and 113 maintain DODAG through the DODAG Information Object (DIO) message 114 which is transmitted via link-local multicasting by using the Trickle 115 timer [RFC6206]. The sink in a DODAG is called the DODAG root. RPL 116 defines rules to transmit the DIO messages within a DODAG. The DODAG 117 root configures the DODAG parameters including RPLInstanceID, 118 DODAGVersionNumber, DODAGID, Rank, etc. and advertises the DODAG 119 parameters in the DIO messages. To join a DODAG, a node selects a set 120 of DODAG parents, on the routes towards the DODAG root, and a 121 preferred DODAG parent as the preferred next hop node for upward 122 traffic. Once a node joins a DODAG, it transmits DIO messages to 123 advertise the DODAG parameters. 125 The traffic inside a LLN flows along the edges of the DODAG, either 126 upward or downward. In RPL, upward routes, having the DODAG root as 127 destination, are provided by the DODAG construction mechanism using 128 DIO messages. Downward routes, from the DODAG root to any other 129 destination, are provided by these destinations transmitting the 130 Destination Advertisement Object (DAO) messages. 132 Three different modes of operation (MOP) for downward routes are 133 specified in [RFC6550]: 135 1) No downward routes supported by RPL. 136 2) Storing mode of operation in which each router stores downward 137 routing tables for its sub-DODAG. In Storing mode, the DAO message 138 is sent to DAO parents. A node unicasts the DAO messages to the 139 selected parent(s). Transmission of the DAO messages propagates 140 from the nodes towards the DODAG root, where each intermediate 141 router adds its downward routing stack to the DAO messages. In 142 Storing mode, downward traffic is sent by using the downward 143 routing tables. 144 3) Non-Storing mode of operation in which only the DODAG root 145 stores routes to all nodes in the network. In Non-Storing mode, 146 the DAO message is sent to the DODAG root. A node unicasts the DAO 147 messages to the DODAG root, which then calculates routes to all 148 destinations by piecing together the information collected from 149 the DAO messages. In Non-Storing mode, downward traffic is sent by 150 way of source routing. 152 An RPL node may act as a leaf node or as a router. RPL defines 153 operation rules for both leaf node and router. For example, a leaf 154 node does not extend DODAG connectivity. An RPL router needs to 155 implement Trickle timer algorithm [RFC6206]. An RPL router 156 implementation needs to support the MOP in use by the DODAG, that is, 157 support for upward routes only or support for upward routes and 158 downward routes in Storing mode or support for upward routes and 159 downward routes in Non-Storing mode. 161 RPL has been implemented and tested [draft-clausen-lln-rpl- 162 experiences-04]. A snapshot of the DODAG was made every ten seconds. 163 In 74.14% of the 4114 snapshots, at least one loop was observed. In 164 RPL, the cause of DODAG loops comes from rank increase. This draft 165 introduces an alternative rank and an Objective Function to eliminate 166 DODAG loops in RPL. In this draft, a node's rank never increases, 167 even if a parent becomes unreachable. As a result, the introduced 168 rank and Objective Function prevent DODAG loops from occurring. This 169 draft also introduces a method for repairing DODAG locally without 170 causing any DODAG loop. The DODAG local repair method applies to both 171 Storing and Non-Storing modes of operation in RPL. 173 2. Terminology 175 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 176 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 177 document are to be interpreted as described in [RFC2119]. 179 Additionally, this draft employs terminologies defined in [RFC6550], 180 and extends following terminologies: 182 DIO: DODAG Information Object in which the rank is represented by two 183 integers. 185 Up: Up refers to the direction from leaf node or router towards the 186 DODAG root. 188 Down: Down refers to the direction from the DODAG root towards leaf 189 node or router. 191 This draft introduces the following new terminologies: 193 DRQ: DODAG Repair Request 195 DRP: DODAG Repair Reply 197 Rank_DRQ: The rank of the node generating the DRQ message. 199 Rank_DRP: The rank of the node transmitting the DRP message. 201 DRQID: IPv6 address of the node generating DRQ message. 203 DRSN: Sequence number of the DRQ message of the node generating DRQ 204 message. 206 3. Alternative Rank 208 In RPL, the rank plays very important role in the DODAG construction 209 and maintenance. The rank of a node defines a position of the node 210 relative to other nodes with respect to the DODAG root. Each node 211 maintains its own rank. The DODAG root has the lowest rank. Nodes 212 maintain their ranks based on parent-child relationship such that a 213 child must have a rank strictly greater than ranks of all its DODAG 214 parents. The DODAG root has no parent. The acyclic structure of the 215 DODAG is guaranteed as long as the rank of any node is strictly 216 greater than ranks of its DODAG parents. It is safe for a node to 217 decrease its rank, as long as its rank remains greater than the ranks 218 of its DODAG parents. However, the rank increase can cause DODAG 219 loops. RPL allows rank increase, which is the source of DODAG loops 220 in RPL. A node's rank increase may also cause all nodes in sub-DODAG 221 to increase their ranks, which may lead to instability in the rank 222 values. 224 3.1. Alternative Rank Definition 226 DODAG loops in RPL can be avoided if nodes do not increase their 227 ranks. In order to meet this restriction, this draft defines the rank 228 of a node as a proper fraction: 230 Rank = m/n (1) 232 where m and n are integers such that 0 <= m < n. 234 The principle of this alternative rank definition comes from the fact 235 that there are an infinite number of proper fractions between any two 236 proper fractions. This guarantees that a node can decrease its rank 237 for any number of times and still keep its rank greater than ranks of 238 its DODAG parents. 240 In this draft, a node maintains its rank as two integers, that is, 241 numerator and denominator. The fractional value is used in rank 242 operations, such as rank comparison. 244 The ROOT_RANK is defined as 0/1 and maintained as 0 and 1. The DODAG 245 root sets its rank to ROOT_RANK. The INFINITE_RANK is defined as 1/1 246 and maintained as 1 and 1. The INFINITE_RANK can not be advertised in 247 the DIO messages by any node. 249 3.2. Rank Split Operation 251 For any two ranks R1 = m/n and R2 = p/q, the rank split operation is 252 defined as: 254 sp(R1, R2) = (m+p)/(n+q) (2) 256 It can be shown that if R1 < R2, then R1 < sp(R1,R2) < R2. That is, 257 the split operation splits two ranks R1 and R2 and generates a new 258 rank sp(R1,R2) that is in between R1 and R2. 260 4. ICMPv6 RPL Control Message Extension 262 This draft uses RPL control messages defined in [RFC6550] except the 263 DIO message. The rank is advertised in the RPL control message using 264 two integers, numerator and denominator, instead of the fractional 265 value. As a result, the format of DIO Base Object is modified. In 266 addition, to repair a DODAG locally, two new RPL control messages, 267 DODAG Repair Request (DRQ) message and DODAG Repair Reply (DRP) 268 message, are introduced. RPL control message format is defined in 269 Figure 6 and Figure 7 of [RFC6550]. The code field for the DRQ and 270 DRP messages needs to be assigned by IANA. The message base for DRQ 271 and DRP are defined as follows. 273 4.1. Format of the Modified DIO Base Object 275 0 1 2 3 276 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 277 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 278 | RPLInstanceID |Version Number | Rank_N | 279 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 280 | Rank_D |G|0| MOP | Prf | DTSN | 281 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 282 | Flags | Reserved | 283 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 284 | | 285 + + 286 | | 287 + DODAGID + 288 | | 289 + + 290 | | 291 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 292 | Option(s)... 293 +-+-+-+-+-+-+-+-+ 295 Figure 1: The Modified DIO Base Object 297 Rank_N: 16-bit unsigned integer indicating the numerator of 298 fractional rank of the node generating DIO message. 300 Rank_D: 16-bit unsigned integer indicating the denominator of 301 fractional rank of the node generating DIO message. 303 The rest of fields are same as being described in [RFC6550]. 305 4.2. DODAG Repair Request (DRQ) 307 The DRQ message is used by a node to repair a DODAG locally if 308 a parent becomes unreachable. A node may also use the DRQ 309 message to discover additional parents if it is necessary. 310 Functionality of DRQ message is different from DIS message 311 defined in [RFC6550]. A DRQ message can be relayed multiple 312 hops. 314 4.2.1. Format of the DRQ Base Object 316 0 1 2 3 317 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 318 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 319 | RPLInstanceID |Version Number | RankQ_N | 320 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 321 | RankQ_D | DRSN | HC | MH | 322 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 323 | | 324 + + 325 | | 326 + DODAGID + 327 | | 328 + + 329 | | 330 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 331 | | 332 + + 333 | | 334 + DRQID + 335 | | 336 + + 337 | | 338 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 339 | Option(s)... 340 +-+-+-+-+-+-+-+-+ 342 Figure 2: The DRQ Base Object 344 RPLInstanceID: 8-bit unsigned field as described in [RFC6550] to 345 indicate which RPL Instance the DODAG is a part. 347 Version Number: 8-bit unsigned integer as described in [RFC6550] to 348 indicate the DODAGVersionNumber. 350 RankQ_N: 16-bit unsigned integer indicating the numerator of 351 fractional rank of the node generating the DRQ message. 353 RankQ_D: 16-bit unsigned integer indicating the denominator of 354 fractional rank of the node generating the DRQ message. 356 DRSN: 8-bit field indicating sequence number of the DRQ message of 357 the node generating the DRQ message. 359 HC: 4-bit field to indicate the number of hops traveled by a DRQ 360 message. 362 MH: 4-bit field to indicate the maximum number of hops a DRQ message 363 can travel. If a DRQ message reaches the maximum number of 364 hops, it must be ignored. 366 DODAGID: 128-bit field as defined in [RFC6550]. A DODAGID is the 367 identifier of a DODAG root. The DODAGID is unique within the 368 scope of a RPL Instance in the LLN. The DODAGID must be a 369 routable IPv6 address belonging to the DODAG root. 371 DRQID: 128-bit IPv6 address of the node generating the DRQ message. 373 4.2.2. Secure DRQ 375 A Secure DRQ message follows the format in Figure 7 of [RFC6550], 376 where the base format is the DRQ message shown in Figure 2. 378 4.2.3. DRQ Options 380 The DRQ message may carry valid options. 382 This draft allows for the DRQ message to carry the following options: 384 0x00 Pad1 385 0x01 PadN 386 Path: This option field is present only if MOP is Non-Storing. The 387 Path field contains IPv6 addresses of nodes traversed by the DRQ 388 message along the path. 390 4.3. DODAG Repair Reply (DRP) 392 Upon receiving a DRQ message, a router with lower rank and non- 393 empty DODAG parent set may generate a DRP message in responding to 394 a received DRQ message. 396 4.3.1. Format of the DRP Base Object 398 0 1 2 3 399 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 400 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 401 | RPLInstanceID |Version Number | RankQ_N | 402 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 403 | RankQ_D | RankP_N | 404 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 405 | RankP_D | DRSN | Reserved | 406 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 407 | | 408 + + 409 | | 410 + DODAGID + 411 | | 412 + + 413 | | 414 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 415 | | 416 + + 417 | | 418 + DRPID + 419 | | 420 + + 421 | | 422 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 423 | Option(s)... 424 +-+-+-+-+-+-+-+-+ 426 Figure 3: The DRP Base Object 428 RPLInstanceID: 8-bit unsigned field as described in [RFC6550] to 429 indicate which RPL Instance the DODAG is a part. 431 Version Number: 8-bit unsigned integer as described in [RFC6550] to 432 indicate the DODAGVersionNumber. 434 RankQ_N: 16-bit unsigned integer indicating the numerator of 435 fractional rank of the node generating the DRQ message. 437 RankQ_D: 16-bit unsigned integer indicating the denominator of 438 fractional rank of the node generating the DRQ message. 440 RankP_N: 16-bit unsigned integer indicating the numerator of 441 fractional rank of the node sending the DRP message. 443 RankP_D: 16-bit unsigned integer indicating the denominator of 444 fractional rank of the node sending the DRP message. 446 DRSN: 8-bit field indicating the sequence number of DRQ message of 447 the node generating the DRQ message. 449 Reserved: 8 unassigned bits of the DRP Base are reserved. They must 450 be set to zero on transmission and must be ignored on 451 reception. 453 DODAGID: 128-bit field as defined in [RFC6550]. A DODAGID is the 454 identifier of a DODAG root. The DODAGID is unique within the 455 scope of a RPL Instance in the LLN. The DODAGID MUST be a 456 routable IPv6 address belonging to the DODAG root. 458 DRPID: 128-bit IPv6 address of the node that is destination of the 459 DRP message. 461 4.3.2. Secure DRP 463 A Secure DRP message follows the format in Figure 7 of [RFC6550], 464 where the base format is the DRP message shown in Figure 3. 466 4.3.3. DRP Options 468 The DRP message may carry valid options. 470 This draft allows for the DRP message to carry the following options: 472 0x00 Pad1 473 0x01 PadN 474 Path: This option is present only if MOP is Non-Storing and flag F 475 is set. The Path field contains IPv6 addresses of traversed nodes 476 by the DRQ message and the upward DRP message along the path. 478 4.4. RPL Control Message Options 479 The formats of option Pad1 and PadN are described in Figure 20 and 480 Figure 21 of [RFC6550], respectively. 482 The format of the Path option is as follows: 484 0 1 2 485 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 486 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 487 | Option Type | Option Length | Path Data 488 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - 490 Figure 4: Format of the Path Option 492 Option Type: 8-bit identifier of the type of option. The Option Type 493 value needs to be assigned by IANA. 495 Option Length: 8-bit unsigned integer, representing the length in 496 octets of the option Path Data field, not including the Option 497 Type and Option Length fields. 499 Path Data: A variable length field that contains a list of IPv6 500 addresses. 502 5. DODAG Construction 504 In RPL, a DODAG is uniquely identified by the (RPLInstanceID, 505 DODAGID) tuple and a DODAG Version is uniquely identified by the 506 (RPLInstanceID, DODAGID, DODAGVersionNumber) tuple. The 507 DODAGVersionNumber is monotonically incremented by the DODAG root. 509 To construct a new DODAG, the DODAG root configures DODAG parameters 510 and transmits a DIO message with new (RPLInstanceID, DODAGID) tuple. 511 To construct a new DODAG Version, the DODAG root transmits a DIO 512 message with an increased DODAGVersionNumber. The DIO message is 513 transmitted via link-local multicasting to all-RPL-nodes. Nodes 514 obtain the DODAG parameters configured by the DODAG root in received 515 DIO messages. 517 Upon receiving the DIO messages transmitted by the DODAG root or 518 neighboring nodes containing new (RPLInstanceID, DODAGID, 519 DODAGVersionNumber) tuple, the first hop neighboring nodes of the 520 DODAG root may decide to join new DODAG advertised in received DIO 521 messages. To do so, the first hop nodes add the DODAG root and 522 selected neighboring nodes into their DODAG parent set and store the 523 DODAG parameters advertised in received DIO messages. The first hop 524 nodes keep all DODAG parameters unchanged except the rank. The first 525 hop nodes use information carried in received DIO messages to 526 calculate their ranks. To calculate its rank, a first hop node find 527 the maximum rank, Rank_Max, of the ranks of its DODAG parents. A 528 first hop node set its rank such that its rank > Rank_max and its 529 rank <= sp(Rank_Max, INFINITE_RANK). Upon joining a new DODAG, the 530 first hop routers generate and transmit the DIO messages by following 531 rules specified in [RFC6550] to advertise the DODAG parameters. A 532 router must not transmit the DIO messages for DODAG Versions of which 533 it is not a member. A router that is not the DODAG root must not 534 change the DODAG parameters received in DIO messages except the rank 535 and DTSN fields. All other DODAG parameters, such as the DODAGID and 536 DODAGVersionNumber, must be propagated unchanged down the DODAG as 537 nodes join new DODAG or new DODAG Version. 539 Upon receiving the DIO messages transmitted by the first hop 540 neighboring routers, the second hop neighboring nodes of the DODAG 541 root that want to join new DODAG or new DODAG Version perform same 542 procedure as the first hop neighboring nodes do. The second hop 543 routers then generate and transmit the DIO messages same as the first 544 hop router do. 546 This DIO message propagation process continues until all nodes 547 receive the DIO messages, select the DODAG parents and store their 548 DODAG parameters, that is, the DODAG is completely constructed. 550 Among its DODAG parents, a node selects one preferred DODAG parent to 551 be used as the preferred next hop node along upward routes to the 552 DODAG root. A node also selects some of its DODAG parents as its DAO 553 parents and schedules the DAO transmission. 555 6. DOADG Local Repair 557 When a DODAG parent becomes unreachable, a node may switch to another 558 DODAG parent for upward traffic. DODAG may be locally repaired by the 559 node transmitting a DRQ message. The DRQ message is transmitted by 560 the DRQ message generator via link-local multicasting to all-RPL- 561 nodes. 563 Upon receiving a DRQ message, a link-local neighboring router which 564 is not the DODAG root discards the DRQ message if it does not have 565 any DODAG parent. If the link-local neighboring router is the DODAG 566 root, it accepts the DRQ message and generates a DRP message. If the 567 link-local neighboring router is not the DODAG root and has a non- 568 empty DODAG parent set and its rank is lower than Rank_DRQ (= 569 RankQ_N/RankQ_D), it accepts the DRQ message and generates a DRP 570 message. If the link-local neighboring router is not the DODAG root 571 and has a non-empty DODAG parent set and its rank is greater than or 572 equal to Rank_DRQ, it forwards the DRQ message to its preferred DODAG 573 parent. This forwarding process continues until the DRQ message is 574 discarded if HC of this DRQ message reaches MH or by a router that 575 has an empty DODAG parent set. Otherwise, the DRQ message reaches a 576 router which is either the DODAG root or a router that has a non- 577 empty DODAG parent set and a rank lower than Rank_DRQ, a DRP message 578 is then generated. 580 The DRP message is unicasted. In Storing mode, the DRP message 581 generator transmits the DRP message to the DRQ message generator by 582 using a downward routing table. In Non-Storing mode, the DRP message 583 is transmitted to the DRQ message generator by using Path option 584 field. 586 6.1. DODAG Local Repair in Storing Mode 588 In Storing mode, if a DODAG parent becomes unreachable, a node 589 removes that DODAG parent from its DODAG parent set. 591 If the updated DODAG parent set becomes empty, the node shall 592 transmit a DRQ message to discover new DODAG parents. 594 If the updated DODAG parent set is not empty, the node checks if the 595 removed DODAG parent is its preferred DODAG parent. If yes, the node 596 shall select a new preferred DODAG parent. Whether or not the removed 597 DODAG parent is the preferred DODAG parent, the node may transmit a 598 DRQ message to discover additional parents. The node may also 599 schedule a No-Path DAO message transmission if the removed DODAG 600 parent is its DAO parent. 602 To transmit a DRQ message in Storing mode, the node generates a DRQ 603 message. It sets RPLInstanceID, DODAGVersionNumber and DODAGID by 604 using the maintained DODAG parameters. It sets RankQ_N and RankQ_D to 605 the numerator and denominator of its fractional rank, respectively. 606 The node increases its DRSN by 1 and sets HC = 0 and MH to an 607 appropriate value. There is no Path option field in Storing mode. 609 6.1.1. DRQ Message Processing 611 When a router receives a DRQ message, it discards the DRQ message if 612 its DODAG parent set is empty. Otherwise, the router performs the 613 following filtering process and discards the DRQ message if any of 614 following conditions is true: 616 i) RPLInstanceID or DODAGVersionNumber or DODAGID in the DRQ 617 message is not equal to the respective value maintained by the 618 router. 619 ii) The DRQ message was received already by comparing DRQID and 620 DRSN. 621 iii) HC is equal to MH. 622 iv) The DRQ message is transmitted by router's DODAG parent. 624 v) The DRQ message is generated by router itself or by its DODAG 625 parent. 627 If the DRQ message passes filtering process, the receiving router 628 processes the DRQ message further. 630 If the receiving router is the DODAG root, it accepts the DRQ message 631 and generates a DRP message. To generate a DRP message, the DODAG 632 root copies RPLInstanceID, DODAGVersionNumber, DRSN, and DODAGID from 633 the DRQ message. It sets DRPID to DRQID, RankQ_N and RankQ_D to the 634 RankQ_N and RankQ_D in DRQ message, respectively. It sets RankP_N and 635 RankP_D to the numerator and denominator of its fractional rank, 636 respectively. The DODAG root forwards the DRP message to the node 637 from which it received the DRQ message. 639 If the receiving router is not the DODAG root and its rank is lower 640 than Rank_DRQ, the router accepts the DRQ message and generates a DRP 641 message as the root does. The router forwards the DRP message to the 642 node from which it received the DRQ message. 644 If the receiving router is not the DODAG root and its rank is greater 645 than or equal to Rank_DRQ, it adds a route entry to node DRQID into 646 its downward routing table, increases value of HC field by 1 and 647 forwards the DRQ message to its preferred DODAG parent. 649 6.1.2. DRP Message Processing 651 When a node receives a DRP message, it first performs filtering 652 process and discards the DRP message if any of following conditions 653 is true: 655 i) RPLInstanceID or DODAGVersionNumber or DODAGID in the DRP 656 message is not equal to the respective value maintained by the 657 receiving node. 658 ii) The DRP message was received already by comparing DRPID and 659 DRSN. 660 iii) The receiving node is leaf node and is not the DRQ message 661 generator. 663 If DRP message passes filtering process, the receiving node processes 664 the DRP message further. 666 If the receiving node is the DRQ message generator and the DRP 667 message sender is not in its DODAG parent set, it may add the DRP 668 message sender into its DODAG parent set and select a new preferred 669 DODAG parent. The receiving node may schedule a DAO message 670 transmission if the DRP message sender is added into its DAO parent 671 set. 673 If the receiving node is not the DRQ message generator, it must be a 674 router. 676 If the receiving router has no route entry to node DRPID in its 677 downward routing table, it discards the DRP message. 679 If the receiving router has a downward route entry to node DRPID and 680 its rank is greater than or equal to Rank_DRQ (= RankQ_N/RankQ_D), it 681 decreases its rank to sp(Rank_DRQ, Rank_DRP), where Rank_DRP = 682 RankP_N/RankP_D. The receiving router updates its DODAG parent set 683 caused by its rank decrease, that is, removing DODAG parents whose 684 ranks are greater than or equal to sp(Rank_DRQ, Rank_DRP). If its 685 preferred DODAG parent is removed, it selects a new preferred DODAG 686 parent. The receiving router then updates the RankP_N and RankP_D 687 fields of the DRP message to the numerator and denominator of its 688 fractional rank, respectively, and forwards the DRP message to next 689 hop node on the downward route. It may schedule a No-Path DAO message 690 transmission if any of its DAO parents is removed due to its rank 691 decrease. 693 If the receiving router has a downward route entry to node DRPID and 694 its rank is lower than Rank_DRQ, it updates the RankP_N and RankP_D 695 fields of DRP message to the numerator and denominator of its 696 fractional rank, respectively, and forwards the DRP message to next 697 hop node on the downward route. Noticed that the rank of receiving 698 router is less than Rank_DRQ if the receiving router is on multiple 699 DODAG repair downward routes. When the receiving router receives a 700 DRP message, it may decrease its rank. Therefore, subsequent DRP 701 messages may carry a Rank_DRQ greater than or equal to the rank of 702 receiving router. If the receiving router is only on a single DODAG 703 repair downward route, its rank must be greater than or equal to 704 Rank_DRQ based on the DRQ message process procedure. 706 6.2. DODAG Local Repair in Non-Storing Mode 708 The handling of parent unreachability in Non-Storing mode is similar 709 to that in Storing mode. The first difference is that after removing 710 a DAO parent from its DAO parent set, if its DODAG parent set is not 711 empty, a node may schedule a DAO message transmission instead of the 712 No-Path DAO message transmission. The second difference is that to 713 generate a DRQ message in Non-Storing mode, a node adds a Path option 714 field by inserting its IPv6 address into the Path option field. The 715 third difference is that the DRP message is sent to destination node 716 DRPID by source routing via Path option. 718 6.2.1. DRQ Message Processing 720 When a router receives a DRQ message, it performs same filtering 721 process as that in Storing mode. If the DRQ message passes filtering 722 process, the receiving router processes the DRQ message further. 724 If the receiving router is the DODAG root, it accepts the DRQ message 725 and generates a DRP message similarly as in Storing mode. The DODAG 726 root copies Path option field from DRQ message to Path option field 727 of DRP message. The DODAG root transmits the DRP message to 728 destination node DRPID by using the route provided in Path option 729 field, and on the downward route, intermediate routers obtain next 730 hop node from the Path option field of DRP message. 732 If the receiving router is not the DODAG root and its rank is lower 733 than Rank_DRQ, it accepts the DRQ message and generates a DRP message 734 similarly as the DODAG root does. It copies the Path option field 735 from DRQ message to the Path option field of DRP message. The 736 receiving router forwards the DRP message to the node from which it 737 received the DRQ message. The DRP message is sent to destination node 738 DRPID via route provided in Path option field. 740 If the receiving router is not the DODAG root and its rank is greater 741 than or equal to Rank_DRQ, It updates the DRQ message by inserting 742 its own IPv6 address into the Path option field, increasing the value 743 of HC field by 1 and forwards the DRQ message to its preferred DODAG 744 parent. 746 6.2.2. DRP Message Processing 748 When a node receives a DRP message, it performs the same filtering 749 process as in Storing mode. If the DRP message passes filtering 750 process, the receiving node processes the DRP message further. The 751 receiving node can be a leaf node or a router. 753 If the receiving node is the DRQ message generator and the DRP 754 message sender is not in its DODAG parent set, it may add the DRP 755 message sender into its DODAG parent set. The receiving node may 756 select a new preferred DODAG parent. It may also schedule a DAO 757 message transmission if the DRP message sender is added into its DAO 758 parent set. 760 If the receiving node is not DRQ message generator, it must be a 761 router. 763 If the receiving router is not on the downward route, it discards the 764 DRP message. Otherwise, if its rank is lower than Rank_DRQ, the 765 receiving router updates the RankP_N and RankP_D fields of the DRP 766 message to the numerator and denominator of its fractional rank, 767 respectively, and forwards the DRP message to destination node DRPID 768 by obtaining route provided in the Path option field. Again, the rank 769 of receiving router is less than Rank_DRQ if the receiving router is 770 on multiple DODAG repair downward routes. If its rank is greater than 771 or equal to Rank_DRQ, the receiving router decreases its rank to 772 sp(Rank_DRQ, Rank_DRP) and updates its DODAG parent set by removing 773 any DODAG parent whose rank is greater than or equal to sp(Rank_DRQ, 774 Rank_DRP). If its preferred DODAG parent is removed, it selects a new 775 preferred DODAG parent. The receiving router updates the RankP_N and 776 RankP_D fields of DRP message to the numerator and denominator of its 777 fractional rank, respectively, and forwards the DRP message to the 778 destination node DRPID by obtaining route provided in the Path option 779 field. Furthermore, the receiving router may schedule a DAO message 780 transmission if any of its DAO parents was removed due to its rank 781 decrease. 783 7. Security Considerations 785 This draft introduces an alternative rank computation method and a 786 DODAG local repair mechanism. In general, the security considerations 787 for the DODAG construction and maintenance are similar to the ones 788 for the operation of RPL as described in Section 19 of [RFC6550]. 789 Section 10 of RPL specification [RFC6550] describes a variety of 790 security mechanisms that provide data confidentiality, 791 authentication, replay protection and delay protection services. Each 792 RPL control message has a secure version that allows the 793 specification of the level of security and the algorithms used to 794 secure the message. New RPL control messages (DRQ and DRP) defined in 795 this draft have secure versions as well. 797 8. IANA Considerations 799 This draft defines two new RPL Control Messages types and a new RPL 800 Control Message Option. 802 Code field for the DODAG Repair Request (DRQ) message needs to be 803 assigned by IANA. 805 Code field for the DODAG Repair Reply (DRP) message needs to be 806 assigned by IANA. 808 Option Type field for Path option field needs to be assigned by IANA. 810 9. References 812 9.1. Normative References 814 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 815 Requirement Levels", BCP 14, RFC 2119, March 1997. 817 [RFC4443] Conta, A., Deering, S., and M. Gupta, "Internet Control 818 Message Protocol (ICMPv6) for the Internet Protocol 819 Version 6 (IPv6) Specification", RFC 4443, March 2006. 821 [RFC6550] Winter, T., Thubert, P., Brandt, A., Hui, J., Kelsey, R., 822 Levis, P., Pister, K., Struik, R., Vasseur, JP., and R. 823 Alexander, "RPL: IPv6 Routing Protocol for Low-Power and 824 Lossy Networks", RFC 6550, March 2012. 826 [RFC6206] Levis, P., Clausen, T., Hui, J., Gnawali, O., Ko, J., "The 827 Trickle Algorithm", RFC 6206, March 2011. 829 [RFC6551] Vasseur, JP., Kim, M., Pister, K., Dejean, N., and D. 830 Barthel, "Routing Metrics Used for Path Calculation in 831 Low-Power and Lossy Networks", RFC 6551, March 2012. 833 9.2. Informative References 835 [83rd IETF Meeting Presentation] Clausen, T., Yi, J., Colin de 836 Verdiere, A., Herberg, U., "Experiences with RPL: IPv6 837 Routing Protocol for Low power and Lossy Networks", Paris, 838 France, March 2012. 840 Authors' Addresses 842 Jianlin Guo 843 Mitsubishi Electric Research Laboratories 844 201 Broadway 845 Cambridge, Massachusetts 02139 846 USA 848 Phone: +1 617 621 7541 849 Email: guo@merl.com 851 Philip Orlik 852 Mitsubishi Electric Research Laboratories 853 201 Broadway 854 Cambridge, Massachusetts 02139 855 USA 857 Phone: +1 617 621 7570 858 Email: porlik@merl.com