<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.3.6: http://docutils.sourceforge.net/" />
+<meta name="generator" content="Docutils 0.4: http://docutils.sourceforge.net/" />
<title>Timers</title>
<meta name="author" content="Cory Sharp, Martin Turon, David Gay" />
<style type="text/css">
</style>
</head>
<body>
+<div class="document" id="timers">
<h1 class="title">Timers</h1>
<table class="docinfo" frame="void" rules="none">
<col class="docinfo-name" />
<td>Cory Sharp, Martin Turon, David Gay</td></tr>
</tbody>
</table>
-<div class="document" id="timers">
<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" id="abstract">
-<h1><a name="abstract">Abstract</a></h1>
+<div class="section">
+<h1><a id="abstract" name="abstract">Abstract</a></h1>
<p>This TEP proposes a Timer design that supports common timing
requirements both in precision and width across common hardware
configurations. This TEP focuses on aligning the Timer abstraction
with the three-layer Hardware Abstraction Architecture (HAA).</p>
</div>
-<div class="section" id="introduction">
-<h1><a name="introduction">1. Introduction</a></h1>
+<div class="section">
+<h1><a id="introduction" name="introduction">1. Introduction</a></h1>
<p>Most microcontrollers offer a rich timer system, with features like:</p>
<ul class="simple">
<li>several counters, possibly of different widths, with multiple clocking options</li>
platform-independent fashion. Instead, following the principles of the
HAA[_tep2], each microcontroller should expose all this functionality
via components and interfaces at the HPL and, where appropriate, HAL levels.
-However, two aspects of timers are sufficiently common and important
+However, two aspects of timers are sufficiently common and important
that they should be made available in a well-defined way: measuring time,
and triggering (possibly repeating) events at specific times. The rest
of this TEP specifies:</p>
events (<a class="reference" href="#interfaces">2. Interfaces</a>)</li>
<li>guidelines on how each microcontroller's HAL SHOULD expose its timer hardware
in terms of the above interfaces (<a class="reference" href="#hal-guidelines">3. HAL guidelines</a>)</li>
-<li>what components a microcontroller's timer HIL MUST implement
+<li>what components a microcontroller's timer HIL MUST implement
(<a class="reference" href="#hil-requirements">4. HIL requirements</a>)</li>
<li>a set of utility components whose use simplifies building the components
specified by the HAL guidelines and HIL requirements (<a class="reference" href="#utility-components">5. Utility components</a>)</li>
<p>This TEP ends with appendices documenting, as an example, the mica2
timer subsystem implementation.</p>
</div>
-<div class="section" id="interfaces">
-<h1><a name="interfaces">2. Interfaces</a></h1>
+<div class="section">
+<h1><a id="interfaces" name="interfaces">2. Interfaces</a></h1>
<p>Before presenting the interfaces (2.2), we start with a general
discussion of the issues of precision, width and accuracy in
timer interfaces (2.1).</p>
-<div class="section" id="precision-width-and-accuracy">
-<h2><a name="precision-width-and-accuracy">2.1 Precision, Width and Accuracy</a></h2>
+<div class="section">
+<h2><a id="precision-width-and-accuracy" name="precision-width-and-accuracy">2.1 Precision, Width and Accuracy</a></h2>
<p>Three fundamental properties of timers are <em>precision</em>, <em>width</em> and
<em>accuracy</em>.</p>
<p>Examples of precision are millisecond, a cycle of a 32kHz clock, and
binary milliseconds, 32768 32kHz ticks, or 1048576 microseconds.
This TEP emphasizes millisecond and 32kHz tick precisions while
reasonably accommodating other precisions. The use of "binary" units
-is motivated by the common availability of hardware clocks driven
+is motivated by the common availability of hardware clocks driven
by a 32768Hz crystal.</p>
<p>Examples of widths are 8-bit, 16-bit, 32-bit, and 64-bit. The width
for timer interfaces and components SHOULD be 32-bits. This TEP
<p>Note that the precision names are expressed as either frequency or
period, whichever is convenient.</p>
</div>
-<div class="section" id="timer-interfaces">
-<h2><a name="timer-interfaces">2.2 Timer interfaces</a></h2>
+<div class="section">
+<h2><a id="timer-interfaces" name="timer-interfaces">2.2 Timer interfaces</a></h2>
<p>This TEP proposes these timer interfaces:</p>
<pre class="literal-block">
interface Counter< precision_tag, size_type >
and Counter interfaces are used by the TinyOS timer system and
advanced user components.</p>
</div>
-<div class="section" id="counter">
-<h2><a name="counter">Counter</a></h2>
+<div class="section">
+<h2><a id="counter" name="counter">Counter</a></h2>
<p>The Counter interface returns the current time and provides commands
and an event for managing overflow conditions. These overflow
commands and events are necessary for properly deriving larger width
}
</pre>
<dl class="docutils">
-<dt>get() </dt>
+<dt>get()</dt>
<dd>return the current time.</dd>
-<dt>isOverflowPending() </dt>
+<dt>isOverflowPending()</dt>
<dd>return TRUE if the overflow flag is set for this counter, i.e., if and
only if an overflow event will occur after the outermost atomic
block exits. Return FALSE otherwise. This command only returns the
state of the overflow flag and causes no side effect.</dd>
-<dt>clearOverflow() </dt>
+<dt>clearOverflow()</dt>
<dd>cancel the pending overflow event clearing the overflow flag.</dd>
-<dt>overflow() </dt>
+<dt>overflow()</dt>
<dd>signals that an overflow in the current time. That is, the current
time has wrapped around from its maximum value to zero.</dd>
</dl>
</div>
-<div class="section" id="alarm">
-<h2><a name="alarm">Alarm</a></h2>
+<div class="section">
+<h2><a id="alarm" name="alarm">Alarm</a></h2>
<p>Alarm components are extensions of Counters that signal an event
when their compare register detects the alarm time has been hit.
All commands and events of the Alarm interface are asynchronous (or
}
</pre>
<dl class="docutils">
-<dt>start(dt) </dt>
+<dt>start(dt)</dt>
<dd>cancel any previously running alarm and set to fire in dt time units
from the time of invocation. The alarm will only fire once then
stop.</dd>
-<dt>stop() </dt>
+<dt>stop()</dt>
<dd>cancel any previously running alarm.</dd>
-<dt>fired() </dt>
+<dt>fired()</dt>
<dd>signals that the alarm has expired.</dd>
-<dt>isRunning() </dt>
+<dt>isRunning()</dt>
<dd>return TRUE if the alarm has been started and has not been cancelled
or has not yet fired. FALSE is returned otherwise.</dd>
</dl>
represents a time from before the last wraparound.</p>
</blockquote>
<dl class="docutils">
-<dt>getNow() </dt>
+<dt>getNow()</dt>
<dd>return the current time in the precision and width of the alarm.</dd>
-<dt>getAlarm() </dt>
+<dt>getAlarm()</dt>
<dd>return the time the currently running alarm will fire or the time
that the previously running alarm was set to fire. getAlarm can
be used with startAt to set an alarm from the previous alarm time,
fired() event to construct periodic alarms.</dd>
</dl>
</div>
-<div class="section" id="busywait">
-<h2><a name="busywait">BusyWait</a></h2>
+<div class="section">
+<h2><a id="busywait" name="busywait">BusyWait</a></h2>
<p>The BusyWait interface allows for very short synchronous delays.
BusyWait should be used sparingly and when an Alarm would not be
reasonably efficient or accurate. The BusyWait interface replaces
<dd>block until at least dt time units have elapsed</dd>
</dl>
</div>
-<div class="section" id="localtime">
-<h2><a name="localtime">LocalTime</a></h2>
+<div class="section">
+<h2><a id="localtime" name="localtime">LocalTime</a></h2>
<p>The LocalTime interface exposes a 32-bit counter without overflow
utilities. This is primarily for application code that does not
care about overflow conditions.</p>
}
</pre>
<dl class="docutils">
-<dt>get() </dt>
+<dt>get()</dt>
<dd>return the current time.</dd>
</dl>
</div>
-<div class="section" id="timer">
-<h2><a name="timer">Timer</a></h2>
+<div class="section">
+<h2><a id="timer" name="timer">Timer</a></h2>
<p>All commands and events of the Timer interface are synchronous (or
in "task context"). The Timer interface provides a set of "basic"
commands for common usage and provides a set of "extended" commands
}
</pre>
<dl class="docutils">
-<dt>startPeriodic(dt) </dt>
+<dt>startPeriodic(dt)</dt>
<dd>cancel any previously running timer and set to fire in dt time units
from the time of invocation. The timer will fire periodically every
dt time units until stopped.</dd>
-<dt>startOneShot(dt) </dt>
+<dt>startOneShot(dt)</dt>
<dd>cancel any previously running timer and set to fire in dt time units
from the time of invocation. The timer will only fire once then
stop.</dd>
-<dt>stop() </dt>
+<dt>stop()</dt>
<dd>cancel any previously running timer.</dd>
<dt>fired()</dt>
<dd>signals that the timer has expired (one-shot) or repeated (periodic).</dd>
-<dt>isRunning() </dt>
+<dt>isRunning()</dt>
<dd>return TRUE if the timer has been started and has not been cancelled
and has not fired for the case of one-shot timers. Once a periodic
timer is started, isRunning will return TRUE until it is cancelled.</dd>
-<dt>isOneShot() </dt>
+<dt>isOneShot()</dt>
<dd>return TRUE if the timer is a one-shot timer. Return FALSE
otherwise if the timer is a periodic timer.</dd>
-<dt>startPeriodicAt(t0,dt) </dt>
+<dt>startPeriodicAt(t0,dt)</dt>
<dd><p class="first">cancel any previously running timer and set to fire at time t1 =
t0+dt. The timer will fire periodically every dt time units until
stopped.</p>
value of <tt class="docutils literal"><span class="pre">t0</span></tt> numerically greater than the current time (returned by
<tt class="docutils literal"><span class="pre">getNow()</span></tt>) represents a time from before the last wraparound.</p>
</dd>
-<dt>startOneShotAt(t0,dt) </dt>
+<dt>startOneShotAt(t0,dt)</dt>
<dd><p class="first">cancel any previously running timer and set to fire at time t1 =
t0+dt. The timer will fire once then stop.</p>
<p class="last"><tt class="docutils literal"><span class="pre">t0</span></tt> is as in <tt class="docutils literal"><span class="pre">startPeriodicAt</span></tt>.</p>
</dd>
-<dt>getNow() </dt>
+<dt>getNow()</dt>
<dd>return the current time in the precision and width of the timer.</dd>
-<dt>gett0() </dt>
+<dt>gett0()</dt>
<dd>return the time anchor for the previously started timer or the time
of the previous event for periodic timers.</dd>
-<dt>getdt() </dt>
+<dt>getdt()</dt>
<dd>return the delay or period for the previously started timer.</dd>
</dl>
</div>
</div>
-<div class="section" id="hal-guidelines">
-<h1><a name="hal-guidelines">3. HAL guidelines</a></h1>
+<div class="section">
+<h1><a id="hal-guidelines" name="hal-guidelines">3. HAL guidelines</a></h1>
<p>Platforms SHOULD expose their relevant timing capabilities using
standard Alarm and Counter interfaces. The design pattern presented
here defines a component naming convention to allow platform
components SHOULD produce compile-time errors when compiled
together.</p>
</div>
-<div class="section" id="hil-requirements">
-<h1><a name="hil-requirements">4. HIL requirements</a></h1>
+<div class="section">
+<h1><a id="hil-requirements" name="hil-requirements">4. HIL requirements</a></h1>
<p>The following component MUST be provided on all platforms</p>
<pre class="literal-block">
HilTimerMilliC
HilTimerMilliC and 1/1048576s for BusyWaitMicroC. Components using
other precisions (e.g., regular, non-binary milliseconds) MAY also be
provided.</p>
-<div class="section" id="hiltimermillic">
-<h2><a name="hiltimermillic">HilTimerMilliC</a></h2>
+<div class="section">
+<h2><a id="hiltimermillic" name="hiltimermillic">HilTimerMilliC</a></h2>
<pre class="literal-block">
configuration HilTimerMilliC
{
Timer.h. HilTimerMilliC is used by the LocalTimeMilliC component and the
TimerMilliC generic component, both found in <tt class="docutils literal"><span class="pre">tos/system/</span></tt></p>
</div>
-<div class="section" id="busywaitmicroc">
-<h2><a name="busywaitmicroc">BusyWaitMicroC</a></h2>
+<div class="section">
+<h2><a id="busywaitmicroc" name="busywaitmicroc">BusyWaitMicroC</a></h2>
<pre class="literal-block">
configuration BusyWaitMicroC
{
inefficient or insufficiently precise.</p>
</div>
</div>
-<div class="section" id="utility-components">
-<h1><a name="utility-components">5. Utility components</a></h1>
+<div class="section">
+<h1><a id="utility-components" name="utility-components">5. Utility components</a></h1>
<p>A number of platform independent generic components are provided to
help implementers and advanced users of the TinyOS timer system:</p>
<ul class="simple">
</ul>
<p>Appendices B and C show how these can be used to help implement
the timer HAL and HIL.</p>
-<div class="section" id="alarmtotimerc">
-<h2><a name="alarmtotimerc">AlarmToTimerC</a></h2>
+<div class="section">
+<h2><a id="alarmtotimerc" name="alarmtotimerc">AlarmToTimerC</a></h2>
<p>AlarmToTimerC converts a 32-bit Alarm to a Timer.</p>
<pre class="literal-block">
generic component AlarmToTimerC( typedef precision_tag )
}
</pre>
</div>
-<div class="section" id="busywaitcounterc">
-<h2><a name="busywaitcounterc">BusyWaitCounterC</a></h2>
+<div class="section">
+<h2><a id="busywaitcounterc" name="busywaitcounterc">BusyWaitCounterC</a></h2>
<p>BusyWaitCounterC uses a Counter to block until a specified amount of
time elapses.</p>
<pre class="literal-block">
}
</pre>
</div>
-<div class="section" id="countertolocaltimec">
-<h2><a name="countertolocaltimec">CounterToLocalTimeC</a></h2>
+<div class="section">
+<h2><a id="countertolocaltimec" name="countertolocaltimec">CounterToLocalTimeC</a></h2>
<p>CounterToLocalTimeC converts from a 32-bit Counter to LocalTime.</p>
<pre class="literal-block">
generic component CounterToLocalTimeC( precision_tag )
}
</pre>
</div>
-<div class="section" id="transformalarmc">
-<h2><a name="transformalarmc">TransformAlarmC</a></h2>
+<div class="section">
+<h2><a id="transformalarmc" name="transformalarmc">TransformAlarmC</a></h2>
<p>TransformAlarmC decreases precision and/or widens an Alarm. An
already widened Counter component is used to help.</p>
<pre class="literal-block">
-generic component TransformAlarmC(
+generic component TransformAlarmC(
typedef to_precision_tag,
typedef to_size_type @integer(),
typedef from_precision_tag,
consistent. No compile errors are generated if the parameters
passed to TransformAlarmC are inconsistent.</p>
</div>
-<div class="section" id="transformcounterc">
-<h2><a name="transformcounterc">TransformCounterC</a></h2>
+<div class="section">
+<h2><a id="transformcounterc" name="transformcounterc">TransformCounterC</a></h2>
<p>TransformCounterC decreases precision and/or widens a Counter.</p>
<pre class="literal-block">
generic component TransformCounterC(
new TransformCounterC( TMilli, uint32_t, T32khz, uint16_t, 5, uint32_t )
</pre>
</div>
-<div class="section" id="virtualizetimerc">
-<h2><a name="virtualizetimerc">VirtualizeTimerC</a></h2>
+<div class="section">
+<h2><a id="virtualizetimerc" name="virtualizetimerc">VirtualizeTimerC</a></h2>
<p>VirtualizeTimerC uses a single Timer to create up to 255 virtual
timers.</p>
<pre class="literal-block">
</pre>
</div>
</div>
-<div class="section" id="implementation">
-<h1><a name="implementation">6. Implementation</a></h1>
+<div class="section">
+<h1><a id="implementation" name="implementation">6. Implementation</a></h1>
<p>The definition of the HIL interfaces are found in <tt class="docutils literal"><span class="pre">tinyos-2.x/tos/lib/timer</span></tt>:</p>
<blockquote>
<ul class="simple">
<li><tt class="docutils literal"><span class="pre">CounterMilli16C.nc</span></tt> provides <tt class="docutils literal"><span class="pre">Counter<TMilli,uint16_t></span></tt></li>
<li><tt class="docutils literal"><span class="pre">CounterMilli32C.nc</span></tt> provides <tt class="docutils literal"><span class="pre">Counter<TMilli,uint32_t></span></tt></li>
<li><tt class="docutils literal"><span class="pre">GpioCaptureC.nc</span></tt></li>
-<li><tt class="docutils literal"><span class="pre">HilTimerMilliC.nc</span></tt> provides <tt class="docutils literal"><span class="pre">LocalTime<TMilli></span></tt> and
+<li><tt class="docutils literal"><span class="pre">HilTimerMilliC.nc</span></tt> provides <tt class="docutils literal"><span class="pre">LocalTime<TMilli></span></tt> and
<tt class="docutils literal"><span class="pre">Timer<TMilli></span> <span class="pre">as</span> <span class="pre">TimerMilli[uint8_t</span> <span class="pre">num]</span></tt></li>
<li><tt class="docutils literal"><span class="pre">Msp430AlarmC.nc</span></tt> is generic and converts an MSP430 timer to a 16-bit Alarm</li>
<li><tt class="docutils literal"><span class="pre">Msp430Capture.nc</span></tt> HPL interface definition for MSP430 timer captures</li>
<tt class="docutils literal"><span class="pre">tinyos-2.x/tos/chips/atm128/timer</span></tt> and
<tt class="docutils literal"><span class="pre">tinyos-2.x/tos/chips/pxa27x/timer</span></tt> respectively.</p>
</div>
-<div class="section" id="author-s-address">
-<h1><a name="author-s-address">7. Author's Address</a></h1>
+<div class="section">
+<h1><a id="author-s-address" name="author-s-address">7. Author's Address</a></h1>
<div class="line-block">
<div class="line">Cory Sharp</div>
<div class="line">Moteiv Corporation</div>
<div class="line">email - <a class="reference" href="mailto:david.e.gay@intel.com">david.e.gay@intel.com</a></div>
</div>
</div>
-<div class="section" id="appendix-a-timer-hardware-on-various-microcontrollers">
-<h1><a name="appendix-a-timer-hardware-on-various-microcontrollers">Appendix A: Timer hardware on various microcontrollers</a></h1>
+<div class="section">
+<h1><a id="appendix-a-timer-hardware-on-various-microcontrollers" name="appendix-a-timer-hardware-on-various-microcontrollers">Appendix A: Timer hardware on various microcontrollers</a></h1>
<blockquote>
<ol class="loweralpha simple">
<li>Atmega128</li>
</blockquote>
</blockquote>
</div>
-<div class="section" id="appendix-b-a-microcontroller-atmega-128-timer-subsystem">
-<h1><a name="appendix-b-a-microcontroller-atmega-128-timer-subsystem">Appendix B: a microcontroller: Atmega 128 timer subsystem</a></h1>
+<div class="section">
+<h1><a id="appendix-b-a-microcontroller-atmega-128-timer-subsystem" name="appendix-b-a-microcontroller-atmega-128-timer-subsystem">Appendix B: a microcontroller: Atmega 128 timer subsystem</a></h1>
<p>The Atmega128 exposes its four timers through a common set of interfaces:</p>
<blockquote>
<ul class="simple">
async command bool isOn(); //<! Is overflow interrupt on?
/// Clock initialization interface
- async command void off(); //<! Turn off the clock
+ async command void off(); //<! Turn off the clock
async command void setScale( uint8_t scale); //<! Turn on the clock
async command uint8_t getScale(); //<! Get prescaler setting
}
/// Interrupt signals
async event void captured(size_type t); //<! Signalled on capture int
- /// Interrupt flag utilites: Bit level set/clr
+ /// Interrupt flag utilites: Bit level set/clr
async command void reset(); //<! Clear the capture interrupt flag
async command void start(); //<! Enable the capture interrupt
async command void stop(); //<! Turn off capture interrupts
another value cause a compile-time error. This is achieved as follows (code
from the implementation of <tt class="docutils literal"><span class="pre">HplAtm128Timer1C</span></tt>)</p>
<pre class="literal-block">
-Compare[0] = HplAtm128Timer1P.CompareA;
+Compare[0] = HplAtm128Timer1P.CompareA;
Compare[1] = HplAtm128Timer1P.CompareB;
Compare[2] = HplAtm128Timer1P.CompareC;
</pre>
<p>which builds a 32-bit alarm and timer over timer 0. divider is used
to initialise the timer0 scaling factor.</p>
</div>
-<div class="section" id="appendix-c-a-mote-mica-family-timer-subsystem">
-<h1><a name="appendix-c-a-mote-mica-family-timer-subsystem">Appendix C: a mote: Mica family timer subsystem</a></h1>
+<div class="section">
+<h1><a id="appendix-c-a-mote-mica-family-timer-subsystem" name="appendix-c-a-mote-mica-family-timer-subsystem">Appendix C: a mote: Mica family timer subsystem</a></h1>
<p>Members of the mica family (mica2, mica2dot, micaz) use the Atmega128
microprocessor and have external crystals at 4 or 7.37MHz. Additionally,
they can be run from an internal oscillator at 1, 2, 4, or 8 MHz. The
<li><p class="first">Timer 1: the 16-bit hardware timer 1 is set to run at 1MHz if possible.
However, the set of dividers for timer 1 is limited to 1, 8,
64, 256 and 1024. So, when clocked at 2 or 4MHz, a divider of 1 is
-selected and timer 1 runs at 2 or 4MHz. To reflect this fact, the
+selected and timer 1 runs at 2 or 4MHz. To reflect this fact, the
HAL components exposing timer 1 are named <tt class="docutils literal"><span class="pre">CounterOne16C</span></tt> and
<tt class="docutils literal"><span class="pre">AlarmOne16C</span></tt> (rather than the <tt class="docutils literal"><span class="pre">CounterMicro16C</span></tt> <tt class="docutils literal"><span class="pre">AlarmMicro16C</span></tt>
as suggested in Section 3).</p>
<p>32-bit microsecond Counters and Alarms, named <tt class="docutils literal"><span class="pre">CounterMicro32C</span></tt> and
<tt class="docutils literal"><span class="pre">AlarmMicro32C</span></tt>, are created from <tt class="docutils literal"><span class="pre">CounterOne16C</span></tt> and
-<tt class="docutils literal"><span class="pre">AlarmOne16C</span></tt> using the TransformAlarmC and TransformCounterC
+<tt class="docutils literal"><span class="pre">AlarmOne16C</span></tt> using the TransformAlarmC and TransformCounterC
utility components.</p>
<p>Three compare registers are available on timer1, so up to three instances
of <tt class="docutils literal"><span class="pre">AlarmOne16C</span></tt> and/or <tt class="docutils literal"><span class="pre">AlarmMicro32C</span></tt> can be created. The timing
<li><p class="first">Timer 3: the 16-bit hardware timer 3 is set to run at a rate close to
32768Hz, if possible. As with timer 1, the limited set of dividers makes
this impossible at some clock frequencies, so the 16-bit timer 3 HAL
-components are named <tt class="docutils literal"><span class="pre">CounterThree16C</span></tt> and <tt class="docutils literal"><span class="pre">AlarmThree16C</span></tt>. As
+components are named <tt class="docutils literal"><span class="pre">CounterThree16C</span></tt> and <tt class="docutils literal"><span class="pre">AlarmThree16C</span></tt>. As
with timer 1, the rate of timer 3 is adjusted in software to
build 32-bit counter and 32-bit alarms, giving components
<tt class="docutils literal"><span class="pre">Counter32khz32C</span></tt> and <tt class="docutils literal"><span class="pre">Alarm32khz32C</span></tt>. As with timer 1, three compare
<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.1: http://docutils.sourceforge.net/" />
+<meta name="generator" content="Docutils 0.4: http://docutils.sourceforge.net/" />
<title>Power Management of Non-Virtualised Devices</title>
<meta name="author" content="Kevin Klues, Vlado Handziski, Jan-Hinrich Hauer, Phil Levis" />
<style type="text/css">
<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.1: http://docutils.sourceforge.net/" />
+<meta name="generator" content="Docutils 0.4: http://docutils.sourceforge.net/" />
<title>Packet Protocols</title>
<meta name="author" content="Philip Levis" />
<style type="text/css">
<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.1: http://docutils.sourceforge.net/" />
+<meta name="generator" content="Docutils 0.4: http://docutils.sourceforge.net/" />
<title>Dissemination of Small Values</title>
<meta name="author" content="Philip Levis and Gilman Tolle" />
<style type="text/css">
<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.1: http://docutils.sourceforge.net/" />
+<meta name="generator" content="Docutils 0.4: http://docutils.sourceforge.net/" />
<title>Collection</title>
<meta name="author" content="Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, and Philip Levis" />
<style type="text/css">
<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>
+<td>Final</td></tr>
<tr class="field"><th class="docinfo-name">TinyOS-Version:</th><td class="field-body">> 2.1</td>
</tr>
<tr><th class="docinfo-name">Author:</th>
<div class="section">
<h1><a id="abstract" name="abstract">Abstract</a></h1>
<p>The memo documents the interfaces, components, and semantics used by
-collection protocol in TinyOS 2.x. Collection provides a best-effort,
-multihop delivery of packets to the root of a tree. There may be
-multiple tree roots in a network, and in this case the semantics
-are <em>anycast</em> delivery to at least one of the roots. A node sending
-a packet does not specify which root the packet is destined to.</p>
+the collection protocols in TinyOS 2.x. Collection provides
+best-effort, multihop delivery of packets to one of a set of
+collection points. There may be multiple collection points in a
+network, and in this case the semantics are <em>anycast</em> delivery to at
+least one of the collection points. A node sending a packet does not
+specify which of the collection points the packet is destined to. The
+union of the paths from each node to one or more of the collection
+points forms a set of trees, and in this document we assume that
+collection points are the roots of these trees.</p>
</div>
<div class="section">
<h1><a id="introduction" name="introduction">1. Introduction</a></h1>
it. Sometimes, depending on the form of data collection, systems need
to be able to inspect packets as they go by, either to gather
statistics, compute aggregates, or suppress redundant transmissions.</p>
-<p>Collection provides a best-effort, multihop delivery of packets to one
-of a network's tree roots: it is an <em>anycast</em> protocol. The semantics
-is that the protocol will make a reasonable effort to deliver the
-message to at least one of the roots in the network. By picking a
-parent node, a collection protocol inductively joins the tree its
-parent has joined. Delivery is best effort, and there can be
-duplicates delivered to one or more roots. Collection provides no
-ordering guarantees. Collection does not provide real-time guarantees,
-although specific implementations may extend the basic functionality
-to do so.</p>
+<p>Collection provides best-effort, multihop delivery of packets to one
+of a network's tree roots: it is an <em>anycast</em> protocol. The
+semantics are that the protocol will make a reasonable effort to
+deliver the message to at least one of the roots in the network. By
+picking a parent node, a node implementing the collection protocol
+inductively joins the tree its parent has joined. Delivery is best
+effort, and there can be duplicates delivered to one or more roots.
+Collection provides no ordering or real-time guarantees, although
+specific implementations may extend the basic functionality to do
+so.</p>
<p>Given the limited state that nodes can store and a general need for
distributed tree building algorithms, collection protocols encounter
several challenges. These challenges are not unique to collection
<li>Loop detection, for when a node selects one of its descendants as
a next hop.</li>
<li>Duplicate suppression, detecting and dealing with lost
-acknowledgments causing packets to replicate in the network,
-wasting capacity.</li>
+acknowledgments that can cause packets to replicate in the
+network, wasting capacity.</li>
<li>Link estimation, evaluating the link quality to single-hop
neighbors.</li>
<li>Self-interference, preventing forwarding packets along the route
</div>
<div class="section">
<h1><a id="collection-interfaces" name="collection-interfaces">2. Collection interfaces</a></h1>
-<p>A node can perform four different roles in collection: sender,
-snooper, in-network processor, and receiver/root. Depending on their
-role, the nodes use different interfaces to interact with the
-collection component.</p>
+<p>A node can perform four different roles in collection: sender (or
+source), snooper, in-network processor, and receiver (or
+root). Depending on their role, the nodes use different interfaces to
+interact with the collection component.</p>
<p>The collection infrastructure can be multiplexed among independent
-applications, by means of a collection identifier. While data traffic
-in the protocol is multiplexed through these identifiers, control
-traffic is not: all data traffic uses the same routing topology.</p>
+applications, by means of a collection identifier. The collection
+identifier is used to identify different data traffic at the sender,
+intermediate-nodes, or the receiver, much like port number in TCP. All
+data traffic, regardless of the collection identifier, use the same
+routing topology.</p>
<p>The nodes that generate data to be sent to the root are <em>senders</em>.
Senders use the Send interface [<a class="reference" href="#id1">1</a>] to send data to the root of
the collection tree. The collection identifier is specified as a
snoopers use the Receive interface [<a class="reference" href="#id1">1</a>] to receive a snooped
message. The collection identifier is specified as a parameter
to Receive during instantiation.</p>
-<p>The nodes can process a packet that are in transit. These in-network
+<p>The nodes can process a packet that is in transit. These in-network
<em>processors</em> use the Intercept interface to receive and update a
packet. The collection identifier is specified as a parameter to
Intercept during instantiation. The Intercept interface has this
use the Receive interface [<a class="reference" href="#id1">1</a>] to receive a message delivered by
collection. The collection identifier is specified as a parameter to
Receive during instantiation.</p>
-<p>The set of all roots and the paths that
-lead to them form the collection routing infrastructure in the network.
-For any connected set of nodes implementing the collection protocol
-there is only one collection infrastructure, <em>i.e.</em>, all roots in this
-set active at the same time are part of the same infrastructure.</p>
+<p>The set of all roots and the paths that lead to them form the
+collection routing infrastructure in the network. For any connected
+set of nodes implementing the collection protocol there is only one
+collection infrastructure, <em>i.e.</em>, all roots in this set active at the
+same time are part of the same infrastructure.</p>
<p>The RootControl interface configures whether a node is a
root:</p>
<pre class="literal-block">
command bool isRoot();
}
</pre>
-<p>Both commands MUST return SUCCESS if the node is now in the specified
-state, and FAIL otherwise. For example, if a node is already a root
-and an application calls RootControl.setRoot(), the call will
+<p>The first two commands MUST return SUCCESS if the node is now in the
+specified state, and FAIL otherwise. For example, if a node is already
+a root and an application calls RootControl.setRoot(), the call will
return SUCCESS. If setRoot() returns SUCCESS, then a subsequent call
-to isRoot() MUST return TRUE. If unsetRoot() returns SUCCESS, then
-a subsequent call to isRoot() MUST return FALSE.</p>
+to isRoot() MUST return TRUE. If unsetRoot() returns SUCCESS, then a
+subsequent call to isRoot() MUST return FALSE.</p>
</div>
<div class="section">
<h1><a id="collection-services" name="collection-services">3 Collection Services</a></h1>
}
}
</pre>
-<p>CollectionC MAY have additional interfaces. These additional
-interfaces MUST have default functions on all outgoing invocations
-(commands for uses, events for provides) of those interfaces so that
-it can operate properly if they are not wired.</p>
+<p>CollectionC MAY have additional interfaces. All outgoing invocations
+(commands for uses, events for provides) of those interfaces MUST have
+default functions. Those default functions enable CollectionC to
+operate properly even when the additional interfaces are not wired.</p>
<p>Components SHOULD NOT wire to CollectionC.Send. The generic
component CollectionSenderC (described in section 3.1) provides
a virtualized sending interface.</p>
protocol operating on top of collection, in the same way that
different am_id_t values represent different protocols operating on
top of active messages. All packets sent with a particular
-collection_id_t generally have the same payload format, so that
+collection_id_t generally SHOULD have the same payload format, so that
snoopers, intercepters, and receivers can parse them properly.</p>
<p>ColletionC MUST NOT signal Receive.receive on non-root
-nodes. CollectionC MAY signal Receive.receive on a root node when a
-data packet successfully arrives at that node. If a root node calls
-Send, CollectionC MUST treat it as it if were a received packet. Note
-that the buffer swapping semantics of Receive.receive, when combined
-with the pass semantics of Send, require that CollectionC make a copy
-of the buffer if it signals Receive.receive.</p>
+nodes. CollectionC MUST signal Receive.receive on a root node when a
+unique (non-duplicate) data packet successfully arrives at that
+node. It MAY signal Receive.receive when a duplicate data packet
+successfully arrives. If a root node calls Send, CollectionC MUST
+treat it as it if were a received packet. Note that the buffer
+swapping semantics of Receive.receive, when combined with the pass
+semantics of Send, require that CollectionC make a copy of the buffer
+if it signals Receive.receive.</p>
<p>If CollectionC receives a data packet to forward and it is not a root
-node, it MAY signal Intercept.forward.</p>
-<p>If CollectionC receives a data packet that a different node
-is supposed to forward, it MAY signal Snoop.receive.</p>
+node, it MAY signal Intercept.forward. CollectionC MAY signal
+Snoop.receive when it hears a packet which a different node is
+supposed to forward. For any given packet it receives, CollectionC
+MUST NOT signal more than one of the Snoop.receive, Receive.receive,
+and Intercept.forward events.</p>
<p>RootControl allows a node to be made a collection tree root.
CollectionC SHOULD NOT configure a node as a root by default.</p>
<p>Packet and CollectionPacket allow components to access collection
<div class="line">Anders Egeskov Petersen</div>
<div class="line">University of Copenhagen, Dept. of Computer Science</div>
<div class="line">Universitetsparken 1</div>
-<div class="line">DK-2100 København Ø</div>
+<div class="line">DK-2100 K¯benhavn ÿ</div>
<div class="line">Denmark</div>
<div class="line"><br /></div>
<div class="line">Sidsel Jensen</div>
<div class="line">University of Copenhagen, Dept. of Computer Science</div>
<div class="line">Universitetsparken 1</div>
-<div class="line">DK-2100 København Ø</div>
+<div class="line">DK-2100 K¯benhavn ÿ</div>
<div class="line">Denmark</div>
<div class="line"><br /></div>
<div class="line">email - <a class="reference" href="mailto:purps@diku.dk">purps@diku.dk</a></div>
<div class="line">Martin Leoold</div>
<div class="line">University of Copenhagen, Dept. of Computer Science</div>
<div class="line">Universitetsparken 1</div>
-<div class="line">DK-2100 København Ø</div>
+<div class="line">DK-2100 K¯benhavn ÿ</div>
<div class="line">Denmark</div>
<div class="line"><br /></div>
<div class="line">Phone +45 3532 1464</div>
<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>
+<td>Final</td></tr>
+<tr class="field"><th class="docinfo-name">TinyOS-Version:</th><td class="field-body">> 2.1</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.8</td>
+<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.15</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2007-02-28</td>
+<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2009-01-16</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>
</div>
<div class="section">
<h1><a id="introduction" name="introduction">1. Introduction</a></h1>
+<p>A collection protocol delivers data to one of possibly several data
+sinks, providing a many-to-one network layer. Collection is a
+fundamental component of most sensor network applications. The
+Collection Tree Protocol (CTP) is a reference Collection protocol in
+TinyOS 2.x. The users use Collection interfaces described in TEP 119
+<a class="footnote-reference" href="#id8" id="id1" name="id1">[3]</a> to use CTP in their applications.</p>
+<p>In this TEP, after a brief discussion of Collection and CTP, we
+specify the CTP routing and data frames. CTP uses routing frames to
+update and build collection tree in the network. CTP uses data frames
+to deliver application payload to the sink and to probe topology
+inconsistencies.</p>
+<p>All fields in this specification are in network byte order.</p>
</div>
<div class="section">
<h1><a id="assumptions-and-limitations" name="assumptions-and-limitations">2. Assumptions and Limitations</a></h1>
<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>
+<li>Has single-hop 16-bit 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>
+<p>CTP has several mechanisms in order to achieve high delivery
+reliability, but it does not promise 100% reliable delivery. It is a
+best effort protocol.</p>
+<p>CTP is designed for relatively low traffic rates such that there is
+enough space in the channel to transmit and receive routing frames
+even when the network is forwarding collection data
+frames. Bandwidth-limited systems or high data rate applications might
+benefit from a different protocol, which can, for example, pack
+multiple small frames into a single data-link packet or employ rate
+control mechanisms.</p>
</div>
<div class="section">
<h1><a id="collection-and-ctp" name="collection-and-ctp">3. Collection and CTP</a></h1>
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>
+ETX values as 16-bit decimal fixed-point real numbers with a precision
+of tenths. An ETX value of 45, for example, represents an ETX of 4.5,
+while an ETX value of 10 represents an ETX of 1.</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
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>
+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. CTP keeps a small cache of packet signature for the
+packets it has seen to detect packet duplicates. When a new packet
+arrives, if its signature results in cache hit, CTP drops the packet
+because it is a duplicate.</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
<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
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-|P|C| 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 ...
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
</pre>
<p>Field definitions are as follows:</p>
<blockquote>
<ul class="simple">
-<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>P: Routing pull. The P bit allows nodes to request routing information from other nodes. If the unicast destination of the data frame with a valid route hears a packet with the P bit set, it SHOULD transmit a routing frame in the near future. Nodes other than the link-layer destination of the data frame MAY respond to the P bit in the data frame.</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. A node forwarding a data frame MUST NOT modify the data payload.</li>
+<li>data: the data payload, of zero or more bytes. A node forwarding a data frame MUST NOT modify the data payload. The length of the data field is computed by subtracting the size of the CTP header from the size of the link layer payload provided by the link layer.</li>
</ul>
</blockquote>
<p>Together, the origin, seqno and collect_id fields denote a unique
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 it
-will route succesfully in the presence of transient loops unless the
+will route successfully 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>
<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
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-|P|C| 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 |
+-+-+-+-+-+-+-+-+
</pre>
<p>The fields are as follows:</p>
<blockquote>
<ul class="simple">
-<li>P: Same as data frame.</li>
+<li>P: Same as data frame with one difference: Routing frames are broadcast so multiple nodes respond to the P bit in the routing 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>
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>
+<p>A node MUST send CTP routing frames as broadcast messages.</p>
</div>
<div class="section">
<h1><a id="implementation" name="implementation">6. Implementation</a></h1>
<div class="section">
<h2><a id="link-estimation" 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
+periodic LEEP <a class="footnote-reference" href="#id6" id="id2" name="id2">[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
+trickle dissemination protocol <a class="footnote-reference" href="#id7" id="id3" name="id3">[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's routing ETX increases by >= 1 transmission</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
+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.</p>
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>
+<p>The component <tt class="docutils literal"><span class="pre">tos/lib/net/4bitle/LinkEstimatorP</span></tt> implements the
+link estimator. It couples LEEP-based and data-based estimates as
+described in <a class="footnote-reference" href="#id9" id="id4" name="id4">[4]</a>.</p>
</div>
<div class="section">
<h2><a id="routing-engine" name="routing-engine">6.2 Routing Engine</a></h2>
<div class="section">
<h2><a id="forwarding-engine" 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>
+forwarding engine. It has five responsibilities:</p>
<blockquote>
<ol class="arabic simple">
<li>Transmitting packets to the next hop, retransmitting when necessary, and
<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 class="line"><br /></div>
+<div class="line"><br /></div>
+<div class="line">Alec Woo</div>
+<div class="line">Arch Rock Corporation</div>
+<div class="line">501 2nd St. Ste 410</div>
+<div class="line">San Francisco, CA 94107-4132</div>
+<div class="line"><br /></div>
+<div class="line">email - <a class="reference" href="mailto:awoo@archrock.com">awoo@archrock.com</a></div>
+<div class="line"><br /></div>
+<div class="line"><br /></div>
+<div class="line">Sukun Kim</div>
+<div class="line">Samsung Electronics</div>
+<div class="line">416 Maetan-3-dong, Yeongtong-Gu</div>
+<div class="line">Suwon, Gyeonggi 443-742</div>
+<div class="line">Korea, Republic of</div>
+<div class="line"><br /></div>
+<div class="line">phone - +82 10 3065 6836</div>
+<div class="line">email - <a class="reference" href="mailto:sukun.kim@samsung.com">sukun.kim@samsung.com</a></div>
</div>
</div>
<div class="section">
-<h1><a id="id3" name="id3">8. Citations</a></h1>
-<table class="docutils footnote" frame="void" id="id4" rules="none">
+<h1><a id="id5" name="id5">8. Citations</a></h1>
+<table class="docutils footnote" frame="void" id="id6" 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>
+<tr><td class="label"><a class="fn-backref" href="#id2" name="id6">[1]</a></td><td>TEP 124: Link Estimation Extension Protocol</td></tr>
</tbody>
</table>
-<table class="docutils footnote" frame="void" id="id5" rules="none">
+<table class="docutils footnote" frame="void" id="id7" 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
+<tr><td class="label"><a class="fn-backref" href="#id3" name="id7">[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>
+<table class="docutils footnote" frame="void" id="id8" rules="none">
+<colgroup><col class="label" /><col /></colgroup>
+<tbody valign="top">
+<tr><td class="label"><a class="fn-backref" href="#id1" name="id8">[3]</a></td><td>TEP 119: Collection.</td></tr>
+</tbody>
+</table>
+<table class="docutils footnote" frame="void" id="id9" rules="none">
+<colgroup><col class="label" /><col /></colgroup>
+<tbody valign="top">
+<tr><td class="label"><a class="fn-backref" href="#id4" name="id9">[4]</a></td><td>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.</td></tr>
+</tbody>
+</table>
</div>
</div>
</body>
<td>Omprakash Gnawali</td></tr>
<tr class="field"><th class="docinfo-name">Draft-Created:</th><td class="field-body">05-Feb-2006</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.4</td>
+<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.9</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2007-02-28</td>
+<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2009-01-31</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>
messages and the total transmitted messages. LEEP appends in-bound
packet reception rate (PRR) estimates to packets. Other nodes hearing
these packets can combine the in-bound PRR values with their own
-in-bound values to compute bi-directional link quality.</p>
+in-bound values to compute bi-directional link quality. Thus, LEEP is
+a discovery and link table bootstrapping mechanism. The link quality
+is often fine-tuned using different mechanisms.</p>
+<p>Link quality estimates obtained using LEEP are often used as a
+bootstrapping values in the link quality table; data transmission
+statistics can later be used to make these estimates more accurate.</p>
</div>
<div class="section">
<h1><a id="definitions" name="definitions">2. Definitions</a></h1>
<div class="section">
-<h2><a id="link-quality" name="link-quality">2.1 Link Quality</a></h2>
-<p>The link quality between a directed node pair (A,B) is the probability
-that a packet transmitted by A will be successfully received by B. The
-bidirectional link quality of an undirected node pair (A,B) is the
-product of the link quality of (A,B) and (B,A). This definition
-assumes independent link losses. It also includes the case when
-the link quality of (A,B) and (B,A) are different; this can occur
-due to local interference or noise.</p>
-</div>
-<div class="section">
-<h2><a id="in-bound-link-quality" name="in-bound-link-quality">2.2 In-bound Link Quality</a></h2>
+<h2><a id="in-bound-link-quality" name="in-bound-link-quality">2.1 In-bound Link Quality</a></h2>
<p>In a node pair (A,B), with B as the node of reference, in-bound link
quality is a value in the range of 0 to 255 that describes the quality
of the link from A to B estimated by B by counting the successfully
-received packets from A among all the transmitted packets or using
-link quality indicators such as LQI and RSSI provided by the radio on
-the node B, or some other methods.</p>
+received packets from A among all the packets transmitted by A. Thus,
+in-bound link quality is the empirical probability that a packet will
+be successfully received on a given link. A value of 255 represents a
+probability of 1 and a value of 0 represents a probability of 0 of
+successfully receiving a packet on a given link.</p>
</div>
<div class="section">
-<h2><a id="out-bound-link-quality" name="out-bound-link-quality">2.3 Out-bound Link Quality</a></h2>
+<h2><a id="out-bound-link-quality" name="out-bound-link-quality">2.2 Out-bound Link Quality</a></h2>
<p>In a node pair (A,B), with B as the node of reference, out-bound link
quality is defined as the quality of the link from B to A. B can
determine the out-bound link quality if A advertises its in-bound link
link qualities.</p>
</div>
<div class="section">
+<h2><a id="bi-directional-link-quality" name="bi-directional-link-quality">2.3 Bi-directional Link Quality</a></h2>
+<p>LEEP does not define or compute bi-directional link quality. LEEP
+provides a way to exchange sufficient information to compute in-bound
+and out-bound link qualities. These two link qualities can be used to
+compute the bi-directional link quality. One popular way to define the
+bi-directional link quality between a node pair (A,B) as the
+probability that a packet transmitted by A will be successfully
+received and acknowledged by B. This approach computes the
+bi-directional link quality of a node pair (A,B) as the product of the
+link quality of (A,B) and (B,A).</p>
+</div>
+<div class="section">
<h2><a id="link-information-entry" name="link-information-entry">2.4 Link Information Entry</a></h2>
<p>Link Information Entry created by node k is a tuple (n,q) where q is
the in-bound link quality from node n to k.</p>
entries describing the in-bound link qualities for a subset of its
neighbors. The Link Information entry on the LEEP frame allows the
receiver node to find the out-bound link quality to the transmitter
-node identified by the data link source address.</p>
+node identified by the data link source address. Thus, LEEP is also a
+way for nodes to discover new nodes and links in the network.</p>
+<p>Link quality estimation is inherently imperfect - data transmission
+and link quality estimation might be done at different timescales. The
+PRR for LEEP frames (broadcast) and data frames (unicast) might be
+different. So LEEP is better used as a link quality bootstrapping
+mechanism. The link quality estimate can be made more accurate later
+using data transmission statistics.</p>
</div>
<div class="section">
<h2><a id="leep-frame" name="leep-frame">3.3 LEEP Frame</a></h2>
<p>The following diagram shows the LEEP header format:</p>
<pre class="literal-block">
1
- 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-|nentry | rsrvd | seqno |
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+|nentry | rsrvd | seqno |
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
</pre>
<p>Field definitions:</p>
<blockquote>
<p>The following diagram shows the Link Information Entry format:</p>
<pre class="literal-block">
1
- 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-| node id |
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+| node id |
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| link quality |
+-+-+-+-+-+-+-+-+
</pre>
possible data link frame. If there is still not enough room to fit all
the Link Information entries, it uses a round-robin policy to select
the entries to be exchanged that could not fit in the previous LEEP
-frame. The LEEP frames are transmitted whenever the CTP <a class="footnote-reference" href="#id4" id="id3" name="id3">[1]</a> beacons,
+frame. The LEEP frames are transmitted whenever the CTP <a class="footnote-reference" href="#id5" id="id3" name="id3">[1]</a> beacons,
sent as a LEEP payload, are sent.</p>
+<p>Another reference implementation resides in
+<tt class="docutils literal"><span class="pre">tinyos-2.x/tos/lib/net/4bitle</span></tt>. This implementation is described in
+detail in <a class="footnote-reference" href="#id6" id="id4" name="id4">[2]</a>.</p>
</div>
<div class="section">
<h1><a id="author-s-address" name="author-s-address">5. Author's Address</a></h1>
</div>
<div class="section">
<h1><a id="citations" name="citations">6. Citations</a></h1>
-<table class="docutils footnote" frame="void" id="id4" rules="none">
+<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="#id3" name="id5">[1]</a></td><td>TEP 123: The Collection Tree Protocol.</td></tr>
+</tbody>
+</table>
+<table class="docutils footnote" frame="void" id="id6" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
-<tr><td class="label"><a class="fn-backref" href="#id3" name="id4">[1]</a></td><td>TEP 123: The Collection Tree Protocol.</td></tr>
+<tr><td class="label"><a class="fn-backref" href="#id4" name="id6">[2]</a></td><td>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.</td></tr>
</tbody>
</table>
</div>
<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.1: http://docutils.sourceforge.net/" />
+<meta name="generator" content="Docutils 0.4: http://docutils.sourceforge.net/" />
<title>TinyOS 802.15.4 Frames</title>
<meta name="author" content="Jonathan Hui, Philip Levis, and David Moss" />
<style type="text/css">
<td>Jonathan Hui, Philip Levis, and David Moss</td></tr>
<tr class="field"><th class="docinfo-name">Draft-Created:</th><td class="field-body">2-Feb-2007</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.5</td>
+<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.6</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2008-06-16</td>
+<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2008-06-20</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>
| 802.15.4 Header | 6lowpan | AM type | data | 802.15.4 CRC |
+-------------------+---------+------------------------------+--------------+
</pre>
-<p>AM type is the same as in a T-frame. 6lowpan is the NALP code to identify
-this as a TinyOS packet. NALP codes must be in the range of 0-63.
-TinyOS uses code 63.</p>
+<p>AM type is the same as in a T-frame. 6lowpan is the NALP code to
+identify this as a TinyOS packet. NALP codes must be in the range of
+0-63. TinyOS uses code 63 (0x3F).</p>
<p>The AM type 63 is reserved for both T-Frames and I-Frames. A TinyOS
program MUST NOT use it.</p>
</div>
<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.1: http://docutils.sourceforge.net/" />
+<meta name="generator" content="Docutils 0.4: http://docutils.sourceforge.net/" />
<title>Creating a New Platform for TinyOS 2.x</title>
<meta name="author" content="Martin Leopold" />
<style type="text/css">
/*
:Author: David Goodger
:Contact: goodger@users.sourceforge.net
-:Date: $Date$
-:Revision: $Revision$
-:Copyright: This stylesheet has been placed in the public domain.
+:date: $Date$
+:version: $Revision$
+:copyright: This stylesheet has been placed in the public domain.
Default cascading style sheet for the HTML output of Docutils.
-
-See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
-customize this style sheet.
*/
-
-/* used to remove borders from tables and images */
-.borderless, table.borderless td, table.borderless th {
- border: 0 }
-
-table.borderless td, table.borderless th {
- /* Override padding for "table.docutils td" with "! important".
- The right padding separates the table cells. */
- padding: 0 0.5em 0 0 ! important }
+body {
+ font-family: Times;
+ font-size: 16px;
+}
.first {
- /* Override more specific margin styles with "! important". */
margin-top: 0 ! important }
-.last, .with-subtitle {
+.last {
margin-bottom: 0 ! important }
.hidden {
blockquote.epigraph {
margin: 2em 5em ; }
-dl.docutils dd {
+dd {
margin-bottom: 0.5em }
-/* Uncomment (and remove this text!) to get bold-faced definition list terms
-dl.docutils dt {
- font-weight: bold }
-*/
-
div.abstract {
margin: 2em 5em }
font-weight: bold ;
text-align: center }
-div.admonition, div.attention, div.caution, div.danger, div.error,
-div.hint, div.important, div.note, div.tip, div.warning {
+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.admonition p.admonition-title, div.hint p.admonition-title,
-div.important p.admonition-title, div.note p.admonition-title,
-div.tip p.admonition-title {
- font-weight: bold ;
- font-family: sans-serif }
-
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 {
font-weight: bold ;
font-family: sans-serif }
-/* Uncomment (and remove this text!) to get reduced vertical space in
- compound paragraphs.
-div.compound .compound-first, div.compound .compound-middle {
- margin-bottom: 0.5em }
-
-div.compound .compound-last, div.compound .compound-middle {
- margin-top: 0.5em }
-*/
+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 ;
font-style: normal }
div.figure {
- margin-left: 2em ;
- margin-right: 2em }
+ margin-left: 2em }
div.footer, div.header {
- clear: both;
font-size: smaller }
div.line-block {
div.sidebar {
margin-left: 1em ;
border: medium outset ;
- padding: 1em ;
+ padding: 0em 1em ;
background-color: #ffffee ;
width: 40% ;
float: right ;
div.topic {
margin: 2em }
-h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
-h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
- margin-top: 0.4em }
+h1 {
+ font-family: Arial, sans-serif;
+ font-size: 20px;
+}
h1.title {
- text-align: center }
+ text-align: center;
+ font-size: 32px;
+}
+
+h2 {
+ font-size: 16px;
+ font-family: Arial, sans-serif;
+}
h2.subtitle {
text-align: center }
-hr.docutils {
- width: 75% }
-
-img.align-left {
- clear: left }
+h3 {
+ font-size: 12px;
+ font-family: Arial, sans-serif;
+}
-img.align-right {
- clear: right }
+hr {
+ width: 75% }
ol.simple, ul.simple {
margin-bottom: 1em }
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 }
+ background-color: #eeeeee;
+ border-color: #000000;
+ border-width: thin;
+ font-size: 14px
+}
span.classifier {
font-family: sans-serif ;
span.option {
white-space: nowrap }
+span.option-argument {
+ font-style: italic }
+
span.pre {
white-space: pre }
span.problematic {
color: red }
-span.section-subtitle {
- /* font-size relative to parent (h1..h6 element) */
- font-size: 80% }
+table {
+ margin-top: 0.5em ;
+ margin-bottom: 0.5em }
table.citation {
- border-left: solid 1px gray;
- margin-left: 1px }
+ border-left: solid thin gray ;
+ padding-left: 0.5ex }
table.docinfo {
- margin: 2em 4em }
-
-table.docutils {
- margin-top: 0.5em ;
- margin-bottom: 0.5em }
+ margin: 2em 4em;
+}
table.footnote {
- border-left: solid 1px black;
- margin-left: 1px }
+ border-left: solid thin black ;
+ padding-left: 0.5ex }
-table.docutils td, table.docutils th,
-table.docinfo td, table.docinfo th {
+td, th {
padding-left: 0.5em ;
padding-right: 0.5em ;
vertical-align: top }
-table.docutils th.field-name, table.docinfo th.docinfo-name {
+th.docinfo-name, th.field-name {
font-weight: bold ;
text-align: left ;
- white-space: nowrap ;
- padding-left: 0 }
+ white-space: nowrap;
+ }
-h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
-h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
+h1 tt, h2 tt, h3 tt, h4 tt, h5 tt, h6 tt {
font-size: 100% }
-tt.docutils {
- background-color: #eeeeee }
+tt {}
ul.auto-toc {
list-style-type: none }
async command void setControl(msp430_compare_control_t control );
async command void setControlAsCompare();
- async command void setControlAsCapture(bool low_to_high);
+ async command void setControlAsCapture(uint8_t cm);
async command void enableEvents();
async command void disableEvents();
-> Sender videre til HplMsp430Usart1C->HplMsp430Usart1P</dd>
<dt>..PXA27</dt>
<dd>Parametriseret m. HplPXA27xUARTP (Init && HplPXA27xUART)
--> init sætter en masse registre og enabler interrupt
+-> init sÃ\8atter en masse registre og enabler interrupt
HalPXA27xSerialP: HplPXA27xUART, Init, noget DMA noget</dd>
</dl>
</div>
<div class="line">Martin Leoold</div>
<div class="line">University of Copenhagen, Dept. of Computer Science</div>
<div class="line">Universitetsparken 1</div>
-<div class="line">DK-2100 København Ø</div>
+<div class="line">DK-2100 K¯benhavn ÿ</div>
<div class="line">Denmark</div>
<div class="line"><br /></div>
<div class="line">Phone +45 3532 1464</div>
<td>Miklos Maroti, Janos Sallai</td></tr>
<tr class="field"><th class="docinfo-name">Draft-Created:</th><td class="field-body">15-May-2008</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.0</td>
+<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.1</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2008-05-15</td>
+<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2008-06-17</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>
<td>Miklos Maroti, Janos Sallai</td></tr>
<tr class="field"><th class="docinfo-name">Draft-Created:</th><td class="field-body">15-May-2008</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.0</td>
+<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.1</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2008-05-15</td>
+<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2008-06-17</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>
/*
:Author: David Goodger
:Contact: goodger@users.sourceforge.net
-:Date: $Date$
-:Revision: $Revision$
-:Copyright: This stylesheet has been placed in the public domain.
+:date: $Date$
+:version: $Revision$
+:copyright: This stylesheet has been placed in the public domain.
Default cascading style sheet for the HTML output of Docutils.
-
-See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
-customize this style sheet.
*/
-
-/* used to remove borders from tables and images */
-.borderless, table.borderless td, table.borderless th {
- border: 0 }
-
-table.borderless td, table.borderless th {
- /* Override padding for "table.docutils td" with "! important".
- The right padding separates the table cells. */
- padding: 0 0.5em 0 0 ! important }
+body {
+ font-family: Times;
+ font-size: 16px;
+}
.first {
- /* Override more specific margin styles with "! important". */
margin-top: 0 ! important }
-.last, .with-subtitle {
+.last {
margin-bottom: 0 ! important }
.hidden {
blockquote.epigraph {
margin: 2em 5em ; }
-dl.docutils dd {
+dd {
margin-bottom: 0.5em }
-/* Uncomment (and remove this text!) to get bold-faced definition list terms
-dl.docutils dt {
- font-weight: bold }
-*/
-
div.abstract {
margin: 2em 5em }
font-weight: bold ;
text-align: center }
-div.admonition, div.attention, div.caution, div.danger, div.error,
-div.hint, div.important, div.note, div.tip, div.warning {
+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.admonition p.admonition-title, div.hint p.admonition-title,
-div.important p.admonition-title, div.note p.admonition-title,
-div.tip p.admonition-title {
- font-weight: bold ;
- font-family: sans-serif }
-
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 {
font-weight: bold ;
font-family: sans-serif }
-/* Uncomment (and remove this text!) to get reduced vertical space in
- compound paragraphs.
-div.compound .compound-first, div.compound .compound-middle {
- margin-bottom: 0.5em }
-
-div.compound .compound-last, div.compound .compound-middle {
- margin-top: 0.5em }
-*/
+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 ;
font-style: normal }
div.figure {
- margin-left: 2em ;
- margin-right: 2em }
+ margin-left: 2em }
div.footer, div.header {
- clear: both;
font-size: smaller }
div.line-block {
div.sidebar {
margin-left: 1em ;
border: medium outset ;
- padding: 1em ;
+ padding: 0em 1em ;
background-color: #ffffee ;
width: 40% ;
float: right ;
div.topic {
margin: 2em }
-h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
-h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
- margin-top: 0.4em }
+h1 {
+ font-family: Arial, sans-serif;
+ font-size: 20px;
+}
h1.title {
- text-align: center }
+ text-align: center;
+ font-size: 32px;
+}
+
+h2 {
+ font-size: 16px;
+ font-family: Arial, sans-serif;
+}
h2.subtitle {
text-align: center }
-hr.docutils {
- width: 75% }
-
-img.align-left {
- clear: left }
+h3 {
+ font-size: 12px;
+ font-family: Arial, sans-serif;
+}
-img.align-right {
- clear: right }
+hr {
+ width: 75% }
ol.simple, ul.simple {
margin-bottom: 1em }
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 }
+ background-color: #eeeeee;
+ border-color: #000000;
+ border-width: thin;
+ font-size: 14px
+}
span.classifier {
font-family: sans-serif ;
span.option {
white-space: nowrap }
+span.option-argument {
+ font-style: italic }
+
span.pre {
white-space: pre }
span.problematic {
color: red }
-span.section-subtitle {
- /* font-size relative to parent (h1..h6 element) */
- font-size: 80% }
+table {
+ margin-top: 0.5em ;
+ margin-bottom: 0.5em }
table.citation {
- border-left: solid 1px gray;
- margin-left: 1px }
+ border-left: solid thin gray ;
+ padding-left: 0.5ex }
table.docinfo {
- margin: 2em 4em }
-
-table.docutils {
- margin-top: 0.5em ;
- margin-bottom: 0.5em }
+ margin: 2em 4em;
+}
table.footnote {
- border-left: solid 1px black;
- margin-left: 1px }
+ border-left: solid thin black ;
+ padding-left: 0.5ex }
-table.docutils td, table.docutils th,
-table.docinfo td, table.docinfo th {
+td, th {
padding-left: 0.5em ;
padding-right: 0.5em ;
vertical-align: top }
-table.docutils th.field-name, table.docinfo th.docinfo-name {
+th.docinfo-name, th.field-name {
font-weight: bold ;
text-align: left ;
- white-space: nowrap ;
- padding-left: 0 }
+ white-space: nowrap;
+ }
-h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
-h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
+h1 tt, h2 tt, h3 tt, h4 tt, h5 tt, h6 tt {
font-size: 100% }
-tt.docutils {
- background-color: #eeeeee }
+tt {}
ul.auto-toc {
list-style-type: none }
<td>Kevin Klues, Chieh-Jan Liang, Jeongyeup Paek, Razvan Musaloiu-E, Ramesh Govindan, Andreas Terzis, Philip Levis</td></tr>
<tr class="field"><th class="docinfo-name">Draft-Created:</th><td class="field-body">13-May-2008</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.3</td>
+<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.1</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2008-05-26</td>
+<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2008-06-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>
</tr>
<tr class="field"><th class="docinfo-name">Group:</th><td class="field-body">Network Protocol Working Group</td>
</tr>
-<tr class="field"><th class="docinfo-name">Type:</th><td class="field-body">Documentary</td>
+<tr class="field"><th class="docinfo-name">Type:</th><td class="field-body">Informational</td>
</tr>
<tr><th class="docinfo-name">Status:</th>
<td>Draft</td></tr>
<td>Omprakash Gnawali</td></tr>
<tr class="field"><th class="docinfo-name">Draft-Created:</th><td class="field-body">19-June-2008</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.1</td>
+<tr class="field"><th class="docinfo-name">Draft-Version:</th><td class="field-body">1.3</td>
</tr>
-<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2008-06-20</td>
+<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2008-06-24</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>
</div>
<div class="section">
<h1><a id="introduction" name="introduction">1. Introduction</a></h1>
-<p>In this TEP, we document the Active Message Type <a class="footnote-reference" href="#id4" id="id3" name="id3">[1]</a> allocations
-in TinyOS 2.1.</p>
+<p>TinyOS network protocols use allocated Active Message Type <a class="citation-reference" href="#tep-116" id="id3" name="id3">[TEP_116]</a>
+to prevent AM ID conflict between different protocols. <a class="citation-reference" href="#tep-4" id="id4" name="id4">[TEP_4]</a>
+describes how AM IDs are allocated for a TinyOS network protocol. In
+this TEP, we document the AM ID allocations in TinyOS 2.1.</p>
+</div>
<div class="section">
-<h2><a id="unreserved-pool-0x80-0xff" name="unreserved-pool-0x80-0xff">2. Unreserved pool (0x80 - 0xFF)</a></h2>
+<h1><a id="unreserved-pool-128-255-0x80-0xff" name="unreserved-pool-128-255-0x80-0xff">2. Unreserved pool 128-255 (0x80 - 0xFF)</a></h1>
<p>The unreserved pool is in the range 128-255 (0x80-0xFF). Applications
distributed with TinyOS use AM IDs in this range. Protocols and
applications in contrib as well as those developed by the community
this range.</p>
</div>
<div class="section">
-<h2><a id="reserved-pool-0x00-0x7f" name="reserved-pool-0x00-0x7f">3. Reserved pool (0x00 - 0x7F)</a></h2>
+<h1><a id="reserved-pool-0-127-0x00-0x7f" name="reserved-pool-0-127-0x00-0x7f">3. Reserved pool 0-127 (0x00 - 0x7F)</a></h1>
<p>The reserved pool is in the range 0-127 (0x00-0x7F). The AM IDs in
this range are used by protocols distributed with TinyOS.</p>
<p>Here is a list of allocations for TinyOS 2.1:</p>
<pre class="literal-block">
-* 0x70 - 0x7F are reserved for collection protocols maintained by
- the Network Protocol Working Group.
+* 0x70 - 0x75 are reserved for collection protocols [TEP_119]_
+ maintained by the Network Protocol Working Group.
- 0x70 - CTP routing beacon and LEEP (''tos/lib/net/ctp'', TEP 119, 123, and 124)
- 0x71 - CTP data packets (''tos/lib/net/ctp'', TEP 119, 123)
- 0x72 - CTP debug messages (''tos/lib/net/ctp'')
- 0x73 - MultiHopLQI routing beacon (''tos/lib/net/lqi'')
- 0x74 - MultiHopLQI data packets (''tos/lib/net/lqi'')
- 0x75 - MultiHopLQI debug messages (''tos/lib/net/lqi'')
+ For CTP (''tos/lib/net/ctp'') [TEP_123]_ and LEEP [TEP_124]_
+ 0x70 - AM_CTP_ROUTING CTP (Routing beacon)
+ 0x71 - AM_CTP_DATA CTP (Data packets)
+ 0x72 - AM_CTP_DEBUG CTP (Debug messages)
-* 0x60 - 0x6F are reserved for dissemination protocols maintained by
- the Network Protocol Working Group.
+ For MultiHopLQI (''tos/lib/net/lqi'')
+ 0x73 - AM_LQI_BEACON_MSG (Routing beacon)
+ 0x74 - AM_LQI_DATA_MSG MultiHopLQI (Data packets)
+ 0x75 - AM_LQI_DEBUG MultiHopLQI (Debug messages)
+
+* 0x60 - 0x62 are reserved for dissemination protocols [TEP_118]_
+ maintained by the Network Protocol Working Group.
- 0x60 - Drip (''tos/lib/net/drip'', TEP 118)
- 0x61 - DIP (''tos/lib/net/dip'', TEP 118)
+ For Drip (''tos/lib/net/drip'')
+ 0x60 - AM_DISSEMINATION_MESSAGE
+ 0x61 - AM_DISSEMINATION_PROBE_MESSAGE
-* 0x50 - 0x5F are reserved for Deluge (''tos/lib/net/Deluge'')
+ For DIP (''tos/lib/net/dip'')
+ 0x62 - AM_DIP
+
+* 0x50 - 0x54 are reserved for Deluge (''tos/lib/net/Deluge'')
maintained by the Network Protocol Working Group.
- 0x50 - AM_DELUGEADVMSG (advertisements)
- 0x51 - AM_DELUGEREQMSG (requests)
- 0x52 - AM_DELUGEDATAMSG (data)
- 0x53 - DELUGE_AM_FLASH_VOL_MANAGER (flash volume manager)
- 0x54 - DELUGE_AM_DELUGE_MANAGER (deluge manger)
+ 0x50 - AM_DELUGEADVMSG (Advertisements)
+ 0x51 - AM_DELUGEREQMSG (Requests)
+ 0x52 - AM_DELUGEDATAMSG (Data)
+ 0x53 - DELUGE_AM_FLASH_VOL_MANAGER (Flash volume manager)
+ 0x54 - DELUGE_AM_DELUGE_MANAGER (Deluge manger)
+
+* 0x3E - AM_TIMESYNCMSG for FTSP (''tos/lib/ftsp'') reserved by the
+ Core Working Group.
-* 0x3F - TinyOS NALP code (TEP 125) reserved by the Core Working
+* 0x3F - TinyOS NALP code [TEP_125]_ reserved by the Core Working
Group.
</pre>
</div>
-</div>
<div class="section">
<h1><a id="author-s-address" name="author-s-address">4. Author's Address</a></h1>
<div class="line-block">
<table class="docutils citation" frame="void" id="tep-4" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
-<tr><td class="label"><a class="fn-backref" href="#id2" name="tep-4">[TEP_4]</a></td><td>TEP 4: Active Message ID Allocation for Network Protocols and Applications</td></tr>
+<tr><td class="label"><a name="tep-4">[TEP_4]</a></td><td><em>(<a class="fn-backref" href="#id2">1</a>, <a class="fn-backref" href="#id4">2</a>)</em> TEP 4: Active Message ID Allocation for Network Protocols and Applications</td></tr>
+</tbody>
+</table>
+<table class="docutils citation" frame="void" id="tep-116" rules="none">
+<colgroup><col class="label" /><col /></colgroup>
+<tbody valign="top">
+<tr><td class="label"><a class="fn-backref" href="#id3" name="tep-116">[TEP_116]</a></td><td>TEP 116: Packet Protocols</td></tr>
+</tbody>
+</table>
+<table class="docutils citation" frame="void" id="tep-118" rules="none">
+<colgroup><col class="label" /><col /></colgroup>
+<tbody valign="top">
+<tr><td class="label"><a name="tep-118">[TEP_118]</a></td><td>TEP 118: Dissemination of Small Values</td></tr>
+</tbody>
+</table>
+<table class="docutils citation" frame="void" id="tep-119" rules="none">
+<colgroup><col class="label" /><col /></colgroup>
+<tbody valign="top">
+<tr><td class="label"><a name="tep-119">[TEP_119]</a></td><td>TEP 119: Collection</td></tr>
+</tbody>
+</table>
+<table class="docutils citation" frame="void" id="tep-123" rules="none">
+<colgroup><col class="label" /><col /></colgroup>
+<tbody valign="top">
+<tr><td class="label"><a name="tep-123">[TEP_123]</a></td><td>TEP 123: The Collection Tree Protocol (CTP)</td></tr>
+</tbody>
+</table>
+<table class="docutils citation" frame="void" id="tep-124" rules="none">
+<colgroup><col class="label" /><col /></colgroup>
+<tbody valign="top">
+<tr><td class="label"><a name="tep-124">[TEP_124]</a></td><td>TEP 124: The Link Estimation Exchange Protocol (LEEP)</td></tr>
</tbody>
</table>
-<table class="docutils footnote" frame="void" id="id4" rules="none">
+<table class="docutils citation" frame="void" id="tep-125" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
-<tr><td class="label"><a class="fn-backref" href="#id3" name="id4">[1]</a></td><td>TEP 116: Packet Protocols</td></tr>
+<tr><td class="label"><a name="tep-125">[TEP_125]</a></td><td>TEP 125: TinyOS 802.15.4 Frames</td></tr>
</tbody>
</table>
</div>
<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.1: http://docutils.sourceforge.net/" />
+<meta name="generator" content="Docutils 0.4: http://docutils.sourceforge.net/" />
<title>Hardware Abstraction Architecture</title>
<meta name="author" content="Vlado Handziski, Joseph Polastre, Jan-Hinrich Hauer, Cory Sharp, Adam Wolisz, David Culler, David Gay" />
<style type="text/css">
<tr class="field"><th class="docinfo-name">Type:</th><td class="field-body">Best Current Practice</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>
+<td>Final</td></tr>
+<tr class="field"><th class="docinfo-name">TinyOS-Version:</th><td class="field-body">> 2.1</td>
</tr>
<tr><th class="docinfo-name">Author:</th>
<td>Omprakash Gnawali</td></tr>
<tr class="field"><th class="docinfo-name">Draft-Created:</th><td class="field-body">07-May-2008</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">2008-06-20</td>
+<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2008-11-04</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>
</div>
<div class="section">
<h1><a id="introduction" name="introduction">1. Introduction</a></h1>
-<p>In order to document the Active Message Type <a class="footnote-reference" href="#id3" id="id2" name="id2">[1]</a>, also known as
+<p>In order to document the Active Message Type <a class="citation-reference" href="#tep-116" id="id2" name="id2">[TEP_116]</a>, also known as
Active Message Identifier (AM ID), used by the protocols and to
prevent AM ID conflicts between applications and protocols distributed
with TinyOS 2.x, the application and protocol developers MUST use AM
Network Protocol Working Group with the following information:
* Working Group responsible for the protocol
* Name of the protocol and relevant TEPs
-* Location of the protocol in TinyOS source tree</p>
-<p>Upon receiving this information, the chair of the Network Protocol
-Working Group will allocate an AM ID and document the allocation.</p>
+* Location of the protocol in TinyOS source tree
+* Number of AM IDs requested and description of each ID
+* Specific AM ID request (only if necessary)</p>
+<p>Upon receiving this request, the chair of the Network Protocol Working
+Group will allocate the AM ID(s) and document the allocation. If the
+request is made for a specific AM ID, the chair of the Network
+Protocol Work Group will try to accommodate that request.</p>
</div>
<div class="section">
<h1><a id="reclaiming-the-am-id-allocation" name="reclaiming-the-am-id-allocation">4. Reclaiming the AM ID Allocation</a></h1>
<h1><a id="documenting-allocations-and-deallocations" name="documenting-allocations-and-deallocations">5. Documenting allocations and deallocations</a></h1>
<p>For each TinyOS 2.x release that introduces a new protocol or use of a
new AM ID, the chair of the Network Protocol Working Group creates a
-new TEP that lists all the AM ID allocations for that release.</p>
+new Informational TEP that lists all the AM ID allocations for that
+release. The TEP is finalized at the time of the release. <a class="citation-reference" href="#tep-135" id="id3" name="id3">[TEP_135]</a>
+documents the AM IDs allocated for TinyOS 2.1.</p>
</div>
<div class="section">
<h1><a id="acknowledgments" name="acknowledgments">6. Acknowledgments</a></h1>
<tr><td class="label"><a class="fn-backref" href="#id1" name="tep-1">[TEP_1]</a></td><td>TEP 1: TEP Structure and Keywords</td></tr>
</tbody>
</table>
-<table class="docutils footnote" frame="void" id="id3" rules="none">
+<table class="docutils citation" frame="void" id="tep-116" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
-<tr><td class="label"><a class="fn-backref" href="#id2" name="id3">[1]</a></td><td>TEP 116: Packet Protocols</td></tr>
+<tr><td class="label"><a class="fn-backref" href="#id2" name="tep-116">[TEP_116]</a></td><td>TEP 116: Packet Protocols</td></tr>
+</tbody>
+</table>
+<table class="docutils citation" frame="void" id="tep-135" rules="none">
+<colgroup><col class="label" /><col /></colgroup>
+<tbody valign="top">
+<tr><td class="label"><a class="fn-backref" href="#id3" name="tep-135">[TEP_135]</a></td><td>TEP 135: Active Message ID Allocation in TinyOS 2.1</td></tr>
</tbody>
</table>
</div>