Optimal queue-size scaling for input-queued switches
For an input-queued switch under uniform traffic with load , let denote the queue length at input for output , and let in stationarity under a scheduling policy. The conjecture is that there exists an admissible scheduling policy for which, as and , , where suppresses logarithmic factors in and .
References
- Approaching Optimal Scaling of Queue Size for an Input-Queued Switch — arXiv — Taha Ameen, Weina Wang
Source: arXiv
Progress summary
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 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 before system size grows, and a -optimal policy.
- A 2014 follow-up improved the bound for to , 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 for every fixed , up to logarithmic factors and with stated scheduling cost. This narrows the gap toward the conjectured exponent , but does not reach the conjectured 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.
Solutions 0
No solutions have been posted yet.