The Trickle Algorithm
Draft of message to be sent after approval:
From: The IESG <email@example.com> To: IETF-Announce <firstname.lastname@example.org> Cc: Internet Architecture Board <email@example.com>, RFC Editor <firstname.lastname@example.org>, roll mailing list <email@example.com>, roll chair <firstname.lastname@example.org> Subject: Protocol Action: 'The Trickle Algorithm' to Proposed Standard (draft-ietf-roll-trickle-08.txt) The IESG has approved the following document: - 'The Trickle Algorithm' (draft-ietf-roll-trickle-08.txt) as a Proposed Standard This document is the product of the Routing Over Low power and Lossy networks Working Group. The IESG contact persons are Adrian Farrel and Stewart Bryant. A URL of this Internet Draft is: http://datatracker.ietf.org/doc/draft-ietf-roll-trickle/
Technical Summary 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 the Trickle algorithm and considerations in its use. The Trickle algorithm establishes a density-aware local communication primitive with an underlying consistency model that guides when a node transmits. When a node's data does not agree with its neighbors, that node communicates quickly to resolve the inconsistency (e.g., in milliseconds). When nodes agree, they slow their communication rate exponentially, such that nodes send packets very infrequently (e.g., a few packets per hour). Instead of flooding a network with packets, the algorithm controls the send rate so each node hears a small trickle of packets, just enough to stay consistent. Furthermore, by relying only on local communication (e.g., broadcast or local multicast), Trickle handles network re-population, is robust to network transience, loss, and disconnection, 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. 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;" 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. Working Group Summary No discontent. Document Quality The Trickle algorithm is a true component of the RPL routing protocol, specified by the ROLL WG, which has passed WG Last Call. Since RPL has been implemented by more than a dozens of implementation and several interoperability events took place, the trickle algorithm has also been successfully implemented (the reason for documenting trickle in a separate document was that it could be used in other circumstances than RPL) Personnel JP Vasseur (email@example.com) is the Document Shepherd. Adrian Farrel (firstname.lastname@example.org) is the Responsible AD.