Improved Queue-Size Scaling for Input-Queued Switches via Graph Factorization

摘要

This paper studies the scaling of the expected total queue size in an n X n input-queued switch, as a function of both the load p and the system scale n. We provide a new class of scheduling policies under which the expected total queue size scales as O (n(l - P)~(-4/3) log (max{~1/_(1-P)})), over all n and p < 1, when the arrival rates are uniform. This improves over the previously best-known scalings in two regimes: O (n~(1.5)(1 - p)~(-1) log ~1/_(1-P) when Ω(n~(-1.5)) ≤ 1 - p ≤ O(n~(-1)) and O (~(n log n)/_((1-p)~2)) when 1 - p ≥ Ω(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.