RFC 6206

The Trickle Algorithm

📅 published March 2011, from ietf

RFC 6206: The Trickle Algorithm 🦋

Okay bestie, this one is the Trickle Algorithm, and it's published as Standards Track by the IETF in March 2011, with ISSN 2070-1721. 💖 The authors are P. Levis (Stanford University), T. Clausen (LIX, Ecole Polytechnique), J. Hui (Arch Rock Corporation), O. Gnawali (Stanford University), and J. Ko (Johns Hopkins University) 🫶. The title block doesn't list anything it obsoletes or updates, so it's standing on its own ✨.

Abstract

Trickle lets nodes on a lossy shared medium (think low-power and lossy networks 🌸) swap information in a way that's highly robust, energy efficient, simple, and scalable 💅. It changes how often nodes transmit, so new information spreads at about the speed of a single link-layer transmission 🔥, but when nothing has changed, a node only sends a few messages per hour 🌙. A simple suppression mechanism and a way of picking transmission points keep the communication rate growing logarithmically with density, which is honestly iconic 👑. This document explains the Trickle algorithm and the things to keep in mind when you use it 🎀.

Status of This Memo

This is an Internet Standards Track document 💜.

This document comes from the Internet Engineering Task Force (IETF) 🧚. It reflects the consensus of the IETF community, got public review, and was approved for publication by the Internet Engineering Steering Group (IESG) ✅. More info about Internet Standards is in Section 2 of RFC 5741 📚.

For the current status, any errata, and how to send feedback, check http://www.rfc-editor.org/info/rfc6206 🍓.

Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved 🌈.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as they stand on the publication date. Please read these carefully, because they spell out your rights and restrictions for this document 🙈. Code Components pulled out of this document must include Simplified BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come with no warranty, as the Simplified BSD License describes 💀.

Table of Contents

1. Introduction ....................................................2
2. Terminology .....................................................3
3. Trickle Algorithm Overview ......................................3
4. Trickle Algorithm ...............................................5
   4.1. Parameters and Variables ...................................5
   4.2. Algorithm Description ......................................5
5. Using Trickle ...................................................6
6. Operational Considerations ......................................7
   6.1. Mismatched Redundancy Constants ............................7
   6.2. Mismatched Imin ............................................7
   6.3. Mismatched Imax ............................................8
   6.4. Mismatched Definitions .....................................8
   6.5. Specifying the Constant k ..................................8
   6.6. Relationship between k and Imin ............................8
   6.7. Tweaks and Improvements to Trickle .........................9
   6.8. Uses of Trickle ............................................9
7. Acknowledgements ...............................................10
8. Security Considerations ........................................10
9. References .....................................................11
   9.1. Normative References ......................................11
   9.2. Informative References ....................................11

1. Introduction ✨

Trickle sets up a density-aware local communication primitive, with an underlying consistency model that decides when a node transmits 💖. If a node's data doesn't match its neighbors', that node talks fast to sort out the mismatch (e.g., in milliseconds ⚡). When everyone agrees, they slow down exponentially, so nodes send packets super rarely (e.g., a few packets per hour 😴). Rather than flooding the network with packets, the algorithm controls the send rate so each node hears a small trickle of packets, just enough to stay consistent 🌸. It also relies only on local communication (e.g., broadcast or local multicast), which means it handles network re-population, is robust to transience, loss, and disconnection, is simple to implement, and needs very little state 💅. Current implementations use 4-11 bytes of RAM and are 50-200 lines of C code [Levis08] 🧚.

Trickle was first built for reprogramming protocols (where the data is the code of the program being updated) 💻, but people have found it's a powerful mechanism for lots of protocol design problems, including control traffic timing, multicast propagation, and route discovery 🔥. The flexibility comes from being able to decide, case by case, what counts as "agreement" or an "inconsistency" 🫶. Section 6.8 shows a few examples of how the algorithm can be used 🎀.

This document describes the Trickle algorithm and gives guidelines for using it 📚. It also states requirements for protocol specifications that use Trickle 🦋. It doesn't report Trickle's performance or behavior results, and it doesn't walk through the algorithm's design in detail, so if you want that, go read [Levis04] and [Levis08] 🤓.

2. Terminology 💜

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119] 🌈.

This document also introduces the following terms ✨:

  • Trickle communication rate: the sum of the number of messages sent or received by the Trickle algorithm in an interval 📨.
  • Trickle transmission rate: the sum of the number of messages sent by the Trickle algorithm in an interval 📤.

