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.
Investigating Solutions
The authors investigated the root cause of this instability using fluid modeling and packet-level simulations. They evaluated four potential remedies:
- Random Pacing: Adding jitter to transmissions to diversify delay samples.
- Slow-start: Using a TCP-like aggressive start to force a buffer reset.
- Probabilistic Window Dropping: Introducing a small chance ($p$) of halving the congestion window upon receiving an ACK.
- 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.
- 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