SCIENCE@home

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

Jiaming Xu,Y. Zhong

Published 2019 in Advances in Applied Probability

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 ρ and the system scale n. We provide a new class of scheduling policies under which the expected total queue size scales as Ołeft( n(1-ρ)^-4/3 łog łeft(\max\\frac1 1-ρ, n\ \right)\right)$, over all n and ρ<1$, when the arrival rates are uniform. This improves over the previously best-known scalings in two regimes: Ołeft(n^1.5 (1-ρ)^-1 łog \frac1 1-ρ \right)$ when Ømega(n^-1.5 ) łe 1-ρ łe O(n^-1 )$ and $Ołeft(\fracnłog n (1-ρ)^2 \right)$ when $1-ρ \geq Ømega(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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-32 of 32 references · Page 1 of 1

CITED BY