On Queue-Size Scaling for Input-Queued Switches

Abstract

We study the optimal scaling of the expected total queue size in an $n\times n$ input-queued switch, as a function of the number of ports $n$ and the load factor $\rho$, which has been conjectured to be $\Theta (n/(1-\rho ))$. In a recent work, the validity of this conjecture has been established for the regime where $1-\rho =O(1/n^2)$. In this paper, we make further progress in the direction of this conjecture. We provide a new class of scheduling policies under which the expected total queue size scales as $O(n^{1.5}(1-\rho {)}^{-1}\log (1/(1-\rho )))$ when $1-\rho =O(1/n)$. This is an improvement over the state of the art; for example, for $\rho =1-1/n$ the best known bound was $O(n^3)$, while ours is $O(n^{2.5}\log n)$.

21 pages, 1 figure