Practical routing in delay-tolerant networks

ABSTRACT

Delay-tolerant networks (DTNs) have the potential to connect devices and areas of the world that are under-served by current networks. A critical challenge for DTNs is determining routes through the network without ever having an end-to-end connection, or even knowing which "routers" will be connected at any given time. Prior approaches have focused either on epidemic message replication or on knowledge of the connectivity schedule. The epidemic approach of replicating messages to all nodes is expensive and does not appear to scale well with increasing load. It can, however, operate without any prior network configuration. The alternatives, by requiring a priori connectivity knowledge, appear infeasible for a self-configuring network.In this paper we present a practical routing protocol that only uses observed information about the network. We designed a metric that estimates how long a message will have to wait before it can be transferred to the next hop. The topology is distributed using a link-state routing protocol, where the link-state packets are "flooded" using epidemic routing. The routing is recomputed when connections are established. Messages are exchanged if the topology suggests that a connected node is "closer" than the current node.We demonstrate through simulation that our protocol provides performance similar to that of schemes that have global knowledge of the network topology, yet without requiring that knowledge. Further, it requires a significantly smaller quantity of buffer, suggesting that our approach will scale with the number of messages in the network, where replication approaches may not.

REFERENCES

• 1: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 2: Dartmouth College. The Dartmouth Wireless Trace Archive. http://cmc.cs.dartmouth.edu/data/.
• 3: James A. Davis , Andrew H. Fagg , Brian N. Levine, Wearable Computers as Packet Transport Mechanisms in Highly-Partitioned Ad-Hoc Networks, Proceedings of the 5th IEEE International Symposium on Wearable Computers, p.141, October 08-09, 2001
• 4: Douglas S. J. De Couto , Daniel Aguayo , John Bicket , Robert Morris, A high-throughput path metric for multi-hop wireless routing, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939000]
• 5: Richard Draves , Jitendra Padhye , Brian Zill, Routing in multi-radio, multi-hop wireless mesh networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023732]
• 6: 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]
• 7: R. Handorean, C. Gill, and G.-C. Roman. Accommodating transient connectivity in ad hoc and mobile settings. Lecture Notes in Computer Science, 3001:305--322, March 2004.
• 8: Bret Hull , Kyle Jamieson , Hari Balakrishnan, Mitigating congestion in wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031512]
• 9: 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
• 10: Anders Lindgren , Avri Doria , Olov Schelén, Probabilistic routing in intermittently connected networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.7 n.3, July 2003 [doi>10.1145/961268.961272]
• 11: 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]
• 12: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 13: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 14: A. Rabagliati. Wizzy digital courier -- how it works.
• 15: E. M. Royer and C.-K. Toh. A review of current routing protocols for ad hoc mobile wireless networks. IEEE Personal Communications, 6:46--55, 1999.
• 16: Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288286]
• 17: L. Song, D. Kotz, R. Jain, and X. He. Evaluating location predictors with extensive wi-fi mobility data. In IEEE INFOCOM 2004, 2004.
• 18: K. Tan, Q. Zhang, and W. Zhu. Shortest path routing in partially connected ad hoc networks. In IEEE GLOBECOM, 2003.
• 19: A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, Apr 2000.

INDEX TERMS

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

General Terms:
Design, Performance

Keywords:
delay tolerant network, route metrics, routing