Technical Report MSC-2015-05

Title: Migration Plans With Minimum Overall Migration Time
Authors: Alexander Nus
Supervisors: Danny Raz
PDFCurrently accessibly only within the Technion network
Abstract: Virtualization is one of the most important technologies that stand behind the recent vast popularity of cloud services. This is due to the fact that it allows placing several Virtual Machines (VMs) on a single physical host and thus improving cost efficiency. The exact VM placement (also known as VM scheduling) has a critical impact on the cloud providers cost and thus has been extensively studied in recent years. Placement algorithms (both in academic papers and in real systems) calculate an optimized placement for a data center, considering various target functions and constraints. However, in most cases they do not deal with the exact way this placement is to be realized taking the current placement into account.

In this thesis we concentrate on the dynamics of this global state change where the goal is to and the best migration plan, that is, a partial ordering of live migrations that realizes a move from the current to the desired placement, takes the minimal possible time, and maintains the placement constraints throughout the process. This is not an easy task since additional resources and intermediate migrations may be needed in order to maintain feasibility; in fact, we show that even in a simple model, capturing only the critical aspects of the problem, computing the optimal migration plan is NP hard. We develop algorithms that and feasible migration plans and prove that their overall migration time is within an adaptive constant factor from the optimal possible time. Then, using data from real cloud placements, we evaluate the expected performance of these algorithms in realistic scenarios. Our results indicate that the algorithms perform very well under this realistic conditions and outperform currently used methods by a considerable factor.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2015
To the main CS technical reports page

Computer science department, Technion