Collection Tree Protocol Notes

Collection Tree Protocol

Two Priciples

  • Datapath Validation: Data traffic quickly discovers and fixes routing inconsistencies
  • Adaptive Beaconing: Extending the Trickle algorithm [1] to routing control traffic reduces route repair latency and sends fewer beacons

The two principles we present allow a routing protocol to react at the same timescales as the topology changes while remaining efficient and robust.

Four Goals

  • Reliability: At least E2E PDR, 99.9% should be achievalbe
  • Robustness: Operate without tuning or configuration
  • Efficiency: Minimum amount of transmissions
  • Hardware Independence: Achieve the three above goals without assuming specific radio chip features

Two Dominant Causes of Poor Performance

  • Link Dynamics In some environments, particularly in the 2.4 GHz frequency space, links can be highly dynamic.
  • Transient Loops Rapid link topology changes can have serious adverse effects on existing routing protocols, causing losses in the data plane or long periods of disconnection while the topology adjusts.

Datapath Validation

We assume expected transmissions (ETX) as the cost metric, but any similar gradient metric can work just as well. A node’s cost is the cost of its next hop plus the cost of its link to the next hop: the cost of a route is the sum of the costs of its links.

Adaptive Beaconing

Adaptive beaconing breaks this tradeoff, achieving both fast recovery and low cost. Adaptive beaconing uses the routing cost gradient to control when to reset the timer interval. The routing layer resets the interval to τl on three events:

  1. It is asked to forward a data packet from a node whose ETX is not higher than its own.
  2. Its routing cost decreases significantly.
  3. It receives a packet with the P bit set.

Control Plane Design

Route Computation and Selection

A CTP routing frame has two fields and two control bits. The two fields advertise the node’s current parent and routing cost. The two control bits are the pull bit (P) and the congested bit (C).

CTP routing frame Part 1 Part 2
Fields Current Parent Routing Cost
Control Bits Pull Bit (P) Congested Bit (C)[2]

To dampen the topology change rate, CTP Noe employs hysteresis in path selection: it only switches routes if it believes the other route is significantly better than its current one, where “significantly” better is having an ETX at least 1.5 lower.

Control Traffic Timing

When the routing topology is working well and routing cost estimates are accurate, CTP Noe slows its beaconing rate. However, when the routing topology changes significantly, or CTP Noe detects a problem with the topology, it quickly informs nearby nodes so they can react accordingly.

It maintains a beaconing interval which varies between 64 ms and one hour. Whenever the timer expires, CTP Noe doubles it, up to the maximum (one hour).Whenever CTP Noe detects an event which indicates the topology needs active maintenance, it resets the timer to the minimum (64 ms).

Resetting the Beacon Interval

  • P bit: When a node boots, its routing table is empty, so it beacons with the P bit set.
  • Cost drops significantly: Resetting its beacon interval allows the node’s neighbors to quickly learn this information.
  • Routing topology inconsistency: The cost of each hop must monotonically decrease. Let p be a path consisting of k links between node n0 and the root, node nk, such that ni forwards its packets to node ni+1. For the routing state to be consistent, the following constraint must be satisfied:

$$ ∀i ∈ {0,k−1}, ETX(n_i) > ETX(n_{i+1}) $$

where ETX(x) is the path ETX from node x to the root.

CTP Noe forwards data packets in a possible loop normally, it does not drop them. However, it introduces a slight pause in forwarding, the length of the minimum beacon interval. This ensures that it sends the resulting beacon before the data packet, such that the inconsistent node has a chance to resolve the problem. If there is a loop of length L, this means that the forwarded packet takes L - 1 hops before reaching the node that triggered topology recovery. As that node has updated its routing table, it will pick a different next hop.

Data Plane Design

This section describes four mechanisms in the data plane that achieve efficiency, robustness, and reliability:

  1. Per-client Queuing
  2. Hybrid Send Queue
  3. Transmit Timer
  4. Packet Summary Cache

CTP Fordwarding path

Eight Byte Header

