idnits 2.17.1 draft-ietf-roll-trickle-03.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 18, 2010) is 5000 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-10 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 19, 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 18, 2010 14 The Trickle Algorithm 15 draft-ietf-roll-trickle-03 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 Trickle and 28 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 19, 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 . . . . . . . . . . . . . . . . . . 3 73 4. Trickle Algorithm . . . . . . . . . . . . . . . . . . . . . . 5 74 4.1. Parameters and Variables . . . . . . . . . . . . . . . . . 5 75 4.2. Algorithm Description . . . . . . . . . . . . . . . . . . 5 76 5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . 6 77 6. Operational Considerations . . . . . . . . . . . . . . . . . . 6 78 6.1. Mismatched redundancy constants . . . . . . . . . . . . . 7 79 6.2. Mismatched Imin . . . . . . . . . . . . . . . . . . . . . 7 80 6.3. Mismatched Imax . . . . . . . . . . . . . . . . . . . . . 7 81 6.4. Mismatched definitions . . . . . . . . . . . . . . . . . . 7 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 . . . . . . . . . . . . . . . . . . . . . . . 9 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." 120 This document describes the Trickle algorithm and provides guidelines 121 for its use. It also states requirements for protocol specifications 122 that use Trickle. This document does not provide results on 123 Trickle's performance or behavior, nor does it explain the 124 algorithm's design in detail: interested readers should refer to 125 [Levis04] and [Levis08]. 127 2. Terminology 129 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 130 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 131 "OPTIONAL" in this document are to be interpreted as described in RFC 132 2119 [RFC2119]. 134 3. Trickle Algorithm Overview 136 Trickle's basic primitive is simple: every so often, a node transmits 137 data unless it hears a few other transmissions whose data suggest its 138 own transmission is redundant. Examples of such data include routing 139 state, software update versions, and the last heard multicast packet. 141 This primitive allows Trickle to scale to thousand-fold variations in 142 network density, quickly propagate updates, distribute transmission 143 load evenly, be robust to transient disconnections, handle network 144 repopulations, and impose a very low maintenance overhead: common 145 uses require on the order of a few packets per hour yet can respond 146 in milliseconds. 148 Trickle sends all messages to a local communication address. The 149 exact address used can depend on both the underlying IP protocol as 150 well as how the higher layer protocol uses Trickle. In IPv6, for 151 example, it can be the link-local multicast address or another local 152 multicast address, while in IPv4 it can be the broadcast address 153 (255.255.255.255). 155 There are two possible results to a Trickle broadcast: either every 156 node that hears the message finds its data is consistent with their 157 own state, or a recipient detects an inconsistency. Detection can be 158 the result of either an out-of-date node hearing something new, or an 159 updated node hearing something old. As long as every node 160 communicates somehow - either receives or transmits - some node will 161 detect the need for an update. 163 For example, consider a simple case where "up to date" is defined by 164 version numbers (e.g., network configuration). If node A transmits 165 that it has version V, but B has version V+1, then B knows that A 166 needs an update. Similarly, if B transmits that it has version V+1, 167 A knows that it needs an update. If B broadcasts or multicasts 168 updates, then all of its neighbors can receive them without having to 169 advertise their need. Some of these recipients might not even have 170 heard A's transmission. 172 In this example, it does not matter who first transmits, A or B; 173 either case will detect the inconsistency. All that matters is that 174 some nodes communicate with one another at some nonzero rate. As 175 long as the network is connected and there is some minimum 176 communication rate for each node, the network will reach eventual 177 consistency. 179 The fact that communication can be either transmission or reception 180 enables the Trickle algorithm to operate in sparse as well as dense 181 networks. A single, disconnected node must transmit at the Trickle 182 communication rate. In a lossless, single-hop network of size n, the 183 Trickle communication rate at each node equals the sum of the Trickle 184 transmission rates across all nodes. The Trickle algorithm blaances 185 the load in such a scenario, as each node's Trickle transmission rate 186 is 1/nth of the Trickle communication rate. Sparser networks require 187 more transmissions per node, but utilization of the radio channel 188 over space will not increase. This is an important property in 189 wireless networks and other shared media, where the channel is a 190 valuable shared resource. Additionally, reducing transmissions in 191 dense networks conserves system energy. 193 4. Trickle Algorithm 195 This section describes the Trickle algorithm. 197 4.1. Parameters and Variables 199 A Trickle timer has three configuration parameters: the minimum 200 interval size Imin, the maximum interval size Imax, and a redundancy 201 constant k: 203 o The minimum interval size is defined in units of time (e.g., 204 milliseconds, seconds). For example, a protocol might define the 205 minimum interval as 100 milliseconds. 207 o The maximum interval size is described as a number of doublings of 208 the minimum interval size (the base-2 log(max/min)). For example, 209 a protocol might define the maximum interval as 16. If the 210 minimum interval is 100ms, then the maximum interval is 100ms * 211 65536, 6,553.6 seconds, or approximately 109 minutes. 213 o The redundancy constant is a natural number (an integer greater 214 than zero). 216 In addition to these three parameters, Trickle maintains three 217 variables: 219 o I, the current interval size 221 o t, a time within the current interval, and 223 o c, a counter. 225 4.2. Algorithm Description 227 The Trickle algorithm has five rules: 229 1. When an interval begins, Trickle resets c to 0 and sets t to a 230 random point in the interval, taken from the range [I/2, I), that 231 is, values greater than or equal to I/2 and less than I. The 232 interval ends at I. 234 2. Whenever Trickle hears a transmission that is "consistent," it 235 increments the counter c. 237 3. At time t, Trickle transmits if and only if the counter c is less 238 than the redundancy constant k. 240 4. When the interval I expires, Trickle doubles the interval length. 241 If this new interval length would be longer than Imax, Trickle 242 sets the interval length I to be Imax. 244 5. If Trickle hears a transmission that is "inconsistent," the 245 Trickle timer resets. If I is greater than Imin, resetting a 246 Trickle timer sets I to Imin and begins a new interval. If I is 247 equal to Imin, resetting a Trickle timer does nothing. Trickle 248 can also reset the timer in response to external "events." 250 The terms consistent, inconsistent and event are in quotes because 251 their meaning depends on how a protocol uses Trickle. 253 5. Using Trickle 255 A protocol specification that uses Trickle MUST specify: 257 o Default values for Imin, Imax, and k. Because link layers can 258 vary widely in their properties, the default value of Imin SHOULD 259 be specified in terms of the worst-case latency of a link layer 260 transmission. For example, a specification should say "the 261 default value of Imin is 4 times the worst case link layer 262 latency" and should not say "the default value of Imin is 500 263 milliseconds." Worst case latency is approximately time until the 264 first link-layer transmission of the frame assuming an idle 265 channel (does not include backoff, virtual carrier sense, etc.). 267 o What constitutes a "consistent" transmission. 269 o What constitutes an "inconsistent" transmission. 271 o What "events," if any, besides inconsistent transmissions that 272 reset the Trickle timer. 274 6. Operational Considerations 276 It is RECOMMENDED that a protocol which uses Trickle include 277 mechanisms to inform nodes of configuration parameters at runtime. 278 However, it is not always possible to do so. In the cases where 279 different nodes have different configuration parameters, Trickle may 280 have unintended behaviors. This section outlines some of those 281 behaviors and operational considerations as educational exercises. 283 6.1. Mismatched redundancy constants 285 If nodes do not agree on the redundancy constant k, then nodes with 286 higher values of k will transmit more often than nodes with lower 287 values of k. In some cases, this increased load can be independent 288 of the density. For example, consider a network where all nodes but 289 one have k=1, and this one node has k=2. The different node can end 290 up transmitting on every interval: it is maintaining a Trickle 291 communication rate of 2 with only itself. Hence, the danger of 292 mismatched k values is uneven transmission load that can deplete the 293 energy of some nodes. 295 6.2. Mismatched Imin 297 If nodes do not agree on Imin, then some nodes, on hearing 298 inconsistent messages, will transmit sooner than others. These 299 faster nodes will have their intervals grow to similar size as the 300 slower nodes within a single slow interval time, but in that period 301 may suppress the slower nodes. However, such suppression will end 302 after the first slow interval, when the nodes generally agree on the 303 interval size. Hence, mismatched Imin values are usually not a 304 significant concern. Note that mismatched Imin values and matching 305 Imax doubling constants will lead to mismatched Imax values. 307 6.3. Mismatched Imax 309 If nodes do not agree on Imax, then this can cause long-term problems 310 with transmission load. Nodes with small Imax values will transmit 311 faster, suppressing those with larger Imax values. The nodes with 312 larger Imax values, always suppressed, will never transmit. In the 313 base case, when the network is consistent, this can cause long-term 314 inequities in energy cost. 316 6.4. Mismatched definitions 318 If nodes do not agree on what constitutes a consistent or 319 inconsistent transmission, then Trickle may fail to operate properly. 320 For example, if a receiver thinks a transmission is consistent, but 321 the transmitter (if in the receivers situation) would have thought it 322 inconsistent, then the receiver will not respond properly and inform 323 the transmitter. This can lead the network to not reach a consistent 324 state. For this reason, unlike the configuration constants k, Imin, 325 and Imax, consistency definitions MUST be clearly stated in the 326 protocol and SHOULD NOT be configured at runtime. 328 6.5. Specifying the constant k 330 There are some edge cases where a protocol may wish to use Trickle 331 with its suppression disabled (k is set to infinity). In general, 332 this approach is highly dangerous and it is NOT RECOMMENDED. 333 Disabling suppression means that every node will always send on every 334 interval, and can lead to congestion in dense networks. This 335 approach is especially dangerous if many nodes reset their intervals 336 at the same time. In general, it is much more desirable to set k to 337 a high value (e.g., 5 or 10) than infinity. Typical values for k are 338 1-5: these achieve a good balance between redundancy and low 339 cost[Levis08]. 341 Nevertheless, there are situations where a protocol may wish to turn 342 off Trickle suppression. Because k is a natural number 343 (Section 4.1), k=0 has no useful meaning. If a protocol allows k to 344 be dynamically configured, a value of 0 remains unused. For ease of 345 debugging and packet inspection, having the parameter describe (k-1) 346 can be confusing. Instead, it is RECOMMENDED that protocols which 347 require turning off suppression reserve k=0 to mean k=infinity. 349 6.6. Relationship between k and Imin 351 Finally, a protocol SHOULD set k and Imin such that Imin is at least 352 two to three as long as it takes to transmit k packets. Otherwise, 353 if more than k nodes reset their intervals to Imin, the resulting 354 communication will lead to congestion and significant packet loss. 355 Experimental results have shown that packet losses from congestion 356 reduce Trickle's efficiency [Levis04]. 358 6.7. Tweaks and improvements to Trickle 360 Trickle is based on a small number of simple, tightly integrated 361 mechanisms that are highly robust to challenging network 362 environments. In our experiences using Trickle, attempts to tweak 363 its behavior are typically not worth the cost. As written, the 364 algorithm is already highly efficient: further reductions in 365 transmissions or response time come at the cost of failures in edge 366 cases. Based on our experiences, we urge protocol designers to 367 suppress the instinct to tweak or improve Trickle without a great 368 deal of experimental evidence that the change does not violate its 369 assumptions and break the algorithm in edge cases. 371 This warning in mind, Trickle is far from perfect. For example, 372 Trickle suppression typically leads sparser nodes to transmit more 373 than denser ones; it is far from the optimal computation of a minimum 374 cover. However, in dynamic network environments such as wireless and 375 low-power, lossy networks, the coordination needed to compute the 376 optimal set of transmissions is typically much greater than the 377 benefits it provides. One of the benefits of Trickle is that it is 378 so simple to implement and requires so little state yet operates so 379 efficiently. Efforts to improve it should be weighed against the 380 cost of increased complexity. 382 6.8. Uses of Trickle 384 The Trickle algorithm has been used in a variety of protocols, both 385 in operational as well as academic settings. Giving a brief overview 386 of some of these uses provides useful examples of how and when it can 387 be used. These examples should not be considered exhaustive. 389 Reliable flooding/dissemination: A protocol uses Trickle to 390 periodically advertise the most recent data it has received, 391 typically through a version number. An inconsistency is when a node 392 hears a newer version number or receives new data. A consistency is 393 when a node hears an older or equal version number. When hearing an 394 older version number, rather than reset its own Trickle timer, it 395 sends an update. Nodes with old version numbers that receive the 396 update will then reset their own timers, leading to fast propagation 397 of the new data. Examples of this use include 398 multicast[I-D.hui-6man-trickle-mcast], network 399 configuration[Lin08][Dang09], and installing new application 400 programs[Hui04][Levis04]. 402 Routing control traffic: A protocol uses Trickle to control when it 403 sends beacons which contain routing state. An inconsistency is when 404 the routing topology changes in a way that could lead to loops or 405 significant stretch: examples include when the routing layer detects 406 a routing loop or when a node's routing cost changes significantly. 407 Consistency is when the routing topology is operating well and is 408 delivering packets successfully. Using the Trickle algorithm in this 409 way allows a routing protocol to react very quickly to problems (Imin 410 is small) but send very few beacons when the topology is stable. 411 Examples of this use include RPL[I-D.ietf-roll-rpl], CTP[Gnawali09], 412 and some current commericial IPv6 routing layers[Hui08]. 414 7. Acknowledgements 416 The authors would like to acknowledge the guidance and input provided 417 by the ROLL chairs, David Culler and JP Vasseur. 419 The authors would also like to acknowledge the helpful comments of 420 Yoav Ben-Yehezkel, Alexandru Petrescu, and Urlich Herberg, which 421 greatly improved the document. 423 8. IANA Considerations 425 This document has no IANA considerations. 427 9. Security Considerations 429 This document has no security considerations. 431 10. References 433 10.1. Normative References 435 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 436 Requirement Levels", BCP 14, RFC 2119, March 1997. 438 10.2. Informative References 440 [Dang09] Dang, T., Bulusu, N., Feng, W., and S. Park, "DHV: A Code 441 Consistency Maintenance Protocol for Multi-hop Wireless 442 Networks", Wireless Sensor Networks: 6th European 443 Conference Proceedings EWSN 2009 Cork, February 2009, . 447 [Gnawali09] 448 Gnawali, O., Fonseca, R., Jamieson, K., Moss, D., and P. 449 Levis, "Collection Tree Protocol", Proceedings of the 7th 450 ACM Conference on Embedded Networked Systems SenSys 2009, 451 November 2009, 452 . 454 [Hui04] Hui, J. and D. Culler, "The dynamic behavior of a data 455 dissemination protocol for network programming at scale", 456 Proceedings of the 2nd ACM Conference on Embedded 457 Networked Systems SenSys 2004, November 2004, 458 . 460 [Hui08] Hui, J. and D. Culler, "IP is dead, long live IP for 461 wireless sensor networks", Proceedings of the 6th ACM 462 Conference on Embedded Networked Systems SenSys 2008, 463 November 2008, 464 . 466 [I-D.hui-6man-trickle-mcast] 467 Hui, J. and R. Kelsey, "Multicast Forwarding Using 468 Trickle", draft-hui-6man-trickle-mcast-00 (work in 469 progress), July 2010. 471 [I-D.ietf-roll-rpl] 472 Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing 473 Protocol for Low power and Lossy Networks", 474 draft-ietf-roll-rpl-10 (work in progress), June 2010. 476 [Levis04] Levis, P., Patel, N., Culler, D., and S. Shenker, 477 "Trickle: A Self-Regulating Algorithm for Code Propagation 478 and Maintenance in Wireless Sensor Networks"", Proceedings 479 of the First USENIX/ACM Symposium on Networked Systems 480 Design and Implementation NSDI 2004, March 2004, 481 . 483 [Levis08] Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S., 484 Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and A. 485 Woo, "The Emergence of a Networking Primitive in Wireless 486 Sensor Networks", Communications of the ACM, v.51 n.7, 487 July 2008, 488 . 490 [Lin08] Lin, K. and P. Levis, "Data Discovery and Dissemination 491 with DIP", Proceedings of the 7th international conference 492 on Information processing in sensor networks IPSN 2008, 493 April 2008, 494 . 496 Authors' Addresses 498 Philip Levis 499 Stanford University 500 358 Gates Hall, Stanford University 501 Stanford, CA 94305 502 USA 504 Phone: +1 650 725 9064 505 Email: pal@cs.stanford.edu 507 Thomas Heide Clausen 508 LIX, Ecole Polytechnique 510 Phone: +33 6 6058 9349 511 Email: T.Clausen@computer.org 512 Jonathan Hui 513 Arch Rock Corporation 514 501 Snd St., Suite 410 515 San Francisco, CA 94107 516 USA 518 Email: jhui@archrock.com 520 Omprakash Gnawali 521 Stanford University 522 S255 Clark Center, 318 Campus Drive 523 Stanford, CA 94305 524 USA 526 Phone: +1 650 725 6086 527 Email: gnawali@cs.stanford.edu 529 JeongGil Ko 530 Johns Hopkins University 531 3400 N. Charles St., 224 New Engineering Building 532 Baltimore, MD 21218 533 USA 535 Phone: +1 410 516 4312 536 Email: jgko@cs.jhu.edu