Erasure-coding based routing for opportunistic networks

By Yong Wang, Sushant Jain, Margaret Martonosi, Kevin R. Fall. WDTN '05, 2005

522 citations recorded by the source corpus.

Routing in Delay Tolerant Networks (DTN) with unpredictable node mobility is a challenging problem because disconnections are prevalent and lack of knowledge about network dynamics hinders good decision making. Current approaches are primarily based on redundant transmissions. They have either high overhead due to excessive transmissions or long delays due to the possibility of making wrong choices when forwarding a few redundant copies. In this paper, we propose a novel forwarding algorithm based on the idea of erasure codes. Erasure coding allows use of a large number of relays while maintaining a constant overhead, which results in fewer cases of long delays.We use simulation to compare the routing performance of using erasure codes in DTN with four other categories of forwarding algorithms proposed in the literature. Our simulations are based on a real-world mobility trace collected in a large outdoor wild-life environment. The results show that the erasure-coding based algorithm provides the best worst-case delay performance with a fixed amount of overhead. We also present a simple analytical model to capture the delay characteristics of erasure-coding based forwarding, which provides insights on the potential of our approach.

View Paper: https://www.semanticscholar.org/paper/f592307bc5972335f0972de073fd601d586d8061

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Delay-Tolerant Networking Architecture (2007, background): “More technical descriptions may be found in [KF03], [JFP04], [JDPF05], and [WJMF05].”
Performance analysis of mobility-assisted routing (2006, background): “Such networks are often collectively referred to as Delay Tolerant Networks (DTN) [1].”
Disruption-Tolerant Networking: A Comprehensive Survey on Recent Developments and Persisting Challenges (2012, background): “However, it was shown to improve the worst-case delay in [74].”
Evaluating Mobility Pattern Space Routing for DTNs (2005, background): “[20] reincode the messages with erasure codes and distribute the ir different parts over a large number of relays, so that the original messages can be reconstituted even if not all packe ts are received.”
Routing in Delay/Disruption Tolerant Networks: A Taxonomy, Survey and Challenges (2013, methodology): “Different from the work [23] in “Naive Replication“ family achieving the high delivery ratio via redundancy, the work in [101] concentrates on achieving the low overhead ratio using the concept of source Spray-and-Wait rather than binary Spray-and-Wait [22].”
Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges (2006, background): “Instead of optimally allocating a fixed portion of the coded blocks on each path from source to destination, it is proposed in [ 41 ] that coded blocks with replication factor r are equally split among the first mr relays (or contacts), for some constant m, and those relays must deliver the coded bl”
Routing in Flying Ad Hoc Networks: A Comprehensive Survey (2020, background): “As a result, FGPA achieved reduced transmission delay with low overhead compared to the other DTN routing protocols such as erasure coding (H-EC) [149] and spray and wait (SW) [150].”
DTN routing as a resource allocation problem (2007, unknown): “For example, several existing DTN routing algorithms [31, 29, 35, 24, 23, 3] route packets using the number of replicas as the heuristic, but the effect of replication varies with different routing metrics.”
Efficient Routing in Intermittently Connected Mobile Networks: The Single-Copy Case (2008, background): “or other multi-copy schemes [14], [21], [22], [26].”
Using redundancy to cope with failures in a delay tolerant network (2005, background): “Finally, we have some experience with the impact of erasure coding on the delay distribution of message delivery in opportunistic DTN networks, which we discuss separately in [22].”
MORA routing and capacity building in disruption-tolerant networks (2008, background): “Schemes also exist that use network coding [39], or restrict the number of copies of a packet [33,30,37,25].”
Practical Routing in Delay-Tolerant Networks (2005, background): “Erasure coding and networking coding schemes have also been investigated to attempt to keep the benefit of multiple copies while reducing the resource costs [49, 50].”
Socially-aware routing for publish-subscribe in delay-tolerant mobile ad hoc networks (2008, background): “certain degree of redundancy in the system [26], [27].”
Efficient Routing in Intermittently Connected Mobile Networks: The Multiple-Copy Case (2008, background): “In the context of disconnected networks, the performance of epidemic routing with or without contention has been addressed in a number of works [1], [15], [37]–[39].”