Large-scale join-idle-queue system with general service times

S. Foss, A. L. Stolyar

Research output: Contribution to journalArticle

Abstract

A parallel server system with n identical servers is considered. The service time distribution has a finite mean 1 / μ, but otherwise is arbitrary. Arriving customers are routed to one of the servers immediately upon arrival. The join-idle-queue routeing algorithm is studied, under which an arriving customer is sent to an idle server, if such is available, and to a randomly uniformly chosen server, otherwise. We consider the asymptotic regime where n → and the customer input flow rate is λn. Under the condition λ / μ < 1/2, we prove that, as n → the sequence of (appropriately scaled) stationary distributions concentrates at the natural equilibrium point, with the fraction of occupied servers being constant at λ / μ. In particular, this implies that the steady-state probability of an arriving customer waiting for service vanishes.

Original languageEnglish (US)
Pages (from-to)995-1007
Number of pages13
JournalJournal of Applied Probability
Volume54
Issue number4
DOIs
StatePublished - Dec 1 2017

Fingerprint

Join
Queue
Server
Customers
Stationary Distribution
Equilibrium Point
Flow Rate
Immediately
Vanish
Imply
Arbitrary

Keywords

  • Large-scale service system
  • asymptotic optimality
  • fluid limit
  • join-idle-queue
  • load balancing
  • pull-based load distribution
  • stationary distribution

ASJC Scopus subject areas

  • Statistics and Probability
  • Mathematics(all)
  • Statistics, Probability and Uncertainty

Cite this

Large-scale join-idle-queue system with general service times. / Foss, S.; Stolyar, A. L.

In: Journal of Applied Probability, Vol. 54, No. 4, 01.12.2017, p. 995-1007.

Research output: Contribution to journalArticle

@article{0eb41c61e8ed47d89c6e601f4fc3c7bc,
title = "Large-scale join-idle-queue system with general service times",
abstract = "A parallel server system with n identical servers is considered. The service time distribution has a finite mean 1 / μ, but otherwise is arbitrary. Arriving customers are routed to one of the servers immediately upon arrival. The join-idle-queue routeing algorithm is studied, under which an arriving customer is sent to an idle server, if such is available, and to a randomly uniformly chosen server, otherwise. We consider the asymptotic regime where n → and the customer input flow rate is λn. Under the condition λ / μ < 1/2, we prove that, as n → the sequence of (appropriately scaled) stationary distributions concentrates at the natural equilibrium point, with the fraction of occupied servers being constant at λ / μ. In particular, this implies that the steady-state probability of an arriving customer waiting for service vanishes.",
keywords = "Large-scale service system, asymptotic optimality, fluid limit, join-idle-queue, load balancing, pull-based load distribution, stationary distribution",
author = "S. Foss and Stolyar, {A. L.}",
year = "2017",
month = "12",
day = "1",
doi = "10.1017/jpr.2017.49",
language = "English (US)",
volume = "54",
pages = "995--1007",
journal = "Journal of Applied Probability",
issn = "0021-9002",
publisher = "University of Sheffield",
number = "4",

}

TY - JOUR

T1 - Large-scale join-idle-queue system with general service times

AU - Foss, S.

AU - Stolyar, A. L.

PY - 2017/12/1

Y1 - 2017/12/1

N2 - A parallel server system with n identical servers is considered. The service time distribution has a finite mean 1 / μ, but otherwise is arbitrary. Arriving customers are routed to one of the servers immediately upon arrival. The join-idle-queue routeing algorithm is studied, under which an arriving customer is sent to an idle server, if such is available, and to a randomly uniformly chosen server, otherwise. We consider the asymptotic regime where n → and the customer input flow rate is λn. Under the condition λ / μ < 1/2, we prove that, as n → the sequence of (appropriately scaled) stationary distributions concentrates at the natural equilibrium point, with the fraction of occupied servers being constant at λ / μ. In particular, this implies that the steady-state probability of an arriving customer waiting for service vanishes.

AB - A parallel server system with n identical servers is considered. The service time distribution has a finite mean 1 / μ, but otherwise is arbitrary. Arriving customers are routed to one of the servers immediately upon arrival. The join-idle-queue routeing algorithm is studied, under which an arriving customer is sent to an idle server, if such is available, and to a randomly uniformly chosen server, otherwise. We consider the asymptotic regime where n → and the customer input flow rate is λn. Under the condition λ / μ < 1/2, we prove that, as n → the sequence of (appropriately scaled) stationary distributions concentrates at the natural equilibrium point, with the fraction of occupied servers being constant at λ / μ. In particular, this implies that the steady-state probability of an arriving customer waiting for service vanishes.

KW - Large-scale service system

KW - asymptotic optimality

KW - fluid limit

KW - join-idle-queue

KW - load balancing

KW - pull-based load distribution

KW - stationary distribution

UR - http://www.scopus.com/inward/record.url?scp=85041353326&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041353326&partnerID=8YFLogxK

U2 - 10.1017/jpr.2017.49

DO - 10.1017/jpr.2017.49

M3 - Article

AN - SCOPUS:85041353326

VL - 54

SP - 995

EP - 1007

JO - Journal of Applied Probability

JF - Journal of Applied Probability

SN - 0021-9002

IS - 4

ER -