[net2-wg] Re: [Tinyos-2-commits] CVS:
tinyos-2.x/tos/lib/net/collection collection.draft, NONE, 1.1.2.1
Joe Polastre
joe at polastre.com
Wed Feb 1 18:53:12 PST 2006
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