An infinite server system with general packing constraints

DOI10.1287/OPRE.2013.1184zbMATH Open1294.90020arXiv1205.4271OpenAlexW2039060503MaRDI QIDQ5166276FDOQ5166276

Authors: Alexander L. Stolyar 

Publication date: 26 June 2014

Published in: Operations Research (Search for Journal in Brave)

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 input flows of different type customers, with a customer mean service time depending on its type. There is infinite number of servers. A server packing {em configuration} is the vector $k=k_i$, where $k_i$ is the number of type $i$ customers the server "contains". Packing constraints must be observed, namely there is a fixed finite set of configurations $k$ that are allowed. Service times of different customers are independent; after a service completion, each customer leaves its server and the system. Each new arriving customer is placed for service immediately; it can be placed into a server already serving other customers (as long as packing constraints are not violated), or into an idle server. We consider a simple parsimonious real-time algorithm, called {em Greedy}, which attempts to minimize the increment of the objective function $su{m}_k{X}_k^{1+alpha}$, $alpha>0$, caused by each new assignment; here $X_k$ is the number of servers in configuration $k$. (When $alpha$ is small, $su{m}_k{X}_k^{1+alpha}$ approximates the total number $su{m}_k{X}_k$ of occupied servers.) Our main results show that certain versions of the Greedy algorithm are {em asymptotically optimal}, in the sense of minimizing $su{m}_k{X}_k^{1+alpha}$ in stationary regime, as the input flow rates grow to infinity. We also show that in the special case when the set of allowed configurations is determined by {em vector-packing} constraints, Greedy algorithm can work with {em aggregate configurations} as opposed to exact configurations $k$, thus reducing computational complexity while preserving the asymptotic optimality.

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

Recommendations

• Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints
• A service system with packing constraints: greedy randomized algorithm achieving sublinear in scale optimality gap
• Large-scale heterogeneous service systems with general packing constraints
• Delay-minimizing capacity allocation in an infinite server-queueing system
• Bandwidth packing

zbMATH Keywords

cloud computingqueueing networksvector packingfluid limitvirtual machineinfinite server systemstochastic bin packing

Mathematics Subject Classification ID

Queues and service in operations research (90B22)

Cited In (10)

• A Service System with Packing Constraints: Greedy Randomized Algorithm Achieving Sublinear in Scale Optimality Gap
• Fcfs infinite bipartite matching of servers and customers
• Scaling limits for infinite-server systems in a random environment
• Approximation of initial loading of infinite-server systems
• A Restless Bandit Model for Resource Allocation, Competition, and Reservation
• Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints
• Allocation schemes of resources with downgrading
• A Theory of Auto-Scaling for Resource Reservation in Cloud Services
• Fully dynamic bin packing revisited
• Large-scale heterogeneous service systems with general packing constraints

This page was built for publication: An infinite server system with general packing constraints

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