idnits 2.17.1 draft-ietf-roll-p2p-rpl-03.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: o Grounded (G) Flag: MUST be cleared since this DAG is temporary in nature and MUST not be used for routing purpose. -- The document date (May 13, 2011) is 4730 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: 'Rem' is mentioned on line 822, but not defined == Missing Reference: 'Rem-1' is mentioned on line 847, 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 (-13) exists of draft-ietf-roll-terminology-05 Summary: 0 errors (**), 0 flaws (~~), 7 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: November 14, 2011 E. Baccelli 6 INRIA 7 A. Brandt 8 Sigma Designs 9 R. Cragie 10 Gridmerge Ltd 11 J. Martocci 12 Johnson Controls 13 May 13, 2011 15 Reactive Discovery of Point-to-Point Routes in Low Power and Lossy 16 Networks 17 draft-ietf-roll-p2p-rpl-03 19 Abstract 21 Point to point (P2P) communication between arbitrary IPv6 routers and 22 hosts in a Low power and Lossy Network (LLN) is a key requirement for 23 many applications. RPL, the IPv6 Routing Protocol for LLNs, 24 constrains the LLN topology to a Directed Acyclic Graph (DAG) and 25 requires the P2P routing to take place along the DAG links. Such P2P 26 routes may be suboptimal and may lead to traffic congestion near the 27 DAG root. This document specifies a P2P route discovery mechanism, 28 complementary to the RPL base functionality. This mechanism allows 29 an IPv6 router or host to discover and establish, on demand, one or 30 more routes to another IPv6 router or host in the LLN such that the 31 discovered routes meet specified constraints. 33 Status of this Memo 35 This Internet-Draft is submitted to IETF in full conformance with the 36 provisions of BCP 78 and BCP 79. 38 Internet-Drafts are working documents of the Internet Engineering 39 Task Force (IETF). Note that other groups may also distribute 40 working documents as Internet-Drafts. The list of current Internet- 41 Drafts is at http://datatracker.ietf.org/drafts/current/. 43 Internet-Drafts are draft documents valid for a maximum of six months 44 and may be updated, replaced, or obsoleted by other documents at any 45 time. It is inappropriate to use Internet-Drafts as reference 46 material or to cite them other than as "work in progress." 48 This Internet-Draft will expire on November 14, 2011. 50 Copyright Notice 52 Copyright (c) 2011 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents 57 (http://trustee.ietf.org/license-info) in effect on the date of 58 publication of this document. Please review these documents 59 carefully, as they describe your rights and restrictions with respect 60 to this document. Code Components extracted from this document must 61 include Simplified BSD License text as described in Section 4.e of 62 the Trust Legal Provisions and are provided without warranty as 63 described in the Simplified BSD License. 65 Table of Contents 67 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 68 2. The Use Cases . . . . . . . . . . . . . . . . . . . . . . . . 4 69 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 70 4. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 6 71 5. Functional Overview . . . . . . . . . . . . . . . . . . . . . 6 72 6. Propagation of Discovery Messages . . . . . . . . . . . . . . 8 73 6.1. The Route Discovery Option . . . . . . . . . . . . . . . . 9 74 6.2. Setting a DIO Carrying a Route Discovery Option . . . . . 12 75 6.3. Joining a Temporary DAG . . . . . . . . . . . . . . . . . 13 76 6.4. Changes to Trickle Operation For DIOs Carrying a Route 77 Discovery Option . . . . . . . . . . . . . . . . . . . . . 13 78 6.5. Processing a DIO Carrying a Route Discovery Option . . . . 14 79 6.6. Additional Processing of a DIO Carrying a Route 80 Discovery Option At An Intermediate Router . . . . . . . . 15 81 6.7. Additional Processing of a DIO Carrying a Route 82 Discovery Option At The Target Node . . . . . . . . . . . 15 83 7. Propagation of Discovery Reply Messages . . . . . . . . . . . 16 84 7.1. The Discovery Reply Object (DRO) . . . . . . . . . . . . . 17 85 7.2. Processing a DRO At An Intermediate Router . . . . . . . . 18 86 7.3. Processing a DRO At The Origin . . . . . . . . . . . . . . 19 87 8. Security Considerations . . . . . . . . . . . . . . . . . . . 20 88 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 89 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 20 90 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20 91 11.1. Normative References . . . . . . . . . . . . . . . . . . . 20 92 11.2. Informative References . . . . . . . . . . . . . . . . . . 21 93 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 21 95 1. Introduction 97 RPL [I-D.ietf-roll-rpl] provides multipoint-to-point (MP2P) routes 98 from routers in a Low power and Lossy Network (LLN) to a sink by 99 organizing the routers along a Directed Acyclic Graph (DAG) rooted at 100 the sink. The routers determine their position in the DAG so as to 101 optimize their routing cost on the path towards the DAG root. A 102 router advertises its position (the "rank") in the DAG by originating 103 a DODAG Information Object (DIO) message. The DIO message is sent 104 via link-local multicast and also includes information such as the 105 DAG root's identity, routing metrics/constraints 106 [I-D.ietf-roll-routing-metrics] and the objective function (OF) in 107 use. When a router joins the DAG, it determines its own rank in the 108 DAG based on that advertised by its neighbors and originates its own 109 DIO message. 111 RPL enables point-to-multipoint (P2MP) routing from a router to its 112 descendants in the DAG by allowing a router to send a Destination 113 Advertisement Object (DAO) upwards along the DAG. In non-storing 114 mode operation, a router's DAO contains a list of its preferred DAG 115 parents. The routers unicast their DAOs to the DAG root, which then 116 uses this information to arrive at source-routes from itself to the 117 individual routers. In storing mode operation, a router's DAO 118 carries potentially aggregated information regarding its descendants 119 and other local prefixes reachable through the router. The router 120 sends its DAO to a selected set of DAG parents, which then use this 121 information in their routing tables and in their own DAOs. 123 RPL also provides mechanisms for point-to-point (P2P) routing between 124 any two routers in the DAG. If the destination is within the 125 source's radio range, the source may directly send packets to the 126 destination. Otherwise, a packet's path from the source to the 127 destination depends on the storing/non-storing operation mode of the 128 DAG. In non-storing mode operation, only the DAG root maintains the 129 "downwards" routing information and hence a packet travels all the 130 way to the DAG root, which then sends it towards its destination 131 using a source route. In storing mode operation, if the destination 132 is a DAG descendant and the source maintains "downwards" hop-by-hop 133 routing state about this descendant, it can forward the packet to a 134 descendant router closer to the destination. Otherwise, the source 135 sends the packet to a DAG parent, which then applies the same set of 136 rules to forward the packet further. Thus, a packet travels up the 137 DAG until it reaches a router that knows of the downwards route to 138 the destination and then it travels down the DAG towards its 139 destination. A router may or may not maintain routing state about a 140 descendant depending on whether its immediate children send it such 141 information in their DAOs. Thus, in the best case with storing mode 142 operation, the "upwards" segment of the P2P route between a source 143 and a destination ends at the first common ancestor of the source and 144 the destination. In the worst case, the "upwards" segment would 145 extend all the way to the DAG root. In both storing and non-storing 146 mode operations, if the destination did not originate a DAO, the 147 packet will travel all the way to the DAG's root, where it will be 148 dropped. 150 The P2P routing functionality available in RPL may be inadequate for 151 applications in the home and commercial building domains for the 152 following reasons [I-D.brandt-roll-rpl-applicability-home-building] 153 [RFC5826][RFC5867]: 155 o The need to maintain routes "proactively", i.e., every possible 156 destination in the DAG must originate a DAO. 158 o Depending on the network topology and OF/metrics in use, the 159 constraint to route only along a DAG may cause significantly 160 suboptimal P2P routes and severe traffic congestion near the DAG 161 root. 163 Thus, there is a need for a mechanism that provides source-initiated 164 discovery of P2P routes that need not be along an existing DAG. This 165 document describes such a mechanism, complementary to the basic RPL 166 functionality. 168 The specified mechanism is based on a reactive on-demand approach, 169 which enables a router to discover one or more routes in either 170 direction between itself and another router in the LLN without any 171 restrictions regarding the existing DAG-membership of the links that 172 such routes may use. The discovered routes may be source routes or 173 hop-by-hop routes. The discovered routes may not be the best 174 available but are guaranteed to satisfy the desired constraints in 175 terms of the routing metrics and are thus considered "good enough" 176 from the application's perspective. 178 A complementary functionality, necessary to help decide whether to 179 initiate a route discovery, is a mechanism to measure the end-to-end 180 cost of an existing route. Section 4 provides further details on how 181 such functionality, described in [I-D.ietf-roll-p2p-measurement], can 182 be used to determine the metric constraints for use in the route 183 discovery mechanism described in this document. 185 2. The Use Cases 187 The mechanisms described in this document are intended to be employed 188 as complementary to RPL in specific scenarios that need point-to- 189 point (P2P) routes between arbitrary routers. 191 One use case, common in a home environment, involves a remote control 192 (or a motion sensor) that suddenly needs to communicate with a lamp 193 module, whose network address is a-priori known. In this case, the 194 source of data (the remote control or the motion sensor) must be able 195 to discover a route to the destination (the lamp module) "on demand". 197 Another use case, common in a large commercial building environment, 198 involves a large LLN deployment where P2P communication along a 199 particular DAG among hundreds (or thousands) of routers creates 200 severe traffic congestion near that DAG's root, and thus routes 201 across this DAG are desirable. 203 The use cases also include scenarios where energy or latency 204 constraints are not satisfied by the P2P routes along a DAG because 205 they involve traversing many more intermediate routers than necessary 206 to reach the destination. 208 3. Terminology 210 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 211 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 212 "OPTIONAL" in this document are to be interpreted as described in 213 [RFC2119]. 215 Additionally, this document uses terminology from 216 [I-D.ietf-roll-terminology] and [I-D.ietf-roll-rpl]. This document 217 introduces the following terms: 219 Origin : The RPL node initiating the route discovery. The origin 220 acts as one end point of the routes to be discovered. 222 Target : The RPL node at the other end point of the routes to be 223 discovered. 225 Intermediate Router: An RPL router that is neither the origin nor the 226 target. 228 Forward Route: A route from the origin to the target. 230 Backward Route: A route from the target to the origin. 232 Bidirectional Route: A route that is both forward and backward. 234 Source Route: A complete and ordered list of routers that can be used 235 by a packet to travel from a source to a destination node. 237 Hop-by-hop Route: The route characterized by each router on the route 238 using its routing table to determine the next hop on the route. 240 4. Applicability 242 The route discovery mechanism, described in this document, may be 243 invoked by an origin when no route exists between itself and the 244 target or when the existing routes do not satisfy the desired 245 performance requirements. The mechanism is designed to discover one 246 or more routes that meet the specified constraints in either 247 direction between an origin and a target. In some application 248 contexts, the metric constraints that the discovered routes must 249 satisfy are intrinsically known or can be specified by the 250 application. For example, an origin that expects a target to be less 251 than 5 hops away may use "hop-count < 5" as the constraint. In other 252 application contexts, the origin may need to measure the cost of an 253 existing route to the target to determine the constraints. For 254 example, an origin that measures the total ETX of its along-DAG route 255 to the target to be 20 may use "ETX < x*20", where x is a fraction 256 that the origin decides, as the constraint. The functionality 257 required to measure the cost of an existing route between the origin 258 and the target is described in [I-D.ietf-roll-p2p-measurement]. In 259 case, there is no existing route between the origin and target or the 260 cost measurement for the existing route fails, the origin will have 261 to guess the constraints used in the initial route discovery. Once, 262 the initial route discovery succeeds or fails, the origin will have a 263 better estimate for the constraints to be used in the subsequent 264 route discovery. 266 This document describes an on-demand discovery mechanism for P2P 267 routes that is complementary to the proactive routes offered by RPL 268 base functionality. The mechanism described in this document may 269 result in discovery of better P2P routes than the ones available 270 along a DAG designed to optimize routing cost to the DAG's root. The 271 improvement in route quality depends on a number of factors including 272 the network topology, the routing metrics in use and the prevalent 273 conditions in the network. A network designer may take in 274 consideration both the benefits (potentially better routes; no need 275 to maintain routes proactively) and costs (control messages generated 276 during the route discovery process) when using this mechanism. 278 5. Functional Overview 280 This section contains a high level description of the route discovery 281 mechanism proposed in this document. 283 The route discovery begins with the origin generating a "Discovery" 284 message. The origin indicates in the message: 286 o The target; 288 o The relevant routing metrics; 290 o The constraints that the discovered route must satisfy. These 291 constraints also limit how far the Discovery message may travel; 293 o The direction (forward: from the origin to the target; backward: 294 from the target to the origin; or bidirectional) of the route 295 being discovered; 297 o The desired number of routes (in case forward/bidirectional routes 298 are being discovered); 300 o Whether the route is a source route or a hop-by-hop one. 302 The Discovery message propagates via IPv6 link-local multicast 303 towards the target accumulating the relevant routing metric values as 304 well as the route it takes. A receiving router (including the 305 target) discards the Discovery message if the accumulated routing 306 metric values do not satisfy the listed constraints. A router may 307 also discard the Discovery message if it does not wish to be a part 308 of the discovered route due to limited resources or due to policy 309 reasons. 311 The route discovery process may result in the discovery of several 312 routes. This document does not specify how the target selects routes 313 among the ones discovered. Example selection methods include 314 selecting routes as they are discovered or selecting the best routes 315 discovered over a certain time period. 317 If the origin had requested the discovery of backward source-routes, 318 the target caches one or more discovered source-routes. 319 Additionally, the target sends a "Discovery Reply" message to the 320 origin to acknowledge the discovery of these routes. 322 If the origin had requested the discovery of "n" forward source- 323 routes, the target sends the discovered source-routes to the origin 324 in "n" Discovery Reply messages, with one Discovery Reply message 325 carrying one discovered source-route. 327 If the origin had requested the discovery of "n" bidirectional 328 source-routes, the target caches "n" discovered source-routes it 329 selects and also sends these routes to the origin in "n" Discovery 330 Reply messages. 332 If the origin had requested the discovery of "n" forward/backward/ 333 bidirectional hop-by-hop routes, the target sends out a Discovery 334 Reply message to the origin for each one of the "n" discovered routes 335 it selects. The Discovery Reply message travels towards the origin 336 along the discovered route. As this message travels towards the 337 origin, it establishes appropriate forward/backward routing state in 338 the routers on the path. 340 6. Propagation of Discovery Messages 342 RPL uses DIO message propagation to build a DAG. The DIO message 343 travels via IPv6 link-local multicast. Each router joining the DAG 344 determines a rank for itself and ignores the subsequent DIO messages 345 received from lower (higher in numerical value) ranked neighbors. 346 Thus, the DIO messages propagate outward from the DAG root rather 347 than return inward towards the DAG root. The DIO message generation 348 at a router is further controlled by a Trickle timer that allows a 349 router to avoid generating unnecessary messages [RFC6206]. The link- 350 local multicast based propagation, Trickle-controlled generation and 351 the rank-based poisoning of messages traveling in the wrong direction 352 (towards the DAG root) provide powerful incentives to use the DIO 353 message as the Discovery message and propagate the DIO/Discovery 354 message by creating a "temporary" DAG. Such an approach also allows 355 reuse of the routing metrics, objective function and packet 356 forwarding framework developed for RPL. This document defines a new 357 RPL option, Route Discovery Option (RDO), which when carried inside a 358 DIO message identifies that message as doing P2P route discovery by 359 creating a temporary DAG as specified in this document. 361 The use of trickle timers to delay the propagation of DIO messages 362 may cause some nodes to generate these messages even when the desired 363 routes have already been discovered. In order to preempt the 364 generation of such unnecessary messages, the target may set a "stop" 365 bit in the Discovery Reply message (Section 7) to let the nodes in 366 the LLN know about the completion of the route discovery process. 368 6.1. The Route Discovery Option 370 0 1 2 3 371 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 372 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 373 | Type = 9 | Option Length | D |H| N | L | Compr | Rem | 374 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 375 | | 376 | Target | 377 | | 378 | | 379 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 380 | | 381 | Address[1..n] | 382 | | 383 | | 384 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 386 Figure 1: Format of the Route Discovery Option 388 In order to be used as a Discovery message, a DIO MUST carry a Route 389 Discovery Option (RDO) illustrated in Figure 1. A Discovery Reply 390 Object (DRO), defined in Section 7.1, MUST also carry a Route 391 Discovery Option. A DIO/DRO message MUST NOT carry more than one 392 Route Discovery Option. A router MUST discard a DIO/DRO if it 393 contains more than one Route Discovery Option. A Route Discovery 394 Option consists of the following fields: 396 o Option Type = 0x09 (to be confirmed by IANA). 398 o Option Length = The length of the option in bytes. 400 o Direction (D): This 2-bit field indicates the direction of the 401 desired routes: 403 * 0x00: Forward; 405 * 0x01: Backward; 407 * 0x02: Bidirectional. 409 When the Route Discovery Option is carried inside a DIO, the link- 410 level metric objects contained in the DIO SHOULD be measured in 411 the direction indicated by the D field. Also, the IPv6 addresses 412 accumulated in the Address vector MUST be accessible in the 413 direction indicated by the D field. When the Route Discovery 414 Option is carried inside a DRO, this field MUST be set to zero on 415 transmission and ignored on reception. 417 o HopByHop (H): This flag, when set to 1, indicates that hop-by-hop 418 routes are desired. The flag is cleared when the source routes 419 are desired. 421 o Number of Routes (N): When the Route Discovery Option is being 422 carried inside a DIO: 424 * The value in this field plus one indicates the number of routes 425 desired. 427 * This field is relevant only when the forward or bidirectional 428 routes are being discovered. 430 * When the backward routes are being discovered, this field MUST 431 be set to zero on transmission and ignored on reception. 433 When the Route Discovery Option is being carried inside a DRO, 434 this field MUST be set to zero on transmission and ignored on 435 reception. 437 o Life Time (L): A 2-bit field that indicates the suggested life 438 time of the temporary DAG, i.e., the suggested duration a router 439 joining the temporary DAG must maintain its membership in the DAG. 440 The mapping between the values in this field and the minimum life 441 time of the temporary DAG is as follows: 443 * 0x00: 1 second; 445 * 0x01: 4 seconds; 447 * 0x02: 16 seconds; 449 * 0x03: 64 seconds; 451 Note that a router MAY detach from the temporary DAG sooner if it 452 receives a DRO message concerning this DAG with "stop" bit set. 454 o Compr: 4-bit unsigned integer indicating the number of prefix 455 octets that are elided from the Target field and the Address 456 vector. For example, Compr value will be 0 if full IPv6 addresses 457 are carried in the Target field and the Address vector. 459 o Rem: When the Route Discovery Option is carried inside a DIO, this 460 field indicates the number of empty fields inside the Address 461 vector. When the Route Discovery Option is carried inside a DRO, 462 this field indicates the number of fields in the Address vector 463 yet to be visited. 465 o Target: The IPv6 address of the target after eliding Compr number 466 of prefix octets. 468 o Address[1..n]: A vector of IPv6 addresses representing a route 469 from the origin towards the target: 471 * Each element in the vector has size (16 - Compr) octets. 473 * The total number of elements inside the Address vector is given 474 by n = (Option Length - 4 - (16 - Compr))/(16 - Compr). 476 * When the Route Discovery Option is carried inside a DIO, the 477 Address vector is used to accumulate a route optimized in the 478 direction specified by the D field. 480 * The IPv6 addresses in the Address vector MUST be accessible in 481 the direction specified by the D field. 483 * The Address vector MUST carry the accumulated route such that 484 the first element in the Address vector contains the IPv6 485 address of the router next to the origin and so on. 487 * The origin and target addresses MUST NOT be included in the 488 Address vector. 490 * A router adding its address to the vector MUST ensure that its 491 address does not already exist in the vector. A router 492 specifying a complete route in the Address vector MUST ensure 493 that the vector does not contain any address more than once. 495 * The Address vector MUST NOT contain any multicast addresses. 497 * A DRO message travels from the target to the origin along a 498 route accumulated in the Address vector inside a Route 499 Discovery Option. Hence, the IPv6 addresses stored in the 500 Address vector MUST be accessible in the backward direction 501 also. 503 * When the Route Discovery Option is carried inside a DRO, the 504 Address vector MUST contain a complete route between the origin 505 and the target such that the first element in the vector 506 contains the IPv6 address of the router next to the origin and 507 the last element contains the IPv6 address of the router next 508 to the target. 510 6.2. Setting a DIO Carrying a Route Discovery Option 512 The Base Object in a DIO message carrying a Route Discovery Option 513 MUST be set in the following manner: 515 o RPLInstanceID: RPLInstanceID MUST be a local value as described in 516 Section 5.1 of [I-D.ietf-roll-rpl]. The origin MUST ensure that 517 different RPLInstanceID values are used in two or more concurrent 518 route discoveries it initiates. 520 o Version Number: MUST be set to zero. The temporary DAG used for 521 P2P route discovery does not exist long enough to have new 522 versions. 524 o Grounded (G) Flag: MUST be cleared since this DAG is temporary in 525 nature and MUST not be used for routing purpose. 527 o Mode of Operation (MOP), DTSN: These fields MUST be set to value 0 528 since this DAG does not support downward routing. 530 o DODAGPreference (Prf): This field MUST be set to value 0 (least 531 preferred). 533 o DODAGID: This field MUST be set to the IPv6 address of the origin. 535 o The other fields in the Base Object can be set in the desired 536 fashion as per the rules described in [I-D.ietf-roll-rpl]. 538 The DODAG Configuration option, carried in the DIO message, MUST be 539 set in the following manner: 541 o MaxRankIncrease: This field MUST be set to 0 to disable local 542 repair of the temporary DAG. 544 o The other fields in the DODAG Configuration option, including the 545 Trickle timer parameters and the OCP, can be set in the desired 546 fashion as per the rules described in [I-D.ietf-roll-rpl]. 548 A DIO, carrying a Route Discovery Option, MUST NOT carry any Route 549 Information or Prefix Information options described in 550 [I-D.ietf-roll-rpl]. 552 The origin MUST NOT originate a DIO with a particular RPLInstanceID 553 for the P2P route discovery more than once in a given 554 P2PDISCOVERY_TIMEOUT duration. 556 6.3. Joining a Temporary DAG 558 When a router joins a temporary DAG advertized by a DIO carrying a 559 Route Discovery Option, it SHOULD maintain its membership in the DAG 560 for the suggested Life Time duration listed in the Route Discovery 561 Option. Maintaining membership in the DAG implies remembering: 563 o The RPLInstanceID, the DODAGID and the DODAGVersionNumber for the 564 temporary DAG; 566 o The router's rank in the temporary DAG; 568 o The best values of the routing metrics, along with the associated 569 route from the origin untill this router (carried inside the Route 570 Discovery Option) in the DIOs received so far. 572 The only purpose of a temporary DAG's existence is to facilitate the 573 propagation of the Discovery messages. The temporary DAG MUST NOT be 574 used to route packets. A router SHOULD detach from the temporary DAG 575 once the duration of its membership in the DAG has exceeded the DAG's 576 suggested life time. A router MAY detach from a temporary DAG sooner 577 when it receives a DRO about the temporary DAG with stop flag set. 579 6.4. Changes to Trickle Operation For DIOs Carrying a Route Discovery 580 Option 582 The DIOs carrying a Route Discovery Option create a DAG solely for 583 the purpose of P2P route discovery. This DAG is temporary in nature, 584 i.e., it exists just long enough to allow the completion of the P2P 585 route discovery process. Low latency is a critical requirement for 586 P2P route discovery in many application scenarios in home and 587 building automation LLNs [RFC5826][RFC5867]. This means that the 588 Imin and Imax parameters, used in Trickle timer operation to control 589 the generation of DIOs for this temporary DAG, can not be too large. 590 Low values for Imin/Imax mean frequent generation of DIOs advertising 591 same information as before. These DIO transmissions would mostly be 592 unnecessary, expensive in terms of energy consumption and may cause 593 congestion in the LLN during the P2P route discovery. One way to 594 avoid the potential DIO storm, caused by frequent DIO generation, is 595 to set the redundancy constant to a small value. A small redundacy 596 constant would suppress a DIO transmission if sufficient "consistent" 597 DIOs have been heard during the preceding Trickle interval. However, 598 a small redundancy constant may also cause a router to not generate 599 its DIO even when the router has a better route to report. 601 Thus, the key requirements regarding DIO generation, from the 602 perspective of P2P route discovery, are as follows: 604 o A router should generate a DIO quickly when it has a better route 605 to advertise. 607 o The DIO generation policy must not lead to a DIO storm. 609 To meet these requirements, 611 o A DIO, carrying a Route Discovery Option, SHOULD be suppressed if 612 the router does not have a better route to advertise. This rule 613 applies irrespecive of the values of the redundancy constant and 614 the number of "consistent" DIOs received in the preceding Trickle 615 interval. 617 o A DIO, carrying a Route Discovery Option, SHOULD NOT be suppressed 618 if the router has a better route to advertise. This rule applies 619 irrespecive of the values of the redundancy constant and the 620 number of "consistent" DIOs received in the preceding Trickle 621 interval. 623 o A router SHOULD consider the receipt of a DIO, that leads to an 624 improvement in the aggregated routing metrics values the router 625 could advertise for this temporary DAG, as an "inconsistency" and 626 hence reset the Trickle timer governing the DIO generation for 627 this temporary DAG [RFC6206]. 629 6.5. Processing a DIO Carrying a Route Discovery Option 631 The rules for DIO processing and transmission, described in Section 8 632 of RPL [I-D.ietf-roll-rpl], apply to DIOs carrying a Route Discovery 633 option as well except as modified in this document. 635 The following rules for processing a DIO carrying a Route Discovery 636 Option apply to both intermediate routers and the target. 638 A router SHOULD update the values of link-level routing metrics 639 included inside the DIO in the direction indicated by the D field in 640 the Route Discovery Option. If the D field is 0x00, i.e., the 641 forward routes are being discovered, any link-level routing metric 642 SHOULD be measured in the direction towards the node receiving the 643 DIO. If the D field is 0x01, i.e., the backward routes are being 644 discovered, any link-level routing metric SHOULD be measured in the 645 direction towards the node originating the DIO. If the D field is 646 0x02, i.e., the bidirectional routes are being discovered, any link- 647 level routing metric SHOULD be calculated so as to take in account 648 the metric's value in both directions. 650 A router MUST discard the DIO with no further processing if it can 651 not evaluate the mandatory route constraints listed in the DIO or if 652 the routing metric values do not satisfy one or more of the mandatory 653 constraints. 655 6.6. Additional Processing of a DIO Carrying a Route Discovery Option 656 At An Intermediate Router 658 When an intermediate router receives a DIO containing a Route 659 Discovery Option, it MUST determine if this DIO is the best it has 660 received so far for this temporary DAG in terms of the routing 661 metrics listed in the DIO. If yes, the router MUST add its own IPv6 662 address to the accumulated route at location Address[n-Rem+1] inside 663 the Route Discovery Option and stores this route in memory along with 664 the routing metrics associated with this route. When a router 665 includes itself in an accumulated route, it MUST ensure that the IPv6 666 address added to the route is accessible in both the backward 667 direction and the direction indicated by the D field in the Route 668 Discovery Option. The router MUST also reset the Trickle timer 669 associated with the temporary DAG whenever it updates the best route 670 it has seen so far. When the Trickle timer fires, an intermediate 671 router checks whether DIO generation is suppressed or not as per 672 Section 6.4. If DIO generation is allowed, the router generates a 673 new DIO DIO for this temporary DAG carrying the best routing metric 674 values it knows and a Route Discovery Option that carried in its 675 Address vector the best route the router has seen so far. 677 6.7. Additional Processing of a DIO Carrying a Route Discovery Option 678 At The Target Node 680 The target considers the route accumulated inside a Route Discovery 681 Option in a received DIO as acceptable if the routing metrics inside 682 the DIO satisfy all the mandatory constraints. The target would 683 select some routes among the acceptable ones for further processing. 684 This document does not prescribe a particular method for the target 685 to select routes. Suppose the Route Discovery Option requests the 686 discovery of "n" routes. The target may select these "n" routes in 687 any manner it desires. Example selection methods include selecting 688 the first "n" acceptable routes or selecting the "n" best routes 689 discovered over a certain time period. 691 If the Route Discovery Option identifies the selected route as a 692 backward source route (D=0x01, H=0), the target stores the discovered 693 route, obtained by reversing the contents of the Address vector, in 694 its memory. The target sends a Discovery Reply Object (DRO) message 695 back to the origin (identified by the DODAGID field in the DIO) after 696 selecting the desired number of such routes. In this DRO, the target 697 includes a Route Discovery Option, which can simply be the copied 698 from one of the DIOs carrying a selected route. The mechanism for 699 the propagation of DRO messages is described in Section 7. 701 If the Route Discovery Option identifies the selected route as a 702 forward source route (D=0x00, H=0), the target sends a DRO message 703 back to the origin. In this DRO, the target includes a Route 704 Discovery Option, which has same contents as the Route Discovery 705 Option contained in the received DIO. 707 If the Route Discovery Option identifies the selected route as a 708 bidirectional source route (D=0x02, H=0), the target stores the 709 discovered route, obtained by reversing the contents of the Address 710 vector, in its memory and sends a DRO message back to the origin. In 711 this DRO, the target includes a Route Discovery Option, which has 712 same contents as the Route Discovery Option contained in the received 713 DIO. 715 If the Route Discovery Option identifies the selected route as a 716 backward hop-by-hop route (D=0x01, H=1), the target stores the state 717 for the discovered route, in the manner described in Section 7.2, in 718 its memory and sends a DRO message back to the origin. In this DRO, 719 the target includes a Route Discovery Option, which has same contents 720 as the Route Discovery Option contained in the received DIO. 722 If the Route Discovery Option identifies the selected route as a 723 forward hop-by-hop route (D=0x00, H=1), the target sends a DRO 724 message back to the origin. In this DRO, the target includes a Route 725 Discovery Option, which has same contents as the Route Discovery 726 Option contained in the received DIO. 728 The target MAY include a Metric Container Option in the DRO. This 729 Metric Container contains the end-to-end routing metric values for 730 the route specified in the Address vector inside the Route Discovery 731 Option contained in the DRO message. 733 A target MUST NOT forward a DIO carrying a Route Discovery option any 734 further. 736 7. Propagation of Discovery Reply Messages 737 7.1. The Discovery Reply Object (DRO) 739 0 1 2 3 740 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 741 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 742 | RPLInstanceID | Version |S| Reserved | 743 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 744 | | 745 | DODAGID | 746 | | 747 | | 748 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 749 | Option(s)... 750 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 752 Figure 2: Format of the Discovery Reply Object (DRO) 754 This document defines a new RPL Control Message type, the Discovery 755 Reply Object (DRO) with code 0x04 (to be confirmed by IANA), that 756 serves one of the following functions: 758 o Acknowledge to the origin the successful discovery of backward 759 source routes; 761 o Carry one forward/bidirectional source route from the target to 762 the origin; 764 o Establish one hop-by-hop forward/backward/bidirectional route as 765 it travels from the target to the origin. 767 A DRO message also serves the function of letting the routers in the 768 LLN know that a P2P route discovery is complete and no more DIO 769 messages need to be generated for the corresponding temporary DAG. A 770 DRO message MUST carry one Route Discovery Option and travel from the 771 target to the origin via link-local multicast along the route 772 specified in the Route Discovery Option. 774 The format for a Discovery Reply Object (DRO) is shown in Figure 2. 775 A DRO consists of the following fields: 777 o RPLInstanceID: The RPLInstanceID of the temporary DAG used for 778 route discovery. 780 o Version: The Version of the temporary DAG used for route 781 discovery. 783 o Stop (S): This flag, when set by the target, indicates that the 784 route discovery being performed by the temporary DAG (identified 785 by the RPLInstanceID, DODAGID and VersionNumber field inside the 786 DRO) is over. The routers, receiving such a DRO, SHOULD cancel 787 any pending DIO transmissions for this DAG and MAY detach from the 788 temporary DAG immediately. The target SHOULD set the stop flag in 789 a DRO when it does not need to receive any more routes via DIOs. 791 o Reserved: These bits are reserved for future use. These bits MUST 792 be set to zero on transmission and MUST be ignored on reception. 794 o DODAGID: The DODAGID of the temporary DAG used for route 795 discovery. The DODAGID also identifies the origin. The 796 RPLInstanceID, the Version and the DODAGID together uniquely 797 identify the temporary DAG used for route discovery and can be 798 copied from the DIO message advertizing the temporary DAG. 800 o Options: The DRO message MUST carry one Route Discovery Option 801 that MUST specify a complete route between the target and the 802 origin. The DRO message MAY carry a Metric Container Option that 803 contains the aggregated routing metrics values for the route 804 specified in Route Discovery Option. 806 7.2. Processing a DRO At An Intermediate Router 808 When a router receives a DRO message that does not list its IPv6 809 address in the DODAGID field, the router MUST process the received 810 message in the following manner: 812 o If the stop flag inside the received DRO is set and the router 813 currently belongs to the temporary DAG identified by the 814 (RPLInstanceID, DODAGID and Version Number fields of the) DRO, the 815 router SHOULD cancel any pending DIO transmissions for this 816 temporary DAG. Additionally, the router MAY detach from the 817 temporary DAG immediately. 819 o An intermediate router MUST ignore any Metric Container Option 820 contained in the DRO message. 822 o If Address[Rem] element inside the Route Discovery Option lists 823 the router's own IPv6 address, the router is a part of the route 824 carried in the Route Discovery Option. In this case, the router 825 MUST do the following: 827 * If the H flag inside the Route Discovery Option inside the DRO 828 message is set, the router MUST store state for the P2P route 829 carried inside the Route Discovery Option. This state consists 830 of: 832 + The RPLInstanceID and the DODAGID fields of the DRO. 834 + The route's destination, either origin (identified by 835 DODAGID field in DRO) or target (identified by Target field 836 in Route Discovery Option). 838 + The IPv6 address of the next hop. 840 For routes in the forward direction (D=0x00 in the Route 841 Discovery Option), the route's destination is the target and 842 the next hop address is Address[Rem+1] (unless Rem value equals 843 the number of elements in the Address vector, in which case the 844 target itself is the next hop). For routes in the backward 845 direction (D=0x01 in the Route Discovery Option), the route's 846 destination is the origin and the next hop address is 847 Address[Rem-1] (unless Rem = 1, in which case the origin itself 848 is the next hop). If the route is bidirectional (D = 0x02 in 849 the Route Discovery Option), two routing states are created, 850 one in forward direction and one in backward direction. 852 * The router MUST decrement the Rem field inside the Route 853 Discovery Option and send the DRO further via link-local 854 multicast. 856 7.3. Processing a DRO At The Origin 858 When a router receives a DRO message that lists its IPv6 address in 859 the DODAGID field, the router recognizes itself as the origin for the 860 corresponding P2P route discovery and processes the Route Discovery 861 Option contained in the DRO in the following manner. 863 If the Route Discovery Option identifies the discovered route as a 864 backward source/hop-by-hop route (D=0x01, H=0 or H=1), the origin 865 considers the DRO receipt as the acknowledgement of successful 866 completion of the P2P route discovery process. 868 If the Route Discovery Option identifies the discovered route as a 869 forward/bidirectional source route (D=0x00 or 0x02, H=0), the origin 870 stores the discovered route, contained in the Address vector, in its 871 memory. 873 If the Route Discovery Option identifies the discovered route as a 874 forward/bidirectional hop-by-hop route (D=0x00 or 0x02, H=1), the 875 origin stores the state for the discovered route in forward 876 direction, in the manner described in Section 7.2, in its memory. 878 If the received DRO message contains a Metric Container Option as 879 well, the origin MAY store the values of the routing metrics 880 associated with the discovered route in its memory. This information 881 may be useful in formulating the constraints for any future P2P route 882 discovery to the target. 884 8. Security Considerations 886 TBA 888 9. IANA Considerations 890 TBA 892 10. Acknowledgements 894 Authors gratefully acknowledge the contributions of the following 895 individuals (in alphabetical order) in the development of this 896 document: Dominique Barthel, Thomas Clausen, Richard Kelsey, Zach 897 Shelby, Pascal Thubert and JP Vasseur. 899 11. References 901 11.1. Normative References 903 [I-D.ietf-roll-p2p-measurement] 904 Goyal, M., Baccelli, E., Brandt, A., Cragie, R., Martocci, 905 J., and C. Perkins, "A Mechanism to Measure the Quality of 906 a Point-to-point Route in a Low Power and Lossy Network", 907 draft-ietf-roll-p2p-measurement-00 (work in progress), 908 April 2011. 910 [I-D.ietf-roll-routing-metrics] 911 Vasseur, J., Kim, M., Pister, K., Dejean, N., and D. 912 Barthel, "Routing Metrics used for Path Calculation in Low 913 Power and Lossy Networks", 914 draft-ietf-roll-routing-metrics-19 (work in progress), 915 March 2011. 917 [I-D.ietf-roll-rpl] 918 Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., 919 Kelsey, R., Levis, P., Pister, K., Struik, R., and J. 920 Vasseur, "RPL: IPv6 Routing Protocol for Low power and 921 Lossy Networks", draft-ietf-roll-rpl-19 (work in 922 progress), March 2011. 924 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 925 Requirement Levels", BCP 14, RFC 2119, March 1997. 927 [RFC6206] Levis, P., Clausen, T., Hui, J., Gnawali, O., and J. Ko, 928 "The Trickle Algorithm", RFC 6206, March 2011. 930 11.2. Informative References 932 [I-D.brandt-roll-rpl-applicability-home-building] 933 Brandt, A., Baccelli, E., and R. Cragie, "Applicability 934 Statement: The use of RPL in Building and Home 935 Environments", 936 draft-brandt-roll-rpl-applicability-home-building-01 (work 937 in progress), November 2010. 939 [I-D.ietf-roll-terminology] 940 Vasseur, J., "Terminology in Low power And Lossy 941 Networks", draft-ietf-roll-terminology-05 (work in 942 progress), March 2011. 944 [RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation 945 Routing Requirements in Low-Power and Lossy Networks", 946 RFC 5826, April 2010. 948 [RFC5867] Martocci, J., De Mil, P., Riou, N., and W. Vermeylen, 949 "Building Automation Routing Requirements in Low-Power and 950 Lossy Networks", RFC 5867, June 2010. 952 Authors' Addresses 954 Mukul Goyal (editor) 955 University of Wisconsin Milwaukee 956 3200 N Cramer St 957 Milwaukee, WI 53201 958 USA 960 Phone: +1 414 2295001 961 Email: mukul@uwm.edu 963 Emmanuel Baccelli 964 INRIA 966 Phone: +33-169-335-511 967 Email: Emmanuel.Baccelli@inria.fr 968 URI: http://www.emmanuelbaccelli.org/ 969 Anders Brandt 970 Sigma Designs 971 Emdrupvej 26A, 1. 972 Copenhagen, Dk-2100 973 Denmark 975 Phone: +45-29609501 976 Email: abr@sdesigns.dk 978 Robert Cragie 979 Gridmerge Ltd 980 89 Greenfield Crescent 981 Wakefield WF4 4WA 982 UK 984 Phone: +44-1924910888 985 Email: robert.cragie@gridmerge.com 987 Jerald Martocci 988 Johnson Controls 989 507 E Michigan St 990 Milwaukee, WI 53202 991 USA 993 Phone: +1 414-524-4010 994 Email: jerald.p.martocci@jci.com