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

Queueing Systems

Management Science and Operations

Queueing Systems 2010 Vol 66:1 p 1-51

2010

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¨CWhitt (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 O(r ¡Ì ) average queue lengths, even if the so called null-controllability (Atar et al., Ann. Appl. Probab. 16, 1764¨C1804, 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.

No