Heavy-Traffic Optimal Size- and State-Aware Dispatching

Runhan Xie, Isaac Grosof, Ziv Scully

TL;DR

This paper settles a long-standing open problem in queueing theory by proving the first lower bound for mean response time in size- and state-aware dispatching systems. The authors introduce CARD (Controlled Asymmetry Reduces Delay), a novel policy that is mathematically proven to be optimal in heavy-traffic conditions, significantly outperforming traditional load-balancing heuristics.

What Problem Does This Paper Address?

In many computing and service systems, a "dispatcher" receives incoming jobs and must immediately assign them to one of several parallel queues. Each queue processes jobs in a First-Come First-Served (FCFS) order.

The authors focus on the size- and state-aware setting: the dispatcher knows exactly how long a job will take to run (size) and exactly how much work is currently pending in each queue (state). While this seems like a scenario where we should be able to find an "optimal" strategy, it has remained an open problem. Specifically:

  1. No Lower Bound: There was no known theoretical limit on how low the mean response time could go, making it impossible to prove if any existing policy was truly optimal.
  2. Suboptimal Heuristics: Common strategies like Least Work Left (LWL) or Size Interval Task Assignment (SITA) perform poorly in heavy traffic because they either balance work too much or don't adapt to the current state of the queues.

Methods

The authors tackle this using a mix of heavy-traffic analysis (studying the system as load approaches 100% capacity) and stochastic modeling.

The CARD Policy

The core contribution is the CARD policy. Its design is counter-intuitive: instead of trying to balance the queues, it intentionally creates asymmetry.

  • Job Classification: Jobs are divided into "small," "medium," and "large" based on size thresholds.
  • Server Roles: In an $n$-server system, $n-1$ servers are designated as "short" servers and one is the "long" server.
  • The Logic: Small jobs always go to short servers. Large jobs always go to the long server. Medium jobs act as a "regulator": they are sent to a short server only if its work is below a specific threshold $c$; otherwise, they go to the long server.

Theoretical Proofs

The authors use the Rate Conservation Law and Palm inversion formula to derive the first non-trivial lower bound for any size- and state-aware policy. They then prove that CARD’s performance matches this lower bound in the heavy-traffic limit, establishing its optimality.

Datasets

The paper uses synthetic simulations to validate the theory across various scenarios:

  • Job Size Distributions: Weibull distributions with mean 1 and varying "Coefficients of Variation" (cv = 1, 10, and 100) to simulate everything from predictable tasks to highly "bursty" or heavy-tailed workloads.
  • System Scale: Simulations were conducted for 2-server and 10-server configurations.
  • Benchmarks: CARD was compared against LWL (Least Work Left), SITA-E (Size Interval Task Assignment), and Dice (a high-performing state-of-the-art heuristic).

Key Insights and Ideas

  • Balance is Bad: In size-aware FCFS systems, the "natural" urge to balance work across all servers is actually detrimental. To minimize mean delay, you want to keep most servers very "empty" so small jobs can zip through, while sequestering large jobs in a single, long queue.
  • The "Medium Job" Valve: The genius of CARD lies in the medium jobs. By using them to fill gaps in the short servers, the policy prevents those servers from idling (wasting capacity) without letting them get so backed up that they delay small jobs.
  • State-Space Collapse: The authors prove a form of "state-space collapse," showing that in heavy traffic, the complex multi-dimensional state of the system effectively behaves like a simpler, predictable model.

Key Results

  • Provable Optimality: CARD is the first size- and state-aware policy proven to be heavy-traffic optimal for any number of servers.
  • Massive Delay Reduction: In simulations with high variability (cv=100) and high load ($\rho=0.98$), CARD achieved a 93% reduction in mean response time compared to LWL and a 61% reduction compared to SITA-E.
  • Competitive with Best Heuristics: CARD performs nearly identically to "Dice," which was previously the best-known heuristic, but CARD has the added benefit of a rigorous mathematical proof of optimality.

Limitations and Future Work

  • Distribution Knowledge: CARD requires knowing the job size distribution to set its thresholds ($m_-, m_+, c$). The authors suggest that future work could explore "learning" these parameters online.
  • Tail Performance: While CARD minimizes mean response time, it does so by "starving" large jobs in the long queue. This can lead to poor "tail" performance (e.g., the 99th percentile latency for very large jobs).
  • Non-Poisson Arrivals: The current proof assumes M/G arrivals (Poisson process). Extending this to more general arrival processes is a noted area for future research.

Summary updated

Abstract

Dispatching systems, where arriving jobs are immediately assigned to one of multiple queues, are ubiquitous in computer systems and service systems. A natural and practically relevant model is one in which each queue serves jobs in FCFS (First-Come First-Served) order. We consider the case where the dispatcher is size-aware, meaning it learns the size (i.e. service time) of each job as it arrives; and state-aware, meaning it always knows the amount of work (i.e. total remaining service time) at each queue. While size- and state-aware dispatching to FCFS queues has been extensively studied, little is known about optimal dispatching for the objective of minimizing mean delay. A major obstacle is that no nontrivial lower bound on mean delay is known, even in heavy traffic (i.e. the limit as load approaches capacity). This makes it difficult to prove that any given policy is optimal, or even heavy-traffic optimal. In this work, we propose the first size- and state-aware dispatching policy that provably minimizes mean delay in heavy traffic. Our policy, called CARD (Controlled Asymmetry Reduces Delay), keeps all but one of the queues short, then routes as few jobs as possible to the one long queue. We prove an upper bound on CARD's mean delay, and we prove the first nontrivial lower bound on the mean delay of any size- and state-aware dispatching policy. Both results apply to any number of servers. Our bounds match in heavy traffic, implying CARD's heavy-traffic optimality. In particular, CARD's heavy-traffic performance improves upon that of LWL (Least Work Left), SITA (Size Interval Task Assignment), and other policies from the literature whose heavy-traffic performance is known.
BibTeX
@inproceedings{xie2024heavy,
  author = {Runhan Xie and Isaac Grosof and Ziv Scully},
  title = {{Heavy-Traffic Optimal Size- and State-Aware Dispatching}},
  booktitle = {SIGMETRICS/Performance (Abstracts)},
  year = {2024},
  url = {https://openreview.net/forum?id=XnxFTmUFON},
}

Loading related content...

Figure