[net2-wg] Re: [Tinyos-2-commits] CVS:
tinyos-2.x/tos/lib/net/collection collection.draft, NONE, 1.1.2.1
Rodrigo Fonseca
rfonseca at cs.berkeley.edu
Wed Feb 1 18:58:10 PST 2006
Thanks Joe, that is a very good suggestion.
I'll make the change.
Rodrigo
On 2/1/06, Joe Polastre <joe at polastre.com> wrote:
> Sorry, sent this to the tinyos-2-commits list when I meant to send it
> to the net2 group.
>
> -Joe
>
> On 2/1/06, Joe Polastre <joe at polastre.com> wrote:
> > comment: would recommend a type for neighbor addresses, such as
> > neighbor_t or nw_address_t. The initial version may just do
> > typedef uint16_t nw_address_t
> > But for integrating well with the improvements Arselan and Jay made to
> > SP for better network naming, you should hide the details of the
> > address behind a typedef or struct.
> >
> > -Joe
> >
> > On 2/1/06, Rodrigo Fonseca <rfonseca76 at users.sourceforge.net> wrote:
> > > Update of /cvsroot/tinyos/tinyos-2.x/tos/lib/net/collection
> > > In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv7483
> > >
> > > Added Files:
> > > Tag: tinyos-2_0_devel-BRANCH
> > > collection.draft
> > > Log Message:
> > > Draft specification of the collection service
> > >
> > > --- NEW FILE: collection.draft ---
> > > Collection Service
> > >
> > > $Id: collection.draft,v 1.1.2.1 2006/02/02 02:49:25 rfonseca76 Exp $
> > >
> > > Rodrigo Fonseca, UCB
> > > Omprakash Gnawali, USC
> > > Kyle Jamieson, MIT
> > >
> > >
> > > This document describes inital thoughts on the collection protocol to be
> > > produced by the net2-wg. The main improvements over the defacto standard
> > > collection from TinyOS 1.x are as follows:
> > >
> > > 1. decoupling of neighbor management and link estimation from the routing
> > > establising element
> > > 2. more general modularization, in the direction of allowing very different
> > > multihop protocols to be implemented along the same lines. This structure can
> > > evolve to a more general network layer architecture.
> > > 3. decoupling of tree identifier from node address
> > >
> > >
> > > Service:
> > >
> > > The service provided by the collection network service is best-effort, multihop
> > > delivery of packets to the root of a specified tree. The interfaces provided
> > > are for sending, receiving, intercepting, and snooping packets. Packets in
> > > transit can be intercepted for in-network processing, and traffic can be
> > > snooped by forwarding nodes.
> > >
> > > [Rodrigo: This needs discussion, as we are parameterizing the send interface
> > > per tree id, and then want to further demultiplex by N_ID.
> > > These interfaces are
> > > parameterized by a network-layer id (in contrast to an AM id). AM ids are used
> > > for multiplexing at the link layer, and NID is used for demultiplexing among
> > > different users of the network layer.
> > > ]
> > >
> > > Best-effort means that absolute reliability should be obtained by higher layer
> > > mechanisms, such as end-to-end retransmissions or forward error correcting
> > > coding. However, it does not preclude network level retransmissions and
> > > link-level retransmissions.
> > >
> > > There can be multiple trees in a network, and there can be multiple roots in a
> > > tree. A network with a single root is a special case of the former. A tree
> > > with multiple roots will provide the semantics of anycast: the message will be
> > > delivered to one of the roots. The specific tree is identified by a tree
> > > identifier (tree_id). Tree_id is explicitly decoupled from the node id that is
> > > the root of the tree, and is considered a network-level name.
> > >
> > > This decoupling has some advantages.
> > > 1. allows transparent substitution of one root by another, in case of
> > > failures for example.
> > > 2. allows any node to become the root of a tree
> > > 3. allows trees with multiple roots
> > >
> > > The specific tree(s) an application sends messages to can be configured at
> > > compile time. A shim module can be interposed between the network layer and
> > > the application and provide an address-free sending interface to a specified
> > > tree_id.
> > >
> > > Service decomposition:
> > >
> > > There are two main functionalities in the collection network protocol,
> > > corresponding to data and control planes. The data plane is responsible for
> > > forwarding of messages, and the control plane is responsible for the
> > > establishment of the routes in the network. In other words, the control plane
> > > tells *where* to send messages to, while the data plane is responsible for
> > > *how* and *when* to send messages. Correspondingly, there are two main modules
> > > in the implementation: a forwarding engine and a routing engine. The basic
> > > interface between the two is a lookup call that obtains a set of next hops to
> > > forward the message to.
> > >
> > > The forwarding engine is responsible for the forwarding discipline: queueing,
> > > scheduling, network-level retransmission. The routing engine is responsible for
> > > building and maintaining the information necessary to get the next hops for a
> > > given message. For example, it should maintain the tree structure. It should
> > > use the services of a link estimator to provide link quality estimates for
> > > different neighbors.
> > >
> > > Control-plane protocol:
> > >
> > > The tree formation protocol is based on a variation of the distance vector
> > > protocol.
> > >
> > > Control packet format:
> > >
> > > 16:source 4:count 4:total | [ 8:tree_id | 8:root_id | 8:root_seqno | 8:hopcount | 16:cost ]+
> > >
> > > source is the neighbor id
> > > total is how many control packets in this message (if there are many roots that
> > > don't fit into a packet)
> > > count is which one of the total packets in this message this belongs to
> > >
> > > Then there is a sequence of cost-to-root messages, specifying the tree_id, the
> > > root_id in that tree, the
> > > hopcount of the sending node, the cost to that root through the sender, and the
> > > sequence number of the root message.
> > >
> > > A tree formation message is simply one initiated by the root, in which the
> > > hopcount and the cost are 0, and the sequence number is incremented with each
> > > broadcast. The root is the only node which increments the cost-to-root entry
> > > sequence numbers.
> > >
> > > The tree_id allows multiple trees, hopcount allows the tree formation and
> > > establishment of hopcounts. Cost allows parent selection. Cost MUST be a
> > > cumulative (additive or multiplicative) measure that represents the cost or
> > > quality to get a message to the root starting from sending node. The root_id
> > > and root_seqno are needed for the prevention of count to infinity problems.
> > >
> > > Each node actively maintains a parent towards the root of a tree. This is the
> > > neighbor with the lowest composed cost (my cost to the neighbor + the
> > > neighbor's cost). This parent is not necessarily used for routing: it is used
> > > to establish the hopcount, and thus the tree structure. A packet can be routed
> > > to any node that decreases the cost to the root. Should a parent die, it will
> > > be readily replaced by another neighbor with a lower cost. This can be done
> > > proactively by looking at the neighbor table, or can wait for the next distance
> > > vector update from a neighbor.
> > >
> > > Data-plane protocol:
> > >
> > > There are two header fields in the data-plane packets that allow successful
> > > routing:
> > > typedef struct {
> > > uint8_t tree_id;
> > > uint16_t min_cost;
> > > } nc_header; //network collection header
> > >
> > > The forwarding engine can elect to perform network-level retransmissions to
> > > alternate next hops should the trasmission to a given next hop fail. This
> > > allows 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. This technique can reduce the buffer
> > > requirements at forwarding nodes, and spread the load in face of congestion.
> > > However it is still an open question whether this is the best response: it
> > > might also spread congestion.
> > >
> > > Link Estimation:
> > >
> > > 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 between the link estimator and the routing engine, see interface
> > > LinkEstimator below. The one requirement is that the quality returned be
> > > standardized. Two candidates are the probability of success of a packet, and
> > > the ETX, or expected number of transmissions to get the message across to the
> > > other node. Some protocols might also be interested in one of the reverse or
> > > forward qualities. It is the job of the link estimator to convert other
> > > metrics to the standardized one, and to possibly have its own control traffic
> > > to exchange reverse link qualities.
> > >
> > > There are currently three ways of doing this: using LQI, using RSSI, or using
> > > an average history of packet losses on a link. In the case of the former, it is
> > > possible that the link estimator be interposed in the network stack and inserts
> > > a header with the source address in each outgoing packet.
> > >
> > > Some Issues:
> > >
> > > Any node can become the root of a tree. Nodes can keep state about a limited
> > > number of trees. An issue arises when there are more trees active than space in
> > > the nodes, and there has to be a decision on which tree to keep information
> > > about.
> > >
> > > One solution is to have it be first-come first-serve. Another is to have a
> > > deterministic priority between tree ids, such that a new tree message will
> > > displace a lower priority one. Eventually a new tree with higher priority id
> > > will reach the root of a lower priority one, and the root will silence.
> > >
> > > Maybe the simpler solution for now is to have a first come-first serve policy,
> > > such that a new root will fail to propagate its messages on a network with more
> > > than one tree.
> > >
> > > Interfaces:
> > >
> > > (The send interface is to be used, parameterized by tree_id)
> > > interface BasicRouting
> > > //To be parameterized by tree_id
> > > command result_t getNextHops(uint16_t* nextHops, uint8_t* n);
> > > interface CostBasedRouting
> > > //To be parameterized by tree_id
> > > command uint16_t getMyCost();
> > > command uint16_t getNeighborCost(uint16_t neighbor);
> > > interface REControl
> > > command result_t initializeRH(message_t *msg, uint8_t tree_id);
> > > command uint8_t getHeaderSize();
> > > command result_t startRoot(uint8_t tree_id);
> > > command result_t stopRoot(uint8_t tree_id);
> > >
> > > interface LinkEstimator:
> > > command uint8_t getLinkQuality(uint16_t neighbor);
> > > command uint8_t getReverseQuality(uint16_t neighbor);
> > > command uint8_t getForwardQuality(uint16_t neighbor);
> > >
> > > interface NeighborTable:
> > > event void evicted(uint16_t neighbor)
> > >
> > > Components:
> > >
> > > LinkEstimator {
> > > provides {
> > > interface LinkEstimator;
> > > interface NeighborTable;
> > > }
> > > }
> > >
> > > MTreeRoutingEngine
> > > provides {
> > > REControl;
> > > BasicRouting[uint8_t tree_id];
> > > CostBasedRouting[uint8_t tree_id];
> > > }
> > > uses {
> > > LinkEstimator;
> > > NeighborTable;
> > > SendMsg[CONTROL_AM_ID];
> > > ReceiveMsg[CONTROL_AM_ID];
> > > }
> > > }
> > >
> > > ForwardingEngine {
> > > provides {
> > > interface Send[uint8_t tree_id]
> > > interface Receive[uint8_t tree_id];
> > > interface Intercept;
> > > interface Snoop;
> > > interface Packet;
> > > }
> > > uses {
> > > interface REControl;
> > > interface BasicRouting[uint8_t tree_id];
> > > interface CostBasedRouting[uint8_t tree_id];
> > > interface SendMsg[COLLECTION_AM_ID];
> > > interface ReceiveMsg[COLLECTION_AM_ID];
> > > }
> > > }
> > >
> > > Observation: while some of these interfaces are similar to the ones specified
> > > for multihop routing in TinyOS 1.x, there were several required changes. The
> > > TinyOS framework assumed address-free protocols, and only one next hop per
> > > message. There was also a coupling assumed between parent selection and
> > > neighbor/link quality estimation, which resulted in the exposure of some
> > > parameters not necessary for the forwarding part. There is parallel between
> > > RouteSelect and BasicRouting, CostBasedRouting and REControl, while calls such
> > > as getQuality shouldn't be exposed to the ForwardingEngine.
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > _______________________________________________
> > > Tinyos-2-commits mailing list
> > > Tinyos-2-commits at mail.millennium.berkeley.edu
> > > https://mail.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-2-commits
> > >
> >
>
More information about the net2-wg
mailing list