--- 1/draft-ietf-roll-trickle-03.txt 2010-08-19 22:12:05.000000000 +0200 +++ 2/draft-ietf-roll-trickle-04.txt 2010-08-19 22:12:05.000000000 +0200 @@ -1,38 +1,38 @@ Networking Working Group P. Levis Internet-Draft Stanford University Intended status: Standards Track T. Clausen -Expires: February 19, 2011 LIX, Ecole Polytechnique +Expires: February 20, 2011 LIX, Ecole Polytechnique J. Hui Arch Rock Corporation O. Gnawali Stanford University J. Ko Johns Hopkins University - August 18, 2010 + August 19, 2010 The Trickle Algorithm - draft-ietf-roll-trickle-03 + draft-ietf-roll-trickle-04 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 selection allows Trickle's communication rate to scale - logarithmically with density. This document describes Trickle and - considerations in its use. + logarithmically with density. This document describes the Trickle + algorithm and considerations in its use. Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. @@ -41,56 +41,56 @@ 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." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at 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 (c) 2010 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 to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 - 3. Trickle Algorithm Overview . . . . . . . . . . . . . . . . . . 3 + 3. Trickle Algorithm Overview . . . . . . . . . . . . . . . . . . 4 4. Trickle Algorithm . . . . . . . . . . . . . . . . . . . . . . 5 4.1. Parameters and Variables . . . . . . . . . . . . . . . . . 5 - 4.2. Algorithm Description . . . . . . . . . . . . . . . . . . 5 + 4.2. Algorithm Description . . . . . . . . . . . . . . . . . . 6 5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . 6 - 6. Operational Considerations . . . . . . . . . . . . . . . . . . 6 + 6. Operational Considerations . . . . . . . . . . . . . . . . . . 7 6.1. Mismatched redundancy constants . . . . . . . . . . . . . 7 6.2. Mismatched Imin . . . . . . . . . . . . . . . . . . . . . 7 6.3. Mismatched Imax . . . . . . . . . . . . . . . . . . . . . 7 - 6.4. Mismatched definitions . . . . . . . . . . . . . . . . . . 7 + 6.4. Mismatched definitions . . . . . . . . . . . . . . . . . . 8 6.5. Specifying the constant k . . . . . . . . . . . . . . . . 8 6.6. Relationship between k and Imin . . . . . . . . . . . . . 8 6.7. Tweaks and improvements to Trickle . . . . . . . . . . . . 8 6.8. Uses of Trickle . . . . . . . . . . . . . . . . . . . . . 9 - 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 9 + 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 9. Security Considerations . . . . . . . . . . . . . . . . . . . 10 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10 10.1. Normative References . . . . . . . . . . . . . . . . . . . 10 10.2. Informative References . . . . . . . . . . . . . . . . . . 10 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11 1. Introduction The Trickle algorithm establishes a density-aware local communication @@ -108,58 +108,64 @@ is simple to implement, and requires very little state. Current implementations use 4-11 bytes of RAM and are 50-200 lines of C code[Levis08]. While Trickle was originally designed for reprogramming protocols (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 range of protocol design problems, including control traffic timing, multicast propagation, and route discovery. This flexibility stems 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 for its use. It also states requirements for protocol specifications that use Trickle. This document does not provide results on Trickle's performance or behavior, nor does it explain the algorithm's design in detail: interested readers should refer to [Levis04] and [Levis08]. 2. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 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 Trickle's basic primitive is simple: every so often, a node transmits data unless it hears a few other transmissions whose data suggest its own transmission is redundant. Examples of such data include routing state, software update versions, and the last heard multicast packet. - This primitive allows Trickle to scale to thousand-fold variations in network density, quickly propagate updates, distribute transmission load evenly, be robust to transient disconnections, handle network - repopulations, and impose a very low maintenance overhead: common - uses require on the order of a few packets per hour yet can respond - in milliseconds. + repopulations, and impose a very low maintenance overhead: one + example use, routing beacons in the CTP protocol [Gnawali09], + 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 exact address used can depend on both the underlying IP protocol as well as how the higher layer protocol uses Trickle. In IPv6, for example, it can be the link-local multicast address or another local multicast address, while in IPv4 it can be the broadcast address (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 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 updated node hearing something old. As long as every node 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 @@ -169,33 +175,33 @@ advertise their need. Some of these recipients might not even have 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. - The fact that 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 blaances - 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 utilization of the radio channel - over space will not increase. This is an important 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. + 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 utilization + of the radio channel over space will not increase. This is an + important 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: @@ -464,21 +470,21 @@ . [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] Winter, T., Thubert, P., and R. Team, "RPL: IPv6 Routing 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, "Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks"", Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation NSDI 2004, March 2004, . [Levis08] Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S., Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and A.