draft-ietf-roll-trickle-05.txt   draft-ietf-roll-trickle-06.txt 
Networking Working Group P. Levis Networking Working Group P. Levis
Internet-Draft Stanford University Internet-Draft Stanford University
Intended status: Standards Track T. Clausen Intended status: Standards Track T. Clausen
Expires: May 14, 2011 LIX, Ecole Polytechnique Expires: June 9, 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
November 10, 2010 December 6, 2010
The Trickle Algorithm The Trickle Algorithm
draft-ietf-roll-trickle-05 draft-ietf-roll-trickle-06
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
skipping to change at page 1, line 46 skipping to change at page 1, line 46
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
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."
This Internet-Draft will expire on May 14, 2011. This Internet-Draft will expire on June 9, 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
skipping to change at page 2, line 27 skipping to change at page 2, line 27
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Trickle Algorithm Overview . . . . . . . . . . . . . . . . . . 4 3. Trickle Algorithm Overview . . . . . . . . . . . . . . . . . . 4
4. Trickle Algorithm . . . . . . . . . . . . . . . . . . . . . . 5 4. Trickle Algorithm . . . . . . . . . . . . . . . . . . . . . . 5
4.1. Parameters and Variables . . . . . . . . . . . . . . . . . 5 4.1. Parameters and Variables . . . . . . . . . . . . . . . . . 5
4.2. Algorithm Description . . . . . . . . . . . . . . . . . . 6 4.2. Algorithm Description . . . . . . . . . . . . . . . . . . 6
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 . . . . . . . . . . . . . . . . . . . . . 7 6.3. Mismatched Imax . . . . . . . . . . . . . . . . . . . . . 7
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 . . . . . . . . . . . . . 8 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. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10
9. Security Considerations . . . . . . . . . . . . . . . . . . . 10 9. Security Considerations . . . . . . . . . . . . . . . . . . . 10
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11
10.1. Normative References . . . . . . . . . . . . . . . . . . . 11 10.1. Normative References . . . . . . . . . . . . . . . . . . . 11
10.2. Informative References . . . . . . . . . . . . . . . . . . 11 10.2. Informative References . . . . . . . . . . . . . . . . . . 11
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12
1. Introduction 1. Introduction
skipping to change at page 3, line 29 skipping to change at page 3, line 29
is simple to implement, and requires very little state. Current is simple to implement, and requires very little state. Current
implementations use 4-11 bytes of RAM and are 50-200 lines of C implementations use 4-11 bytes of RAM and are 50-200 lines of C
code[Levis08]. 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. 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 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 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
skipping to change at page 7, line 14 skipping to change at page 7, line 14
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
It is RECOMMENDED that a protocol which uses Trickle include It is RECOMMENDED that a protocol which uses Trickle includes
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.
skipping to change at page 8, line 7 skipping to change at page 8, line 7
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 MUST 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 1-5: these achieve a good balance between redundancy and low
skipping to change at page 8, line 41 skipping to change at page 8, line 41
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 which 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
Trickle is based on a small number of simple, tightly integrated Trickle is based on a small number of simple, tightly integrated
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
skipping to change at page 9, line 44 skipping to change at page 9, line 44
be used. These examples should not be considered exhaustive. be 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 is when a node
hears a newer version number or receives new data. A consistency is 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 when a node hears an older or equal version number. When hearing an
older version number, rather than reset its own Trickle timer, it older version number, rather than reset its own Trickle timer, it
sends an update. Nodes with old version numbers that receive the sends an update. Nodes with old version numbers that receive the
update will then reset their own timers, leading to fast propagation update will then reset their own timers, leading to fast propagation
of the new data. Examples of this use include of the new data. Examples of this use include multicast[Hui08a],
multicast[I-D.hui-6man-trickle-mcast], network network configuration[Lin08][Dang09], and installing new application
configuration[Lin08][Dang09], and installing new application
programs[Hui04][Levis04]. 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 which contain routing state. An inconsistency is when
the routing topology changes in a way that could lead to loops or the routing topology changes in a way that could lead to loops or
significant stretch: examples include when the routing layer detects significant stretch: examples include when the routing layer detects
a routing loop or when a node's routing cost changes significantly. a routing loop or when a node's routing cost changes significantly.
Consistency is when the routing topology is operating well and is Consistency is when the routing topology is operating well and is
delivering packets successfully. Using the Trickle algorithm in this delivering packets successfully. Using the Trickle algorithm in this
way allows a routing protocol to react very quickly to problems (Imin way allows a routing protocol to react very quickly to problems (Imin
is small) but send very few beacons when the topology is stable. 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], Examples of this use include RPL[I-D.ietf-roll-rpl], CTP[Gnawali09],
and some current commericial IPv6 routing layers[Hui08]. and some current commericial 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 Urlich Herberg, which Yoav Ben-Yehezkel, Alexandru Petrescu, and Ulrich Herberg, which
greatly improved the document. 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
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
skipping to change at page 11, line 38 skipping to change at page 11, line 37
ACM Conference on Embedded Networked Systems SenSys 2009, ACM Conference on Embedded Networked Systems SenSys 2009,
November 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 Systems SenSys 2004, November 2004,
<http://portal.acm.org/citation.cfm?id=1031506>. <http://portal.acm.org/citation.cfm?id=1031506>.
[Hui08] Hui, J. and D. Culler, "IP is dead, long live IP for [Hui08a] Hui, J., "An Extended Internet Architecture for Low-Power
Wireless Networks - Design and Implementation", UC
Berkeley Technical Report EECS-2008-116, September 2008,
<http://portal.acm.org/citation.cfm?id=1460412.1460415>.
[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 Systems SenSys 2008,
November 2008, November 2008,
<http://portal.acm.org/citation.cfm?id=1460412.1460415>. <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] [I-D.ietf-roll-rpl]
Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J.,
Kelsey, R., Levis, P., Pister, K., Struik, R., and J. Kelsey, R., Levis, P., Pister, K., Struik, R., and J.
Vasseur, "RPL: IPv6 Routing Protocol for Low power and Vasseur, "RPL: IPv6 Routing Protocol for Low power and
Lossy Networks", draft-ietf-roll-rpl-15 (work in Lossy Networks", draft-ietf-roll-rpl-15 (work in
progress), November 2010. progress), November 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>.
 End of changes. 20 change blocks. 
27 lines changed or deleted 28 lines changed or added

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