← All problems

Optimal queue-size scaling for input-queued switches

For an n×nn\times n input-queued switch under uniform traffic with load 0<ρ<10<\rho<1, let QijQ_{ij} denote the queue length at input ii for output jj, and let Qtot=∑i,j=1nQijQ_{\mathrm{tot}}=\sum_{i,j=1}^n Q_{ij} in stationarity under a scheduling policy. The conjecture is that there exists an admissible scheduling policy for which, as n→∞n\to\infty and ρ→1\rho\to1, E[Qtot]=O~ ⁣(n1−ρ)\mathbb{E}[Q_{\mathrm{tot}}]=\widetilde{O}\!\left(\frac{n}{1-\rho}\right), where O~\widetilde{O} suppresses logarithmic factors in nn and (1−ρ)−1(1-\rho)^{-1}.

References

Progress summary

Refreshed
Open · progress reported

A new unrefereed paper gets closer to the predicted queue-size bound, but does not prove it in the remaining large-system regime.

The conjecture predicts total queue size of order n/(1−ρ)n/(1-\rho) for input-queued switches, and was documented by Shah, Tsitsiklis, and Zhong in 2011. Heavy-traffic results cover a particular order of limits, but the general large-system regime remains the target.

Known results

  • Shah, Walton, and Zhong (2014): established the conjectured scaling in the heavy-traffic limit, with ρ→1\rho\to1 before system size grows, and a 22-optimal policy.
  • A 2014 follow-up improved the bound for 1−ρ=O(1/n)1-\rho=O(1/n) to O ⁣(n1.5(1−ρ)−1log⁡11−ρ)O\!\left(n^{1.5}(1-\rho)^{-1}\log\frac{1}{1-\rho}\right), but did not resolve the general regime.

October 2026 claimed progress

On October 27, 2026, Taha Ameen and Weina Wang reported that, for uniform traffic and load tending to one, their unrefereed work obtains exponent 2k/(2k−1)2^k/(2^k-1) for every fixed k≥2k\ge2, up to logarithmic factors and with stated scheduling cost. This narrows the gap toward the conjectured exponent 11, but does not reach the conjectured O(n/(1−ρ))O(n/(1-\rho)) scaling.

Current status (as of October 2026): The heavy-traffic limit is established, while the general large-system conjecture remains open and the 2026 exponent improvement is unverified.

Sources

Solutions 0

No solutions have been posted yet.