Input-queued switch queue size approaches optimal scaling with new scheduling policy
Approaching Optimal Scaling of Queue Size for an Input-Queued Switch
Performance
Summary
Managing queues efficiently in network switches is challenging, especially as systems grow larger and busier. The researchers studied how the total queue length grows with system size and load, aiming to confirm a long-standing prediction about its best possible growth. They created a new scheduling method that comes closer and closer to this optimal growth as they fine-tune it, providing a way to keep queues shorter even when systems are heavily loaded. Their method uses a clever multi-level batching design and might be helpful in other complex scheduling problems.
What this means in practice
- •For network schedulers: Implement scheduling policies that keep queue lengths near optimal as switches scale up and approach full load, improving network efficiency and stability.
- •For distributed systems engineers: Use recursive batching techniques to design efficient schedulers for systems with combinatorial constraints on simultaneous job processing.
A theory result. No direct application yet.
Authors
Taha Ameen, Weina Wang
Abstract
We study the scaling of the expected total queue length in an $n\times n$ input-queued switch. It has been conjectured that the optimal scaling is $O(n/(1-ρ))$, up to logarithmic factors, where $ρ$ is the system load. This conjecture has been established in the traditional heavy-traffic regime and in certain sub-regimes of the large-system regime. But it remains unresolved over a wide range of load scalings in the large-system regime. In this paper, we develop a family of scheduling policies parameterized by a positive integer $k\ge 2$. We show that under uniform traffic, our policy achieves an expected total queue length of $O\bigl({n\log\max\{n,1/(1-ρ)\}}\big/{(1-ρ)^{2^k/(2^k-1)}}\bigr)$, as long as $ρ\to 1$ in the large-system regime. As $k$ increases, the exponent $2^k/(2^k-1)$ approaches $1$, bringing our bound arbitrarily close to the conjectured scaling. The expected amortized scheduling cost of the policy is $O(n^3 k)$ per time slot. Our policy is of a batching type, with a novel recursive design that allows an arbitrary number of batching levels. This design principle may also be useful for other scheduling problems in which combinatorial constraints restrict which jobs can be served simultaneously.