3. Trickle Algorithm Overview 🍓

Trickle's core idea is simple. Every so often, a node transmits its data, unless it hears a few other transmissions whose data shows its own transmission is redundant 🙈. Examples of that data include routing state, software update versions, and the last multicast packet it heard 📦. This is how Trickle scales to thousand-fold swings in network density 📈, spreads updates quickly, spreads the transmission load evenly 🫶, survives short disconnections, handles network re-populations, and has very low maintenance overhead 🌱. For instance, routing beacons in the Collection Tree Protocol (CTP) [Gnawali09] only need to send on the order of a few packets per hour, but CTP can still react to topology changes in milliseconds 🔥.

Trickle sends all of its messages to a local communication address 📍. The exact address can depend on the underlying IP protocol and on how the higher-layer protocol uses Trickle 🧭. In IPv6, for example, it can be the link-local multicast address or another local multicast address 💫, while in IPv4 it can be the broadcast address (255.255.255.255) 📡.

A Trickle message has two possible outcomes. Either every node that hears it finds the message data is consistent with its own state, or a recipient spots an inconsistency 👀. An inconsistency can come from an out-of-date node hearing something new, or from an updated node hearing something old 🔁. As long as every node communicates in some way, either by receiving or transmitting, some node will notice the need for an update 🎉.

Here's a simple example 🧁. Say "up to date" is defined by version numbers (e.g., network configuration). If node A transmits that it has version V, but B has version V+1, then B knows A needs an update 💅. Likewise, if B transmits that it has version V+1, A knows it needs an update 🫶. If B broadcasts or multicasts updates, then all of its neighbors can receive them without having to announce their need 📣. Some of those recipients might not have even heard A's transmission 👂. In this example it doesn't matter who transmits first, A or B. The inconsistency gets detected either way ✨.

Because Trickle communication can be either transmission or reception, the algorithm works in sparse networks as well as dense ones 🌟. A single disconnected node has to transmit at the Trickle communication rate 🥺. In a lossless, single-hop network of size n, the Trickle communication rate at each node equals the sum of the Trickle transmission rates across all nodes 🧮. The algorithm balances the load in that scenario, because each node's Trickle transmission rate is 1/nth of the Trickle communication rate ⚖️. Sparser networks need more transmissions per node, but the utilization of a given broadcast domain (e.g., radio channel over space, shared medium) doesn't go up 📻. That's a big deal in wireless networks and other shared media, where the channel is a precious shared resource 💎. Reducing transmissions in dense networks also saves system energy 🔋.

4. Trickle Algorithm 🎀

This section describes the Trickle algorithm 🦋.

4.1. Parameters and Variables 🧩

A Trickle timer runs for a defined interval and has three configuration parameters: the minimum interval size Imin, the maximum interval size Imax, and a redundancy constant k ⏱️:

  • The minimum interval size, Imin, is defined in units of time (e.g., milliseconds, seconds) ⏳. For example, a protocol might define the minimum interval as 100 milliseconds 💫.
  • The maximum interval size, Imax, is described as a number of doublings of the minimum interval size (the base-2 log(max/min)) 📈. For example, a protocol might define Imax as 16 🌸. If the minimum interval is 100 ms, then the amount of time specified by Imax is 100 ms * 65,536, i.e., 6,553.6 seconds or approximately 109 minutes 🤯.
  • The redundancy constant, k, is a natural number (an integer greater than zero) 🔢.

On top of those three parameters, Trickle keeps track of three variables 🧠:

  • I, the current interval size,
  • t, a time within the current interval, and
  • c, a counter.

Next up: Section 4.2 and the algorithm walkthrough 💖.

4.2. Algorithm Description 🦋

okay so Trickle has six rules and they're honestly so elegant 😭💖

  1. when the algorithm starts running, it sets I to some value in the range [Imin, Imax], so I is greater than or equal to Imin and less than or equal to Imax. then it kicks off the very first interval ✨
  2. when an interval begins, Trickle resets c to 0 and picks a random point t in the range [I/2, I). that means t is greater than or equal to I/2 but less than I. the interval wraps up at I 🫶
  3. whenever Trickle hears a transmission that's "consistent", it bumps the counter c up by one 🍓
  4. at time t, Trickle transmits if and only if c is less than the redundancy constant k 💅
  5. when the interval I expires, Trickle doubles the interval length. if that new length would be longer than Imax, Trickle just sets I to Imax instead 🌸
  6. if Trickle hears a transmission that's "inconsistent" and I is greater than Imin, it resets the timer. to reset, Trickle sets I to Imin and starts a fresh interval just like step 2. but if I is already equal to Imin when an "inconsistent" transmission shows up, Trickle does nothing. Trickle can also reset its timer when an external "events" happens 🔥

