idnits 2.17.1 draft-dt-roll-p2p-rpl-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- 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 (August 9, 2010) is 5003 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '0' on line 859 == Unused Reference: 'I-D.ietf-6man-rpl-option' is defined on line 943, but no explicit reference was found in the text == Outdated reference: A later version (-04) exists of draft-brandt-roll-rpl-applicability-home-building-00 == Outdated reference: A later version (-06) exists of draft-ietf-6man-rpl-option-00 == Outdated reference: A later version (-07) exists of draft-ietf-6man-rpl-routing-header-00 == Outdated reference: A later version (-20) exists of draft-ietf-roll-of0-03 == Outdated reference: A later version (-19) exists of draft-ietf-roll-routing-metrics-08 == Outdated reference: A later version (-19) exists of draft-ietf-roll-rpl-11 == Outdated reference: A later version (-13) exists of draft-ietf-roll-terminology-03 == Outdated reference: A later version (-08) exists of draft-ietf-roll-trickle-02 == Outdated reference: A later version (-01) exists of draft-thubert-6man-reverse-routing-header-00 Summary: 0 errors (**), 0 flaws (~~), 11 warnings (==), 2 comments (--). 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 Milwaukee 4 Intended status: Standards Track E. Baccelli, Ed. 5 Expires: February 10, 2011 INRIA 6 P2P. Team 7 August 9, 2010 9 Reactive Discovery of Point-to-Point Routes in Low Power and Lossy 10 Networks 11 draft-dt-roll-p2p-rpl-02 13 Abstract 15 Point to point (P2P) communication between arbitrary IPv6 routers and 16 hosts in a Low power and Lossy Network (LLN) is a key requirement for 17 many applications. RPL, the IPv6 Routing Protocol for LLNs, 18 constrains the LLN topology to a Directed Acyclic Graph (DAG) and 19 requires the P2P routing to take place along the DAG links. Such P2P 20 routes may be significantly suboptimal and may lead to traffic 21 congestion near the DAG root. This document describes a P2P route 22 discovery mechanism complementary to RPL base functionality. This 23 mechanism allows an RPL-aware IPv6 router or host to discover and 24 establish on demand one or more routes to another RPL-aware IPv6 25 router or host in the LLN such that the discovered routes meet the 26 specified cost criteria. 28 Status of this Memo 30 This Internet-Draft is submitted to IETF in full conformance with the 31 provisions of BCP 78 and BCP 79. 33 Internet-Drafts are working documents of the Internet Engineering 34 Task Force (IETF). Note that other groups may also distribute 35 working documents as Internet-Drafts. The list of current Internet- 36 Drafts is at http://datatracker.ietf.org/drafts/current/. 38 Internet-Drafts are draft documents valid for a maximum of six months 39 and may be updated, replaced, or obsoleted by other documents at any 40 time. It is inappropriate to use Internet-Drafts as reference 41 material or to cite them other than as "work in progress." 43 This Internet-Draft will expire on February 10, 2011. 45 Copyright Notice 47 Copyright (c) 2010 IETF Trust and the persons identified as the 48 document authors. All rights reserved. 50 This document is subject to BCP 78 and the IETF Trust's Legal 51 Provisions Relating to IETF Documents 52 (http://trustee.ietf.org/license-info) in effect on the date of 53 publication of this document. Please review these documents 54 carefully, as they describe your rights and restrictions with respect 55 to this document. Code Components extracted from this document must 56 include Simplified BSD License text as described in Section 4.e of 57 the Trust Legal Provisions and are provided without warranty as 58 described in the Simplified BSD License. 60 Table of Contents 62 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 63 2. Targeted Use Cases . . . . . . . . . . . . . . . . . . . . . . 4 64 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 65 4. Functional Overview . . . . . . . . . . . . . . . . . . . . . 6 66 5. Propagation of Discovery Messages . . . . . . . . . . . . . . 7 67 5.1. The Route Discovery Option . . . . . . . . . . . . . . . . 8 68 5.2. Setting a DIO Carrying a Route Discovery Option . . . . . 9 69 5.3. Joining a Temporary DAG . . . . . . . . . . . . . . . . . 11 70 5.4. Processing a DIO Carrying a Route Discovery Option . . . . 11 71 5.5. Additional Processing of a DIO Carrying a Route 72 Discovery Option At An Intermediate Router . . . . . . . . 12 73 5.6. Additional Processing of a DIO Carrying a Route 74 Discovery Option At The Target Node . . . . . . . . . . . 13 75 6. Propagation of Discovery Reply Messages . . . . . . . . . . . 13 76 6.1. The Discovery Reply Object (DRO) . . . . . . . . . . . . . 14 77 6.1.1. The Source Route Option . . . . . . . . . . . . . . . 16 78 6.1.2. Processing a DRO At An Intermediate Router . . . . . . 17 79 6.2. DRO as Acknowledgement for Backward Source Routes . . . . 18 80 6.3. DRO as Carrier of Forward/Bidirectional Source Routes . . 18 81 6.4. Establishing Hop-by-hop Routes Via DRO . . . . . . . . . . 18 82 7. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 19 83 8. Security Considerations . . . . . . . . . . . . . . . . . . . 20 84 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 85 10. Authors and Contributors . . . . . . . . . . . . . . . . . . . 20 86 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20 87 11.1. Normative References . . . . . . . . . . . . . . . . . . . 20 88 11.2. Informative References . . . . . . . . . . . . . . . . . . 21 89 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22 91 1. Introduction 93 RPL [I-D.ietf-roll-rpl] provides multipoint-to-point (MP2P) routes 94 from nodes in a Low power and Lossy Network (LLN) to a sink node by 95 organizing the nodes along a Directed Acyclic Graph (DAG) rooted at 96 the sink. The nodes determine their position in the DAG so as to 97 optimize their routing cost to reach the DAG root. A node advertises 98 its position (the "rank") in the DAG by originating a DODAG 99 Information Object (DIO) message. The DIO message is sent via link- 100 local multicast and also includes information such as the DAG root's 101 identity, the routing metrics/constraints 102 [I-D.ietf-roll-routing-metrics] and the objective function (OF) in 103 use. When a node joins the DAG, it determines its own rank in the 104 DAG based on that advertised by its neighbors and originates its own 105 DIO message. 107 RPL enables point-to-multipoint (P2MP) routing from a node to its 108 descendants in the DAG by allowing a node to send a Destination 109 Advertisement Object (DAO) upwards along the DAG. The DAO carries 110 the potentially aggregated information regarding the descendants (and 111 other local prefixes) reachable through the originating node. 113 RPL also provides mechanisms for point-to-point (P2P) routing between 114 any two nodes in the DAG. If the destination is within the source's 115 "range", the source may directly send packets to the destination. 116 Otherwise, a packet's path from the source to the destination depends 117 on the storing/non-storing operation mode of the DAG. In non-storing 118 mode operation, only the DAG root maintains downward routing 119 information and hence a packet travels all the way to the DAG root, 120 which then sends it towards its destination using a source route. In 121 storing mode operation, if the destination is a DAG descendant and 122 the source maintains "downwards" routing state about this descendant, 123 it can forward the packet along this route. Otherwise, the source 124 sends the packet to a DAG parent, which then applies the same set of 125 rules to forward the packet further. Thus, a packet travels up the 126 DAG until it reaches a node that knows of the downwards route to the 127 destination and then it travels down the DAG towards its destination. 128 A node may or may not maintain routing state about a descendant 129 depending on whether its immediate children send it such information 130 in their DAOs. Thus, in the best case storing mode scenario, the 131 "upwards" segment of the P2P route between a source and a destination 132 ends at the first common ancestor of the source and the destination. 133 In the worst case, the "upwards" segment would extend all the way to 134 the DAG's root. In both storing and non-storing mode operations, if 135 the destination did not originate a DAO, the packet will travel all 136 the way to the DAG's root, where it will be dropped. 138 The P2P routing functionality available in RPL may be inadequate for 139 applications in the home and commercial building domains because of 140 the following reasons 141 [I-D.brandt-roll-rpl-applicability-home-building] [RFC5826][RFC5867]: 143 o The need to maintain routes "proactively", i.e. every possible 144 destination in the DAG must originate a DAO. 146 o Depending on the network topology and OF/metrics in use, the 147 constraint to route only along a DAG may potentially cause 148 significantly suboptimal P2P routes and severe traffic congestion 149 near the DAG root. 151 Clearly, there is a need for a mechanism that provides source- 152 initiated discovery of P2P routes that are not along an existing DAG. 153 This document thus describes such a mechanism, complementary to the 154 basic RPL functionality. 156 The specified scheme is based on a reactive on-demand approach, which 157 enables a node to discover one or more "good enough" routes in either 158 direction between itself and another node in the LLN without any 159 constraints regarding the existing DAG-membership of the links that 160 such routes may use. Such routes may be source-routes or hop-by-hop 161 ones. A complementary functionality, necessary to help decide 162 whether to initiate a route discovery, is a mechanism to measure the 163 end-to-end cost of an existing route. Section 7 provides further 164 details on how such functionality, to be described in a separate 165 document, can be used to determine the "good enough" criteria for use 166 in the route discovery mechanism described in this document. 168 2. Targeted Use Cases 170 The mechanisms described in this document are intended to be employed 171 as complementary to RPL in specific scenarios that need point-to- 172 point (P2P) routes between arbitrary routers. 174 One target use case, common in a home environment, involves a remote 175 control (or a motion sensor) that suddenly needs to communicate with 176 a lamp module, whose network address it knows apriori. In this case, 177 the source of data (the remote control or the motion sensor) must be 178 able to discover a route to the destination (the lamp module) "on 179 demand". 181 Another target use case, common in a large commercial building 182 environment, involves a large LLN deployment where P2P communication 183 along a particular DAG among hundreds (or thousands) of routers 184 creates severe traffic congestion near that DAG's root, and thus 185 routes across this DAG are desirable. 187 Targeted use cases also include scenarios where energy or latency 188 constraints are not satisfied by the P2P routes along a DAG because 189 they involve traversing many more intermediate routers than necessary 190 to reach the destination. 192 3. Terminology 194 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 195 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 196 "OPTIONAL" in this document are to be interpreted as described in 197 [RFC2119]. 199 Additionally, this document uses terminology from 200 [I-D.ietf-roll-terminology] and [I-D.ietf-roll-rpl]. Specifically, 201 the term node refers to an RPL router or an RPL host as defined in 202 [I-D.ietf-roll-rpl]. This document introduces the following terms: 204 Origin Node: The RPL node initiating the route discovery. The origin 205 node acts as one end point of the routes to be discovered. 207 Target Node: The RPL node at the other end point of the routes to be 208 discovered. 210 Intermediate Router: An RPL router that is neither the origin nor the 211 target. 213 Forward Route: A route from the origin node to the target node. 215 Backward Route: A route from the target node to the origin node. 217 Bidirectional Route: A route that can be used in both directions: 218 from the origin node to the target node and vice versa. 220 Source Route: A complete and ordered list of routers that can be used 221 by a packet to travel from a source node to a destination node. Such 222 source routes can be carried by a packet in a proposed Type 4 Routing 223 Header [I-D.ietf-6man-rpl-routing-header]. 225 Hop-by-hop Route: The route characterized by each router on the route 226 using its routing table to determine the next hop on the route. 228 Propagation Constraints: The constraints on aggregated routing metric 229 values, as defined in [I-D.ietf-roll-routing-metrics], that MUST be 230 satisfied before an intermediate router will process the Route 231 Discovery Option (defined in this document) contained inside a DODAG 232 Information Object (DIO). 234 Route Constraints: Additional constraints on aggregated routing 235 metric values, as defined in [I-D.ietf-roll-routing-metrics], that 236 MUST be satisfied by a discovered route in order to be considered 237 "good enough". 239 Good Enough Criteria: The propagation constraints and the route 240 constraints together constitute the good enough criteria. 242 4. Functional Overview 244 This section contains a high level description of the route discovery 245 mechanism proposed in this document. 247 The route discovery begins with the origin node generating a 248 "Discovery" message. The origin node indicates in the message: 250 o The target node; 252 o The relevant routing metrics; 254 o The constraints on how far the Discovery message may travel 255 (henceforth called the propagation constraints); 257 o Additional constraints used to determine if a discovered route is 258 "good enough" (henceforth called the route constraints); 260 o The direction (forward: from the origin node to the target node; 261 backward: from the target node to the origin node; or 262 bidirectional) of the route being discovered; 264 o The desired number of routes; 266 o Whether the route is a source-route or a hop-by-hop one. 268 The Discovery message propagates via IPv6 link-local multicast with a 269 receiving router discarding the message if it does not satisfy the 270 propagation constraints or if hop-by-hop routes are desired and the 271 router cannot store state for such a route. As a copy of the 272 Discovery message travels towards the target node, it accumulates the 273 relevant routing metric values as well as the route it takes. When 274 the target node receives a copy of the Discovery message, it applies 275 both the propagation constraints and the route constraints to 276 determine if the discovered route is good enough. Thus, the good 277 enough discovered routes satisfy both the propagation constraints as 278 well as the route constraints although the propagation of Discovery 279 messages is guided by propagation constraints alone. The propagation 280 constraints and the route constraints together constitute the good 281 enough criteria. Using only a subset of the good enough criteria as 282 the propagation constraints simplifies the operation of intermediate 283 routers, an important consideration in many LLN application domains. 285 The route discovery process may result in the discovery of several 286 good enough routes. This document does not specify how does the 287 target node select routes among the good enough ones. Example 288 selection methods include selecting the routes as they are discovered 289 or selecting the best routes discovered over a certain time period. 291 If the origin node had requested the discovery of backward source- 292 routes, the target node caches one or more good enough source-routes 293 it selects. Additionally, the target node sends one or more 294 "Discovery Reply" message to the origin node to acknowledge the 295 discovery of these routes. These acknowledgements allow the origin 296 node to judge the success of the route discovery. 298 If the origin node had requested the discovery of "n" forward source- 299 routes, the target node sends the "n" good enough source-routes it 300 selects to the origin node in one or more Discovery Reply messages. 302 If the origin node had requested the discovery of "n" bidirectional 303 source-routes, the target node caches the "n" good enough source- 304 routes it identifies and also sends these routes to the origin node 305 in one or more Discovery Reply messages. 307 If the origin node had requested the discovery of "n" forward/ 308 backward/bidirectional hop-by-hop routes, the target node sends out a 309 Discovery Reply message to the origin node for each one of the "n" 310 good enough routes it selects. The Discovery Reply message travels 311 towards the origin node along the discovered route. As this message 312 travels towards the origin node, it establishes appropriate forward/ 313 backward routing state in the routers on the path. 315 5. Propagation of Discovery Messages 317 RPL uses DIO message propagation to build a DAG. The DIO message 318 travels via IPv6 link-local multicast. Each node joining the DAG 319 determines a rank for itself and ignores the subsequent DIO messages 320 received from lower (higher in numerical value) ranked neighbors. 321 Thus, the DIO messages propagate outward from the DAG root rather 322 than return inward towards the DAG root. The DIO message generation 323 at a node is further controlled by a trickle timer that allows a node 324 to avoid generating unnecessary messages [I-D.ietf-roll-trickle]. 325 The link-local multicast based propagation, trickle-controlled 326 generation and the rank-based poisoning of messages traveling in the 327 wrong direction (towards the DAG root) provide powerful incentives to 328 use the DIO message as the Discovery message and propagate the DIO/ 329 Discovery message by creating a "temporary" DAG. The routing metrics 330 used for the creation of this temporary DAG SHOULD be same as (or be 331 a subset of) the routing metrics being used for route discovery. 332 Similarly, the objective function, used for rank calculation in the 333 temporary DAG, SHOULD be same as the objective function that 334 determines the aggregated cost of a route when limited to the routing 335 metrics being used for temporary DAG creation. 337 The propagation constraints limit the spread of the temporary DAG. 338 The temporary DAG restricts the network topology within which the 339 route discovery takes place. Thus, all the discovered routes lie 340 within this restricted topology and implicitly satisfy the 341 propagation constraints. Among the discovered routes, the good 342 enough routes are the ones that meet the route constraints. Thus, 343 for successful route discovery, the propagation constraints and the 344 route constraints MUST be compatible. The division of the overall 345 good enough criteria between the two sets of constraints is an 346 implementation specific decision. If desired, an implementation MAY 347 include all constraints in the set of propagation constraints and 348 keep the set of route constraints empty. 350 5.1. The Route Discovery Option 352 0 1 2 3 353 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 354 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 355 | Type = 9 | Option Length | D |H| N | L |O| Reserved | 356 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 357 | | 358 | Target Address | 359 | | 360 | | 361 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 362 | OCP | 363 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 365 Figure 1: Format of the Route Discovery Option 367 In order to be used as a Discovery message, a DIO MUST carry a "Route 368 Discovery" option illustrated in Figure 1. A DIO MUST NOT carry more 369 than one Route Discovery options. A router MUST ignore the second 370 and subsequent Route Discovery options carried by a DIO. A Route 371 Discovery option consists of the following fields: 373 o Option Type = 0x09 (to be confirmed by IANA). 375 o Option Length = 20 or 22 octets depending on whether the OCP field 376 is included or not. 378 o D: A 2-bit field that indicates the direction of the desired 379 routes: 381 * D = 0x00: Forward; 383 * D = 0x01: Backward; 385 * D = 0x02: Bidirectional. 387 o H: This flag, when set, indicates if hop-by-hop routes are 388 desired. The flag is cleared if source routes are desired. 390 o N: A 3-bit unsigned integer indicating the number of routes 391 desired. 393 o L: A 2-bit field indicating the minimum "Life Time" of the 394 temporary DAG, i.e., the minimum duration a router joining the 395 temporary DAG must maintain its membership in the DAG: 397 * L = 0x00: Minimum life time is 5 seconds; 399 * L = 0x01: Minimum life time is 10 seconds; 401 * L = 0x02: Minimum life time is 1 minute; 403 * L = 0x03: Minimum life time is 10 minutes. 405 o O: This flag, when set, indicates that an OCP field is present in 406 the Route Discovery option. 408 o Target Address: The IPv6 address of the target node. 410 o OCP: 16 bit unsigned integer. An optional field, present only if 411 the O flag is set, This field indicates the objective function 412 that MAY be used by the target node to compare two good enough 413 routes. 415 5.2. Setting a DIO Carrying a Route Discovery Option 417 A DIO message that carries a Route Discovery option MUST set the Base 418 Object, described in [I-D.ietf-roll-rpl], in the following manner: 420 o RPLInstanceID: RPLInstanceID MUST be a local value as described in 421 Section 4.1 of [I-D.ietf-roll-rpl]. 423 o Grounded (G) Flag: MUST be cleared since the objective of DAG 424 formation is the propagation of Route Discovery option. This DAG 425 is temporary in nature and is not used for routing purpose. 427 o Destination Advertisement Supported (A) Flag: MUST be cleared for 428 same reasons as described above. 430 o Destination Advertisement Trigger (T) Flag: MUST be cleared. 432 o Mode of Operation (MOP): This document suggests a new value (0x04) 433 for this field (to be confirmed by IANA). 435 o DODAGPreference (Prf): TBD 437 o Destination Advertisement Trigger Sequence Number (DTSN): TBD 439 o DODAGID: IPv6 address of the origin node. 441 The other fields in the Base Object are set as per the rules 442 described in [I-D.ietf-roll-rpl]. 444 The DODAG Configuration option, carried in the DIO message, specifies 445 the parameters for the trickle timer operation that governs the 446 generation of DIO messages by the routers joining the temporary DAG. 447 The future versions of this document will specify the default values 448 to be used for these parameters. The other fields defined in the 449 DODAG Configuration option are set as follows: 451 o The MaxRankIncrease field MUST be set to 0 to disable local repair 452 of the temporary DAG. 454 o This document RECOMMENDS a value 1 for the MinHopRankInc field. 456 o Objective Code Point (OCP): The OCP to be used for temporary DAG 457 formation. This document RECOMMENDS RPL Objective Function 0, as 458 defined in [I-D.ietf-roll-of0], for use as the objective function 459 for the formation of the temporary DAG. The objective function 460 used for temporary DAG formation SHOULD be compatible with the 461 objective function to determine the aggregated cost of a 462 discovered route. 464 A DIO, that contains a Route Discovery option, MUST specify the 465 propagation constraints in one or more Metric Container options 466 placed before the Route Discovery option and the route constraints in 467 the Metric Container options placed after the Route Discovery option 468 inside the DIO. The routing metrics being used for temporary DAG 469 formation SHOULD be same as or a subset of the routing metrics being 470 used for route discovery. These routing metrics MUST be placed in 471 the Metric Container options placed before the Route Discovery 472 option. 474 A DIO, carrying a Route Discovery option, MUST NOT carry any Route 475 Information or Prefix Information options described in 476 [I-D.ietf-roll-rpl]. 478 5.3. Joining a Temporary DAG 480 When a node joins a temporary DAG advertized by a DIO carrying the 481 Route Discovery option, it MUST maintain its membership in the DAG 482 for the Minimum Life Time duration listed in the Route Discovery 483 option. Maintaining membership in the DAG implies remembering: 485 o The RPLInstanceID, the DODAGID and the DODAGVersionNumber for the 486 temporary DAG; 488 o The node's rank in the temporary DAG as well as the address of at 489 least one DAG parent; 491 o The propagation and the route constraints being used; 493 o In case of intermediate routers, the values for the routing 494 metrics, along with the associated source route from the origin 495 node till this node (carried in a Record Route IPv6 Extension 496 Header proposed in [I-D.thubert-6man-reverse-routing-header]), 497 contained in the best DIO (as per the OCP specified in the DODAG 498 Configuration option) received so far. 500 Although the main purpose of a temporary DAG's existence is to 501 facilitate the propagation of the Route Discovery option, the 502 temporary DAG MAY also be used for the Discovery Reply Object 503 (defined in Section 6.1 to travel from the target node to the origin 504 node. Hence, a node in a temporary DAG SHOULD also remember the 505 address of at least one DAG parent that provides, as per the node's 506 knowledge, the best end-to-end route back to the origin node. A node 507 SHOULD delete information about a temporary DAG once the duration of 508 its membership in the DAG has exceeded the DAG's minimum life time. 510 5.4. Processing a DIO Carrying a Route Discovery Option 512 The rules for DIO processing and transmission, described in Section 7 513 of RPL [I-D.ietf-roll-rpl], apply to DIOs carrying a Route Discovery 514 option as well except as modified in this document. 516 The following rules for processing a DIO carrying a Route Discovery 517 Option apply to both intermediate routers and the target nodes. 519 A node MUST discard the DIO with no further processing and optionally 520 log an error if any of the following conditions are true: 522 o The node does not support the OCP specified in the DODAG 523 Configuration option. 525 o The node does not support one or more of the metrics contained in 526 the Metric Container options in the DIO. 528 o The node does not have sufficient information to calculate the 529 values of these routing metrics. 531 A node MUST discard the DIO with no further processing and optionally 532 log an error if any of the following conditions are found to be true 533 while processing a Route Discovery option contained in the received 534 DIO: 536 o The H field is set, i.e. hop-by-hop routes are desired, but the 537 node cannot participate in a hop-by-hop route. 539 o The node cannot maintain its membership in the temporary DAG for 540 the minimum life time duration mentioned in the Route Discovery 541 option. 543 5.5. Additional Processing of a DIO Carrying a Route Discovery Option 544 At An Intermediate Router 546 After executing the steps listed in Section 5.4, an intermediate 547 router processes a received DIO carrying a Route Discovery option in 548 the following manner. 550 The router updates the routing metric values contained in all the 551 Metric Container options inside the DIO. The router MUST discard the 552 DIO with no further processing and optionally log an error if the 553 aggregated values of the routing metrics do not meet every 554 propagation constraint listed in the DIO. The router MAY optionally 555 check the route constraints listed in the DIO and discard the DIO 556 with no further processing if these constraints are not met. 558 The router determines if this DIO is the best it has received so far 559 for this temporary DAG (as per the OCP in the DODAG Configuration 560 object). If yes, the router makes a copy of the routing metric 561 values contained in this DIO along with the route travelled by the 562 DIO so far. The router also resets the trickle timer and, at the 563 expiry of the timer, generates a new DIO for this temporary DAG 564 carrying the Route Discovery option, the best metric values it knows 565 and the source route associated with these values (in a Record Route 566 IPv6 extension header proposed in 568 [I-D.thubert-6man-reverse-routing-header]). 570 5.6. Additional Processing of a DIO Carrying a Route Discovery Option 571 At The Target Node 573 After executing the steps listed in Section 5.4, a target node 574 processes a received DIO carrying a Route Discovery option in the 575 following manner. 577 The target node updates the routing metric values contained in all 578 the Metric Container options inside the DIO. The target node MUST 579 discard the DIO with no further processing and optionally log an 580 error if the aggregated values of the routing metrics do not meet 581 every propagation and route constraint listed in the Metric Container 582 options in the DIO. 584 Otherwise, the target node considers the source route accumulated by 585 the received DIO as good enough and MAY select it as one of the 586 discovered routes. This document does not prescribe a particular 587 method for selecting routes among the good enough ones. Suppose the 588 Route Discovery option requires the target node to select "n" good 589 enough routes. The target node may select these "n" routes in any 590 manner it desires. Example selection methods include selecting the 591 first "n" good enough routes it discovers or selecting the "n" best 592 good enough routes (using the OCP specified in the Route Discovery 593 option to do the comparison) discovered over a certain time period. 595 If the target node selects at least one good enough route, it MUST 596 send one or more RPL Control Messages carrying a Discovery Reply 597 Object (defined in the next section) back to the origin node 598 (identified by the DODAGID field in the DIO Base Object) as discussed 599 in the following sections. 601 A node MUST NOT forward a DIO carrying a Route Discovery option that 602 lists one of its own addresses as the Target Address. 604 6. Propagation of Discovery Reply Messages 605 6.1. The Discovery Reply Object (DRO) 607 0 1 2 3 608 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 609 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 610 | RPLInstanceID | Version | D |H| N | Reserved | 611 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 612 | | 613 | DODAGID(*) | 614 | | 615 | | 616 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 617 | | 618 | Target Address(*) | 619 | | 620 | | 621 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 622 | Option(s)... 623 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 625 Figure 2: Format of the Discovery Reply Object (DRO) 627 This document defines a new RPL Control Message type, the Discovery 628 Reply Object (DRO) with code 0x04 (to be confirmed by IANA), that 629 serves the following functions: 631 o An acknowledgement from the target node to the origin node 632 regarding the successful discovery of backward source routes; 634 o Carries one or more forward/bidirectional source routes from the 635 target to the origin node; 637 o Establishes a hop-by-hop forward/backward/bidirectional route as 638 it travels from the target to the origin node. 640 The format for a Discovery Reply Object (DRO) is shown in Figure 2. 641 A DRO consists of the following fields: 643 o RPLInstanceID: The RPLInstanceID of the temporary DAG used for 644 route discovery. 646 o Version: The Version of the temporary DAG used for route 647 discovery. 649 o D: A 2-bit field that indicates the direction of the discovered 650 routes: 652 * D = 0x00: Forward; 654 * D = 0x01: Backward; 656 * D = 0x02: Bidirectional. 658 This field has the same value as the corresponding field in the 659 Route Discovery option. 661 o H: A flag that is set if the Discovery Reply Object is 662 establishing an hop-by-hop route. If this flag is set, the 663 Discovery Reply Object also includes: 665 * The DODAGID and Target Address fields; and 667 * One Source Route option (defined in Section 6.1.1) that 668 contains the remaining routers on the hop-by-hop route being 669 established. 671 This flag is clear if the Discovery Reply Object carries (or is an 672 acknowledgement for the discovery of) one or more source routes 673 contained in the Source Route options. 675 o N: A 3-bit field that indicates the number of source routes 676 carried or acknowledged in the Discovery Reply Object. This field 677 MUST have value 1 if the Discovery Reply Object is establishing a 678 hop-by-hop route. 680 o Reserved: These bits are reserved for future use. These bits MUST 681 be set to zero on transmission and MUST be ignored on reception. 683 o DODAGID: The DODAGID of the temporary DAG used for route 684 discovery. The DODAGID also identifies the origin node. This is 685 an optional field that MUST be present in the Discovery Reply 686 Object if H flag is set. The RPLInstanceID, the Version and the 687 DODAGID together uniquely identify the temporary DAG used for 688 route discovery and can be copied from the Base Object of the DIO 689 advertizing the temporary DAG. 691 o Target Address: The IPv6 address of the target node originating 692 the Discovery Reply Object. This is an optional field that MUST 693 be present in the Discovery Reply Object if H flag is set. 695 o Options: The Discovery Reply Object MAY carry up to N Source Route 696 options (defined in the next section) with each such option 697 carrying a source route and optionally followed by a Metric 698 Container option that lists the aggregated values for the routing 699 metrics for the source route. 701 6.1.1. The Source Route Option 703 0 1 2 3 704 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 705 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 706 | Type = 10 | Option Length | Compr | Pad | D | Resvd | 707 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 708 | | 709 . Address[1..n] . 710 . . 711 | | 712 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 714 Figure 3: Format of the Source Route Option 716 The Source Route option, illustrated in Figure 3, carries a source 717 route. A Source Route option MAY be a part of the Discovery Reply 718 Object. When a Source Route option carries a complete source route 719 between the origin and the target node, it MAY be immediately 720 followed by a Metric Container option that contains the aggregated 721 values of the routing metrics for this source route. 723 A Source Route option consists of the following fields: 725 o Option Type = 0x0A (to be confirmed by IANA). 727 o Option Length = Variable, depending on the size of the Addresses 728 vector. 730 o Compr: 4-bit unsigned integer indicating the number of prefix 731 octets that are elided from each address. For example, Compr 732 value will be 0 if full IPv6 addresses are carried in the 733 Addresses vector. 735 o Pad: 4-bit unsigned integer. Number of octets that are used for 736 padding between Address[n] and the end of the Source Route option. 738 o D: A 2-bit field that indicates the direction of the source route: 740 * D = 0x00: Forward, i.e. from the origin node to the target 741 node; 743 * D = 0x01: Backward i. e., from the target node to the origin 744 node; 746 * D = 0x02: Bidirectional. 748 Note that the D field in a Source Route option is independent from 749 the D field in the DRO containing the Source Route option. 751 o Resvd: These bits are reserved for future use. These bits MUST be 752 set to zero on transmission and MUST be ignored on reception. 754 o Address[1..n]: Vector of addresses, numbered 1 to n. Each vector 755 element has size (16 - Compr) octets. 757 Note that the format of the Source Route option is very similar to 758 that of proposed Type 4 Routing Header 759 [I-D.ietf-6man-rpl-routing-header]. 761 A common network configuration for an RPL domain is that all routers 762 within an LLN share a common prefix. The Source Route option uses 763 the Compr field to allow compaction of the Address[1..n] vector when 764 all entries share the same prefix as the DODAGID or the Target 765 Address of the encapsulating Discovery Reply Object. The shared 766 prefix octets are not carried within the Source Route option and each 767 entry in Address[1..n] has size (16 - Compr) octets. When Compr is 768 non-zero, there may exist unused octets between the last entry, 769 Address[n], and the end of the Source Route option. The Pad field 770 indicates the number of unused octets that are used for padding. 771 Note that when Compr is 0, Pad MUST be null and carry a value 0. 773 The Source Route option MUST NOT specify a path that visits a router 774 more than once. When generating a Source Route option, the target 775 node may not know the mapping between IPv6 addresses and routers. 776 Minimally, the target node MUST ensure that: 778 o The IPv6 Addresses do not appear more than once; 780 o The IPv6 addresses of the origin and the target nodes do not 781 appear in the Address vector. 783 Multicast addresses MUST NOT appear in a Source Route option. 785 6.1.2. Processing a DRO At An Intermediate Router 787 When an intermediate router receives a DRO with a clear H flag, it 788 MUST forward the DRO to a parent node in the temporary DAG. 790 When an intermediate router receives a DRO that has H flag set and 791 contains multiple Source Route options, the router MUST drop the DRO 792 with no further processing and optionally log an error message. 794 When an intermediate router receives a DRO that has H flag set and 795 contains a single Source Route option, the router processes the DRO 796 as described in Section 6.4. 798 6.2. DRO as Acknowledgement for Backward Source Routes 800 After selecting one or more backward source routes, a target node 801 MUST send a DRO message to the origin node as an acknowledgement for 802 the discovered routes. Such an acknowledgement helps the origin node 803 determine the success of route discovery. 805 A DRO, serving as an acknowledgement for backward source route 806 discovery, has its D field set to 0x01 (indicating backward) while 807 the H flag is cleared (indicating source route). The N field is set 808 to indicate the number of discovered backward source routes being 809 acknowledged. Such a DRO message MUST NOT contain any option. 811 The target node MAY unicast this DRO message to the origin node or it 812 MAY forward the DRO message to a parent in the temporary DAG. The 813 target node should take in consideration the minimum life time of the 814 temporary DAG when deciding to use it to send the DRO to the origin 815 node. 817 6.3. DRO as Carrier of Forward/Bidirectional Source Routes 819 The target node conveys the discovered forward/bidirectional source 820 routes to the origin node via the Source Route options inside one or 821 more DRO messages. Such a DRO message MUST have its D field set to 822 0x00 (if it carries forward routes) or 0x02 (if its carries 823 bidirectional routes). Also, the H flag MUST be cleared and the N 824 field MUST indicate the number of Source Route options in the DRO. 825 Each Source Route option inside the DRO MAY immediately be followed 826 by a Metric Container option that carries the aggregated values of 827 the relevant routing metrics for this source route. 829 The target node MAY unicast this DRO message to the origin node or it 830 MAY forward the DRO message to a parent in the temporary DAG. The 831 target node should take in consideration the minimum life time of the 832 temporary DAG when deciding to use it to send the DRO to the origin 833 node. 835 6.4. Establishing Hop-by-hop Routes Via DRO 837 In order to establish a hop-by-hop route, the target node sends a DRO 838 message along the discovered route, which is specified in a Source 839 Route option. The D field in the DRO is set to reflect the direction 840 of the discovered route. The H bit in the DRO MUST be set and the 841 DRO MUST include the DODAGID and Target Address fields. The N field 842 in the DRO MUST be set to 1. The target node forwards the DRO to the 843 next hop along the discovered route and includes the discovered 844 route, excluding itself and the origin node, inside the Source Route 845 option in backward direction. Thus, the D field in the Source Route 846 option MUST be 0x01. 848 A router receiving a DRO message MUST drop the DRO and optionally log 849 an error if the router cannot establish the hop-by-hop state for the 850 route or if its own address does not lie as the first element in the 851 Address vector inside the Source Route option. Otherwise, the router 852 MUST establish the hop-by-hop state in the direction specified in the 853 D field in the DRO. The hop-by-hop state in the forward direction 854 includes the RPLInstanceID, the DODAGID and the target node's 855 address. The hop-by-hop state in the backward direction includes the 856 RPLInstanceID, the DODAGID and the origin node's address. After 857 establishing the hop-by-hop state, the router MUST remove its own 858 address from the route contained in the Source Route option and 859 forward the DRO to the next hop (Address[0] in the Source Route 860 option). 862 7. Applicability 864 The route discovery mechanism described in this document may be 865 invoked by an origin node when no route exists between itself and the 866 target node or when the existing routes do not satisfy the desired 867 performance requirements. The mechanism is designed to discover one 868 or more "good enough" routes in either direction between an origin 869 and a target node. In some application contexts, the good enough 870 criteria is intrinsically known. For example, an origin node that 871 expects a target node to be less than 5 hops away may use "hop-count 872 < 5" as the good enough criteria. In other application contexts, the 873 origin node may need to measure the cost of an existing route to the 874 target node to determine the good enough criteria. For example, an 875 origin node that measures the total ETX of its along-DAG route to the 876 target node to be 20 may use "ETX < x*20", where x is a fraction that 877 the origin node decides, as the good enough criteria. The 878 functionality required to measure the cost of an existing route 879 between the origin and the target node will be described in a 880 separate document. In case, there is no existing route between the 881 origin and target nodes or the cost measurement for the existing 882 route fails, the origin node will have to guess the good enough 883 criteria for the initial route discovery. Once, the initial route 884 discovery succeeds or fails, the origin node will have a better 885 estimate for the good enough criteria to be used in the subsequent 886 route discovery. 888 This document describes an on-demand discovery mechanism for P2P 889 routes that is complimentary to the proactive routes offered by RPL 890 base functionality. The mechanism described in this document may 891 result in discovery of better P2P routes than the ones available 892 along a DAG designed to optimize routing cost to the DAG's root. The 893 improvement in route quality depends on a number of factors including 894 the network topology, the routing metrics in use and the prevalent 895 conditions in the network. A network designer may take in 896 consideration both the benefits (potentially better routes; no need 897 to maintain routes proactively) and costs (control messages generated 898 during the route discovery process) when using this mechanism. 900 8. Security Considerations 902 TBA 904 9. IANA Considerations 906 TBA 908 10. Authors and Contributors 910 In addition to the editors, the authors of this document include the 911 following individuals (listed in alphabetical order). 913 Anders Brandt, Sigma Designs, Emdrupvej 26A, 1., Copenhagen, Dk-2100, 914 Denmark. Phone: +45 29609501; Email: abr@sdesigns.dk 916 Robert Cragie, Gridmerge Ltd, 89 Greenfield Crescent, Wakefieldm WF4 917 4WA, UK. Phone: +44 1924910888; Email: robert.cragie@gridmerge.com 919 Jerald Martocci, Johnson Controls, Milwaukee, WI 53202, USA. Phone: 920 +1 414 524 4010; Email:jerald.p.martocci@jci.com 922 Charles Perkins, Tellabs Inc., USA. Email:charliep@computer.org 924 Authors gratefully acknowledge the contributions of Richard Kelsey 925 and Zach Shelby in the development of this document. 927 11. References 929 11.1. Normative References 931 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 932 Requirement Levels", BCP 14, RFC 2119, March 1997. 934 11.2. Informative References 936 [I-D.brandt-roll-rpl-applicability-home-building] 937 Brandt, A., Baccelli, E., and R. Cragie, "Applicability 938 Statement: The use of RPL in Building and Home 939 Environments", 940 draft-brandt-roll-rpl-applicability-home-building-00 (work 941 in progress), April 2010. 943 [I-D.ietf-6man-rpl-option] 944 Hui, J. and J. Vasseur, "RPL Option for Carrying RPL 945 Information in Data-Plane Datagrams", 946 draft-ietf-6man-rpl-option-00 (work in progress), 947 July 2010. 949 [I-D.ietf-6man-rpl-routing-header] 950 Hui, J., Vasseur, J., and D. Culler, "An IPv6 Routing 951 Header for Source Routes with RPL", 952 draft-ietf-6man-rpl-routing-header-00 (work in progress), 953 July 2010. 955 [I-D.ietf-roll-of0] 956 Thubert, P., "RPL Objective Function 0", 957 draft-ietf-roll-of0-03 (work in progress), July 2010. 959 [I-D.ietf-roll-routing-metrics] 960 Vasseur, J., Kim, M., Networks, D., Dejean, N., and D. 961 Barthel, "Routing Metrics used for Path Calculation in Low 962 Power and Lossy Networks", 963 draft-ietf-roll-routing-metrics-08 (work in progress), 964 July 2010. 966 [I-D.ietf-roll-rpl] 967 Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing 968 Protocol for Low power and Lossy Networks", 969 draft-ietf-roll-rpl-11 (work in progress), July 2010. 971 [I-D.ietf-roll-terminology] 972 Vasseur, J., "Terminology in Low power And Lossy 973 Networks", draft-ietf-roll-terminology-03 (work in 974 progress), March 2010. 976 [I-D.ietf-roll-trickle] 977 Levis, P., Gnawali, O., Clausen, T., Hui, J., and J. Ko, 978 "The Trickle Algorithm", draft-ietf-roll-trickle-02 (work 979 in progress), July 2010. 981 [I-D.thubert-6man-reverse-routing-header] 982 Thubert, P., "Reverse Routing Header", 983 draft-thubert-6man-reverse-routing-header-00 (work in 984 progress), June 2010. 986 [RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation 987 Routing Requirements in Low-Power and Lossy Networks", 988 RFC 5826, April 2010. 990 [RFC5867] Martocci, J., De Mil, P., Riou, N., and W. Vermeylen, 991 "Building Automation Routing Requirements in Low-Power and 992 Lossy Networks", RFC 5867, June 2010. 994 Authors' Addresses 996 Mukul Goyal (editor) 997 University of Wisconsin Milwaukee 998 3200 N Cramer St 999 Milwaukee, WI 53211 1000 USA 1002 Phone: +1 414 2295001 1003 Email: mukul@uwm.edu 1005 Emmanuel Baccelli (editor) 1006 INRIA 1008 Phone: +33-169-335-511 1009 Email: Emmanuel.Baccelli@inria.fr 1010 URI: http://www.emmanuelbaccelli.org/ 1012 P2P Team