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

DOI10.1017/APR.2020.31MaRDI QIDQ5005035zbMATH OpenOpenAlexFDO

Authors Jiaming Xu, Yuan Zhong

Publication date 4 August 2021

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.00398

zbMATH Keywords

graph factorizationinput-queued switchqueue-size scaling

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: This paper studies the scaling of the expected total queue size in an $nimesn$ input-queued switch, as a function of both the load $ho$ and the system scale $n$. We provide a new class of scheduling policies under which the expected total queue size scales as $Oleft(n(1-ho{)}^{-4/3}logleft(maxfrac11-ho,night)ight)$, over all $n$ and $ho<1$, when the arrival rates are uniform. This improves over the previously best-known scalings in two regimes: $Oleft(n^{1.5}(1-ho{)}^{-1}logfrac11-hoight)$ when $Omega(n^{-1.5})le1-holeO(n^{-1})$ and $Oleft(fracnlogn(1-ho{)}^{2}ight)$ when $1-hogeqOmega(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.

Recommendations

• On Queue-Size Scaling for Input-Queued Switches
• Optimal scaling of average queue sizes in an input-queued switch: an open problem
• Optimal queue-size scaling in switched networks
• Optimal heavy-traffic queue length scaling in an incompletely saturated switch
• Scheduling of an input-queued switch to achieve maximal throughput

Cites work

• A theorem on flows in networks
• Brownian models of open processing networks: Canonical representation of workload.
• Combinatorial Properties of Matrices of Zeros and Ones
• Communication networks. An optimization, control and stochastic networks perspective
• Complex graphs and networks
• Factors and factorizations of graphs. Proof techniques in factor theory
• Fluid model for a network operating under a fair bandwidth-sharing policy.
• Graph factors and factorization: 1985--2003: a survey
• Heavy traffic queue length behavior in a switch under the MaxWeight algorithm
• Maximal Flow Through a Network
• Maximum Pressure Policies in Stochastic Processing Networks
• MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic
• On factors in random graphs
• On Queue-Size Scaling for Input-Queued Switches
• Optimal queue-size scaling in switched networks
• Optimal scaling of average queue sizes in an input-queued switch: an open problem
• Probabilistic Analysis of the Capacitated Transportation Problem
• Regular spanning subgraphs of bipartite graphs of high minimum degree
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks

Cited in

(4)

• An algorithm for improved delay-scaling in input-queued switches
• On Queue-Size Scaling for Input-Queued Switches
• Optimal scaling of average queue sizes in an input-queued switch: an open problem
• Optimal queue-size scaling in switched networks

This page was built for publication: Improved queue-size scaling for input-queued switches via graph factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5005035)