Delegation forwarding

ABSTRACT

Mobile opportunistic networks are characterized by unpredictable mobility, heterogeneity of contact rates and lack of global information. Successful delivery of messages at low costs and delays in such networks is thus challenging. Most forwarding algorithms avoid the cost associated with flooding the network by forwarding only to nodes that are likely to be good relays, using a quality metric associated with nodes. However it is non-trivial to decide whether an encountered node is a good relay at the moment of encounter. Thus the problem is in part one of online inference of the quality distribution of nodes from sequential samples, and has connections to optimal stopping theory. Based on these observations we develop a new strategy for forwarding, which we refer to as delegation forwarding.

We analyse two variants of delegation forwarding and show that while naive forwarding to high contact rate nodes has cost linear in the population size, the cost of delegation forwarding is proportional to the square root of population size. We then study delegation forwarding with different metrics using real mobility traces and show that delegation forwarding performs as well as previously proposed algorithms at much lower cost. In particular we show that the delegation scheme based on destination contact rate does particularly well.

REFERENCES

• 1: M. Ajtai , N. Megiddo , O. Waarts, Improved algorithms and analysis for secretary problems and generalizations, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.473, October 23-25, 1995
• 2: 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
• 3: Andrei Z. Broder , Adam Kirsch , Ravi Kumar , Michael Mitzenmacher , Eli Upfal , Sergei Vassilvitskii, The hiring problem and Lake Wobegon strategies, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1184-1193, January 20-22, 2008, San Francisco, California
• 4: Burgess, J., Gallagher, B., Jensen, D., and Levine, B. N. MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks. In Proc. IEEE INFOCOM (April 2006).
• 5: Han Cai , Do Young Eun, Crossing over the bounded domain: from exponential to power-law inter-meeting time in MANET, 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.1287873]
• 6: Chaintreau, A., Hui, P., Crowcroft, J., Diot, C., Gass, R., and Scott, J. Pocket Switched Networks: Real-world mobility and its consequences for Opportunistic Forwarding. Tech. Rep. UCAM-CL-TR-617, University of Cambridge, 2005.
• 7: Augustin Chaintreau , Pan Hui , Jon Crowcroft , Christophe Diot , Richard Gass , James Scott, Impact of Human Mobility on Opportunistic Forwarding Algorithms, IEEE Transactions on Mobile Computing, v.6 n.6, p.606-620, June 2007 [doi>10.1109/TMC.2007.1060]
• 8: 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]
• 9: 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]
• 10: Nathan Eagle , Alex (Sandy) Pentland, Reality mining: sensing complex social systems, Personal and Ubiquitous Computing, v.10 n.4, p.255-268, March 2006 [doi>10.1007/s00779-005-0046-3]
• 11: Vijay Erramilli , Augustin Chaintreau , Mark Crovella , Christophe Diot, Diversity of forwarding paths in pocket switched networks, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298330]
• 12: Michele Garetto , Paolo Giaccone , Emilio Leonardi, Capacity scaling in delay tolerant networks with heterogeneous mobile nodes, 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.1288114]
• 13: 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
• 14: Evan P. C. Jones , Lily Li , Paul A. S. Ward, Practical routing in delay-tolerant networks, Proceedings 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]
• 15: Thomas Karagiannis , Jean-Yves Le Boudec , Milan Vojnović, Power law and exponential decay of inter contact times between mobile devices, 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.1287875]
• 16: 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]
• 17: 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]
• 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: Marvin McNett , Geoffrey M. Voelker, Access and mobility of wireless PDA users, ACM SIGMOBILE Mobile Computing and Communications Review, v.7 n.4, October 2003 [doi>10.1145/965732.965744]
• 20: Sarafijanovic-Djukic, N., Pidrkowski, M., and Grossglauser, M. Island hopping: Efficient mobility assisted forwarding in partitioned networks. In IEEE SECON '06.
• 21: Shiryaev, A. N. Optimal Stopping Rules. Springer, 2008.
• 22: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Efficient routing in intermittently connected mobile networks: the multiple-copy case, IEEE/ACM Transactions on Networking (TON), v.16 n.1, p.77-90, February 2008 [doi>10.1109/TNET.2007.897964]
• 23: Vahdat, A., and Becker, D. Epidemic Routing for Partially Connected Ad Hoc Networks. Tech. Rep. CS-200006, Duke University, 2000.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Store and forward networks

General Terms:
Algorithms, Measurement, Performance

Keywords:
delay-tolerant networks, forwarding algorithms, mobile opportunistic networks, optimal stopping, pocket switched networks