models wireless connectivity at the bit level. In these experiments, t is 1 s and t is 1 min.
lh
Each simulation had 400 nodes regularly placed in a
square grid with node spacings of 5, 10, 15, and 20 ft. By
varying network density, we were able to examine how
Trickle’s propagation rate scales over different loss rates
and physical densities. Density ranged from a 5ft spacing between nodes up to 20 ft (the networks were 95 × 95
to 380 × 380). Crossing the network in these topologies
takes from six to forty hops.a Time to complete propagation
varied from 16 s in the densest network to about 70 s for the
sparsest, representing a latency of 2. 7 and 1. 8 s per hop, respectively. The minimum per-hop Trickle latency is—ti 2 and
the consistency mechanism broadcasts a routine 1 s after
discovering an inconsistency, so the best case latency is 1. 5
s per hop. Despite an almost complete lack of coordination
between nodes, Trickle still is able to cause them to cooperate efficiently.
Figure 8 shows how adjusting t changes the propaga-
h
tion time for the 5 and 20 ft spacings. Increasing t from
h
1 to 5min does not significantly affect the propagation
time; indeed, in the sparse case, it propagates faster until roughly the 95th percentile. This result indicates that
there may be little trade-off between the maintenance
overhead of Trickle and its effectiveness in the face of a
propagation event.
A very large t can increase the time to discover incon-
h sistencies to be approximately -t-h 2. However, this is only true
when two stable subnets (t = t ) with different code recon-
h
nect. If new code is introduced, it immediately triggers
nodes to reset t to t , bringing them quickly to a consistent
l
state.
The Maté implementation of Trickle requires few system
resources. It requires approximately 70 bytes of RAM; half of
this is a message buffer for transmissions, a quarter is pointers to code routines. Trickle itself requires only 11 bytes for
its counters; the remaining RAM is for internal coordination
(e.g., pending and initialization flags). The executable code
is 1. 8 K ( 90 lines of code). Other implementations have similar costs. The algorithm requires few CPU cycles, and can
operate at a very low duty cycle.
3. 6. uses and improvements
Trickle is not just used by Maté; it and its derivatives are
used in almost every dissemination protocol today. The Deluge binary dissemination protocol for installing new sensor
node firmware uses Trickle to detect when nodes have different firmware versions9 (t = 500 ms, t = 1.1h). The MNP
lh
binary dissemination protocol (t = 16 s, t = 512 s) adjusts
lh
Trickle so that nodes with more neighbors are more likely
to send updates by preventing low degree nodes from suppressing high degree ones. 23 The Drip command layer of the
Sensornet Management System uses Trickle (t = 100 ms, t
lh
= 32 s) to install commands. 22 The Tenet programming ar-
a These hop count values come from computing the minimum cost
path across the network loss topology, where each link has a weight of
1
1–loss , i.e. the expected number of transmissions to successfully traverse that
link.
104 communicationS of the acm | JULY2008 | voL. 51 | no. 7
figure 7: time to consistency in 20 × 20 toSSim grids (seconds).
the hop count values in each legend are the expected number of
transmissions necessary to get from corner to corner, considering
loss.
16− 20
12− 16
8− 12
4− 8
0− 4
20− 25
15− 20
10− 15
5− 10
0− 5
(a) 5’ Spacing, 6 hops
(b) 10’ Spacing, 16 hops
32− 40
24− 32
16− 24
8− 16
0− 860− 75
45− 60
30− 45
15− 30
0− 15
(c) 15’ Spacing, 32 hops
(d) 20’ Spacing, 40 hops
figure 8: Rate nodes reach consistency for different t s in toSSim. a
h
larger t does not slow reaching consistency.
h
100%
80%
Nodes consistent
60%
40%
20%
5�, 60s
5�, 300 s
20�, 60 s
20�, 300 s
0%
0
10
20
30 40
Time (s)
50
60
70
chitecture uses Trickle (t = 100 ms, t = 32 s) to install small
lh
dynamic code tasks. 7
In the past few years, as collection protocols have improved in efficiency, they have also begun to use Trickle. The
CTP, the standard collection layer in the TinyOS operating
system distribution, 21 uses Trickle timers (t = 64 ms, t = 1 h)
lh
for its routing traffic. The 6LoWPAN IPv6 routing layer in
Arch Rock’s software uses Trickle to keep IPv6 routing tables
and ICMP neighbor lists consistent. 1 As protocols continue
to improve, Trickle’s efficacy and simplicity will cause it to
be used in more protocols and systems.
One limitation with Trickle as described in this paper
is that its maintenance cost grows O(n) with the number
of data items, as nodes must exchange version numbers.
This growth may be a hindering factor as Trickle’s use increases. Recent work on the DIP protocol addresses this
