+An implementation of CTP can be found in the tos/lib/net/ctp directory
+of TinyOS 2.0. This section describes the structure of that implementation
+and is not in any way part of the specification of CTP.
+
+This implementation has three major subcomponents:
+
+1) A **link estimator**, which is responsible for estimating the
+single-hop ETX of communication with single-hop neighbors.
+
+2) A **routing engine**, which uses link estimates as well as
+network-level information to decide which neighbor is the next
+routing hop.
+
+3) A **forwarding engine**, which maintains a queue of packets
+to send. It decides when and if to send them. The name is a little
+misleading: the forwarding engine is responsible for forwarded traffic
+as well as traffic generated on the node.
+
+6.1 Link Estimation
+------------------------------------------------------------------------------
+
+The implementation uses two mechanisms to estimate the quality of a link:
+periodic LEEP [1]_ packets and data packets. The implementation sends
+routing beacons as LEEP packets. These packets seed the neighbor table
+with bidirectional ETX values. The implementation adapts its beaconing
+rate based on network dynamics using an algorithm similar to the
+trickle dissemination protocol [2]_. Beacons are sent on an exponentially
+increasing randomized timer. The implementation resets the timer to a
+small value when one or more of the following conditions are met:
+
+ 1) The routing table is empty (this also sets the P bit)
+ 2) The node's routing ETX increases by >= 1 transmission
+ 3) The node hears a packet with the P bit set
+
+The implementation augments the LEEP link estimates with data
+transmissions. This is a direct measure of ETX. Whenever the data path
+transmits a packet, it tells the link estimator the destination and
+whether it was successfully acknowledged. The estimator produces an
+ETX estimate every 5 such transmissions, where 0 successes has an ETX
+of 6.
+
+The estimator combines the beacon and data estimates by incorporating
+them into an exponentially weighted moving average. Beacon-based
+estimates seed the neighbor table. The expectation is that the low
+beacon rate in a stable network means that for a selected route,
+data estimates will outweigh beacon estimates. Additionally, as
+the rate at which CTP collects data estimates is proportional to
+the transmission rate, then it can quickly detect a broken link and
+switch to another candidate neighbor.
+
+The component ``tos/lib/net/4bitle/LinkEstimatorP`` implements the
+link estimator. It couples LEEP-based and data-based estimates as
+described in [4]_.
+
+6.2 Routing Engine
+------------------------------------------------------------------------------
+
+The implementation's routing engine is responsible for picking the next
+hop for a data transmission. It keeps track of the path ETX values of
+a subset of the nodes maintained by the link estimation table. The minimum
+cost route has the smallest sum the path ETX from that node and the link
+ETX of that node. The path ETX is therefore the sum of link ETX values
+along the entire route. The component ``tos/lib/net/ctp/CtpRoutingEngineP``
+implements the routing engine.
+
+6.3 Forwarding Engine
+------------------------------------------------------------------------------
+
+The component ``tos/lib/net/ctp/CtpForwardingEngineP`` implements the
+forwarding engine. It has five responsibilities:
+
+ 1) Transmitting packets to the next hop, retransmitting when necessary, and
+ passing acknowledgment based information to the link estimator
+ 2) Deciding *when* to transmit packets to the next hop
+ 3) Detecting routing inconsistencies and informing the routing engine
+ 4) Maintaining a queue of packets to transmit, which are a mix of locally
+ generated and forwarded packets
+ 5) Detecting single-hop transmission duplicates caused by lost acknowledgments
+
+The four key functions of the forwading engine are packet reception
+(``SubReceive.receive()``), packet forwarding (``forward()``), packet
+transmission (``sendTask()``) and deciding what to do after a packet
+transmission (``SubSend.sendDone()``).
+
+The receive function decides whether or not the node should forward a
+packet. It checks for duplicates using a small cache of recently received
+packets. If it decides a packet is not a duplicate, it calls the
+forwading function.
+
+The forwarding function formats the packet for forwarding. It checks the
+received packet to see if there is possibly a loop in the network.
+It checks if there is space in the transmission queue.
+If there is no space, it drops the packet and sets the C bit. If the
+transmission queue was empty, then it posts the send task.
+
+The send task examines the packet at the head of the transmission
+queue, formats it for the next hop (requests the route from the
+routing layer, etc.), and submits it to the AM layer.
+
+When the send completes, sendDone examines the packet to see the result.
+If the packet was acknowledged, it pulls the packet off the transmission
+queue. If the packet was locally generated, it signals sendDone() to the
+client above. If it was forwarded, it returns the packet to the forwarding
+message pool. If there are packets remaining in the queue (e.g., the
+packet was not acknowledged), it starts a randomized timer that reposts
+this task. This timer essentially rate limits CTP so that it does not
+stream packets as quickly as possible, in order to prevent self-collisions
+along the path.
+
+7. Citations
+====================================================================
+
+| Rodrigo Fonseca
+| 473 Soda Hall
+| Berkeley, CA 94720-1776
+|
+| phone - +1 510 642-8919
+| email - rfonseca@cs.berkeley.edu
+|
+|
+| Omprakash Gnawali
+| Ronald Tutor Hall (RTH) 418
+| 3710 S. McClintock Avenue
+| Los Angeles, CA 90089
+|
+| phone - +1 213 821-5627
+| email - gnawali@usc.edu
+|
+|
+| Kyle Jamieson
+| The Stata Center
+| 32 Vassar St.
+| Cambridge, MA 02139
+|
+| email - jamieson@csail.mit.edu
+|
+|
+| Philip Levis
+| 358 Gates Hall
+| Computer Science Laboratory
+| Stanford University
+| Stanford, CA 94305
+|
+| phone - +1 650 725 9046
+| email - pal@cs.stanford.edu
+|
+|
+| Alec Woo
+| Arch Rock Corporation
+| 501 2nd St. Ste 410
+| San Francisco, CA 94107-4132
+|
+| email - awoo@archrock.com
+|
+|
+| Sukun Kim
+| Samsung Electronics
+| 416 Maetan-3-dong, Yeongtong-Gu
+| Suwon, Gyeonggi 443-742
+| Korea, Republic of
+|
+| phone - +82 10 3065 6836
+| email - sukun.kim@samsung.com
+
+8. Citations
+====================================================================
+
+.. [1] TEP 124: Link Estimation Extension Protocol
+.. [2] Philip Levis, Neil Patel, David Culler and Scott Shenker. "A
+ Self-Regulating Algorithm for Code Maintenance and Propagation
+ in Wireless Sensor Networks." In Proceedings of the First USENIX
+ Conference on Networked Systems Design and Implementation (NSDI), 2004.
+.. [3] TEP 119: Collection.
+.. [4] Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, and Philip Levis.
+ "Four Bit Wireless Link Estimation." In Proceedings of the Sixth Workshop
+ on Hot Topics in Networks (HotNets VI), November 2007.