Message routing on potential-fields in forwarding-based DTNs

ABSTRACT

In delay (or disruption) tolerant networks(DTNs), the physical network is partitioned and the topology changes by node contacts. In most cases, there are no globally synchronized topology information available, which makes routing in DTNs challenging. To enable message routing without topology, we take potential-based routing(PBR) approach. We define potential-based message forwarding (PBMF) model and potential field construction method, which can be implemented in autonomously and distributed manner. We also discuss message overflow phenomenon, which should be considered in the deployment phase. This work assumes forwarding-based message delivery because of its lightweightness in delivery management. We developed a prototype system and evaluated (1) the behavior of potential-field and message delivery and (2) the model of message overflow. We also carried out a 100-node scale simulation and found that compared to epidemic routing, (3) about 50% of delivery was performed within three times of the best delivery latency and (4) the usage of message storage was reduced to 1%.

REFERENCES

• 1: Anindya Basu , Alvin Lin , Sharad Ramanathan, Routing using potentials: a dynamic traffic-aware routing algorithm, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863962]
• 2: Christian Bettstetter , Giovanni Resta , Paolo Santi, The Node Distribution of the Random Waypoint Mobility Model for Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.2 n.3, p.257-269, July-September 2003 [doi>10.1109/TMC.2003.1233531]
• 3: Chao Chen , Zesheng Chen, Evaluating contacts for routing in highly partitioned mobile networks, Proceedings of the 1st international MobiSys workshop on Mobile opportunistic networking, June 11-11, 2007, San Juan, Puerto Rico [doi>10.1145/1247694.1247698]
• 4: X. Chen and A. L. Murphy. Enabling disconnected transitive communication in mobile ad hoc networks. In ACM POMC, 2001.
• 5: Michael Demmer , Kevin Fall, DTLSR: delay tolerant routing for developing regions, Proceedings of the 2007 workshop on Networked systems for developing regions, August 27-27, 2007, Kyoto, Japan [doi>10.1145/1326571.1326579]
• 6: 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]
• 7: Y. Ganjali and N. McKeown. Routing in a highly dynamic topology. In IEEE SECON, pages 164--175, 2005.
• 8: Sami Iren , Paul D. Amer , Phillip T. Conrad, The transport layer: tutorial and survey, ACM Computing Surveys (CSUR), v.31 n.4, p.360-404, Dec. 1999 [doi>10.1145/344588.344609]
• 9: 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
• 10: V. Lenders, M. May, and B. Plattner. Density-based vs. proximity-based anycast routing for mobile networks. In IEEE INFOCOM, pages 1--13, 2006.
• 11: A. Lindgren, A. Doria, and O. Schelen. Probabilistic routing in intermittently connected networks. Lecture Notes in Computer Science, 3126:239--254, sep 2004.
• 12: H. Liu, Z.-L. Zhang, J. Srivastava, and V. Firoiu. PWave: A multi-source multi-sink anycast routing framework for wireless sensor networks. Lecture Notes in Computer Science, 4479:179--190, nov 2007.
• 13: G. Malkin. RFC2453: Rip version 2, 1998.
• 14: J. Moy. RFC2328: Ospf version 2, 1998.
• 15: Hideya Ochiai , Hiroshi Esaki, Mobility entropy and message routing in community-structured delay tolerant networks, Proceedings of the 4th Asian Conference on Internet Engineering, November 18-20, 2008, Pratunam, Bangkok, Thailand [doi>10.1145/1503370.1503396]
• 16: C. Perkins, E. Belding-Royer, and S. Das. RFC1058: Ad hoc on-demand distance vector (aodv) routing, 2003.
• 17: E. Rosen , A. Viswanathan , R. Callon, Multiprotocol Label Switching Architecture, RFC Editor, 2001
• 18: 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]
• 19: T. Spyropoulos, T. Turletti, and K. Obraczka. Utility-based message replication for intermittently connected heterogeneous networks. In IEEE WoWMoM, 2007.
• 20: A. Vahdat and D. Becker. Epidemic routing for partially-connected ad hoc networks. Technical report, Duke University, 2000.

INDEX TERMS

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

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

General Terms:
Algorithms, Performance, Theory

Keywords:
delay tolerant networks, forwarding-based message delivery, potential-based routing