Large-scale heterogeneous service systems with general packing constraints

DOI10.1017/APR.2016.79zbMATH Open1426.90060arXiv1508.07512OpenAlexW2963819536MaRDI QIDQ5233159FDOQ5233159

Authors: Alexander L. Stolyar 

Publication date: 16 September 2019

Published in: Advances in Applied Probability (Search for Journal in Brave)

Abstract: A service system with multiple types of customers, arriving according to Poisson processes, is considered. The system is heterogeneous in that the servers also can 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 infinity. We consider two variants of the model. For the {em infinite-server} model, we prove asymptotic optimality of the {em 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 in [15] for the homogeneous systems, with all servers of same type.) We then introduce a natural extension of GRAND algorithm for {em 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.

Full work available at URL: https://arxiv.org/abs/1508.07512

Recommendations

• A service system with packing constraints: greedy randomized algorithm achieving sublinear in scale optimality gap
• Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints
• An infinite server system with general packing constraints
• Dynamic routing in large-scale service systems with heterogeneous servers
• Routing and staffing in large-scale service systems: the case of homogeneous impatient customers and heterogeneous servers

zbMATH Keywords

cloud computingblockingqueueing networkfluid limitlossstochastic bin packinggreedy random (GRAND) algorithmheterogeneous service systempacking constraint

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Stochastic network models in operations research (90B15)

Cites Work

• Queueing system with selection of the shortest of two queues: An asymptotic approach
• A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
• Asymptotic independence of queues under randomized load balancing
• Decay of tails at equilibrium for FIFO join the shortest queue networks
• On the Sum-of-Squares algorithm for bin packing
• Pull-based load distribution in large-scale heterogeneous service systems
• An infinite server system with general packing constraints
• Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints
• Interior-point-based online stochastic bin packing

Cited In (9)

• A restless bandit model for resource allocation, competition, and reservation
• Large-scale join-idle-queue system with general service times
• A theory of auto-scaling for resource reservation in cloud services
• A service system with packing constraints: greedy randomized algorithm achieving sublinear in scale optimality gap
• An infinite server system with general packing constraints
• Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints
• Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers
• Pull-based load distribution in large-scale heterogeneous service systems
• Responding to Unexpected Overloads in Large-Scale Service Systems

This page was built for publication: Large-scale heterogeneous service systems with general packing constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233159)