Loss-aware network coding for unicast wireless sessions: design, implementation, and performance evaluation

Shravan K. Rayanchu, Sayandeep Sen, Jianming Wu, Suman Banerjee, Sudipta SenguptaSIGMETRICS 2008 · DOI

TL;DR

This paper introduces CLONE, a novel network coding framework designed to boost throughput in lossy wireless networks. Unlike previous approaches that minimize transmissions, CLONE strategically injects redundancy to combat packet loss, achieving up to a 2x throughput improvement in simulations and real-world tests.

What Problem Does This Paper Address?

Wireless networks, especially mesh networks, are prone to packet loss due to interference and signal degradation. Network coding offers a way to improve efficiency by allowing intermediate nodes to combine packets and send them as a single coded unit, reducing the total number of transmissions needed. However, existing network coding techniques, like COPE, often focus on minimizing transmissions, which can be detrimental in lossy environments by eliminating all redundancy. This leaves valuable opportunities for improving throughput by strategically adding redundancy, especially in scenarios with high packet loss rates (e.g., 30% or more). The challenge is to find an effective way to introduce this redundancy without overwhelming the network or computational resources of wireless devices.

Methods

The paper proposes a suite of algorithms called CLONE (Coding with Loss-awareNEss). CLONE operates at the packet level and focuses on local, opportunistic coding. The core idea is to move beyond simply minimizing transmissions and instead embrace redundancy.

  • Loss-Aware Redundancy: CLONE algorithms strategically introduce redundancy by creating multiple coded packets or duplicate coded packets. This allows destinations to recover lost packets through alternative decoding paths.
  • Design Space Exploration: The authors explore a large design space for redundancy, proposing algorithms with varying levels of complexity and performance.
  • CLONE-kDSP: A heuristic for binary network coding (combining two packets at a time) that aims to find a set of edge-disjoint paths to meet a delivery probability threshold with minimal transmissions.
  • CLONE-k-Loop: A simpler, more practical version of CLONE-kDSP, which generates a sequence of k Type 1 edges forming a loop. This is the most deployable algorithm due to its lower computational cost.
  • CLONE-MultiXOR: A greedy heuristic for the general network coding problem (combining more than two packets). It aims to maximize the number of ways a packet can be decoded by each next-hop node.
  • Opportunistic Coding: CLONE operates opportunistically, using available packets and coding opportunities as they arise.
  • Implementation: CLONE was implemented on a 12-node testbed using the Click modular router and Atheros 5212 wireless cards, demonstrating its practical feasibility.

Datasets

Not discussed in the paper. The evaluation relies on simulations and experiments on a custom-built wireless testbed.

Key Insights and Ideas

  • Redundancy is Key in Lossy Wireless: The most significant insight is that in lossy wireless environments, minimizing transmissions is not always the optimal strategy. Introducing controlled redundancy through network coding can dramatically improve throughput by making the system more resilient to packet loss.
  • The Design Space is Rich: The authors highlight that there's a vast design space for loss-aware network coding, offering various trade-offs between computational complexity, redundancy levels, and performance gains.
  • Local and Opportunistic is Practical: CLONE's focus on local and opportunistic coding makes it suitable for deployment on existing wireless hardware, which has limited processing power.
  • Trade-offs Exist: Different CLONE algorithms offer varying levels of performance gains and computational costs. CLONE-MultiXOR provides the best performance but is computationally intensive, while CLONE-k-Loop is more practical for current hardware.

Key Results

  • Significant Throughput Gains: CLONE algorithms achieved up to a 2x improvement in throughput compared to no coding in simulations and experiments.
  • CLONE-k-Loop Performance: Even the simplest CLONE-k-Loop algorithm provided a considerable reduction in post-coding loss rates, reducing them by up to 50% in some scenarios. For instance, at a 10% link loss rate, it reduced the post-coding loss rate from 20% (no coding) to 2%.
  • CLONE-MultiXOR Superiority: CLONE-MultiXOR consistently outperformed other CLONE variants and no coding, achieving the lowest post-coding loss rates. For example, at a 10% link loss rate, it achieved a 0.6% loss rate compared to 2% for CLONE-k-Loop.
  • Computational Complexity: CLONE-k-Loop has a computational complexity comparable to COPE, making it readily deployable. CLONE-kDSP and CLONE-MultiXOR are more computationally intensive, requiring faster hardware for practical deployment.
  • Testbed Validation: Experimental results on a 12-node testbed confirmed the simulation findings, showing average throughput gains of around 43% for CLONE over no coding.

Limitations and Future Work

  • Computational Cost of Advanced Algorithms: The paper acknowledges that CLONE-kDSP and CLONE-MultiXOR are computationally expensive and may not be feasible on current wireless hardware. Future work could focus on optimizing these algorithms or leveraging faster hardware.
  • Hardware Limitations: The implementation of CLONE-k-Loop was feasible due to its lower computational demands, but more advanced algorithms were limited by current hardware processing speeds.
  • Generalization: While the paper focuses on unicast sessions, future work could explore CLONE's applicability to multicast or broadcast scenarios.
  • Protocol Integration: The authors suggest that further research is needed to effectively integrate network coding with other protocol mechanisms at different layers (MAC, network, transport, application) to maximize its benefits.
  • Exploration of Design Space: The paper presents a starting point for exploring the loss-aware network coding design space. Further research could delve deeper into optimizing redundancy strategies and coding packet combinations.

Summary updated

BibTeX
@inproceedings{rayanchu2008loss,
  author = {Shravan K. Rayanchu and Sayandeep Sen and Jianming Wu and Suman Banerjee and Sudipta Sengupta},
  title = {{Loss-aware network coding for unicast wireless sessions: design, implementation, and performance evaluation}},
  booktitle = {SIGMETRICS},
  year = {2008},
  doi = {10.1145/1375457.1375468},
}
Figure