idnits 2.17.1 draft-ietf-roll-trickle-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Sep 2009 rather than the newer Notice from 28 Dec 2009. (See https://trustee.ietf.org/license-info/) 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 (August 19, 2010) is 4992 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Outdated reference: A later version (-01) exists of draft-hui-6man-trickle-mcast-00 == Outdated reference: A later version (-19) exists of draft-ietf-roll-rpl-11 Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Networking Working Group P. Levis 3 Internet-Draft Stanford University 4 Intended status: Standards Track T. Clausen 5 Expires: February 20, 2011 LIX, Ecole Polytechnique 6 J. Hui 7 Arch Rock Corporation 8 O. Gnawali 9 Stanford University 10 J. Ko 11 Johns Hopkins University 12 August 19, 2010 14 The Trickle Algorithm 15 draft-ietf-roll-trickle-04 17 Abstract 19 The Trickle algorithm allows nodes in a lossy shared medium (e.g., 20 low power and lossy networks) to exchange information in a highly 21 robust, energy efficient, simple, and scalable manner. Dynamically 22 adjusting transmission windows allows Trickle to spread new 23 information on the scale of link-layer transmission times while 24 sending only a few messages per hour when information does not 25 change. A simple suppression mechanism and transmission point 26 selection allows Trickle's communication rate to scale 27 logarithmically with density. This document describes the Trickle 28 algorithm and considerations in its use. 30 Status of this Memo 32 This Internet-Draft is submitted to IETF in full conformance with the 33 provisions of BCP 78 and BCP 79. 35 Internet-Drafts are working documents of the Internet Engineering 36 Task Force (IETF), its areas, and its working groups. Note that 37 other groups may also distribute working documents as Internet- 38 Drafts. 40 Internet-Drafts are draft documents valid for a maximum of six months 41 and may be updated, replaced, or obsoleted by other documents at any 42 time. It is inappropriate to use Internet-Drafts as reference 43 material or to cite them other than as "work in progress." 45 The list of current Internet-Drafts can be accessed at 46 http://www.ietf.org/ietf/1id-abstracts.txt. 48 The list of Internet-Draft Shadow Directories can be accessed at 49 http://www.ietf.org/shadow.html. 51 This Internet-Draft will expire on February 20, 2011. 53 Copyright Notice 55 Copyright (c) 2010 IETF Trust and the persons identified as the 56 document authors. All rights reserved. 58 This document is subject to BCP 78 and the IETF Trust's Legal 59 Provisions Relating to IETF Documents 60 (http://trustee.ietf.org/license-info) in effect on the date of 61 publication of this document. Please review these documents 62 carefully, as they describe your rights and restrictions with respect 63 to this document. Code Components extracted from this document must 64 include Simplified BSD License text as described in Section 4.e of 65 the Trust Legal Provisions and are provided without warranty as 66 described in the BSD License. 68 Table of Contents 70 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 71 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 72 3. Trickle Algorithm Overview . . . . . . . . . . . . . . . . . . 4 73 4. Trickle Algorithm . . . . . . . . . . . . . . . . . . . . . . 5 74 4.1. Parameters and Variables . . . . . . . . . . . . . . . . . 5 75 4.2. Algorithm Description . . . . . . . . . . . . . . . . . . 6 76 5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . 6 77 6. Operational Considerations . . . . . . . . . . . . . . . . . . 7 78 6.1. Mismatched redundancy constants . . . . . . . . . . . . . 7 79 6.2. Mismatched Imin . . . . . . . . . . . . . . . . . . . . . 7 80 6.3. Mismatched Imax . . . . . . . . . . . . . . . . . . . . . 7 81 6.4. Mismatched definitions . . . . . . . . . . . . . . . . . . 8 82 6.5. Specifying the constant k . . . . . . . . . . . . . . . . 8 83 6.6. Relationship between k and Imin . . . . . . . . . . . . . 8 84 6.7. Tweaks and improvements to Trickle . . . . . . . . . . . . 8 85 6.8. Uses of Trickle . . . . . . . . . . . . . . . . . . . . . 9 86 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10 87 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 88 9. Security Considerations . . . . . . . . . . . . . . . . . . . 10 89 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10 90 10.1. Normative References . . . . . . . . . . . . . . . . . . . 10 91 10.2. Informative References . . . . . . . . . . . . . . . . . . 10 92 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11 94 1. Introduction 96 The Trickle algorithm establishes a density-aware local communication 97 primitive with an underlying consistency model that guides when a 98 node transmits. When a node's data does not agree with its 99 neighbors, that node communicates quickly to resolve the 100 inconsistency (e.g., in milliseconds). When nodes agree, they slow 101 their communication rate exponentially, such that nodes send packets 102 very infrequently (e.g., a few packets per hour). Instead of 103 flooding a network with packets, the algorithm controls the send rate 104 so each node hears a small trickle of packets, just enough to stay 105 consistent. Furthermore, by relying only on local communication 106 (e.g., broadcast or local multicast), Trickle handles network re- 107 population, is robust to network transience, loss, and disconnection, 108 is simple to implement, and requires very little state. Current 109 implementations use 4-11 bytes of RAM and are 50-200 lines of C 110 code[Levis08]. 112 While Trickle was originally designed for reprogramming protocols 113 (where the data is the code of the program being updated), experience 114 has shown it to be a powerful mechanism that can be applied to wide 115 range of protocol design problems, including control traffic timing, 116 multicast propagation, and route discovery. This flexibility stems 117 from being able to define, on a case-by-case basis, what constitutes 118 "agreement" or an "inconsistency;" Section Section 6.8 presents a few 119 examples of how the algorithm can be used. 121 This document describes the Trickle algorithm and provides guidelines 122 for its use. It also states requirements for protocol specifications 123 that use Trickle. This document does not provide results on 124 Trickle's performance or behavior, nor does it explain the 125 algorithm's design in detail: interested readers should refer to 126 [Levis04] and [Levis08]. 128 2. Terminology 130 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 131 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 132 "OPTIONAL" in this document are to be interpreted as described in RFC 133 2119 [RFC2119]. 135 Additionally, this document introduces the following terminology: 137 Trickle communication rate: the sum of the number of messages sent 138 or received by the Trickle algorithm in an interval. 140 3. Trickle Algorithm Overview 142 Trickle's basic primitive is simple: every so often, a node transmits 143 data unless it hears a few other transmissions whose data suggest its 144 own transmission is redundant. Examples of such data include routing 145 state, software update versions, and the last heard multicast packet. 146 This primitive allows Trickle to scale to thousand-fold variations in 147 network density, quickly propagate updates, distribute transmission 148 load evenly, be robust to transient disconnections, handle network 149 repopulations, and impose a very low maintenance overhead: one 150 example use, routing beacons in the CTP protocol [Gnawali09], 151 requires sending on the order of a few packets per hour yet can 152 respond in milliseconds. 154 Trickle sends all messages to a local communication address. The 155 exact address used can depend on both the underlying IP protocol as 156 well as how the higher layer protocol uses Trickle. In IPv6, for 157 example, it can be the link-local multicast address or another local 158 multicast address, while in IPv4 it can be the broadcast address 159 (255.255.255.255). 161 There are two possible results to a Trickle message: either every 162 node that hears the message finds its data is consistent with their 163 own state, or a recipient detects an inconsistency. Detection can be 164 the result of either an out-of-date node hearing something new, or an 165 updated node hearing something old. As long as every node 166 communicates somehow - either receives or transmits - some node will 167 detect the need for an update. 169 For example, consider a simple case where "up to date" is defined by 170 version numbers (e.g., network configuration). If node A transmits 171 that it has version V, but B has version V+1, then B knows that A 172 needs an update. Similarly, if B transmits that it has version V+1, 173 A knows that it needs an update. If B broadcasts or multicasts 174 updates, then all of its neighbors can receive them without having to 175 advertise their need. Some of these recipients might not even have 176 heard A's transmission. 178 In this example, it does not matter who first transmits, A or B; 179 either case will detect the inconsistency. All that matters is that 180 some nodes communicate with one another at some nonzero rate. As 181 long as the network is connected and there is some minimum 182 communication rate for each node, the network will reach eventual 183 consistency. 185 The fact that Trickle communication can be either transmission or 186 reception enables the Trickle algorithm to operate in sparse as well 187 as dense networks. A single, disconnected node must transmit at the 188 Trickle communication rate. In a lossless, single-hop network of 189 size n, the Trickle communication rate at each node equals the sum of 190 the Trickle transmission rates across all nodes. The Trickle 191 algorithm balances the load in such a scenario, as each node's 192 Trickle transmission rate is 1/nth of the Trickle communication rate. 193 Sparser networks require more transmissions per node, but utilization 194 of the radio channel over space will not increase. This is an 195 important property in wireless networks and other shared media, where 196 the channel is a valuable shared resource. Additionally, reducing 197 transmissions in dense networks conserves system energy. 199 4. Trickle Algorithm 201 This section describes the Trickle algorithm. 203 4.1. Parameters and Variables 205 A Trickle timer has three configuration parameters: the minimum 206 interval size Imin, the maximum interval size Imax, and a redundancy 207 constant k: 209 o The minimum interval size is defined in units of time (e.g., 210 milliseconds, seconds). For example, a protocol might define the 211 minimum interval as 100 milliseconds. 213 o The maximum interval size is described as a number of doublings of 214 the minimum interval size (the base-2 log(max/min)). For example, 215 a protocol might define the maximum interval as 16. If the 216 minimum interval is 100ms, then the maximum interval is 100ms * 217 65536, 6,553.6 seconds, or approximately 109 minutes. 219 o The redundancy constant is a natural number (an integer greater 220 than zero). 222 In addition to these three parameters, Trickle maintains three 223 variables: 225 o I, the current interval size 227 o t, a time within the current interval, and 229 o c, a counter. 231 4.2. Algorithm Description 233 The Trickle algorithm has five rules: 235 1. When an interval begins, Trickle resets c to 0 and sets t to a 236 random point in the interval, taken from the range [I/2, I), that 237 is, values greater than or equal to I/2 and less than I. The 238 interval ends at I. 240 2. Whenever Trickle hears a transmission that is "consistent," it 241 increments the counter c. 243 3. At time t, Trickle transmits if and only if the counter c is less 244 than the redundancy constant k. 246 4. When the interval I expires, Trickle doubles the interval length. 247 If this new interval length would be longer than Imax, Trickle 248 sets the interval length I to be Imax. 250 5. If Trickle hears a transmission that is "inconsistent," the 251 Trickle timer resets. If I is greater than Imin, resetting a 252 Trickle timer sets I to Imin and begins a new interval. If I is 253 equal to Imin, resetting a Trickle timer does nothing. Trickle 254 can also reset the timer in response to external "events." 256 The terms consistent, inconsistent and event are in quotes because 257 their meaning depends on how a protocol uses Trickle. 259 5. Using Trickle 261 A protocol specification that uses Trickle MUST specify: 263 o Default values for Imin, Imax, and k. Because link layers can 264 vary widely in their properties, the default value of Imin SHOULD 265 be specified in terms of the worst-case latency of a link layer 266 transmission. For example, a specification should say "the 267 default value of Imin is 4 times the worst case link layer 268 latency" and should not say "the default value of Imin is 500 269 milliseconds." Worst case latency is approximately time until the 270 first link-layer transmission of the frame assuming an idle 271 channel (does not include backoff, virtual carrier sense, etc.). 273 o What constitutes a "consistent" transmission. 275 o What constitutes an "inconsistent" transmission. 277 o What "events," if any, besides inconsistent transmissions that 278 reset the Trickle timer. 280 6. Operational Considerations 282 It is RECOMMENDED that a protocol which uses Trickle include 283 mechanisms to inform nodes of configuration parameters at runtime. 284 However, it is not always possible to do so. In the cases where 285 different nodes have different configuration parameters, Trickle may 286 have unintended behaviors. This section outlines some of those 287 behaviors and operational considerations as educational exercises. 289 6.1. Mismatched redundancy constants 291 If nodes do not agree on the redundancy constant k, then nodes with 292 higher values of k will transmit more often than nodes with lower 293 values of k. In some cases, this increased load can be independent 294 of the density. For example, consider a network where all nodes but 295 one have k=1, and this one node has k=2. The different node can end 296 up transmitting on every interval: it is maintaining a Trickle 297 communication rate of 2 with only itself. Hence, the danger of 298 mismatched k values is uneven transmission load that can deplete the 299 energy of some nodes. 301 6.2. Mismatched Imin 303 If nodes do not agree on Imin, then some nodes, on hearing 304 inconsistent messages, will transmit sooner than others. These 305 faster nodes will have their intervals grow to similar size as the 306 slower nodes within a single slow interval time, but in that period 307 may suppress the slower nodes. However, such suppression will end 308 after the first slow interval, when the nodes generally agree on the 309 interval size. Hence, mismatched Imin values are usually not a 310 significant concern. Note that mismatched Imin values and matching 311 Imax doubling constants will lead to mismatched Imax values. 313 6.3. Mismatched Imax 315 If nodes do not agree on Imax, then this can cause long-term problems 316 with transmission load. Nodes with small Imax values will transmit 317 faster, suppressing those with larger Imax values. The nodes with 318 larger Imax values, always suppressed, will never transmit. In the 319 base case, when the network is consistent, this can cause long-term 320 inequities in energy cost. 322 6.4. Mismatched definitions 324 If nodes do not agree on what constitutes a consistent or 325 inconsistent transmission, then Trickle may fail to operate properly. 326 For example, if a receiver thinks a transmission is consistent, but 327 the transmitter (if in the receivers situation) would have thought it 328 inconsistent, then the receiver will not respond properly and inform 329 the transmitter. This can lead the network to not reach a consistent 330 state. For this reason, unlike the configuration constants k, Imin, 331 and Imax, consistency definitions MUST be clearly stated in the 332 protocol and SHOULD NOT be configured at runtime. 334 6.5. Specifying the constant k 336 There are some edge cases where a protocol may wish to use Trickle 337 with its suppression disabled (k is set to infinity). In general, 338 this approach is highly dangerous and it is NOT RECOMMENDED. 339 Disabling suppression means that every node will always send on every 340 interval, and can lead to congestion in dense networks. This 341 approach is especially dangerous if many nodes reset their intervals 342 at the same time. In general, it is much more desirable to set k to 343 a high value (e.g., 5 or 10) than infinity. Typical values for k are 344 1-5: these achieve a good balance between redundancy and low 345 cost[Levis08]. 347 Nevertheless, there are situations where a protocol may wish to turn 348 off Trickle suppression. Because k is a natural number 349 (Section 4.1), k=0 has no useful meaning. If a protocol allows k to 350 be dynamically configured, a value of 0 remains unused. For ease of 351 debugging and packet inspection, having the parameter describe (k-1) 352 can be confusing. Instead, it is RECOMMENDED that protocols which 353 require turning off suppression reserve k=0 to mean k=infinity. 355 6.6. Relationship between k and Imin 357 Finally, a protocol SHOULD set k and Imin such that Imin is at least 358 two to three as long as it takes to transmit k packets. Otherwise, 359 if more than k nodes reset their intervals to Imin, the resulting 360 communication will lead to congestion and significant packet loss. 361 Experimental results have shown that packet losses from congestion 362 reduce Trickle's efficiency [Levis04]. 364 6.7. Tweaks and improvements to Trickle 366 Trickle is based on a small number of simple, tightly integrated 367 mechanisms that are highly robust to challenging network 368 environments. In our experiences using Trickle, attempts to tweak 369 its behavior are typically not worth the cost. As written, the 370 algorithm is already highly efficient: further reductions in 371 transmissions or response time come at the cost of failures in edge 372 cases. Based on our experiences, we urge protocol designers to 373 suppress the instinct to tweak or improve Trickle without a great 374 deal of experimental evidence that the change does not violate its 375 assumptions and break the algorithm in edge cases. 377 This warning in mind, Trickle is far from perfect. For example, 378 Trickle suppression typically leads sparser nodes to transmit more 379 than denser ones; it is far from the optimal computation of a minimum 380 cover. However, in dynamic network environments such as wireless and 381 low-power, lossy networks, the coordination needed to compute the 382 optimal set of transmissions is typically much greater than the 383 benefits it provides. One of the benefits of Trickle is that it is 384 so simple to implement and requires so little state yet operates so 385 efficiently. Efforts to improve it should be weighed against the 386 cost of increased complexity. 388 6.8. Uses of Trickle 390 The Trickle algorithm has been used in a variety of protocols, both 391 in operational as well as academic settings. Giving a brief overview 392 of some of these uses provides useful examples of how and when it can 393 be used. These examples should not be considered exhaustive. 395 Reliable flooding/dissemination: A protocol uses Trickle to 396 periodically advertise the most recent data it has received, 397 typically through a version number. An inconsistency is when a node 398 hears a newer version number or receives new data. A consistency is 399 when a node hears an older or equal version number. When hearing an 400 older version number, rather than reset its own Trickle timer, it 401 sends an update. Nodes with old version numbers that receive the 402 update will then reset their own timers, leading to fast propagation 403 of the new data. Examples of this use include 404 multicast[I-D.hui-6man-trickle-mcast], network 405 configuration[Lin08][Dang09], and installing new application 406 programs[Hui04][Levis04]. 408 Routing control traffic: A protocol uses Trickle to control when it 409 sends beacons which contain routing state. An inconsistency is when 410 the routing topology changes in a way that could lead to loops or 411 significant stretch: examples include when the routing layer detects 412 a routing loop or when a node's routing cost changes significantly. 413 Consistency is when the routing topology is operating well and is 414 delivering packets successfully. Using the Trickle algorithm in this 415 way allows a routing protocol to react very quickly to problems (Imin 416 is small) but send very few beacons when the topology is stable. 417 Examples of this use include RPL[I-D.ietf-roll-rpl], CTP[Gnawali09], 418 and some current commericial IPv6 routing layers[Hui08]. 420 7. Acknowledgements 422 The authors would like to acknowledge the guidance and input provided 423 by the ROLL chairs, David Culler and JP Vasseur. 425 The authors would also like to acknowledge the helpful comments of 426 Yoav Ben-Yehezkel, Alexandru Petrescu, and Urlich Herberg, which 427 greatly improved the document. 429 8. IANA Considerations 431 This document has no IANA considerations. 433 9. Security Considerations 435 This document has no security considerations. 437 10. References 439 10.1. Normative References 441 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 442 Requirement Levels", BCP 14, RFC 2119, March 1997. 444 10.2. Informative References 446 [Dang09] Dang, T., Bulusu, N., Feng, W., and S. Park, "DHV: A Code 447 Consistency Maintenance Protocol for Multi-hop Wireless 448 Networks", Wireless Sensor Networks: 6th European 449 Conference Proceedings EWSN 2009 Cork, February 2009, . 453 [Gnawali09] 454 Gnawali, O., Fonseca, R., Jamieson, K., Moss, D., and P. 455 Levis, "Collection Tree Protocol", Proceedings of the 7th 456 ACM Conference on Embedded Networked Systems SenSys 2009, 457 November 2009, 458 . 460 [Hui04] Hui, J. and D. Culler, "The dynamic behavior of a data 461 dissemination protocol for network programming at scale", 462 Proceedings of the 2nd ACM Conference on Embedded 463 Networked Systems SenSys 2004, November 2004, 464 . 466 [Hui08] Hui, J. and D. Culler, "IP is dead, long live IP for 467 wireless sensor networks", Proceedings of the 6th ACM 468 Conference on Embedded Networked Systems SenSys 2008, 469 November 2008, 470 . 472 [I-D.hui-6man-trickle-mcast] 473 Hui, J. and R. Kelsey, "Multicast Forwarding Using 474 Trickle", draft-hui-6man-trickle-mcast-00 (work in 475 progress), July 2010. 477 [I-D.ietf-roll-rpl] 478 Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing 479 Protocol for Low power and Lossy Networks", 480 draft-ietf-roll-rpl-11 (work in progress), July 2010. 482 [Levis04] Levis, P., Patel, N., Culler, D., and S. Shenker, 483 "Trickle: A Self-Regulating Algorithm for Code Propagation 484 and Maintenance in Wireless Sensor Networks"", Proceedings 485 of the First USENIX/ACM Symposium on Networked Systems 486 Design and Implementation NSDI 2004, March 2004, 487 . 489 [Levis08] Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S., 490 Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and A. 491 Woo, "The Emergence of a Networking Primitive in Wireless 492 Sensor Networks", Communications of the ACM, v.51 n.7, 493 July 2008, 494 . 496 [Lin08] Lin, K. and P. Levis, "Data Discovery and Dissemination 497 with DIP", Proceedings of the 7th international conference 498 on Information processing in sensor networks IPSN 2008, 499 April 2008, 500 . 502 Authors' Addresses 504 Philip Levis 505 Stanford University 506 358 Gates Hall, Stanford University 507 Stanford, CA 94305 508 USA 510 Phone: +1 650 725 9064 511 Email: pal@cs.stanford.edu 513 Thomas Heide Clausen 514 LIX, Ecole Polytechnique 516 Phone: +33 6 6058 9349 517 Email: T.Clausen@computer.org 519 Jonathan Hui 520 Arch Rock Corporation 521 501 Snd St., Suite 410 522 San Francisco, CA 94107 523 USA 525 Email: jhui@archrock.com 527 Omprakash Gnawali 528 Stanford University 529 S255 Clark Center, 318 Campus Drive 530 Stanford, CA 94305 531 USA 533 Phone: +1 650 725 6086 534 Email: gnawali@cs.stanford.edu 536 JeongGil Ko 537 Johns Hopkins University 538 3400 N. Charles St., 224 New Engineering Building 539 Baltimore, MD 21218 540 USA 542 Phone: +1 410 516 4312 543 Email: jgko@cs.jhu.edu