idnits 2.17.1 draft-clausen-lln-rpl-experiences-04.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 (July 16, 2012) is 4302 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-06 -- 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: January 17, 2013 LIX, Ecole Polytechnique 6 U. Herberg 7 Fujitsu Laboratories of America 8 Y. Igarashi 9 Hitachi, Ltd., Yokohama Research 10 Laboratory 11 July 16, 2012 13 Observations of RPL: IPv6 Routing Protocol for Low power and Lossy 14 Networks 15 draft-clausen-lln-rpl-experiences-04 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 January 17, 2013. 49 Copyright Notice 51 Copyright (c) 2012 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 . . . . . . . . . . . . 15 79 8.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 16 80 9. Links Assumed Bi-Directional . . . . . . . . . . . . . . . . . 18 81 9.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 18 82 10. Neighbor Unreachability Detection For Unidirectional Links . . 18 83 10.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 18 84 11. RPL Implementability and Complexity . . . . . . . . . . . . . 20 85 11.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 20 86 12. Underspecification . . . . . . . . . . . . . . . . . . . . . . 21 87 12.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 21 88 13. Protocol Convergence . . . . . . . . . . . . . . . . . . . . . 22 89 13.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 23 90 14. Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 91 14.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 23 92 15. Security Considerations . . . . . . . . . . . . . . . . . . . 25 93 16. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 25 94 17. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 25 95 18. Informative References . . . . . . . . . . . . . . . . . . . . 25 96 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 28 98 1. Introduction 100 RPL - the "Routing Protocol for Low Power and Lossy Networks" 101 [RFC6550] - is a proposal for an IPv6 routing protocol for Low-power 102 Lossy Networks (LLNs), by the ROLL Working Group in the Internet 103 Engineering Task Force (IETF). This routing protocol is intended to 104 be the IPv6 routing protocol for LLNs and sensor networks, applicable 105 in all kinds of deployments and applications of LLNs. 107 The objective of RPL and ROLL is to provide routing in networks which 108 "comprise up to thousands of nodes" [roll-charter], where the 109 majority of the nodes have very constrained resources 110 [I-D.ietf-roll-terminology], and where handling mobility is not an 111 explicit design criteria [RFC5867], [RFC5826], [RFC5673], [RFC5548]. 113 [roll-charter] states that "Typical traffic patterns are not simply 114 unicast flows (e.g. in some cases most if not all traffic can be 115 point to multipoint)", and [I-D.ietf-roll-terminology] further 116 categorizes the supported traffic types into "upward" traffic from 117 sensors to a collection sink or LBR (LLN Border Router) (denoted 118 multipoint-to-point), "downward" traffic from the collection sink or 119 LBR to the sensors (denoted point-to-multipoint) and traffic from 120 "sensor to sensor" (denoted point-to-point traffic), and establishes 121 this terminology for these traffic types. Thus, while the target for 122 RPL and ROLL is to support all of these traffic types, the emphasis 123 among these, according to [roll-charter], appears to be to optimize 124 for multipoint-to-point traffic, while also supporting point-to- 125 multipoint and point-to-point traffic. 127 As of early 2011, RPL has been approved by the IESG, for publication 128 as a "Proposed Standard" RFC (Request for Comments). The implication 129 of a protocol being labeled "Proposed Standard" is that it is 130 considered generally stable: well-understood and community reviewed, 131 no known design issues pending, and with some community support 132 [RFC2026]. 134 "Proposed Standard" is, however, only the first step on the Standards 135 Track, and it is thus opportune to document observations of the 136 protocol, in order to understand which aspects of it necessitate 137 further investigations, and in order to identify possibly weak points 138 which may restrict the deployment scope of the protocol. Most of the 139 observations made in this document (except the ones with explicit 140 description of test scenarios) are not based on single 141 implementation, but general behaviors of [RFC6550]. This document is 142 not an implementation guidebook of RPL, but has as objective to 143 document such observations of RPL, in the spirit of better 144 understanding its characteristics and limits. 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. 235 Depending on the MOP, DAO messages are forwarded differently towards 236 the DODAG Root: 238 o In "non-storing mode", an RPL Router originates a DAO messages, 239 advertising one or more of its parents, and unicasts these to the 240 DODAG Root. Once the DODAG Root has received DAOs from an RPL 241 Router, and from all RPL Routers on the route between it and the 242 DODAG Root, it can use source routing for reaching advertised 243 destinations inside the LLN. 245 o In "storing mode", each RPL Router on the route between the 246 originator of a DAO and the DODAG Root records a route to the 247 prefixes advertised in the DAO, as well as the next-hop towards 248 these (the RPL Router, from which the DAO was received), then 249 forwards the DAO to its preferred parent. 251 "Point-to-point routes", for communication between devices inside the 252 LLN and where neither of the communicating devices are the DODAG 253 Root, are as default supported by having the source sensor transmit a 254 data packet, via its default route to the DODAG Root (i.e., using the 255 upward routes), which will then, depending on the "Mode of Operation" 256 for the DODAG, either add a source-route to the received data packet 257 for reaching the destination sensor (downward routes in non-storing 258 mode), or simply use hop-by-hop routing (downward routes in storing 259 mode) for forwarding the data packet. In the case of storing mode, 260 if the source and the destination for a point-to-point data packet 261 share a common ancestor other than the DODAG Root, a downward route 262 may be available in an RPL Router (and, thus, used) before the data 263 packet reaches the DODAG Root. 265 3.1. RPL Message Emission Timing - Trickle Timers 267 RPL message generation is timer-based, with the DODAG Root being able 268 to configure back-off of message emission intervals using Trickle 269 [RFC6206]. Trickle, as used in RPL, stipulates that an RPL Router 270 transmits a DIO "every so often" - except if receiving a number of 271 DIOs from neighbor RPL routers, enabling the RPL Router to determine 272 if its DIO transmission is redundant. 274 When an RPL Router transmits a DIO, there are two possible outcomes: 275 either every neighbor RPL Router that hears the message finds that 276 the information contained is consistent with its own state (i.e., the 277 received DODAG version number corresponds with that which the RPL 278 Router has recorded, and no better rank is advertised than that which 279 is recorded in the parent set) - or, a recipient RPL Router detects 280 that either the sender of the DIO or itself has out-of-date 281 information. If the sender has out-of-date information, then the 282 recipient RPL Router schedules transmission of a DIO to update this 283 information. If the recipient RPL Router has out-of-date 284 information, then it updates based on the information received in the 285 DIO. 287 With Trickle, an RPL Router will schedule emission of a DIO at some 288 time, t, in the future. When receiving a DIO containing information 289 consistent with its own information, the RPL Router will record that 290 "redundant information has been received" by incrementing a 291 redundancy counter, c. At the time t, if c is below some "redundancy 292 threshold", then it transmits its DIO. Otherwise, transmission of a 293 DIO at this time is suppressed, c is reset and a new t is selected to 294 twice as long time in the future - bounded by a pre-configured 295 maximum value for t. If, on the other hand, the RPL Router has 296 received an out-of-date DIO from one of its neighbors, t is reset to 297 a pre-configured minimum value and c is set to zero. In both cases, 298 at the expiration of t, the RPL Router will verify if c is below the 299 "redundancy threshold" and if so transmit - otherwise, increase t and 300 stay quiet. 302 4. Requirement Of DODAG Root 304 As indicated in Section 3, the DODAG Root has both a special 305 responsibility and is subject to special requirements. The DODAG 306 Root is responsible for determining and maintaining the configuration 307 parameters for the DODAG, and for initiating DIO emissions. 309 The DODAG Root is also responsible (in both storing and non-storing 310 mode) for being able to, when downward routes are supported, maintain 311 sufficient topological information to be able to construct routes to 312 all destinations in the network. 314 When operating in non-storing mode, this entails that the DODAG Root 315 is required to have sufficient memory and sufficient computational 316 resources to be able to record a network graph containing all routes 317 from itself and to all destinations and calculate routes. 319 When operating in storing mode, this entails that the DODAG Root 320 needs enough memory to keep a list of all RPL Routers in the RPL 321 instance, and a next hop for each of those RPL routers. If 322 aggregation is used, the memory requirements can be reduced in 323 storing mode (see Section 8 for observations about aggregation in 324 RPL). 326 The DODAG Root is also required to have sufficient energy available 327 so as to be able to ensure the relay functions required. This, 328 especially for non-storing mode, where all data packets transit 329 through the DODAG Root. 331 4.1. Observations 333 In a given deployment, select RPL Routers can be provisioned with the 334 required energy, memory and computational resources so as to serve as 335 DODAG Roots, and be administratively configured as such - with the 336 remainder of the RPL routers in the network being of typically lesser 337 capacity. [rpl-eval-UCB] indicates that, in storing mode, a TelosB 338 mote with 10KB of RAM has sufficient memory to support up to about 30 339 RPL Routers in the LLN - in a larger network (in storing or non- 340 storing mode, both) the DODAG Root would require at least that much, 341 likely much more, memory. In non-storing mode, the resource 342 requirements on the DODAG Root are likely much higher than in storing 343 mode, as the DODAG Root needs to store a network graph containing 344 complete routes to all destinations in the RPL instance, in order to 345 calculate the routing table (whereas in storing mode, only the next 346 hop for each destination in the RPL instance needs to be stored, and 347 aggregation may be used to further reduce the resource requirements). 349 RPL Routers provisioned with resources to act as DODAG Roots, and 350 administratively configured to act as such, represent a single point 351 of failure in the network. As the memory requirements for the DODAG 352 Root and for other RPL Routers are substantially different, unless 353 all RPL Routers are provisioned with resources (memory, energy, ...) 354 to act as DODAG Roots, effectively if the designated DODAG Root 355 fails, the network fails and RPL is unable to operate. Even if 356 electing another RPL Router as temporary DODAG root (e.g., for 357 forming a "Floating" DODAG) for providing internal connectivity 358 between RPL Routers, this router may not have the necessary resources 359 to satisfy this role as (temporary) DODAG Root. 361 Thus, although in principle RPL provides, by way of "Floating 362 DODAGs", protocol mechanisms for establishing a DODAG for providing 363 internal connectivity even in case of failure of the administratively 364 provisioned DODAG Root - especially in non-storing mode - it is 365 unlikely that any RPL Routers not explicitly provisioned as DODAG 366 Roots will have sufficient resources to undertake this task. 368 Another possible LLN scenario is that only internal point-to-point 369 connectivity is sought, and no RPL Router has a more "central" role 370 than any other - a self-organizing LLN. Requiring special 371 provisioning of a specific "super-node" as DODAG Root is both 372 unnecessary and undesirable. 374 5. RPL Data Traffic Flows 376 RPL makes a-priori assumptions of data traffic types, and explicitly 377 defines three such [I-D.ietf-roll-terminology] traffic types: sensor- 378 to-root data traffic (multipoint-to-point) is predominant, root-to- 379 sensor data traffic (point-to-multipoint) is rare and sensor-to- 380 sensor (point-to-point) data traffic is extremely rare. While not 381 specifically called out thus in [RFC6550], the resulting protocol 382 design, however, reflects these assumptions in that the mechanism 383 constructing multipoint-to-point routes is efficient in terms of 384 control traffic generated and state required, point-to-multipoint 385 route construction much less so - and point-to-point routes subject 386 to potentially significant route stretch (routes going through the 387 DODAG Root in non-storing mode) and over-the-wire overhead from using 388 source routing (from the DODAG Root to the destination) (see 389 Section 7) - or, in case of storing mode, considerable memory 390 requirements in all LLN routers inside the network (see Section 7). 392 An RPL Router selects from among its parents a "preferred parent", to 393 serve as a default route towards the DODAG Root (and to prefixes 394 advertised by the DODAG Root). Thus, RPL provides "upward routes" or 395 "multipoint-to-point routes" from the RPL Routers below the DODAG 396 Root and towards the DODAG Root. 398 An RPL Router which wishes to act as a destination for data traffic 399 ("downward routes" or "point-to-multipoint") issues DAOs upwards in 400 the DODAG towards the DODAG Root, describing which prefixes belong 401 to, and can be reached via, that RPL Router. 403 Point-to-Point routes between RPL Routers below the DODAG Root are 404 supported by having the source RPL Router transmit, via its default 405 route, data traffic towards the DODAG Root. In non-storing mode, the 406 data traffic will reach the DODAG Root, which will reflect the data 407 traffic downward towards the destination RPL Router, adding a strict 408 source routing header indicating the precise route for the data 409 traffic to reach the intended destination RPL Router. In storing 410 mode, the source and the destination may possibly (although, may also 411 not) have a common ancestor other than the DODAG Root, which may 412 provide a downward route to the destination before data traffic 413 reaching the DODAG Root. 415 5.1. Observations 417 The data traffic characteristics, assumed by RPL, do not represent a 418 universal distribution of traffic types in LLNs: 420 o There are scenarios where sensor-to-sensor traffic is a more 421 common occurrence, documented, e.g., in [RFC5867] ("Building 422 Automation Routing Requirements in Low Power and Lossy Networks"). 424 o There are scenarios, where all traffic is bi-directional, e.g., in 425 case sensor devices in the LLN are, in majority, "actively read": 426 a request is issued by the DODAG Root to a specific sensor, and 427 the sensor value is expected returned. In fact, unless all 428 traffic in the LLN is unidirectional, without acknowledgements 429 (e.g., as in UDP), and no control messages (e.g., for service 430 discovery) or other data packets are sent from the DODAG Root to 431 the RPL Routers, traffic will be bi-directional. As an example, 432 the ZigBee Alliance SEP 2.0 specification [SEP2.0] describes the 433 use of HTTP over TCP over ZigBeeIP, between RPL Routers and the 434 DODAG Root - and with the use of TCP inherently causing 435 bidirectional traffic by way of data-packets and their 436 corresponding acknowledgements. 438 For the former, all sensor-to-sensor routes include the DODAG Root, 439 possibly causing congestions on the communication medium near the 440 DODAG Root, and draining energy from the intermediate RPL Routers on 441 an unnecessarily long route. If sensor-to-sensor traffic is common, 442 RPL Routers near the DODAG Root will be particularly solicited as 443 relays, especially in non-storing mode. 445 For the latter, as there is no provision for on-demand generation of 446 routing information from the DODAG Root to a proper subset of all RPL 447 Routers, each RPL Router (besides the Root) is required to generate 448 DAOs. In particular in non-storing mode, each RPL Router will 449 unicast a DAO to the DODAG Root (whereas in storing mode, the DAOs 450 propagate upwards towards the Root). The effects of the requirement 451 to establish downward routes to all RPL Routers are: 453 o Increased memory and processing requirements at the DODAG Root (in 454 particular in non-storing mode) and in RPL routers near the DODAG 455 Root (in storing mode). 457 o A considerable control traffic overhead [bidir], in particular at 458 and near the DODAG Root, therefore: 460 o Potentially congested channels, and: 462 o Energy drain from the RPL Routers. 464 6. Fragmentation Of RPL Control Messages And Data Packet 466 The link technologies in LLNs often use small frames [RFC4919], which 467 are unable to carry the minimum 1280 octet IP packet in a single 468 frame [RFC2460]. In such LLNs, link-specific fragmentation and 469 reassembly of IP packets at a layer below IPv6 is used to transport 470 larger IP packets, providing the required minimum 1280 octet MTU. 472 When link-layer fragmentation is applied, the IP packet has to be 473 reassembled at every hop. Every fragment must be received 474 successfully by the receiving node, or the entire IP packet is lost. 475 Moreover, the additional link-layer frame overhead (and IPv6 Fragment 476 header overhead in case of IP fragmentation) for each of the 477 fragments increases the capacity required from the medium, and may 478 consume more energy for transmitting a higher number of frames on the 479 network interface. 481 RPL is an IPv6 routing protocol, designed to operate on constrained 482 link layers, such as IEEE 802.15.4 [ieee802154], with a maximum frame 483 size of 127 bytes - a much smaller value than the specified minimum 484 MTU of 1280 bytes for IPv6 [RFC2460]. Reducing the need of 485 fragmentation of IP datagrams on such a link layer, 6LoWPAN provides 486 an adaptation layer [RFC4944], [RFC6282], providing "Layer 2.5 487 fragmentation" in order to accommodate IPv6 packet transmissions over 488 the maximum IEEE 802.15.4 frame size of 127 octets, as well as 489 compressing the IPv6 header, reducing the overhead of the IPv6 header 490 from at least 40 octets to a minimum of 2 octets by way of 491 compression. Given the IEEE 802.15.4 frame size of 127 octets, a 492 maximum frame overhead of 25 octets and 21 octets for link layer 493 security [RFC4944], 81 octets remain for L2 payload. Further 494 subtracting 2 octets for the compressed IPv6 header leaves 79 octets 495 for L3 data payload if link-layer fragmentation is to be avoided. 497 The second L in LLN indicating Lossy [roll-charter], higher loss 498 rates than typically seen in IP networks are expected, rendering 499 fragmentation important to avoid, in particular because, as mentioned 500 above, the whole IP packet is dropped if only a single fragment is 501 lost. 503 DIO messages consist of a mandatory base object, facilitating DODAG 504 formation, and additional options for e.g., autoconfiguration and 505 network management. The base object contains two unused octets, 506 reserved for future use, resulting in two bytes of unnecessary zeros, 507 sent with each DIO message. The Prefix Information option, used for 508 automatic configuration of address, carries even four unused octets 509 in order to be compatible with IPv6 neighbor discovery. 511 6.1. Observations 513 [RFC4919] makes the following observation regarding using IP in 514 LoWPAN networks based on IEEE 802.15.4 frames: 516 Applications within LoWPANs are expected to originate small 517 packets. Adding all layers for IP connectivity should still allow 518 transmission in one frame, without incurring excessive 519 fragmentation and reassembly. Furthermore, protocols must be 520 designed or chosen so that the individual "control/protocol 521 packets" fit within a single 802.15.4 frame. Along these lines, 522 IPv6's requirement of sub-IP reassembly [...] may pose challenges 523 for low-end LoWPAN devices that do not have enough RAM or storage 524 for a 1280-octet packet. 526 In order to avoid the link-layer fragmentation and thus to adhere to 527 the recommendation in [RFC4919], each control packet of RPL must fit 528 into the remaining 79 octets of the 802.15.4 frame. While 79 octets 529 may seem to be sufficient to carry RPL control messages, consider the 530 following: RPL control messages are carried in ICMPv6, and the 531 mandatory ICMPv6 header consumes 4 octets. The DIO base another 24 532 octets. If link metrics are used, that consumes at least another 8 533 octets - and this is using a hop count metric; other metrics may 534 require more. The DODAG Configuration Object consumes up to a 535 further 16 octets, for a total of 52 octets. Adding a Prefix 536 Information Object for address configuration consumes another 32 537 octets, for a total of 84 octets - thus exceeding the 79 octets 538 available for L3 data payload and causing link-layer fragmentation of 539 such a DIO. As a point of reference, the ContikiRPL [rpl-contiki] 540 implementation includes both the DODAG Configuration option and the 541 Prefix Information option in all DIO messages. Any other options, 542 e.g., Route Information options indicating prefixes reachable through 543 the DODAG Root, increase the overhead and thus the probability of 544 fragmentation. 546 RPL may further increase the probability of link-layer fragmentation 547 of data traffic: for non-storing mode, RPL employs source-routing for 548 all downward traffic. [RFC6554] specifies the RPL Source Routing 549 header, which imposes a fixed overhead of 8 octets per IP packet 550 leaving 71 octets remaining from the link-layer MTU in order to 551 contain the whole IP packet into a single frame - from which must be 552 deducted a variable number of octets, depending on the length of the 553 route. With fewer octets available for data payload, RPL thus 554 increases the probability for link-layer fragmentation of also data 555 packets. This, in particular, for longer routes, e.g., in point-to- 556 point data traffic between sensors inside the LLN, where data traffic 557 transit through the DODAG Root and are then source-routed to the 558 destination. 560 Given the minimal packet size of LLNs, the routing protocol must 561 impose low (or no) overhead on data packets, hopefully independently 562 of the number of hops [RFC4919]. However, source-routing not only 563 causes increased overhead in the IP header, but also leads to a 564 variable available payload for data (depending on how long the source 565 route is). In point-to-point communication and when non-storing mode 566 is used for downward traffic, the source of a data packet will be 567 unaware of how many octets will be available for payload (without 568 incurring L2.5 fragmentation) when the DODAG Root relays the data 569 packet and add the source routing header. Thus, the source may 570 choose an inefficient size for the data payload: if the data payload 571 is large, it may exceed the link-layer MTU at the DODAG Root after 572 adding the source-routing header; on the other hand, if the data 573 payload is low, the network resources are not used efficiently, which 574 introduces more overhead and more frame transmissions. 576 Unless the DODAG root is the source of an IPv6 packet to be forwarded 577 through an RPL LLN, the IPv6 packet must be encapsulated in IPv6-in- 578 IPv6 tunneling, with the RPL extension added to the outer IPv6 579 header. Similarly, in non-storing mode, the original IPv6 packet 580 must be carried in IPv6-in-IPv6 tunneling, with the RPL routing 581 header added to the outer IPv6 header. Both of these mechanisms add 582 additional overhead, increasing the likelihood that link-layer 583 fragmentation will be required to deliver the IPv6 packet. In 584 addition, even IPv6 packets that are the minimum MTU size of 1280 585 octets will require IPv6 fragmentation to accommodate the RPL tunnel 586 and headers on a deployment using the RFC4944 specification to carry 587 IPv6 over IEEE 802.15.4, because RFC4944 defines the MTU for such 588 deployments to be 1280 octets. The ZigBee Alliance is considering 589 relaxing RFC4944 to use an MTU of 1360 octets in its specification 590 for IPv6 over IEEE 802.15.4 to accommodate 1280 octet IPv6 packets 591 with the required tunnel overhead without fragmentation. 593 7. The DAO Mechanism: Downward and Point-to-Point Routes 595 RPL specifies two distinct and incompatible "modes of operation" for 596 downward traffic: storing mode, where each RPL Router is assumed to 597 maintain routes to all destinations in its sub-DODAG, i.e., RPL 598 Routers that are "deeper down" in the DODAG, and non-storing mode, 599 where only the DODAG Root stores routes to destinations inside the 600 LLN, and where the DODAG Root employs strict source routing in order 601 to route data traffic to the destination RPL Router. 603 7.1. Observations 605 In addition to possible fragmentation, as occurs when using 606 potentially long source routing headers over a medium with a small 607 MTU - similar to what is discussed in Section 6 - the maximum length 608 of the source routing header [RFC6554] is limited to 136 octets, 609 including an 8 octet long header. As each IPv6 address has a length 610 of 16 octets, not more than 8 hops from the source to the destination 611 are possible for "raw IPv6". Using address compression (e.g., as 612 specified in [RFC4944]), the maximum route length may not exceed 64 613 hops. This excludes deployment of RPL for scenarios with long 614 "chain-like" topologies, such as traffic lights along a street. 616 In storing mode, each RPL Router has to store routes for destinations 617 in its sub-DODAG. This implies that, for RPL Routers near the DODAG 618 Root, the required storage is only bounded by the number of 619 destinations in the network. As RPL targets constrained devices with 620 little memory, but also has as ambition to be operating networks 621 consisting of thousands of routers [roll-charter], the storing 622 capacity on these RPL Routers may not be sufficient - or, at least, 623 the storage requirements in RPL Routers "near the DODAG Root" and 624 "far from the DODAG Root" is not homogenous, thus some sort of 625 administrative deployment, and continued administrative maintenance 626 of devices, as the network evolves, is needed. Indeed, 627 [rpl-eval-UCB] argues that practical experiences suggest that RPL in 628 storing mode, with RPL Routers having 10kB of RAM, should be limited 629 to networks of less than ~30 RPL Routers. Aggregation / 630 summarization of addresses may be advanced as a possible argument 631 that this issue is of little significance - Section 8 discusses why 632 such an argument does not apply. Moreover, if the LoWPAN adaption 633 layer [RFC4944] is used in the LLN, route aggregation is not possible 634 since the same /64 is applied across the entire network. 636 In short, the mechanisms in RPL force the choice between requiring 637 all RPL Routers to have sufficient memory to store route entries for 638 all destinations (storing mode) - or, suffer increased risk of 639 fragmentation, and thus loss of data packets, while consuming network 640 capacity by way of source routing through the DODAG Root (non-storing 641 mode). 643 In RPL, the "mode of operation" stipulates that either downward 644 routes are not supported (MOP=0), or that they are supported by way 645 of either storing or non-storing mode. In case downward routes are 646 supported, RPL does not provide any mechanism for discriminating 647 between which routes should or should not be maintained. In 648 particular, in order to calculate routes to a given destination, all 649 intermediaries between the DODAG Root and that destination must 650 themselves be reachable - effectively rendering downward routes in 651 RPL an "all-or-none" situation. In case a destination is 652 unreachable, all the DODAG Root may do is require all destinations to 653 re-issue their DAOs, by way of issuing a DIO with an increased DODAG 654 version number, possibly provoking a broadcast-storm-like situation. 655 This, in particular, as [RFC6550] does not specify DAO message 656 transmission constraints, nor any mechanism for adapting DAO emission 657 to the network capacity. 659 A final point on the DAO mechanism: RPL supports point-to-point 660 traffic only by way of relaying through the DODAG. In networks where 661 point-to-point traffic is no rare occurrence, this causes unduly long 662 routes (with possibly increased energy consumption, increased 663 probability of packet losses) as well as possibly congestion around 664 the DODAG Root. 666 8. Address Aggregation and Summarization 668 As indicated in Section 7, in storing mode, an RPL Router is expected 669 to be able to store routing entries for all destinations in its "sub- 670 DODAG", i.e., routing entries for all destinations in the network 671 where the route to the DODAG Root includes that RPL Router. 673 In the Internet, no single router stores explicit routing entries for 674 all destinations. Rather, IP addresses are assigned hierarchically, 675 such that an IP address does not only uniquely identify a network 676 interface, but also its topological location in the network, as 677 illustrated in Figure 2. All addresses with the same prefix are 678 reachable by way of the same router - which can, therefore, advertise 679 only that prefix. Other routers need only record a single routing 680 entry for that prefix, knowing that as the IP packet reaches the 681 router advertising that prefix, more precise routing information is 682 available. 684 .---. 685 | | 686 '---' 687 | 688 | 689 (a) 690 | 691 |1.x.x.x/8 692 | 693 (b) 694 / \ 695 1.1.x.x/16/ \ 1.2.x.x/16 696 / \ 697 .---. .---. 698 | c | | d | 699 '---' '---' 701 Figure 2: Address Hierarchies 703 Any aggregated routes require the use of a prefix shorter than /64, 704 and subsequent hierarchical assignment of prefixes down to a /64 (as 705 any RPL Router itself provides a /64 subnet to any hosts connected to 706 the router). 708 Moreover, if the 6lowpan adaption layer [RFC4944] is used in the LLN, 709 route aggregation is not possible since the same /64 is applied 710 across the entire network. 712 8.1. Observations 714 In RPL, each RPL Router acquires a number of parents, as described in 715 Section 3, from among which it selects one as its preferred parent 716 and, thus, next-hop on the route to the DODAG Root. RPL Routers 717 maintain a parent set containing possibly more than a single parent 718 so as to be able to rapidly select an alternative preferred parent, 719 should the previously selected such become unavailable. Thus 720 expected behavior is for an RPL Router to be able to change its point 721 of attachment towards the DODAG Root. If IP addresses are assigned 722 in a strictly hierarchical fashion, and if scalability of the routing 723 state maintained in storing mode is based on this hierarchy, then 724 this entails that each time an RPL Router changes its preferred 725 parent, it must also change its own IP address - as well as cause RPL 726 routers in its "sub-DODAG" to do the same. RPL does not specify 727 signaling for reconfiguring addresses in a sub-DODAG, while [RFC6550] 728 specifically allows for aggregation (e.g., in Section 18.2.6.: "[...] 729 it is recommended to delay the sending of DAO message to DAO parents 730 in order to maximize the chances to perform route aggregation"). 732 A slightly less strict hierarchy can be envisioned, where an RPL 733 Router can change its preferred parent without necessarily changing 734 addresses of itself and of its sub-DODAG, provided that its former 735 and new preferred parents both have the same preferred parent, and 736 have addresses hierarchically assigned from that - from the 737 "preferred grandparent". With reference to Figure 1, this could be e 738 changing its preferred parent from d to c, provided that both d and c 739 have b as preferred parent. Doing so would impose a restriction on 740 the parent-set selection, admitting only parents which have 741 themselves the same parent, losing redundancy in the network 742 connectivity. RPL does not specify rules for admitting only parents 743 with identical grand-parents into the parent set - although such is 744 not prohibited either, if the loss of redundancy is acceptable. 746 The DODAG Root incrementing the DODAG version number is the mechanism 747 by which RPL enables global reconfiguration of the network, 748 reconstructing the DODAG with (intended) more optimal routes. In 749 case of addressing hierarchies being enforced, so as to enable 750 aggregation, this will either restrict the ability for an optimal 751 DODAG construction, or will also have to trigger global address 752 autoconfiguration so as to ensure addressing hierarchies. 754 Finally, with IP addresses serving a dual role of an identifier of 755 both an end-point for communication and a topological location in the 756 network, changing the IP address of a device, so as to reflect a 757 change in network topology, also entails interrupting ongoing 758 communication to or through that device. Additional mechanisms 759 (e.g., a DNS-like system) mapping "communications identifiers" and 760 "IP addresses" are required. 762 9. Links Assumed Bi-Directional 764 Parents (and the preferred parent) are selected based on receipt of 765 DIOs, without verification of the ability for an RPL Router to 766 successfully communicate with the parent - i.e., without any 767 bidirectionality check of links. However, the basic use of links is 768 for "upward" routes, i.e., for the RPL Router to use a parent (the 769 preferred parent) as relay towards the DODAG Root - in the opposite 770 direction of the one in which the DIO was received. 772 9.1. Observations 774 Unidirectional links are no rare occurrence, such as is known from 775 wireless multi-hop networks. Preliminary results from a test-bed of 776 AMI (Automated Metering Infrastructure) devices using 950MHz radio 777 interfaces, and with a total of 22 links, show that 36% of these 778 links are unidirectional. If an RPL Router receives a DIO on such a 779 unidirectional link, and selects the originator of the DIO as parent, 780 which would be a bad choice: unicast traffic in the upward direction 781 would be lost. If the RPL Router had verified the bidirectionality 782 of links, it might have selected a better parent, to which it has a 783 bidirectional link. 785 10. Neighbor Unreachability Detection For Unidirectional Links 787 [RFC6550] suggests using Neighbor Unreachability Detection (NUD) 788 [RFC4861] to detect and recover from the situation of unidirectional 789 links between an RPL Router and its (preferred) parent(s). When, 790 e.g., an RPL Router tries (and fails) to actually use another RPL 791 Router for forwarding traffic, NUD is supposed engaged to detect and 792 prompt corrective action, e.g., by way of selecting an alternative 793 preferred parent. 795 NUD is based upon observing if a data packet is making forward 796 progress towards the destination, either by way of indicators from 797 upper-layer protocols (such as TCP and, though not called out in 798 [RFC4861], also from lower-layer protocols such as Link Layer ACKs ) 799 or - failing that - by unicast probing by way of transmitting a 800 unicast Neighbor Solicitation message and expecting that a solicited 801 Neighbor Advertisement message be returned. 803 10.1. Observations 805 An RPL Router may receive, transiently, a DIO from an RPL Router, 806 closer (in terms of rank) to the DODAG Root than any other RPL Router 807 from which a DIO has been received. Some, especially wireless, link 808 layers may exhibit different transmission characteristics between 809 multicast and unicast transmissions (such is the case for some 810 implementations of IEEE 802.11b, where multicast/broadcast 811 transmissions are sent at much lower bit-rates than are unicast; IEEE 812 802.11b is, of course, not suggested as a viable L2 for LLNs, but 813 serves to illustrate that such asymmetric designs exist), leading to 814 a (multicast) DIO being received from farther away than a unicast 815 transmission can reach. DIOs are sent (downward) using link-local 816 multicast, whereas the traffic flowing in the opposite direction 817 (upward) is unicast. Thus, a received (multicast) DIO may not be 818 indicative of useful unicast connectivity - yet, RPL might cause this 819 RPL Router to select this seemingly attractive RPL Router as its 820 preferred parent. This may happen both at initialization, or at any 821 time during the LLN lifetime as RPL allows attachment to a "better 822 parent" over the network lifetime. 824 A DODAG so constructed may appear stable and converged until such 825 time that unicast traffic is to be sent and, thus, NUD invoked. 826 Detecting only at that point that unicast connectivity is not 827 maintained, and causing local (and possibly global) repairs exactly 828 at that time, may lead to traffic not being deliverable. As 829 indicated in Section 8, if scalability is dependent on addresses 830 being assigned hierarchically, changing point-of-attachment may 831 entail more than switching preferred parent. 833 An RPL router may detect that its preferred parent is lost by way of 834 NUD, when trying to communicate to the DODAG Root. If that RPL 835 router has no other parents in its parent set, all it can do is wait: 836 RPL does not provide other mechanisms for an RPL router to react to 837 such an event. In the case where there is no downward traffic (i.e., 838 no data or acknowledgements are sent from the DODAG Root), neither 839 the DODAG Root nor the preferred parent, to which upward connectivity 840 was lost, will be able to detect and react to the event of 841 connectivity loss. 843 In other words, for upward traffic, the RPL routers that by way of 844 NUD detect connectivity loss, will be unable to act in order to 845 restore connectivity (e.g., by way of a signaling mechanism to the 846 DODAG Root, to request DODAG reconstruction by way of version number 847 increase). The RPL routers, which could react (the "preferred 848 parents") will for upward traffic not generate any traffic "downward" 849 allowing NUD to engage and detect connectivity loss. 851 It is worth noting that RPL is optimized for upward traffic 852 (multipoint-to-point traffic), and that this is exactly the type of 853 traffic where NUD is not applicable as a mechanism for detecting and 854 reacting to connectivity loss. 856 Also, absent all RPL Routers consistently advertising their 857 reachability through DAO messages, a protocol requiring bidirectional 858 flows between the communicating devices, such as TCP, will be unable 859 to operate. 861 Finally, upon having been notified by NUD that the "next hop" is 862 unreachable, an RPL Router must discard the preferred parent and 863 select another - hoping that this time, the preferred parent is 864 actually reachable. Also, if NUD indicates "no forward progress" 865 based on an upper-layer protocol, there is no guarantee that the 866 problem stems exclusively from the preferred parent being 867 unreachable. Indeed, it may be a problem farther ahead, possibly 868 outside the LLN, thus changing preferred parent will not alleviate 869 the situation. Moreover, using information from an upper-layer 870 protocol, e.g., to return TCP ACKs back to the source, requires 871 established downward routes in the DODAG (i.e., each RPL router needs 872 to send DAO messages to the DODAG Root, as described in Section 7). 874 Incidentally, this stems from a fundamental difference between "fixed 875 links in the Internet" and "wireless links": whereas the former, as a 876 rule, are reliable, predictable and with losses being rare 877 exceptions, the latter are characterized by frequent losses and 878 general unpredictability. 880 11. RPL Implementability and Complexity 882 RPL is designed to operate on "RPL Routers [...] with constraints on 883 processing power, memory, and energy (battery power)" [RFC6550]. 884 However, the 163 pages long specification of RPL, plus additional 885 specifications for routing headers [RFC6554], Trickle timer 886 [RFC6206], routing metrics [RFC6551] and objective function 887 [RFC6552], describes complex mechanisms (e.g., the upwards and 888 downward data traffic, a security solution, manageability of RPL 889 Routers, auxiliary functions for autoconfiguration of RPL Routers, 890 etc.), and provides no less than 9 message types, and 10 different 891 message options. 893 To give one example, the ContikiRPL implementation 894 (http://www.sics.se/contiki), which provides only storing mode and no 895 security features, consumes about 50 KByte of memory. Sensor 896 hardware, such as MSP430 sensor platforms, does not contain much more 897 memory than that, i.e., there may not be much space left to deploy 898 any application on the RPL Router. 900 11.1. Observations 902 Since RPL is intended as the routing protocol for LLNs, which covers 903 all the diverse applications requirements listed in [RFC5867], 905 [RFC5673], [RFC5826], [RFC5548], it is likely that (i) due to limited 906 memory capacity of the RPL Routers, and (ii) due to expensive 907 development cost of the routing protocol implementation, RPL 908 implementations will only support a partial set of features from the 909 specification, leading to non-interoperable implementations. 911 In order to accommodate for the verbose exchange format, route 912 stretching and source routing for point-to-point traffic, several 913 additional Internet-Drafts are being discussed for adoption in the 914 ROLL Working Group - adding complexity to an already complex 915 specification which, it is worth recalling, was intended to be of a 916 protocol for low-capacity devices. 918 12. Underspecification 920 While [RFC6550] is verbose in many parts, as described in Section 11, 921 some mechanisms are underspecified. 923 While for DIOs, the Trickle timer specifies a relatively efficient 924 and easy-to-understand timing for message transmission, the timing of 925 DAO transmission is not explicit. As each DAO may have a limited 926 lifetime, one "best guess" for implementers would be to send DAO 927 periodically, just before the life-time of the previous DAO expires. 928 Since DAOs may be lost, another "best guess" would be to send several 929 DAOs shortly one after the other in order to increase probability 930 that at least one DAO is successfully received. 932 The same underspecification applies for DAO-ACK messages: optionally, 933 on reception of a DAO, an RPL Router may acknowledge successful 934 reception by returning a DAO-ACK. Timing of DAO-ACK messages is 935 unspecified by RPL. 937 12.1. Observations 939 By not specifying details about message transmission intervals and 940 required actions when receiving DAO and DAO-ACKs, implementations may 941 exhibit a bad performance if not carefully implemented. Some 942 examples are: 944 1. If DAO messages are not sent in due time before the previous DAO 945 expires (or if the DAO is lost during transmission), the routing 946 entry will expire before it is renewed, leading to a possible 947 data traffic loss. 949 2. RPL does not specify to use jitter [RFC5148] (i.e., small random 950 delay for message transmissions). If DAOs are sent periodically, 951 adjacent RPL Routers may transmit DAO messages at the same time, 952 leading to link layer collisions. 954 3. In non-storing mode, the "piece-wise calculation" of routes to a 955 destination from which a DAO has been received, relies on 956 previous reception of DAOs from intermediate RPL Routers along 957 the route. If not all of these DAOs from intermediate RPL 958 Routers have been received, route calculation is not possible, 959 and DAO-ACKs or data traffic cannot be sent to that destination. 961 Other examples of underspecification include detection of 962 connectivity loss, as described in Section 10, as well as the local 963 repair mechanism, which may lead to loops and thus data traffic loss, 964 if not carefully implemented: an RPL Router discovering that all its 965 parents are unreachable, may - according to the RPL specification - 966 "detach" from the DODAG, i.e., increase its own rank to infinity. It 967 may then "poison" its sub-DODAG by advertising its infinite rank in 968 its DIOs. If, however, the RPL Router receives a DIO before it 969 transmits the "poisoned" DIO, it may attach to its own sub-DODAG, 970 creating a loop. If, instead, it had waited some time before 971 processing DIOs again, chances are it would have succeeded in 972 poisoning its sub-DODAG and thus avoided the loop. 974 13. Protocol Convergence 976 Trickle [RFC6206] is used by RPL to schedule transmission of DIO 977 messages, with the objective of minimizing the amount of transmitted 978 DIOs while ensuring a low convergence time of the network. The 979 theoretical behavior of Trickle is well understood, and the 980 convergence properties are well studied. Simulations of the 981 mechanism, such as documented [trickle-multicast], confirm these 982 theoretical studies. 984 In real-world environments, however, varying link qualities may cause 985 the algorithm to converge less well: frequent message losses entail 986 resets of the Trickle timer and more frequent and unpredicted message 987 emissions. 989 This has been observed, e.g., in an experimental testbed: 69 RPL 990 Routers (MSP430-based wireless sensor routers with IEEE 802.15.4, 991 using [rpl-contiki] IPv6 stack and RPL without downward routes; the 992 parameters of the Trickle timer were set to the implementation 993 defaults (minimum DIO interval: 4 s, DIO interval doublings: 8, 994 redundancy constant: 10) were positioned in a fixed grid topology. 995 This resulted in DODAGs being constructed with an average of 2.45 996 children per RPL Router and an average rank of 3.58. 998 In this small test network, the number of DIO messages emitted - 999 expectedly - spiked within the first ~10 seconds. Alas, rather than 1000 taper off to become zero (as the simulation studies would suggest), 1001 the DIO emission rate remained constant at about 70 DIOs per second. 1002 Details on this experiment can be found in [rpl-eval]. 1004 13.1. Observations 1006 The varying link quality in real-world environments results in 1007 frequent changes of the best parent, which triggers a reset of the 1008 Trickle timer and thus the emission of DIOs. Therefore Trickle does 1009 not converge as well for links that are fluctuating in quality as in 1010 theory. 1012 The resulting higher control overhead due to frequent DIO emission, 1013 leads to higher bandwidth and energy consumption as well as possibly 1014 to an increased number of collisions of frames, as observed in 1015 [trickle-multicast]. 1017 14. Loops 1019 [RFC6550] states that it "guarantees neither loop free route 1020 selection nor tight delay convergence times, but can detect and 1021 repair a loop as soon as it is used. RPL uses this loop detection to 1022 ensure that packets make forward progress [...] and trigger repairs 1023 when necessary". This implies that a loop may only then be detected 1024 and fixed when data traffic is sent through the network. 1026 In order to trigger a local repair, RPL relies on the "direction" 1027 information (with values "up" or "down"), contained in an IPv6 hop- 1028 by-hop option header from received a data packet. If an "upward" 1029 data packet is received by an RPL Router, but the previous hop of the 1030 packet is listed with a lower rank in the neighbor set, the RPL 1031 Router concludes that there must be a routing loop and it may 1032 therefore trigger a local repair. For downward traffic in non- 1033 storing mode, the DODAG Root can detect loops if the same router 1034 identifier (i.e., IP address) appears at least twice in the route 1035 towards a destination. 1037 14.1. Observations 1039 The reason for RPL to repair loops only when detected by a data 1040 traffic transmission is to reduce control traffic overhead. However, 1041 there are two problems in repairing loops only when so triggered: (i) 1042 the triggered local repair mechanism delays forward progress of data 1043 packets, increasing end-to-end delays, and (ii) the data packet has 1044 to be buffered during repair. 1046 (i) may seem as the lesser of the two problems, since in a number of 1047 applications, such as data acquisition in smart metering 1048 applications, an increased delay may be acceptable. However, for 1049 applications such as alarm signals or in home automation (e.g., a 1050 light switch), increased delay may be undesirable. 1052 As for (ii), RPL is supposed to run on LLN routers with "constraints 1053 on [...] memory" [RFC6550]; buffering incoming packets during the 1054 route repair may not be possible for all incoming data packets, 1055 leading to dropped packets. Depending on the transport protocol, 1056 these data packets must be retransmitted by the source or are 1057 definitely lost. 1059 If carefully implemented with respect to avoiding loops before they 1060 occur, the impact of the loop detection in RPL may be minimized. 1061 However, it can be observed that with current implementations of RPL, 1062 such as the ContikiRPL implementation, loops do occur - and, 1063 frequently. During the same experiments described in Section 13, a 1064 snapshot of the DODAG was made every ten seconds. In 74.14% of the 1065 4114 snapshots, at least one loop was observed. Further 1066 investigation revealed that in all these cases the DODAG was 1067 partitioned, and the loop occurred in the sub-DODAG that no longer 1068 had a connection to the DODAG Root. When the link to the only parent 1069 of an RPL Router breaks, the RPL Router may increase its rank and - 1070 when receiving a DIO from an RPL Router in its sub-DODAG - attach 1071 itself to its own sub-DODAG, thereby creating a loop - as detailed in 1072 Section 12.1. 1074 While it can be argued that the observed loops are harmless since 1075 they occur in a DODAG partition that has no connection to the DODAG 1076 Root, they show that the state of the network is inconsistent. Even 1077 worse, when the broken link re-appears, it is possible that in 1078 certain situations, the loop is only repaired when data traffic is 1079 sent, possibly leading to data loss (as described above). This can 1080 occur if the link to the previous parent is reestablished, but the 1081 rank of that previous parent has increased in the meantime. 1083 Another problem with the loop repair mechanism arises in non-storing 1084 mode when using only downward traffic: while the DODAG Root can 1085 easily detect loops (as described above), it has no direct means to 1086 trigger a local repair where the loop occurs. Indeed, it can only 1087 trigger a global repair by increasing the DODAG version number, 1088 leading to a Trickle timer reset and increased control traffic 1089 overhead in the network caused by DIO messages, and therefore a 1090 possible energy drain of the RPL Routers and congestion of the 1091 channel. 1093 Finally, loop detection for every data packet increases the 1094 processing overhead. RPL is targeted for deployments on very 1095 constrained devices with little CPU power, therefore a loop detection 1096 for every packet reduces available resources of the LLN router for 1097 other tasks (such as sensing). Moreover, each IPv6 packet needs to 1098 contain the "RPL Option for Carrying RPL Information in Data-Plane 1099 Datagrams" [RFC6553] in order to use loop detection (as well as 1100 determining the RPL instance), which in turn implies an extra IPv6 1101 header (and thus overhead) for IPv6-in-IPv6 tunneling. As this RPL 1102 option is a hop-by-hop option, it needs to be in an encapsulating 1103 IPv6-in-IPv6 tunnel and then regenerated at each hop. 1105 15. Security Considerations 1107 This document does currently not specify any security considerations. 1108 This document also does not provide any evaluation of the security 1109 mechanisms of RPL. 1111 16. IANA Considerations 1113 This document has no actions for IANA. 1115 17. Acknowledgements 1117 The authors would like to thank Matthias Philipp (INRIA) for his 1118 contributions to conducting many of the experiments, revealing or 1119 confirming the issues described in this document. 1121 Moreover, the authors would like to express their gratitude to Ralph 1122 Droms (Cisco) for his careful review of various versions of this 1123 document, for many long discussions, and for his considerable 1124 contributions to both the content and the quality of this document. 1126 18. Informative References 1128 [I-D.ietf-roll-terminology] 1129 Vasseur, JP., "Terminology in Low power And Lossy 1130 Networks", work in 1131 progress draft-ietf-roll-terminology-06, September 2011. 1133 [RFC2026] Bradner, S., "The Internet Standards Process -- Revision 1134 3", BCP 9, RFC 2026, October 1996. 1136 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 1137 (IPv6) Specification", RFC 2460, Decemer 1998. 1139 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 1140 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 1141 September 2007. 1143 [RFC4919] Kushalnagar, N., Montenegro, G., and C. Schumacher, "IPv6 1144 over Low-Power Wireless Personal Area Networks (6LoWPANs): 1145 Overview, Assumptions, Problem Statement, and Goals", 1146 RFC 4919, August 2007. 1148 [RFC4944] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, 1149 "Transmission of IPv6 Packets over IEEE 802.15.4 1150 Networks", RFC 4944, September 2007. 1152 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 1153 Considerations in Mobile Ad Hoc Networks (MANETs)", 1154 RFC 5148, February 2008. 1156 [RFC5548] Dohler, M., Watteyne, T., Winter, T., and D. Barthel, 1157 "Routing Requirements for Urban Low-Power and Lossy 1158 Networks", RFC 5548, May 2009. 1160 [RFC5673] Pister, K., Thubert, P., Dwars, S., and T. Phinney, 1161 "Industrial Routing Requirements in Low-Power and Lossy 1162 Networks", RFC 5673, October 2009. 1164 [RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation 1165 Routing Requirements in Low-Power and Lossy Networks", 1166 RFC 5826, April 2010. 1168 [RFC5867] Martocci, J., Mi, P., Riou, N., and W. Vermeylen, 1169 "Building Automation Routing Requirements in Low Power and 1170 Lossy Networks", RFC 5867, June 2010. 1172 [RFC6206] Levis, P., Clausen, T., Gnawali, O., and J. Ko, "The 1173 Trickle Algorithm", RFC 6206, March 2011. 1175 [RFC6282] Hui, J. and P. Thubert, "Compression Format for IPv6 1176 Datagrams over IEEE 802.15.4-Based Networks", RFC 6282, 1177 September 2011. 1179 [RFC6550] Winther, T., Thubert, P., Hui, J., Vasseur, J., Brandt, 1180 A., Kelsey, R., Levis, P., Piester, K., Struik, R., and R. 1181 Alexander, "RPL: IPv6 Routing Protocol for Low-Power and 1182 Lossy Networks", RFC 6550, March 2012. 1184 [RFC6551] Vasseur, J., Pister, K., Dejan, N., and D. Barthel, 1185 "Routing Metrics Used for Path Calculation in Low-Power 1186 and Lossy Networks", RFC 6551, March 2012. 1188 [RFC6552] Thubert, P., "Objective Function Zero for the Routing 1189 Protocol for Low-Power and Lossy Networks (RPL)", 1190 RFC 6552, March 2012. 1192 [RFC6553] Hui, J. and J. Vasseur, "The Routing Protocol for Low- 1193 Power and Lossy Networks (RPL) Option for Carrying RPL 1194 Information in Data-Plane Datagrams", RFC 6553, 1195 March 2012. 1197 [RFC6554] Hui, J., Vasseur, J., Culler, D., and V. Manral, "An IPv6 1198 Routing Header for Source Routes with the Routing Protocol 1199 for Low-Power and Lossy Networks (RPL)", RFC 6554, 1200 March 2012. 1202 [SEP2.0] Alliance, Zigbee., "ZigSmart Energy version 2.0 (SEP 2.0) 1203 draft 0.7", July 2011. 1205 [bidir] Clausen, T. and U. Herberg, "A Comparative Performance 1206 Study of the Routing Protocols LOAD and RPL with Bi- 1207 Directional Traffic in Low-power and Lossy Networks 1208 (LLN)", Proceedings of the Eighth ACM International 1209 Symposium on Performance Evaluation of Wireless Ad Hoc, 1210 Sensor, and Ubiquitous Networks (PE-WASUN), 2011. 1212 [ieee802154] 1213 Computer Society, IEEE., "IEEE Std. 802.15.4-2003", 1214 October 2003. 1216 [roll-charter] 1217 "ROLL Charter", 1218 web http://datatracker.ietf.org/wg/roll/charter/, 1219 February 2012. 1221 [rpl-contiki] 1222 Tsiftes, N., Eriksson, J., and A. Dunkels, "Low-Power 1223 Wireless IPv6 Routing with ContikiRPL", 1224 Proceedings Proceedings of the 9th ACM/IEEE International 1225 Conference on Information Processing in Sensor Networks 1226 (ISPN), 2011. 1228 [rpl-eval] 1229 Clausen, T., Herberg, U., and M. Philipp, "A Critical 1230 Evaluation of the IPv6 Routing Protocol for Low Power and 1231 Lossy Networks (RPL)", Proceedings of the 5th IEEE 1232 International Conference on Wireless & Mobile Computing, 1233 Networking & Communication (WiMob), 2011. 1235 [rpl-eval-UCB] 1236 Ko, J., Dawson-Haggerty, S., Culler, D., and A. Terzis, 1237 "Evaluating the Performance of RPL and 6LoWPAN in TinyOS", 1238 Proceedings of the Workshop on Extending the Internet to 1239 Low power and Lossy Networks (IP+SN), 2011. 1241 [trickle-multicast] 1242 Clausen, T. and U. Herberg, "Study of Multipoint-to-Point 1243 and Broadcast Traffic Performance in the 'IPv6 Routing 1244 Protocol for Low Power and Lossy Networks' (RPL)", 1245 Journal of Ambient Intelligence and Humanized Computing, 1246 2011. 1248 Authors' Addresses 1250 Thomas Clausen 1251 LIX, Ecole Polytechnique 1252 91128 Palaiseau Cedex, 1253 France 1255 Phone: +33 6 6058 9349 1256 Email: T.Clausen@computer.org 1257 URI: http://www.thomasclausen.org 1259 Axel Colin de Verdiere 1260 LIX, Ecole Polytechnique 1261 91128 Palaiseau Cedex, 1262 France 1264 Phone: +33 6 1264 7119 1265 Email: axel@axelcdv.com 1266 URI: http://www.axelcdv.com/ 1268 Jiazi Yi 1269 LIX, Ecole Polytechnique 1270 91128 Palaiseau Cedex, 1271 France 1273 Phone: +33 1 6933 4031 1274 Email: jiazi@jiaziyi.com 1275 URI: http://www.jiaziyi.com/ 1276 Ulrich Herberg 1277 Fujitsu Laboratories of America 1278 1240 E Arques Ave 1279 Sunnyvale, CA 94085 1280 USA 1282 Email: ulrich@herberg.name 1283 URI: http://www.herberg.name/ 1285 Yuichi Igarashi 1286 Hitachi, Ltd., Yokohama Research Laboratory 1288 Phone: +81 45 860 3083 1289 Email: yuichi.igarashi.hb@hitachi.com 1290 URI: http://www.hitachi.com/