Skip to main content

Please enter a keyword and click the arrow to search the site

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


Queueing Systems


Management Science and Operations

Publication Year



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.

Available on ECCH


Select up to 4 programmes to compare

Select one more to compare
subscribe_image_desktop 5949B9BFE33243D782D1C7A17E3345D0

Sign up to receive our latest news and business thinking direct to your inbox