On Queue-size Scaling for Input-Queued Switches

We study the optimal scaling of the expected total queue size in an n × n input-queued switch, as a function of the number of ports n and the load factor ρ, which has been conjectured to be Θ(n/(1 − ρ)) (cf. [15]). In a recent work [16], the validity of this conjecture has been established for the regime where 1 − ρ = O(1/n²). 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 − ρ)⁻¹ log (1/(1 − ρ))) when 1 − ρ = O(1/n). This is an improvement over the state of the art; for example, for ρ = 1 − 1/n the best known bound was O(n³), while ours is O(n^2.5 log n).