Stochastic Dynamic Bin Packing with Applications to Cloud Computing

Tuesday, November 4, 2014 - 4:00pm

Event Calendar Category

LIDS Seminar Series

Speaker Name

Yuan Zhong

Affiliation

Columbia University

Building and Room number

32-141

Abstract

We present a new class of bin packing models, so-called large-scale stochastic dynamic bin packing, which are primarily motivated by the problem of virtual machine placement into physical servers in cloud computing clusters.

A key performance objective is to minimize the total number of occupied servers. In this talk, we describe several placement policies and establish their performance and scalability properties. In particular, we propose Greedy-Random (GRAND), a class of extremely simple policies, and show that a version of GRAND is asymptotically optimal, as the system scale goes to infinity. We then complement the theoretical results with simulation studies, and conclude with some open problems.

This talk is based on joint works with Sasha Stolyar of Lehigh University.
 

Biography

Yuan Zhong is an assistant professor in the IEOR department at Columbia University. Before joining Columbia, he spent one year as a postdoc in the computer science department at UC Berkeley. He received his B.A. in mathematics from the University of Cambridge in 2006, M.A. in mathematics from Caltech in 2008, and Ph.D. in operations research from MIT in 2012.

Yuan Zhong is broadly interested in the modeling and analysis of large-scale stochastic systems, with applications in areas such as communications networks, data centers, cloud computing and health care. He received the best student paper award at Sigmetrics 2012.

Reception information

Reception to follow.