--- 1/draft-ietf-roll-trickle-07.txt 2011-01-10 20:23:00.000000000 +0100 +++ 2/draft-ietf-roll-trickle-08.txt 2011-01-10 20:23:00.000000000 +0100 @@ -1,25 +1,25 @@ Networking Working Group P. Levis Internet-Draft Stanford University Intended status: Standards Track T. Clausen -Expires: July 9, 2011 LIX, Ecole Polytechnique +Expires: July 14, 2011 LIX, Ecole Polytechnique J. Hui Arch Rock Corporation O. Gnawali Stanford University J. Ko Johns Hopkins University - January 5, 2011 + January 10, 2011 The Trickle Algorithm - draft-ietf-roll-trickle-07 + draft-ietf-roll-trickle-08 Abstract The Trickle algorithm allows nodes in a lossy shared medium (e.g., low power and lossy networks) to exchange information in a highly robust, energy efficient, simple, and scalable manner. Dynamically 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 change. A simple suppression mechanism and transmission point @@ -35,21 +35,21 @@ Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference 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 (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect @@ -58,21 +58,21 @@ the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Trickle Algorithm Overview . . . . . . . . . . . . . . . . . . 4 4. Trickle Algorithm . . . . . . . . . . . . . . . . . . . . . . 5 4.1. Parameters and Variables . . . . . . . . . . . . . . . . . 5 - 4.2. Algorithm Description . . . . . . . . . . . . . . . . . . 6 + 4.2. Algorithm Description . . . . . . . . . . . . . . . . . . 5 5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . 6 6. Operational Considerations . . . . . . . . . . . . . . . . . . 7 6.1. Mismatched Redundancy Constants . . . . . . . . . . . . . 7 6.2. Mismatched Imin . . . . . . . . . . . . . . . . . . . . . 7 6.3. Mismatched Imax . . . . . . . . . . . . . . . . . . . . . 8 6.4. Mismatched Definitions . . . . . . . . . . . . . . . . . . 8 6.5. Specifying the Constant k . . . . . . . . . . . . . . . . 8 6.6. Relationship Between k and Imin . . . . . . . . . . . . . 9 6.7. Tweaks and Improvements to Trickle . . . . . . . . . . . . 9 6.8. Uses of Trickle . . . . . . . . . . . . . . . . . . . . . 9 @@ -162,28 +162,22 @@ 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 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 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 updates, then all of its neighbors can receive them without having to advertise their need. Some of these recipients might not have even - heard A's transmission. - - 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. + heard A's transmission. In this example, it does not matter who + first transmits, A or B; either case will detect the inconsistency. The fact that Trickle communication can be either transmission or reception enables the Trickle algorithm to operate in sparse as well as dense networks. A single, disconnected node must transmit at the Trickle communication rate. In a lossless, single-hop network of size n, the Trickle communication rate at each node equals the sum of the Trickle transmission rates across all nodes. The Trickle algorithm balances the load in such a scenario, as each node's Trickle transmission rate is 1/nth of the Trickle communication rate. Sparser networks require more transmissions per node, but the @@ -192,23 +186,23 @@ property in wireless networks and other shared media, where the channel is a valuable shared resource. Additionally, reducing transmissions in dense networks conserves system energy. 4. Trickle Algorithm This section describes the Trickle algorithm. 4.1. Parameters and Variables - A Trickle timer has three configuration parameters: the minimum - interval size Imin, the maximum interval size Imax, and a redundancy - constant k: + A Trickle timer runs for a defined interval and has three + configuration parameters: the minimum interval size Imin, the maximum + interval size Imax, and a redundancy constant k: o The minimum interval size, Imin, is defined in units of time (e.g., milliseconds, seconds). For example, a protocol might define the minimum interval as 100 milliseconds. o The maximum interval size, Imax, is described as a number of doublings of the minimum interval size (the base-2 log(max/min)). For example, a protocol might define Imax as 16. If the minimum interval is 100ms, then the amount of time specified by Imax is 100ms * 65536, 6,553.6 seconds, or approximately 109 minutes. @@ -220,46 +214,49 @@ variables: o I, the current interval size o t, a time within the current interval, and o c, a counter. 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 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 + 3. Whenever Trickle hears a transmission that is "consistent," it 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. - 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 specified by Imax, Trickle sets the interval length I to be the time specified by Imax. - 5. If Trickle hears a transmission that is "inconsistent," the - Trickle timer resets. If I is greater than Imin when a Trickle - 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), - 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. - Trickle can also reset the timer in response to external - "events." + 6. If Trickle hears a transmission that is "inconsistent" and I is + greater than Imin, it resets the Trickle timer. To reset the + timer, Trickle sets I to Imin and starts a new interval as in + step 2. If I is equal to Imin when Trickle hears an + "inconsistent" transmission, Trickle does nothing. Trickle can + also reset its timer in response to external "events." The terms consistent, inconsistent and event are in quotes because 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 @@ -284,20 +281,23 @@ o What constitutes a "consistent" transmission. o What constitutes an "inconsistent" transmission. o What "events," if any, besides inconsistent transmissions that reset the Trickle timer. 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 It is RECOMMENDED that a protocol which uses Trickle includes mechanisms to inform nodes of configuration parameters at runtime. However, it is not always possible to do so. In the cases where different nodes have different configuration parameters, Trickle may have unintended behaviors. This section outlines some of those behaviors and operational considerations as educational exercises. 6.1. Mismatched Redundancy Constants