Network coding for efficient communication in extreme networks

By J. Widmer, J. L. Boudec. WDTN '05, 2005

455 citations recorded by the source corpus.

Some forms of ad-hoc networks need to operate in extremely performance-challenged environments where end-to-end connectivity is rare. Such environments can be found for example in very sparse mobile networks where nodes "meet" only occasionally and are able to exchange information, or in wireless sensor networks where nodes sleep most of the time to conserve energy. Forwarding mechanisms in such networks usually resort to some form of intelligent flooding, as for example in probabilistic routing.We propose a communication algorithm that significantly reduces the overhead of probabilistic routing algorithms, making it a suitable building block for a delay-tolerant network architecture. Our forwarding scheme is based on network coding. Nodes do not simply forward packets they overhear but may send out information that is coded over the contents of several packets they received. We show by simulation that this algorithm achieves the reliability and robustness of flooding at a small fraction of the overhead.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/5510836fe529903644d3499821ca157a70fe962c

How researchers see this paper

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

In Computer Networks and Communications

Citations in the corpus

Survey of Important Issues in UAV Communication Networks (2016, background): “In [143], the authors have shown that network coding performs better than probabilistic forwarding in disruption prone networks.”
Routing in Delay/Disruption Tolerant Networks: A Taxonomy, Survey and Challenges (2013, methodology): “The work in [106] is regarded as a hybrid of Gossip routing [96] and Epidemic routing [21].”
Network coding: an instant primer (2006, background): “Algorithms for challenging wireless networks which may be very sparse or highly mobile are investigated in [28].”
A survey of practical issues in underwater networks (2006, background): “For example, old packets representing delivered data can be removed from the network using broadcast acknowledgments [53], and network coding [57, 58] can be used to efficiently take advantage of multiple paths.”
Practical Routing in Delay-Tolerant Networks (2005, methodology): “This is the same as the “death certificate” concept in epidemic algorithms [8], and it has been shown to reduce the buer space requirements in delay-tolerant networks [ 41 , 15].”
Efficient Routing in Intermittently Connected Mobile Networks: The Multiple-Copy Case (2008, background): “Despite a number of existing proposals for opportunistic routing [12]–[16] the answer to the previous question has usually been “everyone” or “almost everyone”.”
Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges (2006, methodology): “A probabilistic forwarding approach based on network coding is proposed for DTNs in [ 42 ].”
Efficient Routing in Intermittently Connected Mobile Networks: The Single-Copy Case (2008, background): “K. Psounis and C. S. Raghavendra are with the Department of Electrical Engineering and Computer Science, University of Southern California, Los Angeles, CA 90089, USA (e-mail: kpsounis@usc.edu; raghu@usc.edu).”
Opportunistic networking: data forwarding in disconnected mobile ad hoc networks (2006, background): “Dissemination-based algorithms also include network-coding-based routing [14], which takes an original approach to limit message flooding.”
Evaluating Mobility Pattern Space Routing for DTNs (2005, background): “Widmer et al. [21] have explored network coding techniques.”