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.