Optimal scaling of average queue sizes in an input-queued switch: an open problem

Year
2011
Type(s)
Author(s)
D. Shah, J. N. Tsitsiklis, Y. Zhong
Source
Queueing Systems, Volume 68, No. 3-4, pp. 375-384, 2011
Url
https://link.springer.com/content/pdf/10.1007%2Fs11134-011-9234-1.pdf

We review some known results and state a few versions of an open problem related to the scaling of the total queue size (in steady state) in an n×n input-queued switch, as a function of the port number n and the load factor ρ. Loosely speaking, the question is whether the total number of packets in queue, under either the maximum weight policy or under an optimal policy, scales (ignoring any logarithmic factors) as O(n/(1−ρ)).