:TEP: 119
:Group: Net2 Working Group
:Type: Documentary
-:Status: Draft
-:TinyOS-Version: 2.x
+:Status: Final
+:TinyOS-Version: > 2.1
:Author: Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, and Philip Levis
:Draft-Created: 09-Feb-2006
====================================================================
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.
+the collection protocols in TinyOS 2.x. Collection provides
+best-effort, multihop delivery of packets to one of a set of
+collection points. There may be multiple collection points in a
+network, and in this case the semantics are *anycast* delivery to at
+least one of the collection points. A node sending a packet does not
+specify which of the collection points the packet is destined to. The
+union of the paths from each node to one or more of the collection
+points forms a set of trees, and in this document we assume that
+collection points are the roots of these trees.
+
1. Introduction
====================================================================
Collecting data at a base station is a common requirement of sensor
-network applications. The general approach used is to build one
-or more collection *trees*, each of which is rooted at a base
-station. When a node has data which needs to be collected, it
-sends the data up the tree, and it forwards collection data that
-other nodes send to it. Sometimes, depending on the form of data
-collection, systems need to be able to inspect packets as they go
-by, either to gather statistics, compute aggregates, or suppress
-redundant transmissions.
-
-When a network has multiple base stations that act as *root* nodes,
-rather than one tree, it has a *forest* of trees. By picking a
-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 *anycast* protocol.
-
-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
-collection protocols. Instead, they represent a subset of common
-networking algorithmic edge cases that occur in this protocol
-family:
-
- * Loop detection, detecting when a node selects one of its
- descendants as a new parent.
-
- * Duplicate suppression, detecting and dealing with when lost
- acknowledgments are causing packets to replicate in the
- network, wasting bandwidth.
+network applications. The general approach used is to build one or
+more collection trees, each of which is rooted at a base station. When
+a node has data which needs to be collected, it sends the data up the
+tree, and it forwards collection data that other nodes send to
+it. Sometimes, depending on the form of data collection, systems need
+to be able to inspect packets as they go by, either to gather
+statistics, compute aggregates, or suppress redundant transmissions.
+
+Collection provides best-effort, multihop delivery of packets to one
+of a network's tree roots: it is an *anycast* protocol. The
+semantics are that the protocol will make a reasonable effort to
+deliver the message to at least one of the roots in the network. By
+picking a parent node, a node implementing the collection protocol
+inductively joins the tree its parent has joined. Delivery is best
+effort, and there can be duplicates delivered to one or more roots.
+Collection provides no ordering or real-time guarantees, although
+specific implementations may extend the basic functionality to do
+so.
+
+Given the limited state that nodes can store and a general need for
+distributed tree building algorithms, collection protocols encounter
+several challenges. These challenges are not unique to collection
+protocols. Instead, they represent a subset of common networking
+algorithmic edge cases that generally occur in wireless routing:
+
+ * Loop detection, for when a node selects one of its descendants as
+ a next hop.
+
+ * Duplicate suppression, detecting and dealing with lost
+ acknowledgments that can cause packets to replicate in the
+ network, wasting capacity.
* Link estimation, evaluating the link quality to single-hop
neighbors.
* Self-interference, preventing forwarding packets along the route
from introducing interference for subsequent packets.
-The rest of this document describes a set of components and interfaces
-for a collection service outlined above.
+While collection protocols can take a wide range of approaches to
+address these challenges, the programming interface they provide is
+typically independent of these details. The rest of this document
+describes a set of components and interfaces for collection services.
2. Collection interfaces
====================================================================
-A node can perform four different roles in collection: producer,
-consumer, snooper, and in-network processor. Depending on their role,
-the nodes use different interfaces to interact with the collection
-component.
-
-The nodes that generate data to be sent to the root are
-*producers*. The producers use the Send interface [1_] to send
-data to the root of the collection tree. The collection tree
-identifier is be specified as a parameter to Send during
-instantiation.
-
-Root nodes that receive data from the network are *consumers*. The
-consumers use the Receive interface [1_] to receive a message
-delivered by collection. The collection tree identifier is be
-specified as a parameter to Receive during instantiation.
-
-The nodes that overhear messages in transit are *snoopers*. The snoopers
-use the Receive interface [1_] to receive a snooped message. The
-collection tree identifier is be specified as a parameter to Receive
-during instantiation.
-
-The nodes can process a packet that are in transit. These in-network
-*processors* use the Intercept interface [1_] to receive and
-update a packet. The collection tree identifier is be specified as a
-parameter to Intercept during instantiation.
-
-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::
+A node can perform four different roles in collection: sender (or
+source), snooper, in-network processor, and receiver (or
+root). Depending on their role, the nodes use different interfaces to
+interact with the collection component.
+
+The collection infrastructure can be multiplexed among independent
+applications, by means of a collection identifier. The collection
+identifier is used to identify different data traffic at the sender,
+intermediate-nodes, or the receiver, much like port number in TCP. All
+data traffic, regardless of the collection identifier, use the same
+routing topology.
+
+The nodes that generate data to be sent to the root are *senders*.
+Senders use the Send interface [1_] to send data to the root of
+the collection tree. The collection identifier is specified as a
+parameter to Send during instantiation.
+
+The nodes that overhear messages in transit are *snoopers*. The
+snoopers use the Receive interface [1_] to receive a snooped
+message. The collection identifier is specified as a parameter
+to Receive during instantiation.
+
+The nodes can process a packet that is in transit. These in-network
+*processors* 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::
+
+ interface Intercept {
+ event bool forward(message_t* msg, void* payload, uint8_t len);
+ }
+
+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. The Intercept interface allows a higher
+layer to inspect the internals of a packet and suppress it if needed.
+Intercept can be used for duplicate suppression, aggregation, and
+other higher-level services. As the handler of Intercept.forward()
+does not receive ownership of the packet, it MUST NOT modify the
+packet and MUST copy data out of the packet which it wishes to use
+after the event returns.
+
+Root nodes that receive data from the network are *receivers*. Roots
+use the Receive interface [1_] to receive a message delivered by
+collection. The collection identifier is specified as a parameter to
+Receive during instantiation.
+
+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, *i.e.*, all roots in this set active at the
+same time are part of the same infrastructure.
+
+The RootControl interface configures whether a node is a
+root::
interface RootControl {
command error_t setRoot();
command bool isRoot();
}
+The first two 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. If setRoot() returns SUCCESS, then a subsequent call
+to isRoot() MUST return TRUE. If unsetRoot() returns SUCCESS, then a
+subsequent call to isRoot() MUST return FALSE.
3 Collection Services
====================================================================
-A collection service MUST provide one component, TreeCollectionC,
+A collection service MUST provide one component, CollectionC,
which has the following signature::
- 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];
}
-TreeCollectionC 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.
+CollectionC MAY have additional interfaces. All outgoing invocations
+(commands for uses, events for provides) of those interfaces MUST have
+default functions. Those default functions enable CollectionC to
+operate properly even when the additional interfaces are not wired.
-Components SHOULD NOT wire to TreeCollectionC.Send. The generic
+Components SHOULD NOT wire to CollectionC.Send. The generic
component CollectionSenderC (described in section 3.1) provides
a virtualized sending interface.
protocol operating on top of collection, in the same way that
different am_id_t values represent different protocols operating on
top of active messages. All packets sent with a particular
-collection_id_t generally have the same payload format, so that
-snoopers, intercepters, and receivers can parse it properly.
-
-Receive.receive MUST NOT be signaled on non-root
-nodes. TreeCollectionC 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.
-Note that the buffer swapping semantics of Receive.receive, when
-combined with the pass semantics of Send, require that TreeCollectionC
-make a copy of the buffer if it signals Receive.receive.
-
-If TreeCollectionC receives a data packet to forward and it is not a
-root node, it MAY signal Intercept.forward.
-
-If TreeCollectionC receives a data packet that a different node
-is supposed to forward, it MAY signal Snoop.receive.
+collection_id_t generally SHOULD have the same payload format, so that
+snoopers, intercepters, and receivers can parse them properly.
+
+ColletionC MUST NOT signal Receive.receive on non-root
+nodes. CollectionC MUST signal Receive.receive on a root node when a
+unique (non-duplicate) data packet successfully arrives at that
+node. It MAY signal Receive.receive when a duplicate data packet
+successfully arrives. If a root node calls 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 CollectionC make a copy of the buffer
+if it signals Receive.receive.
+
+If CollectionC receives a data packet to forward and it is not a root
+node, it MAY signal Intercept.forward. CollectionC MAY signal
+Snoop.receive when it hears a packet which a different node is
+supposed to forward. For any given packet it receives, CollectionC
+MUST NOT signal more than one of the Snoop.receive, Receive.receive,
+and Intercept.forward events.
RootControl allows a node to be made a collection tree root.
-TreeCollectionC SHOULD NOT configure a node as a root by default.
+CollectionC SHOULD NOT configure a node as a root by default.
Packet and CollectionPacket allow components to access collection
data packet fields [1_].
-TreeRoutingInspect provides information on the current position of
-the node in a routing tree::
-
- interface TreeRoutingInspect {
- command error_t getParent(am_addr_t* parent);
- command error_t getHopcount(uint8_t* hopcount);
- command error_t getMetric(uint16_t* metric);
- }
-
-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.
-
3.1 CollectionSenderC
--------------------------------------------------------------------
AMSenderC [1_], 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
have a single packet format, so that receivers can parse a packet
-based on its collection ID and contents.
+based on its collection ID and contents.
-4 Implementation
+4. Implementation
====================================================================
-An implementation of this TEP can be found in
-``tinyos-2.x/tos/lib/net/collection``. The implementation consists of
-three major components, which are wired together to form a
-CollectionC: LinkEstimatorP, TreeRoutingEngineP, and ForwardingEngineP.
-
-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.
+Implementations of collection can be found in
+``tinyos-2.x/tos/lib/net/ctp`` and ``tinyos-2.x/tos/lib/net/lqi``.
+The former is the Collection Tree Protocol (CTP), described in TEP 123
+[2_]. The latter is a TinyOS 2.x port of MultihopLqi, a
+CC2420-specific collection protocol in TinyOS 1.x.
-4.1 LinkEstimatorP
---------------------------------------------------------------------
-
-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
-LinkEstimator.getQuality(), LinkEstimator.getforwardQuality(),
-LinkEstimator.getreserveQuality() 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
-[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::
-
- typedef uint16_t neighbor_t
-
- LinkEstimatorP {
- provides {
- interface LinkEstimator;
- interface NeighborTable;
- }
- }
-
- 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)
- }
-
-
-4.2 TreeRoutingEngineP
---------------------------------------------------------------------
-
-TreeRoutingEngineP is responsible for computing routes to the roots of a
-tree. It uses NeighborTable and LinkEstimator interfaces 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
-allows a node to be configured as a root or a non-root node
-dynamically. TreeRoutingEngineP maintains multiple candidate next hops::
-
- 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;
- }
- }
-
-4.3 ForwardingEngineP
---------------------------------------------------------------------
-
-The ForwardingEngineP component provides all the top level interfaces
-(except RootControl) which TreeCollectionC provides and an application
-uses::
-
- generic module ForwardingEngineP() {
- provides {
- interface Init;
- interface StdControl;
- interface Send[uint8_t client];
- interface Receive[collection_id_t id];
- interface Receive as Snoop[collection_id_t id];
- interface Intercept[collection_id_t id];
- interface Packet;
- interface CollectionPacket;
- }
- uses {
- 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 PacketAcknowledgements;
- interface Random;
- interface RootControl;
- interface CollectionId[uint8_t client];
- interface AMPacket;
- interface CollectionDebug;
- }
- }
-
-ForwardingEngineP uses a large number of interfaces, which can be
-broken up into a few groups of functionality:
-
- * Single hop communication: SubSend, SubReceive, SubSnoop,
- SubPacket, PacketAcknowledgments, AMPacket
- * Routing: UnicastNameFreeRouting, TreeRoutingInspect,
- RootControl, CollectionId, SentCache
- * Queue and buffer management: SendQueue, MessagePool,
- QEntryPool
- * Packet timing: Random, RetxmitTimer
-
-
-5. Author's Address
+5. Author Addresses
====================================================================
| Rodrigo Fonseca
6. Citations
====================================================================
-.. [1] TEP 116: Packet Protocols
-
+.. [1] TEP 116: Packet Protocols.
+
+.. [2] TEP 123: The Collection Tree Protocol (CTP).
+
projects / tinyos-2.x.git / blobdiff