the words "consistent", "inconsistent", and "events" are in quotes on purpose, bestie, because what they actually mean depends on how a protocol uses Trickle 🧚

the only time Trickle transmits is at step 4. so there's an inherent delay between noticing an inconsistency (shrinking I down to Imin) and actually responding to it (transmitting at time t in the new interval). and this is intentional 🙈 if every node responded the second it noticed a problem, you could get a broadcast storm, where a bunch of nodes all reply at once in a synchronized way. by making responses follow the Trickle algorithm (with the minimal interval size), a protocol gets to use Trickle's suppression mechanism and can scale across a huge range of node densities. literally genius 👑

5. Using Trickle 🎀

a protocol specification that uses Trickle MUST specify:

  • default values for Imin, Imax, and k. link layers can vary a lot in their properties, so the default value of Imin SHOULD be specified in terms of the worst-case latency of a link-layer transmission. for example, a spec should say "the default value of Imin is 4 times the worst-case link-layer latency", and should not say "the default value of Imin is 500 milliseconds". worst-case latency is roughly the time until the first link-layer transmission of the frame, assuming an idle channel (it doesn't include backoff, virtual carrier sense, etc.) 💖
  • what counts as a "consistent" transmission ✨
  • what counts as an "inconsistent" transmission 🌈
  • what "events", if any (other than inconsistent transmissions), reset the Trickle timer ⭐
  • what information a node transmits in Trickle messages 🍓
  • what actions outside the algorithm the protocol takes, if any, when it detects an inconsistency 🧚

6. Operational Considerations 💜

a protocol that uses Trickle RECOMMENDED includes mechanisms to tell nodes about configuration parameters at runtime. hmm, wait, let me say that properly: it is RECOMMENDED that a protocol using Trickle includes mechanisms to inform nodes of configuration parameters at runtime 🫶 but it isn't always possible to do that. when different nodes have different configuration parameters, Trickle can have unintended behaviors. this section walks through some of those behaviors and operational considerations as educational exercises 📚

6.1. Mismatched Redundancy Constants 💅

if nodes don't agree on the redundancy constant k, then nodes with higher k values will transmit more often than nodes with lower ones. sometimes this extra load has nothing to do with density 😭 for example, picture a network where all nodes but one have k=1, and that one node has k=2. the different node can end up transmitting on every interval, since it's keeping a Trickle communication rate of 2 with only itself. so the danger of mismatched k values is uneven transmission load, which can drain the energy of some nodes in a low-power network 🔋

6.2. Mismatched Imin 🌸

if nodes don't agree on Imin, then some nodes will transmit sooner than others after hearing inconsistent messages. those faster nodes grow their intervals to a size similar to the slower nodes' within a single slow interval, but during that time they might suppress the slower nodes. that suppression ends after the first slow interval, once the nodes generally agree on the interval size. so mismatched Imin values usually aren't a big deal 🙌 also, note that mismatched Imin values together with matching Imax doubling constants will lead to mismatched maximum interval lengths 🧐

6.3. Mismatched Imax 🔥

if nodes don't agree on Imax, that can cause long-term problems with transmission load 😬 nodes with small Imax values transmit faster, which suppresses the ones with larger Imax values. those larger-Imax nodes are always suppressed, so they never get to transmit. in the base case, when the network is consistent, this can create long-term inequities in energy cost 🥲

6.4. Mismatched Definitions 🙈

if nodes don't agree on what counts as a consistent or inconsistent transmission, Trickle may fail to work properly. for example, say a receiver thinks a transmission is consistent, but the transmitter (if it were in the receiver's situation) would have thought it inconsistent. then the receiver won't respond properly or let the transmitter know, and the network can get stuck and fail to reach a consistent state 😵 for this reason, unlike the configuration constants k, Imin, and Imax, consistency definitions MUST be clearly stated in the protocol and SHOULD NOT be configured at runtime 🚫

6.5. Specifying the Constant k 💀

there are a few edge cases where a protocol might want to use Trickle with its suppression turned off (k is set to infinity). in general this is super dangerous, so it is NOT RECOMMENDED 🚨 turning off suppression means every node always sends on every interval, which can cause congestion in dense networks. it's especially risky if a lot of nodes reset their intervals at the same time. in general it's much better to set k to a high value (e.g., 5 or 10) than to infinity. typical values for k are 1-5, since those strike a good balance between redundancy and low cost [Levis08] ⚖️

