[net2-wg] Collection TEP draft
Jonathan Hui
jwhui at cs.berkeley.edu
Thu Feb 9 09:14:28 PST 2006
I would suggest saying that the collection routing layer requires the
use of a separate link estimation mechanism. That this link estimation
mechanism may be shared with other components or network services. And
getLinkQuality( x ) is a required method that the link estimator must
provide. I would think that X providing just getLinkQuality(), which
states something about the link should be the only MUST.
--
Jonathan W. Hui
jwhui at cs.berkeley.edu
http://www.cs.berkeley.edu/~jwhui/
On 2/9/06, Rodrigo Fonseca <rfonseca at eecs.berkeley.edu> wrote:
> This is very true.
>
> Maybe we should just state that we assume these functionalities are
> provided elsewhere.
> It is important that Collection doesn't have to wait for the SP-like
> functionalities, though.
>
> Suggestions?
>
> Thanks,
> Rodrigo
>
>
> On 2/9/06, Jonathan Hui <jwhui at eecs.berkeley.edu> wrote:
> > I feel that link estimation and neighbor table management require a
> > lot more than what this document provides and requires a separate TEP,
> > perhaps as part of a more encompasing SP-like link interface. First,
> > the description on neighbor tables is pretty thin (e.g. we have not
> > described how neighbors enter and leave the table, other than the
> > NeighborTable interface which has a single event). Second, the link
> > estimator can be used for network services other than just collection
> > routing.
> >
> > Question: What is the difference between getLinkQuality and the other
> > two commands? Is it intended to provide the bi-directional link
> > quality?
> >
> > --
> > Jonathan W. Hui
> > jwhui at cs.berkeley.edu
> > http://www.cs.berkeley.edu/~jwhui/
> >
> >
> > On 2/9/06, Omprakash Gnawali <gnawali at usc.edu> 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
> >
>
> _______________________________________________
> 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