Abstract

Live Migration of virtual machines between different physical hosts is an important process for datacenter management, essential for safeguarding hardware integrity and controlling power consumption, among other functions, with no perceptible interruptions for the user of the virtual machine. As the migration operation has a cost in terms of power and service quality degradation, it is of interest to examine how to best conduct multiple live migrations such that the total time needed to complete all planned migrations is minimized. Scheduling of multiple VM migrations may also take into account the risk of bringing the system to a state where all planned migrations cannot be resolved due to deadlocks caused by resource dependencies.

In this work, we propose a set of solutions based on greedy heuristics for the VM migration problem. We have selected four possible criteria to base scheduling decisions on, and we evaluate the total migration time degree of completion of the planned migrations next to a baseline algorithm. Additionally, we propose two decomposed linear programming models intended for column generation solution: a time-based formulation, followed by a precedence-based formulation. We suppose that these decomposed formulations will lead to faster solution times over conventional, “compact” formulations due to their structure permitting the elimination of a large number of variables from explicit consideration when the continuous relaxation is solved with column generation techniques.