idnits 2.17.1 draft-thubert-roll-dao-projection-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 (November 2, 2015) is 3092 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) ** Downref: Normative reference to an Informational RFC: RFC 7102 == Outdated reference: A later version (-08) exists of draft-finn-detnet-architecture-02 == Outdated reference: A later version (-30) exists of draft-ietf-6tisch-architecture-08 Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 ROLL P. Thubert, Ed. 3 Internet-Draft J. Pylakutty 4 Intended status: Standards Track Cisco 5 Expires: May 5, 2016 November 2, 2015 7 Root initiated routing state in RPL 8 draft-thubert-roll-dao-projection-02 10 Abstract 12 This document proposes a root-initiated protocol extension to RPL 13 that enables to install a limited amount of downward routes in non- 14 storing mode. This enables loose source routing down the DODAG. 16 Status of This Memo 18 This Internet-Draft is submitted in full conformance with the 19 provisions of BCP 78 and BCP 79. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF). Note that other groups may also distribute 23 working documents as Internet-Drafts. The list of current Internet- 24 Drafts is at http://datatracker.ietf.org/drafts/current/. 26 Internet-Drafts are draft documents valid for a maximum of six months 27 and may be updated, replaced, or obsoleted by other documents at any 28 time. It is inappropriate to use Internet-Drafts as reference 29 material or to cite them other than as "work in progress." 31 This Internet-Draft will expire on May 5, 2016. 33 Copyright Notice 35 Copyright (c) 2015 IETF Trust and the persons identified as the 36 document authors. All rights reserved. 38 This document is subject to BCP 78 and the IETF Trust's Legal 39 Provisions Relating to IETF Documents 40 (http://trustee.ietf.org/license-info) in effect on the date of 41 publication of this document. Please review these documents 42 carefully, as they describe your rights and restrictions with respect 43 to this document. Code Components extracted from this document must 44 include Simplified BSD License text as described in Section 4.e of 45 the Trust Legal Provisions and are provided without warranty as 46 described in the Simplified BSD License. 48 Table of Contents 50 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 51 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 52 3. New RPL Control Message Options . . . . . . . . . . . . . . . 3 53 3.1. Via Information . . . . . . . . . . . . . . . . . . . . . 4 54 4. Loose Source Routing in Non-storing Mode . . . . . . . . . . 5 55 5. Centralized Computation of Optimized Peer-to-Peer Routes . . 9 56 6. Security Considerations . . . . . . . . . . . . . . . . . . . 12 57 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 58 8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 12 59 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 12 60 9.1. Normative References . . . . . . . . . . . . . . . . . . 13 61 9.2. Informative References . . . . . . . . . . . . . . . . . 13 62 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 14 64 1. Introduction 66 The Routing Protocol for Low Power and Lossy Networks [RFC6550] 67 (LLN)(RPL) specification defines a generic Distance Vector protocol 68 that is designed for very low energy consumption and adapted to a 69 variety of LLNs. RPL forms Destination Oriented Directed Acyclic 70 Graphs (DODAGs) which root often acts as the Border Router to connect 71 the RPL domain to the Internet. The root is responsible to select 72 the RPL Instance that is used to forward a packet coming from the 73 Internet into the RPL domain and set the related RPL information in 74 the packets. 76 The non-storing mode of operation (MOP) is largely utilized because 77 networks can get very large and the amount of memory in nodes close 78 to the root may become prohibitive in storing mode. 80 But as a network gets deep, the size of the source routing header 81 that the root must add to all the downward packets may also become an 82 issue as well. In some cases, RPL network form long lines and a 83 limited number of well-targeted routes would enable a loose source 84 routing operation and save packet size, energy, and eventually 85 fragmentation which is highly detrimental to the LLN operation. 86 Because the capability to store state in every node is limited, the 87 decision of which route is installed where can only be optimized with 88 a global knowledge of the system. 90 RPL storing mode is optimized or Point-to-Multipoint (P2MP), root to 91 leaves and Multipoint-to-Point (MP2P) leaves to root operations. 92 Peer to Peer (P2P) routes in a RPL network will generally suffer from 93 some stretch since routing between 2 peers always happens via a 94 common parent. 96 The 6TiSCH architecture [I-D.ietf-6tisch-architecture] leverages the 97 Deterministic Networking Architecture [I-D.finn-detnet-architecture] 98 as one possible model whereby the device resources and capabilities 99 are exposed to an external controller which installs routing states 100 into the network based on some objective functions that reside in 101 that external entity. 103 Based on heuristics of usage, path length, and knowledge of device 104 capacity and available resources such as battery levels and 105 reservable buffers, a Path Computation Element ([PCE]) with a global 106 visibility on the system could install additional P2P routes that are 107 more optimized for the current needs as expressed by the objective 108 function. 110 This draft enables a RPL root, with optionally the assistance of a 111 PCE, to install and maintain additional storing mode routes within 112 the RPL domain, along a selected set of nodes and for a selected 113 duration, thus providing routes from suitable than those obtained 114 from the distributed operation of RPL in either storing and non- 115 storing modes. 117 2. Terminology 119 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 120 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 121 document are to be interpreted as described in [RFC2119]. 123 The Terminology used in this document is consistent with and 124 incorporates that described in `Terminology in Low power And Lossy 125 Networks' [RFC7102] and [RFC6550]. 127 3. New RPL Control Message Options 129 Section 6.7 of [RFC6550] specifies Control Message Options (CMO) to 130 be placed in RPL messages such as the DAO message. The RPL Target 131 Option and the Transit Information Option (TIO) are such options; the 132 former indicates a node to be reached and the latter specifies a 133 parent that can be used to reach that node. Options may be 134 factorized; one or more contiguous TIOs apply to the one or more 135 contiguous Target options that immediately precede the TIOs in the 136 RPL message. 138 This specification introduces a new Control Message Option, the Via 139 Information option (VIO). Like the TIO, the VIO MUST be preceded by 140 one or more RPL Target options to which it applies. Unlike the TIO, 141 the VIO are not factorized: multiple contiguous Via options indicate 142 an ordered sequence of hops to reach the target(s), presented in the 143 same order as they would appear in a routing header. 145 3.1. Via Information 147 The Via Information option MAY be present in DAO messages, and its 148 format is as follows: 150 0 1 2 3 151 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 152 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 153 | Type = 0x0A | Option Length | Path Sequence | Path Lifetime | 154 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 155 | | 156 + + 157 . . 158 . Next-Hop Address . 159 . . 160 + + 161 | | 162 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 164 Figure 1: Eliding the RPLInstanceID 166 Option Type: 0x0A (to be confirmed by IANA) 168 Option Length: Variable, depending on whether or not Parent Address 169 is present. 171 Path Sequence: 8-bit unsigned integer. When a RPL Target option is 172 issued by the root of the DODAG (i.e. in a DAO message), that 173 root sets the Path Sequence and increments the Path Sequence 174 each time it issues a RPL Target option with updated 175 information. The indicated sequence deprecates any state for a 176 given Target that was learned from a previous sequence and adds 177 to any state that was learned for that sequence. 179 Path Lifetime: 8-bit unsigned integer. The length of time in 180 Lifetime Units (obtained from the Configuration option) that 181 the prefix is valid for route determination. The period starts 182 when a new Path Sequence is seen. A value of all one bits 183 (0xFF) represents infinity. A value of all zero bits (0x00) 184 indicates a loss of reachability. A DAO message that contains 185 a Via Information option with a Path Lifetime of 0x00 for a 186 Target is referred as a No-Path (for that Target) in this 187 document. 189 Next-Hop Address: 8 or 16 bytes. IPv6 Address of the next hop 190 towards the destination(s) indicated in the target option that 191 immediately precede the VIO. The /64 prefix can be elided if 192 it is the same as that of (all of) the target(s). In that 193 case, the Next-Hop Address is expressed as the 8-bytes suffix 194 only, otherwise it is expressed as 16 bytes. 196 4. Loose Source Routing in Non-storing Mode 198 A classical RPL implementation in a very constrained LLN uses the 199 non-storing mode of operation whereby a RPL node indicates a parent- 200 child relationship to the root, using a Destination Advertisement 201 Object (DAO) that is unicast from the node directly to the root, and 202 the root builds a path to a destination down the DODAG by 203 concatenating this information. 205 ------+--------- 206 | Internet 207 | 208 +-----+ 209 | | Border Router 210 | | (RPL Root) 211 +-----+ ^ | | 212 | | DAO | ACK | 213 o o o o | | | Strict 214 o o o o o o o o o | | | Source 215 o o o o o o o o o o | | | Route 216 o o o o o o o o o | | | 217 o o o o o o o o | v v 218 o o o o 219 LLN 221 Figure 2: RPL non-storing operation 223 Nodes are not expected to store downward routing state via their 224 children, and the routing operates in strict source routing mode as 225 detailed in An IPv6 Routing Header for Source Routes with RPL 226 [RFC6554] 228 This draft proposes an addition whereby the root projects a route 229 through an extended DAO to an arbitrary node down the DODAG, 230 indicating a child or a direct sequence of children via which a 231 certain destination (target) may be reached. The root is expected to 232 use the mechanism optimally and with required parsimony to fit within 233 the device resources, but how the root figures the amount of 234 resources that are available is out of scope. 236 ------+--------- 237 | Internet 238 | 239 +-----+ 240 | | Border Router 241 | | (RPL Root) 242 +-----+ | ^ | 243 | | DAO | ACK | 244 o o o o | | | Loose 245 o o o o o o o o o | ^ | Source 246 o o o o o o o o o o | | DAO | Route 247 o o o o o o o o o | ^ | 248 o o o o o o o o v | DAO v 249 o o o o 250 LLN 252 Figure 2: Non-Storing with Projected routes 254 When a RPL domain operates in non-storing Mode of Operation (NS-MOP), 255 only the root possesses routing information about the whole network. 256 A packet that is generated within the domain first reaches the root, 257 which can then apply a source routing information to reach the 258 destination. Similarly, a packet coming from the outside of the 259 domain for a destination that is expected to be in a RPL domain 260 reaches the root. 262 In NS-MOP, the root, or some associated centralized computation 263 engine, can thus determine the amount of packets that reach a 264 destination in the RPL domain, and thus the amount of energy and 265 bandwidth that is wasted for transmission, between itself and the 266 destination, as well as the risk of fragmentation, any potential 267 delays because of a paths longer than necessary (shorter paths exist 268 that would not traverse the root). 270 Additionally, the DAG root knows the whole DAG topology, so when the 271 source of a packet is also in the RPL domain, the root can determine 272 the common parent that would have been used in storing mode, and thus 273 the list of nodes in the path between the common parent and the 274 destination. For instance in the below diagram, if the source is 41 275 and the destination 52, the common parent is the node 22. 277 ------+--------- 278 | Internet 279 | 280 +-----+ 281 | | Border Router 282 | | (RPL Root) 283 +-----+ 284 | \ \____ 285 / \ \ 286 o 11 o 12 o 13 287 / | / \ 288 o 22 o 23 o 24 o 25 289 / \ | \ \ 290 o 31 o 32 o o o 35 291 / / | \ | \ 292 o 41 o 42 o o o 45 o 46 293 | | | | \ | 294 o 51 o 52 o 53 o o 55 o 56 295 LLN 297 Figure 3: Non-Storing with Projected routes 299 With this draft, the root can install routing states along a segment 300 that is either itself to the destination, or from one or more common 301 parents for a particular source/destination pair towards that 302 destination (in our example, this would be the segment made of nodes 303 22, 32, 42). 305 The draft expects that the root has enough information about the 306 capability for each node to store a number of routes, which can be 307 discovered for instance using a Network Management System (NMS) and/ 308 or the RPL routing extensions specified in Routing for Path 309 Calculation in LLNs [RFC6551]. Based on that information, the root 310 computes which segment should be routed and which relevant state 311 should be installed in which nodes. The algorithm is out of scope 312 but it is envisaged that the root could compute the ratio between the 313 optimal path (existing path not traversing the root, and the current 314 path), the application SLA for specific flows that could benefit from 315 shorter paths, the energy wasted in the network, local congestion on 316 various links that would benefit from having flows routed along other 317 paths. 319 This draft introduces a new mode of operation for loose source 320 routing in the LLN, the Non-Storing with Projected routes MOP. With 321 this new MOP, the root sends a unicast DAO message to the last node 322 of the routing segment that must be installed. The DAO message 323 contains the ordered list of hops along the segment as a list of Via 324 Information options that are preceded by one or more RPL Target 325 options to which they relate. Each Via Information option contains a 326 lifetime for which state is to be maintained. 328 The root sends the DAO directly to the last node in the segment, 329 which is expected to be able to route to the targets on its own. 331 The last node in the segment may have another information to reach 332 the target(s), such as a connected route or an already installed 333 projected route. If it does not have such a route then the node 334 should lookup the address on the relevant interfaces. If one of the 335 targets cannot be located, the node MUST answer to the root with a 336 negative DAO-ACK listing the target(s) that could not be located 337 (suggested status 10), and continue the process for those targets 338 that could be located if any. 340 For the targets that could be located, last node in the segment 341 generates a DAO to its loose predecessor in the segment as indicated 342 in the list of Via Information options. 344 The node strips the last Via Information option which corresponds to 345 self, and uses it as source address for the DAO to the predecessor. 346 The address of the predecessor to be used as destination for the DAO 347 message is found in the now last Via Information option. The 348 predecessor is expected to have a route to the address used as 349 source, either connected, installed previously as another DAO, or 350 from other means. 352 The predecessor is expected to have a route to the address used as 353 source and that is his successor. If it does not and cannot locate 354 the successor, the predecessor node MUST answer to the root with a 355 negative DAO-ACK indicating the successor that could not be located. 356 The DAO-ACK contains the list of targets that could not be routed to 357 (suggested status 11). 359 If the predecessor can route to the successor node, then it installs 360 a route to the targets via the successor. If that route is not 361 connected then a recursive lookup will take place to reach the 362 target(s). From there, the node strips the last Via Information 363 option and either answers to the root with a positive DAO-ACK that 364 contains the list of targets that could be routed to, or propagates 365 the DAO to its own predecessor. 367 A NULL lifetime in the Via Information option along the segment is 368 used to clean up the state. 370 In the example below, say that there is a lot of traffic to nodes 55 371 and 56 and the root decides to reduce the size of routing headers to 372 those destinations. The root can first send a DAO to node 45 373 indicating target 55 and a Via segment (35, 45), as well as another 374 DAO to node 46 indicating target 56 and a Via segment (35, 46). This 375 will save one entry in the routing header on both sides. The root 376 may then send a DAO to node 35 indicating targets 55 and 56 a Via 377 segment (13, 24, 35) to fully optimize that path. 379 Alternatively, the root may send a DAO to node 45 indicating target 380 55 and a Via segment (13, 24, 35, 45) and then a DAO to node 46 381 indicating target 56 and a Via segment (13, 24, 35, 46), indicating 382 the same DAO Sequence. 384 5. Centralized Computation of Optimized Peer-to-Peer Routes 386 With the initial specifications of RPL [RFC6550], the P2P path from a 387 source to a destination is often stretched, as illustrated in 388 [RFC6550]: 390 - in non-storing mode, all packets routed within the DODAG flow 391 all the way up to the root of the DODAG. If the destination is in 392 the same DODAG, the root must encapsulate the packet to place a 393 Routing Header that has the strict source route information down 394 the DODAG to the destination. This will be the case even if the 395 destination is relatively close to the source and the root is 396 relatively far off. 398 - in storing mode, unless the destination is a child of the 399 source, the packets will follow the default route up the DODAG as 400 well. If the destination is in the same DODAG, they will 401 eventually reach a common parent that has a DAO route to the 402 destination; at worse, the common parent may also be the root. 403 From that common parent, the packet will follow a path down the 404 DODAG that is optimized for the Objective Function that was used 405 to build the DODAG. 407 It results that it is often beneficial to enable additional P2P 408 routes, either if the RPL route present a stretch from shortest path, 409 or if the new route is engineered with a different objective. 411 ------+--------- 412 | Internet 413 | 414 +-----+ 415 | | Border Router 416 | | (RPL Root) 417 +-----+ 418 X 419 ^ v o o 420 ^ o o v o o o o o 421 ^ o o o v o o o o o 422 ^ o o v o o o o o 423 S o o o D o o o 424 o o o o 425 LLN 427 Figure 4: Routing Stretch 429 For that reason, earlier work at the IETF introduced the Reactive 430 Discovery of Point-to-Point Routes in Low Power and Lossy Networks 431 [RFC6997], which specifies a distributed method for establishing 432 optimized P2P routes. This draft proposes an alternate based on a 433 centralized route computation. 435 It must be noted that RPL has a concept of instance but does not have 436 a concept of an administrative distance, which exists in certain 437 proprietary implementations to sort out conflicts between multiple 438 sources. This draft conforms the instance model as follows: 440 - if the PCE needs to influence a particular instance to add 441 better routes in conformance with the routing objectives in that 442 instance, it may do so. When the PCE modifies an existing 443 instance then the added routes must not create a loop in that 444 instance. This is achieved by always preferring a route obtained 445 from the PCE over a route that is learned via RPL. 447 - If the PCE installs a more specific (Traffic Engineering) route 448 between a particular pair of nodes then it should use a Local 449 Instance from the ingress node of that path. Only packets 450 associated with that instance will be routed along that path. 452 In all cases, the path is indicated by VIA options, and the flow is 453 similar to the flow used to obtain loose source routing. 455 The root sends the DAO with the target option and the Via Option to 456 the lest router in the path; the last router removes the last Via 457 Option and passes the DAO to the previous hop. 459 ------+--------- 460 | Internet 461 | 462 +-----+ 463 | | Border Router 464 | | (RPL Root) 465 +-----+ 466 | Projected DAO message to C 467 o | o o 468 o o o | o o o o o 469 o o o | o o o o o o 470 o o V o o o o o o 471 S A B C D o o o 472 o o o o 473 LLN 475 Figure 5: Projected DAO from root 477 The process recurses till the destination which sends a DAO-ACK to 478 the root. In the example above, for target D, the list of via 479 options is S, A, B and C. The projected DAO is sent by the root to 481 ------+--------- 482 | Internet 483 | 484 +-----+ 485 | | Border Router 486 | | (RPL Root) 487 +-----+ 488 ^ Projected DAO-ACK from S 489 / o o o 490 / o o o o o o o 491 | o o o o o o o o o 492 | o o o o o o o o 493 S A B C D o o o 494 o o o o 495 LLN 497 Figure 6: Projected DAO-ACK to root 499 The process recurses till the destination which sends a DAO-ACK to 500 the root. In the example above, for target D, the list of via 501 options is S, A, B and C. The projected DAO is sent by the root to 502 ------+--------- 503 | Internet 504 | 505 +-----+ 506 | | Border Router 507 | | (RPL Root) 508 +-----+ 509 | 510 o o o o 511 o o o o o o o o o 512 o o o o o o o o o o 513 o o o o o o o o o 514 S>>A>>>B>>C>>>D o o o 515 o o o o 516 LLN 518 Figure 7: Optimized Projected Route 520 6. Security Considerations 522 This draft uses messages that are already present in [RFC6550] with 523 optional secured versions. The same secured versions may be used 524 with this draft, and whatever security is deployed for a given 525 network also applies to the flows in this draft. 527 7. IANA Considerations 529 This document updates the IANA registry for the Mode of Operation 530 (MOP) 532 4: Non-Storing with Projected routes [this] 534 This document updates IANA registry for the RPL Control Message 535 Options 537 0x0A: Via descriptor [this] 539 8. Acknowledgments 541 The authors wish to acknowledge JP Vasseur and Patrick Wetterwald for 542 their contributions to the ideas developed here. 544 9. References 545 9.1. Normative References 547 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 548 Requirement Levels", BCP 14, RFC 2119, 549 DOI 10.17487/RFC2119, March 1997, 550 . 552 [RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J., 553 Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, 554 JP., and R. Alexander, "RPL: IPv6 Routing Protocol for 555 Low-Power and Lossy Networks", RFC 6550, 556 DOI 10.17487/RFC6550, March 2012, 557 . 559 [RFC6551] Vasseur, JP., Ed., Kim, M., Ed., Pister, K., Dejean, N., 560 and D. Barthel, "Routing Metrics Used for Path Calculation 561 in Low-Power and Lossy Networks", RFC 6551, 562 DOI 10.17487/RFC6551, March 2012, 563 . 565 [RFC6554] Hui, J., Vasseur, JP., Culler, D., and V. Manral, "An IPv6 566 Routing Header for Source Routes with the Routing Protocol 567 for Low-Power and Lossy Networks (RPL)", RFC 6554, 568 DOI 10.17487/RFC6554, March 2012, 569 . 571 [RFC7102] Vasseur, JP., "Terms Used in Routing for Low-Power and 572 Lossy Networks", RFC 7102, DOI 10.17487/RFC7102, January 573 2014, . 575 9.2. Informative References 577 [I-D.finn-detnet-architecture] 578 Finn, N., Thubert, P., and M. Teener, "Deterministic 579 Networking Architecture", draft-finn-detnet- 580 architecture-02 (work in progress), November 2015. 582 [I-D.ietf-6tisch-architecture] 583 Thubert, P., "An Architecture for IPv6 over the TSCH mode 584 of IEEE 802.15.4", draft-ietf-6tisch-architecture-08 (work 585 in progress), May 2015. 587 [PCE] IETF, "Path Computation Element", 588 . 590 [RFC6997] Goyal, M., Ed., Baccelli, E., Philipp, M., Brandt, A., and 591 J. Martocci, "Reactive Discovery of Point-to-Point Routes 592 in Low-Power and Lossy Networks", RFC 6997, 593 DOI 10.17487/RFC6997, August 2013, 594 . 596 Authors' Addresses 598 Pascal Thubert (editor) 599 Cisco Systems 600 Village d'Entreprises Green Side 601 400, Avenue de Roumanille 602 Batiment T3 603 Biot - Sophia Antipolis 06410 604 FRANCE 606 Phone: +33 4 97 23 26 34 607 Email: pthubert@cisco.com 609 James Pylakutty 610 Cisco Systems 611 Cessna Business Park 612 Kadubeesanahalli 613 Marathalli ORR 614 Bangalore, Karnataka 560087 615 INDIA 617 Phone: +91 80 4426 4140 618 Email: mundenma@cisco.com