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.
+to deliver application payload to the sink and to probe topology
+inconsistencies.
2. Assumptions and Limitations
==============================================================================
2) Provides synchronous acknowledgments for unicast packets.
3) Provides a protocol dispatch field to support multiple higher-level
protocols.
- 4) Has single-hop source and destination fields.
+ 4) Has single-hop 16-bit source and destination fields.
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 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
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 45, for example, represents an ETX of 4.5,
+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.
Routing loops are a problem that can emerge in a CTP network. Routing
* 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.
+
+Note that the two 16-bit fields, ETX and origin, appear in network
+byte-order in the data frame.
Together, the origin, seqno and collect_id fields denote a unique
***origin packet.*** Together, the origin, seqno, collect_id, and
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 fields are as follows:
- * P: Same as data frame with one difference: Routing frames are broadcast so multiple nodes respond to the P bit in the routing 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. Thus, the P bit in the routing frame can be used for quick bootstrapping of the routes: when a node boots up and sends a frame with the P bit set, the neighboring nodes can quickly transmit routing frames advertising their routes enabling the new node to quickly compute the route to the sink.
* 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.
+Note that the two 16-bit fields, parent and ETX, appear in network
+byte-order in the routing frame.
+
When a node hears a routing frame, it MUST update its routing table to
reflect the address' new metric. If a node's ETX value changes
significantly, then CTP SHOULD transmit a broadcast frame soon thereafter
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
|
| phone - +1 650 725 9046
| email - pal@cs.stanford.edu
+|
+|
+| Alec Woo
+| Arch Rock Corporation
+| 501 2nd St. Ste 410
+| San Francisco, CA 94107-4132
+|
+| email - awoo@archrock.com
+
8. Citations
====================================================================
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.