-<h1><a id="implementation" name="implementation">4 Implementation</a></h1>
-<p>An implementation of this TEP can be found in
-<tt class="docutils literal"><span class="pre">tinyos-2.x/tos/lib/net/ctp</span></tt> and <tt class="docutils literal"><span class="pre">tinyos-2.x/tos/lib/net/4bitle</span></tt>, in
-the CTP protocol. It is beyond the scope of this document to fully
-describe CTP, but we outline its main components. CTP will be
-described in an upcoming TEP [<a class="reference" href="#id3">2</a>]. This implementation is a
-reference implementation, and is not the only possibility. It
-consists of three major components, which are wired together to form
-a CollectionC: LinkEstimatorP, CtpRoutingEngineP, and
-CtpForwardingEngineP.</p>
-<p>This decomposition tries to encourage evolution of components and
-ease of use through modularization. Neighbor management and link
-estimation are decoupled from the routing protocol. Furthermore, the
-routing protocol and route selection are decoupled from the
-forwarding policies, such as queueing and timing.</p>
-<div class="section">
-<h2><a id="linkestimatorp" name="linkestimatorp">4.1 LinkEstimatorP</a></h2>
-<p>LinkEstimatorP estimates the quality of link to or from each
-neighbor. In this TEP, we briefly describe the reference
-implementation in ''tinyos-2.x/tos/lib/4bitle'' and refer the readers
-to <a class="footnote-reference" href="#id4" id="id1" name="id1">[3]</a> for detailed description of the estimator.</p>
-<p>Link estimation is decoupled from the establishment of routes. There
-is a narrow interface -- LinkEstimator and CompareBit -- between the
-link estimator and the routing engine. The one requirement is that the
-quality returned is standardized. A smaller return value from
-LinkEstimator.getLinkQuality() MUST imply that the link to the
-neighbor is estimated to be of a higher quality than the one that
-results in a larger return value. The range of value SHOULD be
-[0,65535] 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. The routing engine instructs
-LinkEstimatorP to insert the neighbor, through which a high quality
-path to the root can be constructed, into the neighbor table by
-returning TRUE when LinkEstimatorP signals Comparebit.shouldInsert()
-for the newly discovered neighbor.</p>
-<p>LinkEstimatorP MAY have its own control messages to compute
-bi-directional link qualities. LinkEstimatorP provides calls (txAck(),
-txNoAck(), and clearDLQ()) to update the link estimates based on
-successful or unsuccessful data transmission to the
-neighbors. LinkEstimatorP uses the LinkPacketMetadata interface to
-determine if the channel was of high quality when a packet is received
-from a neighbor to consider the link to that neighbor for insertion
-into the neighbor table.</p>
-<p>The user of LinkEstimatorP can call insertNeighbor() to manually
-insert a node in the neighbor table, pinNeighbor() to prevent a
-neighbor from being evicted, and unpinNeighbor() to restore eviction
-policy:</p>
-<pre class="literal-block">
-typedef uint16_t neighbor_table_entry_t
-
-LinkEstimatorP {
- provides {
- interface StdControl;
- interface AMSend as Send;
- interface Receive;
- interface LinkEstimator;
- interface Init;
- interface Packet;
- interface CompareBit;
- }
- uses {
- interface AMSend;
- interface AMPacket as SubAMPacket;
- interface Packet as SubPacket;
- interface Receive as SubReceive;
- interface LinkPacketMetadata;
- interface Random;
- }
-}
-
-interface CompareBit {
- event bool shouldInsert(message_t *msg, void* payload, uint8_t len, bool white_bit);
-}
-
-interface LinkEstimator {
- command uint16_t getLinkQuality(uint16_t neighbor);
- command error_t insertNeighbor(am_addr_t neighbor);
- command error_t pinNeighbor(am_addr_t neighbor);
- command error_t unpinNeighbor(am_addr_t neighbor);
- command error_t txAck(am_addr_t neighbor);
- command error_t txNoAck(am_addr_t neighbor);
- command error_t clearDLQ(am_addr_t neighbor);
- event void evicted(am_addr_t neighbor);
-}
-</pre>
-</div>
-<div class="section">
-<h2><a id="ctproutingenginep" name="ctproutingenginep">4.2 CtpRoutingEngineP</a></h2>
-<p>CtpRoutingEngineP is responsible for computing routes to the roots of a
-tree. In traditional networking terminology, this is part of the
-control plane of the network, and is does not directly forward any
-data packets, which is the responsibility of CtpForwardingEngine.
-The main interface between the two is UnicastNameFreeRouting.</p>
-<p>CtpRoutingEngineP uses the LinkEstimator interface 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. CtpRoutingEngineP
-allows a node to be configured as a root or a non-root node
-dynamically. CtpRoutingEngineP maintains multiple candidate next hops:</p>
-<pre class="literal-block">
-generic module CtpRoutingEngineP(uint8_t routingTableSize,
- uint16_t minInterval,
- uint16_t maxInterval) {
- provides {
- interface UnicastNameFreeRouting as Routing;
- interface RootControl;
- interface CtpInfo;
- interface StdControl;
- interface CtpRoutingPacket;
- interface Init;
- }
- uses {
- interface AMSend as BeaconSend;
- interface Receive as BeaconReceive;
- interface LinkEstimator;
- interface AMPacket;
- interface SplitControl as RadioControl;
- interface Timer<TMilli> as BeaconTimer;
- interface Timer<TMilli> as RouteTimer;
- interface Random;
- interface CollectionDebug;
- interface CtpCongestion;
- interface Comparebit;
- }
-}
-</pre>
-<pre class="literal-block">
-interface UnicastNameFreeRouting {
- command am_addr_t nextHop();
-
- command bool hasRoute();
- event void routeFound();
- event void noRoute();
-}
-</pre>
-</div>
-<div class="section">
-<h2><a id="ctpforwardingenginep" name="ctpforwardingenginep">4.3 CtpForwardingEngineP</a></h2>
-<p>The CtpForwardingEngineP component provides all the top level interfaces
-(except RootControl) which CollectionC provides and an application
-uses. It deals with retransmissions, duplicate suppression, packet
-timing, loop detection, and also informs the LinkEstimator of the
-outcome of attempted transmissions.:</p>
-<pre class="literal-block">
-generic module CtpForwardingEngineP() {
- provides {
- interface Init;
- interface StdControl;
- interface Send[uint8_t client];
- interface Receive[collection_id_t id];
- interface Receive as Snoop[collection_id_t id];
- interface Intercept[collection_id_t id];
- interface Packet;
- interface CollectionPacket;
- interface CtpPacket;
- interface CtpCongestion;
- }
- uses {
- interface SplitControl as RadioControl;
- interface AMSend as SubSend;
- interface Receive as SubReceive;
- interface Receive as SubSnoop;
- interface Packet as SubPacket;
- interface UnicastNameFreeRouting;
- interface Queue<fe_queue_entry_t*> as SendQueue;
- interface Pool<fe_queue_entry_t> as QEntryPool;
- interface Pool<message_t> as MessagePool;
- interface Timer<TMilli> as RetxmitTimer;
- interface LinkEstimator;
- interface Timer<TMilli> as CongestionTimer;
- interface Cache<message_t*> as SentCache;
- interface CtpInfo;
- interface PacketAcknowledgements;
- interface Random;
- interface RootControl;
- interface CollectionId[uint8_t client];
- interface AMPacket;
- interface CollectionDebug;
- }
-}
-</pre>
-<p>CtpForwardingEngineP uses a large number of interfaces, which can be
-broken up into a few groups of functionality:</p>
-<blockquote>
-<ul class="simple">
-<li>Single hop communication: SubSend, SubReceive, SubSnoop,
-SubPacket, PacketAcknowledgments, AMPacket</li>
-<li>Routing: UnicastNameFreeRouting, RootControl, CtpInfo,
-CollectionId, SentCache</li>
-<li>Queue and buffer management: SendQueue, MessagePool,
-QEntryPool</li>
-<li>Packet timing: Random, RetxmitTimer</li>
-</ul>
-</blockquote>
-</div>
-</div>
-<div class="section">
-<h1><a id="multihoplqi" name="multihoplqi">4.4 MultihopLqi</a></h1>
-<p>There is another implementation of collection in <tt class="docutils literal"><span class="pre">tos/lib/net/lqi</span></tt>.
-Its software structure is similar, with the exception that it does
-not have a separate link estimator. MultihopLqi only works on
-platforms that have a CC2420 radio, as it uses a special piece
-of physical layer data the radio provides (the LQI value).
-The three major components of the MultihopLqi implementation
-are the modules LqiForwardingEngineP and LqiRoutingEngineP, as
-well as the configuration MultihopLqiP.</p>
projects / tinyos-2.x.git / commitdiff