Analysis of simple counting protocols for delay-tolerant networks

ABSTRACT

Mobile Wireless Delay-Tolerant Networks (DTNs) are wireless networks that suffer from intermittent connectivity, but enjoy the benefit of mobile nodes that can store and forward packets or messages, and can act as relays, bringing packets and messages closer to their destination through a selective forwarding policy. Many DTN protocols compensate for the unpredictability of the network by distributing multiple message copies in the hopes that at least one will eventually be delivered. As the number of message carriers becomes large these schemes experience diminishing marginal benefits from the addition of more message carriers. We describe and analyze the Simple Counting Protocol, an extremely simple and robust method for limiting the fraction of nodes that carry a copy of a message. We examine the performance of this protocol in conjunction with several abstract mobility models and show that the protocol performs reasonably well in diverse circumstances. The Simple Counting Protocol does not assume much about node mobility, and therefore should be useful for applications where little is known about node encounter patterns. The simplicity of its implementation will hopefully make it a useful substitute for epidemic routing as a naive lower bound in protocol performance comparisons.

We also show how the same simple techniques and principles can be applied in conjunction with more complex heuristic DTN protocols to reduce network resource usage, a scheme we call Intermediate Immunity.

REFERENCES

• 1: 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]
• 2: Sushant Jain , Michael Demmer , Rabin Patra , Kevin Fall, Using redundancy to cope with failures in a delay tolerant network, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 3: 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
• 4: 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]
• 5: Mirco Musolesi , Stephen Hailes , Cecilia Mascolo, An ad hoc mobility model founded on social network theory, Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 04-06, 2004, Venice, Italy [doi>10.1145/1023663.1023669]
• 6: Mirco Musolesi , Stephen Hailes , Cecilia Mascolo, Adaptive Routing for Intermittently Connected Mobile Ad Hoc Networks, Proceedings of the Sixth IEEE International Symposium on World of Wireless Mobile and Multimedia Networks, p.183-189, June 13-16, 2005 [doi>10.1109/WOWMOM.2005.17]
• 7: P. Nain, D. Towsley, B. Liu, and Z. Liu. Properties of random direction models. In INFOCOM 2005, 2005.
• 8: Matthew Seligman , Kevin Fall , Padma Mundur, Storage routing for DTN congestion control: Research Articles, Wireless Communications & Mobile Computing, v.7 n.10, p.1183-1196, December 2007 [doi>10.1002/wcm.v7:10]
• 9: R. C. Shah, S. Roy, S. Jain, and W. Brunette. Data mules: Modeling a three-tier architecture for sparse sensor networks. In Proceedings of the 2003 IEEE Workshop on Sensor Network Protocols and Applications, 2003.
• 10: Tara Small , Zygmunt J. Haas, Resource and performance tradeoffs in delay-tolerant wireless networks, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.260-267, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080144]
• 11: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Spray and wait: an efficient routing scheme for intermittently connected mobile networks, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.252-259, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080143]
• 12: A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, 2000.
• 13: B. Walker, T. C. Clancy, and J. Glenn. Using localized random walks to model delay-tolerant protocols. In submission.
• 14: 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.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, Theory

Keywords:
carrier fraction, delay-tolerant networks, epidemic routing, intermediate immunity, localized random walk, simple counting, time-weighted network storage