idnits 2.17.1 draft-ietf-roll-trickle-01.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 (April 10, 2010) is 5123 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: October 12, 2010 LIX, Ecole Polytechnique 6 J. Hui 7 Arch Rock Corporation 8 J. Ko 9 Johns Hopkins University 10 April 10, 2010 12 The Trickle Algorithm 13 draft-ietf-roll-trickle-01 15 Abstract 17 The Trickle algorithm allows wireless nodes to exchange information 18 in a highly robust, energy efficient, simple, and scalable manner. 19 Dynamically adjusting transmission windows allows Trickle to spread 20 new information on the scale of link-layer transmission times while 21 sending only a few messages per hour when information does not 22 change. A simple suppression nechanism and transmission point 23 selection allows Trickle's communication rate to scale 24 logarithmically with density. This document describes Trickle and 25 considerations in its use. 27 Status of this Memo 29 This Internet-Draft is submitted to IETF in full conformance with the 30 provisions of BCP 78 and BCP 79. 32 Internet-Drafts are working documents of the Internet Engineering 33 Task Force (IETF), its areas, and its working groups. Note that 34 other groups may also distribute working documents as Internet- 35 Drafts. 37 Internet-Drafts are draft documents valid for a maximum of six months 38 and may be updated, replaced, or obsoleted by other documents at any 39 time. It is inappropriate to use Internet-Drafts as reference 40 material or to cite them other than as "work in progress." 42 The list of current Internet-Drafts can be accessed at 43 http://www.ietf.org/ietf/1id-abstracts.txt. 45 The list of Internet-Draft Shadow Directories can be accessed at 46 http://www.ietf.org/shadow.html. 48 This Internet-Draft will expire on October 12, 2010. 50 Copyright Notice 52 Copyright (c) 2010 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents 57 (http://trustee.ietf.org/license-info) in effect on the date of 58 publication of this document. Please review these documents 59 carefully, as they describe your rights and restrictions with respect 60 to this document. Code Components extracted from this document must 61 include Simplified BSD License text as described in Section 4.e of 62 the Trust Legal Provisions and are provided without warranty as 63 described in the BSD License. 65 Table of Contents 67 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 68 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3 69 3. Trickle Algorithm Overview . . . . . . . . . . . . . . . . . . 3 70 4. Trickle Algorithm . . . . . . . . . . . . . . . . . . . . . . . 4 71 4.1. Parameters and Variables . . . . . . . . . . . . . . . . . 4 72 4.2. Algorithm Description . . . . . . . . . . . . . . . . . . . 5 73 5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . . 6 74 6. Operational Considerations . . . . . . . . . . . . . . . . . . 6 75 6.1. Mismatched redundancy constants . . . . . . . . . . . . . . 6 76 6.2. Mismatched Imin . . . . . . . . . . . . . . . . . . . . . . 6 77 6.3. Mismatched Imax . . . . . . . . . . . . . . . . . . . . . . 7 78 6.4. Mismatched definitions . . . . . . . . . . . . . . . . . . 7 79 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 7 80 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 7 81 9. Security Considerations . . . . . . . . . . . . . . . . . . . . 7 82 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 7 83 10.1. Normative References . . . . . . . . . . . . . . . . . . . 7 84 10.2. Informative References . . . . . . . . . . . . . . . . . . 8 85 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 8 87 1. Introduction 89 The Trickle algorithm is designed for wireless networks. It 90 establishes a density-aware local broadcast with an underlying 91 consistency model that guides when a node communicates. When a 92 node's data does not agree with its neighbors, it communicates 93 quickly to resolve the inconsistency. When nodes agree, they slow 94 their communicationrate exponentially, such that in a stable state 95 nodes send at most a few packets per hour. Instead of flooding a 96 network with packets, the algorithm controls the send rate so each 97 node hears a small trickle of packets, just enough to stay 98 consistent. Furthermore, by relying only on local broadcasts, 99 Trickle handles network re-population, is robust to network 100 transience, loss, and disconnection, and requires very little state 101 (implementations use 4-11 bytes). 103 While Trickle was originally designed for reprogramming protocols 104 (where the data is the code of the program being updated), experience 105 has shown it to be a powerful mechanism that can be applied to wide 106 range of protocol design problems. For example, routing protocols 107 such as RPL use Trickle to ensure that nodes in a given neighborhood 108 have consistent, loop-free routes. When the topology is consistent, 109 nodes occasionally gossip to check that they still agree, and when 110 the topology changes they gossip more frequently, until they reach 111 consistency again. 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 [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 mote transmits 130 code metadata if it has not heard a few other motes 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 mote 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 mote 141 hearing someone has new code, or an updated mote hearing someone has 142 old code. As long as every mote 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 mote, 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 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 Any "events" besides inconsistent transmissions that reset the 248 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 as an educational exercise. 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 will 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 7. Acknowledgements 305 8. IANA Considerations 307 This document has no IANA considerations.. 309 9. Security Considerations 311 This document has no security considerations. 313 10. References 315 10.1. Normative References 317 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 318 Requirement Levels", BCP 14, RFC 2119, March 1997. 320 10.2. Informative References 322 [Levis08] Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S., 323 Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and A. 324 Woo, "The Emergence of a Networking Primitive in Wireless 325 Sensor Networks", Communications of the ACM, v.51 n.7, 326 July 2008, 327 . 329 Authors' Addresses 331 Philip Levis 332 Stanford University 333 358 Gates Hall, Stanford University 334 Stanford, CA 94305 335 USA 337 Phone: +1 650 725 9064 338 Email: pal@cs.stanford.edu 340 Thomas Heide Clausen 341 LIX, Ecole Polytechnique 343 Phone: +33 6 6058 9349 344 Email: T.Clausen@computer.org 346 Jonathan Hui 347 Arch Rock Corporation 348 501 Snd St., Suite 410 349 San Francisco, CA 94107 350 USA 352 Email: jhui@archrock.com 354 JeongGil Ko 355 Johns Hopkins University 356 3100 Wyman Park Dr., Room 414 357 Baltimore, MD 21211 358 USA 360 Phone: +1 410 516 4312 361 Email: jgko@cs.jhu.edu