Systems with large flexible server pools: Instability of "natural" load balancing

Alexander L. Stolyar, Elena Yudovina

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)2099-2138
Number of pages40
JournalAnnals of Applied Probability
Volume23
Issue number5
DOIs
StatePublished - Oct 1 2013
Externally publishedYes

Fingerprint

Load Balancing
Server
Stationary Distribution
Customers
Equilibrium Point
Routing
Infinity
Fluid Limits
Graph in graph theory
Diffusion Process
Queue
Stationary distribution
Load balancing
Proportion
Deviation
Limiting
Unstable
Scheduling
Scaling
Equilibrium point

Keywords

  • Diffusion limit
  • Fluid limit
  • Instability
  • Load balancing
  • Many server models
  • Tightness of invariant distributions

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Cite this

Systems with large flexible server pools : Instability of "natural" load balancing. / Stolyar, Alexander L.; Yudovina, Elena.

In: Annals of Applied Probability, Vol. 23, No. 5, 01.10.2013, p. 2099-2138.

Research output: Contribution to journalArticle

@article{b314e61becf542a9aac770acdbdb98a5,
title = "Systems with large flexible server pools: Instability of {"}natural{"} load balancing",
abstract = "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.",
keywords = "Diffusion limit, Fluid limit, Instability, Load balancing, Many server models, Tightness of invariant distributions",
author = "Stolyar, {Alexander L.} and Elena Yudovina",
year = "2013",
month = "10",
day = "1",
doi = "10.1214/12-AAP895",
language = "English (US)",
volume = "23",
pages = "2099--2138",
journal = "Annals of Applied Probability",
issn = "1050-5164",
publisher = "Institute of Mathematical Statistics",
number = "5",

}

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/1

Y1 - 2013/10/1

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

VL - 23

SP - 2099

EP - 2138

JO - Annals of Applied Probability

JF - Annals of Applied Probability

SN - 1050-5164

IS - 5

ER -