DTLSR: delay tolerant routing for developing regions

ABSTRACT

We consider the problem of routing in delay tolerant networks deployed in developing regions. Although these environments experience intermittent connectivity (hence the desire to use DTN), in many cases the topology has an underlying stability that we can exploit when designing routing protocols. By making small, yet critical, modifications to classical link state routing, we derive a more effective algorithm capable of leveraging predictions of future link uptimes. We describe a complete and fully-implemented protocol, capable of being deployed in the DTN reference implementation without modification. Using a simulation incorporating real-world network characteristics, we demonstrate that our system operates effectively when conventional routing and forwarding may fail.

REFERENCES

• 1: Albrightson, B., Garcia-Luna-Aceves, J., and Boyle, J. EIGRP - a fast routing protocol based on distance vectors.
• 2: Aruna Balasubramanian , Brian Levine , Arun Venkataramani, DTN routing as a resource allocation problem, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 3: Burgess, J., Gallagher, B., Jensen, D., and Levine, B. MaxProp: Routing for vehicle-based disruption-tolerant networks. In Infocom (2006).
• 4: Cerf, V., et al. RFC 4838: Delay-tolerant networking architecture, Apr. 2007.
• 5: T. Clausen , P. Jacquet, Optimized Link State Routing Protocol (OLSR), RFC Editor, 2003
• 6: Demmer, M., et al. Implementing Delay Tolerant Networking. Tech. Rep. IRB-TR-04-020, Intel Research Berkeley, Dec. 2004.
• 7: Doria, A., Uden, M., and Pandey, D. P. Providing Connectivity to the Saami Nomadic Community. In Development by Design Conference (2002).
• 8: Bowei Du , Michael Demmer , Eric Brewer, Analysis of WWW traffic in Cambodia and Ghana, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135894]
• 9: Kevin Fall, A delay-tolerant network architecture for challenged internets, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863960]
• 10: Stephen Farrell , V. Cahill, Delay- and Disruption-Tolerant Networking, Artech House, Inc., Norwood, MA, 2006
• 11: Sushant Jain , Michael Demmer , Rabin Patra , Kevin Fall, Using redundancy to cope with failures in a delay tolerant network, ACM SIGCOMM Computer Communication Review, v.35 n.4, October 2005
• 12: Sushant Jain , Kevin Fall , Rabin Patra, Routing in a delay tolerant network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 13: Evan P. C. Jones , Lily Li , Paul A. S. Ward, Practical routing in delay-tolerant networks, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.237-243, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080141]
• 14: Philo Juang , Hidekazu Oki , Yong Wang , Margaret Martonosi , Li Shiuan Peh , Daniel Rubenstein, Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 15: Lindgren, A., Doria, A., and Schelén, O. Probabilistic routing in intermittently connected networks. In SAPIR (August 2004).
• 16: Moy, J. RFC 2328: OSPF version 2, Apr. 1998.
• 17: Patra, R., Nedevschi, S., Surana, S., Sheth, A., Subramanian, L., and Brewer, E. WiLDNet: Design and Implementation of High Performance WiFi Based Long Distance Networks. In NSDI (Apr. 2007).
• 18: Alex (Sandy) Pentland , Richard Fletcher , Amir Hasson, DakNet: Rethinking Connectivity in Developing Nations, Computer, v.37 n.1, p.78-83, January 2004 [doi>10.1109/MC.2004.1260729]
• 19: E. Rosen , A. Viswanathan , R. Callon, Multiprotocol Label Switching Architecture, RFC Editor, 2001
• 20: Scott, K., and Burleigh, S. Bundle protocol specification. Work In Progress. Internet Draft, Apr. 2007. draft-irtf-dtnrg-bundle-spec-09.txt.
• 21: A. Seth , D. Kroeker , M. Zaharia , S. Guo , S. Keshav, Low-cost communication for rural internet kiosks using mechanical backhaul, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161127]
• 22: The Aravind Wireless network. http://tier.cs.berkeley.edu/wiki/Aravind.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Design, Performance

Keywords:
delay tolerant networks, developing regions, routing