still, there are situations where a protocol may want to turn off Trickle suppression. because k is a natural number (Section 4.1), k=0 has no useful meaning. if a protocol lets k be dynamically configured, a value of 0 just goes unused. and for ease of debugging and packet inspection, having the parameter describe k-1 instead of k can be confusing 🤔 so instead, it is RECOMMENDED that protocols which need to turn off suppression reserve k=0 to mean k=infinity 🧚

6.6. Relationship between k and Imin 🎀

finally, a protocol SHOULD set k and Imin so that Imin is at least two to three times as long as it takes to transmit k packets. otherwise, if more than k nodes reset their intervals to Imin, the resulting communication leads to congestion and significant packet loss 📉 experimental results have shown that packet losses from congestion reduce Trickle's efficiency [Levis04] 🫠

6.7. Tweaks and Improvements to Trickle 💅

Trickle is built on a small number of simple, tightly integrated mechanisms that are super robust in challenging network environments 💪 from our experience using Trickle, attempts to tweak its behavior usually aren't worth the cost. as written, the algorithm is already highly efficient. further cuts to transmissions or response time come at the cost of failures in edge cases. so based on what we've seen, we really urge protocol designers to resist the urge to tweak or improve Trickle unless there's a ton of experimental evidence that the change doesn't violate its assumptions and break the algorithm in edge cases 🛑

with that warning in mind, Trickle is far from perfect 😅 for example, Trickle suppression typically makes sparser nodes transmit more than denser ones. it's far from the optimal computation of a minimum cover. but in dynamic network environments like wireless and low-power, lossy networks, the coordination needed to compute the optimal set of transmissions is usually way more than the benefits it gives you. one of Trickle's biggest perks is that it's so simple to implement, needs so little state, and still runs so efficiently ✨ any effort to improve it should be weighed against the cost of added complexity 🧠

6.8. Uses of Trickle 🌈

the Trickle algorithm has been used in a variety of protocols, in both operational and academic settings 🎓 a quick overview of some of these uses gives useful examples of how and when it can be used. these examples shouldn't be considered exhaustive 🙌

Reliable flooding/dissemination: a protocol uses Trickle to periodically advertise the most recent data it has received, usually through a version number. an inconsistency happens when a node hears a newer version number or receives new data. a consistency happens when a node hears an older or equal version number. when hearing an older version number, instead of resetting its own Trickle timer, the node sends an update. nodes with old version numbers that receive that update then reset their own timers, which leads to fast propagation of the new data 🚀 examples of this use include multicast [Hui08a], network configuration [Lin08] [Dang09], and installing new application programs [Hui04] [Levis04] 💖

Routing control traffic: a protocol uses Trickle to control when it sends beacons that carry routing state. an inconsistency happens when the routing topology changes in a way that could lead to loops or significant stretch. examples include when the routing layer detects a routing loop or when a node's routing cost changes significantly 😱 a consistency happens when the routing topology is working well and delivering packets successfully ✅ using Trickle this way lets a routing protocol react very quickly to problems (Imin is small) but send very few beacons when the topology is stable 🥰 examples of this use include the IPv6 routing protocol for low-power and lossy networks (RPL) [RPL], CTP [Gnawali09], and some current commercial IPv6 routing layers [Hui08b] 👑

7. Acknowledgements 🫶

the authors would like to acknowledge the guidance and input provided by the ROLL chairs, David Culler and JP Vasseur 💜

the authors would also like to acknowledge the helpful comments of Yoav Ben-Yehezkel, Alexandru Petrescu, and Ulrich Herberg, which greatly improved the document 🌸

8. Security Considerations ✨

okay bestie, so Trickle itself is just an algorithm, which means it doesn't have any specific security considerations on its own 💅. BUT when you actually use Trickle inside a protocol, two security concerns can pop up 🙈. The first one: an adversary can force nodes to send way more packets than they need by forcing Trickle timer resets. In low-power networks, all that extra traffic can seriously hurt the system's lifetime 😭🔋. The second one: an adversary can stop nodes from ever reaching consistency 💀.

Protocols can prevent adversarial Trickle resets by being super careful about what is allowed to cause a reset, and by protecting those events and messages with proper security mechanisms 🛡️. For example, if a node can reset nearby Trickle timers by sending a certain packet, that packet should be authenticated so an adversary can't forge one 🔐. Main character energy for security 👑.

