--- /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 Link Estimation Exchange Protocol (LEEP)</title>
+<meta name="author" content="Omprakash Gnawali" />
+<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-link-estimation-exchange-protocol-leep">
+<h1 class="title">The Link Estimation Exchange Protocol (LEEP)</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">124</td>
+</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>
+<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>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.2</td>
+</tr>
+<tr class="field"><th class="docinfo-name">Draft-Modified:</th><td class="field-body">2007-02-09</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>The memo documents the Link Estimation Exchange Protocol (LEEP). Nodes
+use LEEP to estimate and exchange information about the quality of
+links to the neighbors.</p>
+</div>
+<div class="section">
+<h1><a id="introduction" name="introduction">1. Introduction</a></h1>
+<p>Routing protocols often require bi-directional link qualities to
+compute the routes. Nodes can estimate the quality of the in-bound
+link from a neighbor by estimating the ratio of successfully received
+messages and the total transmitted messages. These in-bound link
+qualities are exchanged among the neighbors using LEEP to determine
+the out-bound link qualities. Bi-directional link quality is computed
+using thus learned in-bound and out-bound link qualities.</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>Quality of the link between any two nodes describes the probability
+with which data link layer packets can be received without any
+error. This definition assumes uncorrelated link losses. The link
+between the nodes A and B may have different quality in A to B and B
+to A directions.</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>
+<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>
+</div>
+<div class="section">
+<h2><a id="out-bound-link-quality" name="out-bound-link-quality">2.3 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
+qualities. LEEP is the protocol that is used to exchange the in-bound
+link qualities.</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>
+</div>
+</div>
+<div class="section">
+<h1><a id="id1" name="id1">3. The Link Estimation Exchange Protocol (LEEP)</a></h1>
+<div class="section">
+<h2><a id="assumptions" name="assumptions">3.1 Assumptions</a></h2>
+<p>Following are the assumptions made by LEEP:</p>
+<p>3.1.1. The data link frame has a single-hop source field.
+3.1.2. The data link layer provides a broadcast address.
+3.1.3. The data link layer provides the length of the LEEP frame.</p>
+</div>
+<div class="section">
+<h2><a id="the-protocol" name="the-protocol">3.2 The Protocol</a></h2>
+<p>To compute the bi-directional link quality, in-bound link quality must
+be exchanged among the neighbors. LEEP maintains a sequence number
+that is incremented by one for each outgoing LEEP frame. The sequence
+number in the LEEP frame MUST be incremented by one even if the data
+link layer retransmits the LEEP frame. The LEEP sequence number MAY be
+used to count the number of missing packets to estimate the in-bound
+link quality from the transmitter. LEEP MUST transmit Link Information
+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>
+</div>
+<div class="section">
+<h2><a id="leep-frame" name="leep-frame">3.3 LEEP Frame</a></h2>
+<p>A LEEP frame has a header, the payload, and a footer with the Link
+Information (LI) entries as shown in this diagram:</p>
+<pre class="literal-block">
+-------------------------------------------------------------
+| LEEP | Payload | LI Entry | LI Entry | ... | LI Entry |
+| Header | | 1 | 2 | | n |
+-------------------------------------------------------------
+</pre>
+<p>The number of Link Information entries can be different in each
+outgoing LEEP frame. The number of Link Information entries MUST not
+increase the size of the LEEP frame beyond the maximum payload length
+allowed by the data link layer. A LEEP frame can have 0 Link
+Information entry.</p>
+</div>
+<div class="section">
+<h2><a id="leep-header" name="leep-header">3.3.1 LEEP header</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 |
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+</pre>
+<p>Field definitions:</p>
+<blockquote>
+<ul class="simple">
+<li>nentry - Number of Link Information entries in the footer</li>
+<li>seqno - LEEP sequence number.</li>
+<li>rsrvd - Reserved and must be set to 0.</li>
+</ul>
+</blockquote>
+</div>
+<div class="section">
+<h2><a id="id2" name="id2">3.3.2 Link Information Entry</a></h2>
+<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 |
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+| link quality |
++-+-+-+-+-+-+-+-+
+</pre>
+<p>Field definitions:</p>
+<blockquote>
+<ul class="simple">
+<li>node id: the link layer address of the neighbor</li>
+<li>link quality: The in-bound link quality from the node identified by node id
+to the node that transmits this Link Information entry</li>
+</ul>
+</blockquote>
+</div>
+</div>
+<div class="section">
+<h1><a id="implementation" name="implementation">4. Implementation</a></h1>
+<p>The following files in <tt class="docutils literal"><span class="pre">tinyos-2.x/tos/lib/net/le</span></tt> provide a
+reference implementation of LEEP described in this TEP.</p>
+<blockquote>
+<ul class="simple">
+<li><tt class="docutils literal"><span class="pre">LinkEstimator.h</span></tt> and <tt class="docutils literal"><span class="pre">LinkEstimatorP.nc</span></tt></li>
+</ul>
+</blockquote>
+<p>The reference implementation uses the LEEP sequence number to count
+the number of missing packets to estimate the in-bound link
+quality. The implementation tries to append Link Information entry for
+all the neighbors in its neighbor table by sending the largest
+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,
+sent as a LEEP payload, are sent.</p>
+</div>
+<div class="section">
+<h1><a id="author-s-address" name="author-s-address">5. Author's Address</a></h1>
+<div class="line-block">
+<div class="line">Omprakash Gnawali</div>
+<div class="line">Ronald Tutor Hall (RTH) 418</div>
+<div class="line">3710 S. McClintock Avenue</div>
+<div class="line">Los Angeles, CA 90089</div>
+<div class="line"><br /></div>
+<div class="line">phone - +1 213 821-5627</div>
+<div class="line">email - <a class="reference" href="mailto:gnawali@usc.edu">gnawali@usc.edu</a></div>
+<div class="line"><br /></div>
+</div>
+</div>
+<div class="section">
+<h1><a id="citations" name="citations">6. Citations</a></h1>
+<table class="docutils footnote" frame="void" id="id4" rules="none">
+<colgroup><col class="label" /><col /></colgroup>
+<tbody valign="top">
+<tr><td class="label"><a class="fn-backref" href="#id3" name="id4">[1]</a></td><td>TEP 123: The Collection Tree Protocol.</td></tr>
+</tbody>
+</table>
+</div>
+</div>
+</body>
+</html>
projects / tinyos-2.x.git / commitdiff