An optimal probabilistic forwarding protocolin delay tolerant networks

ABSTRACT

Due to uncertainty in nodal mobility, DTN routing usually employs multi-copy forwarding schemes. To avoid the cost associated with flooding, much effort has been focused on probabilistic forwarding, which aims to reduce the cost of forwarding while retaining a high performance rate by forwarding messages only to nodes that have high delivery probabilities. This paper aims to provide an optimal forwarding protocol which maximizes the expected delivery rate while satisfying a certain constant on the number of forwardings per message. In our proposed optimal probabilistic forwarding (OPF) protocol, we use an optimal probabilistic forwarding metric derived by modeling each forwarding as an optimal stopping rule problem. We also present several extensions to allow OPF to use only partial routing information and work with other probabilistic forwarding schemes such as ticket-based forwarding. We implement OPF and several other protocols and perform trace-driven simulations. Simulation results show that the delivery rate of OPF is only 5% lower than epidemic, and 20% greater than the state-of-the-art delegation forwarding while generating 5% more copies and 5% longer delay.

REFERENCES

• 1: V. Cerf, S. Burleigh, A. Hooke, L. Torgerson, R. Durst, K. Scott, K. Fall, and H. Weiss. Delay Tolerant Networking Architecture. In Internet draft: draft-irrf-dtnrg-arch.txt, DTN Research Group, 2006.
• 2: A. Vahdate and D. Becker. Epidemic Routing for Partially-connected Ad Hoc Networks. In Technical Report, Duke University, 2002.
• 3: Vikram Srinivasan , Mehul Motani , Wei Tsang Ooi, Analysis and implications of student contact patterns derived from campus schedules, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161100]
• 4: Xiaolan Zhang , Jim Kurose , Brian Neil Levine , Don Towsley , Honggang Zhang, Study of a bus-based disruption-tolerant network: mobility modeling and impact on routing, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287876]
• 5: 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]
• 6: Vijay Erramilli , Mark Crovella , Augustin Chaintreau , Christophe Diot, Delegation forwarding, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China [doi>10.1145/1374618.1374653]
• 7: A. Lindgren, A. Doria, and O. Schelen. Probabilistic Routing in Intermittently Connected Networks. Lecture Notes in Computer Science, 3126:239--254, August 2004.
• 8: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Spray and Focus: Efficient Mobility-Assisted Routing for Heterogeneous and Correlated Mobility, Proceedings of the Fifth IEEE International Conference on Pervasive Computing and Communications Workshops, p.79-85, March 19-23, 2007 [doi>10.1109/PERCOMW.2007.108]
• 9: J. Burgess, B. Gallagher, D. Jensen, and B.N. Levine. MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networking. In Proc. of IEEE INFOCOM, 2006.
• 10: Aruna Balasubramanian , Brian Levine , Arun Venkataramani, DTN routing as a resource allocation problem, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 11: 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]
• 12: M. Grossglauser and M. Vetterli. Locating Nodes with Ease: Last Encounter Routing in Ad Hoc Networks through Mobility Diffusion. In Proc. of IEEE INFOCOM, 2003.
• 13: Optimal Stopping and Applications. http://www.math.ucla.edu/~tom/Stopping/Contents.html.
• 14: D. Watts and S. Strogatz. Collective Dynamics of Small-world Networks. Nature 393, 440, 1998.
• 15: Cong Liu , Jie Wu, Routing in a cyclic mobispace, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China [doi>10.1145/1374618.1374665]
• 16: 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
• 17: 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.
• 18: Cong Liu , Jie Wu, Scalable routing in delay tolerant networks, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288115]
• 19: J. Haas, J.Y. Halpern, and L. Li. Gossip-Based Ad Hoc Routing. In Proc. of IEEE INFOCOM, 2002.
• 20: Elizabeth M. Daly , Mads Haahr, Social network analysis for routing in disconnected delay-tolerant MANETs, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288113]
• 21: Pan Hui , Jon Crowcroft , Eiko Yoneki, Bubble rap: social-based forwarding in delay tolerant networks, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China [doi>10.1145/1374618.1374652]
• 22: 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]
• 23: Libo Song , David F. Kotz, Evaluating opportunistic routing protocols with large realistic contact traces, Proceedings of the second ACM workshop on Challenged networks, September 14-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1287791.1287799]
• 24: Utku Günay Acer , Shivkumar Kalyanaraman , Alhussein A. Abouzeid, Weak state routing for large scale dynamic networks, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287888]
• 25: CRAWDAD data set. Downloaded from http://crawdad.cs.dartmouth.edu/.

INDEX TERMS

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

General Terms:
Algorithms, Measurement, Performance

Keywords:
delay tolerant networks, optimal stopping rule, routing