No symbol left behind: a link-layer protocol for rateless codes

Peter Anthony Iannucci, Jonathan Perry, Hari Balakrishnan, Devavrat ShahMobiCom 2012 · DOI

TL;DR

This paper introduces RateMore, a novel link-layer protocol designed to optimize the use of rateless codes in wireless networks. By learning the decoding characteristics of the channel and employing dynamic programming, RateMore significantly reduces transmission overhead and improves throughput compared to existing HARQ schemes, especially in challenging wireless environments.

What Problem Does This Paper Address?

Wireless communication is inherently unreliable due to factors like user movement, device interference, and fluctuating channel conditions. Traditional approaches like fixed-rate codes struggle to adapt efficiently, leading to wasted transmissions or lost data. Rateless codes offer a promising solution by allowing receivers to utilize all received symbols, regardless of the transmission rate. However, effectively coordinating the sender and receiver to determine when to send more data and when to pause for feedback is a critical challenge. Sending feedback itself consumes valuable transmission time, creating a trade-off between timely updates and efficient data transfer. This paper addresses the problem of optimizing this trade-off to maximize wireless throughput.

Methods

The core of RateMore lies in its two main components:

  • Decoding CDF Learning: Instead of relying on explicit channel state information, RateMore learns the decoding Cumulative Distribution Function (CDF). This function probabilistically describes how many symbols are needed for a receiver to successfully decode a packet. The paper proposes a Gaussian approximation for this CDF, which can be efficiently learned online using exponentially-weighted moving averages of observed symbol counts.
  • Dynamic Programming for Optimal Transmission Schedule: With the learned decoding CDF and an estimate of the feedback delay (nf), RateMore employs a dynamic programming strategy. This strategy determines an optimal sequence of transmission lengths before each feedback pause, aiming to minimize the expected time to successfully decode a packet. This approach effectively balances the cost of sending more symbols against the cost of waiting for feedback.

Datasets

Not discussed in the paper. The authors used simulations with synthetic decoding CDFs and tested their protocol with various rateless codes (Spinal, Strider, Raptor) under different channel conditions (stationary AWGN, slow-fading Rayleigh, fast-fading Rayleigh).

Key Insights and Ideas

  • Decoding CDF as a Unified Abstraction: The decoding CDF is a powerful, code-agnostic way to capture all system uncertainties (channel variations, code performance). This allows the RateMore protocol to be independent of the specific rateless code used.
  • Dynamic Programming for Optimal Trade-offs: The problem of determining the optimal transmission schedule can be framed as a dynamic game against "nature" (the unknown decoding requirement). Dynamic programming provides a principled way to solve this, even with an infinite horizon.
  • Learning is Sufficient and Practical: The paper demonstrates that learning an approximate decoding CDF (specifically, a Gaussian approximation) is sufficient for near-optimal performance, outperforming schemes that rely on explicit channel state estimation.
  • Packet Packing and Block ACKs are Crucial for Efficiency: For practical wireless systems, especially with high bandwidth, aggregating multiple packets and using block ACKs is essential to amortize the cost of feedback and inter-frame spaces.

Key Results

  • Significant Overhead Reduction: RateMore reduces overhead by 2.6x to 3.9x compared to 802.11-style ARQ and 2.8x to 5.4x compared to 3GPP-style "Try-after-n" HARQ.
  • Throughput Improvement: This overhead reduction translates to link-layer throughput improvements of up to 26%.
  • High Efficiency: RateMore achieves efficiency consistently above 95% at medium and high SNRs, and over 88% at low SNRs, even with high feedback costs.
  • Robust Learning: The Gaussian approximation for CDF learning performs within 1.57% of ideal adaptation on fading channels and incurs only a 0.25%-6% loss in throughput compared to knowing the true CDF.
  • Efficient Streaming: The protocol enables efficient streaming of multimedia content under latency constraints, achieving low channel occupancy.

Limitations and Future Work

  • Assumptions: The current implementation assumes half-duplex radios and reliable ACKs at low rates. It also assumes that the feedback delay ($n_f$) is exogenously given and amortized over multiple packets.
  • Future Work: The authors suggest exploring multi-hop latency constraints and unreliable service classes as interesting directions for future research. They also note that while their Gaussian approximation works well, other parametric distributions might offer further improvements. The current work focuses on stationary and slow-fading channels; performance on very fast-fading channels could be further investigated.

Summary updated

BibTeX
@inproceedings{iannucci2012no,
  author = {Peter Anthony Iannucci and Jonathan Perry and Hari Balakrishnan and Devavrat Shah},
  title = {{No symbol left behind: a link-layer protocol for rateless codes}},
  booktitle = {MobiCom},
  year = {2012},
  doi = {10.1145/2348543.2348549},
}
Figure