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 (jvasseur@cisco.com) is the Document Shepherd.
Adrian Farrel (adrian.farrel@huawei.com) is the Responsible AD.