 An Infinite Server System with General Packing ConstraintsAlexander L. Stolyar ()
Operations Research, 2013, vol. 61, issue 5, 1200-1217 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 an infinite number of servers. A server-packing 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 Greedy , that attempts to minimize the increment of the objective function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$\sum_k X_k^{1+\alpha}$\end{document} , (alpha) > 0, caused by each new assignment; here X k is the number of servers in configuration k . (When (alpha) is small, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$\sum_k X_k^{1+\alpha}$\end{document} approximates the total number \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$\sum_k X_k$\end{document} of occupied servers.) Our main results show that certain versions of the Greedy algorithm are asymptotically optimal , in the sense of minimizing \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$\sum_k X_k^{1+\alpha}$\end{document} 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 vector-packing constraints, the Greedy algorithm can work with aggregate configurations as opposed to exact configurations k , thus reducing computational complexity while preserving the asymptotic optimality. Keywords: queueing networks; stochastic bin packing; vector packing; infinite server system; fluid limit; cloud computing; virtual machine (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:61:y:2013:i:5:p:1200-1217 Access Statistics for this article More articles in Operations Research from INFORMS Contact information at EDIRC. |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.