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

input-queued switchqueue-size scalingqueueing theory

Mathematics Subject Classification ID

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

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.
• Optimal heavy-traffic queue length scaling in an incompletely saturated switch
• An algorithm for improved delay-scaling in input-queued switches
• Preemptive scheduling for approximate computing on heterogeneous machines: tradeoff between weighted accuracy and makespan
• scientific article; zbMATH DE number 2088471 (Why is no real title available?)
• Bounds on delays and queue lengths in input-queued cell switches
• 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
• Fluctuation Bounds for the Max-Weight Policy with Applications to State Space Collapse
• Optimal weighted-delay scheduling in 2 2 input-queued switches

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)