Migration plans with minimum overall migration time

In this paper we concentrate on finding 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 constrains 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 for a simple model, capturing only the critical aspects of the problem, computing the optimal migration plan is NP hard. We develop algorithms that find 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.