Join-Idle-Queue system with general service times: Large-scale limit of stationary distributions

Sergey Foss, Aleksandr Stolyar

Research output: Contribution to journalConference article

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 to be routed to one of the servers immediately upon arrival. Join-Idle-Queue routing 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 equal λ/μ. In particular, this implies that the steady-state probability of an arriving customer having to wait for service vanishes.

Original languageEnglish (US)
Pages (from-to)45-47
Number of pages3
JournalPerformance Evaluation Review
Volume45
Issue number2
DOIs
StatePublished - Sep 1 2017
EventWorkshop on MAthematical Performance Modeling and Analysis, MAMA 2017, 2017 Greenmetrics Workshop and Workshop on Critical Infrastructure Network Security, CINS 2017 - Urbana-Champaign, United States
Duration: Jun 1 2017 → …

Fingerprint

Servers
Routing algorithms
Computer systems
Flow rate

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Join-Idle-Queue system with general service times : Large-scale limit of stationary distributions. / Foss, Sergey; Stolyar, Aleksandr.

In: Performance Evaluation Review, Vol. 45, No. 2, 01.09.2017, p. 45-47.

Research output: Contribution to journalConference article

@article{6270adc5a2b0471eb84791340ffe69eb,
title = "Join-Idle-Queue system with general service times: Large-scale limit of stationary distributions",
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 to be routed to one of the servers immediately upon arrival. Join-Idle-Queue routing 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 equal λ/μ. In particular, this implies that the steady-state probability of an arriving customer having to wait for service vanishes.",
author = "Sergey Foss and Aleksandr Stolyar",
year = "2017",
month = "9",
day = "1",
doi = "10.1145/3152042.3152058",
language = "English (US)",
volume = "45",
pages = "45--47",
journal = "Performance Evaluation Review",
issn = "0163-5999",
publisher = "Association for Computing Machinery (ACM)",
number = "2",

}

TY - JOUR

T1 - Join-Idle-Queue system with general service times

T2 - Large-scale limit of stationary distributions

AU - Foss, Sergey

AU - Stolyar, Aleksandr

PY - 2017/9/1

Y1 - 2017/9/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 to be routed to one of the servers immediately upon arrival. Join-Idle-Queue routing 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 equal λ/μ. In particular, this implies that the steady-state probability of an arriving customer having to wait 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 to be routed to one of the servers immediately upon arrival. Join-Idle-Queue routing 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 equal λ/μ. In particular, this implies that the steady-state probability of an arriving customer having to wait for service vanishes.

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

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

U2 - 10.1145/3152042.3152058

DO - 10.1145/3152042.3152058

M3 - Conference article

AN - SCOPUS:85041422385

VL - 45

SP - 45

EP - 47

JO - Performance Evaluation Review

JF - Performance Evaluation Review

SN - 0163-5999

IS - 2

ER -