An analysis of first fit heuristics for the virtual machine relocation problem

In recent years, data centres have come to achieve higher utilization of their infrastructure through the use of virtualization and server consolidation (running multiple application servers simultaneously in one physical server). One problem that arises in these consolidated environments is how to deal with stress situations, that is, when the combined demand of the hosted virtual machines (VMs) exceeds the resource capacity of the host. The VM Relocation problem consists of determining which VMs to migrate and to which hosts to migrate them, so as to relieve the stress situations. In this paper, we propose that the order in which VMs and hosts are considered for migration results in better outcomes, depending on the situation and the data centre´s business goals. We evaluate and compare a set of First Fit-based relocation policies, which consider VMs and hosts in different order. We present simulation results showing that the policies succeed to different extents depending on the scenario and the metrics observed.