Improving Consolidation of Virtual Machines with Risk-aware Bandwidth Oversubscription in Compute Clouds

Current trends in virtualization, green computing and Cloud computing require ever increasing efficiency in consolidating virtual machines without degrading quality of service. In this work, we consider consolidating virtual machines on the minimum number of physical containers (e.g., hosts or racks) where the physical network (e.g., network interface or top of the rack switch link) may become a bottleneck. Since virtual machines do not require maximum of their nominal bandwidth simultaneously, capacity of the physical container can be multiplexed. We assume that each virtual machine has a probabilistic guarantee – derived from its Service Level Agreement with the Cloud provider – on realizing its bandwidth requirements. Therefore, the problem of consolidating virtual machines on the minimum number of physical containers, while preserving these bandwidth allocation guarantees, can be modeled as Stochastic Bin Packing (SBP) problem, where each virtual machine’s bandwidth demand is treated as a random variable.

We consider both off-line and on-line versions of SBP. Under the assumption that virtual machines’ bandwidth consumption obeys Normal distribution, we show a 2-approximation algorithm for the off-line version and improve the previously reported results by presenting (2+)-competitive algorithm for the on-line one. We also observe that a dual PTAS for SBP can be obtained via reduction to the 2-dimensional vector bin packing problem.

Finally, we perform a thorough performance evaluation study using both synthetic and real data to evaluate the behavior of our proposed algorithms showing their practical applicability.

By: David Breitgand; Amir Epstein

Published in: H-0312 in 2012


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .