Using redundancy to cope with failures in a delay tolerant network
- 22 August 2005
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGCOMM Computer Communication Review
- Vol. 35 (4) , 109-120
- https://doi.org/10.1145/1090191.1080106
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.Keywords
This publication has 12 references indexed in Scilit:
- Erasure-coding based routing for opportunistic networksPublished by Association for Computing Machinery (ACM) ,2005
- High Availability in DHTs: Erasure Coding vs. ReplicationPublished by Springer Nature ,2005
- Routing in a delay tolerant networkPublished by Association for Computing Machinery (ACM) ,2004
- A message ferrying approach for data delivery in sparse mobile ad hoc networksPublished by Association for Computing Machinery (ACM) ,2004
- Outage probability of multiple antenna systems: optimal transmission and impact of correlationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Taming the underlying challenges of reliable multihop routing in sensor networksPublished by Association for Computing Machinery (ACM) ,2003
- Data MULEs: modeling a three-tier architecture for sparse sensor networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A delay-tolerant network architecture for challenged internetsPublished by Association for Computing Machinery (ACM) ,2003
- A digital fountain approach to asynchronous reliable multicastIEEE Journal on Selected Areas in Communications, 2002
- Efficient erasure correcting codesIEEE Transactions on Information Theory, 2001