[net2-wg] Collection TEP draft

[Omprakash Gnawali]

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