On queue-size scaling for input-queued switches

This is the authors' abstract. We don't add key points for this paper.

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−ρ)−1log(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.5logn).