[net2-wg] Collection TEP draft
Joe Polastre
joe at polastre.com
Sun Feb 12 14:42:17 PST 2006
Collection should have a specified AM id. Collection should then
dispatch based on a collection id. Multi-dispatch works so much
better than having to wire up MultiHop to AM/SP on each instance.
-Joe
On 2/9/06, Omprakash Gnawali <gnawali at aludra.usc.edu> wrote:
>
> 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
> >
>
> _______________________________________________
> net2-wg mailing list
> net2-wg at millennium.berkeley.edu
> https://mail.millennium.berkeley.edu/cgi-bin/mailman/listinfo/net2-wg
>
More information about the net2-wg
mailing list