tep123.txt

tinyos-2.x.rar

  * 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.

When a node hears a routing frame, it MUST update its routing table to
reflect the address' new metric. If a node's ETX value changes
significantly, then CTP SHOULD transmit a broadcast frame soon thereafter
to notify other nodes, which might change their routes. The parent
field acts as a surrogate for the single-hop destination field of
a data packet: a parent can detect when a child's ETX is significantly
below its own. When a parent hears a child advertise an ETX below its
own, it MUST schedule a routing frame for transmission in the near
future.

A node MUST send CTP routing frames as broadcast messages.

6. Implementation
==============================================================================

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 - [phone]
| email - [e-mail]
|
|
| Omprakash Gnawali
| Ronald Tutor Hall (RTH) 418 
| 3710 S. McClintock Avenue
| Los Angeles, CA 90089 
|
| phone - [phone]
| email - [e-mail]
|
|
| Kyle Jamieson
| The Stata Center
| 32 Vassar St.
| Cambridge, MA 02139 
|
| email - [e-mail]
|
|
| Philip Levis
| 358 Gates Hall
| Computer Science Laboratory
| Stanford University
| Stanford, CA 94305
|
| phone - [phone]
| email - [e-mail]
|
|
| Alec Woo
| Arch Rock Corporation
| 501 2nd St. Ste 410
| San Francisco, CA 94107-4132
|
| email - [e-mail]
|
|
| Sukun Kim
| Samsung Electronics
| 416 Maetan-3-dong, Yeongtong-Gu
| Suwon, Gyeonggi 443-742
| Korea, Republic of
|
| phone - [phone]
| email - [e-mail]

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.