[net2-wg] Collection TEP draft
Jonathan Hui
jwhui at cs.berkeley.edu
Thu Feb 9 08:53:24 PST 2006
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
>
More information about the net2-wg
mailing list