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/n2). 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 n1.5(1 − ρ) −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(n3), while ours is O(n2.5 log n). 1.