Using redundancy to cope with failures in a delay tolerant network

ABSTRACT

We consider the problem of routing in a delay tolerant network (DTN) in the presence of path failures. Previous work on DTN routing has focused on using precisely known network dynamics, which does not account for message losses due to link failures, buffer overruns, path selection errors, unscheduled delays, or other problems. We show how to split, replicate, and erasure code message fragments over multiple delivery paths to optimize the probability of successful message delivery. We provide a formulation of this problem and solve it for two cases: a 0/1 (Bernoulli) path delivery model where messages are either fully lost or delivered, and a Gaussian path delivery model where only a fraction of a message may be delivered. Ideas from the modern portfolio theory literature are borrowed to solve the underlying optimization problem. Our approach is directly relevant to solving similar problems that arise in replica placement in distributed file systems and virtual node placement in DHTs. In three different simulated DTN scenarios covering a wide range of applications, we show the effectiveness of our approach in handling failures.

REFERENCES

• 1: G. J. Alexander and J. C. Francis. Portfolio Analysis. Prentice Hall, 1986.
• 2: H. Boche and E. A. Jorswieck. Outage Probability of Multiple Antenna Systems: Optimal Transmission and Impact of Correlation. In IEEE International Zurich Seminar (IZS), 2004.
• 3: J. W. Byers, M. Luby, and M. Mitzenmacher. A Digital Fountain Approach to Asynchronous Reliable Multicast. IEEE J-SAC, Special Issue on Network Support for Multicast Communication, 20(8), 2002.
• 4: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 5: CPLEX: Linear Programming Solver. http://www.ilog.com/.
• 6: M. Engles. Portfolio Optimization: Beyond Markowitz. Master's thesis, Leiden University, 2004.
• 7: 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]
• 8: 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
• 9: 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
• 10: S. Kim, R. Fonseca, and D. Culler. Reliable Transfer on Wireless Sensor Networks. In SECON, 2004.
• 11: W. Kuo and M. J. Zuo. Optimal Reliability Modeling: Principles and Applications. Wiley, 2002.
• 12: M. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman. Efficient Erasure Correcting Codes. In IEEE Transactions on Information Theory, 2001.
• 13: D. Maillard. Some Remarkable Spots on the Efficient Frontier. Conservatorie National des Arts et Metiers, 2004.
• 14: M. Mitzenmacher. Digital Fountains: A Survey and Look Forward. Information Theory Workshop, 2004.
• 15: A. Mohan, W. Hong, D. Gay, P. Buonadonna, T. Doeppner, and A. Mainwaring. End-to-End Performance Characterization of Sensornet Multihop Routing. In IEEE ICPS, 2005.
• 16: R. Rodrigues and B. Liskov. High Availability in DHTs: Erasure Coding vs. Replication. IPTPS, 2005.
• 17: S. Jain et al. Additional Proofs and Discussion Related to the Optimal use of Redundancy to Cope with Failures in a Delay Tolerant Network. Technical Report 2005-06-04, University of Washington, 2005.
• 18: R. Shah, S. Roy, S. Jain, and W. Brunette. Data MULEs: Modeling a Three-tier Architecture for Sparse Sensor Networks. In IEEE SNPA, 2003.
• 19: Rahul C. Shah , Sven Wietholter , Adam Wolisz , Jan M. Rabaey, Modeling and Analysis of Opportunistic Routing in Low Traffic Scenarios, Proceedings of the Third International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, p.294-304, April 04-06, 2005 [doi>10.1109/WIOPT.2005.30]
• 20: R. H. Tutuncu. Optimization in Finance. Advance Lecture on Mathematical Science and Information Science, 2003.
• 21: A. Vahdat and D. Becker. Epidemic Routing for Partially-connected Ad hoc Networks. Technical Report CS-2000-06, Duke University, 2000.
• 22: Yong Wang , Sushant Jain , Margaret Martonosi , Kevin Fall, Erasure-coding based routing for opportunistic networks, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.229-236, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080140]
• 23: Hakim Weatherspoon , John Kubiatowicz, Erasure Coding Vs. Replication: A Quantitative Comparison, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.328-338, March 07-08, 2002
• 24: Alec Woo , Terence Tong , David Culler, Taming the underlying challenges of reliable multihop routing in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958494]
• 25: 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]

INDEX TERMS

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

General Terms:
Algorithms, Performance, Theory

Keywords:
delay tolerant network, routing