Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints

DOI10.1007/S11134-014-9414-XMaRDI QIDQ2018944zbMATH OpenOpenAlexFDO

Authors Yuan Zhong, Alexander L. Stolyar

Publication date 26 March 2015

Published in Queueing Systems (Search for Journal in Brave)

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

zbMATH Keywords

cloud computingqueueing networksfluid limitvirtual machineinfinite server systemgreedy random algorithmstochastic bin packing

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Stochastic network models in operations research (90B15)

Abstract: We consider a service system model primarily motivated by the problem of efficient assignment of virtual machines to physical host machines in a network cloud, so that the number of occupied hosts is minimized. There are multiple types of arriving customers, where a customer's mean service time depends on its type. There is an infinite number of servers. Multiple customers can be placed for service into one server, subject to general "packing" constraints. Service times of different customers are independent, even if served simultaneously by the same server. Each new arriving customer is placed for service immediately, either into a server already serving other customers (as long as packing constraints are not violated) or into an idle server. After a service completion, each customer leaves its server and the system. We propose an extremely simple and easily implementable customer placement algorithm, called Greedy-Random (GRAND). It places each arriving customer uniformly at random into either one of the already occupied servers (subject to packing constraints) or one of the so-called zero-servers, which are empty servers designated to be available to new arrivals. One instance of GRAND, called GRAND($aZ$), where $age0$ is a parameter, is such that the number of zero-servers at any given time $t$ is $aZ(t)$, where $Z(t)$ is the current total number of customers in the system. We prove that GRAND($aZ$) with $a>0$ is asymptotically optimal, as the customer arrival rates grow to infinity and $ao0$, in the sense of minimizing the total number of occupied servers in steady state. In addition, we study by simulations various versions of GRAND and observe the dependence of convergence speed and steady-state performance on the number of zero-servers.

Recommendations

• A service system with packing constraints: greedy randomized algorithm achieving sublinear in scale optimality gap
• An infinite server system with general packing constraints
• Large-scale heterogeneous service systems with general packing constraints
• Asymptotic properties of stochastic greedy bin-packing
• Dynamic routing in large-scale service systems with heterogeneous servers

Cites work

• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
• A Note on Insensitivity in Stochastic Networks
• An infinite server system with general packing constraints
• Blocking probabilities in large circuit-switched networks
• Dynamics of large uncontrolled loss networks
• Insensitivity in queueing systems
• Interior-point-based online stochastic bin packing
• Loss networks
• On the Sum-of-Squares algorithm for bin packing
• Shadow-routing based control of flexible multiserver pools in overload
• Stochastic bandwidth packing process: stability conditions via Lyapunov function technique

Cited in

(6)

• An infinite server system with general packing constraints
• A service system with packing constraints: greedy randomized algorithm achieving sublinear in scale optimality gap
• scientific article; zbMATH DE number 3941236 (Why is no real title available?)
• Optimality gaps in asymptotic dimensioning of many-server systems
• A theory of auto-scaling for resource reservation in cloud services
• Large-scale heterogeneous service systems with general packing constraints

This page was built for publication: Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints

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