Fully decentralized emulation of best-effort and processor sharing queues

Rade Stanojevic, Robert ShortenSigmetrics 2008 · DOI

TL;DR

This paper introduces two novel, fully decentralized algorithms (C3P and D2R2) for managing network resources in large-scale cloud-based services. These algorithms aim to provide predictable performance and efficient resource allocation by emulating centralized queueing behaviors (best-effort and processor sharing) without requiring global coordination, thus reducing communication overhead and improving fault tolerance.

What Problem Does This Paper Address?

Managing resources in massive, distributed cloud-based services (like those offered by Google or Amazon) is a significant challenge. These services rely on thousands of servers worldwide, making centralized control impractical. A key problem is "Distributed Rate Limiting" (DRL), which aims to control the aggregate bandwidth used by a service. Existing DRL approaches are often heuristic, making their behavior unpredictable and analytically intractable. The core challenge is to achieve fairness – ensuring that individual flows receive a consistent service level, as if they were managed by a single, centralized rate limiter, all while operating in a decentralized manner. This is crucial for predictable performance, fair pricing, and robust service provisioning.

Methods

The paper proposes two new DRL algorithms:

  • Cloud Control with Constant Probabilities (C3P): This algorithm tackles the best-effort DRL problem. It works by having local limiters adjust their capacities based on the difference in loss rates with their immediate neighbors. The core idea is to equalize loss rates across all limiters, which, in best-effort environments, leads to fair bandwidth allocation. The algorithm's dynamics are modeled as a nonlinear system, and the paper provides a rigorous mathematical framework to prove its global stability and convergence to an equilibrium where all loss rates are equal.
  • Distributed Deficit Round Robin (D2R2): This algorithm addresses the more complex processor sharing DRL problem. It aims to emulate a centralized processor sharing queue in a distributed fashion. D2R2 uses a Deficit Round Robin (DRR) scheduler locally and employs a consensus-like mechanism to equalize an "augmenting fair-share" value across neighboring limiters. A key innovation is the introduction of a parameter 'a' that allows the algorithm to converge to a state that is provably close (within O(1)) to the optimal processor sharing allocation, especially in low-demand scenarios.

Both algorithms are designed to be fully decentralized, meaning each limiter only needs information from its direct neighbors, significantly reducing communication overhead compared to previous methods.

Datasets

Not discussed in the paper. The evaluation uses simulations of TCP traffic and on-off sources.

Key Insights and Ideas

  • Decentralization for Scalability: The paper demonstrates that complex network control problems like rate limiting can be effectively managed in a decentralized manner, which is essential for the scalability of modern cloud services.
  • Mathematical Rigor for Heuristics: By framing DRL as a mathematical problem and developing analytical proofs for stability and convergence, the paper moves beyond heuristic approaches, offering predictable and reliable algorithms.
  • Loss Rate as a Fairness Metric: For best-effort traffic, equalizing loss rates across distributed limiters is shown to be a direct path to achieving fairness.
  • Processor Sharing Emulation is Harder: The processor sharing problem is more challenging, and D2R2's O(1) approximation highlights the inherent difficulties in perfectly emulating complex scheduling policies in a distributed, asynchronous environment.
  • Minimizing Drops in TCP: A surprising finding is that C3P, by equalizing loss rates, also minimizes the total number of packet drops in TCP environments, which is a desirable property for overall network efficiency.

Key Results

  • C3P Convergence: The paper proves that C3P converges to an equilibrium where all local limiters have equal loss rates, provided the update parameter 'η' is within a specific stable range. This ensures fair bandwidth allocation for best-effort traffic.
  • D2R2 Convergence: D2R2 is shown to converge to a stable state where local "fair-share" values are equalized. Crucially, the resulting bandwidth allocation is proven to be at most O(1) away from the optimal processor sharing allocation.
  • Empirical Validation: Simulations using ns2 confirm the analytical results. C3P and D2R2 demonstrate accurate aggregate rate control and better fairness (higher Jain's index) compared to existing methods like GRD and FPS.
  • Robustness: Simulations show that C3P and D2R2 are robust to dynamic traffic changes and can adapt to varying traffic mixes.
  • Efficiency: The algorithms exhibit low communication overhead and are computationally light, making them practical for deployment.

Limitations and Future Work

  • D2R2 Exact Convergence: While D2R2 provides an O(1) approximation for processor sharing, the paper notes that achieving exact convergence to the global optimum in all demand scenarios remains an open challenge.
  • Asynchronous Updates and Delays: The current analysis assumes synchronous updates. While the paper suggests that asynchronous updates are possible, further work is needed to fully characterize their impact. Communication delays are also acknowledged as a potential issue that requires more investigation.
  • Node Failures: The paper briefly suggests a mechanism for handling node failures by having neighbors inherit capacity, but a more in-depth analysis of its effectiveness and impact on convergence would be beneficial.
  • General Traffic Mixes for C3P: While the stability of C3P is proven for general differentiable, convex functions relating capacity and loss rate, the specific analysis of minimizing drops is tied to TCP's AIMD behavior. Extending this to other traffic types could be valuable.

Summary updated

BibTeX
@inproceedings{stanojevic2008fully,
  author = {Rade Stanojevic and Robert Shorten},
  title = {{Fully decentralized emulation of best-effort and processor sharing queues}},
  booktitle = {Sigmetrics},
  year = {2008},
  doi = {10.1145/1375457.1375501},
}
Figure