Scalable routing in delay tolerant networks

ABSTRACT

The non-existence of an end-to-end path poses a challenge inadapting the traditional routing algorithms to delay tolerantnetworks (DTNs). Previous works include centralized rout-ing approaches based on deterministic mobility, ferry-basedrouting with deterministic or semi-deterministic mobility, flooding-based approaches for networks with general mobility, and probability-based routing for semi-deterministicmobility models. Unfortunately, none of these methods canguarantee both scalability and delivery. In this work, we investigate scalable deterministic routing in DTNs. Instead of routing with global contact knowledge, we propose a simplified DTN model and a routing algorithm which routes on contact information compressed by three combined methods. Analytical studies and simulation results show that the performance of our proposed routing algorithm, DTN Hierarchical Routing (DHR), approximates that of the optimal time-space Dijkstra's algorithm in terms of delay and hop-count. At the same time, the per node storage overhead is substantially reduced and becomes scalable. Although our work is based on a simplified DTN model, we believe this approach will lay a groundwork for the understanding of scalable routing in DTNs.

REFERENCES

• 1: V. Cerf, S. Burleigh, A. Hooke, L. Torgerson, R. Durst, K. Scott, K. Fall, and H. Weiss. Delay-tolerant network architecture. In Internet draft: draft-irrf-dtnrg-arch.txt, DTN Research Group, 2006.
• 2: B. Chen and R. Morris. L+: Scalable landmark routing and address lookup fo multi-hop wireless network. In MIT LCS Technical Report 837, March 2002.
• 3: Henri Dubois-Ferriere , Matthias Grossglauser , Martin Vetterli, Age matters: efficient route discovery in mobile ad hoc networks using encounter ages, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778446]
• 4: A. Ephremides, J. E. Wieselthier, and D. J. Baker. A design concept for reliable mobile radio networks with frequency hoping signaling. Proc. of IEEE, 75(1):56--73, January 1987.
• 5: J. Eriksson, M. Faloutsos, and S. Krishnamurthy. Scalable ad hoc routing: The case for dynamic addressing. In Proc. of IEEE INFOCOM, 2004.
• 6: J. Ghosh, S. J. Philip, and C. Qiao. Sociological orbit aware location approximation and routing (SOLAR) in MANET. In Proc. of ACM MobiHoc, 2005.
• 7: J. Haas, J. Y. Halpern, and L. Li. Gossip-based ad hoc routing. In Proc. of IEEE INFOCOM, 2002.
• 8: 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
• 9: Jérémie Leguay , Timur Friedman , Vania Conan, DTN routing in a mobility pattern space, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.276-283, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080146]
• 10: A. Lindgren, A. Doria, and O. Schelen. Probabilistic routing in intermittently connected networks. Lecture Notes in Computer Science, 3126:239--254, Aug 2004.
• 11: S. Merugu, M. Ammar, and E. Zegura. Routing in space and time in network with predictable mobility. In Technical report: GIT-CC-04-07, College of Computing, Georgia Tech, 2004.
• 12: G. Pei, M. Gerla, X. Hong, and C. Chiang. A wireless hierarchical routing protocol with group mobility. In Proc. of WCNC, 1999.
• 13: Ram Ramanathan , Martha Steenstrup, Hierarchically-organized, multihop mobile wireless networks for quality-of-service support, Mobile Networks and Applications, v.3 n.1, p.101-119, June 1998 [doi>10.1023/A:1019148009641]
• 14: P. Sinha, R. Sivakumar, and V. Bharghavan. Enhancing ad hoc routing with dynamic virtual infrastructures. In Proc. of IEEE INFOCOM, 2001.
• 15: M. M. B. Tariq, M. Ammar, and E. Zegura. Message ferry route design for sparse ad hoc networks with mobile nodes. In Proc. of ACM MobiHoc, 2005.
• 16: A. Vahdate and D. Becker. Epidemic routing for partially-connected ad hoc networks. In Technical Report, Duke University, 2002.
• 17: Jie Wu , Shuhui Yang , Fei Dai, Logarithmic Store-Carry-Forward Routing in Mobile Ad Hoc Networks, IEEE Transactions on Parallel and Distributed Systems, v.18 n.6, p.735-748, June 2007 [doi>10.1109/TPDS.2007.1061]
• 18: W. Zhao , M. Ammar , E. Zegura, A message ferrying approach for data delivery in sparse mobile ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989483]

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
contact, delay tolerant networks (DTNs), delivery, hierarchical routing, motion cycle, scalability, simulation