X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=tos%2Flib%2Fnet%2Fctp%2FCtpForwardingEngineP.nc;h=cfe8f733976fddd839f6696e64ba00a10fa2bdf4;hb=78f272255a8b5a7480ae0986ce696e9be7f555cd;hp=538fb6469bc49da3dcf6fec9aceb4a1acb3c50b8;hpb=bfa403043f98fb652396c730805366da2f3a54ff;p=tinyos-2.x.git
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.
* - *Case | - *Base wait | - *Wait window | - *Description | - *
Forwarding | - *Immediate | - *Immediate | - *When 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. | - *
Success | - *SENDDONE_OK_OFFSET | - *SENDDONE_OK_WINDOW | - *When the ForwardingEngine successfully sends a packet to the next - * hop, it waits this long before sending the next packet in the queue. - * | - *
Ack Failure | - *SENDDONE_NOACK_OFFSET | - *SENDDONE_NOACK_WINDOW | - *If 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 Detection | - *LOOPY_OFFSET | - *LOOPY_WINDOW | - *If 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