3. Collection and CTP
==============================================================================
-CTP uses expected transmissions (ETX) as its routing gradient. A root has an
-ETX of 0. The ETX of a node is the ETX of its parent plus the ETX of its
-link to its parent. This additive measure assumes that nodes use link-level
-retransmissions. Given a choice of valid routes, CTP SHOULD choose the one with the
-lowest ETX value. CTP represents ETX values as 16-bit fixed-point real numbers
-with a precision of hundredths. An ETX value of 451, for example, represents
-an ETX of 4.51, while an ETX value of 109 represents an ETX of 1.09.
-
-Routing loops are a problem that can emerge in a CTP network. Routing loops
-generally occur when a node choose a new route that has a significantly higher
-ETX than its old one, perhaps in response to losing connectivity with a candidate
-parent. If the new route includes a node which was a descendant, then a loop
-occurs.
+CTP uses expected transmissions (ETX) as its routing gradient. A root
+has an ETX of 0. The ETX of a node is the ETX of its parent plus the
+ETX of its link to its parent. This additive measure assumes that
+nodes use link-level retransmissions. Given a choice of valid routes,
+CTP SHOULD choose the one with the lowest ETX value. CTP represents
+ETX values as 16-bit fixed-point real numbers with a precision of
+hundredths. An ETX value of 45, for example, represents an ETX of 4.5,
+while an ETX value of 10 represents an ETX of 1.
+
+Routing loops are a problem that can emerge in a CTP network. Routing
+loops generally occur when a node choose a new route that has a
+significantly higher ETX than its old one, perhaps in response to
+losing connectivity with a candidate parent. If the new route includes
+a node which was a descendant, then a loop occurs.
CTP addresses loops through two mechanisms. First, every CTP packet
contains a node's current gradient value. If CTP receives a data frame with
The CTP data frame format is as follows::
1
- 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
- |C|P| reserved | THL |
- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
- | ETX |
- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
- | origin |
- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
- | seqno | collect_id |
- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ |P|C| reserved | THL |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | ETX |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | origin |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | seqno | collect_id |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| data ...
- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Field definitions are as follows:
- * C: Congestion notification. If a node is receiving packets faster than it can forward them, it MAY set the C field to notify other nodes. If a node hears a packet from node *N* with the C bit set, it MUST NOT transmit CTP data frames to *N* until it hears a packet from N with the C bit cleared.
* P: Routing pull. The P bit allows nodes to request routing information from other nodes. If a node with a valid route hears a packet with the P bit set, it SHOULD transmit a routing frame in the near future.
+ * C: Congestion notification. If a node drops a CTP data frame, it MUST set the C field on the next data frame it transmits.
* THL: Time Has Lived. When a node generates a CTP data frame, it MUST set THL to 0. When a node receives a CTP data frame, it MUST increment the THL. If a node receives a THL of 255, it increments it to 0.
* ETX: The ETX routing metric of the single-hop sender. When a node transmits a CTP data frame, it MUST put the ETX value of its route through the single-hop destination in the ETX field. If a node receives a packet with a lower gradient than its own, then it MUST schedule a routing frame in the near future.
* origin: The originating address of the packet. A node forwarding a data frame MUST NOT modify the origin field.
The CTP routing frame format is as follows::
1
- 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
- |C|P| reserved | parent |
- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
- | parent | ETX |
- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ |P|C| reserved | parent |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | parent | ETX |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ETX |
+-+-+-+-+-+-+-+-+
The fields are as follows:
- * C: Same as data frame.
* P: Same as data frame.
+ * C: Congestion notification. If a node drops a CTP data frame, it MUST set the C field on the next routing frame it transmits.
* parent: The node's current parent.
* metric: The node's current routing metric value.
6.1 Link Estimation
------------------------------------------------------------------------------
-The link estimator estimates the ETX to single-hop neighbors.
The implementation uses two mechanisms to estimate the quality of a link:
-periodic broadcast packets and data packets. The estimator itself
-only generates broadcast packets. For data traffic, it depends on
-other components telling it about acknowledged and unacknowledged
-transmissions.
-
-The periodic broadcast packets have sequence numbers, which the
-estimator uses to estimate the sender-to-receiver packet reception
-rate (PRR). The data payload of periodic broadcast packets contain
-these estimates. Therefore, when node A receives a link estimation
-broadcast message from node B, it can use the packet header to
-estimate the B-to-A PRR and the packet payload to update B's
-estimate of the A-to-B PRR.
-
-Multiplying these two values gives a *bidirectional* PRR, or
-an estimate of the probability that if A transmits a packet to B,
-B will successfully hear and acknowledge the packet and A will
-hear the acknowledgment. The inverse of the bidirecitonal PRR
-is the ETX.
-
-CTP link estimation adapts its beaconing rate to be slow when
-its routing table is stable and faster when changes occur.
-It adjusts the beaconing interval using an algorithm similar
-to the trickle dissemination protocol[2_]. CTP sends beacons
-more often when one of three conditions occurs:
+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 trasmission
3) The node hears a packet with the P bit set
-CTP also estimates link quality using data transmissions. This
-is a direct measure of ETX. Whenever the data path transmits a
-packet, it tells the link estimator the destimation 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 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 destimation 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
the transmission rate, then it can quickly detect a broken link and
switch to another candidate neighbor.
+The component ``tos/lib/net/le/LinkEstimatorP`` implements the
+link estimator. It couples LEEP-based and data-based estimates.
+
6.2 Routing Engine
------------------------------------------------------------------------------
-The
+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 repsonsibilities:
+
+ 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
+
+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.
+
+
projects / tinyos-2.x.git / blobdiff