draft-ietf-roll-trickle-03.txt   draft-ietf-roll-trickle-04.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: February 19, 2011 LIX, Ecole Polytechnique Expires: February 20, 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
August 18, 2010 August 19, 2010
The Trickle Algorithm The Trickle Algorithm
draft-ietf-roll-trickle-03 draft-ietf-roll-trickle-04
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 allows Trickle's communication rate to scale
logarithmically with density. This document describes Trickle and logarithmically with density. This document describes the Trickle
considerations in its use. algorithm and 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.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet- other groups may also distribute working documents as Internet-
Drafts. Drafts.
skipping to change at page 2, line 6 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 February 19, 2011. This Internet-Draft will expire on February 20, 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 . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . . 5 4.2. Algorithm Description . . . . . . . . . . . . . . . . . . 6
5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . 6 5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . 6
6. Operational Considerations . . . . . . . . . . . . . . . . . . 6 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 . . . . . . . . . . . . . . . . . . 7 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 . . . . . . . . . . . . 8 6.7. Tweaks and improvements to Trickle . . . . . . . . . . . . 8
6.8. Uses of Trickle . . . . . . . . . . . . . . . . . . . . . 9 6.8. Uses of Trickle . . . . . . . . . . . . . . . . . . . . . 9
7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 9 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10
9. Security Considerations . . . . . . . . . . . . . . . . . . . 10 9. Security Considerations . . . . . . . . . . . . . . . . . . . 10
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10
10.1. Normative References . . . . . . . . . . . . . . . . . . . 10 10.1. Normative References . . . . . . . . . . . . . . . . . . . 10
10.2. Informative References . . . . . . . . . . . . . . . . . . 10 10.2. Informative References . . . . . . . . . . . . . . . . . . 10
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11
1. Introduction 1. Introduction
The Trickle algorithm establishes a density-aware local communication The Trickle algorithm establishes a density-aware local communication
skipping to change at page 4, line 29 skipping to change at page 4, 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." "agreement" or an "inconsistency;" Section Section 6.8 presents a few
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
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].
Additionally, this document introduces the following terminology:
Trickle communication rate: the sum of the number of messages sent
or received by the Trickle algorithm in an interval.
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: common repopulations, and impose a very low maintenance overhead: one
uses require on the order of a few packets per hour yet can respond example use, routing beacons in the CTP protocol [Gnawali09],
in milliseconds. requires sending on the order of a few packets per hour yet can
respond in milliseconds.
Trickle sends all messages to a local communication address. The 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 broadcast: 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 its data is consistent with their
own state, or a recipient detects an inconsistency. Detection can be 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 the result of either an out-of-date node hearing something new, or an
updated node hearing something old. As long as every node 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
skipping to change at page 5, line 43 skipping to change at page 5, line 50
advertise their need. Some of these recipients might not even have advertise their need. Some of these recipients might not even have
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 communication can be either transmission or reception The fact that Trickle communication can be either transmission or
enables the Trickle algorithm to operate in sparse as well as dense reception enables the Trickle algorithm to operate in sparse as well
networks. A single, disconnected node must transmit at the Trickle as dense networks. A single, disconnected node must transmit at the
communication rate. In a lossless, single-hop network of size n, the Trickle communication rate. In a lossless, single-hop network of
Trickle communication rate at each node equals the sum of the Trickle size n, the Trickle communication rate at each node equals the sum of
transmission rates across all nodes. The Trickle algorithm blaances the Trickle transmission rates across all nodes. The Trickle
the load in such a scenario, as each node's Trickle transmission rate algorithm balances the load in such a scenario, as each node's
is 1/nth of the Trickle communication rate. Sparser networks require Trickle transmission rate is 1/nth of the Trickle communication rate.
more transmissions per node, but utilization of the radio channel Sparser networks require more transmissions per node, but utilization
over space will not increase. This is an important property in of the radio channel over space will not increase. This is an
wireless networks and other shared media, where the channel is a important property in wireless networks and other shared media, where
valuable shared resource. Additionally, reducing transmissions in the channel is a valuable shared resource. Additionally, reducing
dense networks conserves system energy. transmissions in 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
interval size Imin, the maximum interval size Imax, and a redundancy interval size Imin, the maximum interval size Imax, and a redundancy
constant k: constant k:
skipping to change at page 12, line 9 skipping to change at page 12, line 22
<http://portal.acm.org/citation.cfm?id=1460412.1460415>. <http://portal.acm.org/citation.cfm?id=1460412.1460415>.
[I-D.hui-6man-trickle-mcast] [I-D.hui-6man-trickle-mcast]
Hui, J. and R. Kelsey, "Multicast Forwarding Using Hui, J. and R. Kelsey, "Multicast Forwarding Using
Trickle", draft-hui-6man-trickle-mcast-00 (work in Trickle", draft-hui-6man-trickle-mcast-00 (work in
progress), July 2010. progress), July 2010.
[I-D.ietf-roll-rpl] [I-D.ietf-roll-rpl]
Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing
Protocol for Low power and Lossy Networks", Protocol for Low power and Lossy Networks",
draft-ietf-roll-rpl-10 (work in progress), June 2010. draft-ietf-roll-rpl-11 (work in progress), July 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. 17 change blocks. 
31 lines changed or deleted 37 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/