Scheduling Live Migrations of Virtual Machines during Host Evacuation

Server virtualization introduces new capabilities that improve the efficiency of data centers. One such capability is live migration of virtual machines – the ability to move an operational virtual machine from one physical host to another without perceivable downtime of applications running within the virtual machine. Efficient management of live migrations is particularly important in scenarios involving a large number of migrations, such as host maintenance or workload consolidation, when all virtual machines running on a host need to be evacuated to other hosts. Since live migration is demanding on host and network resources, decreasing the time needed for host evacuation can improve system availability and reduce administrative costs. In an emergency, when a host is likely to become unavailable quickly, minimizing the duration of host evacuation narrows the risk of losing applications.

This paper presents the problem of scheduling virtual machine migrations during host evacuation. Given a set of migrations emanating from a single host, each migration having a length and a predefined destination host, and a set of limits on the number of migrations each host can handle concurrently, the goal is to obtain a migration schedule whose total length (makespan) is minimal. The problem is known to be NP-hard. We obtain approximation bounds on the makespan for two common greedy scheduling heuristics: LS and LPT, and show that an optimal schedule can be generated using LS. We then devise a (2+ǫ)-approximation scheme for the problem. Finally, we introduce a family of custom heuristics, and demonstrate empirically that they outperform the common heuristics. We also demonstrate that the custom heuristics are comparable with a scheduler deploying a commercial constraint programming solver, while our heuristics are considerably simpler and faster.