idnits 2.17.1 draft-clausen-lln-rpl-experiences-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (March 9, 2012) is 4424 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-06) exists of draft-ietf-6man-rpl-option-02 == 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: 0 errors (**), 0 flaws (~~), 3 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: September 10, 2012 LIX, Ecole Polytechnique 6 U. Herberg 7 Fujitsu Laboratories of America 8 March 9, 2012 10 Experiences with RPL: IPv6 Routing Protocol for Low power and Lossy 11 Networks 12 draft-clausen-lln-rpl-experiences-01 14 Abstract 16 With RPL - the "IPv6 Routing Protocol for Low-power Lossy Networks" - 17 having been published as a Proposed Standard after a ~2-year 18 development cycle, this document presents an evaluation of the 19 resulting protocol, of its applicability, and of its limits. The 20 documents presents a selection of observations of the protocol 21 characteristics, exposes experiences acquired when producing various 22 prototype implementations of RPL, and presents results obtained from 23 testing this protocol - by way of network simulations, in network 24 testbeds and in deployments. The document aims at providing a better 25 understanding of possible weaknesses and limits of RPL, notably the 26 possible directions that further protocol developments should 27 explore, in order to address these. 29 Status of this Memo 31 This Internet-Draft is submitted in full conformance with the 32 provisions of BCP 78 and BCP 79. 34 Internet-Drafts are working documents of the Internet Engineering 35 Task Force (IETF). Note that other groups may also distribute 36 working documents as Internet-Drafts. The list of current Internet- 37 Drafts is at http://datatracker.ietf.org/drafts/current/. 39 Internet-Drafts are draft documents valid for a maximum of six months 40 and may be updated, replaced, or obsoleted by other documents at any 41 time. It is inappropriate to use Internet-Drafts as reference 42 material or to cite them other than as "work in progress." 44 This Internet-Draft will expire on September 10, 2012. 46 Copyright Notice 48 Copyright (c) 2012 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents 53 (http://trustee.ietf.org/license-info) in effect on the date of 54 publication of this document. Please review these documents 55 carefully, as they describe your rights and restrictions with respect 56 to this document. Code Components extracted from this document must 57 include Simplified BSD License text as described in Section 4.e of 58 the Trust Legal Provisions and are provided without warranty as 59 described in the Simplified BSD License. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 64 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 65 3. RPL Overview . . . . . . . . . . . . . . . . . . . . . . . . . 4 66 3.1. RPL Message Emission Timing - Trickle Timers . . . . . . . 6 67 4. Requirement Of DODAG Root . . . . . . . . . . . . . . . . . . 7 68 4.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 7 69 5. RPL Data Traffic Flows . . . . . . . . . . . . . . . . . . . . 8 70 5.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 9 71 6. Fragmentation Of RPL Control Messages And Data Packet . . . . 10 72 6.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 11 73 7. The DAO Mechanism: Downward and Point-to-Point Routes . . . . 13 74 7.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 13 75 8. Address Aggregation and Summarization . . . . . . . . . . . . 15 76 8.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 16 77 9. Links Assumed Bi-Directional . . . . . . . . . . . . . . . . . 17 78 9.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 17 79 10. Neighbor Unreachability Detection For Unidirectional Links . . 17 80 10.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 17 81 11. RPL Implementability and Complexity . . . . . . . . . . . . . 19 82 11.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 20 83 12. Underspecification . . . . . . . . . . . . . . . . . . . . . . 20 84 12.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 20 85 13. Protocol Convergence . . . . . . . . . . . . . . . . . . . . . 21 86 13.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 22 87 14. Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 88 14.1. Observations . . . . . . . . . . . . . . . . . . . . . . . 22 89 15. Security Considerations . . . . . . . . . . . . . . . . . . . 24 90 16. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 91 17. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 24 92 18. Informative References . . . . . . . . . . . . . . . . . . . . 24 93 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 27 95 1. Introduction 97 RPL - the "Routing Protocol for Low Power and Lossy Networks" 98 [I-D.ietf-roll-rpl] - is a proposal for an IPv6 routing protocol for 99 Low-power Lossy Networks (LLNs), by the ROLL Working Group in the 100 Internet Engineering Task Force (IETF). This routing protocol is 101 intended to be the IPv6 routing protocol for LLNs and sensor 102 networks, applicable in all kinds of deployments and applications of 103 LLNs. 105 The objective of RPL and ROLL is to provide routing in networks which 106 "comprise up to thousands of nodes" [roll-charter], where the 107 majority of the nodes have very constrained resources 108 [I-D.ietf-roll-terminology], and where handling mobility is not an 109 explicit design criteria [RFC5867], [RFC5826], [RFC5673], [RFC5548]. 111 [roll-charter] states that "Typical traffic patterns are not simply 112 unicast flows (e.g. in some cases most if not all traffic can be 113 point to multipoint)", and [I-D.ietf-roll-terminology] further 114 categorizes the supported traffic types into "upward" traffic from 115 sensors to a collection sink or LBR (LLN Border Router) (denoted 116 multipoint-to-point), "downward" traffic from the collection sink or 117 LBR to the sensors (denoted point-to-multipoint) and traffic from 118 "sensor to sensor" (denoted point-to-point traffic), and establishes 119 this terminology for these traffic types. Thus, while the target for 120 RPL and ROLL is to support all of these traffic types, the emphasis 121 among these, according to [roll-charter], appears to be to optimize 122 for multipoint-to-point traffic, while also supporting point-to- 123 multipoint and point-to-point traffic. 125 As of early 2011, RPL has been approved by the IESG, for publication 126 as a "Proposed Standard" RFC (Request for Comments). The implication 127 of a protocol being labeled "Proposed Standard" is that it is 128 considered generally stable: well-understood and community reviewed, 129 no known design issues pending, and with some community support 130 [RFC2026]. 132 "Proposed Standard" is, however, only the first step on the Standards 133 Track, and it is thus opportune to document experiences with the 134 protocol, in order to understand which aspects of it necessitate 135 further investigations, and in order to identify possibly weak points 136 which may restrict the deployment scope of the protocol. This 137 document has as objective to document such experiences with and 138 observations of RPL, in the spirit of better understanding its 139 characteristics and limits. 141 2. Terminology 143 This document uses the terminology and notation defined in 144 [I-D.ietf-roll-rpl]. 146 Additionally, this document uses terminology from 147 [I-D.ietf-roll-terminology], specifically the terms defined for the 148 traffic types "MP2P" (Multipoint-to-Point), "P2P" (Point To Point) 149 and "P2MP" (Point-to-Multipoint). 151 Finally, this document introduces the following terminology: 153 RPL Router - A device, running the RPL protocol, as specified by 154 [I-D.ietf-roll-rpl]. 156 3. RPL Overview 158 The basic construct in RPL is a "Destination Oriented Directed 159 Acyclic Graph" (DODAG), depicted in Figure 1, with a single RPL 160 router acting as DODAG root. The DODAG root has responsabilities in 161 addition to those of other RPL routers, including for initiating, 162 configuring, and managing the DODAG, and (in some cases) acting as a 163 central relay for traffic through and between RPL routers in the LLN. 165 (s) 166 ^ ^ ^ 167 / | \ 168 (a) | (b) 169 ^ (c) ^ 170 / ^ (d) 171 (f) | ^ ^ 172 (e)--/ \ 173 (g) 175 Figure 1: RPL DODAG 177 In an LLN, in which RPL has converged to a stable state, each RPL 178 Router has identified a stable set of parents, each of which is a 179 potential next-hop on a route towards the DODAG root. One of the 180 parents is selected as preferred parent. Each RPL Router, which is 181 part of a DODAG (i.e., which has selected parents and a preferred 182 parent) will emit DODAG Information Object (DIO) messages, using 183 link-local multicast, indicating its respective rank in the DODAG 184 (i.e., distance to the DODAG Root according to some metric(s), in the 185 simplest form hop-count). Upon having received a (number of such) 186 DIO messages, an RPL Router will calculate its own rank such that it 187 is greater than the rank of each of its parents, select a preferred 188 parent and then itself start emitting DIO messages. 190 DODAG formation thus starts at the DODAG Root (initially, the only 191 RPL Router which is part of a DODAG), and spreads gradually to cover 192 the whole LLN as DIOs are received, parents and preferred parents are 193 selected, and further RPL Routers participate in the DODAG. The 194 DODAG Root also includes, in DIO messages, a DODAG Configuration 195 Object, describing common configuration attributes for all RPL 196 Routers in that network - including their mode of operation, timer 197 characteristics etc. RPL Routers in a DODAG include a verbatim copy 198 of the last received DODAG Configuration Object in their DIO 199 messages, permitting also such configuration parameters propagating 200 through the network. 202 As a Distance Vector protocol, RPL restricts the ability for an RPL 203 Router to change rank. An RPL Router can freely assume a smaller 204 rank than previously advertised (i.e., logically move closer to the 205 DODAG Root) if it discovers a parent advertising a lower rank, and 206 must then disregard all previous parents of ranks higher than the 207 router's new rank. The ability for an RPL Router to assume a greater 208 rank (i.e., logically move farther from the DODAG Root) than 209 previously advertised is restricted in order to avoid count-to- 210 infinity problems. The DODAG Root can trigger "global recalculation" 211 of the DODAG by increasing a sequence number, DODAG version, in DIO 212 messages. 214 The DODAG so constructed is used for installing routes: the 215 "preferred parent" of an RPL Router can serve as a default route 216 towards the DODAG Root, and the DODAG Root can embed in its DIO 217 messages the destination prefixes, included by DIOs generated by RPL 218 Routers through the LLN, to which connectivity is provided by the 219 DODAG Root. Thus, RPL by way of DIO generation provides "upward 220 routes" or "multipoint-to-point routes" from the sensors inside the 221 LLN and towards the DODAG Root (and, possibly, to destinations 222 reachable through the DODAG Root). 224 "Downward routes" are enabled by having sensors issue Destination 225 Advertisement Object (DAO) messages, propagating as unicast via 226 preferred parents towards the DODAG Root. These describe which 227 prefixes belong to, and can be reached via, which RPL Router. In a 228 network, all RPL Routers must operate in either of storing mode or 229 non-storing mode, specified by way of a "Mode of Operation" (MOP) 230 flag in the DODAG Configuration Object from the DODAG Root. 231 Depending on the MOP, DAO messages are forwarded differently towards 232 the DODAG Root: 234 o In "non-storing mode", an RPL Router originates a DAO messages, 235 advertising one or more of its parents, and unicasts these to the 236 DODAG Root. Once the DODAG Root has received DAOs from an RPL 237 Router, and from all RPL Routers on the route between it and the 238 DODAG Root, it can use source routing for reaching advertised 239 destinations inside the LLN. 241 o In "storing mode", each RPL Router on the route between the 242 originator of a DAO and the DODAG Root records a route to the 243 prefixes advertised in the DAO, as well as the next-hop towards 244 these (the RPL Router, from which the DAO was received), then 245 forwards the DAO to its preferred parent. 247 "Point-to-point routes", for communication between devices inside the 248 LLN and where neither of the communicating devices are the DODAG 249 Root, are as default supported by having the source sensor transmit a 250 data packet, via its default route to the DODAG Root (i.e., using the 251 upward routes), which will then, depending on the "Mode of Operation" 252 for the DODAG, either add a source-route to the received data packet 253 for reaching the destination sensor (downward routes in non-storing 254 mode), or simply use hop-by-hop routing (downward routes in storing 255 mode) for forwarding the data packet. In the case of storing mode, 256 if the source and the destination for a point-to-point data packet 257 share a common ancestor other than the DODAG Root, a downward route 258 may be available in an RPL Router (and, thus, used) before the data 259 packet reaches the DODAG Root. 261 3.1. RPL Message Emission Timing - Trickle Timers 263 RPL message generation is timer-based, with the DODAG Root being able 264 to configure back-off of message emission intervals using Trickle 265 [RFC6206]. Trickle, as used in RPL, stipulates that an RPL Router 266 transmits a DIO "every so often" - except if receiving a number of 267 DIOs from neighbor RPL routers, enabling the RPL Router to determine 268 if its DIO transmission is redundant. 270 When an RPL Router transmits a DIO, there are two possible outcomes: 271 either every neighbor RPL Router that hears the message finds that 272 the information contained is consistent with its own state (i.e., the 273 received DODAG version number corresponds with that which the RPL 274 Router has recorded, and no better rank is advertised than that which 275 is recorded in the parent set) - or, a recipient RPL Router detects 276 that either the sender of the DIO or itself has out-of-date 277 information. If the sender has out-of-date information, then the 278 recipient RPL Router schedules transmission of a DIO to update this 279 information. If the recipient RPL Router has out-of-date 280 information, then it updates based on the information received in the 281 DIO. 283 With Trickle, an RPL Router will schedule emission of a DIO at some 284 time, t, in the future. When receiving a DIO containing information 285 consistent with its own information, the RPL Router will record that 286 "redundant information has been received" by incrementing a 287 redundancy counter, c. At the time t, if c is below some "redundancy 288 threshold", then it transmits its DIO. Otherwise, transmission of a 289 DIO at this time is suppressed, c is reset and a new t is selected to 290 twice as long time in the future - bounded by a pre-configured 291 maximum value for t. If, on the other hand, the RPL Router has 292 received an out-of-date DIO from one of its neighbors, t is reset to 293 a pre-configured minimum value and c is set to zero. In both cases, 294 at the expiration of t, the RPL Router will verify if c is below the 295 "redundancy threshold" and if so transmit - otherwise, increase t and 296 stay quiet. 298 4. Requirement Of DODAG Root 300 As indicated in Section 3, the DODAG Root has both a special 301 responsibility and is subject to special requirements. The DODAG 302 Root is responsible for determining and maintaining the configuration 303 parameters for the DODAG, and for initiating DIO emissions. 305 The DODAG Root is also responsible (in both storing and non-storing 306 mode) for being able to, when downward routes are supported, maintain 307 sufficient topological information to be able to construct routes to 308 all destinations in the network. 310 When operating in non-storing mode, this entails that the DODAG Root 311 is required to have sufficient memory and sufficient computational 312 resources to be able to record a network graph containing all routes 313 from itself and to all destinations and calculate routes. 315 When operating in storing mode, this entails that the DODAG Root 316 needs enough memory to keep a list of all RPL Routers in the RPL 317 instance, and a next hop for each of those RPL routers. If 318 aggregation is used, the memory requirements can be reduced in 319 storing mode (see Section 8 for observations about aggregation in 320 RPL). 322 The DODAG Root is also required to have sufficient energy available 323 so as to be able to ensure the relay functions required. This, 324 especially for non-storing mode, where all data packets transit 325 through the DODAG Root. 327 4.1. Observations 329 In a given deployment, select RPL Routers can be provisioned with the 330 required energy, memory and computational resources so as to serve as 331 DODAG Roots, and be administratively configured as such - with the 332 remainder of the RPL routers in the network being of typically lesser 333 capacity. [rpl-eval-UCB] indicates that, in storing mode, a TelosB 334 mote with 10KB of RAM has sufficient memory to support up to about 30 335 RPL Routers in the LLN - in a larger network (in storing or non- 336 storing mode, both) the DODAG Root would require at least that much, 337 likely much more, memory. In non-storing mode, the resource 338 requirements on the DODAG Root are likely much higher than in storing 339 mode, as the DODAG Root needs to store a network graph containing 340 complete routes to all destinations in the RPL instance, in order to 341 calculate the routing table (whereas in storing mode, only the next 342 hop for each destination in the RPL instance needs to be stored, and 343 aggregation may be used to further reduce the resource requirements). 345 RPL Routers provisioned with resources to act as DODAG Roots, and 346 administratively configured to act as such, represent a single point 347 of failure in the network. As the memory requirements for the DODAG 348 Root and for other RPL Routers are substantially different, unless 349 all RPL Routers are provisioned with resources (memory, energy, ...) 350 to act as DODAG Roots, effectively if the designated DODAG Root 351 fails, the network fails and RPL is unable to operate. Even if 352 electing another RPL Router as temporary DODAG root (e.g., for 353 forming a "Floating" DODAG) for providing internal connectivity 354 between RPL Routers, this router may not have the necessary resources 355 to satisfy this role as (temporary) DODAG Root. 357 Thus, although in principle RPL provides, by way of "Floating 358 DODAGs", protocol mechanisms for establishing a DODAG for providing 359 internal connectivity even in case of failure of the administratively 360 provisioned DODAG Root - especially in non-storing mode - it is 361 unlikely that any RPL Routers not explicitly provisioned as DODAG 362 Roots will have sufficient resources to undertake this task. 364 Another possible LLN scenario is that only internal point-to-point 365 connectivity is sought, and no RPL Router has a more "central" role 366 than any other - a self-organizing LLN. Requiring special 367 provisioning of a specific "super-node" as DODAG Root is both 368 unnecessary and undesirable. 370 5. RPL Data Traffic Flows 372 RPL makes a-priori assumptions of data traffic types, and explicitly 373 defines three such [I-D.ietf-roll-terminology] traffic types: sensor- 374 to-root data traffic (multipoint-to-point) is predominant, root-to- 375 sensor data traffic (point-to-multipoint) is rare and sensor-to- 376 sensor (point-to-point) data traffic is extremely rare. While not 377 specifically called out thus in [I-D.ietf-roll-rpl], the resulting 378 protocol design, however, reflects these assumptions in that the 379 mechanism constructing multipoint-to-point routes is efficient in 380 terms of control traffic generated and state required, point-to- 381 multipoint route construction much less so - and point-to-point 382 routes subject to potentially significant route stretch (routes going 383 through the DODAG Root in non-storing mode) and over-the-wire 384 overhead from using source routing (from the DODAG Root to the 385 destination) (see Section 7) - or, in case of storing mode, 386 considerable memory requirements in all LLN routers inside the 387 network (see Section 7). 389 An RPL Router selects from among its parents a "preferred parent", to 390 serve as a default route towards the DODAG Root (and to prefixes 391 advertised by the DODAG Root). Thus, RPL provides "upward routes" or 392 "multipoint-to-point routes" from the RPL Routers below the DODAG 393 Root and towards the DODAG Root. 395 An RPL Router which wishes to act as a destination for data traffic 396 ("downward routes" or "point-to-multipoint") issues DAOs upwards in 397 the DODAG towards the DODAG Root, describing which prefixes belong 398 to, and can be reached via, that RPL Router. 400 Point-to-Point routes between RPL Routers below the DODAG Root are 401 supported by having the source RPL Router transmit, via its default 402 route, data traffic towards the DODAG Root. In non-storing mode, the 403 data traffic will reach the DODAG Root, which will reflect the data 404 traffic downward towards the destination RPL Router, adding a strict 405 source routing header indicating the precise route for the data 406 traffic to reach the intended destination RPL Router. In storing 407 mode, the source and the destination may possibly (although, may also 408 not) have a common ancestor other than the DODAG Root, which may 409 provide a downward route to the destination before data traffic 410 reaching the DODAG Root. 412 5.1. Observations 414 The data traffic characteristics, assumed by RPL, do not represent a 415 universal distribution of traffic types in LLNs: 417 o There are scenarios where sensor-to-sensor traffic is a more 418 common occurrence, documented, e.g., in [RFC5867] ("Building 419 Automation Routing Requirements in Low Power and Lossy Networks"). 421 o There are scenarios, where all traffic is bi-directional, e.g., in 422 case sensor devices in the LLN are, in majority, "actively read": 423 a request is issued by the DODAG Root to a specific sensor, and 424 the sensor value is expected returned. In fact, unless all 425 traffic in the LLN is unidirectional, without acknowledgements 426 (e.g., as in UDP), and no control messages (e.g., for service 427 discovery) or other data packets are sent from the DODAG Root to 428 the RPL Routers, traffic will be bi-directional. As an example, 429 the ZigBee Alliance SEP 2.0 specification [SEP2.0] describes the 430 use of HTTP over TCP over ZigBeeIP, between RPL Routers and the 431 DODAG Root - and with the use of TCP inherently causing 432 bidirectional traffic by way of data-packets and their 433 corresponding acknowledgements. 435 For the former, all sensor-to-sensor routes include the DODAG Root, 436 possibly causing congestions on the communication medium near the 437 DODAG Root, and draining energy from the intermediate RPL Routers on 438 an unnecessarily long route. If sensor-to-sensor traffic is common, 439 RPL Routers near the DODAG Root will be particularly solicited as 440 relays, especially in non-storing mode. 442 For the latter, as there is no provision for on-demand generation of 443 routing information from the DODAG Root to a proper subset of all RPL 444 Routers, each RPL Router (besides the Root) is required to generate 445 DAOs. In particular in non-storing mode, each RPL Router will 446 unicast a DAO to the DODAG Root (whereas in storing mode, the DAOs 447 propagate upwards towards the Root). The effects of the requirement 448 to establish downward routes to all RPL Routers are: 450 o Increased memory and processing requirements at the DODAG Root (in 451 particular in non-storing mode) and in RPL routers near the DODAG 452 Root (in storing mode). 454 o A considerable control traffic overhead [bidir], in particular at 455 and near the DODAG Root, therefore: 457 o Potentially congested channels, and: 459 o Energy drain from the RPL Routers. 461 6. Fragmentation Of RPL Control Messages And Data Packet 463 The link technologies in LLNs often use small frames [RFC4919], which 464 are unable to carry the minimum 1280 octet IP packet in a single 465 frame [RFC2460]. In such LLNs, link-specific fragmentation and 466 reassembly of IP packets at a layer below IPv6 is used to transport 467 larger IP packets, providing the required minimum 1280 octet MTU. 469 When link-layer fragmentation is applied, the IP packet has to be 470 reassembled at every hop. Every fragment must be received 471 successfully by the receiving node, or the entire IP packet is lost. 472 Moreover, the additional link-layer frame overhead (and IPv6 Fragment 473 header overhead in case of IP fragmentation) for each of the 474 fragments increases the capacity required from the medium, and may 475 consume more energy for transmitting a higher number of frames on the 476 network interface. 478 RPL is an IPv6 routing protocol, designed to operate on constrained 479 link layers, such as IEEE 802.15.4 [ieee802154], with a maximum frame 480 size of 127 bytes - a much smaller value than the specified minimum 481 MTU of 1280 bytes for IPv6 [RFC2460]. Reducing the need of 482 fragmentation of IP datagrams on such a link layer, 6LoWPAN provides 483 an adaptation layer [RFC4944], [RFC6282], providing "Layer 2.5 484 fragmentation" in order to accommodate IPv6 packet transmissions over 485 the maximum IEEE 802.15.4 frame size of 127 octets, as well as 486 compressing the IPv6 header, reducing the overhead of the IPv6 header 487 from at least 40 octets to a minimum of 2 octets by way of 488 compression. Given the IEEE 802.15.4 frame size of 127 octets, a 489 maximum frame overhead of 25 octets and 21 octets for link layer 490 security [RFC4944], 81 octets remain for L2 payload. Further 491 subtracting 2 octets for the compressed IPv6 header leaves 79 octets 492 for L3 data payload if link-layer fragmentation is to be avoided. 494 The second L in LLN indicating Lossy [roll-charter], higher loss 495 rates than typically seen in IP networks are expected, rendering 496 fragmentation important to avoid, in particular because, as mentioned 497 above, the whole IP packet is dropped if only a single fragment is 498 lost. 500 DIO messages consist of a mandatory base object, facilitating DODAG 501 formation, and additional options for e.g., autoconfiguration and 502 network management. The base object contains two unused octets, 503 reserved for future use, resulting in two bytes of unnecessary zeros, 504 sent with each DIO message. The Prefix Information option, used for 505 automatic configuration of address, carries even four unused octets 506 in order to be compatible with IPv6 neighbor discovery. 508 6.1. Observations 510 [RFC4919] makes the following observation regarding using IP in 511 LoWPAN networks based on IEEE 802.15.4 frames: 513 Applications within LoWPANs are expected to originate small 514 packets. Adding all layers for IP connectivity should still allow 515 transmission in one frame, without incurring excessive 516 fragmentation and reassembly. Furthermore, protocols must be 517 designed or chosen so that the individual "control/protocol 518 packets" fit within a single 802.15.4 frame. Along these lines, 519 IPv6's requirement of sub-IP reassembly [...] may pose challenges 520 for low-end LoWPAN devices that do not have enough RAM or storage 521 for a 1280-octet packet. 523 In order to avoid the link-layer fragmentation and thus to adhere to 524 the recommendation in [RFC4919], each control packet of RPL must fit 525 into the remaining 79 octets of the 802.15.4 frame. While 79 octets 526 may seem to be sufficient to carry RPL control messages, consider the 527 following: RPL control messages are carried in ICMPv6, and the 528 mandatory ICMPv6 header consumes 4 octets. The DIO base another 24 529 octets. If link metrics are used, that consumes at least another 8 530 octets - and this is using a hop count metric; other metrics may 531 require more. The DODAG Configuration Object consumes up to a 532 further 16 octets, for a total of 52 octets. Adding a Prefix 533 Information Object for address configuration consumes another 32 534 octets, for a total of 84 octets - thus exceeding the 79 octets 535 available for L3 data payload and causing link-layer fragmentation of 536 such a DIO. As a point of reference, the ContikiRPL [rpl-contiki] 537 implementation includes both the DODAG Configuration option and the 538 Prefix Information option in all DIO messages. Any other options, 539 e.g., Route Information options indicating prefixes reachable through 540 the DODAG Root, increase the overhead and thus the probability of 541 fragmentation. 543 RPL may further increase the probability of link-layer fragmentation 544 of data traffic: for non-storing mode, RPL employs source-routing for 545 all downward traffic. [I-D.ietf-6man-header] specifies the RPL 546 Source Routing header, which imposes a fixed overhead of 8 octets per 547 IP packet leaving 71 octets remaining from the link-layer MTU in 548 order to contain the whole IP packet into a single frame - from which 549 must be deducted a variable number of octets, depending on the length 550 of the route. With fewer octets available for data payload, RPL thus 551 increases the probability for link-layer fragmentation of also data 552 packets. This, in particular, for longer routes, e.g., in point-to- 553 point data traffic between sensors inside the LLN, where data traffic 554 transit through the DODAG Root and are then source-routed to the 555 destination. 557 Given the minimal packet size of LLNs, the routing protocol must 558 impose low (or no) overhead on data packets, hopefully independently 559 of the number of hops [RFC4919]. However, source-routing not only 560 causes increased overhead in the IP header, but also leads to a 561 variable available payload for data (depending on how long the source 562 route is). In point-to-point communication and when non-storing mode 563 is used for downward traffic, the source of a data packet will be 564 unaware of how many octets will be available for payload (without 565 incurring L2.5 fragmentation) when the DODAG Root relays the data 566 packet and add the source routing header. Thus, the source may 567 choose an inefficient size for the data payload: if the data payload 568 is large, it may exceed the link-layer MTU at the DODAG Root after 569 adding the source-routing header; on the other hand, if the data 570 payload is low, the network resources are not used efficiently, which 571 introduces more overhead and more frame transmissions. 573 Unless the DODAG root is the source of an IPv6 packet to be forwarded 574 through an RPL LLN, the IPv6 packet must be encapsulated in IPv6-in- 575 IPv6 tunneling, with the RPL extension added to the outer IPv6 576 header. Similarly, in non-storing mode, the original IPv6 packet 577 must be carried in IPv6-in-IPv6 tunneling, with the RPL routing 578 header added to the outer IPv6 header. Both of these mechanisms add 579 additional overhead, increasing the likelihood that link-layer 580 fragmentation will be required to deliver the IPv6 packet. In 581 addition, even IPv6 packets that are the minimum MTU size of 1280 582 octets will require IPv6 fragmentation to accommodate the RPL tunnel 583 and headers on a deployment using the RFC4944 specification to carry 584 IPv6 over IEEE 802.15.4, because RFC4944 defines the MTU for such 585 deployments to be 1280 octets. The ZigBee Alliance is considering 586 relaxing RFC4944 to use an MTU of 1360 octets in its specification 587 for IPv6 over IEEE 802.15.4 to accommodate 1280 octet IPv6 packets 588 with the required tunnel overhead without fragmentation. 590 7. The DAO Mechanism: Downward and Point-to-Point Routes 592 RPL specifies two distinct and incompatible "modes of operation" for 593 downward traffic: storing mode, where each RPL Router is assumed to 594 maintain routes to all destinations in its sub-DODAG, i.e., RPL 595 Routers that are "deeper down" in the DODAG, and non-storing mode, 596 where only the DODAG Root stores routes to destinations inside the 597 LLN, and where the DODAG Root employs strict source routing in order 598 to route data traffic to the destination RPL Router. 600 7.1. Observations 602 In addition to possible fragmentation, as occurs when using 603 potentially long source routing headers over a medium with a small 604 MTU - similar to what is discussed in Section 6 - the maximum length 605 of the source routing header [I-D.ietf-6man-header] is limited to 136 606 octets, including an 8 octet long header. As each IPv6 address has a 607 length of 16 octets, not more than 8 hops from the source to the 608 destination are possible for "raw IPv6". Using address compression 609 (e.g., as specified in [RFC4944]), the maximum route length may not 610 exceed 64 hops. This excludes deployment of RPL for scenarios with 611 long "chain-like" topologies, such as traffic lights along a street. 613 In storing mode, each RPL Router has to store routes for destinations 614 in its sub-DODAG. This implies that, for RPL Routers near the DODAG 615 Root, the required storage is only bounded by the number of 616 destinations in the network. As RPL targets constrained devices with 617 little memory, but also has as ambition to be operating networks 618 consisting of thousands of routers [roll-charter], the storing 619 capacity on these RPL Routers may not be sufficient - or, at least, 620 the storage requirements in RPL Routers "near the DODAG Root" and 621 "far from the DODAG Root" is not homogenous, thus some sort of 622 administrative deployment, and continued administrative maintenance 623 of devices, as the network evolves, is needed. Indeed, 624 [rpl-eval-UCB] argues that practical experiences suggest that RPL in 625 storing mode, with RPL Routers having 10kB of RAM, should be limited 626 to networks of less than ~30 RPL Routers. Aggregation / 627 summarization of addresses may be advanced as a possible argument 628 that this issue is of little significance - Section 8 discusses why 629 such an argument does not apply. Moreover, if the LoWPAN adaption 630 layer [RFC4944] is used in the LLN, route aggregation is not possible 631 since the same /64 is applied across the entire network. 633 In short, the mechanisms in RPL force the choice between requiring 634 all RPL Routers to have sufficient memory to store route entries for 635 all destinations (storing mode) - or, suffer increased risk of 636 fragmentation, and thus loss of data packets, while consuming network 637 capacity by way of source routing through the DODAG Root (non-storing 638 mode). 640 In RPL, the "mode of operation" stipulates that either downward 641 routes are not supported (MOP=0), or that they are supported by way 642 of either storing or non-storing mode. In case downward routes are 643 supported, RPL does not provide any mechanism for discriminating 644 between which routes should or should not be maintained. In 645 particular, in order to calculate routes to a given destination, all 646 intermediaries between the DODAG Root and that destination must 647 themselves be reachable - effectively rendering downward routes in 648 RPL an "all-or-none" situation. In case a destination is 649 unreachable, all the DODAG Root may do is require all destinations to 650 re-issue their DAOs, by way of issuing a DIO with an increased DODAG 651 version number, possibly provoking a broadcast-storm-like situation. 652 This, in particular, as [I-D.ietf-roll-rpl] does not specify DAO 653 message transmission constraints, nor any mechanism for adapting DAO 654 emission to the network capacity. 656 A final point on the DAO mechanism: RPL supports point-to-point 657 traffic only by way of relaying through the DODAG. In networks where 658 point-to-point traffic is no rare occurrence, this causes unduly long 659 routes (with possibly increased energy consumption, increased 660 probability of packet losses) as well as possibly congestion around 661 the DODAG Root. 663 8. Address Aggregation and Summarization 665 As indicated in Section 7, in storing mode, an RPL Router is expected 666 to be able to store routing entries for all destinations in its "sub- 667 DODAG", i.e., routing entries for all destinations in the network 668 where the route to the DODAG Root includes that RPL Router. 670 In the Internet, no single router stores explicit routing entries for 671 all destinations. Rather, IP addresses are assigned hierarchically, 672 such that an IP address does not only uniquely identify a network 673 interface, but also its topological location in the network, as 674 illustrated in Figure 2. All addresses with the same prefix are 675 reachable by way of the same router - which can, therefore, advertise 676 only that prefix. Other routers need only record a single routing 677 entry for that prefix, knowing that as the IP packet reaches the 678 router advertising that prefix, more precise routing information is 679 available. 681 .---. 682 | | 683 '---' 684 | 685 | 686 (a) 687 | 688 |1.x.x.x/8 689 | 690 (b) 691 / \ 692 1.1.x.x/16/ \ 1.2.x.x/16 693 / \ 694 .---. .---. 695 | c | | d | 696 '---' '---' 698 Figure 2: Address Hierarchies 700 Any aggregated routes require the use of a prefix shorter than /64, 701 and subsequent hierarchical assignment of prefixes down to a /64 (as 702 any RPL Router itself provides a /64 subnet to any hosts connected to 703 the router). 705 Moreover, if the 6lowpan adaption layer [RFC4944] is used in the LLN, 706 route aggregation is not possible since the same /64 is applied 707 across the entire network. 709 8.1. Observations 711 In RPL, each RPL Router acquires a number of parents, as described in 712 Section 3, from among which it selects one as its preferred parent 713 and, thus, next-hop on the route to the DODAG Root. RPL Routers 714 maintain a parent set containing possibly more than a single parent 715 so as to be able to rapidly select an alternative preferred parent, 716 should the previously selected such become unavailable. Thus 717 expected behavior is for an RPL Router to be able to change its point 718 of attachment towards the DODAG Root. If IP addresses are assigned 719 in a strictly hierarchical fashion, and if scalability of the routing 720 state maintained in storing mode is based on this hierarchy, then 721 this entails that each time an RPL Router changes its preferred 722 parent, it must also change its own IP address - as well as cause RPL 723 routers in its "sub-DODAG" to do the same. RPL does not specify 724 signaling for reconfiguring addresses in a sub-DODAG, while 725 [I-D.ietf-roll-rpl] specifically allows for aggregation (e.g., in 726 Section 18.2.6.: "[...] it is recommended to delay the sending of DAO 727 message to DAO parents in order to maximize the chances to perform 728 route aggregation"). 730 A slightly less strict hierarchy can be envisioned, where an RPL 731 Router can change its preferred parent without necessarily changing 732 addresses of itself and of its sub-DODAG, provided that its former 733 and new preferred parents both have the same preferred parent, and 734 have addresses hierarchically assigned from that - from the 735 "preferred grandparent". With reference to Figure 1, this could be e 736 changing its preferred parent from d to c, provided that both d and c 737 have b as preferred parent. Doing so would impose a restriction on 738 the parent-set selection, admitting only parents which have 739 themselves the same parent, losing redundancy in the network 740 connectivity. RPL does not specify rules for admitting only parents 741 with identical grand-parents into the parent set - although such is 742 not prohibited either, if the loss of redundancy is acceptable. 744 The DODAG Root incrementing the DODAG version number is the mechanism 745 by which RPL enables global reconfiguration of the network, 746 reconstructing the DODAG with (intended) more optimal routes. In 747 case of addressing hierarchies being enforced, so as to enable 748 aggregation, this will either restrict the ability for an optimal 749 DODAG construction, or will also have to trigger global address 750 autoconfiguration so as to ensure addressing hierarchies. 752 Finally, with IP addresses serving a dual role of an identifier of 753 both an end-point for communication and a topological location in the 754 network, changing the IP address of a device, so as to reflect a 755 change in network topology, also entails interrupting ongoing 756 communication to or through that device. Additional mechanisms 757 (e.g., a DNS-like system) mapping "communications identifiers" and 758 "IP addresses" are required. 760 9. Links Assumed Bi-Directional 762 Parents (and the preferred parent) are selected based on receipt of 763 DIOs, without verification of the ability for an RPL Router to 764 successfully communicate with the parent - i.e., without any 765 bidirectionality check of links. However, the basic use of links is 766 for "upward" routes, i.e., for the RPL Router to use a parent (the 767 preferred parent) as relay towards the DODAG Root - in the opposite 768 direction of the one in which the DIO was received. 770 9.1. Observations 772 Unidirectional links are no rare occurrence, such as is known from 773 wireless multi-hop networks. If an RPL Router receives a DIO on such 774 a unidirectional link, and selects the originator of the DIO as 775 parent, that would be a bad choice: unicast traffic in the upward 776 direction would be lost. If the RPL Router had verified the 777 bidirectionality of links, it might have selected a better parent, to 778 which it has a bidirectional link. 780 10. Neighbor Unreachability Detection For Unidirectional Links 782 [I-D.ietf-roll-rpl] suggests using Neighbor Unreachability Detection 783 (NUD) [RFC4861] to detect and recover from the situation of 784 unidirectional links between an RPL Router and its (preferred) 785 parent(s). When, e.g., an RPL Router tries (and fails) to actually 786 use another RPL Router for forwarding traffic, NUD is supposed 787 engaged to detect and prompt corrective action, e.g., by way of 788 selecting an alternative preferred parent. 790 NUD is based upon observing if a data packet is making forward 791 progress towards the destination, either by way of indicators from 792 upper-layer protocols (such as TCP and, though not called out in 793 [RFC4861], also from lower-layer protocols such as Link Layer ACKs ) 794 or - failing that - by unicast probing by way of transmitting a 795 unicast Neighbor Solicitation message and expecting that a solicited 796 Neighbor Advertisement message be returned. 798 10.1. Observations 800 An RPL Router may receive, transiently, a DIO from an RPL Router, 801 closer (in terms of rank) to the DODAG Root than any other RPL Router 802 from which a DIO has been received. Some, especially wireless, link 803 layers may exhibit different transmission characteristics between 804 multicast and unicast transmissions (such is the case for some 805 implementations of IEEE 802.11b, where multicast/broadcast 806 transmissions are sent at much lower bit-rates than are unicast; IEEE 807 802.11b is, of course, not suggested as a viable L2 for LLNs, but 808 serves to illustrate that such asymmetric designs exist), leading to 809 a (multicast) DIO being received from farther away than a unicast 810 transmission can reach. DIOs are sent (downward) using link-local 811 multicast, whereas the traffic flowing in the opposite direction 812 (upward) is unicast. Thus, a received (multicast) DIO may not be 813 indicative of useful unicast connectivity - yet, RPL might cause this 814 RPL Router to select this seemingly attractive RPL Router as its 815 preferred parent. This may happen both at initialization, or at any 816 time during the LLN lifetime as RPL allows attachment to a "better 817 parent" over the network lifetime. 819 A DODAG so constructed may appear stable and converged until such 820 time that unicast traffic is to be sent and, thus, NUD invoked. 821 Detecting only at that point that unicast connectivity is not 822 maintained, and causing local (and possibly global) repairs exactly 823 at that time, may lead to traffic not being deliverable. As 824 indicated in Section 8, if scalability is dependent on addresses 825 being assigned hierarchically, changing point-of-attachment may 826 entail more than switching preferred parent. 828 An RPL router may detect that its preferred parent is lost by way of 829 NUD, when trying to communicate to the DODAG Root. If that RPL 830 router has no other parents in its parent set, all it can do is wait: 831 RPL does not provide other mechanisms for an RPL router to react to 832 such an event. In the case where there is no downward traffic (i.e., 833 no data or acknowledgements are sent from the DODAG Root), neither 834 the DODAG Root nor the preferred parent, to which upward connectivity 835 was lost, will be able to detect and react to the event of 836 connectivity loss. 838 In other words, for upward traffic, the RPL routers that by way of 839 NUD detect connectivity loss, will be unable to act in order to 840 restore connectivity (e.g., by way of a signaling mechanism to the 841 DODAG Root, to request DODAG reconstruction by way of version number 842 increase). The RPL routers, which could react (the "preferred 843 parents") will for upward traffic not generate any traffic "downward" 844 allowing NUD to engage and detect connectivity loss. 846 It is worth noting that RPL is optimized for upward traffic 847 (multipoint-to-point traffic), and that this is exactly the type of 848 traffic where NUD is not applicable as a mechanism for detecting and 849 reacting to connectivity loss. 851 Also, absent all RPL Routers consistently advertising their 852 reachability through DAO messages, a protocol requiring bidirectional 853 flows between the communicating devices, such as TCP, will be unable 854 to operate. 856 Finally, upon having been notified by NUD that the "next hop" is 857 unreachable, an RPL Router must discard the preferred parent and 858 select another - hoping that this time, the preferred parent is 859 actually reachable. Also, if NUD indicates "no forward progress" 860 based on an upper-layer protocol, there is no guarantee that the 861 problem stems exclusively from the preferred parent being 862 unreachable. Indeed, it may be a problem farther ahead, possibly 863 outside the LLN, thus changing preferred parent will not alleviate 864 the situation. Moreover, using information from an upper-layer 865 protocol, e.g., to return TCP ACKs back to the source, requires 866 established downward routes in the DODAG (i.e., each RPL router needs 867 to send DAO messages to the DODAG Root, as described in Section 7). 869 Incidentally, this stems from a fundamental difference between "fixed 870 links in the Internet" and "wireless links": whereas the former, as a 871 rule, are reliable, predictable and with losses being rare 872 exceptions, the latter are characterized by frequent losses and 873 general unpredictability. 875 11. RPL Implementability and Complexity 877 RPL is designed to operate on "RPL Routers [...] with constraints on 878 processing power, memory, and energy (battery power)" 879 [I-D.ietf-roll-rpl]. However, the 163 pages long specification of 880 RPL, plus additional specifications for routing headers 881 [I-D.ietf-6man-header], Trickle timer [RFC6206], routing metrics 882 [I-D.ietf-roll-routing-metrics] and objective function 883 [I-D.ietf-roll-rpl-of0], describes complex mechanisms (e.g., the 884 upwards and downward data traffic, a security solution, manageability 885 of RPL Routers, auxiliary functions for autoconfiguration of RPL 886 Routers, etc.), and provides no less than 9 message types, and 10 887 different message options. 889 To give one example, the ContikiRPL implementation 890 (http://www.sics.se/contiki), which provides only storing mode and no 891 security features, consumes about 50 KByte of memory. Sensor 892 hardware, such as MSP430 sensor platforms, does not contain much more 893 memory than that, i.e., there may not be much space left to deploy 894 any application on the RPL Router. 896 11.1. Observations 898 Since RPL is intended as the routing protocol for LLNs, which covers 899 all the diverse applications requirements listed in [RFC5867], 900 [RFC5673], [RFC5826], [RFC5548], it is likely that (i) due to limited 901 memory capacity of the RPL Routers, and (ii) due to expensive 902 development cost of the routing protocol implementation, RPL 903 implementations will only support a partial set of features from the 904 specification, leading to non-interoperable implementations. 906 In order to accommodate for the verbose exchange format, route 907 stretching and source routing for point-to-point traffic, several 908 additional Internet-Drafts are being discussed for adoption in the 909 ROLL Working Group - adding complexity to an already complex 910 specification which, it is worth recalling, was intended to be of a 911 protocol for low-capacity devices. 913 12. Underspecification 915 While [I-D.ietf-roll-rpl] is verbose in many parts, as described in 916 Section 11, some mechanisms are underspecified. 918 While for DIOs, the Trickle timer specifies a relatively efficient 919 and easy-to-understand timing for message transmission, the timing of 920 DAO transmission is not explicit. As each DAO may have a limited 921 lifetime, one "best guess" for implementers would be to send DAO 922 periodically, just before the life-time of the previous DAO expires. 923 Since DAOs may be lost, another "best guess" would be to send several 924 DAOs shortly one after the other in order to increase probability 925 that at least one DAO is successfully received. 927 The same underspecification applies for DAO-ACK messages: optionally, 928 on reception of a DAO, an RPL Router may acknowledge successful 929 reception by returning a DAO-ACK. Timing of DAO-ACK messages is 930 unspecified by RPL. 932 12.1. Observations 934 By not specifying details about message transmission intervals and 935 required actions when receiving DAO and DAO-ACKs, implementations may 936 exhibit a bad performance if not carefully implemented. Some 937 examples are: 939 1. If DAO messages are not sent in due time before the previous DAO 940 expires (or if the DAO is lost during transmission), the routing 941 entry will expire before it is renewed, leading to a possible 942 data traffic loss. 944 2. RPL does not specify to use jitter [RFC5148] (i.e., small random 945 delay for message transmissions). If DAOs are sent periodically, 946 adjacent RPL Routers may transmit DAO messages at the same time, 947 leading to link layer collisions. 949 3. In non-storing mode, the "piece-wise calculation" of routes to a 950 destination from which a DAO has been received, relies on 951 previous reception of DAOs from intermediate RPL Routers along 952 the route. If not all of these DAOs from intermediate RPL 953 Routers have been received, route calculation is not possible, 954 and DAO-ACKs or data traffic cannot be sent to that destination. 956 Other examples of underspecification include detection of 957 connectivity loss, as described in Section 10, as well as the local 958 repair mechanism, which may lead to loops and thus data traffic loss, 959 if not carefully implemented: an RPL Router discovering that all its 960 parents are unreachable, may - according to the RPL specification - 961 "detach" from the DODAG, i.e., increase its own rank to infinity. It 962 may then "poison" its sub-DODAG by advertising its infinite rank in 963 its DIOs. If, however, the RPL Router receives a DIO before it 964 transmits the "poisoned" DIO, it may attach to its own sub-DODAG, 965 creating a loop. If, instead, it had waited some time before 966 processing DIOs again, chances are it would have succeeded in 967 poisoning its sub-DODAG and thus avoided the loop. 969 13. Protocol Convergence 971 Trickle [RFC6206] is used by RPL to schedule transmission of DIO 972 messages, with the objective of minimizing the amount of transmitted 973 DIOs while ensuring a low convergence time of the network. The 974 theoretical behavior of Trickle is well understood, and the 975 convergence properties are well studied. Simulations of the 976 mechanism, such as documented [trickle-multicast], confirm these 977 theoretical studies. 979 In real-world environments, however, varying link qualities may cause 980 the algorithm to converge less well: frequent message losses entail 981 resets of the Trickle timer and more frequent and unpredicted message 982 emissions. 984 This has been observed, e.g., in an experimental testbed: 69 RPL 985 Routers (MSP430-based wireless sensor routers with IEEE 802.15.4, 986 using [rpl-contiki] IPv6 stack and RPL without downward routes; the 987 parameters of the Trickle timer were set to the implementation 988 defaults (minimum DIO interval: 4 s, DIO interval doublings: 8, 989 redundancy constant: 10) were positioned in a fixed grid topology. 990 This resulted in DODAGs being constructed with an average of 2.45 991 children per RPL Router and an average rank of 3.58. 993 In this small test network, the number of DIO messages emitted - 994 expectedly - spiked within the first ~10 seconds. Alas, rather than 995 taper off to become zero (as the simulation studies would suggest), 996 the DIO emission rate remained constant at about 70 DIOs per second. 997 Details on this experiment can be found in [rpl-eval]. 999 13.1. Observations 1001 The varying link quality in real-world environments results in 1002 frequent changes of the best parent, which triggers a reset of the 1003 Trickle timer and thus the emission of DIOs. Therefore Trickle does 1004 not converge as well for links that are fluctuating in quality as in 1005 theory. 1007 The resulting higher control overhead due to frequent DIO emission, 1008 leads to higher bandwidth and energy consumption as well as possibly 1009 to an increased number of collisions of frames, as observed in 1010 [trickle-multicast]. 1012 14. Loops 1014 [I-D.ietf-roll-rpl] states that it "guarantees neither loop free 1015 route selection nor tight delay convergence times, but can detect and 1016 repair a loop as soon as it is used. RPL uses this loop detection to 1017 ensure that packets make forward progress [...] and trigger repairs 1018 when necessary". This implies that a loop may only then be detected 1019 and fixed when data traffic is sent through the network. 1021 In order to trigger a local repair, RPL relies on the "direction" 1022 information (with values "up" or "down"), contained in an IPv6 hop- 1023 by-hop option header from received a data packet. If an "upward" 1024 data packet is received by an RPL Router, but the previous hop of the 1025 packet is listed with a lower rank in the neighbor set, the RPL 1026 Router concludes that there must be a routing loop and it may 1027 therefore trigger a local repair. For downward traffic in non- 1028 storing mode, the DODAG Root can detect loops if the same router 1029 identifier (i.e., IP address) appears at least twice in the route 1030 towards a destination. 1032 14.1. Observations 1034 The reason for RPL to repair loops only when detected by a data 1035 traffic transmission is to reduce control traffic overhead. However, 1036 there are two problems in repairing loops only when so triggered: (i) 1037 the triggered local repair mechanism delays forward progress of data 1038 packets, increasing end-to-end delays, and (ii) the data packet has 1039 to be buffered during repair. 1041 (i) may seem as the lesser of the two problems, since in a number of 1042 applications, such as data acquisition in smart metering 1043 applications, an increased delay may be acceptable. However, for 1044 applications such as alarm signals or in home automation (e.g., a 1045 light switch), increased delay may be undesirable. 1047 As for (ii), RPL is supposed to run on LLN routers with "constraints 1048 on [...] memory" [I-D.ietf-roll-rpl]; buffering incoming packets 1049 during the route repair may not be possible for all incoming data 1050 packets, leading to dropped packets. Depending on the transport 1051 protocol, these data packets must be retransmitted by the source or 1052 are definitely lost. 1054 If carefully implemented with respect to avoiding loops before they 1055 occur, the impact of the loop detection in RPL may be minimized. 1056 However, it can be observed that with current implementations of RPL, 1057 such as the ContikiRPL implementation, loops do occur - and, 1058 frequently. During the same experiments described in Section 13, a 1059 snapshot of the DODAG was made every ten seconds. In 74.14% of the 1060 4114 snapshots, at least one loop was observed. Further 1061 investigation revealed that in all these cases the DODAG was 1062 partitioned, and the loop occurred in the sub-DODAG that no longer 1063 had a connection to the DODAG Root. When the link to the only parent 1064 of an RPL Router breaks, the RPL Router may increase its rank and - 1065 when receiving a DIO from an RPL Router in its sub-DODAG - attach 1066 itself to its own sub-DODAG, thereby creating a loop - as detailed in 1067 Section 12.1. 1069 While it can be argued that the observed loops are harmless since 1070 they occur in a DODAG partition that has no connection to the DODAG 1071 Root, they show that the state of the network is inconsistent. Even 1072 worse, when the broken link re-appears, it is possible that in 1073 certain situations, the loop is only repaired when data traffic is 1074 sent, possibly leading to data loss (as described above). This can 1075 occur if the link to the previous parent is reestablished, but the 1076 rank of that previous parent has increased in the meantime. 1078 Another problem with the loop repair mechanism arises in non-storing 1079 mode when using only downward traffic: while the DODAG Root can 1080 easily detect loops (as described above), it has no direct means to 1081 trigger a local repair where the loop occurs. Indeed, it can only 1082 trigger a global repair by increasing the DODAG version number, 1083 leading to a Trickle timer reset and increased control traffic 1084 overhead in the network caused by DIO messages, and therefore a 1085 possible energy drain of the RPL Routers and congestion of the 1086 channel. 1088 Finally, loop detection for every data packet increases the 1089 processing overhead. RPL is targeted for deployments on very 1090 constrained devices with little CPU power, therefore a loop detection 1091 for every packet reduces available resources of the LLN router for 1092 other tasks (such as sensing). Moreover, each IPv6 packet needs to 1093 contain the "RPL Option for Carrying RPL Information in Data-Plane 1094 Datagrams" [I-D.ietf-6man-rpl-option] in order to use loop detection 1095 (as well as determining the RPL instance), which in turn implies an 1096 extra IPv6 header (and thus overhead) for IPv6-in-IPv6 tunneling. As 1097 this RPL option is a hop-by-hop option, it needs to be in an 1098 encapsulating IPv6-in-IPv6 tunnel and then regenerated at each hop. 1100 15. Security Considerations 1102 This document does currently not specify any security considerations. 1103 This document also does not provide any evaluation of the security 1104 mechanisms of RPL. 1106 16. IANA Considerations 1108 This document has no actions for IANA. 1110 17. Acknowledgements 1112 The authors would like to thank Matthias Philipp (INRIA) for his 1113 contributions to conducting many of the experiments, revealing or 1114 confirming the issues described in this document. 1116 Moreover, the authors would like to express their gratitude to Ralph 1117 Droms (Cisco) for his careful review of various versions of this 1118 document, for many long discussions, and for his considerable 1119 contributions to both the content and the quality of this document. 1121 18. Informative References 1123 [I-D.ietf-6man-header] 1124 Hui, J., Vasseur, J., Culler, D., and V. Manral, "An IPv6 1125 Routing Header for Source Routes with RPL", work in 1126 progress draft-ietf-6man-rpl-routing-header-07.txt, 1127 December 2011. 1129 [I-D.ietf-6man-rpl-option] 1130 Hui, J. and J. Vasseur, "RPL Option for Carrying RPL 1131 Information in Data-Plane Datagrams", work in 1132 progress draft-ietf-6man-rpl-option-02, February 2011. 1134 [I-D.ietf-roll-routing-metrics] 1135 Vasseur, J., Pister, K., Dejan, N., and D. Barthel, 1136 "Routing Metrics used for Path Calculation in Low Power 1137 and Lossy Networks", work in 1138 progress draft-ietf-roll-routing-metrics-19, March 2011. 1140 [I-D.ietf-roll-rpl] 1141 Winther, T., Thubert, P., Hui, J., Vasseur, J., Brandt, 1142 A., Kelsey, R., Levis, P., Piester, K., and R. Struik, 1143 "RPL: IPv6 Routing Protocol for Low power and Lossy 1144 Networks", work in progress draft-ietf-roll-rpl-19.txt, 1145 March 2011. 1147 [I-D.ietf-roll-rpl-of0] 1148 Thubert, P., "RPL Objective Function Zero", work in 1149 progress draft-ietf-roll-of0-20, September 2011. 1151 [I-D.ietf-roll-terminology] 1152 Vasseur, JP., "Terminology in Low power And Lossy 1153 Networks", work in 1154 progress draft-ietf-roll-terminology-06, September 2011. 1156 [RFC2026] Bradner, S., "The Internet Standards Process -- Revision 1157 3", BCP 9, RFC 2026, October 1996. 1159 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 1160 (IPv6) Specification", RFC 2460, Decemer 1998. 1162 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 1163 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 1164 September 2007. 1166 [RFC4919] Kushalnagar, N., Montenegro, G., and C. Schumacher, "IPv6 1167 over Low-Power Wireless Personal Area Networks (6LoWPANs): 1168 Overview, Assumptions, Problem Statement, and Goals", 1169 RFC 4919, August 2007. 1171 [RFC4944] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, 1172 "Transmission of IPv6 Packets over IEEE 802.15.4 1173 Networks", RFC 4944, September 2007. 1175 [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter 1176 Considerations in Mobile Ad Hoc Networks (MANETs)", 1177 RFC 5148, February 2008. 1179 [RFC5548] Dohler, M., Watteyne, T., Winter, T., and D. Barthel, 1180 "Routing Requirements for Urban Low-Power and Lossy 1181 Networks", RFC 5548, May 2009. 1183 [RFC5673] Pister, K., Thubert, P., Dwars, S., and T. Phinney, 1184 "Industrial Routing Requirements in Low-Power and Lossy 1185 Networks", RFC 5673, October 2009. 1187 [RFC5826] Brandt, A., Buron, J., and G. Porcu, "Home Automation 1188 Routing Requirements in Low-Power and Lossy Networks", 1189 RFC 5826, April 2010. 1191 [RFC5867] Martocci, J., Mi, P., Riou, N., and W. Vermeylen, 1192 "Building Automation Routing Requirements in Low Power and 1193 Lossy Networks", RFC 5867, June 2010. 1195 [RFC6206] Levis, P., Clausen, T., Gnawali, O., and J. Ko, "The 1196 Trickle Algorithm", RFC 6206, March 2011. 1198 [RFC6282] Hui, J. and P. Thubert, "Compression Format for IPv6 1199 Datagrams over IEEE 802.15.4-Based Networks", RFC 6282, 1200 September 2011. 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/ 1267 Jiazi Yi 1268 LIX, Ecole Polytechnique 1269 91128 Palaiseau Cedex, 1270 France 1272 Phone: +33 1 6933 4031 1273 Email: jiazi@jiaziyi.com 1274 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/