Improved queue-size scaling for input-queued switches via graph factorization

2019/03/01 by Xu, Jiaming, Zhong, Yuan
#FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI)

paper · doi:10.48550/arxiv.1903.00398

Abstract

This paper studies the scaling of the expected total queue size in an n× 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( n(1-ρ)^-4/3 log (max\(1)/(1-ρ), n\)), over all n and ρ<1, when the arrival rates are uniform. This improves over the previously best-known scalings in two regimes: O(n^1.5(1-ρ)^-1 log (1)/(1-ρ)) when Ω(n^-1.5) ≤ 1-ρ≤ O(n^-1) and O((nlog n)/((1-ρ)²)) when 1-ρ≥ Ω(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.

Related

• On Queue-Size Scaling for Input-Queued Switches
• Optimal Heavy-Traffic Queue Length Scaling in an Incompletely Saturated Switch
• Queue Length Behavior in a Switch under the MaxWeight Algorithm
• Logarithmic Heavy Traffic Error Bounds in Generalized Switch and Load Balancing Systems
• A Delay Analysis of Maximal Matching Switching with Speedup