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.
Introduction
In modern computing and service infrastructures, dispatchers play a critical role by assigning incoming tasks to parallel servers. A common configuration involves First-Come First-Served (FCFS) queues. This paper addresses systems where the dispatcher is both size-aware (knowing the service time of each job) and state-aware (knowing the remaining work in each queue).
Despite the prevalence of these systems, finding an optimal dispatching strategy to minimize mean delay has remained an open problem. The primary challenge has been the absence of a non-trivial lower bound on mean delay, even in heavy-traffic scenarios where system load approaches capacity. Without such a benchmark, it is impossible to verify if any policy—including common heuristics like Least Work Left (LWL) or Size Interval Task Assignment (SITA)—is truly optimal.
The CARD Policy: Controlled Asymmetry
The authors introduce CARD (Controlled Asymmetry Reduces Delay), a novel policy designed to minimize mean delay by intentionally creating system asymmetry. Unlike traditional load-balancing heuristics that attempt to equalize work across servers, CARD maintains a distinction between "short" and "long" queues.
In an $n$-server system, CARD designates $n-1$ servers to handle "short" queues and one server for a "long" queue. Jobs are categorized into three classes:
- Small Jobs: Always routed to short servers to ensure rapid completion.
- Large Jobs: Always routed to the long server to prevent them from blocking smaller tasks.
- Medium Jobs: Act as a regulatory mechanism. They are sent to a short server only if its current work $W_s$ is below a threshold $c$; otherwise, they are sent to the long server.
This "medium job valve" ensures that short servers remain busy without becoming congested, effectively sequestering large delays into a single queue.
Theoretical Foundations and Optimality
The researchers established the first non-trivial lower bound for mean delay in size- and state-aware dispatching using the Rate Conservation Law and Palm inversion formula. By proving that CARD's performance matches this lower bound in the heavy-traffic limit, they demonstrated its optimality for any number of servers. This result also confirms a "state-space collapse," where the complex multi-server system behaves predictably under heavy load.
Performance Results
Simulations using various job size distributions (e.g., Weibull distributions with high variability) validate the theoretical findings. CARD demonstrates significant improvements over traditional policies, particularly as the system load approaches capacity.
In high-variability scenarios ($cv=100$) at $98\%$ load, CARD reduces mean response time by approximately $93\%$ compared to LWL and $61\%$ compared to SITA-E. Furthermore, CARD performs competitively with "Dice," a high-performing state-of-the-art heuristic, while providing the rigorous mathematical guarantee of optimality that Dice lacks.
Conclusion and Future Directions
CARD represents a significant advancement in queueing theory, settling a long-standing question regarding optimal dispatching. However, some practical challenges remain. The policy currently requires prior knowledge of the job size distribution to set optimal thresholds ($m_-, m_+, c$). Future research may focus on adaptive versions of CARD that learn these parameters online. Additionally, while CARD minimizes mean delay, it does so by increasing the delay for the largest jobs; exploring policies that balance mean delay with tail performance remains an open area for investigation.
Summary updated