The Trickle Algorithm
Extracted elements (24)
Protocol designers are cautioned against tweaking the Trickle algorithm without extensive experimental evidence, as its mechanisms are tightly integrated. Further reductions in transmissions or response time typically come at the cost of edge-case failures; simplicity and low state requirements are explicit design goals.
The algorithm introduces an intentional delay between detecting an inconsistency (resetting I to Imin) and responding to it (transmitting at time t). Immediately transmitting upon detecting inconsistency would cause a broadcast storm where many nodes respond simultaneously; the Trickle delay allows the suppression mechanism to scale the response across all node densities.
The transmission point t is chosen randomly from [I/2, I) rather than at a fixed point in the interval to avoid synchronized transmissions across nodes, distributing load evenly and enabling the suppression mechanism to work correctly.
Trickle counts both transmitted and received messages toward the 'Trickle communication rate', enabling operation in both sparse networks (where a single disconnected node must transmit at full rate) and dense networks (where suppression reduces per-node transmission rate), without protocol changes.
Trickle exponentially doubles the interval length when the network is consistent, reducing communication to a few packets per hour under stable conditions. This allows rapid propagation (Imin scale, e.g., milliseconds) when inconsistencies arise while conserving energy and channel capacity during steady state.
Trickle has been applied to reliable flooding/dissemination (version-number-based consistency), routing control traffic (RPL, CTP), multicast propagation, and network configuration maintenance. The algorithm's flexibility stems from allowing protocols to define 'consistency' and 'inconsistency' on a case-by-case basis.
Trickle relies exclusively on local communication (broadcast or local multicast) rather than unicast, making it robust to network re-population, transient disconnections, and lossy links, with minimal state (current implementations use 4-11 bytes of RAM and 50-200 lines of C code).
Trickle's suppression mechanism (suppressing transmission when c >= k) allows communication rate to scale logarithmically with network density. In a lossless single-hop network of n nodes, each node's transmission rate is 1/nth of the total communication rate, ensuring that denser networks do not consume more shared channel capacity.
Mismatched Imax values among nodes cause long-term transmission inequity: nodes with smaller Imax transmit more frequently and suppress those with larger Imax, potentially silencing high-Imax nodes entirely and causing unequal energy drain.
Mismatched Imin values are generally not a significant concern: faster nodes (lower Imin) will suppress slower nodes temporarily, but intervals converge to similar sizes within one slow interval period.
Mismatched k values cause uneven transmission load independent of density; a single node with k=2 in an otherwise k=1 network can transmit on every interval indefinitely, depleting its energy in low-power networks.
A protocol SHOULD set k and Imin such that Imin is at least two to three times as long as the time required to transmit k packets; otherwise, if more than k nodes simultaneously reset to Imin, the resulting burst of communication causes congestion and significant packet loss that reduces Trickle's efficiency.
A protocol specification that uses Trickle MUST specify default values for Imin, Imax, and k.
A protocol using Trickle MUST specify what constitutes a 'consistent' transmission, what constitutes an 'inconsistent' transmission, what external events (if any) reset the Trickle timer, what information a node transmits in Trickle messages, and what actions the protocol takes outside the algorithm when an inconsistency is detected.
Consistency definitions MUST be clearly stated in the protocol and SHOULD NOT be configured at runtime, because unlike k, Imin, and Imax, mismatched consistency definitions can prevent the network from ever reaching a consistent state.
It is RECOMMENDED that a protocol using Trickle include mechanisms to inform nodes of configuration parameters at runtime, though this is not always possible.
It is RECOMMENDED that protocols which need to allow disabling suppression reserve k=0 to mean k=infinity, since k=0 has no meaningful value as a natural number and avoids off-by-one confusion in packet inspection.
Setting k to infinity (disabling suppression) is NOT RECOMMENDED, as it causes every node to transmit on every interval and can cause congestion in dense networks; k should be set to a high value (e.g., 5 or 10) rather than infinity.
The default value of Imin SHOULD be specified in terms of the worst-case latency of a link-layer transmission (e.g., 'four times the worst-case link-layer latency') rather than as an absolute time value, to accommodate varying link-layer properties.
The Trickle timer has three configuration parameters: Imin (minimum interval size, in time units), Imax (maximum interval size, expressed as number of doublings of Imin), and k (redundancy constant, a natural number greater than zero).
Trickle maintains three runtime variables: I (current interval size), t (a time point within the current interval chosen from [I/2, I)), and c (a counter of consistent transmissions heard in the current interval).
An adversary can attempt to prevent nodes from reaching consistency by sending spoofed 'consistent' messages that suppress a node's transmissions, keeping it unable to notify neighbors of an inconsistency. Authenticated messages or a transitive consistency model mitigate this; additionally, because Trickle operates on shared broadcast media, an adversary suppressing node A must itself send messages inconsistent with A's neighbors, so it cannot simultaneously suppress A and hide the inconsistency from the network. Trickle should filter unicast messages to limit this attack surface.
An adversary can force excessive packet transmissions by triggering Trickle timer resets, increasing energy consumption and potentially depleting battery-powered nodes. Protocols should authenticate any messages or events that can cause a timer reset to prevent forgery.
The Trickle algorithm defines six rules: (1) on start, set I in [Imin, Imax]; (2) on interval begin, reset c=0 and pick t randomly from [I/2, I); (3) on consistent reception, increment c; (4) at time t, transmit only if c < k; (5) on interval expiry, double I up to Imax; (6) on inconsistent reception with I > Imin, reset I to Imin and begin a new interval.