REAL

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

Mann, Zoltán Ádám (2015) Rigorous results on the effectiveness of some heuristics for the consolidation of virtual machines in a cloud data center. FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF GRID COMPUT, 51. pp. 1-6. ISSN 0167-739X

[img]
Preview
Text
Mann_FGCS_2015.pdf

Download (186kB) | Preview

Abstract

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.

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Q Science / természettudomány > QA Mathematics / matematika > QA76 Computer software / programozás
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 19 Sep 2015 22:25
Last Modified: 19 Sep 2016 23:15
URI: http://real.mtak.hu/id/eprint/26978

Actions (login required)

Edit Item Edit Item