Networking Working Group                                        P. Levis
Internet-Draft                                       Stanford University
Intended status: Standards Track                              T. Clausen
Expires: July 14, 2011                          LIX, Ecole Polytechnique
                                                                  J. Hui
                                                   Arch Rock Corporation
                                                              O. Gnawali
                                                     Stanford University
                                                                   J. Ko
                                                Johns Hopkins University
                                                        January 10, 2011

                         The Trickle Algorithm


   The Trickle algorithm allows nodes in a lossy shared medium (e.g.,
   low power and lossy networks) to exchange information in a highly
   robust, energy efficient, simple, and scalable manner.  Dynamically
   adjusting transmission windows allows Trickle to spread new
   information on the scale of link-layer transmission times while
   sending only a few messages per hour when information does not
   change.  A simple suppression mechanism and transmission point
   selection allows Trickle's communication rate to scale
   logarithmically with density.  This document describes the Trickle
   algorithm and considerations in its use.

Status of this Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on July 14, 2011.

Copyright Notice

Levis, et al.             Expires July 14, 2011                 [Page 1]

Internet-Draft         draft-ietf-roll-trickle-08           January 2011

   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
   ( in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  3
   3.  Trickle Algorithm Overview . . . . . . . . . . . . . . . . . .  4
   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  . . . . . . . . . . . . .  9
     6.7.  Tweaks and Improvements to Trickle . . . . . . . . . . . .  9
     6.8.  Uses of Trickle  . . . . . . . . . . . . . . . . . . . . .  9
   7.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10
   8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 10
   9.  Security Considerations  . . . . . . . . . . . . . . . . . . . 10
   10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11
     10.1. Normative References . . . . . . . . . . . . . . . . . . . 11
     10.2. Informative References . . . . . . . . . . . . . . . . . . 11
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12

Levis, et al.             Expires July 14, 2011                 [Page 2]

Internet-Draft         draft-ietf-roll-trickle-08           January 2011

1.  Introduction

   The Trickle algorithm establishes a density-aware local communication
   primitive with an underlying consistency model that guides when a
   node transmits.  When a node's data does not agree with its
   neighbors, that node communicates quickly to resolve the
   inconsistency (e.g., in milliseconds).  When nodes agree, they slow
   their communication rate exponentially, such that nodes send packets
   very infrequently (e.g., a few packets per hour).  Instead of
   flooding a network with packets, the algorithm controls the send rate
   so each node hears a small trickle of packets, just enough to stay
   consistent.  Furthermore, by relying only on local communication
   (e.g., broadcast or local multicast), Trickle handles network re-
   population, is robust to network transience, loss, and disconnection,
   is simple to implement, and requires very little state.  Current
   implementations use 4-11 bytes of RAM and are 50-200 lines of C

   While Trickle was originally designed for reprogramming protocols
   (where the data is the code of the program being updated), experience
   has shown it to be a powerful mechanism that can be applied to wide
   range of protocol design problems, including control traffic timing,
   multicast propagation, and route discovery.  This flexibility stems
   from being able to define, on a case-by-case basis, what constitutes
   "agreement" or an "inconsistency;" Section 6.8 presents a few
   examples of how the algorithm can be used.

   This document describes the Trickle algorithm and provides guidelines
   for its use.  It also states requirements for protocol specifications
   that use Trickle.  This document does not provide results on
   Trickle's performance or behavior, nor does it explain the
   algorithm's design in detail: interested readers should refer to
   [Levis04] and [Levis08].

2.  Terminology

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

   Additionally, this document introduces the following terminology:

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

Levis, et al.             Expires July 14, 2011                 [Page 3]

Internet-Draft         draft-ietf-roll-trickle-08           January 2011

   Trickle transmission rate:  the sum of the number of messages sent by
         the Trickle algorithm in an interval.

3.  Trickle Algorithm Overview

   Trickle's basic primitive is simple: every so often, a node transmits
   data unless it hears a few other transmissions whose data suggest its
   own transmission is redundant.  Examples of such data include routing
   state, software update versions, and the last heard multicast packet.
   This primitive allows Trickle to scale to thousand-fold variations in
   network density, quickly propagate updates, distribute transmission
   load evenly, be robust to transient disconnections, handle network
   repopulations, and impose a very low maintenance overhead: one
   example use, routing beacons in the CTP protocol [Gnawali09],
   requires sending on the order of a few packets per hour yet can
   respond in milliseconds.

   Trickle sends all messages to a local communication address.  The
   exact address used can depend on both the underlying IP protocol as
   well as 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

   There are two possible results to a Trickle message: either every
   node that hears the message finds the message data is consistent with
   its own state, or a recipient detects an inconsistency.  Detection
   can be the result of either an out-of-date node hearing something
   new, or an updated node hearing something old.  As long as every node
   communicates somehow - either receives or transmits - some node will
   detect the need for an update.

   For example, consider a simple case where "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 that A
   needs an update.  Similarly, if B transmits that it has version V+1,
   A knows that it needs an update.  If B broadcasts or multicasts
   updates, then all of its neighbors can receive them without having to
   advertise their need.  Some of these recipients might not have even
   heard A's transmission.  In this example, it does not matter who
   first transmits, A or B; either case will detect the inconsistency.

   The fact that Trickle communication can be either transmission or
   reception enables the Trickle algorithm to operate in sparse as well
   as dense networks.  A single, disconnected node must 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

Levis, et al.             Expires July 14, 2011                 [Page 4]

Internet-Draft         draft-ietf-roll-trickle-08           January 2011

   the Trickle transmission rates across all nodes.  The Trickle
   algorithm balances the load in such a scenario, as each node's
   Trickle transmission rate is 1/nth of the Trickle communication rate.
   Sparser networks require more transmissions per node, but the
   utilization of a given broadcast domain (e.g., radio channel over
   space, shared medium) will not increase.  This is an important
   property in wireless networks and other shared media, where the
   channel is a valuable shared resource.  Additionally, reducing
   transmissions in dense networks conserves 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:

   o  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.

   o  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 100ms, then the amount of time specified by Imax is
      100ms * 65536, 6,553.6 seconds, or approximately 109 minutes.

   o  The redundancy constant is a natural number (an integer greater
      than zero).

   In addition to these three parameters, Trickle maintains three

   o  I, the current interval size

   o  t, a time within the current interval, and

   o  c, a counter.

4.2.  Algorithm Description

   The Trickle algorithm has six rules:

Levis, et al.             Expires July 14, 2011                 [Page 5]

Internet-Draft         draft-ietf-roll-trickle-08           January 2011

   1.  When the algorithm starts execution, it sets I to a value in the
       range of [Imin, Imax], that is, greater than or equal to Imin and
       less then or equal to Imax.  The algorithm then begins the first

   2.  When an interval begins, Trickle resets c to 0 and sets t to a
       random point in the interval, taken from the range [I/2, I), that
       is, values greater than or equal to I/2 and less than I. The
       interval ends at I.

   3.  Whenever Trickle hears a transmission that is "consistent," it
       increments the counter c.

   4.  At time t, Trickle transmits if and only if the counter c is less
       than the redundancy constant k.

   5.  When the interval I expires, Trickle doubles the interval length.
       If this new interval length would be longer than the time
       specified by Imax, Trickle sets the interval length I to be the
       time specified by Imax.

   6.  If Trickle hears a transmission that is "inconsistent" and I is
       greater than Imin, it resets the Trickle timer.  To reset the
       timer, Trickle sets I to Imin and starts a new interval as in
       step 2.  If I is equal to Imin when Trickle hears an
       "inconsistent" transmission, Trickle does nothing.  Trickle can
       also reset its timer in response to external "events."

   The terms consistent, inconsistent and event are in quotes because
   their meaning depends on how a protocol uses Trickle.

   The only time the Trickle algorithm transmits is at step 3 of the
   above algorithm.  This means there is an inherent delay between
   detecting an inconsistency (shrinking I to Imin) and responding to
   that inconsistency (transmitting at time t in the new interval).
   This is intentional.  Immediately responding to detecting an
   inconsistency can cause a broadcast storm, where many nodes respond
   at once and in a synchronized fashion.  By making responses follow
   the Trickle algorithm (with the minimal interval size), a protocol
   can benefit from Trickle's suppression mechanism and scale across a
   huge range of node densities.

5.  Using Trickle

   A protocol specification that uses Trickle MUST specify:

Levis, et al.             Expires July 14, 2011                 [Page 6]

Internet-Draft         draft-ietf-roll-trickle-08           January 2011

   o  Default values for Imin, Imax, and k.  Because link layers can
      vary widely in their properties, the default value of Imin SHOULD
      be specified in terms of the worst-case latency of a link layer
      transmission.  For example, a specification 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 approximately time until the
      first link-layer transmission of the frame assuming an idle
      channel (does not include backoff, virtual carrier sense, etc.).

   o  What constitutes a "consistent" transmission.

   o  What constitutes an "inconsistent" transmission.

   o  What "events," if any, besides inconsistent transmissions that
      reset the Trickle timer.

   o  What information a node transmits in Trickle messages.

   o  What actions outside the algorithm the protocol takes, if any,
      when it detects an inconsistency.

6.  Operational Considerations

   It is RECOMMENDED that a protocol which uses Trickle includes
   mechanisms to inform nodes of configuration parameters at runtime.
   However, it is not always possible to do so.  In the cases where
   different nodes have different configuration parameters, Trickle may
   have unintended behaviors.  This section outlines some of those
   behaviors and operational considerations as educational exercises.

6.1.  Mismatched Redundancy Constants

   If nodes do not agree on the redundancy constant k, then nodes with
   higher values of k will transmit more often than nodes with lower
   values of k.  In some cases, this increased load can be independent
   of the density.  For example, consider a network where all nodes but
   one have k=1, and this one node has k=2.  The different node can end
   up transmitting on every interval: it is maintaining a Trickle
   communication rate of 2 with only itself.  Hence, the danger of
   mismatched k values is uneven transmission load that can deplete the
   energy of some nodes in a low power network.

6.2.  Mismatched Imin

   If nodes do not agree on Imin, then some nodes, on hearing
   inconsistent messages, will transmit sooner than others.  These

Levis, et al.             Expires July 14, 2011                 [Page 7]

Internet-Draft         draft-ietf-roll-trickle-08           January 2011

   faster nodes will have their intervals grow to similar size as the
   slower nodes within a single slow interval time, but in that period
   may suppress the slower nodes.  However, such suppression will end
   after the first slow interval, when the nodes generally agree on the
   interval size.  Hence, mismatched Imin values are usually not a
   significant concern.  Note that mismatched Imin values and matching
   Imax doubling constants will lead to mismatched maximum interval

6.3.  Mismatched Imax

   If nodes do not agree on Imax, then this can cause long-term problems
   with transmission load.  Nodes with small Imax values will transmit
   faster, suppressing those with larger Imax values.  The nodes with
   larger Imax values, always suppressed, will never transmit.  In the
   base case, when the network is consistent, this can cause long-term
   inequities in energy cost.

6.4.  Mismatched Definitions

   If nodes do not agree on what constitutes a consistent or
   inconsistent transmission, then Trickle may fail to operate properly.
   For example, if a receiver thinks a transmission is consistent, but
   the transmitter (if in the receivers situation) would have thought it
   inconsistent, then the receiver will not respond properly and inform
   the transmitter.  This can lead the network to not 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 some edge cases where a protocol may wish to use Trickle
   with its suppression disabled (k is set to infinity).  In general,
   this approach is highly dangerous and it is NOT RECOMMENDED.
   Disabling suppression means that every node will always send on every
   interval, and can lead to congestion in dense networks.  This
   approach is especially dangerous if many nodes reset their intervals
   at the same time.  In general, it is much more desirable to set k to
   a high value (e.g., 5 or 10) than infinity.  Typical values for k are
   1-5: these achieve a good balance between redundancy and low

   Nevertheless, there are situations where a protocol may wish to turn
   off Trickle suppression.  Because k is a natural number
   (Section 4.1), k=0 has no useful meaning.  If a protocol allows k to
   be dynamically configured, a value of 0 remains unused.  For ease of
   debugging and packet inspection, having the parameter describe k-1

Levis, et al.             Expires July 14, 2011                 [Page 8]

Internet-Draft         draft-ietf-roll-trickle-08           January 2011

   rather than k can be confusing.  Instead, it is RECOMMENDED that
   protocols which require turning off suppression reserve k=0 to mean

6.6.  Relationship Between k and Imin

   Finally, a protocol SHOULD set k and Imin such 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 will lead 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 based on a small number of simple, tightly integrated
   mechanisms that are highly robust to challenging network
   environments.  In our experiences using Trickle, attempts to tweak
   its behavior are typically not worth the cost.  As written, the
   algorithm is already highly efficient: further reductions in
   transmissions or response time come at the cost of failures in edge
   cases.  Based on our experiences, we urge protocol designers to
   suppress the instinct to tweak or improve Trickle without a great
   deal of experimental evidence that the change does not violate its
   assumptions and break the algorithm in edge cases.

   This warning in mind, Trickle is far from perfect.  For example,
   Trickle suppression typically leads sparser nodes to transmit more
   than denser ones; it is far from the optimal computation of a minimum
   cover.  However, in dynamic network environments such as wireless and
   low-power, lossy networks, the coordination needed to compute the
   optimal set of transmissions is typically much greater than the
   benefits it provides.  One of the benefits of Trickle is that it is
   so simple to implement and requires so little state yet operates so
   efficiently.  Efforts to improve it should be weighed against the
   cost of increased complexity.

6.8.  Uses of Trickle

   The Trickle algorithm has been used in a variety of protocols, both
   in operational as well as academic settings.  Giving a brief overview
   of some of these uses provides useful examples of how and when it can
   be used.  These examples should not be considered exhaustive.

   Reliable flooding/dissemination: A protocol uses Trickle to
   periodically advertise the most recent data it has received,
   typically through a version number.  An inconsistency is when a node
   hears a newer version number or receives new data.  A consistency is

Levis, et al.             Expires July 14, 2011                 [Page 9]

Internet-Draft         draft-ietf-roll-trickle-08           January 2011

   when a node hears an older or equal version number.  When hearing an
   older version number, rather than reset its own Trickle timer, it
   sends an update.  Nodes with old version numbers that receive the
   update will then reset their own timers, leading to fast propagation
   of the new data.  Examples of this use include multicast[Hui08a],
   network configuration[Lin08][Dang09], and installing new application

   Routing control traffic: A protocol uses Trickle to control when it
   sends beacons which contain routing state.  An inconsistency is 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.
   Consistency is when the routing topology is operating well and is
   delivering packets successfully.  Using the Trickle algorithm in this
   way allows a routing protocol to react very quickly to problems (Imin
   is small) but send very few beacons when the topology is stable.
   Examples of this use include RPL[I-D.ietf-roll-rpl], CTP[Gnawali09],
   and some current commericial 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.  IANA Considerations

   This document has no IANA considerations.

9.  Security Considerations

   As it is an algorithm, Trickle itself does not have any specific
   security considerations.  However, two security concerns can arise
   when Trickle is used in a protocol.  The first is that an adversary
   can force nodes to send many more packets than needed by forcing
   Trickle timer resets.  In low power networks this increase in traffic
   can harm system lifetime.  The second concern is that an adversary
   can prevent nodes from reaching consistency.

   Protocols can prevent adversarial Trickle resets by carefully
   selecting what can cause a reset and protecting these events and

Levis, et al.             Expires July 14, 2011                [Page 10]

Internet-Draft         draft-ietf-roll-trickle-08           January 2011

   messages with proper security mechanisms.  For example, if a node can
   reset nearby Trickle timers by sending a certain packet, this packet
   should be authenticated such that an adversary cannot forge one.

   An adversary can possibly prevent nodes from reaching consistency by
   suppressing transmissions with "consistent" messages.  For example,
   imagine node A detects an inconsistency and resets its Trickle timer.
   If an adversary can prevent A from sending messages that inform
   nearby nodes of the inconsistency in order to repair it, 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.  E.g., if messages that are
   consistent with A and so suppress its transmissions are by definition
   inconsistent with what A heard, then an adversary cannot
   simultaneously prevent A from notifying neighbors and not notify the
   neighbors itself (recall Trickle operates on shared, broadcast
   media).  Note that this means Trickle should filter unicast messages.

10.  References

10.1.  Normative References

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

10.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,

              Gnawali, O., Fonseca, R., Jamieson, K., Moss, D., and P.
              Levis, "Collection Tree Protocol", Proceedings of the 7th
              ACM Conference on Embedded Networked Systems SenSys 2009,
              November 2009,

   [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 Systems SenSys 2004, November 2004,

   [Hui08a]   Hui, J., "An Extended Internet Architecture for Low-Power

Levis, et al.             Expires July 14, 2011                [Page 11]

Internet-Draft         draft-ietf-roll-trickle-08           January 2011

              Wireless Networks - Design and Implementation", UC
              Berkeley Technical Report EECS-2008-116, September 2008,

   [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 Systems SenSys 2008,
              November 2008,

              Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J.,
              Kelsey, R., Levis, P., Pister, K., Struik, R., and J.
              Vasseur, "RPL: IPv6 Routing Protocol for Low power and
              Lossy Networks", draft-ietf-roll-rpl-17 (work in
              progress), December 2010.

   [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,

   [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, v.51 n.7,
              July 2008,

   [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,

Levis, et al.             Expires July 14, 2011                [Page 12]

Internet-Draft         draft-ietf-roll-trickle-08           January 2011

Authors' Addresses

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

   Phone: +1 650 725 9064

   Thomas Heide Clausen
   LIX, Ecole Polytechnique

   Phone: +33 6 6058 9349

   Jonathan Hui
   Arch Rock Corporation
   501 Snd St., Suite 410
   San Francisco, CA  94107


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

   Phone: +1 650 725 6086

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

   Phone: +1 410 516 4312

Levis, et al.             Expires July 14, 2011                [Page 13]