<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
-<meta name="generator" content="Docutils 0.4: http://docutils.sourceforge.net/" />
+<meta name="generator" content="Docutils 0.3.6: http://docutils.sourceforge.net/" />
<title>The Collection Tree Protocol (CTP)</title>
<meta name="author" content="Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, Sukun Kim, Philip Levis, and Alec Woo" />
<style type="text/css">
</style>
</head>
<body>
-<div class="document" id="the-collection-tree-protocol-ctp">
<h1 class="title">The Collection Tree Protocol (CTP)</h1>
<table class="docinfo" frame="void" rules="none">
<col class="docinfo-name" />
<td>Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, Sukun Kim, Philip Levis, and Alec Woo</td></tr>
<tr class="field"><th class="docinfo-name">Draft-Created:</th><td class="field-body">3-Aug-2006</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.2</td>
+<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.8</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2006-07-12</td>
+<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2007-02-28</td>
</tr>
<tr class="field"><th class="docinfo-name">Draft-Discuss:</th><td class="field-body">TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu></td>
</tr>
</tbody>
</table>
+<div class="document" id="the-collection-tree-protocol-ctp">
<div class="note">
<p class="first admonition-title">Note</p>
<p class="last">This memo documents a part of TinyOS for the TinyOS Community, and
of this memo is unlimited. This memo is in full compliance with
TEP 1.</p>
</div>
-<div class="section">
-<h1><a id="abstract" name="abstract">Abstract</a></h1>
-<p>This memo documents the Collection Tree Protocol (CTP), which
-provides best-effort anycast datagram communication to one of the
+<div class="section" id="abstract">
+<h1><a name="abstract">Abstract</a></h1>
+<p>This memo documents the Collection Tree Protocol (CTP), which
+provides best-effort anycast datagram communication to one of the
collection roots in a network.</p>
</div>
-<div class="section">
-<h1><a id="introduction" name="introduction">1. Introduction</a></h1>
+<div class="section" id="introduction">
+<h1><a name="introduction">1. Introduction</a></h1>
</div>
-<div class="section">
-<h1><a id="assumptions-and-limitations" name="assumptions-and-limitations">2. Assumptions and Limitations</a></h1>
+<div class="section" id="assumptions-and-limitations">
+<h1><a name="assumptions-and-limitations">2. Assumptions and Limitations</a></h1>
<p>CTP is a tree-based collection protocol. Some number of nodes in a
network advertise themselves as tree roots. Nodes form a set of routing
trees to these roots. CTP is <strong>address-free</strong> in that a node does not
<li>Has single-hop source and destination fields.</li>
</ol>
</blockquote>
-<p>CTP assumes that it has link quality estimates of some number of nearby
-neighbors. These provide an estimate of the number of transmissions it
+<p>CTP assumes that it has link quality estimates of some number of nearby
+neighbors. These provide an estimate of the number of transmissions it
takes for the node to send a unicast packet whose acknowledgment is
successfully received.</p>
<p>CTP has several mechanisms in order to improve delivery reliability,
might benefit from a different protocol, which can, for example, pack
multiple small frames into a single data-link packet.</p>
</div>
-<div class="section">
-<h1><a id="collection-and-ctp" name="collection-and-ctp">3. Collection and CTP</a></h1>
-<p>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.</p>
-<p>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.</p>
+<div class="section" id="collection-and-ctp">
+<h1><a name="collection-and-ctp">3. Collection and CTP</a></h1>
+<p>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.</p>
+<p>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.</p>
<p>CTP addresses loops through two mechanisms. First, every CTP packet
contains a node's current gradient value. If CTP receives a data frame with
a gradient value lower than its own, then this indicates that there
the same THL value, while a looped version of the packet is unlikely
to do so.</p>
</div>
-<div class="section">
-<h1><a id="ctp-data-frame" name="ctp-data-frame">4. CTP Data Frame</a></h1>
+<div class="section" id="ctp-data-frame">
+<h1><a name="ctp-data-frame">4. CTP Data Frame</a></h1>
<p>The CTP data frame format is as follows:</p>
<pre class="literal-block">
- 1
- 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
+ 1
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-|C|P| reserved | THL |
+|P|C| reserved | THL |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ETX |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-| origin |
+| origin |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-| seqno | collect_id |
+| seqno | collect_id |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-| data ...
+| data ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
</pre>
<p>Field definitions are as follows:</p>
<blockquote>
<ul class="simple">
-<li>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.</li>
-<li>P: Routing pull. The P bit allows nodes to request routing information from other nodes. If a node hears a packet with the P bit set, it SHOULD transmit a routing frame in the near future if it has a valid route.</li>
+<li>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.</li>
+<li>C: Congestion notification. If a node drops a CTP data frame, it MUST set the C field on the next data frame it transmits.</li>
<li>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.</li>
<li>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.</li>
<li>origin: The originating address of the packet. A node forwarding a data frame MUST NOT modify the origin field.</li>
<li>seqno: Origin sequence number. The originating node sets this field, and a node forwarding a data frame MUST NOT modify it.</li>
<li>collect_id: Higher-level protocol identifier. The origin sets this field, and a node forwarding a data frame MUST NOT modify it.</li>
-<li>data: the data payload, of zero or more bytes.</li>
+<li>data: the data payload, of zero or more bytes. A node forwarding a data frame MUST NOT modify the data payload.</li>
</ul>
</blockquote>
-<p>Together, the origin, seqno and collect_id fields denote a unique
+<p>Together, the origin, seqno and collect_id fields denote a unique
<strong>*origin packet.*</strong> Together, the origin, seqno, collect_id, and
THL denote a unique <strong>*packet instance*</strong> within the network. The
distinction is important for duplicate suppression in the presence
of routing loops. If a node suppresses origin packets, then if
asked to forward the same packet twice due to a routing loop, it will
-drop the packet. However, if it suppresses packet instances, then
-unless the THL has wrapped around to the identical value it had
-on previous times around.</p>
-<p>A node MUST send CTP data frames as unicast messages with link-layer
+drop the packet. However, if it suppresses packet instances, then it
+will route succesfully in the presence of transient loops unless the
+THL happens to wrap around to a forwarded packet instance.</p>
+<p>A node MUST send CTP data frames as unicast messages with link-layer
acknowledgments enabled.</p>
</div>
-<div class="section">
-<h1><a id="ctp-routing-frame" name="ctp-routing-frame">5. CTP Routing Frame</a></h1>
+<div class="section" id="ctp-routing-frame">
+<h1><a name="ctp-routing-frame">5. CTP Routing Frame</a></h1>
<p>The CTP routing frame format is as follows:</p>
<pre class="literal-block">
- 1
- 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
+ 1
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-|C|P| reserved | address |
+|P|C| reserved | parent |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-| address | ETX |
+| parent | ETX |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-| ETX |
+| ETX |
+-+-+-+-+-+-+-+-+
</pre>
<p>The fields are as follows:</p>
<blockquote>
<ul class="simple">
-<li>C: Same as data frame.</li>
<li>P: Same as data frame.</li>
-<li>address: The node's active message address.</li>
+<li>C: Congestion notification. If a node drops a CTP data frame, it MUST set the C field on the next routing frame it transmits.</li>
+<li>parent: The node's current parent.</li>
<li>metric: The node's current routing metric value.</li>
</ul>
</blockquote>
<p>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.</p>
+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.</p>
+</div>
+<div class="section" id="implementation">
+<h1><a name="implementation">6. Implementation</a></h1>
+<p>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.</p>
+<p>This implementation has three major subcomponents:</p>
+<p>1) A <strong>link estimator</strong>, which is responsible for estimating the
+single-hop ETX of communication with single-hop neighbors.</p>
+<p>2) A <strong>routing engine</strong>, which uses link estimates as well as
+network-level information to decide which neighbor is the next
+routing hop.</p>
+<p>3) A <strong>forwarding engine</strong>, 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.</p>
+<div class="section" id="link-estimation">
+<h2><a name="link-estimation">6.1 Link Estimation</a></h2>
+<p>The implementation uses two mechanisms to estimate the quality of a link:
+periodic LEEP <a class="footnote-reference" href="#id4" id="id1" name="id1">[1]</a> 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 <a class="footnote-reference" href="#id5" id="id2" name="id2">[2]</a>. 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:</p>
+<blockquote>
+<ol class="arabic simple">
+<li>The routing table is empty (this also sets the P bit)</li>
+<li>The node's routing ETX increases by >= 1 trasmission</li>
+<li>The node hears a packet with the P bit set</li>
+</ol>
+</blockquote>
+<p>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.</p>
+<p>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.</p>
+<p>The component <tt class="docutils literal"><span class="pre">tos/lib/net/le/LinkEstimatorP</span></tt> implements the
+link estimator. It couples LEEP-based and data-based estimates.</p>
+</div>
+<div class="section" id="routing-engine">
+<h2><a name="routing-engine">6.2 Routing Engine</a></h2>
+<p>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 <tt class="docutils literal"><span class="pre">tos/lib/net/ctp/CtpRoutingEngineP</span></tt>
+implements the routing engine.</p>
+</div>
+<div class="section" id="forwarding-engine">
+<h2><a name="forwarding-engine">6.3 Forwarding Engine</a></h2>
+<p>The component <tt class="docutils literal"><span class="pre">tos/lib/net/ctp/CtpForwardingEngineP</span></tt> implements the
+forwarding engine. It has five repsonsibilities:</p>
+<blockquote>
+<ol class="arabic simple">
+<li>Transmitting packets to the next hop, retransmitting when necessary, and
+passing acknowledgment based information to the link estimator</li>
+<li>Deciding <em>when</em> to transmit packets to the next hop</li>
+<li>Detecting routing inconsistencies and informing the routing engine</li>
+<li>Maintaining a queue of packets to transmit, which are a mix of locally
+generated and forwarded packets</li>
+<li>Detecting single-hop transmission duplicates caused by lost acknowledgments</li>
+</ol>
+</blockquote>
+<p>The four key functions of the forwading engine are packet reception
+(<tt class="docutils literal"><span class="pre">SubReceive.receive()</span></tt>), packet forwarding (<tt class="docutils literal"><span class="pre">forward()</span></tt>), packet
+transmission (<tt class="docutils literal"><span class="pre">sendTask()</span></tt>) and deciding what to do after a packet
+transmission (<tt class="docutils literal"><span class="pre">SubSend.sendDone()</span></tt>).</p>
+<p>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.</p>
+<p>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.</p>
+<p>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.</p>
+<p>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.</p>
+</div>
+</div>
+<div class="section" id="citations">
+<h1><a name="citations">7. Citations</a></h1>
+<div class="line-block">
+<div class="line">Rodrigo Fonseca </div>
+<div class="line">473 Soda Hall</div>
+<div class="line">Berkeley, CA 94720-1776</div>
+<div class="line"><br /></div>
+<div class="line">phone - +1 510 642-8919</div>
+<div class="line">email - <a class="reference" href="mailto:rfonseca@cs.berkeley.edu">rfonseca@cs.berkeley.edu</a></div>
+<div class="line"><br /></div>
+<div class="line"><br /></div>
+<div class="line">Omprakash Gnawali</div>
+<div class="line">Ronald Tutor Hall (RTH) 418 </div>
+<div class="line">3710 S. McClintock Avenue</div>
+<div class="line">Los Angeles, CA 90089 </div>
+<div class="line"><br /></div>
+<div class="line">phone - +1 213 821-5627</div>
+<div class="line">email - <a class="reference" href="mailto:gnawali@usc.edu">gnawali@usc.edu</a></div>
+<div class="line"><br /></div>
+<div class="line"><br /></div>
+<div class="line">Kyle Jamieson</div>
+<div class="line">The Stata Center</div>
+<div class="line">32 Vassar St.</div>
+<div class="line">Cambridge, MA 02139 </div>
+<div class="line"><br /></div>
+<div class="line">email - <a class="reference" href="mailto:jamieson@csail.mit.edu">jamieson@csail.mit.edu</a></div>
+<div class="line"><br /></div>
+<div class="line"><br /></div>
+<div class="line">Philip Levis</div>
+<div class="line">358 Gates Hall</div>
+<div class="line">Computer Science Laboratory</div>
+<div class="line">Stanford University</div>
+<div class="line">Stanford, CA 94305</div>
+<div class="line"><br /></div>
+<div class="line">phone - +1 650 725 9046</div>
+<div class="line">email - <a class="reference" href="mailto:pal@cs.stanford.edu">pal@cs.stanford.edu</a></div>
+</div>
+</div>
+<div class="section" id="id3">
+<h1><a name="id3">8. Citations</a></h1>
+<table class="docutils footnote" frame="void" id="id4" rules="none">
+<colgroup><col class="label" /><col /></colgroup>
+<tbody valign="top">
+<tr><td class="label"><a class="fn-backref" href="#id1" name="id4">[1]</a></td><td>TEP 124: Link Estimation Extension Protocol</td></tr>
+</tbody>
+</table>
+<table class="docutils footnote" frame="void" id="id5" rules="none">
+<colgroup><col class="label" /><col /></colgroup>
+<tbody valign="top">
+<tr><td class="label"><a class="fn-backref" href="#id2" name="id5">[2]</a></td><td>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.</td></tr>
+</tbody>
+</table>
</div>
</div>
</body>
projects / tinyos-2.x.git / blobdiff