Now the consistency problem, which is kind of scary 😱. An adversary can possibly keep nodes from reaching consistency by suppressing transmissions with "consistent" messages 🙅‍♀️. Picture this: node A detects an inconsistency and resets its Trickle timer. If an adversary can stop A from sending messages that tell nearby nodes about the inconsistency (so it can get repaired), then A may remain inconsistent indefinitely 🥺. Depending on the security model of the network, authenticated messages or a transitive notion of consistency can prevent this problem ✨.

Let's say an adversary wants to stop A from notifying its neighbors. To do that, it has to send messages that are consistent with A. But those messages are, by definition, inconsistent with what A's neighbors have 🤯. So the adversary can't both keep A from notifying neighbors AND avoid notifying them itself. Remember, Trickle operates on shared, broadcast media 📡. Which means... Trickle should filter unicast messages 🎀. Iconic, honestly.

9. References ✨

9.1. Normative References

  • [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.

9.2. Informative References

  • [Dang09] Dang, T., Bulusu, N., Feng, W., and S. Park, "DHV: A Code Consistency Maintenance Protocol for Multi-hop Wireless Networks", Wireless Sensor Networks: 6th European Conference Proceedings EWSN 2009 Cork, February 2009, <http://portal.acm.org/citation.cfm?id=1506781>.
  • [Gnawali09] Gnawali, O., Fonseca, R., Jamieson, K., Moss, D., and P. Levis, "Collection Tree Protocol", Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems, SenSys 2009, November 2009, <http://portal.acm.org/citation.cfm?id=1644038.1644040>.
  • [Hui04] Hui, J. and D. Culler, "The dynamic behavior of a data dissemination protocol for network programming at scale", Proceedings of the 2nd ACM Conference on Embedded Networked Sensor Systems, SenSys 2004, November 2004, <http://portal.acm.org/citation.cfm?id=1031506>.
  • [Hui08a] Hui, J., "An Extended Internet Architecture for Low-Power Wireless Networks - Design and Implementation", UC Berkeley Technical Report EECS-2008-116, September 2008, <http://www.eecs.berkeley.edu/Pubs/>.
  • [Hui08b] Hui, J. and D. Culler, "IP is dead, long live IP for wireless sensor networks", Proceedings of the 6th ACM Conference on Embedded Networked Sensor Systems, SenSys 2008, November 2008, <http://portal.acm.org/citation.cfm?id=1460412.1460415>.
  • [Levis04] Levis, P., Patel, N., Culler, D., and S. Shenker, "Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks", Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation, NSDI 2004, March 2004, <http://portal.acm.org/citation.cfm?id=1251177>.
  • [Levis08] Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S., Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and A. Woo, "The Emergence of a Networking Primitive in Wireless Sensor Networks", Communications of the ACM, Vol. 51 No. 7, July 2008, <http://portal.acm.org/citation.cfm?id=1364804>.
  • [Lin08] Lin, K. and P. Levis, "Data Discovery and Dissemination with DIP", Proceedings of the 7th international conference on Information processing in sensor networks, IPSN 2008, April 2008, <http://portal.acm.org/citation.cfm?id=1371607.1372753>.
  • [RPL] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Clausen, T., Hui, J., Kelsey, R., Levis, P., Pister, K., Struik, R., and JP. Vasseur, "RPL: IPv6 Routing Protocol for Low power and Lossy Networks", Work in Progress, March 2011.

Authors' Addresses 🎀

Philip Levis
Stanford University
358 Gates Hall
Stanford, CA  94305
USA

Phone: +1 650 725 9064
EMail: pal@cs.stanford.edu


Thomas Heide Clausen
LIX, Ecole Polytechnique

Phone: +33 6 6058 9349
EMail: T.Clausen@computer.org


Jonathan Hui
Arch Rock Corporation
501 2nd St., Suite 410
San Francisco, CA  94107
USA

EMail: jhui@archrock.com


Omprakash Gnawali
Stanford University
S255 Clark Center, 318 Campus Drive
Stanford, CA  94305
USA

Phone: +1 650 725 6086
EMail: gnawali@cs.stanford.edu


JeongGil Ko
Johns Hopkins University
3400 N. Charles St., 224 New Engineering Building
Baltimore, MD  21218
USA

Phone: +1 410 516 4312
EMail: jgko@cs.jhu.edu
📦 where this page comes from