<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
-<meta name="generator" content="Docutils 0.4: http://docutils.sourceforge.net/" />
-<title>Dissemination</title>
+<meta name="generator" content="Docutils 0.4.1: http://docutils.sourceforge.net/" />
+<title>Dissemination of Small Values</title>
<meta name="author" content="Philip Levis and Gilman Tolle" />
<style type="text/css">
</style>
</head>
<body>
-<div class="document" id="dissemination">
-<h1 class="title">Dissemination</h1>
+<div class="document" id="dissemination-of-small-values">
+<h1 class="title">Dissemination of Small Values</h1>
<table class="docinfo" frame="void" rules="none">
<col class="docinfo-name" />
<col class="docinfo-content" />
<td>Philip Levis and Gilman Tolle</td></tr>
<tr class="field"><th class="docinfo-name">Draft-Created:</th><td class="field-body">10-Dec-2004</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.7</td>
+<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.8</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2007-06-14</td>
+<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2007-08-24</td>
</tr>
<tr class="field"><th class="docinfo-name">Draft-Discuss:</th><td class="field-body">TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu></td>
</tr>
<h1><a id="abstract" name="abstract">Abstract</a></h1>
<p>The memo documents the interfaces, components, and semantics for
disseminating small (smaller than a single packet payload) pieces of
-data in TinyOS 2.x. Dissemination is reliably delivering a piece of
-data to every node in a network.</p>
+data in TinyOS 2.x. Dissemination establishes eventual consistency
+across the entire network on a shared variable and tells an
+application when the variable changes. Common uses of this mechanism
+include network reconfiguration and reprogramming.</p>
</div>
<div class="section">
<h1><a id="introduction" name="introduction">1. Introduction</a></h1>
-<p>Dissemination is a basic sensor network protocol. The ability to
-reliably deliver a piece of data to every node allows administrators
-to reconfigure, query, and reprogram a network. Reliability is
-important because it makes the operation robust to temporary
-disconnections or high packet loss. Unlike flooding protocols, which
-are discrete efforts that terminate, possibly not delivering the data
-to some nodes, dissemination achieves reliability by using a
-continuous approach that can detect when a node is missing the data.</p>
+<p>Dissemination is a service for establishing eventual consistency on a
+shared variable. Every node in the network stores a copy of this
+variable. The dissemination service tells nodes when the value
+changes, and exchanges packets to it will reach eventual consistency
+across the network. At any given time, two nodes may disagree, but
+over time the number of disagreements will shrink and the network will
+converge on a single value.</p>
+<p>Eventual consistency is robust to temporary disconnections or high
+packet loss. Unlike flooding protocols, which are discrete efforts
+that terminate and not reach consistency, dissemination assures that
+the network will reach consensus on the value as long as it is not
+disconnected.</p>
<p>Depending on the size of the data item, dissemination protocols can
differ greatly: efficiently disseminating tens of kilobytes of a
binary requires a different protocol than disseminating a two-byte
similarities. Separating a dissemination protocol into two parts ---
control traffic and data traffic --- shows that while the data traffic
protocols are greatly dependent on the size of the data item, the
-control traffic tends to be the same or very similar.</p>
-<p>Being able to reliably disseminate small values into a network is a
-useful building block for sensornet applications. It allows an
-administrator to inject small programs or commands and configuration
-constants. Because TinyOS nodes have limited RAM, these dissemination
-services have the assumption that data values have some form of
-versioning. Dissemination propagates only the most recent version.
-This means that if a node is disconnected from a network and the
-network goes through eight versions of a disseminated value, when it
-rejoins the network it will only see the most recent. The rest of this
-document describes a set of components and interfaces for a
-dissemination service of this kind.</p>
+control traffic tends to be the same or very similar. For example, the
+Deluge binary reprogramming service, disseminates metadata about the
+binaries. When nodes learn the disseminated metadata differs from the
+metadata of their local binary, they know they either have a bad
+binary or need a new one.</p>
+<p>Novelty is an explicit consideration in dissemination's consistency
+model: it seeks to have every node agree on what the most recent
+version of the variable is. In this way, a node can prompt the network
+to reach consistency on a new value for a variable by telling the
+network it is newer. If several nodes all decide they need to update
+the variable, dissemination ensures that the network converges on a
+single value. Consistency does not mean that every node will see every
+possible value the variable takes: it only means that the network will
+eventually agree on what the newest is. This means that if a node is
+disconnected from a network and the network goes through eight
+versions of a disseminated value, when it rejoins the network it will
+only see the most recent.</p>
+<p>Being able to disseminate small values into a network is a useful
+building block for sensornet applications. It allows an administrator
+to inject small programs or commands and configuration constants. For
+example, installing a small program through the entire network can be
+cast as the problem of establishing consistency on a variable that
+contains the program.</p>
+<p>The rest of this document describes a set of components and interfaces
+for a dissemination service included in TinyOS 2.0. This service only
+handles small values that can fit in a single packet. Larger values
+would likely require different interfaces and abstractions.</p>
</div>
<div class="section">
<h1><a id="dissemination-interfaces" name="dissemination-interfaces">2. Dissemination interfaces</a></h1>
<pre class="literal-block">
interface DisseminationValue<t> {
command const t* get();
+ command void set(const t*);
event void changed();
}
command void change(t* newVal);
}
</pre>
-<p>These interfaces assume that the allocation for the disseminated data
-is within the dissemination service. A consumer can obtain a const
-pointer to the data through DissemnationValue.get(). It MUST NOT
-store this pointer, as it may not be constant across updates.
-Additionally, doing so wastes RAM, as it can be easily re-obtained.
-The service signals a changed() event whenever the dissemination value
-changes, in case the consumer needs to perform some computation on it.</p>
-<p>DisseminationUpdate has a single command, <tt class="docutils literal"><span class="pre">change</span></tt>, which takes a
+<p>These interfaces assume that the dissemination service allocates space
+to store the variable. In that way, multiple components can all access
+and share the same variable that the dissemination service establishes
+consistency over. A consumer can obtain a const pointer to the data
+through DissemnationValue.get(). It MUST NOT store this pointer, as it
+may not be constant across updates. Additionally, doing so wastes
+RAM, as it can be easily re-obtained. The service signals a changed()
+event whenever the dissemination value changes, in case the consumer
+needs to perform some computation on it or take some action.</p>
+<p>DisseminationValue has a command, ''set'', which allows a node to
+change its local copy of a value without establishing consistency.
+This command exists so a node can establish an initial value for the
+variable. A node MUST NOT call ''set'' after it has handled a
+''changed'' event, or the network may become inconsistent. If a node
+has received an update or a client has called ''change'' then set MUST
+NOT apply its new value.</p>
+<p>DisseminationUpdate has a single command, ''change'', which takes a
pointer as an argument. This pointer is not stored: a provider of
-DisseminationUpdate MUST copy the data into its own allocated memory.</p>
+DisseminationUpdate MUST copy the data into its own allocated memory.
+DisseminationValue MUST signal ''changed'' in response to a
+call to ''change''.</p>
<p>A dissemination protocol MUST reach consensus on the newest value in a
network (assuming the network is connected). Calling change
implicitly makes the data item "newer" so that it will be disseminated
provides interface DisseminationUpdate <t>;
}
</pre>
-<p>The t argument MUST be able to fit in a single message_t [TEP111] after
-considering the headers that the dissemination protocol introduces.
-A dissemination implementation SHOULD have a compile error if a larger
-type than this is used.</p>
-<p>As each instantiation of DisseminatorC probably allocates storage
-and generates code, if more than one component wants to share
-a disseminated value then they SHOULD encapsulate the value in
-a non-generic component that can be shared. E.g.:</p>
+<p>The t argument MUST be able to fit in a single message_t [TEP111]
+after considering the headers that the dissemination protocol
+introduces. A dissemination implementation SHOULD have a compile
+error if a larger type than this is used.</p>
+<p>As each instantiation of DisseminatorC probably allocates storage and
+generates code, if more than one component wants to share a
+disseminated value then they SHOULD encapsulate the value in a
+non-generic component that can be shared. E.g.:</p>
<pre class="literal-block">
configuration DisseminateTxPowerC {
provides interface DisseminationValue<uint8_t>;
</div>
<div class="section">
<h1><a id="dissemination-keys" name="dissemination-keys">4 Dissemination Keys</a></h1>
-<p>One issue that comes up when using this interfaces is the selection of
-a key for each value. On one hand, using unique() is easy, but this
+<p>One issue that comes up when using these interfaces is the selection
+of a key for each value. On one hand, using unique() is easy, but this
means that the keyspaces for two different compilations of the same
program might be different and there's no way to support a network
-with more than one binary. On the other, having a component declare
-its own key internally means that you can run into key collisions that
-can't be resolved. In the middle, an application can select keys on
-behalf of other components.</p>
+with more than one binary. On the other hand, having a component
+declare its own key internally means that you can run into key
+collisions that can't be resolved. In the middle, an application can
+select keys on behalf of other components.</p>
<p>Ordinarily, dissemination keys can be generated by unique or selected
by hand. However, these defined keys can be overridden by an
application-specific header file. The unique namespace and the static
<h1><a id="more-complex-dissemination" name="more-complex-dissemination">5. More Complex Dissemination</a></h1>
<p>An application can use this low-level networking primitive to build
more complex dissemination systems. For example, if you want have a
-dissemination that only nodes which satisfy a predicate receive, you
-can do that by making the <t> a struct that stores a predicate and
-data value in it, and layering the predicate evaluation on top of the
-above interfaces.</p>
+dissemination that causes only nodes which satisfy a predicate to
+apply a change, you can do that by making the <t> a struct that stores
+a predicate and data value in it, and layering the predicate
+evaluation on top of the above interfaces.</p>
</div>
<div class="section">
<h1><a id="implementation" name="implementation">6. Implementation</a></h1>
-<p>An implementation of this TEP can be found in
-<tt class="docutils literal"><span class="pre">tinyos-2.x/tos/lib/net</span></tt>. This dissemination implementation uses
-network trickles <a class="footnote-reference" href="#id3" id="id1" name="id1">[2]</a>. Each dissemination value has a separate
-trickle.</p>
+<p>Two implementations of this TEP exist and can be found in
+<tt class="docutils literal"><span class="pre">tinyos-2.x/tos/lib/net</span></tt>. The first, Drip, can be found in
+''tinyos-2.x/tos/lib/net/drip''. The second, DIP, can be found in
+''tinyos-2.x/tos/lib/net/dip''. Both implementations are based on the
+Trickle algorithm[2]_. Drip is a simple, basic implementation that
+establishes an independent trickle for each variable. DIP uses a more
+complex approach involving hash trees, such that it is faster,
+especially when the dissemination service is maintaining many
+variables[3]_. This complexity, however, causes DIP to use more
+program memory.</p>
</div>
<div class="section">
<h1><a id="author-s-address" name="author-s-address">6. Author's Address</a></h1>
</div>
<div class="section">
<h1><a id="citations" name="citations">7. Citations</a></h1>
+<table class="docutils footnote" frame="void" id="id1" rules="none">
+<colgroup><col class="label" /><col /></colgroup>
+<tbody valign="top">
+<tr><td class="label"><a name="id1">[1]</a></td><td>TEP 111: message_t.</td></tr>
+</tbody>
+</table>
<table class="docutils footnote" frame="void" id="id2" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
-<tr><td class="label"><a name="id2">[1]</a></td><td>TEP 111: message_t.</td></tr>
+<tr><td class="label"><a name="id2">[2]</a></td><td>Philip Levis, Neil Patel, David Culler, and Scott Shenker. "Trickle: A Self-Regulating Algorithm for Code Maintenance and Propagation in Wireless Sensor Networks." In Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI 2004).</td></tr>
</tbody>
</table>
<table class="docutils footnote" frame="void" id="id3" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
-<tr><td class="label"><a class="fn-backref" href="#id1" name="id3">[2]</a></td><td>Philip Levis, Neil Patel, David Culler, and Scott Shenker. "Trickle: A Self-Regulating Algorithm for Code Maintenance and Propagation in Wireless Sensor Networks." In Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI 2004).</td></tr>
+<tr><td class="label"><a name="id3">[3]</a></td><td>Kaisen Lin and Philip Levis. "Data Discovery and Dissemination with DIP." In Proceedings of the Proceedings of the Seventh International Conference on Information Processing in Wireless Sensor Networks (IPSN), 2008.</td></tr>
</tbody>
</table>
</div>
-============================
-Dissemination
-============================
+================================
+Dissemination of Small Values
+================================
:TEP: 118
:Group: Net2 Working Group
The memo documents the interfaces, components, and semantics for
disseminating small (smaller than a single packet payload) pieces of
-data in TinyOS 2.x. Dissemination is reliably delivering a piece of
-data to every node in a network.
+data in TinyOS 2.x. Dissemination establishes eventual consistency
+across the entire network on a shared variable and tells an
+application when the variable changes. Common uses of this mechanism
+include network reconfiguration and reprogramming.
+
1. Introduction
====================================================================
-Dissemination is a a sensor network protocol that reliably delivers a
-piece of data to every node in the network. Dissemination can be used
-to reconfigure, query, and reprogram a network. Reliability is
-important because it makes the operation robust to temporary
-disconnections or high packet loss. Unlike flooding protocols, which
-are discrete efforts that terminate, possibly not delivering the data
-to some nodes, dissemination achieves reliability by using a
-continuous approach that can detect when a node is missing the data.
+Dissemination is a service for establishing eventual consistency on a
+shared variable. Every node in the network stores a copy of this
+variable. The dissemination service tells nodes when the value
+changes, and exchanges packets to it will reach eventual consistency
+across the network. At any given time, two nodes may disagree, but
+over time the number of disagreements will shrink and the network will
+converge on a single value.
+
+Eventual consistency is robust to temporary disconnections or high
+packet loss. Unlike flooding protocols, which are discrete efforts
+that terminate and not reach consistency, dissemination assures that
+the network will reach consensus on the value as long as it is not
+disconnected.
Depending on the size of the data item, dissemination protocols can
differ greatly: efficiently disseminating tens of kilobytes of a
similarities. Separating a dissemination protocol into two parts ---
control traffic and data traffic --- shows that while the data traffic
protocols are greatly dependent on the size of the data item, the
-control traffic tends to be the same or very similar.
-
-Being able to reliably disseminate small values into a network is a
-useful building block for sensornet applications. It allows an
-administrator to inject small programs or commands and configuration
-constants. Because TinyOS nodes have limited RAM, these dissemination
-services have the assumption that data values have some form of
-versioning. Dissemination propagates only the most recent version.
-This means that if a node is disconnected from a network and the
-network goes through eight versions of a disseminated value, when it
-rejoins the network it will only see the most recent. The rest of this
-document describes a set of components and interfaces for a
-dissemination service included in TinyOS 2.0.
+control traffic tends to be the same or very similar. For example, the
+Deluge binary reprogramming service, disseminates metadata about the
+binaries. When nodes learn the disseminated metadata differs from the
+metadata of their local binary, they know they either have a bad
+binary or need a new one.
+
+Novelty is an explicit consideration in dissemination's consistency
+model: it seeks to have every node agree on what the most recent
+version of the variable is. In this way, a node can prompt the network
+to reach consistency on a new value for a variable by telling the
+network it is newer. If several nodes all decide they need to update
+the variable, dissemination ensures that the network converges on a
+single value. Consistency does not mean that every node will see every
+possible value the variable takes: it only means that the network will
+eventually agree on what the newest is. This means that if a node is
+disconnected from a network and the network goes through eight
+versions of a disseminated value, when it rejoins the network it will
+only see the most recent.
+
+Being able to disseminate small values into a network is a useful
+building block for sensornet applications. It allows an administrator
+to inject small programs or commands and configuration constants. For
+example, installing a small program through the entire network can be
+cast as the problem of establishing consistency on a variable that
+contains the program.
+
+The rest of this document describes a set of components and interfaces
+for a dissemination service included in TinyOS 2.0. This service only
+handles small values that can fit in a single packet. Larger values
+would likely require different interfaces and abstractions.
2. Dissemination interfaces
====================================================================
interface DisseminationValue<t> {
command const t* get();
+ command void set(const t*);
event void changed();
}
}
-These interfaces assume that the allocation for the disseminated data
-is within the dissemination service. A consumer can obtain a const
-pointer to the data through DissemnationValue.get(). It MUST NOT
-store this pointer, as it may not be constant across updates.
-Additionally, doing so wastes RAM, as it can be easily re-obtained.
-The service signals a changed() event whenever the dissemination value
-changes, in case the consumer needs to perform some computation on it.
-
-DisseminationUpdate has a single command, ``change``, which takes a
+These interfaces assume that the dissemination service allocates space
+to store the variable. In that way, multiple components can all access
+and share the same variable that the dissemination service establishes
+consistency over. A consumer can obtain a const pointer to the data
+through DissemnationValue.get(). It MUST NOT store this pointer, as it
+may not be constant across updates. Additionally, doing so wastes
+RAM, as it can be easily re-obtained. The service signals a changed()
+event whenever the dissemination value changes, in case the consumer
+needs to perform some computation on it or take some action.
+
+DisseminationValue has a command, ''set'', which allows a node to
+change its local copy of a value without establishing consistency.
+This command exists so a node can establish an initial value for the
+variable. A node MUST NOT call ''set'' after it has handled a
+''changed'' event, or the network may become inconsistent. If a node
+has received an update or a client has called ''change'' then set MUST
+NOT apply its new value.
+
+DisseminationUpdate has a single command, ''change'', which takes a
pointer as an argument. This pointer is not stored: a provider of
DisseminationUpdate MUST copy the data into its own allocated memory.
+DisseminationValue MUST signal ''changed'' in response to a
+call to ''change''.
A dissemination protocol MUST reach consensus on the newest value in a
network (assuming the network is connected). Calling change
provides interface DisseminationUpdate <t>;
}
-The t argument MUST be able to fit in a single message_t [TEP111] after
-considering the headers that the dissemination protocol introduces.
-A dissemination implementation SHOULD have a compile error if a larger
-type than this is used.
+The t argument MUST be able to fit in a single message_t [TEP111]
+after considering the headers that the dissemination protocol
+introduces. A dissemination implementation SHOULD have a compile
+error if a larger type than this is used.
-As each instantiation of DisseminatorC probably allocates storage
-and generates code, if more than one component wants to share
-a disseminated value then they SHOULD encapsulate the value in
-a non-generic component that can be shared. E.g.::
+As each instantiation of DisseminatorC probably allocates storage and
+generates code, if more than one component wants to share a
+disseminated value then they SHOULD encapsulate the value in a
+non-generic component that can be shared. E.g.::
configuration DisseminateTxPowerC {
provides interface DisseminationValue<uint8_t>;
An application can use this low-level networking primitive to build
more complex dissemination systems. For example, if you want have a
-dissemination that only nodes which satisfy a predicate receive, you
-can do that by making the <t> a struct that stores a predicate and
-data value in it, and layering the predicate evaluation on top of the
-above interfaces.
+dissemination that causes only nodes which satisfy a predicate to
+apply a change, you can do that by making the <t> a struct that stores
+a predicate and data value in it, and layering the predicate
+evaluation on top of the above interfaces.
6. Implementation
====================================================================
-An implementation of this TEP can be found in
-``tinyos-2.x/tos/lib/net``. This dissemination implementation uses
-network trickles [2]_. Each dissemination value has a separate
-trickle.
+Two implementations of this TEP exist and can be found in
+``tinyos-2.x/tos/lib/net``. The first, Drip, can be found in
+''tinyos-2.x/tos/lib/net/drip''. The second, DIP, can be found in
+''tinyos-2.x/tos/lib/net/dip''. Both implementations are based on the
+Trickle algorithm[2]_. Drip is a simple, basic implementation that
+establishes an independent trickle for each variable. DIP uses a more
+complex approach involving hash trees, such that it is faster,
+especially when the dissemination service is maintaining many
+variables[3]_. This complexity, however, causes DIP to use more
+program memory.
+
6. Author's Address
====================================================================
.. [1] TEP 111: message_t.
.. [2] Philip Levis, Neil Patel, David Culler, and Scott Shenker. "Trickle: A Self-Regulating Algorithm for Code Maintenance and Propagation in Wireless Sensor Networks." In Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI 2004).
+
+.. [3] Kaisen Lin and Philip Levis. "Data Discovery and Dissemination with DIP." In Proceedings of the Proceedings of the Seventh International Conference on Information Processing in Wireless Sensor Networks (IPSN), 2008.
+
projects / tinyos-2.x.git / commitdiff