X-Git-Url: https://oss.titaniummirror.com/gitweb/?p=tinyos-2.x.git;a=blobdiff_plain;f=doc%2Fhtml%2Ftep123.html;h=f3ea4462388e6e3ad7d712841f39feac9837380f;hp=d2406572123ad2137e191985854ecfd020049c31;hb=e9bfab607e051bae6afb47b44892ce37541d1b44;hpb=adf1de6c009d13b7b52e68535c63b28f59c97400 diff --git a/doc/html/tep123.html b/doc/html/tep123.html index d2406572..f3ea4462 100644 --- a/doc/html/tep123.html +++ b/doc/html/tep123.html @@ -291,16 +291,16 @@ ul.auto-toc {
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 +[3] to use CTP in their applications.
+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.
+All fields in this specification are in network byte order.
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.
-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 tries very hard.
-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.
+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.
+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.
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 @@ -377,13 +393,17 @@ will form a loop whose ETX increases forever. CTP's second mechanism is to not consider routes with an ETX higher than a reasonable constant. The value of this constant is implementation dependent.
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.
+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.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 @@ -398,30 +418,30 @@ to do so.
The CTP data frame format is as follows:
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 ... -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Field definitions are as follows:
-
- 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.
+- 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.
- C: Congestion notification. If a node drops a CTP data frame, it MUST set the C field on the next data frame it transmits.
- 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.
- origin: The originating address of the packet. A node forwarding a data frame MUST NOT modify the origin field.
- seqno: Origin sequence number. The originating node sets this field, and a node forwarding a data frame MUST NOT modify it.
- collect_id: Higher-level protocol identifier. The origin sets this field, and a node forwarding a data frame MUST NOT modify it.
-- data: the data payload, of zero or more bytes. A node forwarding a data frame MUST NOT modify the data payload.
+- 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.
Together, the origin, seqno and collect_id fields denote a unique @@ -431,7 +451,7 @@ distinction is important for duplicate suppression in the presence of routing loops. If a node suppresses origin packets, then if asked to forward the same packet twice due to a routing loop, it will drop the packet. However, if it suppresses packet instances, then 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.
A node MUST send CTP data frames as unicast messages with link-layer acknowledgments enabled.
@@ -441,19 +461,19 @@ acknowledgments enabled.The CTP routing frame format is as follows:
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 | +-+-+-+-+-+-+-+-+
The fields are as follows:
-
- P: Same as data frame.
+- P: Same as data frame with one difference: Routing frames are broadcast so multiple nodes respond to the P bit in the routing 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.
- parent: The node's current parent.
- metric: The node's current routing metric value.
@@ -468,6 +488,7 @@ a data packet: a parent can detect when a child's ETX is significantly 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. +A node MUST send CTP routing frames as broadcast messages.
The implementation uses two mechanisms to estimate the quality of a link: -periodic LEEP [1] packets and data packets. The implementation sends +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 +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:
- The routing table is empty (this also sets the P bit)
-- The node's routing ETX increases by >= 1 trasmission
+- The node's routing ETX increases by >= 1 transmission
- The node hears a packet with the P bit set
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.
@@ -515,8 +536,9 @@ 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.
+The component tos/lib/net/4bitle/LinkEstimatorP implements the +link estimator. It couples LEEP-based and data-based estimates as +described in [4].
The component tos/lib/net/ctp/CtpForwardingEngineP implements the -forwarding engine. It has five repsonsibilities:
+forwarding engine. It has five responsibilities:
- Transmitting packets to the next hop, retransmitting when necessary, and @@ -606,25 +628,57 @@ along the path.
phone - +1 650 725 9046email - pal@cs.stanford.edu+++Alec Woo+Arch Rock Corporation+501 2nd St. Ste 410+San Francisco, CA 94107-4132++email - awoo@archrock.com+++Sukun Kim+Samsung Electronics+416 Maetan-3-dong, Yeongtong-Gu+Suwon, Gyeonggi 443-742+Korea, Republic of++phone - +82 10 3065 6836+email - sukun.kim@samsung.com
[1] | TEP 124: Link Estimation Extension Protocol |
[1] | TEP 124: Link Estimation Extension Protocol |
[2] | Philip Levis, Neil Patel, David Culler and Scott Shenker. "A + |
[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. |
[3] | TEP 119: Collection. |
[4] | 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. |