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

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(sqrt(r)) of its capacity. The main results are: (i) We show that, in general, a system in a stationary regime has at least O(sqrt(r)) average queue lengths, even if the so called null-controllability [7] on a finite time interval is possible; strategies achieving this O(sqrt (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 for the arrival processes formed (at its output) by the Shadow routing. (Result (iii) in turn implies order-optimality of the Shadow routing algorithm [34].) Simulation results demonstrate good performance and robustness of our scheme.