Forwarding in opportunistic networks with resource constraints

ABSTRACT

Effective forwarding in mobile opportunistic networks is a challenge, given the unpredictable mobility of nodes, short contact durations between nodes, wireless interference and limited buffer sizes.

Most forwarding algorithms aim at decreasing costs (relative to flooding the network) by forwarding only to nodes which are likely to be good relays. While it is non-trivial to decide if an encountered node is a good relay or not at the moment of encounter, it is harder still to prioritize which messages to transmit under the presence of short contact durations and which messages to drop when buffers become full.

The main objective of this paper is to study different message prioritization schemes using real measurements. Such schemes can be broadly divided into two categories - schemes which do not use any network information, and schemes which do. Examples of the former set of schemes include FIFO/LIFO etc. For the latter set of schemes, there is a key design choice: On one hand, we have the following scheme: when a forwarding opportunity presents itself, assign high priorities to messages which are relatively close to their intended destination. On the other hand, we can assign high priorities to messages which are farther away from their destination than closer messages. In order to decide if messages are close to their destination or not, we have to rely on a forwarding algorithm. For this, we use delegation forwarding schemes which have been shown to be efficient in terms of cost incurred in the network. We develop a new set of prioritization schemes based on delegation schemes. We consider these schemes in our empirical study.

REFERENCES

• 1: 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
• 2: BURGESS, J., GALLAGHER, B., JENSEN, D., AND LEVINE, B. N. MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks. In Proc. IEEE INFOCOM (April 2006).
• 3: 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]
• 4: 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]
• 5: James A. Davis , Andrew H. Fagg , Brian N. Levine, Wearable Computers as Packet Transport Mechanisms in Highly-Partitioned Ad-Hoc Networks, Proceedings of the 5th IEEE International Symposium on Wearable Computers, p.141, October 08-09, 2001
• 6: 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]
• 7: 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]
• 8: 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]
• 9: 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]
• 10: 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
• 11: 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]
• 12: 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]
• 13: 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]
• 14: Erik Nordström , Christophe Diot , Richard Gass , Per Gunningberg, Experiences from measuring human mobility using Bluetooth inquiring devices, Proceedings of the 1st international workshop on System evaluation for mobile platforms, p.15-20, June 11-11, 2007, San Juan, Puerto Rico [doi>10.1145/1247721.1247725]
• 15: Ram Ramanathan , Richard Hansen , Prithwish Basu , Regina Rosales-Hain , Rajesh Krishnan, Prioritized epidemic routing for opportunistic networks, Proceedings of the 1st international MobiSys workshop on Mobile opportunistic networking, June 11-11, 2007, San Juan, Puerto Rico [doi>10.1145/1247694.1247707]
• 16: SARAFIJANOVIC-DJUKIC, N., PIDRKOWSKI, M., AND GROSSGLAUSER, M. Island hopping: Efficient mobility assisted forwarding in partitioned networks. In IEEE SECON'06 (Reston, VA, USA).
• 17: SPYROPOULOS, T., PSOUNIS, K., AND RAGHAVENDRA, C. Efficient routing in intermittently connected mobile networks: The multi copy case. IEEE/ACM Trans. Netw. 2, 2 (2008), 477--486.
• 18: 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, pocket switched networks