On Queue-Size Scaling for Input-Queued Switches

DOI10.1214/14-SSY151MaRDI QIDQ2956539zbMATH OpenFDO

Authors Devavrat Shah, Yuan Zhong, John N. Tsitsiklis

Publication date 18 January 2017

Full work available at URL https://arxiv.org/abs/1405.4764, https://projecteuclid.org/euclid.ssy/1479287404

zbMATH Keywords

queueing theoryinput-queued switchqueue-size scaling

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Applications of Markov renewal processes (reliability, queueing networks, etc.) (60K20) Network protocols (68M12)

Abstract: We study the optimal scaling of the expected total queue size in an $nimesn$ input-queued switch, as a function of the number of ports $n$ and the load factor $ho$, which has been conjectured to be $Theta(n/(1-ho))$. In a recent work, the validity of this conjecture has been established for the regime where $1-ho=O(1/n^2)$. In this paper, we make further progress in the direction of this conjecture. We provide a new class of scheduling policies under which the expected total queue size scales as $O(n^{1.5}(1-ho{)}^{-1}log(1/(1-ho)))$ when $1-ho=O(1/n)$. This is an improvement over the state of the art; for example, for $ho=1-1/n$ the best known bound was $O(n^3)$, while ours is $O(n^{2.5}logn)$.

Recommendations

• Optimal scaling of average queue sizes in an input-queued switch: an open problem
• Optimal queue-size scaling in switched networks
• Improved queue-size scaling for input-queued switches via graph factorization
• An algorithm for improved delay-scaling in input-queued switches
• Heavy traffic queue length scaling in switches with reconfiguration delay
• Optimal heavy-traffic queue length scaling in an incompletely saturated switch
• On the speedup required for combined input- and output-queued switching
• Scheduling of an input-queued switch to achieve maximal throughput
• On queuing lengths in on-line switching

Cited in

(11)

• The limits of input-queued switch performance with future packet arrival information.
• Preemptive scheduling for approximate computing on heterogeneous machines: tradeoff between weighted accuracy and makespan
• Bounds on delays and queue lengths in input-queued cell switches
• An algorithm for improved delay-scaling in input-queued switches
• Fluctuation Bounds for the Max-Weight Policy with Applications to State Space Collapse
• Optimal heavy-traffic queue length scaling in an incompletely saturated switch
• scientific article; zbMATH DE number 2088471 (Why is no real title available?)
• Optimal queue-size scaling in switched networks
• Improved queue-size scaling for input-queued switches via graph factorization
• Optimal weighted-delay scheduling in 2 2 input-queued switches
• Optimal scaling of average queue sizes in an input-queued switch: an open problem

This page was built for publication: On Queue-Size Scaling for Input-Queued Switches

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