From 809dd954050997d163cc809ae1b43dd1db9d441d Mon Sep 17 00:00:00 2001 From: scipio Date: Tue, 6 Feb 2007 03:45:27 +0000 Subject: [PATCH] Updates to TEP 123. --- doc/html/tep123.html | 187 +++++++++++++++++++++++++++++++------------ doc/txt/tep123.txt | 172 ++++++++++++++++++++++++++++----------- 2 files changed, 263 insertions(+), 96 deletions(-) diff --git a/doc/html/tep123.html b/doc/html/tep123.html index 997d719f..7b49fd48 100644 --- a/doc/html/tep123.html +++ b/doc/html/tep123.html @@ -303,9 +303,9 @@ ul.auto-toc { Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, Sukun Kim, Philip Levis, and Alec Woo Draft-Created:3-Aug-2006 -Draft-Version:1.1.2.3 +Draft-Version:1.6 -Draft-Modified:2006-10-25 +Draft-Modified:2007-01-16 Draft-Discuss:TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu> @@ -358,18 +358,19 @@ multiple small frames into a single data-link packet.

3. Collection and CTP

-

CTP uses expected transmissions (ETX) as its routing gradient. A root has an -ETX of 0. The ETX of a node is the ETX of its parent plus the ETX of its -link to its parent. This additive measure assumes that nodes use link-level -retransmissions. Given a choice of valid routes, CTP SHOULD choose the one with the -lowest ETX value. CTP represents ETX values as 16-bit fixed-point real numbers -with a precision of hundredths. An ETX value of 451, for example, represents -an ETX of 4.51, while an ETX value of 109 represents an ETX of 1.09.

-

Routing loops are a problem that can emerge in a CTP network. Routing loops -generally occur when a node choose a new route that has a significantly higher -ETX than its old one, perhaps in response to losing connectivity with a candidate -parent. If the new route includes a node which was a descendant, then a loop -occurs.

+

CTP uses expected transmissions (ETX) as its routing gradient. A root +has an ETX of 0. The ETX of a node is the ETX of its parent plus the +ETX of its link to its parent. This additive measure assumes that +nodes use link-level retransmissions. Given a choice of valid routes, +CTP SHOULD choose the one with the lowest ETX value. CTP represents +ETX values as 16-bit fixed-point real numbers with a precision of +hundredths. An ETX value of 451, for example, represents an ETX of +4.51, while an ETX value of 109 represents an ETX of 1.09.

+

Routing loops are a problem that can emerge in a CTP network. Routing +loops generally occur when a node choose a new route that has a +significantly higher ETX than its old one, perhaps in response to +losing connectivity with a candidate parent. If the new route includes +a node which was a descendant, then a loop occurs.

CTP addresses loops through two mechanisms. First, every CTP packet contains a node's current gradient value. If CTP receives a data frame with a gradient value lower than its own, then this indicates that there @@ -418,7 +419,7 @@ to do so.

Field definitions are as follows:

    -
  • C: Congestion notification. If a node is receiving packets faster than it can forward them, it MAY set the C field to notify other nodes. If a node hears a packet from node N with the C bit set, it MUST NOT transmit CTP data frames to N until it hears a packet from N with the C bit cleared.
    • +
  • C: Congestion notification. If a node drops a CTP data frame, it MUST set the C field on the next data frame it transmits.
  • 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.
  • 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.
  • 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.
    • @@ -457,7 +458,7 @@ acknowledgments enabled.

    The fields are as follows:

      -
    • C: Same as data frame.
      • +
    • C: Congestion notification. If a node drops a CTP data frame, it MUST set the C field on the next routing frame it transmits.
    • P: Same as data frame.
    • parent: The node's current parent.
    • metric: The node's current routing metric value.
      • @@ -490,29 +491,14 @@ misleading: the forwarding engine is responsible for forwarded traffic as well as traffic generated on the node.

      6.1 Link Estimation

      -

      The link estimator estimates the ETX to single-hop neighbors. -The implementation uses two mechanisms to estimate the quality of a link: -periodic broadcast packets and data packets. The estimator itself -only generates broadcast packets. For data traffic, it depends on -other components telling it about acknowledged and unacknowledged -transmissions.

      -

      The periodic broadcast packets have sequence numbers, which the -estimator uses to estimate the sender-to-receiver packet reception -rate (PRR). The data payload of periodic broadcast packets contain -these estimates. Therefore, when node A receives a link estimation -broadcast message from node B, it can use the packet header to -estimate the B-to-A PRR and the packet payload to update B's -estimate of the A-to-B PRR.

      -

      Multiplying these two values gives a bidirectional PRR, or -an estimate of the probability that if A transmits a packet to B, -B will successfully hear and acknowledge the packet and A will -hear the acknowledgment. The inverse of the bidirecitonal PRR -is the ETX.

      -

      CTP link estimation adapts its beaconing rate to be slow when -its routing table is stable and faster when changes occur. -It adjusts the beaconing interval using an algorithm similar -to the trickle dissemination protocol[2_]. CTP sends beacons -more often when one of three conditions occurs:

      +

      The implementation uses two mechanisms to estimate the quality of a link: +periodic LEEP [1] 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 [2]. 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:

      1. The routing table is empty (this also sets the P bit)
        2. @@ -520,12 +506,12 @@ more often when one of three conditions occurs:

      2. The node hears a packet with the P bit set
      -

      CTP also estimates link quality using data transmissions. This -is a direct measure of ETX. Whenever the data path transmits a -packet, it tells the link estimator the destimation and whether -it was successfully acknowledged. The estimator produces an ETX -estimate every 5 such transmissions, where 0 successes has an -ETX of 6.

      +

      The implementation augments the LEEP link estimates with data +transmissions. This is a direct measure of ETX. Whenever the data path +transmits a packet, it tells the link estimator the destimation and +whether it was successfully acknowledged. The estimator produces an +ETX estimate every 5 such transmissions, where 0 successes has an ETX +of 6.

      The estimator combines the beacon and data estimates by incorporating them into an exponentially weighted moving average. Beacon-based estimates seed the neighbor table. The expectation is that the low @@ -534,17 +520,116 @@ data estimates will outweigh beacon estimates. Additionally, as the rate at which CTP collects data estimates is proportional to the transmission rate, then it can quickly detect a broken link and switch to another candidate neighbor.

      +

      The component tos/lib/net/le/LinkEstimatorP implements the +link estimator. It couples LEEP-based and data-based estimates.

      6.2 Routing Engine

      -

      The

      +

      The implementation's routing engine is responsible for picking the next +hop for a data transmission. It keeps track of the path ETX values of +a subset of the nodes maintained by the link estimation table. The minimum +cost route has the smallest sum the path ETX from that node and the link +ETX of that node. The path ETX is therefore the sum of link ETX values +along the entire route. The component tos/lib/net/ctp/CtpRoutingEngineP +implements the routing engine.

      +
      +

      6.3 Forwarding Engine

      +

      The component tos/lib/net/ctp/CtpForwardingEngineP implements the +forwarding engine. It has five repsonsibilities:

      +
      +
        +
      1. Transmitting packets to the next hop, retransmitting when necessary, and +passing acknowledgment based information to the link estimator
        2. +
      2. Deciding when to transmit packets to the next hop
        3. +
      3. Detecting routing inconsistencies and informing the routing engine
        4. +
      4. Maintaining a queue of packets to transmit, which are a mix of locally +generated and forwarded packets
        5. +
      5. Detecting single-hop transmission duplicates caused by lost acknowledgments
        6. +
      +
      +

      The four key functions of the forwading engine are packet reception +(SubReceive.receive()), packet forwarding (forward()), packet +transmission (sendTask()) and deciding what to do after a packet +transmission (SubSend.sendDone()).

      +

      The receive function decides whether or not the node should forward a +packet. It checks for duplicates using a small cache of recently received +packets. If it decides a packet is not a duplicate, it calls the +forwading function.

      +

      The forwarding function formats the packet for forwarding. It checks the +received packet to see if there is possibly a loop in the network. +It checks if there is space in the transmission queue. +If there is no space, it drops the packet and sets the C bit. If the +transmission queue was empty, then it posts the send task.

      +

      The send task examines the packet at the head of the transmission +queue, formats it for the next hop (requests the route from the +routing layer, etc.), and submits it to the AM layer.

      +

      When the send completes, sendDone examines the packet to see the result. +If the packet was acknowledged, it pulls the packet off the transmission +queue. If the packet was locally generated, it signals sendDone() to the +client above. If it was forwarded, it returns the packet to the forwarding +message pool. If there are packets remaining in the queue (e.g., the +packet was not acknowledged), it starts a randomized timer that reposts +this task. This timer essentially rate limits CTP so that it does not +stream packets as quickly as possible, in order to prevent self-collisions +along the path.

      +
      +
+
+

7. Citations

+
+
Rodrigo Fonseca
+
473 Soda Hall
+
Berkeley, CA 94720-1776
+

+
phone - +1 510 642-8919
+
email - rfonseca@cs.berkeley.edu
+

+

+
Omprakash Gnawali
+
Ronald Tutor Hall (RTH) 418
+
3710 S. McClintock Avenue
+
Los Angeles, CA 90089
+

+
phone - +1 213 821-5627
+
email - gnawali@usc.edu
+

+

+
Kyle Jamieson
+
The Stata Center
+
32 Vassar St.
+
Cambridge, MA 02139
+

+
email - jamieson@csail.mit.edu
+

+

+
Philip Levis
+
358 Gates Hall
+
Computer Science Laboratory
+
Stanford University
+
Stanford, CA 94305
+

+
phone - +1 650 725 9046
+
email - pal@cs.stanford.edu
-
-

Docutils System Messages

-
-

System Message: ERROR/3 (txt/tep123.txt, line 232); backlink

-Unknown target name: "2".
+
+
+

8. Citations

+ + + + + +
[1]TEP 124: Link Estimation Extension Protocol
+ + + + + +
[2]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.
diff --git a/doc/txt/tep123.txt b/doc/txt/tep123.txt index 60d6cbfa..96af8a42 100644 --- a/doc/txt/tep123.txt +++ b/doc/txt/tep123.txt @@ -66,19 +66,20 @@ multiple small frames into a single data-link packet. 3. Collection and CTP ============================================================================== -CTP uses expected transmissions (ETX) as its routing gradient. A root has an -ETX of 0. The ETX of a node is the ETX of its parent plus the ETX of its -link to its parent. This additive measure assumes that nodes use link-level -retransmissions. Given a choice of valid routes, CTP SHOULD choose the one with the -lowest ETX value. CTP represents ETX values as 16-bit fixed-point real numbers -with a precision of hundredths. An ETX value of 451, for example, represents -an ETX of 4.51, while an ETX value of 109 represents an ETX of 1.09. - -Routing loops are a problem that can emerge in a CTP network. Routing loops -generally occur when a node choose a new route that has a significantly higher -ETX than its old one, perhaps in response to losing connectivity with a candidate -parent. If the new route includes a node which was a descendant, then a loop -occurs. +CTP uses expected transmissions (ETX) as its routing gradient. A root +has an ETX of 0. The ETX of a node is the ETX of its parent plus the +ETX of its link to its parent. This additive measure assumes that +nodes use link-level retransmissions. Given a choice of valid routes, +CTP SHOULD choose the one with the lowest ETX value. CTP represents +ETX values as 16-bit fixed-point real numbers with a precision of +hundredths. An ETX value of 451, for example, represents an ETX of +4.51, while an ETX value of 109 represents an ETX of 1.09. + +Routing loops are a problem that can emerge in a CTP network. Routing +loops generally occur when a node choose a new route that has a +significantly higher ETX than its old one, perhaps in response to +losing connectivity with a candidate parent. If the new route includes +a node which was a descendant, then a loop occurs. CTP addresses loops through two mechanisms. First, every CTP packet contains a node's current gradient value. If CTP receives a data frame with @@ -208,43 +209,25 @@ as well as traffic generated on the node. 6.1 Link Estimation ------------------------------------------------------------------------------ -The link estimator estimates the ETX to single-hop neighbors. The implementation uses two mechanisms to estimate the quality of a link: -periodic broadcast packets and data packets. The estimator itself -only generates broadcast packets. For data traffic, it depends on -other components telling it about acknowledged and unacknowledged -transmissions. - -The periodic broadcast packets have sequence numbers, which the -estimator uses to estimate the sender-to-receiver packet reception -rate (PRR). The data payload of periodic broadcast packets contain -these estimates. Therefore, when node A receives a link estimation -broadcast message from node B, it can use the packet header to -estimate the B-to-A PRR and the packet payload to update B's -estimate of the A-to-B PRR. - -Multiplying these two values gives a *bidirectional* PRR, or -an estimate of the probability that if A transmits a packet to B, -B will successfully hear and acknowledge the packet and A will -hear the acknowledgment. The inverse of the bidirecitonal PRR -is the ETX. - -CTP link estimation adapts its beaconing rate to be slow when -its routing table is stable and faster when changes occur. -It adjusts the beaconing interval using an algorithm similar -to the trickle dissemination protocol[2_]. CTP sends beacons -more often when one of three conditions occurs: +periodic LEEP [1]_ 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 [2]_. 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: 1) The routing table is empty (this also sets the P bit) 2) The node's routing ETX increases by >= 1 trasmission 3) The node hears a packet with the P bit set -CTP also estimates link quality using data transmissions. This -is a direct measure of ETX. Whenever the data path transmits a -packet, it tells the link estimator the destimation and whether -it was successfully acknowledged. The estimator produces an ETX -estimate every 5 such transmissions, where 0 successes has an -ETX of 6. +The implementation augments the LEEP link estimates with data +transmissions. This is a direct measure of ETX. Whenever the data path +transmits a packet, it tells the link estimator the destimation and +whether it was successfully acknowledged. The estimator produces an +ETX estimate every 5 such transmissions, where 0 successes has an ETX +of 6. The estimator combines the beacon and data estimates by incorporating them into an exponentially weighted moving average. Beacon-based @@ -255,11 +238,110 @@ 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. +The component ``tos/lib/net/le/LinkEstimatorP`` implements the +link estimator. It couples LEEP-based and data-based estimates. + 6.2 Routing Engine ------------------------------------------------------------------------------ -The +The implementation's routing engine is responsible for picking the next +hop for a data transmission. It keeps track of the path ETX values of +a subset of the nodes maintained by the link estimation table. The minimum +cost route has the smallest sum the path ETX from that node and the link +ETX of that node. The path ETX is therefore the sum of link ETX values +along the entire route. The component ``tos/lib/net/ctp/CtpRoutingEngineP`` +implements the routing engine. +6.3 Forwarding Engine +------------------------------------------------------------------------------ +The component ``tos/lib/net/ctp/CtpForwardingEngineP`` implements the +forwarding engine. It has five repsonsibilities: + + 1) Transmitting packets to the next hop, retransmitting when necessary, and + passing acknowledgment based information to the link estimator + 2) Deciding *when* to transmit packets to the next hop + 3) Detecting routing inconsistencies and informing the routing engine + 4) Maintaining a queue of packets to transmit, which are a mix of locally + generated and forwarded packets + 5) Detecting single-hop transmission duplicates caused by lost acknowledgments + +The four key functions of the forwading engine are packet reception +(``SubReceive.receive()``), packet forwarding (``forward()``), packet +transmission (``sendTask()``) and deciding what to do after a packet +transmission (``SubSend.sendDone()``). + +The receive function decides whether or not the node should forward a +packet. It checks for duplicates using a small cache of recently received +packets. If it decides a packet is not a duplicate, it calls the +forwading function. + +The forwarding function formats the packet for forwarding. It checks the +received packet to see if there is possibly a loop in the network. +It checks if there is space in the transmission queue. +If there is no space, it drops the packet and sets the C bit. If the +transmission queue was empty, then it posts the send task. + +The send task examines the packet at the head of the transmission +queue, formats it for the next hop (requests the route from the +routing layer, etc.), and submits it to the AM layer. + +When the send completes, sendDone examines the packet to see the result. +If the packet was acknowledged, it pulls the packet off the transmission +queue. If the packet was locally generated, it signals sendDone() to the +client above. If it was forwarded, it returns the packet to the forwarding +message pool. If there are packets remaining in the queue (e.g., the +packet was not acknowledged), it starts a randomized timer that reposts +this task. This timer essentially rate limits CTP so that it does not +stream packets as quickly as possible, in order to prevent self-collisions +along the path. + +7. Citations +==================================================================== + +| Rodrigo Fonseca +| 473 Soda Hall +| Berkeley, CA 94720-1776 +| +| phone - +1 510 642-8919 +| email - rfonseca@cs.berkeley.edu +| +| +| Omprakash Gnawali +| Ronald Tutor Hall (RTH) 418 +| 3710 S. McClintock Avenue +| Los Angeles, CA 90089 +| +| phone - +1 213 821-5627 +| email - gnawali@usc.edu +| +| +| Kyle Jamieson +| The Stata Center +| 32 Vassar St. +| Cambridge, MA 02139 +| +| email - jamieson@csail.mit.edu +| +| +| Philip Levis +| 358 Gates Hall +| Computer Science Laboratory +| Stanford University +| Stanford, CA 94305 +| +| phone - +1 650 725 9046 +| email - pal@cs.stanford.edu + +8. Citations +==================================================================== + +.. [1] TEP 124: Link Estimation Extension Protocol +.. [2] 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. + + -- 2.39.2