draft-ietf-roll-trickle-02.txt   draft-ietf-roll-trickle-03.txt 
Networking Working Group P. Levis Networking Working Group P. Levis
Internet-Draft Stanford University Internet-Draft Stanford University
Intended status: Informational T. Clausen Intended status: Standards Track T. Clausen
Expires: January 7, 2011 LIX, Ecole Polytechnique Expires: February 19, 2011 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
July 6, 2010 August 18, 2010
The Trickle Algorithm The Trickle Algorithm
draft-ietf-roll-trickle-02 draft-ietf-roll-trickle-03
Abstract Abstract
The Trickle algorithm allows wireless nodes to exchange information The Trickle algorithm allows nodes in a lossy shared medium (e.g.,
in a highly robust, energy efficient, simple, and scalable manner. low power and lossy networks) to exchange information in a highly
Dynamically adjusting transmission windows allows Trickle to spread robust, energy efficient, simple, and scalable manner. Dynamically
new information on the scale of link-layer transmission times while 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 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 allows Trickle's communication rate to scale
logarithmically with density. This document describes Trickle and logarithmically with density. This document describes Trickle and
considerations in its use. considerations in its use.
Status of this Memo Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
skipping to change at page 2, line 5 skipping to change at page 2, line 6
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on January 7, 2011. This Internet-Draft will expire on February 19, 2011.
Copyright Notice Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the Copyright (c) 2010 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
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the BSD License. described in the BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Trickle Algorithm Overview . . . . . . . . . . . . . . . . . . 3 3. Trickle Algorithm Overview . . . . . . . . . . . . . . . . . . 3
4. Trickle Algorithm . . . . . . . . . . . . . . . . . . . . . . . 4 4. Trickle Algorithm . . . . . . . . . . . . . . . . . . . . . . 5
4.1. Parameters and Variables . . . . . . . . . . . . . . . . . 4 4.1. Parameters and Variables . . . . . . . . . . . . . . . . . 5
4.2. Algorithm Description . . . . . . . . . . . . . . . . . . . 5 4.2. Algorithm Description . . . . . . . . . . . . . . . . . . 5
5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . . 5 5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . 6
6. Operational Considerations . . . . . . . . . . . . . . . . . . 6 6. Operational Considerations . . . . . . . . . . . . . . . . . . 6
6.1. Mismatched redundancy constants . . . . . . . . . . . . . . 6 6.1. Mismatched redundancy constants . . . . . . . . . . . . . 7
6.2. Mismatched Imin . . . . . . . . . . . . . . . . . . . . . . 6 6.2. Mismatched Imin . . . . . . . . . . . . . . . . . . . . . 7
6.3. Mismatched Imax . . . . . . . . . . . . . . . . . . . . . . 7 6.3. Mismatched Imax . . . . . . . . . . . . . . . . . . . . . 7
6.4. Mismatched definitions . . . . . . . . . . . . . . . . . . 7 6.4. Mismatched definitions . . . . . . . . . . . . . . . . . . 7
6.5. Specifying the constant k . . . . . . . . . . . . . . . . . 7 6.5. Specifying the constant k . . . . . . . . . . . . . . . . 8
6.6. Relationship between k and Imin . . . . . . . . . . . . . . 7 6.6. Relationship between k and Imin . . . . . . . . . . . . . 8
6.7. Tweaks and improvements to Trickle . . . . . . . . . . . . 8 6.7. Tweaks and improvements to Trickle . . . . . . . . . . . . 8
7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 8 6.8. Uses of Trickle . . . . . . . . . . . . . . . . . . . . . 9
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 8 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 9
9. Security Considerations . . . . . . . . . . . . . . . . . . . . 8 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8 9. Security Considerations . . . . . . . . . . . . . . . . . . . 10
10.1. Normative References . . . . . . . . . . . . . . . . . . . 8 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10
10.2. Informative References . . . . . . . . . . . . . . . . . . 9 10.1. Normative References . . . . . . . . . . . . . . . . . . . 10
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 9 10.2. Informative References . . . . . . . . . . . . . . . . . . 10
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11
1. Introduction 1. Introduction
The Trickle algorithm is designed for wireless networks. It The Trickle algorithm establishes a density-aware local communication
establishes a density-aware local broadcast with an underlying primitive with an underlying consistency model that guides when a
consistency model that guides when a node communicates. When a node transmits. When a node's data does not agree with its
node's data does not agree with its neighbors, it communicates neighbors, that node communicates quickly to resolve the
quickly to resolve the inconsistency. When nodes agree, they slow inconsistency (e.g., in milliseconds). When nodes agree, they slow
their communication rate exponentially, such that nodes send at most their communication rate exponentially, such that nodes send packets
a few packets per hour. Instead of flooding a network with packets, very infrequently (e.g., a few packets per hour). Instead of
the algorithm controls the send rate so each node hears a small flooding a network with packets, the algorithm controls the send rate
trickle of packets, just enough to stay consistent. Furthermore, by so each node hears a small trickle of packets, just enough to stay
relying only on local broadcasts, Trickle handles network re- 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, population, is robust to network transience, loss, and disconnection,
and requires very little state (implementations use 4-11 bytes). is simple to implement, and requires very little state. Current
implementations use 4-11 bytes of RAM and are 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 wide
range of protocol design problems, including control traffic timing, range of protocol design problems, including control traffic timing,
multicast propagation, and route discovery. 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."
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 on
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 RFC
2119 [RFC2119]. 2119 [RFC2119].
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
code metadata if it has not heard a few other nodes transmit the same data unless it hears a few other transmissions whose data suggest its
thing. This allows Trickle to scale to thousand-fold variations in 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 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 maintenance overhead on the order of a repopulations, and impose a very low maintenance overhead: common
few packets per hour. uses require on the order of a few packets per hour yet can respond
in milliseconds.
Trickle sends all messages to the local broadcast address. There are Trickle sends all messages to a local communication address. The
two possible results to a Trickle broadcast: either every node that exact address used can depend on both the underlying IP protocol as
hears the message is up to date, or a recipient detects the need for well as how the higher layer protocol uses Trickle. In IPv6, for
an update. Detection can be the result of either an out-of-date node example, it can be the link-local multicast address or another local
hearing someone has new code, or an updated node hearing someone has multicast address, while in IPv4 it can be the broadcast address
old code. As long as every node communicates somehow - either (255.255.255.255).
receives or transmits - the need for an update will be detected.
There are two possible results to a Trickle broadcast: either every
node that hears the message finds its data is consistent with their
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 For example, consider a simple case where "up to date" is defined by
version numbers (e.g., network configuration). If node A broadcasts 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 broadcasts that it has V+1, A knows needs an update. Similarly, if B transmits that it has version V+1,
that it needs an update. If B broadcasts updates, then all of its A knows that it needs an update. If B broadcasts or multicasts
neighbors can receive them without having to advertise their need. updates, then all of its neighbors can receive them without having to
Some of these recipients might not even have heard A's transmission. advertise their need. Some of these recipients might not even have
heard A's transmission.
In this example, it does not matter who first transmits, A or B; In this example, it does not matter who first transmits, A or B;
either case will detect the inconsistency. All that matters is that either case will detect the inconsistency. All that matters is that
some nodes communicate with one another at some nonzero rate. As some nodes communicate with one another at some nonzero rate. As
long as the network is connected and there is some minimum long as the network is connected and there is some minimum
communication rate for each node, the network will reach eventual communication rate for each node, the network will reach eventual
consistency. consistency.
The fact that communication can be either transmission or reception The fact that communication can be either transmission or reception
enables Trickle to operate in sparse as well as dense networks. A enables the Trickle algorithm to operate in sparse as well as dense
single, disconnected node must transmit at the communication rate. networks. A single, disconnected node must transmit at the Trickle
In a lossless, single-hop network of size n, the sum of transmissions communication rate. In a lossless, single-hop network of size n, the
over the network is the communication rate, so for each node it is Trickle communication rate at each node equals the sum of the Trickle
1/n. Sparser networks require more transmissions per node, but transmission rates across all nodes. The Trickle algorithm blaances
utilization of the radio channel over space will not increase. This the load in such a scenario, as each node's Trickle transmission rate
is an important property in wireless networks, where the channel is a is 1/nth of the Trickle communication rate. Sparser networks require
more transmissions per node, but utilization of the radio channel
over space 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 valuable shared resource. Additionally, reducing transmissions in
dense networks conserves system energy. dense networks conserves system energy.
4. Trickle Algorithm 4. Trickle Algorithm
This section describes the Trickle algorithm. This section describes the Trickle algorithm.
4.1. Parameters and Variables 4.1. Parameters and Variables
A Trickle timer has three configuration parameters: the minimum A Trickle timer has three configuration parameters: the minimum
skipping to change at page 6, line 28 skipping to change at page 6, line 45
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 five rules: The Trickle algorithm has five rules:
1. When an interval begins, Trickle resets c to 0 and sets t to a 1. 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). 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.
2. Whenever Trickle hears a transmission that is "consistent," it 2. Whenever Trickle hears a transmission that is "consistent," it
increments counter c. increments the counter c.
3. At time t, Trickle transmits if and only if counter c is less 3. At time t, Trickle transmits if and only if the counter c is less
than the redundancy constant k. than the redundancy constant k.
4. When an interval expires, Trickle doubles the interval length. 4. When the interval I expires, Trickle doubles the interval length.
If this new interval length would be longer than Imax, Trickle If this new interval length would be longer than Imax, Trickle
sets the interval length I to be Imax. sets the interval length I to be Imax.
5. If Trickle hears a transmission that is "inconsistent," the 5. If Trickle hears a transmission that is "inconsistent," the
Trickle timer resets. If I is greater than Imin, resetting a Trickle timer resets. If I is greater than Imin, resetting a
Trickle timer sets I to Imin and begins a new interval. If I is Trickle timer sets I to Imin and begins a new interval. If I is
equal to Imin, resetting a Trickle timer does nothing. Trickle equal to Imin, resetting a Trickle timer does nothing. Trickle
may also reset the timer in response to external "events." can also reset the timer in response to external "events."
The terms consistent, inconsistent and event are in quotes because The terms consistent, inconsistent and event are in quotes because
their meaning depends on the use of Trickle. their meaning depends on how a protocol uses Trickle.
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 500
milliseconds." Worst case latency is the time until the first milliseconds." Worst case latency is approximately time until the
link-layer transmission of the frame assuming an idle channel first link-layer transmission of the frame assuming an idle
(does not include backoff, virtual carrier sense, etc.). 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 that
reset the Trickle timer. reset the Trickle timer.
6. Operational Considerations 6. Operational Considerations
skipping to change at page 7, line 38 skipping to change at page 8, line 12
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 communication up transmitting on every interval: it is maintaining a Trickle
rate of 2 with only itself. Hence, the danger of mismatched k values communication rate of 2 with only itself. Hence, the danger of
is uneven transmission load that can deplete the energy of some mismatched k values is uneven transmission load that can deplete the
nodes. energy of some nodes.
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 similar size as the
slower nodes within a single slow interval time, but in that period slower nodes within a single slow interval time, but in that period
may suppress the slower nodes. However, such suppression will end may suppress the slower nodes. However, such suppression will end
after the first slow interval, when the nodes generally agree on the after the first slow interval, when the nodes generally agree on the
interval size. Hence, mismatched Imin values are usually not a interval size. Hence, mismatched Imin values are usually not a
significant concern. significant concern. Note that mismatched Imin values and matching
Imax doubling constants will lead to mismatched Imax values.
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 receivers situation) would have thought it
inconsistent, then the receiver will not respond properly and inform inconsistent, then the receiver will not respond properly and inform
the transmitter. This can lead the network to not reach a consistent the transmitter. This can lead the network to not reach a consistent
state. For this reason, unlike the configuration constants k, Imin, state. For this reason, unlike the configuration constants k, Imin,
and Imax, consistency definitions should be clearly stated in the and Imax, consistency definitions MUST be clearly stated in the
protocol and should not be configured at runtime. 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, and 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 are
1-5: these achieve a good balance between redundancy and low cost. 1-5: these achieve a good balance between redundancy and low
cost[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), c=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 (c-1) debugging and packet inspection, having the parameter describe (k-1)
can be counter-productive. Instead, it is RECOMMENDED that protocols can be confusing. Instead, it is RECOMMENDED that protocols which
which require turning off suppression reserve c=0 to mean c=infinity. require turning off suppression reserve k=0 to mean 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 as long as it takes to transmit k packets. Otherwise, two to three as long as it takes to transmit k packets. Otherwise,
if more than k nodes reset their intervals to Imin, the resulting if more than k nodes reset their intervals to Imin, the resulting
communication will lead to congestion and significant packet loss. communication will lead to congestion and significant packet loss.
Experimental results have shown that packet losses from congestion Experimental results have shown that packet losses from congestion
reduce Trickle's efficiency [Levis04]. reduce Trickle's efficiency [Levis04].
skipping to change at page 9, line 24 skipping to change at page 9, line 51
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, 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, cover. However, in dynamic network environments such as wireless and
the coordination needed to compute the optimal set of transmissions low-power, lossy networks, the coordination needed to compute the
is typically much greater than the benefits it provides. One of the optimal set of transmissions is typically much greater than the
benefits of Trickle is that it is so simple to implement and requires benefits it provides. One of the benefits of Trickle is that it is
so little state yet operates so efficiently. Efforts to improve it so simple to implement and requires so little state yet operates so
should be weighed against the cost of increased complexity. 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
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[I-D.hui-6man-trickle-mcast], network
configuration[Lin08][Dang09], and installing new application
programs[Hui04][Levis04].
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[Hui08].
7. Acknowledgements 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 Urlich Herberg, which
greatly improved the document.
8. IANA Considerations 8. IANA Considerations
This document has no IANA considerations. This document has no IANA considerations.
9. Security Considerations 9. Security Considerations
This document has no security considerations. This document has no security considerations.
10. References 10. References
10.1. Normative References 10.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 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, <htt
p://books.google.com/
books?id=3fb5eePdkBgC&pg=PA327&lpg=PA327>.
[Gnawali09]
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,
<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 Systems SenSys 2004, November 2004,
<http://portal.acm.org/citation.cfm?id=1031506>.
[Hui08] 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,
<http://portal.acm.org/citation.cfm?id=1460412.1460415>.
[I-D.hui-6man-trickle-mcast]
Hui, J. and R. Kelsey, "Multicast Forwarding Using
Trickle", draft-hui-6man-trickle-mcast-00 (work in
progress), July 2010.
[I-D.ietf-roll-rpl]
Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing
Protocol for Low power and Lossy Networks",
draft-ietf-roll-rpl-10 (work in progress), June 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, v.51 n.7,
July 2008, 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
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>.
Authors' Addresses Authors' Addresses
Philip Levis Philip Levis
Stanford University Stanford University
358 Gates Hall, Stanford University 358 Gates Hall, Stanford University
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
 End of changes. 33 change blocks. 
94 lines changed or deleted 202 lines changed or added

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