Rigorous results on the effectiveness of some heuristics for the consolidation of virtual machines in a cloud data center

• The MM heuristic is proven to be a 3/2-approximation algorithm.
• The result of the MBFD heuristic can be arbitrarily far from the optimum.
• If MM and MBFD give optimal results, then their interplay is a 2-approximation algorithm.

Dynamic consolidation of virtual machines (VMs) in a cloud data center can be used to minimize power consumption. Beloglazov et al. have proposed the MM (Minimization of Migrations) heuristic for selecting the VMs to migrate from under- or over-utilized hosts, as well as the MBFD (Modified Best Fit Decreasing) heuristic for deciding the placement of the migrated VMs. According to their simulation results, these heuristics work very well in practice. In this paper, we investigate what performance guarantees can be rigorously proven for the heuristics. In particular, we establish that MM is optimal with respect to the number of selected VMs of an over-utilized host and it is a 1.5-approximation with respect to the decrease in utilization. On the other hand, we show that the result of MBFD can be arbitrarily far from the optimum. Moreover, we show that even if both MM and MBFD deliver optimal results, their combination does not necessarily result in optimal VM consolidation, but approximation results can be proven under suitable technical conditions. To the best of our knowledge, these are the first rigorously proven results on the effectiveness of also practically useful heuristic algorithms for the VM consolidation problem.