The Quest for LEDBAT Fairness

Giovanna Carofiglio, Luca Muscariello, Dario Rossi, Silvio Valenti

TL;DR

LEDBAT, the protocol powering BitTorrent’s "nice" background transfers, suffers from a "late-comer advantage" where new flows can accidentally starve existing ones. This paper identifies the protocol's additive decrease mechanism as the root cause of this unfairness and proposes two effective fixes—probabilistic window drops and multiplicative decrease—to ensure all flows get their fair share of spare bandwidth.

What Problem Does This Paper Address?

LEDBAT (Low Extra Delay Background Transfer) was designed to be a "Lower than Best Effort" (LBE) protocol. Its goal is to soak up unused bandwidth for background tasks (like file sharing) without interfering with high-priority traffic like VoIP, gaming, or web browsing. It does this by monitoring queuing delay: if the delay rises above a certain target, LEDBAT slows down.

However, the protocol has a "late-comer" flaw. To calculate queuing delay, a flow must first know the "base delay" (the time a packet takes when the network is empty). If a new flow starts while an existing LEDBAT flow is already occupying the link, the newcomer mistakes the existing queue for the empty state. Consequently, the newcomer sets an artificially high delay target, becomes more aggressive, and eventually pushes the original flow into total starvation.

Methods

The authors investigate the root cause of this instability using both mathematical fluid modeling and packet-level simulations. They evaluate four potential solutions:

  1. Random Pacing: Adding jitter to packet transmissions to help flows "see" different delay samples.
  2. Slow-start: Using a TCP-like aggressive start to intentionally fill the buffer and force a "reset" of everyone's delay measurements.
  3. Probabilistic Window Dropping: Introducing a small probability ($p$) that a sender will halve its congestion window upon receiving an ACK, regardless of current delay.
  4. Multiplicative Decrease: Replacing LEDBAT’s standard linear (additive) decrease with a multiplicative one (reducing the window by a factor $\beta$) whenever the delay target is exceeded.

Datasets

The paper does not use real-world traffic traces or external datasets. Instead, it relies on controlled packet-level simulations (likely using a tool like ns-2). These simulations model a bottleneck link with specific parameters:

  • Target Delay ($\tau$): 25 ms.
  • Buffer Size: 60 packets.
  • Flow Scenarios: Two-flow and multi-flow (up to 10 flows) scenarios with staggered start times to trigger the late-comer effect.

Key Insights and Ideas

  • The Additive Decrease Trap: The "aha moment" is the realization that the problem isn't just a measurement error; it's the math of the window update. LEDBAT’s original linear decrease is too "gentle" to ever fully empty the queue. This prevents late-comers from ever seeing the true base delay.
  • Randomness vs. Structure: While random pacing (jitter) failed to fix the issue, random window drops worked. By de-correlating the decisions of different flows, random drops break the "persistent unfair state" that the protocol otherwise gets stuck in.
  • The Efficiency-Fairness Tradeoff: There is no free lunch. Solutions that maximize fairness (like aggressive multiplicative decrease) tend to slightly reduce overall link utilization (efficiency), and vice versa.

Key Results

  • Random Pacing: Found to be ineffective. It slightly slowed the "ramp-up" of the late-comer but didn't prevent starvation.
  • Slow-start: Provided a partial solution but was deemed too aggressive for an LBE protocol, as it could cause packet loss for the very interactive traffic LEDBAT is supposed to protect.
  • Probabilistic Drops: Highly effective. A drop probability $p$ between $10^{-4}$ and $10^{-3}$ allowed for a fair share of resources while maintaining high link efficiency.
  • Multiplicative Decrease: This was the most robust solution for fairness. By setting the decrease factor $\beta$ such that $1-\beta$ is small (e.g., 0.05), the system converges to a fair state regardless of how many flows are competing.

Limitations and Future Work

The authors acknowledge that their study focuses primarily on intra-protocol fairness (LEDBAT vs. LEDBAT). While they touch upon the impact on other traffic (like TCP), a more exhaustive study of how these modifications affect LEDBAT's "lower than best effort" priority relative to standard TCP is needed.

Future work involves refining the design of an Additive-Increase/Multiplicative-Decrease (AIMD) controller specifically for LEDBAT and exploring the optimal choice of the $\beta$ parameter across a wider variety of network topologies and delay targets.

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},
}

Loading related content...

Figure