Multicasting in delay tolerant networks: semantic models and routing algorithms

ABSTRACT

Delay tolerant networks (DTNs) are a class of emerging networks that experience frequent and long-duration partitions. These networks have a variety of applications in situations such as crisis environments and deep-space communication. In this paper, we study the problem of multicasting in DTNs. Multicast supports the distribution of data to a group of users, a service needed for many potential DTN applications. While multicasting in the Internet and mobile ad hoc networks has been studied extensively, due to the unique characteristic of frequent partitioning in DTNs, multicasting in DTNs is a considerably different and challenging problem. It not only requires new definitions of multicast semantics but also brings new issues to the design of routing algorithms. In this paper, we propose new semantic models for DTN multicast and develop several multicast routing algorithms with different routing strategies. We present a framework to evaluate these algorithms in DTNs. To the best of our knowledge, this is the first study of multicasting in DTNs. Our objectives are to understand how routing performance is affected by the availability of knowledge about network topology and group membership and to guide the design of DTN routing protocols. Using ns simulations, we find that efficient multicast routing for DTNs can be constructed using only partial knowledge. In addition, accurate topology information is generally more important in routing than up-to-date membership information. We also find that routing algorithms that forward data along multiple paths achieve better delivery ratios, especially when available knowledge is limited.

REFERENCES

• 1: DARPA Disruption Tolerant Networking Program: http://www.darpa.mil/ato/solicit/dtn.
• 2: Lorenzo Aguilar, Datagram routing for internet multicasting, Proceedings of the ACM SIGCOMM symposium on Communications architectures and protocols: tutorials & symposium, p.58-63, June 06-08, 1984, Montréal, Quebec, Canada, United States
• 3: Tony Ballardie , Paul Francis , Jon Crowcroft, Core based trees (CBT), Conference proceedings on Communications architectures, protocols and applications, p.85-95, September 13-17, 1993, San Francisco, California, United States
• 4: S. Burleigh, A. Hooke, L. Torgerson, K. Fall, V. Cerf, B. Durst, K. Scott, and H. Weiss. Delay-tolerant networking -- an approach to interplanetary internet. IEEE Communications Magazine, June 2003.
• 5: A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott. Pocket switched networks: Real-world mobility and its consequences for opportunistic forwarding. Technical Report UCAM-CL-TR-617, University of Cambridge, Computer Lab, February 2005.
• 6: Ching-Chuan Chiang , Mario Gerla , Lixia Zhang, Forwarding Group Multicast Protocol (FGMP) for multihop, mobile wireless networks, Cluster Computing, v.1 n.2, p.187-196, 1998 [doi>10.1023/A:1019037500012]
• 7: Stephen E. Deering , David R. Cheriton, Multicast routing in datagram internetworks and extended LANs, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.85-110, May 1990 [doi>10.1145/78952.78953]
• 8: Stephen Deering , Deborah Estrin , Dino Farinacci , Van Jacobson , Ching-Gung Liu , Liming Wei, An architecture for wide-area multicast routing, Proceedings of the conference on Communications architectures, protocols and applications, p.126-135, August 31-September 02, 1994, London, United Kingdom
• 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: A. A. Hasson, R. Fletcher, and A. Pentland. DakNet: A road to universal broadband connectivity. Wireless Internet UN ICT Conference Case Study, 2003.
• 11: Qingfeng Huang , Chenyang Lu , Gruia-Catalin Roman, Spatiotemporal multicast in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958516]
• 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: D. Johnson and D. Maltz. Dynamic source routing in ad-hoc wireless networks. In ACM SIGCOMM, August 1996.
• 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: S. Lee, M. Gerla, and C. Chiang. On-demand multicast routing protocol (ODMRP) for ad hoc networks. Internet draft, June 1999.
• 16: J. Moy. Multicast extensions to OSPF. RFC 1584, Mar. 1994.
• 17: Network simulator 2. http://www.isi.edu/nsnam/ns/.
• 18: Elizabeth M. Royer , Charles E. Perkins, Multicast operation of the ad-hoc on-demand distance vector routing protocol, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.207-218, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313538]
• 19: R. Shah, S. Roy, S. Jain, and W. Brunette. Data MULEs: Modeling a three-tier architecture for sparse sensor networks. In IEEE SNPA Workshop, 2003.
• 20: A. Vahdat and D. Becker. Epidemic routing for partially-connected ad hoc networks. Technical report, Duke University, 2000.
• 21: Randolph Y. Wang , Sumeet Sobti , Nitin Garg , Elisha Ziskind , Junwen Lai , Arvind Krishnamurthy, Turning the postal system into a generic digital communication mechanism, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 22: H. Wu, R. Fujimoto, and G. Riley. Analytical models for data dissemination in vehicle-to-vehicle networks. In IEEE VTC 2004/Fall.
• 23: 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]
• 24: W. Zhao, M. Ammar, and E. Zegura. Multicasting in delay tolerant networks: Semantic models and routing algorithms. Technical report, College of Computing, Georgia Institute of Technology, 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

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

General Terms:
Algorithms, Design, Performance

Keywords:
delay tolerant networks, multicast, semantic model