From: scipio Date: Fri, 17 Jul 2009 21:16:34 +0000 (+0000) Subject: First step at refactoring. X-Git-Tag: rc_6_tinyos_2_1_1~353 X-Git-Url: https://oss.titaniummirror.com/gitweb/?p=tinyos-2.x.git;a=commitdiff_plain;h=78f272255a8b5a7480ae0986ce696e9be7f555cd First step at refactoring. --- diff --git a/tos/lib/net/ctp/CtpForwardingEngineP.nc b/tos/lib/net/ctp/CtpForwardingEngineP.nc index 538fb646..cfe8f733 100644 --- a/tos/lib/net/ctp/CtpForwardingEngineP.nc +++ b/tos/lib/net/ctp/CtpForwardingEngineP.nc @@ -31,35 +31,51 @@ */ /** - * The ForwardingEngine is responsible for queueing and scheduling outgoing - * packets in a collection protocol. It maintains a pool of forwarding messages - * and a packet send - * queue. A ForwardingEngine with a forwarding message pool of size F - * and C CollectionSenderC clients has a send queue of size - * F + C. This implementation has a large number of configuration - * constants, which can be found in ForwardingEngine.h. + * This component contains the forwarding path + * of CTP London, the standard CTP implementation packaged with + * TinyOS 2.x. The CTP specification can be found in TEP 123. + * The paper entitled "Collection Tree Protocol," by Omprakash + * Gnawali et al., in SenSys 2009, describes the implementation and + * provides detailed performance results.

+ * + *

The CTP London ForwardingEngine is responsible for queueing and scheduling + * outgoing packets. It maintains a pool of + * forwarding messages and a packet send queue. A ForwardingEngine + * with a forwarding message pool of size F and C + * CollectionSenderC clients has a send queue of size F + + * C. This implementation several configuration + * constants, which can be found in ForwardingEngine.h.

* *

Packets in the send queue are sent in FIFO order, with head-of-line * blocking. Because this is a tree collection protocol, all packets are going * to the same destination, and so the ForwardingEngine does not distinguish - * packets from one another: packets from CollectionSenderC clients are - * treated identically to forwarded packets.

+ * packets from one another. Packets from CollectionSenderC clients are + * sent identically to forwarded packets: only their buffer handling is + different.

* *

If ForwardingEngine is on top of a link layer that supports * synchronous acknowledgments, it enables them and retransmits packets * when they are not acked. It transmits a packet up to MAX_RETRIES times - * before giving up and dropping the packet.

+ * before giving up and dropping the packet. MAX_RETRIES is typically a + * large number (e.g., >20), as this implementation assumes there is + * link layer feedback on failed packets, such that link costs will go + * up and cause the routing layer to pick a next hop.

* *

The ForwardingEngine detects routing loops and tries to correct - * them. It assumes that the collection tree is based on a gradient, - * such as hop count or estimated transmissions. When the ForwardingEngine + * them. Routing is in terms of a cost gradient, where the collection root + * has a cost of zero and a node's cost is the cost of its next hop plus + * the cost of the link to that next hop. + * If there are no loops, then this gradient value decreases monotonically + * along a route. When the ForwardingEngine * sends a packet to the next hop, it puts the local gradient value in * the packet header. If a node receives a packet to forward whose * gradient value is less than its own, then the gradient is not monotonically * decreasing and there may be a routing loop. When the ForwardingEngine * receives such a packet, it tells the RoutingEngine to advertise its * gradient value soon, with the hope that the advertisement will update - * the node who just sent a packet and break the loop. + * the node who just sent a packet and break the loop. It also pauses the + * before the next packet transmission, in hopes of giving the routing layer's + * packet a priority.

* *

ForwardingEngine times its packet transmissions. It differentiates * between four transmission cases: forwarding, success, ack failure, @@ -67,61 +83,14 @@ * ForwardingEngine waits a randomized period of time before sending the next * packet. This approach assumes that the network is operating at low * utilization; its goal is to prevent correlated traffic -- such as - * nodes along a route forwarding packets -- from interfering with itself. - * The values for these constants are defined in CC2420ForwardingEngine.h. - * A waiting interval is Base wait plus a random wait in the range of - * 0 - Wait window. + * nodes along a route forwarding packets -- from interfering with itself.

* - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - * - *
CaseBase waitWait windowDescription
ForwardingImmediateImmediateWhen the ForwardingEngine receives a packet to forward and it is not - * already sending a packet (queue is empty). In this case, it immediately - * forwards the packet.
SuccessSENDDONE_OK_OFFSETSENDDONE_OK_WINDOWWhen the ForwardingEngine successfully sends a packet to the next - * hop, it waits this long before sending the next packet in the queue. - *
Ack FailureSENDDONE_NOACK_OFFSETSENDDONE_NOACK_WINDOWIf the link layer supports acks and the ForwardingEngine did not - * receive an acknowledgment from the next hop, it waits this long before - * trying a retransmission. If the packet has exceeded the retransmission - * count, ForwardingEngine drops the packet and uses the Success timer instead.
Loop DetectionLOOPY_OFFSETLOOPY_WINDOWIf the ForwardingEngine is asked to forward a packet from a node that - * believes it is closer to the root, the ForwardingEngine pauses its - * transmissions for this interval and triggers the RoutingEngine to - * send an update. The goal is to let the gradient become consistent before - * sending packets, in order to prevent routing loops from consuming - * bandwidth and energy.
+ *

While this implementation can work on top of a variety of link estimators, + * it is designed to work with a 4-bit link estimator (4B). Details on 4B can + * be found in the HotNets paper "Four Bit Link Estimation" by Rodrigo Fonseca + * et al. The forwarder provides the "ack" bit for each sent packet, telling the + * estimator whether the packet was acknowledged.

* - *

For CC2420-based platforms, SENDDONE_OK_OFFSET and SENDDONE_NOACK_OFFSET are 16ms, - LOOPY_OFFSET is 64ms, SENDDONE_OK_WINDOW and SENDDONE_NOACK_WINDOW are 15ms and - LOOPY_WINDOW is 63ms. DIfferent radios have different packet timings and so use - different constants.

- * @author Philip Levis * @author Kyle Jamieson * @date $Date$ @@ -144,30 +113,48 @@ generic module CtpForwardingEngineP() { interface CtpCongestion; } uses { + // These five interfaces are used in the forwarding path + // SubSend is for sending packets + // PacketAcknowledgements is for enabling layer 2 acknowledgments + // RetxmitTimer is for timing packet sends for improved performance + // LinkEstimator is for providing the ack bit to a link estimator interface AMSend as SubSend; - interface Receive as SubReceive; - interface Receive as SubSnoop; - interface Packet as SubPacket; + interface PacketAcknowledgements; + interface Timer as RetxmitTimer; + interface LinkEstimator; interface UnicastNameFreeRouting; - interface SplitControl as RadioControl; + interface Packet as SubPacket; + + // These four data structures are used to manage packets to forward. + // SendQueue and QEntryPool are the forwarding queue. + // MessagePool is the buffer pool for messages to forward. + // SentCache is for suppressing duplicate packet transmissions. interface Queue as SendQueue; interface Pool as QEntryPool; interface Pool as MessagePool; - interface Timer as RetxmitTimer; - - interface LinkEstimator; - - // Counts down from the last time we heard from our parent; used - // to expire local state about parent congestion. interface Cache as SentCache; + + interface Receive as SubReceive; + interface Receive as SubSnoop; interface CtpInfo; - interface PacketAcknowledgements; - interface Random; interface RootControl; interface CollectionId[uint8_t client]; interface AMPacket; - interface CollectionDebug; interface Leds; + interface Random; + + // This implementation has extensive debugging instrumentation. + // Wiring up the CollectionDebug interface provides information + // on important events, such as transmissions, receptions, + // and cache checks. The TinyOS release includes scripts for + // parsing these messages. + interface CollectionDebug; + + + // The ForwardingEngine monitors whether the underlying + // radio is on or not in order to start/stop forwarding + // as appropriate. + interface SplitControl as RadioControl; } } implementation {