draft-ietf-roll-trickle-07.txt   draft-ietf-roll-trickle-08.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: July 9, 2011 LIX, Ecole Polytechnique Expires: July 14, 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
January 5, 2011 January 10, 2011
The Trickle Algorithm The Trickle Algorithm
draft-ietf-roll-trickle-07 draft-ietf-roll-trickle-08
Abstract Abstract
The Trickle algorithm allows nodes in a lossy shared medium (e.g., The Trickle algorithm allows nodes in a lossy shared medium (e.g.,
low power and lossy networks) to exchange information in a highly low power and lossy networks) to exchange information in a highly
robust, energy efficient, simple, and scalable manner. Dynamically robust, energy efficient, simple, and scalable manner. Dynamically
adjusting transmission windows allows Trickle to spread new adjusting transmission windows allows Trickle to spread new
information on the scale of link-layer transmission times while information on the scale of link-layer transmission times while
sending only a few messages per hour when information does not sending only a few messages per hour when information does not
change. A simple suppression mechanism and transmission point change. A simple suppression mechanism and transmission point
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 July 9, 2011. This Internet-Draft will expire on July 14, 2011.
Copyright Notice Copyright Notice
Copyright (c) 2011 IETF Trust and the persons identified as the Copyright (c) 2011 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
skipping to change at page 2, line 24 skipping to change at page 2, line 24
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . . 5
5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . 6 5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . 6
6. Operational Considerations . . . . . . . . . . . . . . . . . . 7 6. Operational Considerations . . . . . . . . . . . . . . . . . . 7
6.1. Mismatched Redundancy Constants . . . . . . . . . . . . . 7 6.1. Mismatched Redundancy Constants . . . . . . . . . . . . . 7
6.2. Mismatched Imin . . . . . . . . . . . . . . . . . . . . . 7 6.2. Mismatched Imin . . . . . . . . . . . . . . . . . . . . . 7
6.3. Mismatched Imax . . . . . . . . . . . . . . . . . . . . . 8 6.3. Mismatched Imax . . . . . . . . . . . . . . . . . . . . . 8
6.4. Mismatched Definitions . . . . . . . . . . . . . . . . . . 8 6.4. Mismatched Definitions . . . . . . . . . . . . . . . . . . 8
6.5. Specifying the Constant k . . . . . . . . . . . . . . . . 8 6.5. Specifying the Constant k . . . . . . . . . . . . . . . . 8
6.6. Relationship Between k and Imin . . . . . . . . . . . . . 9 6.6. Relationship Between k and Imin . . . . . . . . . . . . . 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
skipping to change at page 4, line 44 skipping to change at page 4, line 44
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 have even 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; either case will detect the inconsistency.
In this example, it does not matter who first transmits, A or B;
either case will detect the inconsistency. All that matters is that
some nodes communicate with one another at some nonzero rate. As
long as the network is connected and there is some minimum
communication rate for each node, the network will reach eventual
consistency.
The fact that Trickle communication can be either transmission or The fact that Trickle communication can be either transmission or
reception enables the Trickle algorithm to operate in sparse as well reception enables the Trickle algorithm to operate in sparse as well
as dense networks. A single, disconnected node must transmit at the as dense networks. A single, disconnected node must transmit at the
Trickle communication rate. In a lossless, single-hop network of Trickle communication rate. In a lossless, single-hop network of
size n, the Trickle communication rate at each node equals the sum of size n, the Trickle communication rate at each node equals the sum of
the Trickle transmission rates across all nodes. The Trickle the Trickle transmission rates across all nodes. The Trickle
algorithm balances the load in such a scenario, as each node's algorithm balances the load in such a scenario, as each node's
Trickle transmission rate is 1/nth of the Trickle communication rate. Trickle transmission rate is 1/nth of the Trickle communication rate.
Sparser networks require more transmissions per node, but the Sparser networks require more transmissions per node, but the
skipping to change at page 5, line 26 skipping to change at page 5, line 20
property in wireless networks and other shared media, where the property in wireless networks and other shared media, where the
channel is a valuable shared resource. Additionally, reducing channel is a valuable shared resource. Additionally, reducing
transmissions in 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 runs for a defined interval and has three
interval size Imin, the maximum interval size Imax, and a redundancy configuration parameters: the minimum interval size Imin, the maximum
constant k: interval size Imax, and a redundancy constant k:
o The minimum interval size, Imin, is defined in units of time o The minimum interval size, Imin, is defined in units of time
(e.g., milliseconds, seconds). For example, a protocol might (e.g., milliseconds, seconds). For example, a protocol might
define the minimum interval as 100 milliseconds. define the minimum interval as 100 milliseconds.
o The maximum interval size, Imax, is described as a number of o The maximum interval size, Imax, is described as a number of
doublings of the minimum interval size (the base-2 log(max/min)). doublings of the minimum interval size (the base-2 log(max/min)).
For example, a protocol might define Imax as 16. If the minimum For example, a protocol might define Imax as 16. If the minimum
interval is 100ms, then the amount of time specified by Imax is interval is 100ms, then the amount of time specified by Imax is
100ms * 65536, 6,553.6 seconds, or approximately 109 minutes. 100ms * 65536, 6,553.6 seconds, or approximately 109 minutes.
skipping to change at page 6, line 7 skipping to change at page 5, line 48
variables: variables:
o I, the current interval size o I, the current interval size
o t, a time within the current interval, and o t, a time within the current interval, and
o c, a counter. o c, a counter.
4.2. Algorithm Description 4.2. Algorithm Description
The Trickle algorithm has five rules: The Trickle algorithm has six rules:
1. When an interval begins, Trickle resets c to 0 and sets t to a 1. When the algorithm starts execution, it sets I to a value in the
range of [Imin, Imax], that is, greater than or equal to Imin and
less then or equal to Imax. The algorithm then begins the first
interval.
2. When an interval begins, Trickle resets c to 0 and sets t to a
random point in the interval, taken from the range [I/2, I), that random point in the interval, taken from the range [I/2, I), that
is, values greater than or equal to I/2 and less than I. The is, values greater than or equal to I/2 and less than I. The
interval ends at I. interval ends at I.
2. Whenever Trickle hears a transmission that is "consistent," it 3. Whenever Trickle hears a transmission that is "consistent," it
increments the counter c. increments the counter c.
3. At time t, Trickle transmits if and only if the counter c is less 4. At time t, Trickle transmits if and only if the counter c is less
than the redundancy constant k. than the redundancy constant k.
4. When the interval I expires, Trickle doubles the interval length. 5. When the interval I expires, Trickle doubles the interval length.
If this new interval length would be longer than the time If this new interval length would be longer than the time
specified by Imax, Trickle sets the interval length I to be the specified by Imax, Trickle sets the interval length I to be the
time specified by Imax. time specified by Imax.
5. If Trickle hears a transmission that is "inconsistent," the 6. If Trickle hears a transmission that is "inconsistent" and I is
Trickle timer resets. If I is greater than Imin when a Trickle greater than Imin, it resets the Trickle timer. To reset the
timer resets, Trickle sets I to Imin, resets c to 0, and sets t timer, Trickle sets I to Imin and starts a new interval as in
to random point in the interval, taken from the range [I/2, I), step 2. If I is equal to Imin when Trickle hears an
that is, values greater than or equal to I/2 and less than I. If "inconsistent" transmission, Trickle does nothing. Trickle can
I is equal to Imin, resetting a Trickle timer does nothing. also reset its timer in response to external "events."
Trickle 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 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 The only time the Trickle algorithm transmits is at step 3 of the
above algorithm. This means there is an inherent delay between above algorithm. This means there is an inherent delay between
detecting an inconsistency (shrinking I to Imin) and responding to detecting an inconsistency (shrinking I to Imin) and responding to
that inconsistency (transmitting at time t in the new interval). that inconsistency (transmitting at time t in the new interval).
This is intentional. Immediately responding to detecting an This is intentional. Immediately responding to detecting an
inconsistency can cause a broadcast storm, where many nodes respond inconsistency can cause a broadcast storm, where many nodes respond
skipping to change at page 7, line 24 skipping to change at page 7, line 24
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. o What information a node transmits in Trickle messages.
o What actions outside the algorithm the protocol takes, if any,
when it detects an inconsistency.
6. Operational Considerations 6. Operational Considerations
It is RECOMMENDED that a protocol which uses Trickle includes It is RECOMMENDED that a protocol 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
 End of changes. 14 change blocks. 
29 lines changed or deleted 29 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/