--- /dev/null
+<?xml version="1.0" encoding="utf-8" ?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+<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/" />
+<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">
+
+/*
+:Author: David Goodger
+:Contact: goodger@users.sourceforge.net
+:date: $Date$
+:version: $Revision$
+:copyright: This stylesheet has been placed in the public domain.
+
+Default cascading style sheet for the HTML output of Docutils.
+*/
+body {
+ font-family: Times;
+ font-size: 16px;
+}
+
+.first {
+ margin-top: 0 ! important }
+
+.last {
+ margin-bottom: 0 ! important }
+
+.hidden {
+ display: none }
+
+a.toc-backref {
+ text-decoration: none ;
+ color: black }
+
+blockquote.epigraph {
+ margin: 2em 5em ; }
+
+dd {
+ margin-bottom: 0.5em }
+
+/* Uncomment (& remove this text!) to get bold-faced definition list terms
+dt {
+ font-weight: bold }
+*/
+
+div.abstract {
+ margin: 2em 5em }
+
+div.abstract p.topic-title {
+ font-weight: bold ;
+ text-align: center }
+
+div.attention, div.caution, div.danger, div.error, div.hint,
+div.important, div.note, div.tip, div.warning, div.admonition {
+ margin: 2em ;
+ border: medium outset ;
+ padding: 1em }
+
+div.attention p.admonition-title, div.caution p.admonition-title,
+div.danger p.admonition-title, div.error p.admonition-title,
+div.warning p.admonition-title {
+ color: red ;
+ font-weight: bold ;
+ font-family: sans-serif }
+
+div.hint p.admonition-title, div.important p.admonition-title,
+div.note p.admonition-title, div.tip p.admonition-title,
+div.admonition p.admonition-title {
+ font-weight: bold ;
+ font-family: sans-serif }
+
+div.dedication {
+ margin: 2em 5em ;
+ text-align: center ;
+ font-style: italic }
+
+div.dedication p.topic-title {
+ font-weight: bold ;
+ font-style: normal }
+
+div.figure {
+ margin-left: 2em }
+
+div.footer, div.header {
+ font-size: smaller }
+
+div.line-block {
+ display: block ;
+ margin-top: 1em ;
+ margin-bottom: 1em }
+
+div.line-block div.line-block {
+ margin-top: 0 ;
+ margin-bottom: 0 ;
+ margin-left: 1.5em }
+
+div.sidebar {
+ margin-left: 1em ;
+ border: medium outset ;
+ padding: 0em 1em ;
+ background-color: #ffffee ;
+ width: 40% ;
+ float: right ;
+ clear: right }
+
+div.sidebar p.rubric {
+ font-family: sans-serif ;
+ font-size: medium }
+
+div.system-messages {
+ margin: 5em }
+
+div.system-messages h1 {
+ color: red }
+
+div.system-message {
+ border: medium outset ;
+ padding: 1em }
+
+div.system-message p.system-message-title {
+ color: red ;
+ font-weight: bold }
+
+div.topic {
+ margin: 2em }
+
+h1 {
+ font-family: Arial, sans-serif;
+ font-size: 20px;
+}
+
+h1.title {
+ text-align: center;
+ font-size: 32px;
+}
+
+h2 {
+ font-size: 16px;
+ font-family: Arial, sans-serif;
+}
+
+h2.subtitle {
+ text-align: center }
+
+h3 {
+ font-size: 12px;
+ font-family: Arial, sans-serif;
+}
+
+hr {
+ width: 75% }
+
+ol.simple, ul.simple {
+ margin-bottom: 1em }
+
+ol.arabic {
+ list-style: decimal }
+
+ol.loweralpha {
+ list-style: lower-alpha }
+
+ol.upperalpha {
+ list-style: upper-alpha }
+
+ol.lowerroman {
+ list-style: lower-roman }
+
+ol.upperroman {
+ list-style: upper-roman }
+
+p.attribution {
+ text-align: right ;
+ margin-left: 50% }
+
+p.caption {
+ font-style: italic }
+
+p.credits {
+ font-style: italic ;
+ font-size: smaller }
+
+p.label {
+ white-space: nowrap }
+
+p.rubric {
+ font-weight: bold ;
+ font-size: larger ;
+ color: maroon ;
+ text-align: center }
+
+p.sidebar-title {
+ font-family: sans-serif ;
+ font-weight: bold ;
+ font-size: larger }
+
+p.sidebar-subtitle {
+ font-family: sans-serif ;
+ font-weight: bold }
+
+p.topic-title {
+ font-weight: bold }
+
+pre.address {
+ margin-bottom: 0 ;
+ margin-top: 0 ;
+ font-family: serif ;
+ font-size: 100% }
+
+pre.line-block {
+ font-family: serif ;
+ font-size: 100% }
+
+pre.literal-block, pre.doctest-block {
+ margin-left: 2em ;
+ margin-right: 2em ;
+ background-color: #eeeeee;
+ border-color: #000000;
+ border-width: thin;
+ font-size: 14px
+}
+
+span.classifier {
+ font-family: sans-serif ;
+ font-style: oblique }
+
+span.classifier-delimiter {
+ font-family: sans-serif ;
+ font-weight: bold }
+
+span.interpreted {
+ font-family: sans-serif }
+
+span.option {
+ white-space: nowrap }
+
+span.option-argument {
+ font-style: italic }
+
+span.pre {
+ white-space: pre }
+
+span.problematic {
+ color: red }
+
+table {
+ margin-top: 0.5em ;
+ margin-bottom: 0.5em }
+
+table.citation {
+ border-left: solid thin gray ;
+ padding-left: 0.5ex }
+
+table.docinfo {
+ margin: 2em 4em;
+}
+
+table.footnote {
+ border-left: solid thin black ;
+ padding-left: 0.5ex }
+
+td, th {
+ padding-left: 0.5em ;
+ padding-right: 0.5em ;
+ vertical-align: top }
+
+th.docinfo-name, th.field-name {
+ font-weight: bold ;
+ text-align: left ;
+ white-space: nowrap;
+ }
+
+h1 tt, h2 tt, h3 tt, h4 tt, h5 tt, h6 tt {
+ font-size: 100% }
+
+tt {}
+
+ul.auto-toc {
+ list-style-type: none }
+
+</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" />
+<col class="docinfo-content" />
+<tbody valign="top">
+<tr class="field"><th class="docinfo-name">TEP:</th><td class="field-body">123</td>
+</tr>
+<tr class="field"><th class="docinfo-name">Group:</th><td class="field-body">Network Working Group</td>
+</tr>
+<tr class="field"><th class="docinfo-name">Type:</th><td class="field-body">Documentary</td>
+</tr>
+<tr><th class="docinfo-name">Status:</th>
+<td>Draft</td></tr>
+<tr class="field"><th class="docinfo-name">TinyOS-Version:</th><td class="field-body">2.x</td>
+</tr>
+<tr><th class="docinfo-name">Author:</th>
+<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>
+<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2006-07-12</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="note">
+<p class="first admonition-title">Note</p>
+<p class="last">This memo documents a part of TinyOS for the TinyOS Community, and
+requests discussion and suggestions for improvements. Distribution
+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
+collection roots in a network.</p>
+</div>
+<div class="section">
+<h1><a id="introduction" 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>
+<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
+send a packet to a particular root; instead, it implicitly chooses a
+root by choosing a next hop. Nodes generate routes to roots using
+a routing gradient.</p>
+<p>The CTP protocol assumes that the data link layer provides four things:</p>
+<blockquote>
+<ol class="arabic simple">
+<li>Provides an efficient local broadcast address.</li>
+<li>Provides synchronous acknowledgments for unicast packets.</li>
+<li>Provides a protocol dispatch field to support multiple higher-level
+protocols.</li>
+<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
+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,
+but it does not promise 100% reliable delivery. It is best effort, but
+a best effort that <em>tries very hard.</em></p>
+<p>CTP is designed for relatively low traffic rates. Bandwidth-limited systems
+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>
+<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
+is an inconsistency in the tree. CTP tries to resolve the inconsistency
+by broadcasting a beacon frame, with the hope that the node which sent
+the data frame will hear it and adjust its routes accordingly. If a
+collection of nodes is separated from the rest of the network, then they
+will form a loop whose ETX increases forever. CTP's second mechanism
+is to not consider routes with an ETX higher than a reasonable constant.
+The value of this constant is implementation dependent.</p>
+<p>Packet duplication is an additional problem that can occur in CTP.
+Packet duplication occurs when a node receives a data frame successfully
+and transmits an ACK, but the ACK is not received. The sender retransmits
+the packet, and the receiver receives it a second time. This can have
+disasterous effects over multiple hops, as the duplication is exponential.
+For example, if each hop on average produces one duplicate, then on the
+first hop there will be two packets, on the second there will be four,
+on the third there will be eight, etc.</p>
+<p>Routing loops complicate duplicate suppression, as a routing loop may
+cause a node to legitimately receive a packet more than once. Therefore,
+if a node suppresses duplicates based solely on originating address and
+sequence number, packets in routing loops may be dropped. CTP data frames
+therefore have an additional time has lived (THL) field, which the
+routing layer increments on each hop. A link-level retransmission has
+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>
+<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
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+|C|P| reserved | THL |
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+| ETX |
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+| origin |
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+| seqno | collect_id |
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+| 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>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>
+</ul>
+</blockquote>
+<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
+acknowledgments enabled.</p>
+</div>
+<div class="section">
+<h1><a id="ctp-routing-frame" 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
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+|C|P| reserved | address |
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+| address | 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>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>
+</div>
+</div>
+</body>
+</html>
projects / tinyos-2.x.git / commitdiff