[net2-wg] Collection TEP draft

Thu Feb 9 08:41:34 PST 2006

One more question I forgot to ask. How should we allocate or assign the AM
id's? Should there be global allocation? If not, perhaps we should not
use AM id's in the internal components -- users might not know what id's
are being used internally. For example, how will a user know not to use
the id's used by collection control and data packets?

On Thu, 9 Feb 2006, Omprakash Gnawali wrote:

>
> Phil:
>
> 1. Should the interfaces Snoop and Intercept be defined in TEP 116 ? I
> saw some variations of Snoop as components but not as interfaces in
> that TEP. For collection, we might want interfaces because
> applications need to know what type of packet it is. Or would you
> rather have Receive interface be provided as Snoop ? We might still
> need to do something different for Intercept. For now, I am assuming
> that these interfaces are defined in TEP 116.
>
> 2. TEP 117 seems taken. Hence the number "xyz" below.
>
> 3. Do we have/need access to the docs directory ?
>
> Rodrigo:
>
> I tried to make the router a bit more generic than our original
> plans. We can make changes if you want the router to be a bit more
> specific to the implementation we had in mind.
>
> Everybody else, please send your comments.
>
>
> ============================
> Collection
> ============================
>
> :TEP: xyz
> :Group: Net2 Working Group
> :Type: Documentary
> :Status: Draft
> :TinyOS-Version: 2.x
> :Author: Rodrigo Fonseca, Omprakash Gnawali, and Kyle Jamieson
>
> :Draft-Created: 09-Feb-2006
> :Draft-Discuss: TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu>
>
> .. Note::
>
>    This memo documents a part of TinyOS for the TinyOS Community, and
>    requests discussion and suggestions for improvements.  Distribution
>    of this memo is unlimited. This memo is in full compliance with
>    TEP 1.
>
> Abstract
> ====================================================================
>
> 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 specified tree.
>
> 1. Introduction
> ====================================================================
>
> One of the most common functions that a sensor network performs is
> collection of data from the network to a base station. Upon generating
> data, either by sensing or other means, a node uses the collection
> protocol to send the data to a base station. The data is forwarded by
> the nodes between the sender and the base station towards the base
> station. Processing, visualization, and archival of data is done at
> the base station.
>
> Often there MAY be multiple such base stations or gateway nodes
> (referred to as roots in the rest of the document) in a collection
> tree that spans a network. Furthermore, there can be multiple trees in
> a single network as a result of running different protocols; each
> protocol building its own tree. Collection provides a best-effort,
> multihop delivery of packets to the root of a specified tree. In
> addition, collection provides mechanism to intercept packets for
> in-network processing and snoop the packets in transit.
>
> The proposed collection protocol uses two principals to encourage
> evolution of components and ease of use: modularization and tree-based
> naming. The neighbor management and link estimation are are decoupled
> from the routing protocol. So are routing protocol and the forwarding
> element. This modularization allows these components to evolve
> independently while maximizing reuse of existing components. Using
> tree based naming lesses the burden on applications while determining
> the end point of collection. The discovery and selection of root is
> performed internally by collection.
>
> Different applications desire different properties in a collection
> protocol. Some applications might have ADUs larger than the ones that
> are directly accomodated by the collection interface. Some
> applications might require reliable delivery of data. While collection
> does not address these and many other specific needs of an
> application, it provides interfaces and components on top of which
> these services can be built.
>
> The rest of this document describes a set of components and interfaces
> for a collection service outlined above.
>
> 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[_tep116] 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[_tep116] 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 Snoop interface[_tep116] to receive a snooped
> message. The collection tree identifier is be specified as a
> parameter to Snoop during instantiation.
>
> The nodes can process a packet that are in transit. These in-network
> processors use the Intercept interface [_tep116] 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.
>
> interface RootControl {
> 	command error_t setRoot();
> 	command error_t unsetRoot();
> 	command bool isRoot();
> }
>
>
> 3 Collection Service
> ====================================================================
>
> A collection service MUST provide one component, CollectionC,
> which has the following signature::
>
> generic configuration CollectionC {
> 	provides {
> 		interface Send[uint8_t tree_id]
> 		interface Receive[uint8_t tree_id];
> 		interface Intercept[uint8_t tree_id];
> 		interface Snoop[uint8_t tree_id];
> 		interface Packet;
> 		interface RootControl[uint8_t tree_id];
> 	}
> }
>
> CollectionC.Receive.receive is signalled at the root when a collection
> packet matching the tree_id arrives at a node. CollectionC.Send.send
> returns EBUSY only if there is a send request outstanding on this
> CollectionC. CollectionC.Intercept.receive is signalled when a
> collection packet is received with destination the address matching
> the local address node. CollectionC.Snoop.snoop is signalled when a
> collection packet matching the tree_id is received.
>
> RootControl.setRoot() is called to make a node into a root of the
> collection tree. CollectionC SHOULD NOT configure a node as a root by
> default.
>
> 4 Collection Components
> ====================================================================
>
> Collection consists of three components: LinkEstimatorP,
> MTreeRoutingTreeP, and ForwardingEngineP.
>
>
> 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 MTreeRoutingTreeP
> --------------------------------------------------------------------
>
> LinkEstimatorP 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. MTreeRoutingTreeP SHOULD
> allow a node to be configured as a root or a non-root node
> dynamically. MTreeRoutingTreeP MAY maintain multiple next hops to a
> root.
>
> MTreeRoutingEngineP
> 	provides {
> 		interface REControl[uint8_t tree_id];
> 		interface RootControl[uint8_t tree_id];
> 		interface Routing[uint8_t tree_id];
> 	}
> 	uses {
> 		interface LinkEstimator;
> 		interface NeighborTable;
> 		interface AMSend[COLLECTION_CONTROL_AM_ID];
> 		interface Receive[COLLECTION_CONTROL_AM_ID];
> 	}
> }
>
> interface REControl {
> 	command error_t initializeRH(message_t *msg);
> 	command uint8_t getHeaderSize();
> 	command error_t startRoot();
> 	command error_t stopRoot();
> }
>
>
> interface Routing {
> 	command result_t getNextHops(neighbor_t* nextHops, uint8_t* n);
> }
>
>
> 4.3 ForwardingEngineP
> --------------------------------------------------------------------
>
> ForwardingEngineP component provides all the top level interface
> (except RootControl) which is used by an application to interact with
> CollectionC.
>
> ForwardingEngineP {
> 	provides {
> 		interface Send[uint8_t tree_id]
> 		interface Receive[uint8_t tree_id];
> 		interface Intercept;
> 		interface Snoop;
> 		interface Packet;
> 	}
> 	uses {
> 		interface REControl;
> 		interface Routing[uint8_t tree_id];
> 		interface SendMsg[COLLECTION_DATA_AM_ID];
> 		interface ReceiveMsg[COLLECTION_DATA_AM_ID];
> 	}
> }
>
> The forwarding engine MUST must try to transmit a collection packet to
> the first next hop. The forwarding engine MAY perform network-level
> retransmissions to alternate next hops returned by Routing.getNextHops
> should the trasmission to the firstnext hop fail. This might allow
> recoveries in routing on time scales shorter than those required for
> route convergence, and leverages routing engines that can provide
> multiple next hops towards a given destination.
>
>
> 5. Author's Address
> ====================================================================
>
> | Rodrigo Fonseca
> | 473 Soda Hall
> | Berkeley, CA 94720-1776
> |
> | phone - +1 510 642-8919
> | email - rfonseca at cs.berkeley.edu
> |
> |
> | Omprakash Gnawali
> | Ronald Tutor Hall (RTH) 418
> | 3710 S. McClintock Avenue
> | Los Angeles, CA 90089
> |
> | phone - +1 213 821-5627
> | email - gnawali at usc.edu
> |
> |
> | Kyle Jamieson
> | The Stata Center
> | 32 Vassar St.
> | Cambridge, MA 02139
> |
> | email - jamieson at csail.mit.edu
>
>
> 6. Citations
> ====================================================================
>
> .. [tep116] TEP 116: Packet Protocols
>
> _______________________________________________
> net2-wg mailing list
> net2-wg at millennium.berkeley.edu
> https://mail.millennium.berkeley.edu/cgi-bin/mailman/listinfo/net2-wg
>