Improved queue-size scaling for input-queued switches via graph factorization

Abstract

This paper studies the scaling of the expected total queue size in an $n\times n$ input-queued switch, as a function of both the load $\ddot{I}$ and the system scale $n$. We provide a new class of scheduling policies under which the expected total queue size scales as $O\left(n(1-\ddot{I}{)}^{-4/3}\log \left(\max \{\frac{1}{1-\ddot{I}},n\}\right)\right)$, over all $n$ and $\ddot{I}<1$, when the arrival rates are uniform. This improves over the previously best-known scalings in two regimes: $O\left(n^{1.5}(1-\ddot{I}{)}^{-1}\log \frac{1}{1-\ddot{I}}\right)$ when $\hat{I}\text{c◯}(n^{-1.5})\le 1-\ddot{I}\le O(n^{-1})$ and $O\left(\frac{n\log n}{(1-\ddot{I}{)}^2}\right)$ when $1-\ddot{I}\ge \hat{I}\text{c◯}(n^{-1})$. A key ingredient in our method is a tight characterization of the largest $k$-factor of a random bipartite multigraph, which may be of independent interest.

42 pages, 4 figures