skip to main content

RSRG Seminar

Thursday, May 16, 2013
12:00pm to 1:00pm
Add to Cal
Annenberg 213
Optimal Online Bin Packing in an Infinite Server System
Yuan Zhong, Computer Science, UC Berkeley,

 

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, after which it 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. 
For more information, please contact Sydney Garstang by phone at x4555 or by email at [email protected].