TY - JOUR
T1 - Systems with large flexible server pools
T2 - Instability of "natural" load balancing
AU - Stolyar, Alexander L.
AU - Yudovina, Elena
PY - 2013/10
Y1 - 2013/10
N2 - We consider general large-scale service systems with multiple customer classes and multiple server (agent) pools, mean service times depend both on the customer class and server pool. It is assumed that the allowed activities (routing choices) form a tree (in the graph with vertices being both customer classes and server pools). We study the behavior of the system under a natural (load balancing) routing/scheduling rule, Longest-Queue Freest-Server (LQFS-LB), in the many-server asymptotic regime, such that the exogenous arrival rates of the customer classes, as well as the number of agents in each pool, grow to infinity in proportion to some scaling parameter r. Equilibrium point of the system under LQBS-LB is the desired operating point, with server pool loads minimized and perfectly balanced. Our main results are as follows. (a)We show that, quite surprisingly (given the tree assumption), for certain parameter ranges, the fluid limit of the system may be unstable in the vicinity of the equilibrium point; such instability may occur if the activity graph is not "too small." (b) Using (a), we demonstrate that the sequence of stationary distributions of diffusion-scaled processes [measuring O(√r) deviations from the equilibrium point] may be nontight, and in fact may escape to infinity. (c) In one special case of interest, however, we show that the sequence of stationary distributions of diffusionscaled processes is tight, and the limit of stationary distributions is the stationary distribution of the limiting diffusion process.
AB - We consider general large-scale service systems with multiple customer classes and multiple server (agent) pools, mean service times depend both on the customer class and server pool. It is assumed that the allowed activities (routing choices) form a tree (in the graph with vertices being both customer classes and server pools). We study the behavior of the system under a natural (load balancing) routing/scheduling rule, Longest-Queue Freest-Server (LQFS-LB), in the many-server asymptotic regime, such that the exogenous arrival rates of the customer classes, as well as the number of agents in each pool, grow to infinity in proportion to some scaling parameter r. Equilibrium point of the system under LQBS-LB is the desired operating point, with server pool loads minimized and perfectly balanced. Our main results are as follows. (a)We show that, quite surprisingly (given the tree assumption), for certain parameter ranges, the fluid limit of the system may be unstable in the vicinity of the equilibrium point; such instability may occur if the activity graph is not "too small." (b) Using (a), we demonstrate that the sequence of stationary distributions of diffusion-scaled processes [measuring O(√r) deviations from the equilibrium point] may be nontight, and in fact may escape to infinity. (c) In one special case of interest, however, we show that the sequence of stationary distributions of diffusionscaled processes is tight, and the limit of stationary distributions is the stationary distribution of the limiting diffusion process.
KW - Diffusion limit
KW - Fluid limit
KW - Instability
KW - Load balancing
KW - Many server models
KW - Tightness of invariant distributions
UR - http://www.scopus.com/inward/record.url?scp=84885165778&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84885165778&partnerID=8YFLogxK
U2 - 10.1214/12-AAP895
DO - 10.1214/12-AAP895
M3 - Article
AN - SCOPUS:84885165778
SN - 1050-5164
VL - 23
SP - 2099
EP - 2138
JO - Annals of Applied Probability
JF - Annals of Applied Probability
IS - 5
ER -