The data frame header shares two fields with the routing frame, the one byte control field (P and C bits) and the two byte route ETX field. The one byte time has lived (THL) is the opposite of a TTL: it starts at zero at an end point and each hop increments it by one. A one-byte dispatch identifier called Collect ID, allows multiple clients to share a single CTP Noe layer. A two byte origin field contains the identifier of the node that originated the packet, and a node increments a one byte sequence number on each packet it originates.

Per-client Queuing

CTP Noe maintains two levels of queues. The top level is a set of one-deep client queues.

Hybrid Send Queue

CTP Noe’s lower level queue contains both route through- and locally-generated traffic (as in ARC[3]), maintained by a FIFO policy. This hybrid send queue is of length C+F, where C is the number of CTP Noe clients and F is the size of the forwarding buffer pool.

Transmit Timer

A. Woo and D. E. Culler. A transmission control scheme for media access in sensor networks. In Proceedings of the seventh annual international conference on Mobile computing and networking, Rome, Italy, July 2001.

Transmit (Packet Summary) Cache

Link layer acknowledgments are not perfect: they are subject both to false positives and false negatives.

  • False Positives:
  • False Negatives: False negatives cause a node to retransmit a packet which is already in the next hop’s forwarding queue.

It detects duplicates by examining three values: the origin address, the origin sequence number, and the THL.

We have found that, in practice and even under high load, having a cache size of four slots is enough to suppress most (> 99%) duplicates on the testbeds that we used for experiments.

Evaluation

  1. Testbeds
    The 5th percentile can prove the lower bound of the CTP performance.

  2. Experimental Methodology
    We modified three variables across all of the experiments: the inter-packet interval (IPI) with which the application sends packets with CTP Noe, the MAC layer used, and the node ID of the root node. Baseline - MultihopLQI, a well-established, well-tested, and highly used collection layer that is part of the TinyOS release.

  3. Reliable, Robust, Hardware-independent

    • Average Delivery Ratio
    • Delivery Ratio
  1. Efficiency
    Cost (metric which accounts for all the control and data transmissions in the network normalized by the packets received at the sink)

  2. Adaptive Control Traffic
    Beaconing Rate

  3. Topology Inconsistencies

    • Number of beacons for selected nodes in the neighborhood of the new node
    • Breakdown of control overhead
  1. Robustness to Failure
    Robustness of CTP Noe and MultiHopLQI when the 10 most-heavily-forwarding nodes fail

  2. Agility
    We ran a different experiment. We ran CTP Noe on Tutornet with each node generating a data packet every eight seconds for six minutes, allowing it to settle on a good routing tree delivering 100% of the packets. Then we stopped generating data traffic on all the nodes for 14 minutes. At the 20th minute, we removed (erased the program running on the mote) node 26 from the network and shortly thereafter made node 53 (node 26’s child in the routing tree) start sending data packets.

  3. Transmit Timer

  4. Transmit Cache
    Enable/Disable cache

  5. External Interference

    • 802.11 Wi-Fi (1-11) Interference
    • 802.15.4 (11-26)
  1. Link Layers
    Six experiments on the Motelab testbed using the standard TinyOS CSMA layer, low-power listening with BoX-MAC, and low-power probing with LPP. Table 4 has further details on these results.

  2. Energy Profile
    CTP Noe’s low energy profile is possible because it selects efficient paths, avoids unnecessary control traffic, and actively monitors the topology using the the data plane.

  3. Testbed Observations

Source Code

References


  1. P. Levis, N. Patel, D. Culler, and S. Shenker. Trickle: A selfregulating algorithm for code maintenance and propagation in wireless sensor networks. In Proc. of the USENIX NSDI Conf., San Francisco, CA, Mar. 2004.

  2. The C bit is for signaling higher-layer congestion control and is not relevant for this paper.

  3. A. Woo and D. E. Culler. A transmission control scheme for media access in sensor networks. In Proceedings of the seventh annual international conference on Mobile comput- ing and networking, Rome, Italy, July 2001.