munication connectivity varies due to environmental and
electromagnetic factors, with the additional constraint
that no human being will shepherd the device to a better setting, as with a cell phone or a laptop. The degree
of the network at a node, i.e., the number of nodes in its
communication neighborhood, is determined not by the
desired network organization but by the physical device
placement, which is often dictated by application requirements and physical constraints. There may be thousands
of nodes in close proximity, or just a few. A single transmission may be received by many devices, so any retransmission, response, or even a simple acknowledgment,
may cause huge contention, interference, and loss. Redundancy is essential for reliability, but it also can be a
primary cause of loss.
This last point is one of the key observations that have
emerged from a decade of development of networking abstractions for wireless sensor networks: the variety of network topologies and densities across which sensor network
protocols must operate calls for a polite, density-aware, local
retransmission scheme. This paper describes the Trickle algorithm, which uses such a communication pattern to provide an eventual consistency mechanism to protocols and
services. In the past ten years, a key insight that has emerged
from the wireless sensor network community is that many
protocol problems can be reduced to maintaining eventual consistency. Correspondingly, Trickle has emerged as
the core networking primitive at the heart of practical, efficient, and robust implementations of many sensor network
protocols and systems. Before diving into the details of the
Trickle, however, we review how core sensor networking protocols work and differ from conventional networking protocols, with the goal of exploring how a Trickle-like primitive
satisfies some of their needs.
2. net WoRKinG PRotocoLS
Networking issues are at the core of embedded sensor network design because radio communication—listening,
receiving, and transmitting—dominates the active energy
budget and defines system lifetime. The standard energy
cost metric for multihop protocols, in either link layer
meshing or network layer routing, is communication cost,
defined as the number of individual radio transmissions
and receptions. One protocol is more efficient than another
if it can provide equivalent performance (e.g., throughput,
latency, delivery ratio) at a lower communication cost. Protocols focus on minimizing transmissions and making sure
transmitted packets arrive successfully.
Almost all sensor network systems rely on two multihop
protocols for their basic operation: a collection protocol
for pulling data out of a network and a dissemination
protocol for pushing data into a network through one or
more distinguished nodes or egress routers. Many higher
level protocols build on dissemination and collection. For
example, reprogramming services such as Deluge9 use
dissemination to deliver commands to change program
images. Management layers22 and remote source-level debuggers25 also use dissemination. Reliable transport protocols, such as RCRT, 18 and rate control protocols such as
IFRC, 19 operate on collection trees. Point-to-point routing
schemes, such as S4, 16 establish overlays over multiple
parallel collection topologies.
While collection and dissemination have the opposite
communication patterns (all-to-one vs. one-to-all) and differ
in reliability (unreliable vs. reliable), both maintain eventually consistent shared state between nodes. The rest of this
section provides a high-level overview of these two protocol
classes. It provides details on the challenging problems they
introduce, and how some of them can be solved through
eventual consistency.
2. 1. Pushing data in: dissemination
One problem sensor network administrators face is dynamically changing how a network collects data by changing the
sampled sensors, the sampling rate, or even the code running on the nodes by disseminating the change to every
node in a network. We begin with a discussion of dissemination protocols because they were the original impetus for
Trickle and are its simplest application.
Early systems used packet floods to disseminate changes.
Flooding protocols rebroadcast packets they receive. Flooding is very simple—often just a line or two of code—but has
many problems. First, floods are unreliable. Inevitably, some
nodes do not receive the packet, so users typically repeatedly
flood until every node receives it. Second, in high density
networks, many nodes end up rebroadcasting packets at the
same time. These messages collide and cause a form of network collapse called a “broadcast storm.” 17
Second-generation dissemination and network programming systems like Xnp3 and TinyDB15 use an adaptive flood
combined with a protocol to request missing messages.
Adaptive flooding uses an estimate of the node density to
limit the flooding rate. The missing message protocol allows nodes to request the (hopefully few) missing messages
from their neighbors. Unfortunately, getting such protocols
to work well can be tricky, especially across a range of network densities and object sizes.
Another way to look at dissemination protocols is that
they ensure that every node has an eventually consistent
version of some shared state, such as the value of a configuration parameter or command. Data consistency is when
all nodes have the same version of that state, and nodes resolve inconsistencies by updating neighbors to the newer
version. Inductively, these definitions cause the network to
converge on the most recent version. To disseminate a command, a system installs it on one node as a newer version
and initiates the consistency protocol.
Casting dissemination as a data consistency problem
means it does not provide full reliability. Eventual consistency only promises to deliver the most recent version to connected nodes. Disconnected nodes can and
often do miss updates. In practice, however, this limitation is rarely problematic. An administrator who changes the data reporting rate three times then adds some
new nodes and expects them to receive the most recent
reporting rate, not all three. Similarly, when sending
commands, users do not expect a new node to receive
the entire history of all commands injected into a net-