idnits 2.17.1 draft-thubert-roll-dao-projection-00.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 (June 29, 2015) is 3217 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-01 == 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: December 31, 2015 June 29, 2015 7 Root initiated routing state in RPL 8 draft-thubert-roll-dao-projection-00 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 December 31, 2015. 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 . . . . . . . . . . . . . . . . . . . . . . . . . 4 52 3. New RPL Control Message Options . . . . . . . . . . . . . . . 4 53 3.1. Via Information . . . . . . . . . . . . . . . . . . . . . 5 54 4. Operation . . . . . . . . . . . . . . . . . . . . . . . . . . 6 55 5. Security Considerations . . . . . . . . . . . . . . . . . . . 9 56 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 57 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 9 58 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 59 8.1. Normative References . . . . . . . . . . . . . . . . . . 9 60 8.2. Informative References . . . . . . . . . . . . . . . . . 10 61 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 63 1. Introduction 65 The Routing Protocol for Low Power and Lossy Networks [RFC6550] 66 (LLN)(RPL) specification defines a generic Distance Vector protocol 67 that is indeed designed for very low energy consumption and adapted 68 to a variety of LLNs. RPL forms Destination Oriented Directed 69 Acyclic Graphs (DODAGs) which root often acts as the Border Router to 70 connect the RPL domain to the Internet. The root is responsible to 71 select the RPL Instance that is used to forward a packet coming from 72 the Internet into the RPL domain and set the related RPL information 73 in the packets. 75 A classical RPL implementation in a very constrained LLN uses the 76 non-storing mode of operation whereby a RPL node indicates a parent- 77 child relationship to the root, using a Destination Advertisement 78 Object (DAO) that is unicast from the node directly to the root, and 79 the root builds a path to a destination down the DODAG by 80 concatenating this information. 82 ------+--------- 83 | Internet 84 | 85 +-----+ 86 | | Border Router 87 | | (RPL Root) 88 +-----+ ^ | | 89 | | DAO | ACK | 90 o o o o | | | Strict 91 o o o o o o o o o | | | Source 92 o o o o o o o o o o | | | Route 93 o o o o o o o o o | | | 94 o o o o o o o o | v v 95 o o o o 96 LLN 98 Figure 1: RPL non-storing operation 100 Nodes are not expected to store downward routing state via their 101 children, and the routing operates in strict source routing mode as 102 detailed in An IPv6 Routing Header for Source Routes with RPL 103 [RFC6554] 105 The non-storing mode of operation (MOP) is largely utilized because 106 networks can get very large and the amount of memory in nodes close 107 to the root may become prohibitive in storing mode. But as a network 108 gets deep, the size of the source routing header that the root must 109 add to all the downward packets may also become an issue as well. In 110 some cases, RPL network form long lines and a limited number of well- 111 targeted routes would enable a loose source routing operation and 112 save packet size, energy, and eventually fragmentation which is 113 highly detrimental to the LLN operation. 115 This draft proposes an addition whereby the root projects a route 116 through an extended DAO to an arbitrary node down the DODAG, 117 indicating a child or a direct sequence of children via which a 118 certain destination (target) may be reached. The root is expected to 119 use the mechanism optimally and with required parsimony to fit within 120 the device resources, but how the root figures the amount of 121 resources that are available is out of scope. 123 ------+--------- 124 | Internet 125 | 126 +-----+ 127 | | Border Router 128 | | (RPL Root) 129 +-----+ | ^ | 130 | | DAO | ACK | 131 o o o o | | | Loose 132 o o o o o o o o o | ^ | Source 133 o o o o o o o o o o | | DAO | Route 134 o o o o o o o o o | ^ | 135 o o o o o o o o v | DAO v 136 o o o o 137 LLN 139 Figure 2: Non-Storing with Projected routes 141 The 6TiSCH architecture [I-D.ietf-6tisch-architecture] leverages the 142 Deterministic Networking Architecture [I-D.finn-detnet-architecture] 143 as one possible model whereby the device resources and capabilities 144 are exposed to an external entity (a Path Computation Element [PCE]), 145 which installs routing states into the network based on some 146 objective functions that reside in that external entity. 148 Based on non-specified heuristics of usage, path length, and 149 knowledge of device capacity, this draft enables a RPL root to 150 install and maintain a local and temporary storing mode path within 151 the RPL domain, along a selected set of nodes and for a selected 152 duration, thus advantageously modifying the mode of operation of RPL 153 in non-storing mode. 155 2. Terminology 157 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 158 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 159 document are to be interpreted as described in [RFC2119]. 161 The Terminology used in this document is consistent with and 162 incorporates that described in `Terminology in Low power And Lossy 163 Networks' [RFC7102] and [RFC6550]. 165 3. New RPL Control Message Options 167 Section 6.7 of [RFC6550] specifies Control Message Options (CMO) to 168 be placed in RPL messages such as the DAO message. The RPL Target 169 option indicates a node to be reached and the Transit Information 170 Option specifies a parent that can be used to reach that node. 172 This specification introduces a new Control Message Option, the Via 173 Information option. One or more Via Information options MUST be 174 preceded by one or more RPL Target options, and the Via options 175 indicate an ordered sequence of hops to reach the target(s), 176 presented in the same order as they would in a routing header. 178 3.1. Via Information 180 The Via Information option MAY be present in DAO messages, and its 181 format is as follows: 183 0 1 2 3 184 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 185 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 186 | Type = 0x0A | Option Length | Path Sequence | Path Lifetime | 187 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 188 | | 189 + + 190 . . 191 . Child Address . 192 . . 193 + + 194 | | 195 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 197 Figure 1: Eliding the RPLInstanceID 199 Option Type: 0x0A (to be confirmed by IANA) 201 Option Length: Variable, depending on whether or not Parent Address 202 is present. 204 Path Sequence: 8-bit unsigned integer. When a RPL Target option is 205 issued by the root of the DODAG (i.e. in a DAO message), that 206 root sets the Path Sequence and increments the Path Sequence 207 each time it issues a RPL Target option with updated 208 information. The indicated sequence deprecates any state for a 209 given Target that was learned from a previous sequence and adds 210 to any state that was learned for that sequence. 212 Path Lifetime: 8-bit unsigned integer. The length of time in 213 Lifetime Units (obtained from the Configuration option) that 214 the prefix is valid for route determination. The period starts 215 when a new Path Sequence is seen. A value of all one bits 216 (0xFF) represents infinity. A value of all zero bits (0x00) 217 indicates a loss of reachability. A DAO message that contains 218 a Via Information option with a Path Lifetime of 0x00 for a 219 Target is referred as a No-Path (for that Target) in this 220 document. 222 Child Address: 8 or 16 bytes. IPv6 Address of the child of the node 223 that is a next hop towards the destination(s) indicated in the 224 target option. If the /64 prefix is the same as that of (all 225 of) the target(s) then the prefix can be elided and the address 226 is expressed as the 8-bytes suffix only. 228 4. Operation 230 When a RPL domain operates in non-storing Mode of Operation (NS-MOP), 231 only the root possesses routing information about the whole network. 232 A packet that is generated within the domain first reaches the root, 233 which can then apply a source routing information to reach the 234 destination. Similarly, a packet coming from the outside of the 235 domain for a destination that is expected to be in a RPL domain 236 reaches the root. 238 In NS-MOP, the root, or some associated centralized computation 239 engine, can thus determine the amount of packets that reach a 240 destination in the RPL domain, and thus the amount of energy and 241 bandwidth that is wasted for transmission, between itself and the 242 destination, as well as the risk of fragmentation, any potential 243 delays because of a paths longer than necessary (shorter paths exist 244 that would not traverse the root). 246 Additionally, the DAG root knows the whole DAG topology, so when the 247 source of a packet is also in the RPL domain, the root can determine 248 the common parent that would have been used in storing mode, and thus 249 the list of nodes in the path between the common parent and the 250 destination. For instance in the below diagram, if the source is 41 251 and the destination 52, the common parent is the node 22. 253 ------+--------- 254 | Internet 255 | 256 +-----+ 257 | | Border Router 258 | | (RPL Root) 259 +-----+ 260 | \ \____ 261 / \ \ 262 o 11 o 12 o 13 263 / | / \ 264 o 22 o 23 o 24 o 25 265 / \ | \ \ 266 o 31 o 32 o o o 35 267 / / | \ | \ 268 o 41 o 42 o o o 45 o 46 269 | | | | \ | 270 o 51 o 52 o 53 o o 55 o 56 271 LLN 273 Figure 2: Non-Storing with Projected routes 275 With this draft, the root can install routing states along a segment 276 that is either itself to the destination, or from one or more common 277 parents for a particular source/destination pair towards that 278 destination (in our example, this would be the segment made of nodes 279 22, 32, 42). 281 The draft expects that the root has enough information about the 282 capability for each node to store a number of routes, which can be 283 discovered for instance using a Network Management System (NMS) and/ 284 or the RPL routing extensions specified in Routing for Path 285 Calculation in LLNs [RFC6551]. Based on that information, the root 286 computes which segment should be routed and which relevant state 287 should be installed in which nodes. The algorithm is out of scope 288 but it is envisaged that the root could compute the ratio between the 289 optimal path (existing path not traversing the root, and the current 290 path), the application SLA for specific flows that could benefit from 291 shorter paths, the energy wasted in the network, local congestion on 292 various links that would benefit from having flows routed along other 293 paths. 295 This draft introduces a new mode of operation for loose source 296 routing in the LLN, the Non-Storing with Projected routes MOP. With 297 this new MOP, the root sends a unicast DAO message to the last node 298 of the routing segment that must be installed. The DAO message 299 contains the ordered list of hops along the segment as a list of Via 300 Information options that are preceded by one or more RPL Target 301 options to which they relate. Each Via Information option contains a 302 lifetime for which state is to be maintained. 304 The root sends the DAO directly to the last node in the segment, 305 which is expected to be able to route to the targets on its own. 307 The last node in the segment may have another information to reach 308 the target(s), such as a connected route or an already installed 309 projected route. If it does not have such a route then the node 310 should lookup the address on the relevant interfaces. If one of the 311 targets cannot be located, the node MUST answer to the root with a 312 negative DAO-ACK listing the target(s) that could not be located 313 (suggested status 10), and continue the process for those targets 314 that could be located if any. 316 For the targets that could be located, last node in the segment 317 generates a DAO to its loose predecessor in the segment as indicated 318 in the list of Via Information options. 320 The node strips the last Via Information option which corresponds to 321 self, and uses it as source address for the DAO to the predecessor. 322 The address of the predecessor to be used as destination for the DAO 323 message is found in the now last Via Information option. The 324 predecessor is expected to have a route to the address used as 325 source, either connected, installed previously as another DAO, or 326 from other means. 328 The predecessor is expected to have a route to the address used as 329 source and that is his successor. If it does not and cannot locate 330 the successor, the predecessor node MUST answer to the root with a 331 negative DAO-ACK indicating the successor that could not be located. 332 The DAO-ACK contains the list of targets that could not be routed to 333 (suggested status 11). 335 If the predecessor can route to the successor node, then it installs 336 a route to the targets via the successor. If that route is not 337 connected then a recursive lookup will take place to reach the 338 target(s). From there, the node strips the last Via Information 339 option and either answers to the root with a positive DAO-ACK that 340 contains the list of targets that could be routed to, or propagates 341 the DAO to its own predecessor. 343 A NULL lifetime in the Via Information option along the segment is 344 used to clean up the state. 346 In the example below, say that there is a lot of traffic to nodes 55 347 and 56 and the root decides to reduce the size of routing headers to 348 those destinations. The root can first send a DAO to node 45 349 indicating target 55 and a Via segment (35, 45), as well as another 350 DAO to node 46 indicating target 56 and a Via segment (35, 46). This 351 will save one entry in the routing header on both sides. The root 352 may then send a DAO to node 35 indicating targets 55 and 56 a Via 353 segment (13, 24, 35) to fully optimize that path. 355 Alternatively, the root may send a DAO to node 45 indicating target 356 55 and a Via segment (13, 24, 35, 45) and then a DAO to node 46 357 indicating target 56 and a Via segment (13, 24, 35, 46), indicating 358 the same DAO Sequence. 360 5. Security Considerations 362 This draft uses messages that are already present in [RFC6550] with 363 optional secured versions. The same secured versions may be used 364 with this draft, and whatever security is deployed for a given 365 network also applies to the flows in this draft. 367 6. IANA Considerations 369 This document updates the IANA registry for the Mode of Operation 370 (MOP) 372 4: Non-Storing with Projected routes [this] 374 This document updates IANA registry for the RPL Control Message 375 Options 377 0x0A: Via descriptor [this] 379 7. Acknowledgements 381 The authors wish to acknowledge JP Vasseur and Patrick Wetterwald for 382 their contributions to the ideas developed here. 384 8. References 386 8.1. Normative References 388 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 389 Requirement Levels", BCP 14, RFC 2119, March 1997. 391 [RFC6550] Winter, T., Thubert, P., Brandt, A., Hui, J., Kelsey, R., 392 Levis, P., Pister, K., Struik, R., Vasseur, JP., and R. 393 Alexander, "RPL: IPv6 Routing Protocol for Low-Power and 394 Lossy Networks", RFC 6550, March 2012. 396 [RFC6551] Vasseur, JP., Kim, M., Pister, K., Dejean, N., and D. 397 Barthel, "Routing Metrics Used for Path Calculation in 398 Low-Power and Lossy Networks", RFC 6551, March 2012. 400 [RFC6554] Hui, J., Vasseur, JP., Culler, D., and V. Manral, "An IPv6 401 Routing Header for Source Routes with the Routing Protocol 402 for Low-Power and Lossy Networks (RPL)", RFC 6554, March 403 2012. 405 [RFC7102] Vasseur, JP., "Terms Used in Routing for Low-Power and 406 Lossy Networks", RFC 7102, January 2014. 408 8.2. Informative References 410 [I-D.finn-detnet-architecture] 411 Finn, N., Thubert, P., and M. Teener, "Deterministic 412 Networking Architecture", draft-finn-detnet- 413 architecture-01 (work in progress), March 2015. 415 [I-D.ietf-6tisch-architecture] 416 Thubert, P., "An Architecture for IPv6 over the TSCH mode 417 of IEEE 802.15.4", draft-ietf-6tisch-architecture-08 (work 418 in progress), May 2015. 420 [PCE] IETF, "Path Computation Element", 421 . 423 Authors' Addresses 425 Pascal Thubert (editor) 426 Cisco Systems 427 Village d'Entreprises Green Side 428 400, Avenue de Roumanille 429 Batiment T3 430 Biot - Sophia Antipolis 06410 431 FRANCE 433 Phone: +33 4 97 23 26 34 434 Email: pthubert@cisco.com 435 James Pylakutty 436 Cisco Systems 437 Cessna Business Park 438 Kadubeesanahalli 439 Marathalli ORR 440 Bangalore, Karnataka 560087 441 INDIA 443 Phone: +91 80 4426 4140 444 Email: mundenma@cisco.com