dd {
margin-bottom: 0.5em }
-/* Uncomment (& remove this text!) to get bold-faced definition list terms
-dt {
- font-weight: bold }
-*/
-
div.abstract {
margin: 2em 5em }
<h1><a id="abstract" name="abstract">Abstract</a></h1>
<p>The memo documents the interfaces, components, and semantics used by
collection protocol in TinyOS 2.x. Collection provides a best-effort,
-multihop delivery of packets to the root of a tree.</p>
+multihop delivery of packets to the root of <em>a</em> tree. There may be
+multiple roots in a network, and in this case the semantics implemented
+are of <em>anycast</em> delivery to at least one of the roots. A node sending
+a packet does not specify which root the packet is destined to.</p>
</div>
<div class="section">
<h1><a id="introduction" name="introduction">1. Introduction</a></h1>
parent node, a collection protocol implicitly joins one of these
trees. Collection provides a best-effort,
multihop delivery of packets to one of a network's tree roots:
-it is an <em>anycast</em> protocol.</p>
+it is an <em>anycast</em> protocol. The semantics is that the protocol
+will make a reasonable effort to deliver the message to at least
+one of the roots in the network. There are however no guarantees of
+delivery, and there can be duplicates delivered to one or more
+roots. There is also no ordering guarantees.</p>
<p>Given the limited state that nodes can store and a general need
for distributed tree building algorithms, simple collection protocols
encounter several challenges. These challenges are not unique to
consumer, snooper, and in-network processor. Depending on their role,
the nodes use different interfaces to interact with the collection
component.</p>
-<p>The nodes that generate data to be sent to the root are
-<em>producers</em>. The producers use the Send interface [<a class="reference" href="#id1">1</a>] to send
-data to the root of the collection tree. The collection tree
-identifier is be specified as a parameter to Send during
-instantiation.</p>
-<p>Root nodes that receive data from the network are <em>consumers</em>. The
-consumers use the Receive interface [<a class="reference" href="#id1">1</a>] to receive a message
-delivered by collection. The collection tree identifier is be
-specified as a parameter to Receive during instantiation.</p>
-<p>The nodes that overhear messages in transit are <em>snoopers</em>. The snoopers
-use the Receive interface [<a class="reference" href="#id1">1</a>] to receive a snooped message. The
-collection tree identifier is be specified as a parameter to Receive
-during instantiation.</p>
-<p>The nodes can process a packet that are in transit. These in-network
-<em>processors</em> use the Intercept interface [<a class="reference" href="#id1">1</a>] to receive and
-update a packet. The collection tree identifier is be specified as a
-parameter to Intercept during instantiation.</p>
+<p>A consumer is a root of a tree. The set of all roots and the paths that
+lead to them form the collection routing infrastructure in the network.
+For any connected set of nodes implementing the collection protocol
+there is only one collection infrastructure, <em>i.e.</em>, all roots in this
+set active at the same time are part of the same infrastructure.</p>
<p>A node is configured to become a root by using the RootControl
interface. RootControl.setRoot() MUST make the current node a root of
-the tree specified during instantiation. RootControl.unsetRoot() MUST
-make the current root no longer a root in the tree specified during
-instantiation. RootControl.unsetRoot() MAY be called on a node that is
-not a root:</p>
+the collection infrastructure. RootControl.unsetRoot() MUST make
+the current root no longer a root in the collection infrastructure.
+Both calls are idempotent. RootControl.setRoot() MAY be called on a
+node that is already a root, to no effect. RootControl.unsetRoot() MAY
+be called on a node that is not a root:</p>
<pre class="literal-block">
interface RootControl {
command error_t setRoot();
command bool isRoot();
}
</pre>
+<p>Both commands MUST return SUCCESS if the node is now in the specified
+state, and FAIL otherwise. For example, if a node is already a root
+and an application calls RootControl.setRoot(), the call will
+return SUCCESS.</p>
+<p>The collection infrastructure can be multiplexed among independent
+applications, by means of a <em>collection identifier</em>. It is important
+to note that the <em>data</em> traffic in the protocol is multiplexed,
+while the <em>control</em> traffic is not.</p>
+<p>The nodes that generate data to be sent to the root are <em>producers</em>.
+The producers use the Send interface [<a class="reference" href="#id1">1</a>] to send data to the root
+of the collection tree. The collection identifier is specified as a
+parameter to Send during instantiation.</p>
+<p>Root nodes that receive data from the network are <em>consumers</em>. The
+consumers use the Receive interface [<a class="reference" href="#id1">1</a>] to receive a message
+delivered by collection. The collection identifier is specified
+as a parameter to Receive during instantiation.</p>
+<p>The nodes that overhear messages in transit are <em>snoopers</em>. The
+snoopers use the Receive interface [<a class="reference" href="#id1">1</a>] to receive a snooped
+message. The collection identifier is specified as a parameter
+to Receive during instantiation.</p>
+<p>The nodes can process a packet that are in transit. These in-network
+<em>processors</em> use the Intercept interface to receive
+and update a packet. The collection identifier is specified as a parameter
+to Intercept during instantiation. The Intercept interface has this
+signature:</p>
+<pre class="literal-block">
+interface Intercept {
+ event bool forward(message_t* msg, void* payload, uint8_t len);
+}
+</pre>
+<p>Intercept has a single event, Intercept.forward(). A collection
+service SHOULD signal this event when it receives a packet to forward.
+If the return value of the event is FALSE, then the collection layer
+MUST NOT forward the packet. This interface allows a higher layer
+to inspect the internals of a packet and possibly suppress it if
+it is unnecessary or if its contents can be aggregated into an
+existing packet.</p>
</div>
<div class="section">
<h1><a id="collection-services" name="collection-services">3 Collection Services</a></h1>
-<p>A collection service MUST provide one component, TreeCollectionC,
+<p>A collection service MUST provide one component, CollectionC,
which has the following signature:</p>
<pre class="literal-block">
-configuration TreeCollectionC {
+configuration CollectionC {
provides {
interface StdControl;
interface Send[uint8_t client];
interface RootControl;
interface Packet;
interface CollectionPacket;
- interface TreeRoutingInspect;
}
uses {
interface CollectionId[uint8_t client];
}
}
</pre>
-<p>TreeCollectionC MAY have additional interfaces, but they MUST have
+<p>CollectionC MAY have additional interfaces, but they MUST have
default functions on all outgoing invocations (commands for uses,
events for provides) of those interfaces so that it can operate
properly if they are not wired.</p>
-<p>Components SHOULD NOT wire to TreeCollectionC.Send. The generic
+<p>Components SHOULD NOT wire to CollectionC.Send. The generic
component CollectionSenderC (described in section 3.1) provides
a virtualized sending interface.</p>
<p>Receive, Snoop, and Intercept are all parameterized by
collection_id_t generally have the same payload format, so that
snoopers, intercepters, and receivers can parse it properly.</p>
<p>Receive.receive MUST NOT be signaled on non-root
-nodes. TreeCollectionC MAY signal Receive.receive on a root node when
+nodes. CollectionC MAY signal Receive.receive on a root node when
a data packet successfully arrives at that node. If a root node calls
-Send, TreeCollectionC MUST treat it as it if were a received packet.
+Send, CollectionC MUST treat it as it if were a received packet.
Note that the buffer swapping semantics of Receive.receive, when
-combined with the pass semantics of Send, require that TreeCollectionC
+combined with the pass semantics of Send, require that CollectionC
make a copy of the buffer if it signals Receive.receive.</p>
-<p>If TreeCollectionC receives a data packet to forward and it is not a
+<p>If CollectionC receives a data packet to forward and it is not a
root node, it MAY signal Intercept.forward.</p>
-<p>If TreeCollectionC receives a data packet that a different node
+<p>If CollectionC receives a data packet that a different node
is supposed to forward, it MAY signal Snoop.receive.</p>
<p>RootControl allows a node to be made a collection tree root.
-TreeCollectionC SHOULD NOT configure a node as a root by default.</p>
+CollectionC SHOULD NOT configure a node as a root by default.</p>
<p>Packet and CollectionPacket allow components to access collection
data packet fields [<a class="reference" href="#id1">1</a>].</p>
-<p>TreeRoutingInspect provides information on the current position of
-the node in a routing tree:</p>
-<pre class="literal-block">
-interface TreeRoutingInspect {
- command error_t getParent(am_addr_t* parent);
- command error_t getHopcount(uint8_t* hopcount);
- command error_t getMetric(uint16_t* metric);
-}
-</pre>
-<p>In each of these commands, if the return value is not SUCCESS, the
-value stored in the pointer argument is undefined. The getMetric
-command provides a measure of the quality of a node's route to the
-base station. This routing metric MUST be monotonically increasing
-across hops. In a collection tree, if node A is the parent of node B,
-then node B's metric value MUST be greater than node A's.</p>
<div class="section">
<h2><a id="collectionsenderc" name="collectionsenderc">3.1 CollectionSenderC</a></h2>
<p>Collection has a virtualized sending abstraction, the generic
component CollectionSenderC:</p>
-<div class="system-message">
-<p class="system-message-title">System Message: WARNING/2 (<tt class="docutils">txt/tep119.txt</tt>, line 198)</p>
-Literal block expected; none found.</div>
-<dl class="docutils">
-<dt>generic configuration CollectionSenderC(collection_id_t collectid) {</dt>
-<dd><dl class="first docutils">
-<dt>provides {</dt>
-<dd>interface Send;
-interface Packet;</dd>
-</dl>
-<div class="system-message">
-<p class="system-message-title">System Message: WARNING/2 (<tt class="docutils">txt/tep119.txt</tt>, line 202)</p>
-Definition list ends without a blank line; unexpected unindent.</div>
-<p class="last">}</p>
-</dd>
-</dl>
-<div class="system-message">
-<p class="system-message-title">System Message: WARNING/2 (<tt class="docutils">txt/tep119.txt</tt>, line 203)</p>
-Definition list ends without a blank line; unexpected unindent.</div>
-<p>}</p>
+<pre class="literal-block">
+generic configuration CollectionSenderC(collection_id_t collectid) {
+ provides {
+ interface Send;
+ interface Packet;
+ }
+}
+</pre>
<p>This abstraction follows a similar virtualization approach to
AMSenderC [<a class="reference" href="#id1">1</a>], except that it is parameterized by a collection_id_t
rather than an am_id_t. As with am_id_t, every collection_id_t SHOULD
<div class="section">
<h1><a id="implementation" name="implementation">4 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/collection</span></tt>. The implementation consists of
-three major components, which are wired together to form a
-CollectionC: LinkEstimatorP, TreeRoutingEngineP, and ForwardingEngineP.</p>
-<p>This decomposition tries to encourage evolution of components and ease
-of use through modularization. Neighbor management and link estimation
-are are decoupled from the routing protocol. Furthermore, the routing
-protocol and route selection are decoupled from the forwarding policies,
-such as queueing and timing.</p>
+<tt class="docutils literal"><span class="pre">tinyos-2.x/tos/lib/net/ctp</span></tt> and <tt class="docutils literal"><span class="pre">tinyos-2.x/tos/lib/net/4bitle</span></tt>, in
+the CTP protocol. It is beyond the scope of this document to fully
+describe CTP, but we outline its main components. CTP will be
+described in an upcoming TEP [<a class="reference" href="#id2">2</a>]. This implementation is a
+reference implementation, and is not the only possibility. It
+consists of three major components, which are wired together to form
+a CollectionC: LinkEstimatorP, CtpTreeRoutingEngineP, and
+CtpForwardingEngineP.</p>
+<p>This decomposition tries to encourage evolution of components and
+ease of use through modularization. Neighbor management and link
+estimation are decoupled from the routing protocol. Furthermore, the
+routing protocol and route selection are decoupled from the
+forwarding policies, such as queueing and timing.</p>
<div class="section">
<h2><a id="linkestimatorp" name="linkestimatorp">4.1 LinkEstimatorP</a></h2>
<p>LinkEstimatorP estimates the quality of link to or from each
-neighbor. Link estimation can be done in a variety of ways, and we do
-not impose one here. It is decoupled from the establishment of
-routes. There is a narrow interface (LinkEstimator) between the link
-estimator and the routing engine. The one requirement is that the
-quality returned is standardized. A larger return value from
+neighbor. Link estimation can be done in a variety of ways, and we
+do not impose one here. It is decoupled from the establishment of
+routes. There is a narrow interface -- LinkEstimator -- between the
+link estimator and the routing engine. The one requirement is that
+the quality returned is standardized. A smaller return value from
LinkEstimator.getQuality(), LinkEstimator.getforwardQuality(),
-LinkEstimator.getreserveQuality() MUST imply that the link to the
+LinkEstimator.getReverseQuality() MUST imply that the link to the
neighbor is estimated to be of a higher quality than the one that
-results in a smaller return value. The range of value SHOULD be
+results in a larger return value. The range of value SHOULD be
[0,255] and the variation in link quality in that range SHOULD be
linear. Radio provided values such as LQI or RSI, beacon based link
estimation to compute ETX, or their combination are some possible
-approaches to estimating link qualities. LinkEstimatorP MAY have its
-own control messages to compute bi-directional link qualities:</p>
+approaches to estimating link qualities.</p>
+<p>LinkEstimatorP MAY have its own control messages to compute
+bi-directional link qualities. LinkEstimatorP provides calls
+(txAck(), txNoAck(), and clearDLQ()) to update the link estimates
+based on successful or unsuccessful data transmission to the
+neighbors.</p>
+<p>The user of LinkEstimatorP can call insertNeighbor() to manually
+insert a node in the neighbor table, pinNeighbor() to prevent a
+neighbor from being evicted, and unpinNeighbor() to restore eviction
+policy:</p>
<pre class="literal-block">
-typedef uint16_t neighbor_t
+typedef uint16_t neighbor_table_entry_t
LinkEstimatorP {
provides {
+ interface StdControl;
+ interface AMSend as Send;
+ interface Receive;
interface LinkEstimator;
- interface NeighborTable;
+ interface Init;
+ interface Packet;
+ interface LinkSrcPacket;
}
}
interface LinkEstimator {
- command uint8_t getLinkQuality(neighbot_t neighbor);
- command uint8_t getReverseQuality(neighbot_t neighbor);
- command uint8_t getForwardQuality(neighbot_t neighbor);
-}
-
-interface NeighborTable {
- event void evicted(neighbot_t neighbor)
+ command uint8_t getLinkQuality(uint16_t neighbor);
+ command uint8_t getReverseQuality(uint16_t neighbor);
+ command uint8_t getForwardQuality(uint16_t neighbor);
+ command error_t insertNeighbor(am_addr_t neighbor);
+ command error_t pinNeighbor(am_addr_t neighbor);
+ command error_t unpinNeighbor(am_addr_t neighbor);
+ command error_t txAck(am_addr_t neighbor);
+ command error_t txNoAck(am_addr_t neighbor);
+ command error_t clearDLQ(am_addr_t neighbor);
+ event void evicted(am_addr_t neighbor);
}
</pre>
</div>
<div class="section">
-<h2><a id="treeroutingenginep" name="treeroutingenginep">4.2 TreeRoutingEngineP</a></h2>
-<p>TreeRoutingEngineP is responsible for computing routes to the roots of a
-tree. It uses NeighborTable and LinkEstimator interfaces to learn
+<h2><a id="ctproutingenginep" name="ctproutingenginep">4.2 CtpRoutingEngineP</a></h2>
+<p>CtpRoutingEngineP is responsible for computing routes to the roots of a
+tree. In traditional networking terminology, this is part of the
+control plane of the network, and is does not directly forward any
+data packets, which is the responsibility of CtpForwardingEngine.
+The main interface between the two is UnicastNameFreeRouting.</p>
+<p>CtpRoutingEngineP uses the LinkEstimator interface to learn
about the nodes in the neighbor table maintained by LinkEstimatorP and
the quality of links to and from the neighbors. The routing protocol
on which collection is implemented MUST be a tree-based routing
-protocol with a single or multiple roots. TreeRoutingEngineP
+protocol with a single or multiple roots. CtpRoutingEngineP
allows a node to be configured as a root or a non-root node
-dynamically. TreeRoutingEngineP maintains multiple candidate next hops:</p>
+dynamically. CtpRoutingEngineP maintains multiple candidate next hops:</p>
<pre class="literal-block">
-generic module TreeRoutingEngineP(uint8_t routingTableSize) {
- provides {
- interface UnicastNameFreeRouting as Routing;
- interface RootControl;
- interface TreeRoutingInspect;
- interface StdControl;
- interface Init;
- }
- uses {
- interface AMSend as BeaconSend;
- interface Receive as BeaconReceive;
- interface LinkEstimator;
- interface AMPacket;
- interface LinkSrcPacket;
- interface SplitControl as RadioControl;
- interface Timer<TMilli> as BeaconTimer;
- interface Random;
- interface CollectionDebug;
- }
+generic module CtpRoutingEngineP(uint8_t routingTableSize,
+ uint16_t minInterval,
+ uint16_t maxInterval) {
+ provides {
+ interface UnicastNameFreeRouting as Routing;
+ interface RootControl;
+ interface CtpInfo;
+ interface StdControl;
+ interface CtpRoutingPacket;
+ interface Init;
+ }
+ uses {
+ interface AMSend as BeaconSend;
+ interface Receive as BeaconReceive;
+ interface LinkEstimator;
+ interface AMPacket;
+ interface LinkSrcPacket;
+ interface SplitControl as RadioControl;
+ interface Timer<TMilli> as BeaconTimer;
+ interface Timer<TMilli> as RouteTimer;
+ interface Random;
+ interface CollectionDebug;
+ interface CtpCongestion;
+ }
+}
+</pre>
+<pre class="literal-block">
+interface UnicastNameFreeRouting {
+ command am_addr_t nextHop();
+
+ command bool hasRoute();
+ event void routeFound();
+ event void noRoute();
}
</pre>
</div>
<div class="section">
-<h2><a id="forwardingenginep" name="forwardingenginep">4.3 ForwardingEngineP</a></h2>
-<p>The ForwardingEngineP component provides all the top level interfaces
-(except RootControl) which TreeCollectionC provides and an application
-uses:</p>
+<h2><a id="ctpforwardingenginep" name="ctpforwardingenginep">4.3 CtpForwardingEngineP</a></h2>
+<p>The CtpForwardingEngineP component provides all the top level interfaces
+(except RootControl) which CollectionC provides and an application
+uses. It deals with retransmissions, duplicate suppression, packet
+timing, loop detection, and also informs the LinkEstimator of the
+outcome of attempted transmissions.:</p>
<pre class="literal-block">
-generic module ForwardingEngineP() {
+generic module CtpForwardingEngineP() {
provides {
interface Init;
interface StdControl;
interface Intercept[collection_id_t id];
interface Packet;
interface CollectionPacket;
+ interface CtpPacket;
+ interface CtpCongestion;
}
uses {
+ interface SplitControl as RadioControl;
interface AMSend as SubSend;
interface Receive as SubReceive;
interface Receive as SubSnoop;
interface Packet as SubPacket;
interface UnicastNameFreeRouting;
- interface SplitControl as RadioControl;
interface Queue<fe_queue_entry_t*> as SendQueue;
interface Pool<fe_queue_entry_t> as QEntryPool;
interface Pool<message_t> as MessagePool;
interface Timer<TMilli> as RetxmitTimer;
- interface Cache<uint32_t> as SentCache;
- interface TreeRoutingInspect;
+ interface LinkEstimator;
+ interface Timer<TMilli> as CongestionTimer;
+ interface Cache<message_t*> as SentCache;
+ interface CtpInfo;
interface PacketAcknowledgements;
interface Random;
interface RootControl;
}
}
</pre>
-<p>ForwardingEngineP uses a large number of interfaces, which can be
+<p>CtpForwardingEngineP uses a large number of interfaces, which can be
broken up into a few groups of functionality:</p>
<blockquote>
<ul class="simple">
<li>Single hop communication: SubSend, SubReceive, SubSnoop,
SubPacket, PacketAcknowledgments, AMPacket</li>
-<li>Routing: UnicastNameFreeRouting, TreeRoutingInspect,
-RootControl, CollectionId, SentCache</li>
+<li>Routing: UnicastNameFreeRouting, RootControl, CtpInfo,
+CollectionId, SentCache</li>
<li>Queue and buffer management: SendQueue, MessagePool,
QEntryPool</li>
<li>Packet timing: Random, RetxmitTimer</li>
</div>
</div>
<div class="section">
-<h1><a id="author-s-address" name="author-s-address">5. Author's Address</a></h1>
+<h1><a id="multihoplqi" name="multihoplqi">4.4 MultihopLqi</a></h1>
+<p>There is another implementation of collection in <tt class="docutils literal"><span class="pre">tos/lib/net/lqi</span></tt>.
+Its software structure is similar, with the exception that it does
+not have a separate link estimator. MultihopLqi only works on
+platforms that have a CC2420 radio, as it uses a special piece
+of physical layer data the radio provides (the LQI value).
+The three major components of the MultihopLqi implementation
+are the modules LqiForwardingEngineP and LqiRoutingEngineP, as
+well as the configuration MultihopLqiP.</p>
+</div>
+<div class="section">
+<h1><a id="author-addresses" name="author-addresses">5. Author Addresses</a></h1>
<div class="line-block">
<div class="line">Rodrigo Fonseca</div>
<div class="line">473 Soda Hall</div>
<tr><td class="label"><a name="id1">[1]</a></td><td>TEP 116: Packet Protocols</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">[2]</a></td><td>TEP 123: The Collection Tree Protocol (CTP)</td></tr>
+</tbody>
+</table>
</div>
</div>
</body>
projects / tinyos-2.x.git / blobdiff