idnits 2.17.1 draft-clausen-lln-rpl-experiences-07.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 : ---------------------------------------------------------------------------- ** There is 1 instance of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (January 29, 2014) is 3730 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Obsolete informational reference (is this intentional?): RFC 2460 (Obsoleted by RFC 8200) Summary: 1 error (**), 0 flaws (~~), 1 warning (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group T. Clausen 3 Internet-Draft A. Colin de Verdiere 4 Intended status: Informational J. Yi 5 Expires: August 2, 2014 LIX, Ecole Polytechnique 6 U. Herberg 7 Fujitsu Laboratories of America 8 Y. Igarashi 9 Hitachi, Ltd., Yokohama Research 10 Laboratory 11 January 29, 2014 13 Observations of RPL: IPv6 Routing Protocol for Low power and Lossy 14 Networks 15 draft-clausen-lln-rpl-experiences-07 17 Abstract 19 With RPL - the "IPv6 Routing Protocol for Low-power Lossy Networks" - 20 having been published as a Proposed Standard after a ~2-year 21 development cycle, this document presents an evaluation of the 22 resulting protocol, of its applicability, and of its limits. The 23 documents presents a selection of observations of the protocol 24 characteristics, exposes experiences acquired when producing various 25 prototype implementations of RPL, and presents results obtained from 26 testing this protocol - by way of network simulations, in network 27 testbeds and in deployments. The document aims at providing a better 28 understanding of possible limits of RPL, notably the possible 29 directions that further protocol developments should explore, in 30 order to address these. 32 Status of this Memo 34 This Internet-Draft is submitted in full conformance with the 35 provisions of BCP 78 and BCP 79. 37 Internet-Drafts are working documents of the Internet Engineering 38 Task Force (IETF). Note that other groups may also distribute 39 working documents as Internet-Drafts. The list of current Internet- 40 Drafts is at http://datatracker.ietf.org/drafts/current/. 42 Internet-Drafts are draft documents valid for a maximum of six months 43 and may be updated, replaced, or obsoleted by other documents at any 44 time. It is inappropriate to use Internet-Drafts as reference 45 material or to cite them other than as "work in progress." 47 This Internet-Draft will expire on August 2, 2014. 49 Copyright Notice 51 Copyright (c) 2014 IETF Trust and the persons identified as the 52 document authors. All rights reserved. 54 This document is subject to BCP 78 and the IETF Trust's Legal 55 Provisions Relating to IETF Documents 56 (http://trustee.ietf.org/license-info) in effect on the date of 57 publication of this document. Please review these documents 58 carefully, as they describe your rights and restrictions with respect 59 to this document. Code Components extracted from this document must 60 include Simplified BSD License text as described in Section 4.e of 61 the Trust Legal Provisions and are provided without warranty as 62 described in the Simplified BSD License. 64 Table of Contents 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 67 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 68 3. RPL Overview . . . . . . . . . . . . . . . . . . . . . . . . . 5 69 3.1. RPL Message Emission Timing - Trickle Timers . . . . . . . 7 70 4. Requirement Of DODAG Root . . . . . . . . . . . . . . . . . . 8 71 4.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 8 72 5. RPL Data Traffic Flows . . . . . . . . . . . . . . . . . . . . 9 73 5.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 10 74 6. Fragmentation Of RPL Control Messages And Data Packet . . . . 12 75 6.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 12 76 7. The DAO Mechanism: Downward and Point-to-Point Routes . . . . 14 77 7.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 14 78 8. Address Aggregation and Summarization . . . . . . . . . . . . 16 79 8.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 17 80 9. Link Bidirectionality Verification . . . . . . . . . . . . . . 18 81 9.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 18 82 10. Neighbor Unreachability Detection For Unidirectional Links . . 19 83 10.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 20 84 11. RPL Implementability and Complexity . . . . . . . . . . . . . 21 85 11.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 22 86 12. Underspecification . . . . . . . . . . . . . . . . . . . . . . 22 87 12.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 22 88 13. Protocol Convergence . . . . . . . . . . . . . . . . . . . . . 23 89 13.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 24 90 13.2. Caveat . . . . . . . . . . . . . . . . . . . . . . . . . . 24 91 14. Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 92 14.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 25 93 15. Security Considerations . . . . . . . . . . . . . . . . . . . 26 94 16. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27 95 17. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 27 96 18. Informative References . . . . . . . . . . . . . . . . . . . . 27 97 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 30 99 1. Introduction 101 RPL - the "Routing Protocol for Low Power and Lossy Networks" 102 [RFC6550] - is a proposal for an IPv6 routing protocol for Low-power 103 Lossy Networks (LLNs), by the ROLL Working Group in the Internet 104 Engineering Task Force (IETF). This routing protocol is intended to 105 be the IPv6 routing protocol for LLNs and sensor networks, applicable 106 in all kinds of deployments and applications of LLNs. 108 The objective of RPL and ROLL is to provide routing in networks which 109 "comprise up to thousands of nodes" [roll-charter], where the 110 majority of the nodes have very constrained resources 111 [I-D.ietf-roll-terminology], and where handling mobility is not an 112 explicit design criteria [RFC5867], [RFC5826], [RFC5673], [RFC5548]. 114 [roll-charter] states that "Typical traffic patterns are not simply 115 unicast flows (e.g. in some cases most if not all traffic can be 116 point to multipoint)", and [I-D.ietf-roll-terminology] further 117 categorizes the supported traffic types into "upward" traffic from 118 sensors to a collection sink or LBR (LLN Border Router) (denoted 119 multipoint-to-point), "downward" traffic from the collection sink or 120 LBR to the sensors (denoted point-to-multipoint) and traffic from 121 "sensor to sensor" (denoted point-to-point traffic), and establishes 122 this terminology for these traffic types. Thus, while the target for 123 RPL and ROLL is to support all of these traffic types, the emphasis 124 among these, according to [roll-charter], appears to be to optimize 125 for multipoint-to-point traffic, while also supporting point-to- 126 multipoint and point-to-point traffic. 128 With experiences obtained since the publication of RPL as [RFC6550], 129 it is opportune to document observations of the protocol, in order to 130 understand which aspects of it work well and which necessitate 131 further investigations. Understanding possible limitations is 132 important to identify issues which may restrict the deployment scope 133 of the protocol and which may need further protocol work or 134 enhancements. 136 The observations made in this document, except for when explicitly 137 noted otherwise, do not depend on any specific implementation or 138 deployment, but can be understood from simply analyzing the protocol 139 specification [RFC6550]. That said, all observations made have been 140 confirmed to also be present in, at least, some deployments or test 141 platforms with RPL, i.e., have been experimentally confirmed. 143 This document is explicitly not an implementation guidebook for RPL. 144 It has as objective to document observations of behaviors of 145 [RFC6550], in the spirit of better understanding the characteristics 146 and limits of the protocol. 148 2. Terminology 150 This document uses the terminology and notation defined in [RFC6550]. 152 Additionally, this document uses terminology from 153 [I-D.ietf-roll-terminology], specifically the terms defined for the 154 traffic types "MP2P" (Multipoint-to-Point), "P2P" (Point To Point) 155 and "P2MP" (Point-to-Multipoint). 157 Finally, this document introduces the following terminology: 159 RPL Router - A device, running the RPL protocol, as specified by 160 [RFC6550]. 162 3. RPL Overview 164 The basic construct in RPL is a "Destination Oriented Directed 165 Acyclic Graph" (DODAG), depicted in Figure 1, with a single RPL 166 Router acting as DODAG Root. The DODAG Root has responsabilities in 167 addition to those of other RPL Routers, including for initiating, 168 configuring, and managing the DODAG, and (in some cases) acting as a 169 central relay for traffic through and between RPL Routers in the LLN. 171 (s) 172 ^ ^ ^ 173 / | \ 174 (a) | (b) 175 ^ (c) ^ 176 / ^ (d) 177 (f) | ^ ^ 178 (e)--/ \ 179 (g) 181 Figure 1: RPL DODAG 183 In an LLN, in which RPL has converged to a stable state, each RPL 184 Router has identified a stable set of parents, each of which is a 185 potential next-hop on a route towards the DODAG Root. One of the 186 parents is selected as preferred parent. Each RPL Router, which is 187 part of a DODAG (i.e., which has selected parents and a preferred 188 parent) will emit DODAG Information Object (DIO) messages, using 189 link-local multicast, indicating its respective rank in the DODAG 190 (i.e., distance to the DODAG Root according to some metric(s), in the 191 simplest form hop-count). Upon having received a (number of such) 192 DIO messages, an RPL Router will calculate its own rank such that it 193 is greater than the rank of each of its parents, select a preferred 194 parent and then itself start emitting DIO messages. 196 DODAG formation thus starts at the DODAG Root (initially, the only 197 RPL Router which is part of a DODAG), and spreads gradually to cover 198 the whole LLN as DIOs are received, parents and preferred parents are 199 selected, and further RPL Routers participate in the DODAG. The 200 DODAG Root also includes, in DIO messages, a DODAG Configuration 201 Object, describing common configuration attributes for all RPL 202 Routers in that network - including their mode of operation, timer 203 characteristics etc. RPL Routers in a DODAG include a verbatim copy 204 of the last received DODAG Configuration Object in their DIO 205 messages, permitting also such configuration parameters propagating 206 through the network. 208 As a Distance Vector protocol, RPL restricts the ability for an RPL 209 Router to change rank. An RPL Router can freely assume a smaller 210 rank than previously advertised (i.e., logically move closer to the 211 DODAG Root) if it discovers a parent advertising a lower rank, and 212 must then disregard all previous parents of ranks higher than the 213 router's new rank. The ability for an RPL Router to assume a greater 214 rank (i.e., logically move farther from the DODAG Root) than 215 previously advertised is restricted in order to avoid count-to- 216 infinity problems. The DODAG Root can trigger "global recalculation" 217 of the DODAG by increasing a sequence number, DODAG version, in DIO 218 messages. 220 The DODAG so constructed is used for installing routes: the 221 "preferred parent" of an RPL Router can serve as a default route 222 towards the DODAG Root, and the DODAG Root can embed in its DIO 223 messages the destination prefixes, included by DIOs generated by RPL 224 Routers through the LLN, to which connectivity is provided by the 225 DODAG Root. Thus, RPL by way of DIO generation provides "upward 226 routes" or "multipoint-to-point routes" from the sensors inside the 227 LLN and towards the DODAG Root (and, possibly, to destinations 228 reachable through the DODAG Root). 230 "Downward routes" are enabled by having sensors issue Destination 231 Advertisement Object (DAO) messages, propagating as unicast via 232 preferred parents towards the DODAG Root. These describe which 233 prefixes belong to, and can be reached via, which RPL Router. In a 234 network, all RPL Routers must operate in either of storing mode or 235 non-storing mode, specified by way of a "Mode of Operation" (MOP) 236 flag in the DODAG Configuration Object from the DODAG Root. Those 237 two modes are non-interoperable, i.e., a mixture of RPL Routers 238 running in different modes is impossible in the same routing domain. 239 Depending on the MOP, DAO messages are forwarded differently towards 240 the DODAG Root: 242 o In "non-storing mode", an RPL Router originates a DAO messages, 243 advertising one or more of its parents, and unicasts these to the 244 DODAG Root. Once the DODAG Root has received DAOs from an RPL 245 Router, and from all RPL Routers on the route between it and the 246 DODAG Root, it can use source routing for reaching advertised 247 destinations inside the LLN. 249 o In "storing mode", each RPL Router on the route between the 250 originator of a DAO and the DODAG Root records a route to the 251 prefixes advertised in the DAO, as well as the next-hop towards 252 these (the RPL Router, from which the DAO was received), then 253 forwards the DAO to its preferred parent. 255 "Point-to-point routes", for communication between devices inside the 256 LLN and where neither of the communicating devices are the DODAG 257 Root, are as default supported by having the source sensor transmit a 258 data packet, via its default route to the DODAG Root (i.e., using the 259 upward routes), which will then, depending on the "Mode of Operation" 260 for the DODAG, either add a source-route to the received data packet 261 for reaching the destination sensor (downward routes in non-storing 262 mode), or simply use hop-by-hop routing (downward routes in storing 263 mode) for forwarding the data packet. In the case of storing mode, 264 if the source and the destination for a point-to-point data packet 265 share a common ancestor other than the DODAG Root, a downward route 266 may be available in an RPL Router (and, thus, used) before the data 267 packet reaches the DODAG Root. 269 3.1. RPL Message Emission Timing - Trickle Timers 271 RPL message generation is timer-based, with the DODAG Root being able 272 to configure back-off of message emission intervals using Trickle 273 [RFC6206]. Trickle, as used in RPL, stipulates that an RPL Router 274 transmits a DIO "every so often" - except if receiving a number of 275 DIOs from neighbor RPL Routers, enabling the RPL Router to determine 276 if its DIO transmission is redundant. 278 When an RPL Router transmits a DIO, there are two possible outcomes: 279 either every neighbor RPL Router that hears the message finds that 280 the information contained is consistent with its own state (i.e., the 281 received DODAG version number corresponds with that which the RPL 282 Router has recorded, and no better rank is advertised than that which 283 is recorded in the parent set) - or, a recipient RPL Router detects 284 that either the sender of the DIO or itself has out-of-date 285 information. If the sender has out-of-date information, then the 286 recipient RPL Router schedules transmission of a DIO to update this 287 information. If the recipient RPL Router has out-of-date 288 information, then it updates based on the information received in the 289 DIO. 291 With Trickle, an RPL Router will schedule emission of a DIO at some 292 time, t, in the future. When receiving a DIO containing information 293 consistent with its own information, the RPL Router will record that 294 "redundant information has been received" by incrementing a 295 redundancy counter, c. At the time t, if c is below some "redundancy 296 threshold", then it transmits its DIO. Otherwise, transmission of a 297 DIO at this time is suppressed, c is reset and a new t is selected to 298 twice as long time in the future - bounded by a pre-configured 299 maximum value for t. If, on the other hand, the RPL Router has 300 received an out-of-date DIO from one of its neighbors, t is reset to 301 a pre-configured minimum value and c is set to zero. In both cases, 302 at the expiration of t, the RPL Router will verify if c is below the 303 "redundancy threshold" and if so transmit - otherwise, increase t and 304 stay quiet. 306 4. Requirement Of DODAG Root 308 As indicated in Section 3, the DODAG Root has both a special 309 responsibility and is subject to special requirements. The DODAG 310 Root is responsible for determining and maintaining the configuration 311 parameters for the DODAG, and for initiating DIO emissions. 313 The DODAG Root is also responsible (in both storing and non-storing 314 mode) for being able to, when downward routes are supported, maintain 315 sufficient topological information to be able to construct routes to 316 all destinations in the network. 318 When operating in non-storing mode, this entails that the DODAG Root 319 is required to have sufficient memory and sufficient computational 320 resources to be able to record a network graph containing all routes 321 from itself and to all destinations and to calculate routes. 323 When operating in storing mode, this entails that the DODAG Root 324 needs enough memory to keep a list of all RPL Routers in the RPL 325 instance, and a next hop for each of those RPL Routers. If 326 aggregation is used, the memory requirements can be reduced in 327 storing mode (see Section 8 for observations about aggregation in 328 RPL). 330 The DODAG Root is also required to have sufficient energy available 331 so as to be able to ensure the relay functions required. This, 332 especially for non-storing mode, where all data packets transit 333 through the DODAG Root. 335 4.1. Observations 337 In a given deployment, select RPL Routers can be provisioned with the 338 required energy, memory and computational resources so as to serve as 339 DODAG Roots, and be administratively configured as such - with the 340 remainder of the RPL Routers in the network being of typically lesser 341 capacity. In storing mode, the DODAG root needs to keep a routing 342 entry for all RPL Routers in the RPL instance. In non-storing mode, 343 the resource requirements on the DODAG Root are likely much higher 344 than in storing mode, as the DODAG Root needs to store a network 345 graph containing complete routes to all destinations in the RPL 346 instance, in order to calculate the routing table (whereas in storing 347 mode, only the next hop for each destination in the RPL instance 348 needs to be stored, and aggregation may be used to further reduce the 349 resource requirements). 351 RPL Routers provisioned with resources to act as DODAG Roots, and 352 administratively configured to act as such, represent a single point 353 of failure in the network. As the memory requirements for the DODAG 354 Root and for other RPL Routers are substantially different, unless 355 all RPL Routers are provisioned with resources (memory, energy, ...) 356 to act as DODAG Roots, effectively if the designated DODAG Root 357 fails, the network fails and RPL is unable to operate. Even if 358 electing another RPL Router as temporary DODAG Root (e.g., for 359 forming a "Floating" DODAG) for providing internal connectivity 360 between RPL Routers, this RPL Router may not have the necessary 361 resources to satisfy this role as (temporary) DODAG Root. 363 Thus, although in principle RPL provides, by way of "Floating 364 DODAGs", protocol mechanisms for establishing a DODAG for providing 365 internal connectivity even in case of failure of the administratively 366 provisioned DODAG Root, all (or at least a large number) of the RPL 367 routers need to have resources to act as roots to support floating 368 DODAG, especially in non-storing mode. 370 Another possible LLN scenario is that only internal point-to-point 371 connectivity is sought, and no RPL Router has a more "central" role 372 than any other - a self-organizing LLN. In those cases, it would be 373 hard to specify such "super-device" as DODAG root, and can result in 374 non-optimal routes. 376 5. RPL Data Traffic Flows 378 RPL makes a-priori assumptions of data traffic types, and explicitly 379 defines three such [I-D.ietf-roll-terminology] traffic types: sensor- 380 to-root data traffic (multipoint-to-point) is predominant, root-to- 381 sensor data traffic (point-to-multipoint) is rare and sensor-to- 382 sensor (point-to-point) data traffic is extremely rare. While not 383 specifically called out thus in [RFC6550], the resulting protocol 384 design, however, reflects these assumptions in that the mechanism 385 constructing multipoint-to-point routes is efficient in terms of 386 control traffic generated and state required, point-to-multipoint 387 route construction much less so - and point-to-point routes subject 388 to potentially significant route stretch (routes going through the 389 DODAG Root in non-storing mode) and over-the-wire overhead from using 390 source routing (from the DODAG Root to the destination) (see 391 Section 7) - or, in case of storing mode, considerable memory 392 requirements in all LLN routers inside the network (see Section 7). 394 An RPL Router selects from among its parents a "preferred parent", to 395 serve as a default route towards the DODAG Root (and to prefixes 396 advertised by the DODAG Root). Thus, RPL provides "upward routes" or 397 "multipoint-to-point routes" from the RPL Routers below the DODAG 398 Root and towards the DODAG Root. 400 An RPL Router which wishes to act as a destination for data traffic 401 ("downward routes" or "point-to-multipoint") issues DAOs upwards in 402 the DODAG towards the DODAG Root, describing which prefixes belong 403 to, and can be reached via, that RPL Router. 405 Point-to-Point routes between RPL Routers below the DODAG Root are 406 supported by having the source RPL Router transmit, via its default 407 route, data traffic towards the DODAG Root. In non-storing mode, the 408 data traffic will reach the DODAG Root, which will reflect the data 409 traffic downward towards the destination RPL Router, adding a strict 410 source routing header indicating the precise route for the data 411 traffic to reach the intended destination RPL Router. In storing 412 mode, the source and the destination may possibly (although, may also 413 not) have a common ancestor other than the DODAG Root, which may 414 provide a downward route to the destination before data traffic 415 reaching the DODAG Root. 417 5.1. Observations 419 RPL is suited for networks where sensor-to-root traffic is dominant, 420 by distribution of DIO messages and building of a collection tree. 421 The one way traffic from the sensor to the root can be forwarded 422 through the preferred parent. 424 However, the data traffic characteristics, assumed by RPL, do not 425 represent a universal distribution of traffic types in LLNs: 427 o There are scenarios where sensor-to-sensor traffic is a more 428 common occurrence, documented, e.g., in [RFC5867] ("Building 429 Automation Routing Requirements in Low Power and Lossy Networks"). 431 o There are scenarios, where all traffic is bi-directional, e.g., in 432 case sensor devices in the LLN are, in majority, "actively read": 433 a request is issued by the DODAG Root to a specific sensor, and 434 the sensor value is expected returned. In fact, unless all 435 traffic in the LLN is unidirectional, without acknowledgements 436 (e.g., as in UDP), and no control messages (e.g., for service 437 discovery) or other data packets are sent from the DODAG Root to 438 the RPL Routers, traffic will be bi-directional. The IETF 439 protocol for use in constrained environments, CoAP 440 [I-D.ietf-core-coap], makes use of acknowledgements to control 441 packet loss and ensure that packets are received by the packet 442 destination. In the four message types defined for CoAP: 443 confirmable, acknowledgement, reset and non-confirmable, the first 444 three are dedicate for sending/acknowledgement cycle. Another 445 example is that the ZigBee Alliance SEP 2.0 specification [SEP2.0] 446 describes the use of HTTP over TCP over ZigBeeIP, between RPL 447 Routers and the DODAG Root - and with the use of TCP inherently 448 causing bidirectional traffic by way of data-packets and their 449 corresponding acknowledgements. In fact, current Internet 450 protocols generally require some form of acknowledgment, and 451 foregoing an acknowledgment probably means a trade-off in the area 452 of reliable transmission or repeated retransmissions or both. 454 For the former, all sensor-to-sensor routes include the DODAG Root, 455 possibly causing congestions on the communication medium near the 456 DODAG Root, and draining energy from the intermediate RPL Routers on 457 an unnecessarily long route. If sensor-to-sensor traffic is common, 458 RPL Routers near the DODAG Root will be particularly solicited as 459 relays, especially in non-storing mode. 461 For the latter, as there is no provision for on-demand generation of 462 routing information from the DODAG Root to a proper subset of all RPL 463 Routers, each RPL Router (besides the Root) is required to generate 464 DAOs. In particular in non-storing mode, each RPL Router will 465 unicast a DAO to the DODAG Root (whereas in storing mode, the DAOs 466 propagate upwards towards the Root). The effects of the requirement 467 to establish downward routes to all RPL Routers are: 469 o Increased memory and processing requirements at the DODAG Root (in 470 particular in non-storing mode) and in RPL Routers near the DODAG 471 Root (in storing mode). 473 o A considerable control traffic overhead [bidir], in particular at 474 and near the DODAG Root, therefore: 476 o Potentially congested channels, and: 478 o Energy drain from the RPL Routers. 480 6. Fragmentation Of RPL Control Messages And Data Packet 482 Link layers, used in LLNs, are often unable to provide an MTU of, at 483 least, 1280 octets - as otherwise required for IPv6 [RFC2460]. In 484 such LLNs, link-specific fragmentation and reassembly of IP packets 485 at a layer below IPv6 is used to transport larger IP packets, 486 providing the required minimum 1280 octet MTU [RFC4919]. 488 When such below-the-IP-layer fragmentation is used, the IP packet has 489 to be reassembled at every hop. Every fragment must be received 490 successfully by the receiving device, or the entire IP packet is 491 lost. Moreover, the additional link-layer frame overhead (and IPv6 492 Fragment header overhead in case of IP fragmentation) for each of the 493 fragments increases the capacity required from the medium, and may 494 consume more energy for transmitting a higher number of frames on the 495 network interface. 497 RPL is an IPv6 routing protocol, designed to operate on constrained 498 link layers, such as [ieee802154], with a maximum frame size of 127 499 bytes - a much smaller value than the specified minimum MTU of 1280 500 bytes for IPv6 [RFC2460]. Reducing the need of fragmentation of IP 501 datagrams on such a link layer, 6LoWPAN provides an adaptation layer 502 [RFC4944], [RFC6282], providing "Layer 2.5 fragmentation" in order to 503 accommodate IPv6 packet transmissions over the maximum IEEE 802.15.4 504 frame size of 127 octets, as well as compressing the IPv6 header, 505 reducing the overhead of the IPv6 header from at least 40 octets to a 506 minimum of 2 octets. Given the IEEE 802.15.4 frame size of 127 507 octets, a maximum frame overhead of 25 octets and 21 octets for link 508 layer security [RFC4944], 81 octets remain for L2 payload. Further 509 subtracting 2 octets for the compressed IPv6 header leaves 79 octets 510 for L3 data payload if link-layer fragmentation is to be avoided. 512 The second L in LLN indicating Lossy [roll-charter], higher loss 513 rates than typically seen in IP networks are expected, rendering 514 fragmentation important to avoid. This, in particular because, as 515 mentioned above, the whole IP packet is dropped if only a single 516 fragment is lost. 518 6.1. Observations 520 [RFC4919] makes the following observation regarding using IP in 521 LoWPAN networks based on IEEE 802.15.4 frames: 523 Applications within LoWPANs are expected to originate small 524 packets. Adding all layers for IP connectivity should still allow 525 transmission in one frame, without incurring excessive 526 fragmentation and reassembly. Furthermore, protocols must be 527 designed or chosen so that the individual "control/protocol 528 packets" fit within a single 802.15.4 frame. Along these lines, 529 IPv6's requirement of sub-IP reassembly [...] may pose challenges 530 for low-end LoWPAN devices that do not have enough RAM or storage 531 for a 1280-octet packet. 533 In order to avoid the link-layer fragmentation and thus to adhere to 534 the recommendation in [RFC4919], each control packet of RPL must fit 535 into the remaining 79 octets of the 802.15.4 frame. While 79 octets 536 may seem to be sufficient to carry RPL control messages, consider the 537 following: RPL control messages are carried in ICMPv6, and the 538 mandatory ICMPv6 header consumes 4 octets. The DIO base another 24 539 octets. If link metrics are used, that consumes at least another 8 540 octets - and this is when using a simple hop count metric; other 541 metrics may require more. The DODAG Configuration Object consumes up 542 to a further 16 octets, for a total of 52 octets. Adding a Prefix 543 Information Object for address configuration consumes another 32 544 octets, for a total of 84 octets - thus exceeding the 79 octets 545 available for L3 data payload and causing link-layer fragmentation of 546 such a DIO. As a point of reference, the ContikiRPL [rpl-contiki] 547 implementation includes both the DODAG Configuration option and the 548 Prefix Information option in all DIO messages. Any other options, 549 e.g., Route Information options indicating prefixes reachable through 550 the DODAG Root, increase the overhead and thus the probability of 551 fragmentation. 553 RPL may further increase the probability of link-layer fragmentation 554 of data traffic: for non-storing mode, RPL employs source-routing for 555 all downward traffic. [RFC6554] specifies the RPL Source Routing 556 header, which imposes a fixed overhead of 8 octets per IP packet 557 leaving 71 octets remaining from the link-layer MTU in order to 558 contain the whole IP packet into a single frame - from which must be 559 deducted a variable number of octets, depending on the length of the 560 route. With fewer octets available for data payload, RPL thus 561 increases the probability for link-layer fragmentation of also data 562 packets. This, in particular, for longer routes, e.g., for point-to- 563 point data traffic between sensors inside the LLN, where data traffic 564 transit through the DODAG Root and is then source-routed to the 565 destination. The overhead of source routing is further detailed in 566 Section 7. 568 Given the minimal packet size of LLNs, the routing protocol must 569 impose low (or no) overhead on data packets, hopefully independently 570 of the number of hops [RFC4919]. However, source-routing not only 571 causes increased overhead in the IP header, it also leads to a 572 variable available payload for data (depending on how long the source 573 route is). In point-to-point communication and when non-storing mode 574 is used for downward traffic, the source of a data packet will be 575 unaware of how many octets will be available for payload (without 576 incurring L2.5 fragmentation) when the DODAG Root relays the data 577 packet and adds the source routing header. Thus, the source may 578 choose an inefficient size for the data payload: if the data payload 579 is large, it may exceed the link-layer MTU at the DODAG Root after 580 adding the source-routing header; on the other hand, if the data 581 payload is low, the network resources are not used efficiently, which 582 introduces more overhead and more frame transmissions. 584 Unless the DODAG Root is the source of an IPv6 packet to be forwarded 585 through an RPL LLN, the IPv6 packet must be encapsulated in IPv6-in- 586 IPv6 tunneling, with the RPL extension added to the outer IPv6 587 header. Similarly, in non-storing mode, the original IPv6 packet 588 must be carried in IPv6-in-IPv6 tunneling, with the RPL routing 589 header added to the outer IPv6 header. Both of these mechanisms add 590 additional overhead, increasing the likelihood that link-layer 591 fragmentation will be required to deliver the IPv6 packet. In 592 addition, even IPv6 packets that are the minimum MTU size of 1280 593 octets will require IPv6 fragmentation to accommodate the RPL tunnel 594 and headers on a deployment using the [RFC4944] specification to 595 carry IPv6 over IEEE 802.15.4, because RFC4944 defines the MTU for 596 such deployments to be 1280 octets. The ZigBee Alliance is 597 considering relaxing [RFC4944] to use an MTU of 1360 octets in its 598 specification for IPv6 over IEEE 802.15.4 to accommodate 1280 octet 599 IPv6 packets with the required tunnel overhead without fragmentation. 601 7. The DAO Mechanism: Downward and Point-to-Point Routes 603 RPL specifies two distinct and incompatible "modes of operation" for 604 downward traffic: storing mode, where each RPL Router is assumed to 605 maintain routes to all destinations in its sub-DODAG, i.e., RPL 606 Routers that are "deeper down" in the DODAG, and non-storing mode, 607 where only the DODAG Root stores routes to destinations inside the 608 LLN, and where the DODAG Root employs strict source routing in order 609 to route data traffic to the destination RPL Router. 611 7.1. Observations 613 In addition to possible fragmentation, as occurs when using 614 potentially long source routing headers over a medium with a small 615 MTU - similar to what is discussed in Section 6 - the maximum length 616 of the source routing header [RFC6554] is limited to 136 octets, 617 including an 8 octet long header. As each IPv6 address has a length 618 of 16 octets, not more than 8 hops from the source to the destination 619 are possible for "raw IPv6". Using address compression (e.g., as 620 specified in [RFC4944]), the maximum route length may not exceed 64 621 hops. This excludes deployment of RPL for scenarios with long 622 "chain-like" topologies, such as traffic lights along a street. 624 In storing mode, each RPL Router has to store routes for destinations 625 in its sub-DODAG. This implies that, for RPL Routers near the DODAG 626 Root, the required storage is only bounded by the number of 627 destinations in the network. As RPL targets constrained devices with 628 little memory, but also has as ambition to be operating networks 629 consisting of thousands of routers [roll-charter], the storing 630 capacity on these RPL Routers may need to be the same as DODAG root - 631 or, at least, the storage requirements in RPL Routers "near the DODAG 632 Root" and "far from the DODAG Root" is not homogenous, thus some sort 633 of administrative deployment, and continued administrative 634 maintenance of devices, as the network evolves, is needed. 636 In an experimental testbed, [rpl-eval-UCB] argues that practical 637 experiences suggest that RPL in storing mode, with RPL Routers having 638 10kB of RAM (TELOSB mote with TinyOS, 16-bit RISC, 48 kB program 639 flash memory, 16 kB configuration EEPROM), should be limited to 640 networks of less than ~30 RPL Routers. Note that observation of less 641 than 30 RPL Routers only presents the results obtained from specified 642 testbed and implementation in [rpl-eval-UCB]. Aggregation / 643 summarization of addresses may be advanced as a possible argument 644 that this issue is of little significance - Section 8 discusses why 645 such an argument does not apply. Moreover, if the LoWPAN adaption 646 layer [RFC4944] is used in the LLN, route aggregation is not possible 647 since the same /64 is applied across the entire network. 649 In short, the mechanisms in RPL force the choice between requiring 650 all RPL Routers to have sufficient memory to store route entries for 651 all destinations (storing mode) - or, suffer increased risk of 652 fragmentation, and thus loss of data packets, while consuming network 653 capacity by way of source routing through the DODAG Root (non-storing 654 mode). 656 In RPL, the "mode of operation" stipulates that either downward 657 routes are not supported (MOP=0), or that they are supported by way 658 of either storing or non-storing mode. In case downward routes are 659 supported, RPL does not provide any mechanism for discriminating 660 between which routes should or should not be maintained. In 661 particular, in order to calculate routes to a given destination, all 662 intermediaries between the DODAG Root and that destination must 663 themselves be reachable - effectively rendering downward routes in 664 RPL an "all-or-none" situation. In case a destination is 665 unreachable, all the DODAG Root may do is increase DTSN (Destination 666 Advertisement Trigger Sequence Number) to trigger DAO message 667 transmission, or eventually increase the DODAG version number in case 668 the destination is still unreachable, which possibly provokes a 669 broadcast-storm-like situation. This, in particular, as [RFC6550] 670 does not specify DAO message transmission constraints, nor any 671 mechanism for adapting DAO emission to the network capacity. 673 In storing mode, a DTSN increment by the DODAG Root works only if all 674 RPL Routers, on the path from the DODAG Root to the "lost" target RPL 675 Router, have kept their routing table up-to-date by triggering DAO 676 updates, and thus have a route to the target RPL Router. In non- 677 storing mode, the DODAG Root incrementing its DTSN will trigger 678 global DAO updates, and thus extra overhead in the network and delay 679 in the recalculation of the missing route. 681 Furthermore, DTSN increments are carried by way of DIO messages. In 682 case the "lost" target RPL Router has lost all of its parents, it 683 will not be able to receive DIO messages from them, and thus will 684 have to wait until it has poisoned its sub-DODAG and joined the DODAG 685 through another parent. The only way the DODAG Root can speed up 686 this process is by incrementing the DODAG version number, thus 687 triggering global recalculation of the DODAG. 689 Even in case the DTSN increment is carried to the "lost" target RPL 690 Router through another parent, the triggered DAO will need to go up 691 the DODAG to the DODAG Root via another route, which might itself be 692 broken. This would necessitate the use of local repair mechanisms, 693 potentially causing loops in the network (see Section 14) and 694 eventually global DODAG recalculation. 696 8. Address Aggregation and Summarization 698 As indicated in Section 7, in storing mode, an RPL Router is expected 699 to be able to store routing entries for all destinations in its "sub- 700 DODAG", i.e., routing entries for all destinations in the network 701 where the route to the DODAG Root includes that RPL Router. 703 In the Internet, no single router stores explicit routing entries for 704 all destinations. Rather, IP addresses are assigned hierarchically, 705 such that an IP address does not only uniquely identify a network 706 interface, but also its topological location in the network, as 707 illustrated in Figure 2. All addresses with the same prefix are 708 reachable by way of the same router - which can, therefore, advertise 709 only that prefix. Other routers need only record a single routing 710 entry for that prefix, knowing that as the IP packet reaches the 711 router advertising that prefix, more precise routing information is 712 available. 714 .---. 715 | | 716 '---' 717 | 718 | 719 (a) 720 | 721 |1.x.x.x/8 722 | 723 (b) 724 / \ 725 1.1.x.x/16/ \ 1.2.x.x/16 726 / \ 727 .---. .---. 728 | c | | d | 729 '---' '---' 731 Figure 2: Address Hierarchies 733 Any aggregated routes require the use of a prefix shorter than /64, 734 and subsequent hierarchical assignment of prefixes down to a /64 (as 735 any RPL Router itself provides a /64 subnet to any hosts connected to 736 the RPL Router). 738 Moreover, if the 6lowpan adaption layer [RFC4944] is used in the LLN, 739 route aggregation is not possible since the same /64 is applied 740 across the entire network. 742 8.1. Observations 744 In RPL, each RPL Router acquires a number of parents, as described in 745 Section 3, from among which it selects one as its preferred parent 746 and, thus, next-hop on the route to the DODAG Root. RPL Routers 747 maintain a parent set containing possibly more than a single parent 748 so as to be able to rapidly select an alternative preferred parent, 749 should the previously selected such become unavailable. Thus 750 expected behavior is for an RPL Router to be able to change its point 751 of attachment towards the DODAG Root. If IP addresses are assigned 752 in a strictly hierarchical fashion, and if scalability of the routing 753 state maintained in storing mode is based on this hierarchy, then 754 this entails that each time an RPL Router changes its preferred 755 parent, it must also change its own IP address - as well as cause RPL 756 Routers in its "sub-DODAG" to do the same. RPL does not specify 757 signaling for reconfiguring addresses in a sub-DODAG, while [RFC6550] 758 specifically allows for aggregation (e.g., in Section 18.2.6.: "[...] 759 it is recommended to delay the sending of DAO message to DAO parents 760 in order to maximize the chances to perform route aggregation"). 762 A slightly less strict hierarchy can be envisioned, where an RPL 763 Router can change its preferred parent without necessarily changing 764 addresses of itself and of its sub-DODAG, provided that its former 765 and new preferred parents both have the same preferred parent, and 766 have addresses hierarchically assigned from that - from the 767 "preferred grandparent". With reference to Figure 1, this could be e 768 changing its preferred parent from d to c, provided that both d and c 769 have b as preferred parent. Doing so would impose a restriction on 770 the parent-set selection, admitting only parents which have 771 themselves the same parent, losing redundancy in the network 772 connectivity. RPL does not specify rules for admitting only parents 773 with identical grand-parents into the parent set - although such is 774 not prohibited either, if the loss of redundancy is acceptable. 776 The DODAG Root incrementing the DODAG version number is the mechanism 777 by which RPL enables global reconfiguration of the network, 778 reconstructing the DODAG with (intended) more optimal routes. In 779 case of addressing hierarchies being enforced, so as to enable 780 aggregation, this will either restrict the ability for an optimal 781 DODAG construction, or will also have to trigger global address 782 autoconfiguration so as to ensure addressing hierarchies. 784 Finally, with IP addresses serving a dual role of an identifier of 785 both an end-point for communication and a topological location in the 786 network, changing the IP address of a device, so as to reflect a 787 change in network topology, also entails interrupting ongoing 788 communication to or through that device. Additional mechanisms 789 (e.g., a DNS-like system) mapping "communications identifiers" and 790 "IP addresses" are required. 792 9. Link Bidirectionality Verification 794 Parents (and the preferred parent) are selected based on receipt of 795 DIOs. This, alone, does not guarantee the ability of an RPL Router 796 to successfully communicate with the parent. However, the basic use 797 of links is for "upward" routes, i.e., for the RPL Router to use a 798 parent (the preferred parent) as relay towards the DODAG Root - in 799 the opposite direction of the one in which the DIO was received. 801 9.1. Observations 803 Unidirectional links are no rare occurrence, such as is known from 804 wireless multi-hop networks. Preliminary results from a test-bed of 805 AMI (Automated Metering Infrastructure) devices using 950MHz radio 806 interfaces, and with a total of 22 links, show that 36% of these 807 links are unidirectional. If an RPL Router receives a DIO on such a 808 unidirectional link, and selects the originator of the DIO as parent, 809 which would be a bad choice: unicast traffic in the upward direction 810 would be lost. If the RPL Router had verified the bidirectionality 811 of links, it might have selected a better parent, to which it has a 812 bidirectional link. 814 [RFC6550] discusses some mechanisms which can (if deemed needed) be 815 used to verify that a link is bidirectional before choosing an RPL 816 Router as a parent. While requiring one mechanism for bidirectional 817 verification to be used, the document does not specify which method 818 to be used, and how to be used. The mechanisms discussed include NUD 819 [RFC4861], BFD [RFC5881] and [RFC5184]. BFD is explicitly called out 820 as "often not desirable" as it uses a proactive approach (exchange of 821 periodic HELLO messages), and thus would "lead to excessive control 822 traffic". Furthermore, not all L2 protocols provide L2 823 acknowledgements; even less so for multicast packets - and so, not on 824 RPL DIOs, the multicast transmission of which is a requirement for 825 the Trickle timer flooding reduction to be effective (see 826 Section 3.1). This has as consequence that such L2 acknowledgements 827 can only be used to determine if a given link is bidirectional or 828 unidirectional once the RPL Router already has selected parents AND 829 actually has data traffic to forward by way of these parents - in 830 contradiction with RPL's stated design principle that require that 831 the reachability of an RPL Router be verified before choosing it as a 832 parent ([RFC6550], Section 1.1). Absent any mechanism specified by 833 RPL to verify the bidirectionality of links, RPL Routers thus have to 834 rely on NUD to choose their parent correctly (see Section 10). 836 10. Neighbor Unreachability Detection For Unidirectional Links 838 [RFC6550] suggests using Neighbor Unreachability Detection (NUD) 839 [RFC4861] to detect and recover from the situation of unidirectional 840 links between an RPL Router and its (preferred) parent(s). When, 841 e.g., an RPL Router tries (and fails) to actually use another RPL 842 Router for forwarding traffic, NUD is supposed engaged to detect and 843 prompt corrective action, e.g., by way of selecting an alternative 844 preferred parent. 846 NUD is based upon observing if a data packet is making forward 847 progress towards the destination, either by way of indicators from 848 upper-layer protocols (such as TCP and, though not called out in 849 [RFC4861], also from lower-layer protocols such as Link Layer ACKs ) 850 or - failing that - by unicast probing by way of transmitting a 851 unicast Neighbor Solicitation message and expecting that a solicited 852 Neighbor Advertisement message be returned. 854 10.1. Observations 856 An RPL Router may receive, transiently, a DIO from an RPL Router, 857 closer (in terms of rank) to the DODAG Root than any other RPL Router 858 from which a DIO has been received. Some, especially wireless, link 859 layers may exhibit different transmission characteristics between 860 multicast and unicast transmissions (such is the case for some 861 implementations of IEEE 802.11b, where multicast/broadcast 862 transmissions are sent at much lower bit-rates than are unicast; IEEE 863 802.11b is, of course, not suggested as a viable L2 for LLNs, but 864 serves to illustrate that such asymmetric designs exist), leading to 865 a (multicast) DIO being received from farther away than a unicast 866 transmission can reach. DIOs are sent (downward) using link-local 867 multicast, whereas the traffic flowing in the opposite direction 868 (upward) is unicast. Thus, a received (multicast) DIO may not be 869 indicative of useful unicast connectivity - yet, RPL might cause this 870 RPL Router to select this seemingly attractive RPL Router as its 871 preferred parent. This may happen both at initialization, or at any 872 time during the LLN lifetime as RPL allows attachment to a "better 873 parent" over the network lifetime. 875 A DODAG so constructed may appear stable and converged until such 876 time that unicast traffic is to be sent and, thus, NUD invoked. 877 Detecting only at that point that unicast connectivity is not 878 maintained, and causing local (and possibly global) repairs exactly 879 at that time, may lead to traffic not being deliverable. As 880 indicated in Section 8, if scalability is dependent on addresses 881 being assigned hierarchically, changing point-of-attachment may 882 entail more than switching preferred parent. 884 An RPL Router may detect that its preferred parent is lost by way of 885 NUD, when trying to communicate to the DODAG Root. If that RPL 886 Router has no other parents in its parent set, all it can do is wait: 887 RPL does not provide other mechanisms for an RPL Router to react to 888 such an event. In the case where there is no downward traffic (i.e., 889 no data or acknowledgements are sent from the DODAG Root), neither 890 the DODAG Root nor the preferred parent, to which upward connectivity 891 was lost, will be able to detect and react to the event of 892 connectivity loss. 894 In other words, for upward traffic, the RPL Routers that by way of 895 NUD detect connectivity loss, will be unable to act in order to 896 restore connectivity (e.g., by way of a signaling mechanism to the 897 DODAG Root, to request DODAG reconstruction by way of version number 898 increase). The RPL Routers, which could react (the "preferred 899 parents") will for upward traffic not generate any traffic "downward" 900 allowing NUD to engage and detect connectivity loss. 902 It is worth noting that RPL is optimized for upward traffic 903 (multipoint-to-point traffic), and that this is exactly the type of 904 traffic where NUD is not applicable as a mechanism for detecting and 905 reacting to connectivity loss. 907 Also, absent all RPL Routers consistently advertising their 908 reachability through DAO messages, a protocol requiring bidirectional 909 flows between the communicating devices, such as TCP or CoAP 910 confirmable-acknowledgement exchange, will be unable to operate. 912 Finally, upon having been notified by NUD that the "next hop" is 913 unreachable, an RPL Router must discard the preferred parent and 914 select another - hoping that this time, the preferred parent is 915 actually reachable. Also, if NUD indicates "no forward progress" 916 based on an upper-layer protocol, there is no guarantee that the 917 problem stems exclusively from the preferred parent being 918 unreachable. Indeed, it may be a problem further ahead, possibly 919 outside the LLN, thus changing preferred parent will not alleviate 920 the situation. Moreover, using information from an upper-layer 921 protocol, e.g., to return TCP ACKs back to the source, requires 922 established downward routes in the DODAG (i.e., each RPL Router needs 923 to send DAO messages to the DODAG Root, as described in Section 7). 925 Incidentally, this stems from a fundamental difference between "fixed 926 links in the Internet" and "wireless links": whereas the former, as a 927 rule, are reliable, predictable and with losses being rare 928 exceptions, the latter are characterized by frequent losses and 929 general unpredictability. 931 11. RPL Implementability and Complexity 933 RPL is designed to operate on "RPL Routers [...] with constraints on 934 processing power, memory, and energy (battery power)" [RFC6550]. 935 However, the 163 pages long specification of RPL, plus additional 936 specifications for routing headers [RFC6554], Trickle timer 937 [RFC6206], routing metrics [RFC6551] and objective function 938 [RFC6552], describes complex mechanisms (e.g., the upwards and 939 downward data traffic, a security solution, manageability of RPL 940 Routers, auxiliary functions for autoconfiguration of RPL Routers, 941 etc.), and provides no less than 9 message types, and 10 different 942 message options. 944 To give one example, the ContikiRPL implementation 945 (http://www.sics.se/contiki), which provides only storing mode and no 946 security features, consumes about 50 KByte of memory. Sensor 947 hardware, such as MSP430 sensor platforms, does not contain much more 948 memory than that, i.e., there may not be much space left to deploy 949 any application on the RPL Router. 951 11.1. Observations 953 Since RPL is intended as the routing protocol for LLNs, which covers 954 all the diverse applications requirements listed in [RFC5867], 955 [RFC5673], [RFC5826], [RFC5548], it is likely that (i) due to limited 956 memory capacity of the RPL Routers, and (ii) due to expensive 957 development cost of the routing protocol implementation, RPL 958 implementations will only support a partial set of features from the 959 specification, leading to non-interoperable implementations. 961 In order to accommodate for the verbose exchange format, route 962 stretching and source routing for point-to-point traffic, several 963 additional Internet-Drafts are being discussed for adoption in the 964 ROLL Working Group - adding complexity to an already complex 965 specification which, it is worth recalling, was intended to be of a 966 protocol for low-capacity devices. 968 12. Underspecification 970 While [RFC6550] provides various options and extensions in many 971 parts, which makes a complex protocol, as described in Section 11, 972 some mechanisms are underspecified. 974 While for DIOs, the Trickle timer specifies a relatively efficient 975 and easy-to-understand timing for message transmission, the timing of 976 DAO transmission is not explicit. As each DAO may have a limited 977 lifetime, one "best guess" for implementers would be to send DAO 978 periodically, just before the life-time of the previous DAO expires. 979 Since DAOs may be lost, another "best guess" would be to send several 980 DAOs shortly one after the other in order to increase probability 981 that at least one DAO is successfully received. 983 The same underspecification applies for DAO-ACK messages: optionally, 984 on reception of a DAO, an RPL Router may acknowledge successful 985 reception by returning a DAO-ACK. Timing of DAO-ACK messages is 986 unspecified by RPL. 988 12.1. Observations 990 By not specifying details about message transmission intervals and 991 required actions when receiving DAO and DAO-ACKs, implementations may 992 exhibit a bad performance if not carefully implemented. Some 993 examples are: 995 1. If DAO messages are not sent in due time before the previous DAO 996 expires (or if the DAO is lost during transmission), the routing 997 entry will expire before it is renewed, leading to a possible 998 data traffic loss. 1000 2. RPL does not specify to use jitter [RFC5148] (i.e., small random 1001 delay for message transmissions). If DAOs are sent periodically, 1002 adjacent RPL Routers may transmit DAO messages at the same time, 1003 leading to link layer collisions. 1005 3. In non-storing mode, the "piece-wise calculation" of routes to a 1006 destination from which a DAO has been received, relies on 1007 previous reception of DAOs from intermediate RPL Routers along 1008 the route. If not all of these DAOs from intermediate RPL 1009 Routers have been received, route calculation is not possible, 1010 and DAO-ACKs or data traffic cannot be sent to that destination. 1012 Other examples of underspecification include detection of 1013 connectivity loss, as described in Section 10, as well as the local 1014 repair mechanism, which may lead to loops and thus data traffic loss, 1015 if not carefully implemented: an RPL Router discovering that all its 1016 parents are unreachable, may - according to the RPL specification - 1017 "detach" from the DODAG, i.e., increase its own rank to infinity. It 1018 may then "poison" its sub-DODAG by advertising its infinite rank in 1019 its DIOs. If, however, the RPL Router receives a DIO before it 1020 transmits the "poisoned" DIO, it may attach to its own sub-DODAG, 1021 creating a loop. If, instead, it had waited some time before 1022 processing DIOs again, chances are it would have succeeded in 1023 poisoning its sub-DODAG and thus avoided the loop. 1025 13. Protocol Convergence 1027 Trickle [RFC6206] is used by RPL to schedule transmission of DIO 1028 messages, with the objective of minimizing the amount of transmitted 1029 DIOs while ensuring a low convergence time of the network. The 1030 theoretical behavior of Trickle is well understood, and the 1031 convergence properties are well studied. Simulations of the 1032 mechanism, such as documented [trickle-multicast], confirm these 1033 theoretical studies. 1035 In real-world environments, however, varying link qualities may cause 1036 the algorithm to converge less well: frequent message losses entail 1037 resets of the Trickle timer and more frequent and unpredicted message 1038 emissions. 1040 13.1. Observations 1042 The varying link quality in real-world environments results in 1043 frequent changes of the best parent, which triggers a reset of the 1044 Trickle timer and thus the emission of DIOs. Therefore Trickle does 1045 not converge as well for links that are fluctuating in quality as in 1046 theory. 1048 This has been observed, e.g., in an experimental testbed: 69 RPL 1049 Routers (MSP430-based wireless sensor routers with IEEE 802.15.4, 1050 using [rpl-contiki] IPv6 stack and RPL without downward routes; the 1051 parameters of the Trickle timer were set to the implementation 1052 defaults (minimum DIO interval: 4 s, DIO interval doublings: 8, 1053 redundancy constant: 10) were positioned in a fixed grid topology. 1054 This resulted in DODAGs being constructed with an average of 2.45 1055 children per RPL Router and an average rank of 3.58. 1057 In this small test network, the number of DIO messages emitted - 1058 expectedly - spiked within the first ~10 seconds. Alas, rather than 1059 taper off to become zero (as the simulation studies would suggest), 1060 the DIO emission rate remained constant at about 70 DIOs per second. 1061 Details on this experiment can be found in [rpl-eval]. 1063 In another experimental testbed with 17 RPL routers (Tmote Sky, 1064 Contiki platform [powertrace]), the authors also showed that the DIO 1065 emission continues with constant rate. Even with a relatively high 1066 data rate for sensor networks (every router sends 1 packet to the 1067 root per minute), the energy used for routing control packets is 1068 higher than the data traffic transmission. 1070 The resulting higher control overhead due to frequent DIO emission, 1071 leads to higher bandwidth and energy consumption as well as possibly 1072 to an increased number of collisions of frames, as observed in 1073 [trickle-multicast]. 1075 13.2. Caveat 1077 Note that these observations do not claim that it is impossible to 1078 parametrize Trickle timers so that a given deployment exhibits the 1079 theoretical characteristics (or, characetristics sufficiently close 1080 thereto) of the Trickle mechanism. These observations suggest that 1081 the default parameter values, provided for Trickle timers in 1082 [RFC6550], did not apply to the small network tested. These 1083 observations also suggest that special care is required when 1084 selecting the values for the parameters for Trickle timers, and that 1085 these values likely are to be determined experimentally, and 1086 individually for each deployment. 1088 14. Loops 1090 [RFC6550] states that it "guarantees neither loop free route 1091 selection nor tight delay convergence times, but can detect and 1092 repair a loop as soon as it is used. RPL uses this loop detection to 1093 ensure that packets make forward progress [...] and trigger repairs 1094 when necessary". This implies that a loop may only then be detected 1095 and fixed when data traffic is sent through the network. 1097 In order to trigger a local repair, RPL relies on the "direction" 1098 information (with values "up" or "down"), contained in an IPv6 hop- 1099 by-hop option header from received a data packet. If an "upward" 1100 data packet is received by an RPL Router, but the previous hop of the 1101 packet is listed with a lower rank in the neighbor set, the RPL 1102 Router concludes that there must be a routing loop and it may 1103 therefore trigger a local repair. For downward traffic in non- 1104 storing mode, the DODAG Root can detect loops if the same RPL Router 1105 identifier (i.e., IP address) appears at least twice in the route 1106 towards a destination. 1108 14.1. Observations 1110 The reason for RPL to repair loops only when detected by a data 1111 traffic transmission is to reduce control traffic overhead. However, 1112 there are two problems in repairing loops only when so triggered: (i) 1113 the triggered local repair mechanism delays forward progress of data 1114 packets, increasing end-to-end delays, and (ii) the data packet has 1115 to be buffered during repair. 1117 (i) may seem as the lesser of the two problems, since in a number of 1118 applications, such as data acquisition in smart metering 1119 applications, an increased delay may be acceptable. However, for 1120 applications such as alarm signals or in home automation (e.g., a 1121 light switch), increased delay may be undesirable. 1123 As for (ii), RPL is supposed to run on LLN routers with "constraints 1124 on [...] memory" [RFC6550]; buffering incoming packets during the 1125 route repair may not be possible for all incoming data packets, 1126 leading to dropped packets. Depending on the transport protocol, 1127 these data packets must be retransmitted by the source or are 1128 definitely lost. 1130 If carefully implemented with respect to avoiding loops before they 1131 occur, the impact of the loop detection in RPL may be minimized. 1132 However, it can be observed that with current implementations of RPL, 1133 such as the ContikiRPL implementation, loops do occur - and, 1134 frequently. During the same experiments described in Section 13, a 1135 snapshot of the DODAG was made every ten seconds. In 74.14% of the 1136 4114 snapshots, at least one loop was observed. Further 1137 investigation revealed that in all these cases the DODAG was 1138 partitioned, and the loop occurred in the sub-DODAG that no longer 1139 had a connection to the DODAG Root. When the link to the only parent 1140 of an RPL Router breaks, the RPL Router may increase its rank and - 1141 when receiving a DIO from an RPL Router in its sub-DODAG - attach 1142 itself to its own sub-DODAG, thereby creating a loop - as detailed in 1143 Section 12.1. 1145 While it can be argued that the observed loops are harmless since 1146 they occur in a DODAG partition that has no connection to the DODAG 1147 Root, they show that the routes are not built correctly. Even worse, 1148 when the broken link re-appears, it is possible that in certain 1149 situations, the loop is only repaired when data traffic is sent, 1150 possibly leading to data loss (as described above). This can occur 1151 if the link to the previous parent is reestablished, but the rank of 1152 that previous parent has increased in the meantime. 1154 Another problem with the loop repair mechanism arises in non-storing 1155 mode when using only downward traffic: while the DODAG Root can 1156 easily detect loops (as described above), it has no direct means to 1157 trigger a local repair where the loop occurs. Indeed, it can only 1158 trigger a global repair by increasing the DODAG version number, 1159 leading to a Trickle timer reset and increased control traffic 1160 overhead in the network caused by DIO messages, and therefore a 1161 possible energy drain of the RPL Routers and congestion of the 1162 channel. 1164 Finally, loop detection for every data packet increases the 1165 processing overhead. RPL is targeted for deployments on very 1166 constrained devices with little CPU power, therefore a loop detection 1167 for every packet reduces available resources of the LLN router for 1168 other tasks (such as sensing). Moreover, each IPv6 packet needs to 1169 contain the "RPL Option for Carrying RPL Information in Data-Plane 1170 Datagrams" [RFC6553] in order to use loop detection (as well as 1171 determining the RPL instance), which in turn implies an extra IPv6 1172 header (and thus overhead) for IPv6-in-IPv6 tunneling. As this RPL 1173 option is a hop-by-hop option, it needs to be in an encapsulating 1174 IPv6-in-IPv6 tunnel and then regenerated at each hop. 1176 15. Security Considerations 1178 This document does currently not specify any security considerations. 1179 This document also does not provide any evaluation of the security 1180 mechanisms of RPL. 1182 16. IANA Considerations 1184 This document has no actions for IANA. 1186 17. Acknowledgements 1188 The authors would like to thank Matthias Philipp (INRIA) for his 1189 contributions to conducting many of the experiments, revealing or 1190 confirming the issues described in this document. 1192 Moreover, the authors would like to express their gratitude to Ralph 1193 Droms (Cisco) for his careful review of various versions of this 1194 document, for many long discussions, and for his considerable 1195 contributions to both the content and the quality of this document. 1197 18. Informative References 1199 [I-D.ietf-core-coap] 1200 Shelby, Z., Hartke, K., and C. Bormann, "Constrained 1201 Application Protocol (CoAP)", draft-ietf-core-coap-18 1202 (work in progress), June 2013. 1204 [I-D.ietf-roll-terminology] 1205 Vasseur, J., "Terms used in Routing for Low power And 1206 Lossy Networks", draft-ietf-roll-terminology-13 (work in 1207 progress), October 2013. 1209 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 1210 (IPv6) Specification", RFC 2460, Decemer 1998. 1212 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 1213 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 1214 September 2007. 1216 [RFC4919] Kushalnagar, N., Montenegro, G., and C. Schumacher, "IPv6 1217 over Low-Power Wireless Personal Area Networks (6LoWPANs): 1218 Overview, Assumptions, Problem Statement, and Goals", 1219 RFC 4919, August 2007. 1221 [RFC4944] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, 1222 "Transmission of IPv6 Packets over IEEE 802.15.4 1223 Networks", RFC 4944, September 2007. 1225 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 1226 Considerations in Mobile Ad Hoc Networks (MANETs)", 1227 RFC 5148, February 2008. 1229 [RFC5184] Aggarwal, R., Kompella, K., Nadeau, T., and G. Swallow, 1230 "Bidirectional Forwarding Detection (BFD) for IPv4 and 1231 IPv6 (Single Hop)", RFC 5184, June 2010. 1233 [RFC5548] Dohler, M., Watteyne, T., Winter, T., and D. Barthel, 1234 "Routing Requirements for Urban Low-Power and Lossy 1235 Networks", RFC 5548, May 2009. 1237 [RFC5673] Pister, K., Thubert, P., Dwars, S., and T. Phinney, 1238 "Industrial Routing Requirements in Low-Power and Lossy 1239 Networks", RFC 5673, October 2009. 1241 [RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation 1242 Routing Requirements in Low-Power and Lossy Networks", 1243 RFC 5826, April 2010. 1245 [RFC5867] Martocci, J., Mi, P., Riou, N., and W. Vermeylen, 1246 "Building Automation Routing Requirements in Low Power and 1247 Lossy Networks", RFC 5867, June 2010. 1249 [RFC5881] Ward, D. and D. Katz, "Bidirectional Forwarding Detection 1250 (BFD) for IPv4 and IPv6 (Single Hop)", RFC 5881, 1251 June 2010. 1253 [RFC6206] Levis, P., Clausen, T., Gnawali, O., and J. Ko, "The 1254 Trickle Algorithm", RFC 6206, March 2011. 1256 [RFC6282] Hui, J. and P. Thubert, "Compression Format for IPv6 1257 Datagrams over IEEE 802.15.4-Based Networks", RFC 6282, 1258 September 2011. 1260 [RFC6550] Winther, T., Thubert, P., Hui, J., Vasseur, J., Brandt, 1261 A., Kelsey, R., Levis, P., Piester, K., Struik, R., and R. 1262 Alexander, "RPL: IPv6 Routing Protocol for Low-Power and 1263 Lossy Networks", RFC 6550, March 2012. 1265 [RFC6551] Vasseur, J., Pister, K., Dejan, N., and D. Barthel, 1266 "Routing Metrics Used for Path Calculation in Low-Power 1267 and Lossy Networks", RFC 6551, March 2012. 1269 [RFC6552] Thubert, P., "Objective Function Zero for the Routing 1270 Protocol for Low-Power and Lossy Networks (RPL)", 1271 RFC 6552, March 2012. 1273 [RFC6553] Hui, J. and J. Vasseur, "The Routing Protocol for Low- 1274 Power and Lossy Networks (RPL) Option for Carrying RPL 1275 Information in Data-Plane Datagrams", RFC 6553, 1276 March 2012. 1278 [RFC6554] Hui, J., Vasseur, J., Culler, D., and V. Manral, "An IPv6 1279 Routing Header for Source Routes with the Routing Protocol 1280 for Low-Power and Lossy Networks (RPL)", RFC 6554, 1281 March 2012. 1283 [SEP2.0] Alliance, Zigbee., "ZigSmart Energy version 2.0 (SEP 2.0) 1284 draft 0.7", July 2011. 1286 [bidir] Clausen, T. and U. Herberg, "A Comparative Performance 1287 Study of the Routing Protocols LOAD and RPL with Bi- 1288 Directional Traffic in Low-power and Lossy Networks 1289 (LLN)", Proceedings of the Eighth ACM International 1290 Symposium on Performance Evaluation of Wireless Ad Hoc, 1291 Sensor, and Ubiquitous Networks (PE-WASUN), 2011. 1293 [ieee802154] 1294 Computer Society, IEEE., "IEEE Std. 802.15.4-2003", 1295 October 2003. 1297 [powertrace] 1298 Dunkels, A., Eriksson, J., Finne, N., and N. Tsiftes, 1299 "Powertrace: Network-level Power Profiling for Low-power 1300 Wireless Networks", Technical Report SICS T2011:05. 1302 [roll-charter] 1303 "ROLL Charter", 1304 web http://datatracker.ietf.org/wg/roll/charter/, 1305 February 2012. 1307 [rpl-contiki] 1308 Tsiftes, N., Eriksson, J., and A. Dunkels, "Low-Power 1309 Wireless IPv6 Routing with ContikiRPL", 1310 Proceedings Proceedings of the 9th ACM/IEEE International 1311 Conference on Information Processing in Sensor Networks 1312 (ISPN), 2011. 1314 [rpl-eval] 1315 Clausen, T., Herberg, U., and M. Philipp, "A Critical 1316 Evaluation of the IPv6 Routing Protocol for Low Power and 1317 Lossy Networks (RPL)", Proceedings of the 5th IEEE 1318 International Conference on Wireless & Mobile Computing, 1319 Networking & Communication (WiMob), 2011. 1321 [rpl-eval-UCB] 1322 Ko, J., Dawson-Haggerty, S., Culler, D., and A. Terzis, 1323 "Evaluating the Performance of RPL and 6LoWPAN in TinyOS", 1324 Proceedings of the Workshop on Extending the Internet to 1325 Low power and Lossy Networks (IP+SN), 2011. 1327 [trickle-multicast] 1328 Clausen, T. and U. Herberg, "Study of Multipoint-to-Point 1329 and Broadcast Traffic Performance in the 'IPv6 Routing 1330 Protocol for Low Power and Lossy Networks' (RPL)", 1331 Journal of Ambient Intelligence and Humanized Computing, 1332 2011. 1334 Authors' Addresses 1336 Thomas Clausen 1337 LIX, Ecole Polytechnique 1338 91128 Palaiseau Cedex, 1339 France 1341 Phone: +33 6 6058 9349 1342 Email: T.Clausen@computer.org 1343 URI: http://www.thomasclausen.org 1345 Axel Colin de Verdiere 1346 LIX, Ecole Polytechnique 1347 91128 Palaiseau Cedex, 1348 France 1350 Phone: +33 6 1264 7119 1351 Email: axel@axelcdv.com 1352 URI: http://www.axelcdv.com/ 1354 Jiazi Yi 1355 LIX, Ecole Polytechnique 1356 91128 Palaiseau Cedex, 1357 France 1359 Phone: +33 1 6933 4031 1360 Email: jiazi@jiaziyi.com 1361 URI: http://www.jiaziyi.com/ 1362 Ulrich Herberg 1363 Fujitsu Laboratories of America 1364 1240 E Arques Ave 1365 Sunnyvale, CA 94085 1366 USA 1368 Email: ulrich@herberg.name 1369 URI: http://www.herberg.name/ 1371 Yuichi Igarashi 1372 Hitachi, Ltd., Yokohama Research Laboratory 1374 Phone: +81 45 860 3083 1375 Email: yuichi.igarashi.hb@hitachi.com 1376 URI: http://www.hitachi.com/