User Tools

Site Tools


optimal_online_bin_packing_in_an_infinite_server_system

Abstract: We consider a large-scale service system model motivated by the problem of efficient placement of virtual machines to physical host machines in a network cloud. Customers of different types arrive to a system with an infinite number of servers, and are immediately placed into a server, subject to system packing constraints. Each arriving customer stays for a random amount of time, and leaves its server and the system.

A key performance objective is minimizing the total number of occupied hosts. In this talk, we describe various greedy placement policies and discuss their performances. In particular, we show that a policy called “Greedy with sublinear Safety Stocks (GSS)” is asymptotically optimal, as the customer arrival rates grow to infinity.

This is joint work with Alexander Stolyar.

Bio: Yuan Zhong recently completed his PhD degree in the Operations Research Center at MIT under the supervision of Devavrat Shah and John Tsitsiklis. He is currently a postdoctoral scholar in the Computer Science department at University of California, Berkeley, and will join the the Department of Industrial Engineering and Operations Research at Columbia University in Fall 2013. Yuan is broadly interested in the modeling and analysis of large-scale stochastic systems, with business and engineering applications. He is a recipient of the Kenneth C. Sevcik Outstanding Student Paper Award at Sigmetrics/Performance 2012, London, UK.

optimal_online_bin_packing_in_an_infinite_server_system.txt · Last modified: 2016/09/01 19:15 (external edit)