|M.Sc Student||Nus Alexander|
|Subject||Migration Plans with Minimum Overall Migration Time|
|Department||Department of Computer Science||Supervisor||Professor Dan Raz|
|Full Thesis text|
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 these realistic conditions and outperform currently used methods by a considerable factor.