Optimal queue-size scaling in switched networks

Abstract

We consider a switched (queuing) network in which there are constraints on which queues may be served simultaneously; such networks have been used to effectively model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time, based on the current state or past history of the system. In the main result of this paper, we provide a new class of online scheduling policies that achieve optimal queue-size scaling for a class of switched networks including input-queued switches. In particular, it establishes the validity of a conjecture (documented in Shah, Tsitsiklis and Zhong [Queueing Syst. 68 (2011) 375-384]) about optimal queue-size scaling for input-queued switches.

Published in at http://dx.doi.org/10.1214/13-AAP970 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (6)

• State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy
• Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse
• Asymptotic optimality of maximum pressure policies in stochastic processing networks
• Proportional fairness and its relationship with multi-class queueing networks
• Qualitative properties of $\alpha$-fair policies in bandwidth-sharing networks
• Correction. Brownian models of open processing networks: canonical representation of workload

Cited by in corpus (7)

• Queue Length Behavior in a Switch under the MaxWeight Algorithm
• Low-Complexity Switch Scheduling Algorithms: Delay Optimality in Heavy Traffic
• Improved queue-size scaling for input-queued switches via graph factorization
• Centralized Congestion Control and Scheduling in a Datacenter
• Optimal Scheduling Control in Fluid Models of General $n\times n$ Input-Queued Switches
• Store-Forward and its implications for Proportional Scheduling
• Stability of MaxWeight-(α,g)