The quest for LEDBAT fairness

Giovanna Carofiglio, Luca Muscariello, Dario Rossi, Silvio Valenti

Abstract

BitTorrent developers recently introduced LEDBAT (Low Extra Delay Background Transfer), a delay-based congestion control algorithm designed to provide a "lower than Best Effort" service. While intended to yield to interactive traffic, LEDBAT suffers from a significant "late-comer advantage" where newer flows aggressively starve existing ones. This study identifies the protocol's additive decrease mechanism as the root cause of this unfairness and evaluates countermeasures, including probabilistic window drops and multiplicative decrease, to restore equitable bandwidth sharing.

The Problem: Late-Comer Advantage

LEDBAT aims to utilize spare bandwidth without impacting high-priority traffic by monitoring queuing delay relative to a "base delay" (the minimum observed round-trip time). However, if a new flow begins while an existing LEDBAT flow is already saturating the link, the newcomer misidentifies the current queue as the empty state. This leads to an artificially high delay target, allowing the late-comer to become more aggressive and eventually push the original flow into total starvation.

The late-comer advantage: A new flow (Flow 2) incorrectly estimates base delay and starves the original flow (left), a phenomenon that scales to multiple flows (right) due to a persistent queue (middle).

Investigating Solutions

The authors investigated the root cause of this instability using fluid modeling and packet-level simulations. They evaluated four potential remedies:

  1. Random Pacing: Adding jitter to transmissions to diversify delay samples.
  2. Slow-start: Using a TCP-like aggressive start to force a buffer reset.
  3. Probabilistic Window Dropping: Introducing a small chance ($p$) of halving the congestion window upon receiving an ACK.
  4. Multiplicative Decrease: Replacing linear decrease with a multiplicative factor ($\beta$) when delay targets are exceeded.

Key Results and Insights

  • Ineffective Measures: Random pacing failed to prevent starvation, only slightly delaying the inevitable takeover.
  • Partial Success with Slow-Start: While Slow-Start helped mitigate the late-comer advantage by forcing a queue reset, it was considered too aggressive for a background protocol, as it could cause packet loss for the interactive traffic LEDBAT is meant to protect.
Evaluation of the Slow-Start mechanism, which provides a partial but overly aggressive solution to the late-comer problem.
  • Robust Solutions: Both Probabilistic Drops and Multiplicative Decrease proved highly effective. A drop probability between $10^{-4}$ and $10^{-3}$ or a small multiplicative decrease factor (e.g., $\beta = 0.05$) allowed flows to converge to a fair share while maintaining high link efficiency.

The Root Cause: The Additive Decrease Trap

The study's "aha moment" was the realization that the problem is structural. LEDBAT’s original linear (additive) decrease is too gentle to ever fully empty the queue, preventing late-comers from discovering the true base delay. By introducing randomness or more aggressive decrease mechanisms, the protocol can break out of these persistent unfair states.

Conclusion

Ensuring fairness in LEDBAT requires moving beyond simple linear adjustments. While a tradeoff exists between efficiency and fairness, implementing multiplicative decrease or probabilistic drops provides a robust way to prevent flow starvation and fulfill LEDBAT's promise of being a "nice" background protocol.

Summary updated

Abstract

BitTorrent developers have recently introduced a new application layer congestion control algorithm based on UDP framing at transport layer and currently under definition at the IETF LEDBAT Working Group. LEDBAT is a delay-based protocol which aims at offering a "lower than Best Effort" data transfer service, with a lower priority with respect to elastic TCP and interactive traffic (e.g., VoIP, game). However, in its current specification, LEDBAT is affected by a late-comer advantage: indeed the last flow arriving at the bottleneck is more aggressive due to a wrong estimation of the base delay and finally takes over all resources. In this work, we study several solutions to the late-comer problem by means of packet level simulations and simple analysis: in the investigation process, we individuate the root cause for LEDBAT unfairness and propose effective countermeasures.
BibTeX
@inproceedings{carofiglio2010quest,
  author = {Giovanna Carofiglio and Luca Muscariello and Dario Rossi and Silvio Valenti},
  title = {{The quest for LEDBAT fairness}},
  booktitle = {GLOBECOM},
  year = {2010},
  doi = {10.1109/glocom.2010.5683559},
}
Figure