Prioritized epidemic routing for opportunistic networks

ABSTRACT

We describe PRioritized EPidemic (PREP) for routing in opportunistic networks. PREP prioritizes bundles based on costs to destination, source, and expiry time. Costs are derived from per-link "average availability" information that is disseminated in an epidemic manner. PREP maintains a gradient of replication density that decreases with increasing distance from the destination. Simulation results show that PREP outperforms AODV and Epidemic Routing by a factor of about 4 and 1.4 respectively, with the gap widening with decreasing density and decreasing storage. We expect PREP to be of greater value than other proposed solutions in highly disconnected and mobile networks where no schedule information or repeatable patterns exist.

REFERENCES

• 1: Wizzyproject.http://www.wizzy.org.za.
• 2: B. Burns, O. Brock, and B. Levine. Mv routing and capacity building in disruption tolerant networks. In In Proc. IEEE Infocom, August 2005.
• 3: E.W. Dijkstra. A note on two problems in connexion with graphs. Numer. Math. 1:269, 271, 1959.
• 4: J. Burgess et al. Maxprop: Routing for vehicle-based disruption tolerant networks. In In Proc. IEEE Infocom, 2006.
• 5: 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
• 6: S. Burleigh et al. Delay-tolerant networking: An approach to interplanetary internet. IEEE Communications Magazine, June, 2003.
• 7: T. Spyropoulos et al. Single-copy routing in intermittently connected mobile networks. In In Proc. IEEE SECON, 2004.
• 8: V. Cerf et al. Delay-tolerant network architecture, April 2007. Internet RFC 4838.
• 9: K. Harras, K. Almeroth, and E. Belding-Royer. Delay tolerant mobile networks (dtmns): Controlled ooding schemes in sparse mobile networks, 2005.
• 10: 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
• 11: 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
• 12: Evan P. C. Jones , Lily Li , Paul A. S. Ward, Practical routing in delay-tolerant networks, Proceeding 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]
• 13: A. Lindgren, A. Doria, and O. Scheln. Probabilistic routing in intermittently connected networks. In Proc. ACM Mobihoc, 2003.
• 14: P. Marshall. The disruption tolerant networking program, 2005. http://www.darpa.mil/sto/solicitations/DTN/briefs.htm.
• 15: 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]
• 16: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Spray and wait: an efficient routing scheme for intermittently connected mobile networks, Proceeding 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]
• 17: P. Jacquet T. Clausen. Optimized link state routing protocol (olsr), October 2003. Internet RFC 3626.
• 18: A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks, 2000.
• 19: Z. Zhang. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: Overview and challenges. IEEE Communication Surveys and Tutorials, Jan 2006.
• 20: 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]
• 21: Wenrui Zhao , Mostafa Ammar , Ellen Zegura, Multicasting in delay tolerant networks: semantic models and routing algorithms, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.268-275, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080145]

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
disruption tolerant networks, epidemic routing, opportunistic networks