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

DOI10.1017/APR.2020.31zbMATH Open1473.60147arXiv1903.00398OpenAlexW3088506439MaRDI QIDQ5005035FDOQ5005035

Authors: Jiaming Xu, Yuan Zhong 

Publication date: 4 August 2021

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

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.

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

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

zbMATH Keywords

graph factorizationinput-queued switchqueue-size scaling

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• 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

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)