draft-ietf-roll-trickle-08.txt   rfc6206.txt 
Networking Working Group P. Levis Internet Engineering Task Force (IETF) P. Levis
Internet-Draft Stanford University Request for Comments: 6206 Stanford University
Intended status: Standards Track T. Clausen Category: Standards Track T. Clausen
Expires: July 14, 2011 LIX, Ecole Polytechnique ISSN: 2070-1721 LIX, Ecole Polytechnique
J. Hui J. Hui
Arch Rock Corporation Arch Rock Corporation
O. Gnawali O. Gnawali
Stanford University Stanford University
J. Ko J. Ko
Johns Hopkins University Johns Hopkins University
January 10, 2011 March 2011
The Trickle Algorithm The Trickle Algorithm
draft-ietf-roll-trickle-08
Abstract Abstract
The Trickle algorithm allows nodes in a lossy shared medium (e.g., The Trickle algorithm allows nodes in a lossy shared medium (e.g.,
low power and lossy networks) to exchange information in a highly low-power and lossy networks) to exchange information in a highly
robust, energy efficient, simple, and scalable manner. Dynamically robust, energy efficient, simple, and scalable manner. Dynamically
adjusting transmission windows allows Trickle to spread new adjusting transmission windows allows Trickle to spread new
information on the scale of link-layer transmission times while information on the scale of link-layer transmission times while
sending only a few messages per hour when information does not sending only a few messages per hour when information does not
change. A simple suppression mechanism and transmission point change. A simple suppression mechanism and transmission point
selection allows Trickle's communication rate to scale selection allow Trickle's communication rate to scale logarithmically
logarithmically with density. This document describes the Trickle with density. This document describes the Trickle algorithm and
algorithm and considerations in its use. considerations in its use.
Status of this Memo
This Internet-Draft is submitted in full conformance with the Status of This Memo
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering This is an Internet Standards Track document.
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months This document is a product of the Internet Engineering Task Force
and may be updated, replaced, or obsoleted by other documents at any (IETF). It represents the consensus of the IETF community. It has
time. It is inappropriate to use Internet-Drafts as reference received public review and has been approved for publication by the
material or to cite them other than as "work in progress." Internet Engineering Steering Group (IESG). Further information on
Internet Standards is available in Section 2 of RFC 5741.
This Internet-Draft will expire on July 14, 2011. Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
http://www.rfc-editor.org/info/rfc6206.
Copyright Notice Copyright Notice
Copyright (c) 2011 IETF Trust and the persons identified as the Copyright (c) 2011 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
skipping to change at page 2, line 19 skipping to change at page 2, line 22
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction ....................................................2
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology .....................................................3
3. Trickle Algorithm Overview . . . . . . . . . . . . . . . . . . 4 3. Trickle Algorithm Overview ......................................3
4. Trickle Algorithm . . . . . . . . . . . . . . . . . . . . . . 5 4. Trickle Algorithm ...............................................5
4.1. Parameters and Variables . . . . . . . . . . . . . . . . . 5 4.1. Parameters and Variables ...................................5
4.2. Algorithm Description . . . . . . . . . . . . . . . . . . 5 4.2. Algorithm Description ......................................5
5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . 6 5. Using Trickle ...................................................6
6. Operational Considerations . . . . . . . . . . . . . . . . . . 7 6. Operational Considerations ......................................7
6.1. Mismatched Redundancy Constants . . . . . . . . . . . . . 7 6.1. Mismatched Redundancy Constants ............................7
6.2. Mismatched Imin . . . . . . . . . . . . . . . . . . . . . 7 6.2. Mismatched Imin ............................................7
6.3. Mismatched Imax . . . . . . . . . . . . . . . . . . . . . 8 6.3. Mismatched Imax ............................................8
6.4. Mismatched Definitions . . . . . . . . . . . . . . . . . . 8 6.4. Mismatched Definitions .....................................8
6.5. Specifying the Constant k . . . . . . . . . . . . . . . . 8 6.5. Specifying the Constant k ..................................8
6.6. Relationship Between k and Imin . . . . . . . . . . . . . 9 6.6. Relationship between k and Imin ............................8
6.7. Tweaks and Improvements to Trickle . . . . . . . . . . . . 9 6.7. Tweaks and Improvements to Trickle .........................9
6.8. Uses of Trickle . . . . . . . . . . . . . . . . . . . . . 9 6.8. Uses of Trickle ............................................9
7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10 7. Acknowledgements ...............................................10
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 8. Security Considerations ........................................10
9. Security Considerations . . . . . . . . . . . . . . . . . . . 10 9. References .....................................................11
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 9.1. Normative References ......................................11
10.1. Normative References . . . . . . . . . . . . . . . . . . . 11 9.2. Informative References ....................................11
10.2. Informative References . . . . . . . . . . . . . . . . . . 11
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12
1. Introduction 1. Introduction
The Trickle algorithm establishes a density-aware local communication The Trickle algorithm establishes a density-aware local communication
primitive with an underlying consistency model that guides when a primitive with an underlying consistency model that guides when a
node transmits. When a node's data does not agree with its node transmits. When a node's data does not agree with its
neighbors, that node communicates quickly to resolve the neighbors, that node communicates quickly to resolve the
inconsistency (e.g., in milliseconds). When nodes agree, they slow inconsistency (e.g., in milliseconds). When nodes agree, they slow
their communication rate exponentially, such that nodes send packets their communication rate exponentially, such that nodes send packets
very infrequently (e.g., a few packets per hour). Instead of very infrequently (e.g., a few packets per hour). Instead of
flooding a network with packets, the algorithm controls the send rate flooding a network with packets, the algorithm controls the send rate
so each node hears a small trickle of packets, just enough to stay so each node hears a small trickle of packets, just enough to stay
consistent. Furthermore, by relying only on local communication consistent. Furthermore, by relying only on local communication
(e.g., broadcast or local multicast), Trickle handles network re- (e.g., broadcast or local multicast), Trickle handles network
population, is robust to network transience, loss, and disconnection, re-population; is robust to network transience, loss, and
is simple to implement, and requires very little state. Current disconnection; is simple to implement; and requires very little
implementations use 4-11 bytes of RAM and are 50-200 lines of C state. Current implementations use 4-11 bytes of RAM and are
code[Levis08]. 50-200 lines of C code [Levis08].
While Trickle was originally designed for reprogramming protocols While Trickle was originally designed for reprogramming protocols
(where the data is the code of the program being updated), experience (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 has shown it to be a powerful mechanism that can be applied to a wide
range of protocol design problems, including control traffic timing, range of protocol design problems, including control traffic timing,
multicast propagation, and route discovery. This flexibility stems multicast propagation, and route discovery. This flexibility stems
from being able to define, on a case-by-case basis, what constitutes from being able to define, on a case-by-case basis, what constitutes
"agreement" or an "inconsistency;" Section 6.8 presents a few "agreement" or an "inconsistency"; Section 6.8 presents a few
examples of how the algorithm can be used. examples of how the algorithm can be used.
This document describes the Trickle algorithm and provides guidelines This document describes the Trickle algorithm and provides guidelines
for its use. It also states requirements for protocol specifications for its use. It also states requirements for protocol specifications
that use Trickle. This document does not provide results on that use Trickle. This document does not provide results regarding
Trickle's performance or behavior, nor does it explain the Trickle's performance or behavior, nor does it explain the
algorithm's design in detail: interested readers should refer to algorithm's design in detail: interested readers should refer to
[Levis04] and [Levis08]. [Levis04] and [Levis08].
2. Terminology 2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in RFC "OPTIONAL" in this document are to be interpreted as described in
2119 [RFC2119]. RFC 2119 [RFC2119].
Additionally, this document introduces the following terminology: Additionally, this document introduces the following terminology:
Trickle communication rate: the sum of the number of messages sent Trickle communication rate: the sum of the number of messages sent
or received by the Trickle algorithm in an interval. or received by the Trickle algorithm in an interval.
Trickle transmission rate: the sum of the number of messages sent by Trickle transmission rate: the sum of the number of messages sent by
the Trickle algorithm in an interval. the Trickle algorithm in an interval.
3. Trickle Algorithm Overview 3. Trickle Algorithm Overview
Trickle's basic primitive is simple: every so often, a node transmits Trickle's basic primitive is simple: every so often, a node transmits
data unless it hears a few other transmissions whose data suggest its data unless it hears a few other transmissions whose data suggest its
own transmission is redundant. Examples of such data include routing own transmission is redundant. Examples of such data include routing
state, software update versions, and the last heard multicast packet. state, software update versions, and the last heard multicast packet.
This primitive allows Trickle to scale to thousand-fold variations in This primitive allows Trickle to scale to thousand-fold variations in
network density, quickly propagate updates, distribute transmission network density, quickly propagate updates, distribute transmission
load evenly, be robust to transient disconnections, handle network load evenly, be robust to transient disconnections, handle network
repopulations, and impose a very low maintenance overhead: one re-populations, and impose a very low maintenance overhead: one
example use, routing beacons in the CTP protocol [Gnawali09], example use, routing beacons in the Collection Tree Protocol (CTP)
requires sending on the order of a few packets per hour yet can [Gnawali09], requires sending on the order of a few packets per hour,
respond in milliseconds. yet CTP can respond to topology changes in milliseconds.
Trickle sends all messages to a local communication address. The Trickle sends all messages to a local communication address. The
exact address used can depend on both the underlying IP protocol as exact address used can depend on the underlying IP protocol as well
well as how the higher layer protocol uses Trickle. In IPv6, for as how the higher-layer protocol uses Trickle. In IPv6, for example,
example, it can be the link-local multicast address or another local it can be the link-local multicast address or another local multicast
multicast address, while in IPv4 it can be the broadcast address address, while in IPv4 it can be the broadcast address
(255.255.255.255). (255.255.255.255).
There are two possible results to a Trickle message: either every There are two possible results to a Trickle message: either every
node that hears the message finds the message data is consistent with node that hears the message finds that the message data is consistent
its own state, or a recipient detects an inconsistency. Detection with its own state, or a recipient detects an inconsistency.
can be the result of either an out-of-date node hearing something Detection can be the result of either an out-of-date node hearing
new, or an updated node hearing something old. As long as every node something new, or an updated node hearing something old. As long as
communicates somehow - either receives or transmits - some node will every node communicates somehow -- either receives or transmits --
detect the need for an update. some node will detect the need for an update.
For example, consider a simple case where "up to date" is defined by For example, consider a simple case where "up to date" is defined by
version numbers (e.g., network configuration). If node A transmits 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 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, 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 A knows that it needs an update. If B broadcasts or multicasts
updates, then all of its neighbors can receive them without having to updates, then all of its neighbors can receive them without having to
advertise their need. Some of these recipients might not have even advertise their need. Some of these recipients might not have even
heard A's transmission. In this example, it does not matter who heard A's transmission. In this example, it does not matter who
first transmits, A or B; either case will detect the inconsistency. first transmits -- A or B; the inconsistency will be detected in
either case.
The fact that Trickle communication can be either transmission or The fact that Trickle communication can be either transmission or
reception enables the Trickle algorithm to operate in sparse as well reception enables the Trickle algorithm to operate in sparse as well
as dense networks. A single, disconnected node must transmit at the as dense networks. A single, disconnected node must transmit at the
Trickle communication rate. In a lossless, single-hop network of Trickle communication rate. In a lossless, single-hop network of
size n, the Trickle communication rate at each node equals the sum of size n, the Trickle communication rate at each node equals the sum of
the Trickle transmission rates across all nodes. The Trickle the Trickle transmission rates across all nodes. The Trickle
algorithm balances the load in such a scenario, as each node's algorithm balances the load in such a scenario, as each node's
Trickle transmission rate is 1/nth of the Trickle communication rate. Trickle transmission rate is 1/nth of the Trickle communication rate.
Sparser networks require more transmissions per node, but the Sparser networks require more transmissions per node, but the
skipping to change at page 5, line 31 skipping to change at page 5, line 22
configuration parameters: the minimum interval size Imin, the maximum configuration parameters: the minimum interval size Imin, the maximum
interval size Imax, and a redundancy constant k: interval size Imax, and a redundancy constant k:
o The minimum interval size, Imin, is defined in units of time o The minimum interval size, Imin, is defined in units of time
(e.g., milliseconds, seconds). For example, a protocol might (e.g., milliseconds, seconds). For example, a protocol might
define the minimum interval as 100 milliseconds. define the minimum interval as 100 milliseconds.
o The maximum interval size, Imax, is described as a number of o The maximum interval size, Imax, is described as a number of
doublings of the minimum interval size (the base-2 log(max/min)). doublings of the minimum interval size (the base-2 log(max/min)).
For example, a protocol might define Imax as 16. If the minimum For example, a protocol might define Imax as 16. If the minimum
interval is 100ms, then the amount of time specified by Imax is interval is 100 ms, then the amount of time specified by Imax is
100ms * 65536, 6,553.6 seconds, or approximately 109 minutes. 100 ms * 65,536, i.e., 6,553.6 seconds or approximately
109 minutes.
o The redundancy constant is a natural number (an integer greater o The redundancy constant, k, is a natural number (an integer
than zero). greater than zero).
In addition to these three parameters, Trickle maintains three In addition to these three parameters, Trickle maintains three
variables: variables:
o I, the current interval size o I, the current interval size,
o t, a time within the current interval, and o t, a time within the current interval, and
o c, a counter. o c, a counter.
4.2. Algorithm Description 4.2. Algorithm Description
The Trickle algorithm has six rules: The Trickle algorithm has six rules:
1. When the algorithm starts execution, it sets I to a value in the 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 range of [Imin, Imax] -- that is, greater than or equal to Imin
less then or equal to Imax. The algorithm then begins the first and less than or equal to Imax. The algorithm then begins the
interval. first interval.
2. When an interval begins, Trickle resets c to 0 and sets t to a 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 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 is, values greater than or equal to I/2 and less than I. The
interval ends at I. interval ends at I.
3. Whenever Trickle hears a transmission that is "consistent," it 3. Whenever Trickle hears a transmission that is "consistent", it
increments the counter c. increments the counter c.
4. At time t, Trickle transmits if and only if the counter c is less 4. At time t, Trickle transmits if and only if the counter c is less
than the redundancy constant k. than the redundancy constant k.
5. When the interval I expires, Trickle doubles the interval length. 5. When the interval I expires, Trickle doubles the interval length.
If this new interval length would be longer than the time If this new interval length would be longer than the time
specified by Imax, Trickle sets the interval length I to be the specified by Imax, Trickle sets the interval length I to be the
time specified by Imax. time specified by Imax.
6. If Trickle hears a transmission that is "inconsistent" and I is 6. If Trickle hears a transmission that is "inconsistent" and I is
greater than Imin, it resets the Trickle timer. To reset the greater than Imin, it resets the Trickle timer. To reset the
timer, Trickle sets I to Imin and starts a new interval as in 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 step 2. If I is equal to Imin when Trickle hears an
"inconsistent" transmission, Trickle does nothing. Trickle can "inconsistent" transmission, Trickle does nothing. Trickle can
also reset its timer in response to external "events." also reset its timer in response to external "events".
The terms consistent, inconsistent and event are in quotes because The terms "consistent", "inconsistent", and "events" are in quotes
their meaning depends on how a protocol uses Trickle. because their meaning depends on how a protocol uses Trickle.
The only time the Trickle algorithm transmits is at step 3 of the The only time the Trickle algorithm transmits is at step 4 of the
above algorithm. This means there is an inherent delay between above algorithm. This means there is an inherent delay between
detecting an inconsistency (shrinking I to Imin) and responding to detecting an inconsistency (shrinking I to Imin) and responding to
that inconsistency (transmitting at time t in the new interval). that inconsistency (transmitting at time t in the new interval).
This is intentional. Immediately responding to detecting an This is intentional. Immediately responding to detecting an
inconsistency can cause a broadcast storm, where many nodes respond inconsistency can cause a broadcast storm, where many nodes respond
at once and in a synchronized fashion. By making responses follow at once and in a synchronized fashion. By making responses follow
the Trickle algorithm (with the minimal interval size), a protocol the Trickle algorithm (with the minimal interval size), a protocol
can benefit from Trickle's suppression mechanism and scale across a can benefit from Trickle's suppression mechanism and scale across a
huge range of node densities. huge range of node densities.
5. Using Trickle 5. Using Trickle
A protocol specification that uses Trickle MUST specify: A protocol specification that uses Trickle MUST specify:
o Default values for Imin, Imax, and k. Because link layers can o Default values for Imin, Imax, and k. Because link layers can
vary widely in their properties, the default value of Imin SHOULD vary widely in their properties, the default value of Imin SHOULD
be specified in terms of the worst-case latency of a link layer be specified in terms of the worst-case latency of a link-layer
transmission. For example, a specification should say "the transmission. For example, a specification should say "the
default value of Imin is 4 times the worst case link layer default value of Imin is 4 times the worst-case link-layer
latency" and should not say "the default value of Imin is 500 latency" and should not say "the default value of Imin is
milliseconds." Worst case latency is approximately time until the 500 milliseconds". Worst-case latency is approximately the time
first link-layer transmission of the frame assuming an idle until the first link-layer transmission of the frame, assuming an
channel (does not include backoff, virtual carrier sense, etc.). idle channel (does not include backoff, virtual carrier sense,
etc.).
o What constitutes a "consistent" transmission. o What constitutes a "consistent" transmission.
o What constitutes an "inconsistent" transmission. o What constitutes an "inconsistent" transmission.
o What "events," if any, besides inconsistent transmissions that o What "events", if any -- besides inconsistent transmissions --
reset the Trickle timer. reset the Trickle timer.
o What information a node transmits in Trickle messages. o What information a node transmits in Trickle messages.
o What actions outside the algorithm the protocol takes, if any, o What actions outside the algorithm the protocol takes, if any,
when it detects an inconsistency. when it detects an inconsistency.
6. Operational Considerations 6. Operational Considerations
It is RECOMMENDED that a protocol which uses Trickle includes It is RECOMMENDED that a protocol that uses Trickle include
mechanisms to inform nodes of configuration parameters at runtime. mechanisms to inform nodes of configuration parameters at runtime.
However, it is not always possible to do so. In the cases where However, it is not always possible to do so. In the cases where
different nodes have different configuration parameters, Trickle may different nodes have different configuration parameters, Trickle may
have unintended behaviors. This section outlines some of those have unintended behaviors. This section outlines some of those
behaviors and operational considerations as educational exercises. behaviors and operational considerations as educational exercises.
6.1. Mismatched Redundancy Constants 6.1. Mismatched Redundancy Constants
If nodes do not agree on the redundancy constant k, then nodes with 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 higher values of k will transmit more often than nodes with lower
values of k. In some cases, this increased load can be independent values of k. In some cases, this increased load can be independent
of the density. For example, consider a network where all nodes but 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 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 up transmitting on every interval: it is maintaining a Trickle
communication rate of 2 with only itself. Hence, the danger of communication rate of 2 with only itself. Hence, the danger of
mismatched k values is uneven transmission load that can deplete the mismatched k values is uneven transmission load that can deplete the
energy of some nodes in a low power network. energy of some nodes in a low-power network.
6.2. Mismatched Imin 6.2. Mismatched Imin
If nodes do not agree on Imin, then some nodes, on hearing If nodes do not agree on Imin, then some nodes, on hearing
inconsistent messages, will transmit sooner than others. These inconsistent messages, will transmit sooner than others. These
faster nodes will have their intervals grow to similar size as the faster nodes will have their intervals grow to a size similar to that
slower nodes within a single slow interval time, but in that period of the slower nodes within a single slow interval time, but in that
may suppress the slower nodes. However, such suppression will end period may suppress the slower nodes. However, such suppression will
after the first slow interval, when the nodes generally agree on the end after the first slow interval, when the nodes generally agree on
interval size. Hence, mismatched Imin values are usually not a the interval size. Hence, mismatched Imin values are usually not a
significant concern. Note that mismatched Imin values and matching significant concern. Note that mismatched Imin values and matching
Imax doubling constants will lead to mismatched maximum interval Imax doubling constants will lead to mismatched maximum interval
lengths. lengths.
6.3. Mismatched Imax 6.3. Mismatched Imax
If nodes do not agree on Imax, then this can cause long-term problems If nodes do not agree on Imax, then this can cause long-term problems
with transmission load. Nodes with small Imax values will transmit with transmission load. Nodes with small Imax values will transmit
faster, suppressing those with larger Imax values. The nodes with faster, suppressing those with larger Imax values. The nodes with
larger Imax values, always suppressed, will never transmit. In the larger Imax values, always suppressed, will never transmit. In the
base case, when the network is consistent, this can cause long-term base case, when the network is consistent, this can cause long-term
inequities in energy cost. inequities in energy cost.
6.4. Mismatched Definitions 6.4. Mismatched Definitions
If nodes do not agree on what constitutes a consistent or If nodes do not agree on what constitutes a consistent or
inconsistent transmission, then Trickle may fail to operate properly. inconsistent transmission, then Trickle may fail to operate properly.
For example, if a receiver thinks a transmission is consistent, but For example, if a receiver thinks a transmission is consistent, but
the transmitter (if in the receivers situation) would have thought it the transmitter (if in the receiver's situation) would have thought
inconsistent, then the receiver will not respond properly and inform it inconsistent, then the receiver will not respond properly and
the transmitter. This can lead the network to not reach a consistent inform the transmitter. This can lead the network to not reach a
state. For this reason, unlike the configuration constants k, Imin, consistent state. For this reason, unlike the configuration
and Imax, consistency definitions MUST be clearly stated in the constants k, Imin, and Imax, consistency definitions MUST be clearly
protocol and SHOULD NOT be configured at runtime. stated in the protocol and SHOULD NOT be configured at runtime.
6.5. Specifying the Constant k 6.5. Specifying the Constant k
There are some edge cases where a protocol may wish to use Trickle There are some edge cases where a protocol may wish to use Trickle
with its suppression disabled (k is set to infinity). In general, with its suppression disabled (k is set to infinity). In general,
this approach is highly dangerous and it is NOT RECOMMENDED. this approach is highly dangerous and it is NOT RECOMMENDED.
Disabling suppression means that every node will always send on every Disabling suppression means that every node will always send on every
interval, and can lead to congestion in dense networks. This interval; this can lead to congestion in dense networks. This
approach is especially dangerous if many nodes reset their intervals 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 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 a high value (e.g., 5 or 10) than infinity. Typical values for k
1-5: these achieve a good balance between redundancy and low are 1-5: these achieve a good balance between redundancy and low cost
cost[Levis08]. [Levis08].
Nevertheless, there are situations where a protocol may wish to turn Nevertheless, there are situations where a protocol may wish to turn
off Trickle suppression. Because k is a natural number off Trickle suppression. Because k is a natural number
(Section 4.1), k=0 has no useful meaning. If a protocol allows k to (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 be dynamically configured, a value of 0 remains unused. For ease of
debugging and packet inspection, having the parameter describe k-1 debugging and packet inspection, having the parameter describe k-1
rather than k can be confusing. Instead, it is RECOMMENDED that rather than k can be confusing. Instead, it is RECOMMENDED that
protocols which require turning off suppression reserve k=0 to mean protocols that require turning off suppression reserve k=0 to mean
k=infinity. k=infinity.
6.6. Relationship Between k and Imin 6.6. Relationship between k and Imin
Finally, a protocol SHOULD set k and Imin such that Imin is at least 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. 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 Otherwise, if more than k nodes reset their intervals to Imin, the
resulting communication will lead to congestion and significant resulting communication will lead to congestion and significant
packet loss. Experimental results have shown that packet losses from packet loss. Experimental results have shown that packet losses from
congestion reduce Trickle's efficiency [Levis04]. congestion reduce Trickle's efficiency [Levis04].
6.7. Tweaks and Improvements to Trickle 6.7. Tweaks and Improvements to Trickle
skipping to change at page 9, line 30 skipping to change at page 9, line 21
mechanisms that are highly robust to challenging network mechanisms that are highly robust to challenging network
environments. In our experiences using Trickle, attempts to tweak environments. In our experiences using Trickle, attempts to tweak
its behavior are typically not worth the cost. As written, the its behavior are typically not worth the cost. As written, the
algorithm is already highly efficient: further reductions in algorithm is already highly efficient: further reductions in
transmissions or response time come at the cost of failures in edge transmissions or response time come at the cost of failures in edge
cases. Based on our experiences, we urge protocol designers to cases. Based on our experiences, we urge protocol designers to
suppress the instinct to tweak or improve Trickle without a great suppress the instinct to tweak or improve Trickle without a great
deal of experimental evidence that the change does not violate its deal of experimental evidence that the change does not violate its
assumptions and break the algorithm in edge cases. assumptions and break the algorithm in edge cases.
This warning in mind, Trickle is far from perfect. For example, With this warning in mind, Trickle is far from perfect. For example,
Trickle suppression typically leads sparser nodes to transmit more Trickle suppression typically leads sparser nodes to transmit more
than denser ones; it is far from the optimal computation of a minimum than denser ones; it is far from the optimal computation of a minimum
cover. However, in dynamic network environments such as wireless and cover. However, in dynamic network environments such as wireless and
low-power, lossy networks, the coordination needed to compute the low-power, lossy networks, the coordination needed to compute the
optimal set of transmissions is typically much greater than the optimal set of transmissions is typically much greater than the
benefits it provides. One of the benefits of Trickle is that it is 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 so simple to implement and requires so little state yet operates so
efficiently. Efforts to improve it should be weighed against the efficiently. Efforts to improve it should be weighed against the
cost of increased complexity. cost of increased complexity.
6.8. Uses of Trickle 6.8. Uses of Trickle
The Trickle algorithm has been used in a variety of protocols, both The Trickle algorithm has been used in a variety of protocols, in
in operational as well as academic settings. Giving a brief overview operational as well as academic settings. Giving a brief overview of
of some of these uses provides useful examples of how and when it can some of these uses provides useful examples of how and when it can be
be used. These examples should not be considered exhaustive. used. These examples should not be considered exhaustive.
Reliable flooding/dissemination: A protocol uses Trickle to Reliable flooding/dissemination: A protocol uses Trickle to
periodically advertise the most recent data it has received, periodically advertise the most recent data it has received,
typically through a version number. An inconsistency is when a node typically through a version number. An inconsistency occurs when a
hears a newer version number or receives new data. A consistency is node hears a newer version number or receives new data. A
when a node hears an older or equal version number. When hearing an consistency occurs when a node hears an older or equal version
older version number, rather than reset its own Trickle timer, it number. When hearing an older version number, rather than reset its
sends an update. Nodes with old version numbers that receive the own Trickle timer, the node sends an update. Nodes with old version
update will then reset their own timers, leading to fast propagation numbers that receive the update will then reset their own timers,
of the new data. Examples of this use include multicast[Hui08a], leading to fast propagation of the new data. Examples of this use
network configuration[Lin08][Dang09], and installing new application include multicast [Hui08a], network configuration [Lin08] [Dang09],
programs[Hui04][Levis04]. and installing new application programs [Hui04] [Levis04].
Routing control traffic: A protocol uses Trickle to control when it Routing control traffic: A protocol uses Trickle to control when it
sends beacons which contain routing state. An inconsistency is when sends beacons that contain routing state. An inconsistency occurs
the routing topology changes in a way that could lead to loops or when the routing topology changes in a way that could lead to loops
significant stretch: examples include when the routing layer detects or significant stretch: examples include when the routing layer
a routing loop or when a node's routing cost changes significantly. detects a routing loop or when a node's routing cost changes
Consistency is when the routing topology is operating well and is significantly. Consistency occurs when the routing topology is
delivering packets successfully. Using the Trickle algorithm in this operating well and is delivering packets successfully. Using the
way allows a routing protocol to react very quickly to problems (Imin Trickle algorithm in this way allows a routing protocol to react very
is small) but send very few beacons when the topology is stable. quickly to problems (Imin is small) but send very few beacons when
Examples of this use include RPL[I-D.ietf-roll-rpl], CTP[Gnawali09], the topology is stable. Examples of this use include the IPv6
and some current commericial IPv6 routing layers[Hui08b]. routing protocol for low-power and lossy networks (RPL) [RPL], CTP
[Gnawali09], and some current commercial IPv6 routing layers
[Hui08b].
7. Acknowledgements 7. Acknowledgements
The authors would like to acknowledge the guidance and input provided The authors would like to acknowledge the guidance and input provided
by the ROLL chairs, David Culler and JP Vasseur. by the ROLL chairs, David Culler and JP Vasseur.
The authors would also like to acknowledge the helpful comments of The authors would also like to acknowledge the helpful comments of
Yoav Ben-Yehezkel, Alexandru Petrescu, and Ulrich Herberg, which Yoav Ben-Yehezkel, Alexandru Petrescu, and Ulrich Herberg, which
greatly improved the document. greatly improved the document.
8. IANA Considerations 8. Security Considerations
This document has no IANA considerations.
9. Security Considerations
As it is an algorithm, Trickle itself does not have any specific As it is an algorithm, Trickle itself does not have any specific
security considerations. However, two security concerns can arise security considerations. However, two security concerns can arise
when Trickle is used in a protocol. The first is that an adversary 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 can force nodes to send many more packets than needed by forcing
Trickle timer resets. In low power networks this increase in traffic Trickle timer resets. In low-power networks, this increase in
can harm system lifetime. The second concern is that an adversary traffic can harm system lifetime. The second concern is that an
can prevent nodes from reaching consistency. adversary can prevent nodes from reaching consistency.
Protocols can prevent adversarial Trickle resets by carefully Protocols can prevent adversarial Trickle resets by carefully
selecting what can cause a reset and protecting these events and selecting what can cause a reset and protecting these events and
messages with proper security mechanisms. For example, if a node can messages with proper security mechanisms. For example, if a node can
reset nearby Trickle timers by sending a certain packet, this packet reset nearby Trickle timers by sending a certain packet, this packet
should be authenticated such that an adversary cannot forge one. should be authenticated such that an adversary cannot forge one.
An adversary can possibly prevent nodes from reaching consistency by An adversary can possibly prevent nodes from reaching consistency by
suppressing transmissions with "consistent" messages. For example, suppressing transmissions with "consistent" messages. For example,
imagine node A detects an inconsistency and resets its Trickle timer. imagine node A detects an inconsistency and resets its Trickle timer.
If an adversary can prevent A from sending messages that inform If an adversary can prevent A from sending messages that inform
nearby nodes of the inconsistency in order to repair it, then A may nearby nodes of the inconsistency in order to repair it, then A may
remain inconsistent indefinitely. Depending on the security model of remain inconsistent indefinitely. Depending on the security model of
the network, authenticated messages, or a transitive notion of the network, authenticated messages or a transitive notion of
consistency can prevent this problem. E.g., if messages that are consistency can prevent this problem. For example, let us suppose an
consistent with A and so suppress its transmissions are by definition adversary wishes to suppress A from notifying neighbors of an
inconsistent with what A heard, then an adversary cannot inconsistency. To do so, it must send messages that are consistent
simultaneously prevent A from notifying neighbors and not notify the with A. These messages are by definition inconsistent with those of
neighbors itself (recall Trickle operates on shared, broadcast A's neighbors. Correspondingly, an adversary cannot simultaneously
media). Note that this means Trickle should filter unicast messages. prevent A from notifying neighbors and not notify the neighbors
itself (recall that Trickle operates on shared, broadcast media).
Note that this means Trickle should filter unicast messages.
10. References 9. References
10.1. Normative References 9.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
10.2. Informative References 9.2. Informative References
[Dang09] Dang, T., Bulusu, N., Feng, W., and S. Park, "DHV: A Code [Dang09] Dang, T., Bulusu, N., Feng, W., and S. Park, "DHV: A Code
Consistency Maintenance Protocol for Multi-hop Wireless Consistency Maintenance Protocol for Multi-hop Wireless
Networks", Wireless Sensor Networks: 6th European Networks", Wireless Sensor Networks: 6th European
Conference Proceedings EWSN 2009 Cork, February 2009, Conference Proceedings EWSN 2009 Cork, February 2009,
<http://books.google.com/books?id=3fb5eePdkBg>. <http://portal.acm.org/citation.cfm?id=1506781>.
[Gnawali09] [Gnawali09]
Gnawali, O., Fonseca, R., Jamieson, K., Moss, D., and P. Gnawali, O., Fonseca, R., Jamieson, K., Moss, D., and P.
Levis, "Collection Tree Protocol", Proceedings of the 7th Levis, "Collection Tree Protocol", Proceedings of the 7th
ACM Conference on Embedded Networked Systems SenSys 2009, ACM Conference on Embedded Networked Sensor
November 2009, Systems, SenSys 2009, November 2009,
<http://portal.acm.org/citation.cfm?id=1644038.1644040>. <http://portal.acm.org/citation.cfm?id=1644038.1644040>.
[Hui04] Hui, J. and D. Culler, "The dynamic behavior of a data [Hui04] Hui, J. and D. Culler, "The dynamic behavior of a data
dissemination protocol for network programming at scale", dissemination protocol for network programming at scale",
Proceedings of the 2nd ACM Conference on Embedded Proceedings of the 2nd ACM Conference on Embedded
Networked Systems SenSys 2004, November 2004, Networked Sensor Systems, SenSys 2004, November 2004,
<http://portal.acm.org/citation.cfm?id=1031506>. <http://portal.acm.org/citation.cfm?id=1031506>.
[Hui08a] Hui, J., "An Extended Internet Architecture for Low-Power [Hui08a] Hui, J., "An Extended Internet Architecture for Low-Power
Wireless Networks - Design and Implementation", UC Wireless Networks - Design and Implementation", UC
Berkeley Technical Report EECS-2008-116, September 2008, Berkeley Technical Report EECS-2008-116, September 2008,
<http://portal.acm.org/citation.cfm?id=1460412.1460415>. <http://www.eecs.berkeley.edu/Pubs/>.
[Hui08b] Hui, J. and D. Culler, "IP is dead, long live IP for [Hui08b] Hui, J. and D. Culler, "IP is dead, long live IP for
wireless sensor networks", Proceedings of the 6th ACM wireless sensor networks", Proceedings of the 6th ACM
Conference on Embedded Networked Systems SenSys 2008, Conference on Embedded Networked Sensor Systems, SenSys
November 2008, 2008, November 2008,
<http://portal.acm.org/citation.cfm?id=1460412.1460415>. <http://portal.acm.org/citation.cfm?id=1460412.1460415>.
[I-D.ietf-roll-rpl]
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, [Levis04] Levis, P., Patel, N., Culler, D., and S. Shenker,
"Trickle: A Self-Regulating Algorithm for Code Propagation "Trickle: A Self-Regulating Algorithm for Code Propagation
and Maintenance in Wireless Sensor Networks"", Proceedings and Maintenance in Wireless Sensor Networks", Proceedings
of the First USENIX/ACM Symposium on Networked Systems of the First USENIX/ACM Symposium on Networked Systems
Design and Implementation NSDI 2004, March 2004, Design and Implementation, NSDI 2004, March 2004,
<http://portal.acm.org/citation.cfm?id=1251177>. <http://portal.acm.org/citation.cfm?id=1251177>.
[Levis08] Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S., [Levis08] Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S.,
Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and A. Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and A.
Woo, "The Emergence of a Networking Primitive in Wireless Woo, "The Emergence of a Networking Primitive in Wireless
Sensor Networks", Communications of the ACM, v.51 n.7, Sensor Networks", Communications of the ACM, Vol. 51 No.
July 2008, 7, July 2008,
<http://portal.acm.org/citation.cfm?id=1364804>. <http://portal.acm.org/citation.cfm?id=1364804>.
[Lin08] Lin, K. and P. Levis, "Data Discovery and Dissemination [Lin08] Lin, K. and P. Levis, "Data Discovery and Dissemination
with DIP", Proceedings of the 7th international conference with DIP", Proceedings of the 7th international conference
on Information processing in sensor networks IPSN 2008, on Information processing in sensor networks, IPSN 2008,
April 2008, April 2008,
<http://portal.acm.org/citation.cfm?id=1371607.1372753>. <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 Authors' Addresses
Philip Levis Philip Levis
Stanford University Stanford University
358 Gates Hall, Stanford University 358 Gates Hall
Stanford, CA 94305 Stanford, CA 94305
USA USA
Phone: +1 650 725 9064 Phone: +1 650 725 9064
Email: pal@cs.stanford.edu EMail: pal@cs.stanford.edu
Thomas Heide Clausen Thomas Heide Clausen
LIX, Ecole Polytechnique LIX, Ecole Polytechnique
Phone: +33 6 6058 9349 Phone: +33 6 6058 9349
Email: T.Clausen@computer.org EMail: T.Clausen@computer.org
Jonathan Hui Jonathan Hui
Arch Rock Corporation Arch Rock Corporation
501 Snd St., Suite 410 501 2nd St., Suite 410
San Francisco, CA 94107 San Francisco, CA 94107
USA USA
Email: jhui@archrock.com EMail: jhui@archrock.com
Omprakash Gnawali Omprakash Gnawali
Stanford University Stanford University
S255 Clark Center, 318 Campus Drive S255 Clark Center, 318 Campus Drive
Stanford, CA 94305 Stanford, CA 94305
USA USA
Phone: +1 650 725 6086 Phone: +1 650 725 6086
Email: gnawali@cs.stanford.edu EMail: gnawali@cs.stanford.edu
JeongGil Ko JeongGil Ko
Johns Hopkins University Johns Hopkins University
3400 N. Charles St., 224 New Engineering Building 3400 N. Charles St., 224 New Engineering Building
Baltimore, MD 21218 Baltimore, MD 21218
USA USA
Phone: +1 410 516 4312 Phone: +1 410 516 4312
Email: jgko@cs.jhu.edu EMail: jgko@cs.jhu.edu
 End of changes. 70 change blocks. 
180 lines changed or deleted 176 lines changed or added

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/