How does the collection tree protocol detect routing loops
CTP has been used in research, teaching, and in commercial products. Experiences with CTP has also informed the design of the IPv6 Routing Protocol for Low power and Lossy Networks (RPL).
CTP Mechanisms
CTP is a distance vector routing protocol designed for sensor networks. CTP computes the routes from each node in the network to the root (specified destinations) in the network. CTP uses these three mechanisms to overcome the challenges faced by distance vector routing protocol in a highly dynamic wireless network:
| Agile and Accurate Link Quality Estimation : The links in a wireless network are highly dynamic and exhibit bursty behavior over short time scales. This property of wireless links suggests that a link quality must be agile for it to be accurate. The four-bit link estimator used in CTP uses information from the physical, data link, and network layers to provide accurate link quality estimates despite these challenges. |
Datapath Validation : In a dynamic wireless environment, a routing path that is reliable at one point can become unreliable or even unavailable within a few seconds. Due to changing link qualities, loops can form and cause network congestion and energy drain due to looping packets. Thus, these problems in the routing path must be detected as quickly as they occurr. CTP uses datapath validation to detect these problems at the timescale of data packet transmission (a few tens of milliseconds). It does so by using data packets transmissions and receptions as topology probes and quickly detecting the problem when the packets do not make progress towards the destination in the routing metric space.
| Adaptive Beaconing : Routing protocols typically broadcast control packets at a fixed interval (e.g., every 30 seconds). This interval poses a basic tradeoff. A small interval, i.e., frequent beacons, makes the protocol more responsive to the changes in the network, but uses more bandwidth and energy. A large interval uses less bandwidth and energy but can let topological problems persist for a long time. CTP uses adaptive beaconing to break this tradeoff. When the topology is inconsistent and has problems, it sends beacons faster. Otherwise, it decreases the beaconing rate exponentially. Thus, CTP can quickly respond to adverse wireless dynamics while incuring low control overhead in the long term. |
Publications
CTP uses the four-bit link quality estimator, which is described in this paper:
Deployments
- There is a 330-node CTP deployment in China called GreenOrbs. GreenOrbs continuously monitors the environment in a forest. More information available at greenorbs.org.
- There is a 200-node CTP deployment at Stanford called Powernet. Powernet monitors energy used by computing equipments in the computer science department.
- Rincon Research deployed CTP for surveillence application.
- There is a microclimate monitoring company (which declined to be listed on this page) that deploys CTP commercially.
| Powernet Deployment map | CTP Routing Topology on Powernet |
CTP and the Internet
- T. Winter, P. Thubert, A. Brandt, T. Clausen, J. Hui, P. Levis, K. Pister, R. Struik, JP. Vasseur, RPL: IPv6 Routing Protocol for Low power and Lossy Networks (draft-ietf-roll-rpl-19)
- O. Gnawali, P. Levis, The Minimum Rank Objective Function with Hysteresis (draft-ietf-roll-minrank-hysteresis-of-01)
- P. Levis, T. Clausen, J. Hui, O. Gnawali, J. Ko, RFC 6206: The Trickle Algorithm (RFC 6206)
CTP as a Benchmark
- Scott H Moeller, Avinash Sridharan, Bhaskar Krishnamachari, and Omprakash Gnawali, Routing Without Routes: The Backpressure Collection Protocol , IPSN 2010.
- Hackmann, G., Chipara, O., and Lu, C. 2008, Robust topology control for indoor wireless sensor networks, SenSys 2008.
- Alizai, M. H., Landsiedel, O., Link, J. A., Gotz, S., and Wehrle, K. 2009. Bursty traffic over bursty links, SenSys 2009.
CTP as an Enabling Research
- Octav Chipara, Chenyang Lu, homas C. Bailey, Gruia-Catalin Roman, Reliable Clinical Monitoring using Wireless Sensor Networks: Experience in a Step-down Hospital Unit , SenSys 2010.
- Chieh-Jan Mike Liang, Nissanka B. Priyantha, Jie Liu, Andreas Terzis, Surviving Wi-Fi Interference in Low Power ZigBee Networks , SenSys 2010.
- Peng Li, John Regehr, T-Check: Bug Finding for Sensor Networks , IPSN 2010.
- James Horey, Arthur Maccabe and Eric Nelson. Tables: A Spreadsheet-Inspired Programming Model for Sensor Networks , DCOSS 2010.
- Omprakash Gnawali, Leonidas Guibas, and Philip Levis, A Case for Evaluating Sensor Network Protocols Concurrently , WiNTECH 2010.
- JeongGil Ko, T.Gao, A.Terzis, Empirical Study of a Medical Sensor Application in an Urban Emergency Department , BodyNets 2009.
- Yang Chen, Omprakash Gnawali, Maria Kazandjieva, Philip Levis, John Regehr, Surviving Sensor Network Software Faults , SOSP 2009.
- Muhammad Hamad Alizai, Olaf Landsiedel, Jo Agila Bitsch Link, Stefan Gotz, and Klaus Wehrle, Bursty traffic over bursty links , SenSys 2009.
Implementations
- TinyOS includes a nesC implementation of CTP. [Link]
- Mantis OS includes a C implementation of CTP. [Tarball]
- There is a Java implementation of CTP for Sun SPOTs at dev.java.net. [Link]
- There is a C implementation of CTP in Contiki OS.
- There is a C++ implementation of CTP by Ugo Colesanti and Silvia Santini for Castalia WSN simulator 3.0. [Link to Google Code][Stanford copy - Zip]
- There is a CTP implementation on Linux/Click by Jung Il Choi, Mayank Jain, Jung Woo Lee, and Juan Batiz-Benet from Stanford. [Tarball]
Ugo Colesanti, Silvia Santini, The Collection Tree Protocol for the Castalia Wireless Sensor Networks Simulator , Technical Report No. 729, Department of Computer Science, ETH Zurich, Zurich, Switzerland, June 2011. [Stanford copy]
