idnits 2.17.1 draft-ietf-roll-p2p-rpl-04.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: ---------------------------------------------------------------------------- == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 23) being 62 lines 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 (July 11, 2011) is 4665 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: 'Rem' is mentioned on line 826, but not defined == Outdated reference: A later version (-10) exists of draft-ietf-roll-p2p-measurement-00 == Outdated reference: A later version (-04) exists of draft-brandt-roll-rpl-applicability-home-building-01 == Outdated reference: A later version (-06) exists of draft-ietf-6man-rpl-option-03 == Outdated reference: A later version (-07) exists of draft-ietf-6man-rpl-routing-header-03 == Outdated reference: A later version (-13) exists of draft-ietf-roll-terminology-05 Summary: 0 errors (**), 0 flaws (~~), 8 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force M. Goyal, Ed. 3 Internet-Draft University of Wisconsin 4 Intended status: Experimental Milwaukee 5 Expires: January 12, 2012 E. Baccelli 6 M. Philipp 7 INRIA 8 A. Brandt 9 Sigma Designs 10 R. Cragie 11 Gridmerge Ltd 12 J. Martocci 13 Johnson Controls 14 July 11, 2011 16 Reactive Discovery of Point-to-Point Routes in Low Power and Lossy 17 Networks 18 draft-ietf-roll-p2p-rpl-04 20 Abstract 22 Point to point (P2P) communication between arbitrary IPv6 routers in 23 a Low power and Lossy Network (LLN) is a key requirement for many 24 applications. RPL, the IPv6 Routing Protocol for LLNs, constrains 25 the LLN topology to a Directed Acyclic Graph (DAG) and requires the 26 P2P routing to take place along the DAG links. Such P2P routes may 27 be suboptimal and may lead to traffic congestion near the DAG root. 28 This document specifies a P2P route discovery mechanism, 29 complementary to the RPL base functionality. This mechanism allows 30 an IPv6 router to discover and establish, on demand, a route to 31 another IPv6 router in the LLN such that the discovered route meets 32 specified constraints. 34 Status of this Memo 36 This Internet-Draft is submitted to IETF in full conformance with the 37 provisions of BCP 78 and BCP 79. 39 Internet-Drafts are working documents of the Internet Engineering 40 Task Force (IETF). Note that other groups may also distribute 41 working documents as Internet-Drafts. The list of current Internet- 42 Drafts is at http://datatracker.ietf.org/drafts/current/. 44 Internet-Drafts are draft documents valid for a maximum of six months 45 and may be updated, replaced, or obsoleted by other documents at any 46 time. It is inappropriate to use Internet-Drafts as reference 47 material or to cite them other than as "work in progress." 49 This Internet-Draft will expire on January 12, 2012. 51 Copyright Notice 53 Copyright (c) 2011 IETF Trust and the persons identified as the 54 document authors. All rights reserved. 56 This document is subject to BCP 78 and the IETF Trust's Legal 57 Provisions Relating to IETF Documents 58 (http://trustee.ietf.org/license-info) in effect on the date of 59 publication of this document. Please review these documents 60 carefully, as they describe your rights and restrictions with respect 61 to this document. Code Components extracted from this document must 62 include Simplified BSD License text as described in Section 4.e of 63 the Trust Legal Provisions and are provided without warranty as 64 described in the Simplified BSD License. 66 Table of Contents 68 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 69 2. The Use Cases . . . . . . . . . . . . . . . . . . . . . . . . 4 70 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 71 4. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 6 72 5. Functional Overview . . . . . . . . . . . . . . . . . . . . . 6 73 6. P2P Route Discovery By Creating a Temporary DAG . . . . . . . 8 74 6.1. The Route Discovery Option . . . . . . . . . . . . . . . . 9 75 6.2. Setting a DIO Carrying a Route Discovery Option . . . . . 12 76 6.3. Joining a Temporary DAG . . . . . . . . . . . . . . . . . 13 77 6.4. Trickle Operation For DIOs Carrying a Route Discovery 78 Option . . . . . . . . . . . . . . . . . . . . . . . . . . 13 79 6.5. Processing a DIO Carrying a Route Discovery Option . . . . 14 80 6.6. Additional Processing of a DIO Carrying a Route 81 Discovery Option At An Intermediate Router . . . . . . . . 15 82 6.7. Additional Processing of a DIO Carrying a Route 83 Discovery Option At The Target . . . . . . . . . . . . . . 15 84 7. The Discovery Reply Object (DRO) . . . . . . . . . . . . . . . 16 85 7.1. Processing a DRO At An Intermediate Router . . . . . . . . 18 86 7.2. Processing a DRO At The Origin . . . . . . . . . . . . . . 19 87 8. The Discovery Reply Object Acknowledgement (DRO-ACK) . . . . . 20 88 9. Packet Forwarding Along a P2P Route . . . . . . . . . . . . . 20 89 10. Security Considerations . . . . . . . . . . . . . . . . . . . 21 90 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21 91 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 21 92 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21 93 13.1. Normative References . . . . . . . . . . . . . . . . . . . 21 94 13.2. Informative References . . . . . . . . . . . . . . . . . . 22 95 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 23 97 1. Introduction 99 RPL [I-D.ietf-roll-rpl] provides multipoint-to-point (MP2P) routes 100 from routers in a Low power and Lossy Network (LLN) to a sink by 101 organizing the routers along a Directed Acyclic Graph (DAG) rooted at 102 the sink. The routers determine their position in the DAG so as to 103 optimize their routing cost on the path towards the DAG root. A 104 router advertises its position (the "rank") in the DAG by originating 105 a DODAG Information Object (DIO) message. The DIO message is sent 106 via link-local multicast and also includes information such as the 107 DAG root's identity, routing metrics/constraints 108 [I-D.ietf-roll-routing-metrics] and the objective function (OF) in 109 use. When a router joins the DAG, it determines its own rank in the 110 DAG based on that advertised by its neighbors and originates its own 111 DIO message. 113 RPL enables point-to-multipoint (P2MP) routing from a router to its 114 descendants in the DAG by allowing a router to send a Destination 115 Advertisement Object (DAO) upwards along the DAG. In non-storing 116 mode operation, a router's DAO contains a list of its preferred DAG 117 parents. The routers unicast their DAOs to the DAG root, which then 118 uses this information to arrive at source-routes from itself to the 119 individual routers. In storing mode operation, a router's DAO 120 carries potentially aggregated information regarding its descendants 121 and other local prefixes reachable through the router. The router 122 sends its DAO to a selected set of DAG parents, which then use this 123 information in their routing tables and in their own DAOs. 125 RPL also provides mechanisms for point-to-point (P2P) routing between 126 any two routers in the DAG. If the destination is within the 127 source's radio range, the source may directly send packets to the 128 destination. Otherwise, a packet's path from the source to the 129 destination depends on the storing/non-storing operation mode of the 130 DAG. In non-storing mode operation, only the DAG root maintains the 131 "downwards" routing information and hence a packet travels all the 132 way to the DAG root, which then sends it towards its destination 133 using a source route. In storing mode operation, if the destination 134 is a DAG descendant and the source maintains "downwards" hop-by-hop 135 routing state about this descendant, it can forward the packet to a 136 descendant router closer to the destination. Otherwise, the source 137 sends the packet to a DAG parent, which then applies the same set of 138 rules to forward the packet further. Thus, a packet travels up the 139 DAG until it reaches a router that knows of the downwards route to 140 the destination and then it travels down the DAG towards its 141 destination. A router may or may not maintain routing state about a 142 descendant depending on whether its immediate children send it such 143 information in their DAOs. Thus, in the best case with storing mode 144 operation, the "upwards" segment of the P2P route between a source 145 and a destination ends at the first common ancestor of the source and 146 the destination. In the worst case, the "upwards" segment would 147 extend all the way to the DAG root. In both storing and non-storing 148 mode operations, if the destination did not originate a DAO, the 149 packet will travel all the way to the DAG's root, where it will be 150 dropped. 152 The P2P routing functionality available in RPL may be inadequate for 153 applications in the home and commercial building domains for the 154 following reasons [I-D.brandt-roll-rpl-applicability-home-building] 155 [RFC5826][RFC5867]: 157 o The need to maintain routes "proactively", i.e., every possible 158 destination in the DAG must originate a DAO. 160 o Depending on the network topology and OF/metrics in use, the 161 constraint to route only along a DAG may cause significantly 162 suboptimal P2P routes and severe traffic congestion near the DAG 163 root. 165 Thus, there is a need for a mechanism that provides source-initiated 166 discovery of a P2P route that need not be along an existing DAG. 167 This document describes such a mechanism, complementary to the basic 168 RPL functionality. 170 The specified mechanism is based on a reactive on-demand approach, 171 which enables a router to discover a route to another router in the 172 LLN without any restrictions regarding the existing DAG-membership of 173 the links that the route may use. The specified mechanism allows for 174 the discovery of sources routes as well as hop-by-hop ones. The 175 discovered route may not be the best available but is guaranteed to 176 satisfy the desired constraints in terms of the routing metrics and 177 is thus considered "good enough" from the application's perspective. 179 A complementary functionality, necessary to help decide whether to 180 initiate a route discovery, is a mechanism to measure the end-to-end 181 cost of an existing route. Section 4 provides further details on how 182 such functionality, described in [I-D.ietf-roll-p2p-measurement], can 183 be used to determine the metric constraints for use in the route 184 discovery mechanism described in this document. 186 2. The Use Cases 188 The mechanisms described in this document are intended to be employed 189 as complementary to RPL in specific scenarios that need point-to- 190 point (P2P) routes between arbitrary routers. 192 One use case, common in a home environment, involves a remote control 193 (or a motion sensor) that suddenly needs to communicate with a lamp 194 module, whose network address is a-priori known. In this case, the 195 source of data (the remote control or the motion sensor) must be able 196 to discover a route to the destination (the lamp module) "on demand". 198 Another use case, common in a large commercial building environment, 199 involves a large LLN deployment where P2P communication along a 200 particular DAG among hundreds (or thousands) of routers creates 201 severe traffic congestion near that DAG's root, and thus routes 202 across this DAG are desirable. 204 The use cases also include scenarios where energy or latency 205 constraints are not satisfied by the P2P routes along a DAG because 206 they involve traversing many more intermediate routers than necessary 207 to reach the destination. 209 3. Terminology 211 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 212 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 213 "OPTIONAL" in this document are to be interpreted as described in 214 [RFC2119]. 216 Additionally, this document uses terminology from 217 [I-D.ietf-roll-terminology] and [I-D.ietf-roll-rpl]. This document 218 introduces the following terms: 220 Origin : The RPL node initiating the route discovery. 222 Target : The RPL node at the other end point of the route(s) to be 223 discovered. 225 Intermediate Router: An RPL router that is neither the origin nor the 226 target. 228 Forward Route: A route in the forward direction, i.e., from the 229 origin to the target. 231 Backward Route: A route in the backward direction, i.e., from the 232 target to the origin. 234 Bidirectional Route: A route that can be used in both forward and 235 backward directions. 237 Source Route: A complete and ordered list of routers that can be used 238 by a packet to travel from a source to a destination node. 240 Hop-by-hop Route: The route characterized by each router on the route 241 using its routing table to determine the next hop on the route. 243 4. Applicability 245 The route discovery mechanism, described in this document, may be 246 invoked by an origin when no route exists between itself and the 247 target or when the existing routes do not satisfy the desired 248 performance requirements. The mechanism is designed to discover and 249 establish one hop-by-hop route or discover one or more source routes 250 such that the discovered route(s) meet the specified constraints. In 251 some application contexts, the constraints that the discovered 252 route(s) must satisfy are intrinsically known or can be specified by 253 the application. For example, an origin that expects a target to be 254 less than 5 hops away may use "hop-count < 5" as the constraint. In 255 other application contexts, the origin may need to measure the cost 256 of an existing route to the target to determine the constraints. For 257 example, an origin that measures the total ETX of its along-DAG route 258 to the target to be 20 may use "ETX < x*20", where x is a fraction 259 that the origin decides, as the constraint. The functionality 260 required to measure the cost of an existing route between the origin 261 and the target is described in [I-D.ietf-roll-p2p-measurement]. In 262 case, there is no existing route between the origin and target or the 263 cost measurement for the existing route fails, the origin will have 264 to guess the constraints used in the initial route discovery. Once, 265 the initial route discovery succeeds or fails, the origin will have a 266 better estimate for the constraints to be used in the subsequent 267 route discovery. 269 This document describes an on-demand discovery mechanism for P2P 270 routes that is complementary to the proactive routes offered by RPL 271 base functionality. The mechanism described in this document may 272 result in discovery of better P2P routes than the ones available 273 along a DAG designed to optimize routing cost to the DAG's root. The 274 improvement in route quality depends on a number of factors including 275 the network topology, the routing metrics in use and the prevalent 276 conditions in the network. A network designer may take in 277 consideration both the benefits (potentially better routes; no need 278 to maintain routes proactively) and costs (control messages generated 279 during the route discovery process) when using this mechanism. 281 5. Functional Overview 283 This section contains a high level description of the route discovery 284 mechanism proposed in this document. 286 The P2P route discovery takes place by forming a temporary DAG rooted 287 at the origin. The DIOs used to create the temporary DAG also carry 288 the following information: 290 o The target 292 o The relevant routing metrics 294 o The constraints that the discovered route must satisfy. These 295 constraints also limit how far the Discovery message may travel. 297 o The nature of the route(s) to be discovered: hop-by-hop or source 298 routes. This specification allows for the discovery of one hop- 299 by-hop route or up to four source routes in the forward direction. 301 o The desired number of routes (if source routes are being 302 discovered) 304 o Whether the route(s) need to be bidirectional. If bidirectional 305 route(s) are being discovered, the target may store the route in 306 backward direction for use as a source route. This specification 307 does not provide for the establishment of backward hop-by-hop 308 routes. 310 As the routers join the temporary DAG, they keep track of the best 311 (partial) route(s) they have seen and advertise these routes, along 312 with the corresponding routing metrics, in their DIOs. The routing 313 metrics are measured in forward direction unless bidirectional routes 314 are being discovered, in which case the measurement of routing 315 metrics need to take in account both forward and backward directions. 316 A router, including the target, discards a received DIO if the 317 aggregated routing metrics on the route advertised by the DIO do not 318 satisfy the listed constraints. These constraints can be used to 319 limit the propagation of DIO messages used for P2P route discovery. 320 A router may also discard a received DIO if it does not wish to be a 321 part of the discovered route due to limited resources or due to 322 policy reasons. 324 When the target receives a DIO, it checks whether the route 325 advertised therein satisfies the routing constraints. If yes, the 326 target may select the route for further processing as described next. 327 This document does not specify a particular method for the target to 328 select a route among the ones that satisfy the route constraints. 329 Example selection methods include selecting any route that meets the 330 constraints or selecting the best route(s) discovered over a certain 331 time period. 333 If one or more source routes are being discovered, the target sends 334 the discovered source routes to the origin via Discovery Reply Object 335 (DRO) messages, defined in Section 7, with one DRO message carrying 336 one discovered route. On receiving a DRO message, the origin stores 337 the route contained therein in its memory. 339 If a hop-by-hop route is being discovered, the target sends a DRO 340 message to the origin after selecting a suitable route among the ones 341 that satisfy the route constraints. The DRO message travels towards 342 the origin along the discovered route, establishing state for this 343 route in the routers on the path. 345 The target may store a discovered route in its memory if it is 346 bidirectional and use it as a backward source-route to send packets 347 to the origin. 349 The target may request the origin to acknowledge the receipt of a DRO 350 message by sending back a DRO Acknowledgement (DRO-ACK) message 351 (Section 8). The origin unicasts a DRO-ACK message to the target. 352 When the target does not receive the requested DRO-ACK within a 353 certain time interval of sending a DRO, it resends the DRO message 354 carrying the same route as before. 356 6. P2P Route Discovery By Creating a Temporary DAG 358 RPL uses DIO message propagation to build a DAG. The DIO message 359 travels via IPv6 link-local multicast. Each router joining the DAG 360 determines a rank for itself and ignores the subsequent DIO messages 361 received from lower (higher in numerical value) ranked neighbors. 362 Thus, the DIO messages propagate outward from the DAG root rather 363 than return inward towards the DAG root. The DIO message generation 364 at a router is further controlled by a Trickle timer that allows a 365 router to avoid generating unnecessary messages [RFC6206]. The link- 366 local multicast based propagation, Trickle-controlled generation and 367 the rank-based poisoning of messages traveling in the wrong direction 368 (towards the DAG root) provide powerful incentives to use the DIO 369 message for P2P route discovery by creating a "temporary" DAG. Such 370 an approach also allows the reuse of the routing metrics, objective 371 function and packet forwarding framework developed for RPL. This 372 document defines a new RPL option, Route Discovery Option (RDO), 373 which when carried inside a DIO message identifies that message as 374 doing P2P route discovery by creating a temporary DAG as specified in 375 this document. 377 The use of trickle timers to delay the propagation of DIO messages 378 may cause some nodes to generate these messages even when the desired 379 routes have already been discovered. In order to preempt the 380 generation of such unnecessary messages, the target may set a "stop" 381 bit in the DRO message to let the nodes in the LLN know about the 382 completion of the route discovery process. 384 6.1. The Route Discovery Option 386 0 1 2 3 387 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 388 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 389 | Type = 9 | Option Length |D|H| N | Compr | L | Rem | 390 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 391 | | 392 | Target | 393 | | 394 | | 395 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 396 | | 397 | Address[1..n] | 398 | | 399 | | 400 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 402 Figure 1: Format of the Route Discovery Option 404 In order to perform P2P route discovery as specified in this 405 document, a DIO MUST carry a Route Discovery Option (RDO) illustrated 406 in Figure 1. A Discovery Reply Object (DRO) message, defined in 407 Section 7, MUST also carry a Route Discovery Option. A DIO/DRO 408 message MUST NOT carry more than one Route Discovery Option. A 409 router MUST discard a DIO/DRO if it contains more than one Route 410 Discovery Option. A Route Discovery Option consists of the following 411 fields: 413 o Option Type: 0x09 (to be confirmed by IANA). 415 o Option Length: The length of the option in bytes. 417 o Direction (D): This flag indicates the direction in which the 418 desired routes should be optimized. The flag is set to 1 if the 419 routes are to be optimized for use in both forward and backward 420 directions. If the discovered routes need be optimized in the 421 forward direction only, the flag is reset to 0. Note that the 422 discovered routes must have bidirectional reachability 423 irrespective of the value of D flag. This is because the DRO 424 messages travel from the target to the origin along one of the 425 discovered routes. When the Route Discovery Option is carried 426 inside a DIO, the link-level metric objects contained in the DIO 427 SHOULD be measured in the direction indicated by the D flag. When 428 the Route Discovery Option is carried inside a DRO message, this 429 flag should be set to zero on transmission and ignored on 430 reception. 432 o Hop-by-hop (H): This flag is set to 1 if a hop-by-hop route is 433 desired. The flag is reset to zero if source routes are desired. 434 This specification allows for the establishment of one hop-by-hop 435 route and up to four source routes in the forward direction. This 436 specification does not allow for the establishment of hop-by-hop 437 routes in the backward direction. If a bidirectional route is 438 discovered, the target MAY use the route in backward direction as 439 a source route to reach the origin, irrespective of the value of H 440 flag. 442 o Number of Routes (N): When the Route Discovery Option is being 443 carried inside a DIO and the source routes are being discovered, 444 the value in this field plus one indicates the desired number of 445 routes. When a hop-by-hop route is being discovered or when the 446 Route Discovery Option is being carried inside a DRO message, this 447 field MUST be set to zero on transmission and ignored on 448 reception. 450 o Compr: 4-bit unsigned integer indicating the number of prefix 451 octets that are elided from the Target field and the Address 452 vector. For example, Compr value will be 0 if full IPv6 addresses 453 are carried in the Target field and the Address vector. 455 o Life Time (L): A 2-bit field that indicates the suggested life 456 time of the temporary DAG, i.e., the suggested duration a router 457 joining the temporary DAG must maintain its membership in the DAG. 458 The mapping between the values in this field and the minimum life 459 time of the temporary DAG is as follows: 461 * 0x00: 1 second; 463 * 0x01: 4 seconds; 465 * 0x02: 16 seconds; 467 * 0x03: 64 seconds; 469 Note that a router MAY detach from the temporary DAG sooner if it 470 receives a DRO message concerning this DAG with "stop" bit set. 471 When a Route Discovery Option is included inside a DRO message, 472 this field MUST be set to zero on transmission and ignored on 473 reception. 475 o Rem: When the Route Discovery Option is carried inside a DIO, this 476 field indicates the number of empty fields inside the Address 477 vector. When the Route Discovery Option is carried inside a DRO 478 message, this field indicates the number of fields in the Address 479 vector yet to be visited. 481 o Target: The IPv6 address of the target after eliding Compr number 482 of prefix octets. 484 o Address[1..n]: A vector of IPv6 addresses representing a (partial) 485 route in the forward direction: 487 * Each element in the vector has size (16 - Compr) octets. 489 * The total number of elements inside the Address vector is given 490 by n = (Option Length - 4 - (16 - Compr))/(16 - Compr). 492 * When the Route Discovery Option is carried inside a DIO, the 493 Address vector is used to accumulate a route optimized in the 494 direction specified by the D field. 496 * The IPv6 addresses in the Address vector MUST be accessible in 497 both forward and backward directions. Accessibility in the 498 backward direction is required because the DRO message uses the 499 route accumulated in the Address vector to travel from the 500 target to the origin. 502 * The Address vector MUST carry the accumulated route in the 503 forward direction, i.e., the first element in the Address 504 vector must contain the IPv6 address of the router next to the 505 origin and so on. 507 * The origin and target addresses MUST NOT be included in the 508 Address vector. 510 * A router adding its address to the vector MUST ensure that its 511 address does not already exist in the vector. A router 512 specifying a complete route in the Address vector MUST ensure 513 that the vector does not contain any address more than once. 515 * The Address vector MUST NOT contain any multicast addresses. 517 * When the Route Discovery Option is carried inside a DRO 518 message, the Address vector MUST contain a complete route 519 between the origin and the target such that the first element 520 in the vector contains the IPv6 address of the router next to 521 the origin and the last element contains the IPv6 address of 522 the router next to the target. 524 6.2. Setting a DIO Carrying a Route Discovery Option 526 The Base Object in a DIO message carrying a Route Discovery Option 527 MUST be set in the following manner: 529 o RPLInstanceID: RPLInstanceID MUST be a local value as described in 530 Section 5.1 of [I-D.ietf-roll-rpl]. The origin MUST NOT use the 531 same RPLInstanceID in two or more concurrent route discoveries. 532 The origin MAY use the same RPLInstanceID value to establish hop- 533 by-hop P2P routes to different target routers. 535 o Version Number: MUST be set to zero. The temporary DAG used for 536 P2P route discovery does not exist long enough to have new 537 versions. 539 o Grounded (G) Flag: MUST be cleared since this DAG is temporary in 540 nature and MUST NOT be used for routing purpose. 542 o Mode of Operation (MOP), DTSN: These fields MUST be set to value 0 543 since this DAG does not support downward routing. 545 o DODAGPreference (Prf): This field MUST be set to value 0 (least 546 preferred). 548 o DODAGID: This field MUST be set to the IPv6 address of the origin. 550 o The other fields in the Base Object can be set in the desired 551 fashion as per the rules described in [I-D.ietf-roll-rpl]. 553 The DODAG Configuration option, carried in the DIO message, MUST be 554 set in the following manner: 556 o MaxRankIncrease: This field MUST be set to 0 to disable local 557 repair of the temporary DAG. 559 o Trickle parameters SHOULD be set as described in Section 6.4. 561 o The Default Lifetime and Lifetime Unit parameters in DODAG 562 Configuration option indicate the life time of the state the 563 routers maintain for a hop-by-hop route established using the 564 mechanism described in this draft. 566 o The other fields in the DODAG Configuration option, including the 567 OCP, can be set in the desired fashion as per the rules described 568 in [I-D.ietf-roll-rpl]. 570 A DIO, carrying a Route Discovery Option, MUST NOT carry any Route 571 Information or Prefix Information options described in 573 [I-D.ietf-roll-rpl]. 575 6.3. Joining a Temporary DAG 577 When a router joins a temporary DAG advertized by a DIO carrying a 578 Route Discovery Option, it SHOULD maintain its membership in the DAG 579 for the suggested Life Time duration listed in the Route Discovery 580 Option. Maintaining membership in the DAG implies remembering: 582 o The RPLInstanceID, the DODAGID and the DODAGVersionNumber for the 583 temporary DAG; 585 o The router's rank in the temporary DAG; 587 o The best values of the routing metrics, along with the associated 588 route(s) from the origin until this router (carried inside the 589 Route Discovery Option) in the DIOs received so far. 591 The only purpose of a temporary DAG's existence is to facilitate the 592 propagation of the Discovery messages. The temporary DAG MUST NOT be 593 used to route packets. A router SHOULD detach from the temporary DAG 594 once the duration of its membership in the DAG has exceeded the DAG's 595 suggested life time. A router MAY detach from a temporary DAG sooner 596 when it receives a DRO about the temporary DAG with stop flag set. 598 6.4. Trickle Operation For DIOs Carrying a Route Discovery Option 600 An RPL router uses a Trickle timer [RFC6206] to control DIO 601 transmissions. The Trickle control of DIO transmissions provides 602 quick resolution of any "inconsistency" while avoiding redundant DIO 603 transmissions. The Trickle algorithm also imparts protection against 604 loss of DIOs due to inherent lack of reliability in wireless 605 communication. When controlling the transmissions of a DIO carrying 606 a Route Discovery Option, a Trickle timer SHOULD follow the following 607 rules: 609 o The receipt of a DIO, that allows the router to advertise a better 610 route (in terms of the routing metrics and the OCP in use) than 611 before, is considered "inconsistent" and hence resets the Trickle 612 timer. Note that the first receipt of a DIO advertising a 613 particular temporary DAG is always considered an inconsistent 614 event under this rule. 616 o The receipt of a DIO, that advertises a better route than the 617 router but does not lead to the router advertising a better route 618 itself, is considered "consistent". 620 o The receipt of a DIO, that advertises as good a route as the 621 router itself, is considered "consistent". 623 o The receipt of a DIO, that advertises a worse route than what the 624 router advertises, is considered neither "consistent" nor 625 "inconsistent", i.e., the receipt of such a DIO has no impact on 626 the Trickle operation. 628 o The recommended values of Imin and Imax are same as in base RPL 629 specification [I-D.ietf-roll-rpl], i.e., 8ms and 2.3 hours 630 respectively. 632 o The recommended value of redundancy constant "k" is 1. With this 633 value of "k", a DIO transmission will be suppressed if the router 634 receives even a single "consistent" DIO during a timer interval. 636 6.5. Processing a DIO Carrying a Route Discovery Option 638 The rules for DIO processing and transmission, described in Section 8 639 of RPL [I-D.ietf-roll-rpl], apply to DIOs carrying a Route Discovery 640 option as well except as modified in this document. 642 The following rules for processing a DIO carrying a Route Discovery 643 Option apply to both intermediate routers and the target. 645 A router SHOULD discard a received DIO with no further processing if 646 it does not have bidirectional reachability with the neighbor that 647 originated the received DIO. This is to ensure that a discovered 648 route can be used to send a DRO message from the target to the 649 origin. Note that bidirectional reachability does not mean that the 650 link must have the same values for a routing metric in both 651 directions. A router SHOULD update the values of the link-level 652 routing metrics included inside the DIO in the direction indicated by 653 the D flag in the Route Discovery Option. If the D flag is 0, i.e., 654 the discovered routes need not be bidirectional, the link-level 655 routing metrics SHOULD be measured in the forward direction, i.e., 656 towards the node receiving the DIO. If the D flag is 1, i.e., 657 bidirectional routes are desired, the link-level routing metrics 658 SHOULD be calculated so as to take in account the metric's value in 659 both forward and backward directions. 661 A router MUST discard the DIO with no further processing if it can 662 not evaluate the mandatory route constraints listed in the DIO or if 663 the routing metric values do not satisfy one or more of the mandatory 664 constraints. 666 6.6. Additional Processing of a DIO Carrying a Route Discovery Option 667 At An Intermediate Router 669 When an intermediate router receives a DIO containing a Route 670 Discovery Option, it MUST determine whether this DIO advertises a 671 better route than the router itself and whether the receipt of the 672 DIO would allow the router to advertise a better route than before. 673 Accordingly, the router SHOULD consider this DIO as consistent/ 674 inconsistent from Trickle perspective as described in Section 6.4. 675 If the received DIO would allow the router to improve the route it 676 advertises, the router MUST add its IPv6 address to the route inside 677 the received DIO at location Address[n-Rem+1] and store this route in 678 memory for inclusion in its future DIOs. When an intermediate router 679 adds itself to a route, it MUST ensure that the IPv6 address added to 680 the route is accessible in both forward and backward directions. To 681 improve the diversity of the routes being discovered, an intermediate 682 router SHOULD remember multiple partial routes, the best it knows in 683 terms of the routing metrics, that it can advertise in the Route 684 Discovery Option inside its DIO. When the router generates its DIO, 685 it SHOULD randomly select the partial route to be included in the 686 Route Discovery Option from the set of best routes it has seen so 687 far. 689 6.7. Additional Processing of a DIO Carrying a Route Discovery Option 690 At The Target 692 The target discards a received DIO with no further processing if the 693 routing metrics inside the DIO do not satisfy the the mandatory 694 constraints. Otherwise, the target MAY select the route contained in 695 the Route Discovery Option for further processing. This document 696 does not prescribe a particular method for the target to select such 697 routes. Example selection methods include selecting the desired 698 number of routes as they are identified or selecting the best routes 699 discovered over a certain time period. If multiple routes are 700 desired, the target SHOULD avoid selecting routes that have large 701 segments in common. If a discovered route is bidirectional (D=1), 702 the target MAY store the route in backward direction, obtained by 703 reversing the discovered forward route, for use as a source route to 704 reach the origin. After selecting a route, the target sends a 705 Discovery Reply Object (DRO) message back to the origin (identified 706 by the DODAGID field in the DIO). In this DRO, the target includes a 707 Route Discovery Option that contains the selected route inside the 708 Address vector. The Route Discovery Option included in the DRO 709 message MUST copy the H flag from the Route Discovery Option inside 710 the received DIO message. The other fields inside the Route 711 Discovery Option MUST be set as specified in Section 6.1. The 712 mechanism for the propagation of DRO messages is described in 713 Section 7. 715 The target MAY set the A flag inside the DRO message if it desires 716 the origin to send back a DRO-ACK message on receiving the DRO. In 717 this case, the target waits for DRO_ACK_WAIT_TIME duration for the 718 DRO-ACK message to arrive. Failure to receive the DRO-ACK message 719 within this time duration causes the target to retransmit the DRO 720 message. The target MAY retransmit the DRO message in this fashion 721 up to MAX_DRO_RETRANSMISSIONS times. 723 The target MAY include a Metric Container Option in the DRO message. 724 This Metric Container contains the end-to-end routing metric values 725 for the route specified in the Route Discovery Option. The target 726 MAY set the stop flag inside the DRO message if it has already 727 selected the desired number of routes. A target MUST NOT forward a 728 DIO carrying a Route Discovery option any further. 730 7. The Discovery Reply Object (DRO) 732 0 1 2 3 733 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 734 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 735 | RPLInstanceID | Version |S|A|Seq| Reserved | 736 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 737 | | 738 | DODAGID | 739 | | 740 | | 741 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 742 | Option(s)... 743 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 745 Figure 2: Format of the Discovery Reply Object (DRO) 747 This document defines a new RPL Control Message type, the Discovery 748 Reply Object (DRO) with code 0x04 (to be confirmed by IANA), that 749 serves one of the following functions: 751 o Carry a discovered source route from the target to the origin; 753 o Establish a hop-by-hop route as it travels from the target to the 754 origin. 756 A DRO message MAY also serve the function of letting the routers in 757 the LLN know that a P2P route discovery is complete and no more DIO 758 messages need to be generated for the corresponding temporary DAG. A 759 DRO message MUST carry one Route Discovery Option and travel from the 760 target to the origin via link-local multicast along the route 761 specified in the Route Discovery Option. 763 The format for a Discovery Reply Object (DRO) is shown in Figure 2. 764 A DRO consists of the following fields: 766 o RPLInstanceID: The RPLInstanceID of the temporary DAG used for 767 route discovery. 769 o Version: The Version of the temporary DAG used for route 770 discovery. 772 o Stop (S): This flag, when set by the target, indicates that the 773 P2P route discovery is over. The routers, receiving such a DRO, 774 SHOULD cancel any pending DIO transmissions for the temporary DAG 775 created for the route discovery and MAY detach from this DAG 776 immediately. Note that the stop flag serves to stop further DIO 777 transmissions for a P2P route discovery but it does not affect the 778 processing of DRO messages at either the origin or the 779 intermediate routers. In other words, a router (the origin or an 780 intermediate router) MUST continue to process the DRO messages 781 even if an earlier DRO message (with same RPLInstanceID, DODAGID 782 and Version Number fields) had the stop flag set. 784 o Ack Required (A): This flag, when set by the target, indicates 785 that the origin SHOULD unicast a DRO-ACK message to the target 786 when it receives the DRO. 788 o Sequence Number (Seq): This 2-bit field indicates the sequence 789 number for the DRO. This field is relevant when the A flag is 790 set, i.e., the target requests an acknowledgement from the origin 791 for a received DRO. The origin includes the RPLInstanceID, the 792 DODAGID and the Sequence Number of the received DRO inside the 793 DRO-ACK message it sends back to the target. 795 o Reserved: These bits are reserved for future use. These bits MUST 796 be set to zero on transmission and MUST be ignored on reception. 798 o DODAGID: The DODAGID of the temporary DAG used for route 799 discovery. The DODAGID also identifies the origin. The 800 RPLInstanceID, the Version and the DODAGID together uniquely 801 identify the temporary DAG used for route discovery and can be 802 copied from the DIO message advertizing the temporary DAG. 804 o Options: The DRO message MUST carry one Route Discovery Option 805 that MUST specify a complete route between the target and the 806 origin. The DRO message MAY carry a Metric Container Option that 807 contains the aggregated routing metrics values for the route 808 specified in Route Discovery Option. 810 7.1. Processing a DRO At An Intermediate Router 812 When a router receives a DRO message that does not list its IPv6 813 address in the DODAGID field, the router MUST process the received 814 message in the following manner: 816 o If the stop flag inside the received DRO is set and the router 817 currently belongs to the temporary DAG identified by the 818 (RPLInstanceID, DODAGID and Version fields of the) DRO, the router 819 SHOULD cancel any pending DIO transmissions for this temporary 820 DAG. Additionally, the router MAY detach from the temporary DAG 821 immediately. 823 o An intermediate router MUST ignore any Metric Container Option 824 contained in the DRO message. 826 o If Address[Rem] element inside the Route Discovery Option lists 827 the router's own IPv6 address, the router is a part of the route 828 carried in the Route Discovery Option. In this case, the router 829 MUST do the following: 831 * If the H flag inside the Route Discovery Option inside the DRO 832 message is set, the router SHOULD store the state for the 833 forward hop-by-hop route carried inside the Route Discovery 834 Option. This state consists of: 836 + The RPLInstanceID and the DODAGID fields of the DRO. 838 + The route's destination, the target (identified by Target 839 field in Route Discovery Option). 841 + The IPv6 address of the next hop, Address[Rem+1] (unless Rem 842 value equals the number of elements in the Address vector, 843 in which case the target itself is the next hop). 845 The router MUST drop the DRO message without further processing 846 if the H flag inside the Route Discovery Option is set but the 847 router chooses not to store the state for the hop-by-hop route. 849 * If the router already maintains a hop-by-hop state listing the 850 target as the destination and carrying same RPLInstanceID and 851 DODAGID fields as the received DRO and the next hop information 852 in the state does not match the next hop indicated in the 853 received DRO, the router MUST drop the DRO message with no 854 further processing. 856 * The router MUST decrement the Rem field inside the Route 857 Discovery Option and send the DRO further via link-local 858 multicast. 860 7.2. Processing a DRO At The Origin 862 When a router receives a DRO message that lists its IPv6 address in 863 the DODAGID field, the router recognizes itself as the origin for the 864 corresponding P2P route discovery and processes the Route Discovery 865 Option contained in the DRO in the following manner. 867 If the stop flag inside the received DRO is set and the origin still 868 belongs to the temporary DAG it initiated, it SHOULD cancel any 869 pending DIO transmissions for this temporary DAG. Additionally, the 870 origin MAY detach from the temporary DAG immediately. 872 If the Route Discovery Option inside the DRO identifies the 873 discovered route as a source route (H=0), the origin SHOULD store in 874 its memory the discovered route contained in the Address vector. 876 If the Route Discovery Option inside the DRO identifies the 877 discovered route as a hop-by-hop route (H=1), the origin SHOULD store 878 in its memory the state for the discovered route in the manner 879 described in Section 7.1. 881 If the received DRO message contains a Metric Container Option as 882 well, the origin MAY store the values of the routing metrics 883 associated with the discovered route in its memory. This information 884 may be useful in formulating the constraints for any future P2P route 885 discovery to the target. 887 If the A flag is set to one in the received DRO message, the origin 888 SHOULD generate a DRO-ACK message as described in Section 8 and 889 unicast the message to the target. The origin MAY source route the 890 DRO-ACK message to the target using the route contained in the 891 received DRO. If the received DRO established a hop-by-hop route to 892 the target, the origin MAY send the DRO-ACK message along this route. 893 Section 9 describes how a packet may be forwarded along a route 894 discovered using the mechanism described in this document. 896 8. The Discovery Reply Object Acknowledgement (DRO-ACK) 898 0 1 2 3 899 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 900 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 901 | RPLInstanceID | Version |Seq| Reserved | 902 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 903 | | 904 | DODAGID | 905 | | 906 | | 907 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 909 Figure 3: Format of the Discovery Reply Object Acknowledgement (DRO- 910 ACK) 912 A DRO message may fail to reach the origin due to a number of 913 reasons. Unlike the DIO messages that benefit from Trickle- 914 controlled retransmissions, the DRO messages are prone to loss due to 915 reasons associated with wireless communication. Since a DRO message 916 travels via link-local multicast, it can not use link-level 917 acknowledgements to improve the reliability of its transmission. 918 Also, an intermediate router may drop the DRO message (e.g., because 919 of its inability to store the state for the hop-by-hop route the DRO 920 is establishing). To protect against the potential failure of a DRO 921 message to reach the origin, the target MAY request the origin to 922 send back a DRO Acknowledgement (DRO-ACK) message on receiving a DRO 923 message. Failure to receive such an acknowledgement within the 924 DRO_ACK_WAIT_TIME interval of sending the DRO message forces the 925 target to resend the message. 927 DRO Acknowledgement is a new RPL Control Message type with code 0x05 928 (to be confirmed by IANA). A DRO-ACK message MUST travel as a 929 unicast message from the origin to the target. The format for a DRO- 930 ACK message is shown in Figure 3. Various fields in a DRO-ACK 931 message MUST have the same values as the corresponding fields in the 932 DRO message. The field marked as "Reserved" MUST be set to zero on 933 transmission and MUST be ignored on reception. 935 9. Packet Forwarding Along a P2P Route 937 This document specifies a mechanism to discover P2P routes, which can 938 be either source routes or hop-by-hop ones. A packet MAY use an RH4 939 header [I-D.ietf-6man-rpl-routing-header] to travel along a P2P 940 source route. Travel along a P2P hop-by-hop route requires 941 specifying the RPLInstanceID and the DODAGID to identify the route. 943 This is because P2P route discovery does not use globally unique 944 RPLInstanceID values and hence both the RPLInstanceID, which is a 945 local value assigned by the origin, and the DODAGID, which is an IPv6 946 address belonging to the origin, are required to uniquely identify a 947 P2P hop-by-hop route to a particular destination. A packet MAY 948 include an RPL option [I-D.ietf-6man-rpl-option] inside the IPv6 hop- 949 by-hop options header to travel along a P2P hop-by-hop route. In 950 this case, the origin MUST set the DODAGID of the P2P route as the 951 source IPv6 address of the packet. Further, the origin MUST specify 952 the RPLInstanceID, associated with the P2P route, inside the RPL 953 option and set the O flag inside the RPL option to 1. A router 954 receiving this packet will check the O flag inside the RPL option and 955 correctly infer the source IPv6 address of the packet as the DODAGID 956 of the hop-by-hop route to be used for forwarding the packet further. 958 10. Security Considerations 960 TBA 962 11. IANA Considerations 964 TBA 966 12. Acknowledgements 968 Authors gratefully acknowledge the contributions of the following 969 individuals (in alphabetical order) in the development of this 970 document: Dominique Barthel, Thomas Clausen, Richard Kelsey, Phil 971 Levis, Zach Shelby, Pascal Thubert and JP Vasseur. 973 13. References 975 13.1. Normative References 977 [I-D.ietf-roll-p2p-measurement] 978 Goyal, M., Baccelli, E., Brandt, A., Cragie, R., Martocci, 979 J., and C. Perkins, "A Mechanism to Measure the Quality of 980 a Point-to-point Route in a Low Power and Lossy Network", 981 draft-ietf-roll-p2p-measurement-00 (work in progress), 982 April 2011. 984 [I-D.ietf-roll-routing-metrics] 985 Vasseur, J., Kim, M., Pister, K., Dejean, N., and D. 986 Barthel, "Routing Metrics used for Path Calculation in Low 987 Power and Lossy Networks", 988 draft-ietf-roll-routing-metrics-19 (work in progress), 989 March 2011. 991 [I-D.ietf-roll-rpl] 992 Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., 993 Kelsey, R., Levis, P., Pister, K., Struik, R., and J. 994 Vasseur, "RPL: IPv6 Routing Protocol for Low power and 995 Lossy Networks", draft-ietf-roll-rpl-19 (work in 996 progress), March 2011. 998 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 999 Requirement Levels", BCP 14, RFC 2119, March 1997. 1001 [RFC6206] Levis, P., Clausen, T., Hui, J., Gnawali, O., and J. Ko, 1002 "The Trickle Algorithm", RFC 6206, March 2011. 1004 13.2. Informative References 1006 [I-D.brandt-roll-rpl-applicability-home-building] 1007 Brandt, A., Baccelli, E., and R. Cragie, "Applicability 1008 Statement: The use of RPL in Building and Home 1009 Environments", 1010 draft-brandt-roll-rpl-applicability-home-building-01 (work 1011 in progress), November 2010. 1013 [I-D.ietf-6man-rpl-option] 1014 Hui, J. and J. Vasseur, "RPL Option for Carrying RPL 1015 Information in Data-Plane Datagrams", 1016 draft-ietf-6man-rpl-option-03 (work in progress), 1017 March 2011. 1019 [I-D.ietf-6man-rpl-routing-header] 1020 Hui, J., Vasseur, J., Culler, D., and V. Manral, "An IPv6 1021 Routing Header for Source Routes with RPL", 1022 draft-ietf-6man-rpl-routing-header-03 (work in progress), 1023 March 2011. 1025 [I-D.ietf-roll-terminology] 1026 Vasseur, J., "Terminology in Low power And Lossy 1027 Networks", draft-ietf-roll-terminology-05 (work in 1028 progress), March 2011. 1030 [RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation 1031 Routing Requirements in Low-Power and Lossy Networks", 1032 RFC 5826, April 2010. 1034 [RFC5867] Martocci, J., De Mil, P., Riou, N., and W. Vermeylen, 1035 "Building Automation Routing Requirements in Low-Power and 1036 Lossy Networks", RFC 5867, June 2010. 1038 Authors' Addresses 1040 Mukul Goyal (editor) 1041 University of Wisconsin Milwaukee 1042 3200 N Cramer St 1043 Milwaukee, WI 53201 1044 USA 1046 Phone: +1 414 2295001 1047 Email: mukul@uwm.edu 1049 Emmanuel Baccelli 1050 INRIA 1052 Phone: +33-169-335-511 1053 Email: Emmanuel.Baccelli@inria.fr 1054 URI: http://www.emmanuelbaccelli.org/ 1056 Matthias Philipp 1057 INRIA 1059 Email: Matthias.Philipp@inria.fr 1061 Anders Brandt 1062 Sigma Designs 1063 Emdrupvej 26A, 1. 1064 Copenhagen, Dk-2100 1065 Denmark 1067 Phone: +45-29609501 1068 Email: abr@sdesigns.dk 1070 Robert Cragie 1071 Gridmerge Ltd 1072 89 Greenfield Crescent 1073 Wakefield WF4 4WA 1074 UK 1076 Phone: +44-1924910888 1077 Email: robert.cragie@gridmerge.com 1078 Jerald Martocci 1079 Johnson Controls 1080 507 E Michigan St 1081 Milwaukee, WI 53202 1082 USA 1084 Phone: +1 414-524-4010 1085 Email: jerald.p.martocci@jci.com