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