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.
+multihop delivery of packets to the root of a tree. There may be
+multiple tree roots in a network, and in this case the semantics
+are *anycast* delivery to at least one of the roots. A node sending
+a packet does not specify which root the packet is destined to.
+
1. Introduction
====================================================================
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.
+it is an *anycast* 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.
Given the limited state that nodes can store and a general need
for distributed tree building algorithms, simple collection protocols
* 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,
+snooper, in-network processor, and consumer. Depending on their role,
the nodes use different interfaces to interact with the collection
-component.
+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.
+The collection infrastructure can be multiplexed among independent
+applications, by means of a *collection identifier*. It is important
+to note that the *data* traffic in the protocol is multiplexed,
+while the *control* traffic is not.
-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 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 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 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 identifier is 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.
+*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::
-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::
+ 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. 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.
+
+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 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();
}
+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. 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. These additional
+interfaces 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.
-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.
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
+ColletionC MUST NOT signal Receive.receive on non-root
+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.
-If TreeCollectionC receives a data packet to forward and it is not a
+If CollectionC 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
+If CollectionC receives a data packet that a different node
is supposed to forward, it MAY signal Snoop.receive.
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
--------------------------------------------------------------------
Collection has a virtualized sending abstraction, the generic
component CollectionSenderC::
-generic configuration CollectionSenderC(collection_id_t collectid) {
- provides {
- interface Send;
- interface Packet;
+ generic configuration CollectionSenderC(collection_id_t collectid) {
+ provides {
+ interface Send;
+ interface Packet;
+ }
}
-}
This abstraction follows a similar virtualization approach to
AMSenderC [1_], except that it is parameterized by a collection_id_t
====================================================================
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.
+``tinyos-2.x/tos/lib/net/ctp`` and ``tinyos-2.x/tos/lib/net/4bitle``, 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 [2_]. 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, CtpRoutingEngineP, and
+CtpForwardingEngineP.
+
+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.
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
+neighbor. In this TEP, we briefly describe the reference
+implementation in ''tinyos-2.x/tos/lib/4bitle'' and refer the readers
+to [3]_ for a detailed description of the estimator.
+
+Link estimation is decoupled from the establishment of routes. There
+is a narrow interface -- LinkEstimator and CompareBit -- between the
+link estimator and the routing engine. A smaller return value from
+LinkEstimator.getLinkQuality() implies that the link to the neighbor
+is estimated to be of a higher quality than the one that results in a
+larger return value. 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
+returns (ETX-1)*10 as the link quality. The routing engine instructs
+LinkEstimatorP to insert the neighbor, through which a high quality
+path to the root can be constructed, into the neighbor table by
+returning TRUE when LinkEstimatorP signals Comparebit.shouldInsert()
+for the newly discovered neighbor.
+
+LinkEstimatorP does not generate its own control messages to compute
+link qualities. When a user of LinkEstimatorP (CtpRoutingEngineP, for
+example) sends a packet using the Send interface provided by
+LinkEstimatorP, link estimation information is also sent with the
+packet as described in an upcoming TEP [4_]. LinkEstimatorP provides
+calls (txAck(), txNoAck(), and clearDLQ()) to update the link
+estimates based on successful or unsuccessful data transmission to the
+neighbors. LinkEstimatorP uses the LinkPacketMetadata interface to
+determine if the channel was of high quality when a packet is received
+from a neighbor to consider the link to that neighbor for insertion
+into the neighbor table.
+
+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::
+
+ 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 CompareBit;
+ }
+ uses {
+ interface AMSend;
+ interface AMPacket as SubAMPacket;
+ interface Packet as SubPacket;
+ interface Receive as SubReceive;
+ interface LinkPacketMetadata;
+ interface Random;
}
}
- interface LinkEstimator {
- command uint8_t getLinkQuality(neighbot_t neighbor);
- command uint8_t getReverseQuality(neighbot_t neighbor);
- command uint8_t getForwardQuality(neighbot_t neighbor);
+ interface CompareBit {
+ event bool shouldInsert(message_t *msg, void* payload, uint8_t len, bool white_bit);
}
- interface NeighborTable {
- event void evicted(neighbot_t neighbor)
+ interface LinkEstimator {
+ command uint16_t getLinkQuality(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);
}
-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::
+4.2 CtpRoutingEngineP
+--------------------------------------------------------------------
- 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;
- }
+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 CtpForwardingEngineP.
+The main interface between the two is UnicastNameFreeRouting.
+
+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 computes a routing tree with a single
+or multiple roots. CtpRoutingEngineP allows a node to be configured as
+a root or a non-root node dynamically. CtpRoutingEngineP maintains
+multiple candidate next hops::
+
+ 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 SplitControl as RadioControl;
+ interface Timer<TMilli> as BeaconTimer;
+ interface Timer<TMilli> as RouteTimer;
+ interface Random;
+ interface CollectionDebug;
+ interface CtpCongestion;
+ interface Comparebit;
+ }
}
-4.3 ForwardingEngineP
+
+::
+
+ interface UnicastNameFreeRouting {
+ command am_addr_t nextHop();
+
+ command bool hasRoute();
+ event void routeFound();
+ event void noRoute();
+ }
+
+
+
+4.3 CtpForwardingEngineP
--------------------------------------------------------------------
-The ForwardingEngineP component provides all the top level interfaces
-(except RootControl) which TreeCollectionC provides and an application
-uses::
+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.::
- 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;
}
}
-ForwardingEngineP uses a large number of interfaces, which can be
+
+CtpForwardingEngineP 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
+ * Routing: UnicastNameFreeRouting, RootControl, CtpInfo,
+ CollectionId, SentCache
* Queue and buffer management: SendQueue, MessagePool,
QEntryPool
* Packet timing: Random, RetxmitTimer
+4.4 MultihopLqi
+====================================================================
+
+There is another implementation of collection in ``tos/lib/net/lqi``.
+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.
+
-5. Author's Address
+5. Author Addresses
====================================================================
| Rodrigo Fonseca
====================================================================
.. [1] TEP 116: Packet Protocols
-
+
+.. [2] TEP 123: The Collection Tree Protocol (CTP)
+
+.. [3] Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, and Philip Levis. "Four Bit Wireless Link Estimation." In Proceedings of the Sixth Workshop on Hot Topics in Networks (HotNets VI), November 2007
+
+.. [4] TEP 124: The Link Estimation Exchange Protocol (LEEP)
projects / tinyos-2.x.git / blobdiff