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.
- * P: Routing pull. The P bit allows nodes to request routing information from other nodes. If a node hears a packet with the P bit set, it SHOULD transmit a routing frame in the near future if it has a valid route.
+ * 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.
+ * 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.
* 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.
+ * data: the data payload, of zero or more bytes. A node forwarding a data frame MUST NOT modify the data payload.
Together, the origin, seqno and collect_id fields denote a unique
***origin packet.*** Together, the origin, seqno, collect_id, and
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
-unless the THL has wrapped around to the identical value it had
-on previous times around.
+drop the packet. However, if it suppresses packet instances, then it
+will route succesfully 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.
own, it MUST schedule a routing frame for transmission in the near
future.
+6. Implementation
+==============================================================================
+
+An implementation of CTP can be found in the tos/lib/net/ctp directory
+of TinyOS 2.0. This section describes the structure of that implementation
+and is not in any way part of the specification of CTP.
+
+This implementation has three major subcomponents:
+
+1) A **link estimator**, which is responsible for estimating the
+single-hop ETX of communication with single-hop neighbors.
+
+2) A **routing engine**, which uses link estimates as well as
+network-level information to decide which neighbor is the next
+routing hop.
+
+3) A **forwarding engine**, which maintains a queue of packets
+to send. It decides when and if to send them. The name is a little
+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:
+
+ 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 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
+beacon rate in a stable network means that for a selected route,
+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.
+
+6.2 Routing Engine
+------------------------------------------------------------------------------
+
+The
+
+
+
projects / tinyos-2.x.git / blobdiff