idnits 2.17.1 draft-ietf-roll-trickle-02.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 (July 6, 2010) is 5014 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 1 error (**), 0 flaws (~~), 1 warning (==), 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: Informational T. Clausen 5 Expires: January 7, 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 July 6, 2010 14 The Trickle Algorithm 15 draft-ietf-roll-trickle-02 17 Abstract 19 The Trickle algorithm allows wireless nodes to exchange information 20 in a highly robust, energy efficient, simple, and scalable manner. 21 Dynamically adjusting transmission windows allows Trickle to spread 22 new information on the scale of link-layer transmission times while 23 sending only a few messages per hour when information does not 24 change. A simple suppression mechanism and transmission point 25 selection allows Trickle's communication rate to scale 26 logarithmically with density. This document describes Trickle and 27 considerations in its use. 29 Status of this Memo 31 This Internet-Draft is submitted to IETF 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), its areas, and its working groups. Note that 36 other groups may also distribute working documents as Internet- 37 Drafts. 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 The list of current Internet-Drafts can be accessed at 45 http://www.ietf.org/ietf/1id-abstracts.txt. 47 The list of Internet-Draft Shadow Directories can be accessed at 48 http://www.ietf.org/shadow.html. 50 This Internet-Draft will expire on January 7, 2011. 52 Copyright Notice 54 Copyright (c) 2010 IETF Trust and the persons identified as the 55 document authors. All rights reserved. 57 This document is subject to BCP 78 and the IETF Trust's Legal 58 Provisions Relating to IETF Documents 59 (http://trustee.ietf.org/license-info) in effect on the date of 60 publication of this document. Please review these documents 61 carefully, as they describe your rights and restrictions with respect 62 to this document. Code Components extracted from this document must 63 include Simplified BSD License text as described in Section 4.e of 64 the Trust Legal Provisions and are provided without warranty as 65 described in the BSD License. 67 Table of Contents 69 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 70 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3 71 3. Trickle Algorithm Overview . . . . . . . . . . . . . . . . . . 3 72 4. Trickle Algorithm . . . . . . . . . . . . . . . . . . . . . . . 4 73 4.1. Parameters and Variables . . . . . . . . . . . . . . . . . 4 74 4.2. Algorithm Description . . . . . . . . . . . . . . . . . . . 5 75 5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . . 5 76 6. Operational Considerations . . . . . . . . . . . . . . . . . . 6 77 6.1. Mismatched redundancy constants . . . . . . . . . . . . . . 6 78 6.2. Mismatched Imin . . . . . . . . . . . . . . . . . . . . . . 6 79 6.3. Mismatched Imax . . . . . . . . . . . . . . . . . . . . . . 7 80 6.4. Mismatched definitions . . . . . . . . . . . . . . . . . . 7 81 6.5. Specifying the constant k . . . . . . . . . . . . . . . . . 7 82 6.6. Relationship between k and Imin . . . . . . . . . . . . . . 7 83 6.7. Tweaks and improvements to Trickle . . . . . . . . . . . . 8 84 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 8 85 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 8 86 9. Security Considerations . . . . . . . . . . . . . . . . . . . . 8 87 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8 88 10.1. Normative References . . . . . . . . . . . . . . . . . . . 8 89 10.2. Informative References . . . . . . . . . . . . . . . . . . 9 90 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 9 92 1. Introduction 94 The Trickle algorithm is designed for wireless networks. It 95 establishes a density-aware local broadcast with an underlying 96 consistency model that guides when a node communicates. When a 97 node's data does not agree with its neighbors, it communicates 98 quickly to resolve the inconsistency. When nodes agree, they slow 99 their communication rate exponentially, such that nodes send at most 100 a few packets per hour. Instead of flooding a network with packets, 101 the algorithm controls the send rate so each node hears a small 102 trickle of packets, just enough to stay consistent. Furthermore, by 103 relying only on local broadcasts, Trickle handles network re- 104 population, is robust to network transience, loss, and disconnection, 105 and requires very little state (implementations use 4-11 bytes). 107 While Trickle was originally designed for reprogramming protocols 108 (where the data is the code of the program being updated), experience 109 has shown it to be a powerful mechanism that can be applied to wide 110 range of protocol design problems, including control traffic timing, 111 multicast propagation, and route discovery. 113 This document describes the Trickle algorithm and provides guidelines 114 for its use. It also states requirements for protocol specifications 115 that use Trickle. This document does not provide results on 116 Trickle's performance or behavior, nor does it explain the 117 algorithm's design in detail: interested readers should refer to 118 [Levis04] and [Levis08]. 120 2. Terminology 122 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 123 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 124 "OPTIONAL" in this document are to be interpreted as described in RFC 125 2119 [RFC2119]. 127 3. Trickle Algorithm Overview 129 Trickle's basic primitive is simple: every so often, a node transmits 130 code metadata if it has not heard a few other nodes transmit the same 131 thing. This allows Trickle to scale to thousand-fold variations in 132 network density, quickly propagate updates, distribute transmission 133 load evenly, be robust to transient disconnections, handle network 134 repopulations, and impose a maintenance overhead on the order of a 135 few packets per hour. 137 Trickle sends all messages to the local broadcast address. There are 138 two possible results to a Trickle broadcast: either every node that 139 hears the message is up to date, or a recipient detects the need for 140 an update. Detection can be the result of either an out-of-date node 141 hearing someone has new code, or an updated node hearing someone has 142 old code. As long as every node communicates somehow - either 143 receives or transmits - the need for an update will be detected. 145 For example, consider a simple case where "up to date" is defined by 146 version numbers (e.g., network configuration). If node A broadcasts 147 that it has version V, but B has version V+1, then B knows that A 148 needs an update. Similarly, if B broadcasts that it has V+1, A knows 149 that it needs an update. If B broadcasts updates, then all of its 150 neighbors can receive them without having to advertise their need. 151 Some of these recipients might not even have heard A's transmission. 153 In this example, it does not matter who first transmits, A or B; 154 either case will detect the inconsistency. All that matters is that 155 some nodes communicate with one another at some nonzero rate. As 156 long as the network is connected and there is some minimum 157 communication rate for each node, the network will reach eventual 158 consistency. 160 The fact that communication can be either transmission or reception 161 enables Trickle to operate in sparse as well as dense networks. A 162 single, disconnected node must transmit at the communication rate. 163 In a lossless, single-hop network of size n, the sum of transmissions 164 over the network is the communication rate, so for each node it is 165 1/n. Sparser networks require more transmissions per node, but 166 utilization of the radio channel over space will not increase. This 167 is an important property in wireless networks, where the channel is a 168 valuable shared resource. Additionally, reducing transmissions in 169 dense networks conserves system energy. 171 4. Trickle Algorithm 173 This section describes the Trickle algorithm. 175 4.1. Parameters and Variables 177 A Trickle timer has three configuration parameters: the minimum 178 interval size Imin, the maximum interval size Imax, and a redundancy 179 constant k: 181 o The minimum interval size is defined in units of time (e.g., 182 milliseconds, seconds). For example, a protocol might define the 183 minimum interval as 100 milliseconds. 185 o The maximum interval size is described as a number of doublings of 186 the minimum interval size (the base-2 log(max/min)). For example, 187 a protocol might define the maximum interval as 16. If the 188 minimum interval is 100ms, then the maximum interval is 100ms * 189 65536, 6,553.6 seconds, or approximately 109 minutes. 191 o The redundancy constant is a natural number (an integer greater 192 than zero). 194 In addition to these three parameters, Trickle maintains three 195 variables: 197 o I, the current interval size 199 o t, a time within the current interval, and 201 o c, a counter. 203 4.2. Algorithm Description 205 The Trickle algorithm has five rules: 207 1. When an interval begins, Trickle resets c to 0 and sets t to a 208 random point in the interval, taken from the range [I/2, I). 210 2. Whenever Trickle hears a transmission that is "consistent," it 211 increments counter c. 213 3. At time t, Trickle transmits if and only if counter c is less 214 than the redundancy constant k. 216 4. When an interval expires, Trickle doubles the interval length. 217 If this new interval length would be longer than Imax, Trickle 218 sets the interval length I to be Imax. 220 5. If Trickle hears a transmission that is "inconsistent," the 221 Trickle timer resets. If I is greater than Imin, resetting a 222 Trickle timer sets I to Imin and begins a new interval. If I is 223 equal to Imin, resetting a Trickle timer does nothing. Trickle 224 may also reset the timer in response to external "events." 226 The terms consistent, inconsistent and event are in quotes because 227 their meaning depends on the use of Trickle. 229 5. Using Trickle 231 A protocol specification that uses Trickle MUST specify: 233 o Default values for Imin, Imax, and k. Because link layers can 234 vary widely in their properties, the default value of Imin should 235 be specified in terms of the worst-case latency of a link layer 236 transmission. For example, a specification should say "the 237 default value of Imin is 4 times the worst case link layer 238 latency" and should not say "the default value of Imin is 500 239 milliseconds." Worst case latency is the time until the first 240 link-layer transmission of the frame assuming an idle channel 241 (does not include backoff, virtual carrier sense, etc.). 243 o What constitutes a "consistent" transmission. 245 o What constitutes an "inconsistent" transmission. 247 o What "events," if any, besides inconsistent transmissions that 248 reset the Trickle timer. 250 6. Operational Considerations 252 It is RECOMMENDED that a protocol which uses Trickle include 253 mechanisms to inform nodes of configuration parameters at runtime. 254 However, it is not always possible to do so. In the cases where 255 different nodes have different configuration parameters, Trickle may 256 have unintended behaviors. This section outlines some of those 257 behaviors and operational considerations as educational exercises. 259 6.1. Mismatched redundancy constants 261 If nodes do not agree on the redundancy constant k, then nodes with 262 higher values of k will transmit more often than nodes with lower 263 values of k. In some cases, this increased load can be independent 264 of the density. For example, consider a network where all nodes but 265 one have k=1, and this one node has k=2. The different node can end 266 up transmitting on every interval: it is maintaining a communication 267 rate of 2 with only itself. Hence, the danger of mismatched k values 268 is uneven transmission load that can deplete the energy of some 269 nodes. 271 6.2. Mismatched Imin 273 If nodes do not agree on Imin, then some nodes, on hearing 274 inconsistent messages, will transmit sooner than others. These 275 faster nodes will have their intervals grow to similar size as the 276 slower nodes within a single slow interval time, but in that period 277 may suppress the slower nodes. However, such suppression will end 278 after the first slow interval, when the nodes generally agree on the 279 interval size. Hence, mismatched Imin values are usually not a 280 significant concern. 282 6.3. Mismatched Imax 284 If nodes do not agree on Imax, then this can cause long-term problems 285 with transmission load. Nodes with small Imax values will transmit 286 faster, suppressing those with larger Imax values. The nodes with 287 larger Imax values, always suppressed, will never transmit. In the 288 base case, when the network is consistent, this can cause long-term 289 inequities in energy cost. 291 6.4. Mismatched definitions 293 If nodes do not agree on what constitutes a consistent or 294 inconsistent transmission, then Trickle may fail to operate properly. 295 For example, if a receiver thinks a transmission is consistent, but 296 the transmitter (if in the receivers situation) would have thought it 297 inconsistent, then the receiver will not respond properly and inform 298 the transmitter. This can lead the network to not reach a consistent 299 state. For this reason, unlike the configuration constants k, Imin, 300 and Imax, consistency definitions should be clearly stated in the 301 protocol and should not be configured at runtime. 303 6.5. Specifying the constant k 305 There are some edge cases where a protocol may wish to use Trickle 306 with its suppression disabled (k is set to infinity). In general, 307 this approach is highly dangerous and it is NOT RECOMMENDED. 308 Disabling suppression means that every node will always send on every 309 interval, and can lead to congestion in dense networks. This 310 approach is especially dangerous if many nodes reset their intervals 311 at the same time. In general, it is much more desirable to set k to 312 a high value (e.g., 5 or 10) than infinity. Typical values for k are 313 1-5: these achieve a good balance between redundancy and low cost. 315 Nevertheless, there are situations where a protocol may wish to turn 316 off Trickle suppression. Because k is a natural number 317 (Section 4.1), c=0 has no useful meaning. If a protocol allows k to 318 be dynamically configured, a value of 0 remains unused. For ease of 319 debugging and packet inspection, having the parameter describe (c-1) 320 can be counter-productive. Instead, it is RECOMMENDED that protocols 321 which require turning off suppression reserve c=0 to mean c=infinity. 323 6.6. Relationship between k and Imin 325 Finally, a protocol SHOULD set k and Imin such that Imin is at least 326 two to three as long as it takes to transmit k packets. Otherwise, 327 if more than k nodes reset their intervals to Imin, the resulting 328 communication will lead to congestion and significant packet loss. 329 Experimental results have shown that packet losses from congestion 330 reduce Trickle's efficiency [Levis04]. 332 6.7. Tweaks and improvements to Trickle 334 Trickle is based on a small number of simple, tightly integrated 335 mechanisms that are highly robust to challenging network 336 environments. In our experiences using Trickle, attempts to tweak 337 its behavior are typically not worth the cost. As written, the 338 algorithm is already highly efficient: further reductions in 339 transmissions or response time come at the cost of failures in edge 340 cases. Based on our experiences, we urge protocol designers to 341 suppress the instinct to tweak or improve Trickle without a great 342 deal of experimental evidence that the change does not violate its 343 assumptions and break the algorithm in edge cases. 345 This warning in mind, Trickle is far from perfect. For example, 346 Trickle suppression typically leads sparser nodes to transmit more 347 than denser ones; it is far from the optimal computation of a minimum 348 cover. However, in dynamic network environments such as wireless, 349 the coordination needed to compute the optimal set of transmissions 350 is typically much greater than the benefits it provides. One of the 351 benefits of Trickle is that it is so simple to implement and requires 352 so little state yet operates so efficiently. Efforts to improve it 353 should be weighed against the cost of increased complexity. 355 7. Acknowledgements 357 8. IANA Considerations 359 This document has no IANA considerations. 361 9. Security Considerations 363 This document has no security considerations. 365 10. References 367 10.1. Normative References 369 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 370 Requirement Levels", BCP 14, RFC 2119, March 1997. 372 10.2. Informative References 374 [Levis04] Levis, P., Patel, N., Culler, D., and S. Shenker, 375 "Trickle: A Self-Regulating Algorithm for Code Propagation 376 and Maintenance in Wireless Sensor Networks"", Proceedings 377 of the First USENIX/ACM Symposium on Networked Systems 378 Design and Implementation NSDI 2004, March 2004, 379 . 381 [Levis08] Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S., 382 Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and A. 383 Woo, "The Emergence of a Networking Primitive in Wireless 384 Sensor Networks", Communications of the ACM, v.51 n.7, 385 July 2008, 386 . 388 Authors' Addresses 390 Philip Levis 391 Stanford University 392 358 Gates Hall, Stanford University 393 Stanford, CA 94305 394 USA 396 Phone: +1 650 725 9064 397 Email: pal@cs.stanford.edu 399 Thomas Heide Clausen 400 LIX, Ecole Polytechnique 402 Phone: +33 6 6058 9349 403 Email: T.Clausen@computer.org 405 Jonathan Hui 406 Arch Rock Corporation 407 501 Snd St., Suite 410 408 San Francisco, CA 94107 409 USA 411 Email: jhui@archrock.com 412 Omprakash Gnawali 413 Stanford University 414 S255 Clark Center, 318 Campus Drive 415 Stanford, CA 94305 416 USA 418 Phone: +1 650 725 6086 419 Email: gnawali@cs.stanford.edu 421 JeongGil Ko 422 Johns Hopkins University 423 3400 N. Charles St., 224 New Engineering Building 424 Baltimore, MD 21218 425 USA 427 Phone: +1 410 516 4312 428 Email: jgko@cs.jhu.edu