Control of systems with flexible multi-server pools: A shadow routing approach

Alexander L. Stolyar, Tolga Tezcan

Research output: Contribution to journalArticle

Abstract

A general model with multiple input flows (classes) and several flexible multi-server pools is considered. We propose a robust, generic scheme for routing new arrivals, which optimally balances server pools' loads, without the knowledge of the flow input rates and without solving any optimization problem. The scheme is based on Shadow routing in a virtual queueing system. We study the behavior of our scheme in the Halfin-Whitt (or, QED) asymptotic regime, when server pool sizes and the input rates are scaled up simultaneously by a factor r growing to infinity, while keeping the system load within O(√r) of its capacity. The main results are as follows. (i) We show that, in general, a system in a stationary regime has at least OO(√r) average queue lengths, even if the so called null-controllability (Atar et al., Ann. Appl. Probab. 16, 1764-1804, 2006) on a finite time interval is possible; strategies achieving this O(√r) growth rate we call order-optimal. (ii) We show that some natural algorithms, such as MaxWeight, that guarantee stability, are not order-optimal. (iii) Under the complete resource pooling condition, we prove the diffusion limit of the arrival processes into server pools, under the Shadow routing. (We conjecture that result (iii) leads to order-optimality of the Shadow routing algorithm; a formal proof of this fact is an important subject of future work.) Simulation results demonstrate good performance and robustness of our scheme.

Original languageEnglish (US)
Pages (from-to)1-51
Number of pages51
JournalQueueing Systems
Volume66
Issue number1
DOIs
StatePublished - Jul 15 2010
Externally publishedYes

Keywords

  • Diffusion limit
  • Halfin-Whitt regime
  • Large flexible server pools
  • Many server asymptotics
  • Order-optimality
  • Queueing networks
  • Routing and scheduling
  • Shadow routing

ASJC Scopus subject areas

  • Statistics and Probability
  • Computer Science Applications
  • Management Science and Operations Research
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Control of systems with flexible multi-server pools: A shadow routing approach'. Together they form a unique fingerprint.

  • Cite this