An infinite server system with general packing constraints: Asymptotic optimality of a greedy randomized algorithm

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Motivated primarily by the problem of efficient assignment of virtual machines to physical host machines in a network cloud, we consider an infinite-server system with several types of arriving customers. Multiple customers can be placed into one server for service, subject to general 'packing' constraints. Service times of different customers are independent, even if served simultaneously by the same server. Customers are placed for service immediately upon arrival, and leave the system after service completion. A key system objective is to minimize the total number of occupied servers. We propose Greedy-Random (GRAND), an extremely simple customer placement algorithm, which is also easy to implement. We show that a version of GRAND is essentially asymptotically optimal, as the customer arrival rates grow to infinity. We also study several versions of the GRAND algorithms by simulations.

Original languageEnglish (US)
Title of host publication2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
PublisherIEEE Computer Society
Pages575-582
Number of pages8
ISBN (Print)9781479934096
DOIs
StatePublished - Jan 1 2013
Event51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013 - Monticello, IL, United States
Duration: Oct 2 2013Oct 4 2013

Publication series

Name2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013

Other

Other51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
CountryUnited States
CityMonticello, IL
Period10/2/1310/4/13

    Fingerprint

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Control and Systems Engineering

Cite this

Stolyar, A. L., & Zhong, Y. (2013). An infinite server system with general packing constraints: Asymptotic optimality of a greedy randomized algorithm. In 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013 (pp. 575-582). [6736576] (2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013). IEEE Computer Society. https://doi.org/10.1109/Allerton.2013.6736576