<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.6</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">2007-01-16</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>
+<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
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 drops a CTP data frame, it MUST set the C field on the next data frame it transmits.</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>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
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
+<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 | parent |
+|P|C| reserved | parent |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-| parent | ETX |
+| parent | ETX |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-| ETX |
+| ETX |
+-+-+-+-+-+-+-+-+
</pre>
<p>The fields are as follows:</p>
<blockquote>
<ul class="simple">
-<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>P: Same as data frame.</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>
own, it MUST schedule a routing frame for transmission in the near
future.</p>
</div>
-<div class="section">
-<h1><a id="implementation" name="implementation">6. Implementation</a></h1>
+<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>
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">
-<h2><a id="link-estimation" name="link-estimation">6.1 Link Estimation</a></h2>
+<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
<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,
+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
<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">
-<h2><a id="routing-engine" name="routing-engine">6.2 Routing Engine</a></h2>
+<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
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">
-<h2><a id="forwarding-engine" name="forwarding-engine">6.3 Forwarding Engine</a></h2>
+<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>
along the path.</p>
</div>
</div>
-<div class="section">
-<h1><a id="citations" name="citations">7. Citations</a></h1>
+<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">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"><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">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">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">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">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">email - <a class="reference" href="mailto:pal@cs.stanford.edu">pal@cs.stanford.edu</a></div>
</div>
</div>
-<div class="section">
-<h1><a id="id3" name="id3">8. Citations</a></h1>
+<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">
projects / tinyos-2.x.git / blobdiff