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.

By: Alex Glikson, Amir Epstein, Assaf Israel, John Marberg

Published in: H-0296 in 2011


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .