Instability of natural load balancing in large-scale flexible-server systems

Alexander L. Stolyar, Elena Yudovina

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider large-scale service systems with several customer classes and several server pools. Mean service time of a customer depends both on the customer class and the server type. The routing is restricted to a fixed set of "activities," i.e. (customer-class, server-type) pairs. We assume that the bipartite graph with vertices being customer-classes and server-types, and edges being the activities, is a tree. The system behavior under a natural load balancing routing/scheduling rule, Longest-queue freest-server (LQFS-LB), is studied in both fluid-limit and Halfin-Whitt asymptotic regimes. We show that, quite surprizingly, LQFS-LB may render the system unstable in the vicinity of the equilibrium point. Such instability cannot occur in systems with "small" number of customer classes. We prove stability in one important special case.

Original languageEnglish (US)
Title of host publication2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011
Pages361-368
Number of pages8
DOIs
StatePublished - Dec 1 2011
Externally publishedYes
Event2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011 - Monticello, IL, United States
Duration: Sep 28 2011Sep 30 2011

Publication series

Name2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011

Other

Other2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011
CountryUnited States
CityMonticello, IL
Period9/28/119/30/11

    Fingerprint

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Control and Systems Engineering

Cite this

Stolyar, A. L., & Yudovina, E. (2011). Instability of natural load balancing in large-scale flexible-server systems. In 2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011 (pp. 361-368). [6120190] (2011 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2011). https://doi.org/10.1109/Allerton.2011.6120190