1. Introduction
==============================================================================
+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.
+
2. Assumptions and Limitations
==============================================================================
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 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. Bandwidth-limited systems
-might benefit from a different protocol, which can, for example, pack
-multiple small frames into a single data-link packet.
+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.
3. Collection and CTP
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.
+hundredths. An ETX value of 45, for example, represents an ETX of 4.5,
+while an ETX value of 10 represents an ETX of 1.
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
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,
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 a node with a valid route hears a packet with the P bit set, it SHOULD transmit a routing frame in the near future. Data frames are unicast so only the destination of the unicast transmission responds 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.
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
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.
own, it MUST schedule a routing frame for transmission in the near
future.
+A node MUST send CTP routing frames as broadcast messages.
+
6. Implementation
==============================================================================
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
+ 2) The node's routing ETX increases by >= 1 transmission
3) 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.
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]_.
6.2 Routing Engine
------------------------------------------------------------------------------
------------------------------------------------------------------------------
The component ``tos/lib/net/ctp/CtpForwardingEngineP`` implements the
-forwarding engine. It has five repsonsibilities:
+forwarding engine. It has five responsibilities:
1) Transmitting packets to the next hop, retransmitting when necessary, and
passing acknowledgment based information to the link estimator
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.
projects / tinyos-2.x.git / blobdiff