Approaching Optimal Scaling of Queue Size for an Input-Queued Switch

Abstract

We study the scaling of the expected total queue length in an n× 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≥ 2. We show that under uniform traffic, our policy achieves an expected total queue length of O(nlogmax{n,1/(1−ρ)}/(1−ρ)^{2^k/(2^k−1)}), as long as ρ→ 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³ 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.

Scaling Limits of Density Fluctuation Fields of the Symmetric Partial Exclusion Processes Approaching the Zero Range Process
Kanta Nozawa
arXiv21 Oct 2026PreprintCC BY 4.0Full textProbabilityarXiv
Optimal Control of a Non-Stationary Inventory-Queue, with Applications to EV-Battery Swapping
Hanyu Cheng, David Yao
arXiv28 Sep 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Time-optimal vaccination in state-dependent SIR models: a single switch criterion and numerical examples outside its regime
Yeachan Park, Jiwoong Jang, Yeoneung Kim
arXiv16 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Dropout Universality: Scaling Laws and Optimal Scheduling at the Edge-of-Chaos
Lucas Fernandez Sarmiento
arXiv29 Sep 2026PreprintCC BY 4.0Full textStatistics Condensed matterarXiv
Near-Optimal Parallel M-Matrix Scaling
Chih-Hung Liu, Aaron Sidford, Ta-Wei Tu
arXiv15 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{ameen2026approaching,
  title = {{Approaching Optimal Scaling of Queue Size for an Input-Queued Switch}},
  author = {Taha Ameen and Weina Wang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.37521},
  eprint = {2610.37521},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.37521},
}

RIS

TY  - UNPB
TI  - Approaching Optimal Scaling of Queue Size for an Input-Queued Switch
AU  - Taha Ameen
AU  - Weina Wang
PY  - 2026
DA  - 2026/10/27
PB  - arXiv
DO  - 10.48550/arxiv.2610.37521
UR  - https://arxiv.org/abs/2610.37521
AB  - We study the scaling of the expected total queue length in an n× 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≥ 2. We show that under uniform traffic, our policy achieves an expected total queue length of O(nlogmax{n,1/(1−ρ)}/(1−ρ)^2^k/(2^k−1)), as long as ρ→ 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.
ER  -

Abstract

Related

Cite