Large-scale heterogeneous service systems with general packing constraints

Research output: Contribution to journalArticle

Abstract

A service system with multiple types of customers, arriving according to Poisson processes, is considered. The system is heterogeneous in that the servers can also be of multiple types. Each customer has an independent, exponentially distributed service time, with the mean determined by its type. Multiple customers (possibly of different types) can be placed for service into one server, subject to 'packing' constraints, which depend on the server type. Service times of different customers are independent, even if served simultaneously by the same server. The large-scale asymptotic regime is considered such that the customer arrival rates grow to ∞. We consider two variants of the model. For the infinite-server model, we prove asymptotic optimality of the greedy random (GRAND) algorithm in the sense of minimizing the weighted (by type) number of occupied servers in steady state. (This version of GRAND generalizes that introduced by Stolyar and Zhong (2015) for homogeneous systems, with all servers of the same type.) We then introduce a natural extension of the GRAND algorithm for finite-server systems with blocking. Assuming subcritical system load, we prove existence, uniqueness, and local stability of the large-scale system equilibrium point such that no blocking occurs. This result strongly suggests a conjecture that the steady-state blocking probability under the algorithm vanishes in the large-scale limit.

Original languageEnglish (US)
Pages (from-to)61-83
Number of pages23
JournalAdvances in Applied Probability
Volume49
Issue number1
DOIs
StatePublished - Mar 1 2017

Fingerprint

Packing
Servers
Server
Customers
Asymptotic Optimality
Blocking Probability
Blocking probability
Local Stability
Natural Extension
Large-scale Systems
Poisson process
Equilibrium Point
Large scale systems
Vanish
Existence and Uniqueness
Generalise
Model

Keywords

  • Queueing network
  • blocking
  • cloud computing
  • fluid limit
  • greedy random (GRAND) algorithm
  • heterogeneous service system
  • loss
  • packing constraint
  • stochastic bin packing

ASJC Scopus subject areas

  • Statistics and Probability
  • Applied Mathematics

Cite this

Large-scale heterogeneous service systems with general packing constraints. / Stolyar, A. L.

In: Advances in Applied Probability, Vol. 49, No. 1, 01.03.2017, p. 61-83.

Research output: Contribution to journalArticle

@article{04285bb9d07b49c3a54ca5a74bdadd5f,
title = "Large-scale heterogeneous service systems with general packing constraints",
abstract = "A service system with multiple types of customers, arriving according to Poisson processes, is considered. The system is heterogeneous in that the servers can also be of multiple types. Each customer has an independent, exponentially distributed service time, with the mean determined by its type. Multiple customers (possibly of different types) can be placed for service into one server, subject to 'packing' constraints, which depend on the server type. Service times of different customers are independent, even if served simultaneously by the same server. The large-scale asymptotic regime is considered such that the customer arrival rates grow to ∞. We consider two variants of the model. For the infinite-server model, we prove asymptotic optimality of the greedy random (GRAND) algorithm in the sense of minimizing the weighted (by type) number of occupied servers in steady state. (This version of GRAND generalizes that introduced by Stolyar and Zhong (2015) for homogeneous systems, with all servers of the same type.) We then introduce a natural extension of the GRAND algorithm for finite-server systems with blocking. Assuming subcritical system load, we prove existence, uniqueness, and local stability of the large-scale system equilibrium point such that no blocking occurs. This result strongly suggests a conjecture that the steady-state blocking probability under the algorithm vanishes in the large-scale limit.",
keywords = "Queueing network, blocking, cloud computing, fluid limit, greedy random (GRAND) algorithm, heterogeneous service system, loss, packing constraint, stochastic bin packing",
author = "Stolyar, {A. L.}",
year = "2017",
month = "3",
day = "1",
doi = "10.1017/apr.2016.79",
language = "English (US)",
volume = "49",
pages = "61--83",
journal = "Advances in Applied Probability",
issn = "0001-8678",
publisher = "University of Sheffield",
number = "1",

}

TY - JOUR

T1 - Large-scale heterogeneous service systems with general packing constraints

AU - Stolyar, A. L.

PY - 2017/3/1

Y1 - 2017/3/1

N2 - A service system with multiple types of customers, arriving according to Poisson processes, is considered. The system is heterogeneous in that the servers can also be of multiple types. Each customer has an independent, exponentially distributed service time, with the mean determined by its type. Multiple customers (possibly of different types) can be placed for service into one server, subject to 'packing' constraints, which depend on the server type. Service times of different customers are independent, even if served simultaneously by the same server. The large-scale asymptotic regime is considered such that the customer arrival rates grow to ∞. We consider two variants of the model. For the infinite-server model, we prove asymptotic optimality of the greedy random (GRAND) algorithm in the sense of minimizing the weighted (by type) number of occupied servers in steady state. (This version of GRAND generalizes that introduced by Stolyar and Zhong (2015) for homogeneous systems, with all servers of the same type.) We then introduce a natural extension of the GRAND algorithm for finite-server systems with blocking. Assuming subcritical system load, we prove existence, uniqueness, and local stability of the large-scale system equilibrium point such that no blocking occurs. This result strongly suggests a conjecture that the steady-state blocking probability under the algorithm vanishes in the large-scale limit.

AB - A service system with multiple types of customers, arriving according to Poisson processes, is considered. The system is heterogeneous in that the servers can also be of multiple types. Each customer has an independent, exponentially distributed service time, with the mean determined by its type. Multiple customers (possibly of different types) can be placed for service into one server, subject to 'packing' constraints, which depend on the server type. Service times of different customers are independent, even if served simultaneously by the same server. The large-scale asymptotic regime is considered such that the customer arrival rates grow to ∞. We consider two variants of the model. For the infinite-server model, we prove asymptotic optimality of the greedy random (GRAND) algorithm in the sense of minimizing the weighted (by type) number of occupied servers in steady state. (This version of GRAND generalizes that introduced by Stolyar and Zhong (2015) for homogeneous systems, with all servers of the same type.) We then introduce a natural extension of the GRAND algorithm for finite-server systems with blocking. Assuming subcritical system load, we prove existence, uniqueness, and local stability of the large-scale system equilibrium point such that no blocking occurs. This result strongly suggests a conjecture that the steady-state blocking probability under the algorithm vanishes in the large-scale limit.

KW - Queueing network

KW - blocking

KW - cloud computing

KW - fluid limit

KW - greedy random (GRAND) algorithm

KW - heterogeneous service system

KW - loss

KW - packing constraint

KW - stochastic bin packing

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

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

U2 - 10.1017/apr.2016.79

DO - 10.1017/apr.2016.79

M3 - Article

AN - SCOPUS:85015961617

VL - 49

SP - 61

EP - 83

JO - Advances in Applied Probability

JF - Advances in Applied Probability

SN - 0001-8678

IS - 1

ER -