ceClub: Almost Optimal Virtual Machine Placement for Traffic Intense Data Centers

Liane Lewin-Eytan (Yahoo! Labs)
Wednesday, 22.1.2014, 11:30
EE Meyer Building 861

The recent growing popularity of cloud-based solutions and the variety of new applications present new challenges for cloud management and resource utilization. In this paper we concentrate on the networking aspect and consider the placement problem of virtual machines (VMs) of applications with intense bandwidth requirements. Optimizing the available network bandwidth is far more complex than optimizing resources like memory or CPU, since every network link may be used by many physical hosts and thus by the VMs residing in these hosts. We focus on maximizing the benefit from the overall communication sent by the VMs to a single designated point in the data center (called the root). This is the typical case when considering a storage area network of applications with intense storage requirements.

We formulate a bandwidth-constrained VM placement optimization problem that models this setting. This problem is NP hard, and we present a polynomial-time constant approximation algorithm for its most general version, in which hosts are connected to the root by a general network graph. For more practical cases, in which the network topology is a tree and the benefit is a simple function of the allocated bandwidth, we present improved approximation algorithms that are more efficient in terms of running time. We evaluate the expected performance of our proposed algorithms through a simulation study over traces from a real production data center, providing strong indications to the superiority of our proposed solutions.

Liane Lewin-Eytan received her B.Sc, M.Sc, and Ph.D. from the Dept. of Electrical Engineering, Technion - Israel Institute of Technology, Haifa in 1999, 2001 and 2008, respectively. She is currently a Research Scientist at Yahoo Labs. During the years 2009-2013, she was a Research Staff Member at IBM Research - Haifa, and worked among others on smart grid networks, cloud networking and network virtualization. Among her research interests are non-cooperative networking games, dynamic and online network analysis, network virtualization, data science and machine learning.

Back to the index of events