draft-ietf-roll-trickle-06.txt   draft-ietf-roll-trickle-07.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: June 9, 2011 LIX, Ecole Polytechnique Expires: July 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
December 6, 2010 January 5, 2011
The Trickle Algorithm The Trickle Algorithm
draft-ietf-roll-trickle-06 draft-ietf-roll-trickle-07
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 June 9, 2011. This Internet-Draft will expire on July 9, 2011.
Copyright Notice Copyright Notice
Copyright (c) 2010 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
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
skipping to change at page 2, line 29 skipping to change at page 2, line 29
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 . . . . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . 8 6.6. Relationship Between k and Imin . . . . . . . . . . . . . 9
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
skipping to change at page 4, line 30 skipping to change at page 4, line 30
respond in milliseconds. respond 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 both the underlying IP protocol as
well as how the higher layer protocol uses Trickle. In IPv6, for well as how the higher layer protocol uses Trickle. In IPv6, for
example, it can be the link-local multicast address or another local example, it can be the link-local multicast address or another local
multicast address, while in IPv4 it can be the broadcast address multicast 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 its data is consistent with their node that hears the message finds the message data is consistent with
own state, or a recipient detects an inconsistency. Detection can be its own state, or a recipient detects an inconsistency. Detection
the result of either an out-of-date node hearing something new, or an can be the result of either an out-of-date node hearing something
updated node hearing something old. As long as every node new, or an updated node hearing something old. As long as every node
communicates somehow - either receives or transmits - some node will communicates somehow - either receives or transmits - some node will
detect the need for an update. 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 even have advertise their need. Some of these recipients might not have even
heard A's transmission. 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 Trickle communication can be either transmission or The fact that Trickle communication can be either transmission or
skipping to change at page 6, line 37 skipping to change at page 6, line 37
timer resets, Trickle sets I to Imin, resets c to 0, and sets t timer resets, Trickle sets I to Imin, resets c to 0, and sets t
to random point in the interval, taken from the range [I/2, I), to 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. If that is, values greater than or equal to I/2 and less than I. If
I is equal to Imin, resetting a Trickle timer does nothing. I is equal to Imin, resetting a Trickle timer does nothing.
Trickle can also reset the timer in response to external Trickle can also reset the timer in response to external
"events." "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 how a protocol uses Trickle. their meaning depends on how a protocol uses Trickle.
The only time the Trickle algorithm transmits is at step 3 of the
above algorithm. This means there is an inherent delay between
detecting an inconsistency (shrinking I to Imin) and responding to
that inconsistency (transmitting at time t in the new interval).
This is intentional. Immediately responding to detecting an
inconsistency can cause a broadcast storm, where many nodes respond
at once and in a synchronized fashion. By making responses follow
the Trickle algorithm (with the minimal interval size), a protocol
can benefit from Trickle's suppression mechanism and scale across a
huge range of node densities.
5. Using Trickle 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
skipping to change at page 7, line 12 skipping to change at page 7, line 22
first link-layer transmission of the frame assuming an idle first link-layer transmission of the frame assuming an idle
channel (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.
o What information a node transmits in Trickle messages.
6. Operational Considerations 6. Operational Considerations
It is RECOMMENDED that a protocol which uses Trickle includes 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
skipping to change at page 12, line 4 skipping to change at page 12, line 14
[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 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.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-17 (work in
progress), November 2010. 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.
 End of changes. 13 change blocks. 
15 lines changed or deleted 27 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/