A Virtual Machine Repacking in Clouds: Faster Live Migration Algorithms

Makhlouf Hadji, Paul Labrogère (IRT SystemX)

Résumé

Repacking in clouds, or the reassignment of services to physical servers, is required to reduce cost and improve infrastructure utilization. Initial provisioning through smart placement is not sufficient to ensure system efficiency. This paper presents a novel and original scalable linear programming algorithm, based on b-matching theory, to optimally solve the repacking problem with negligible SLA violations. A greedy algorithm based on matroid theory is proposed to eliminate completely SLA violations and derive a solution whose performance is compared to a Best-Fit and a Bin-Packing formulation acting as lower and upper bounds or benchmarks. Reported performance results show that both the b-matching and the greedy algorithms scale well and trade-off the number of migrations and servers to find optimal solutions. The b-matching uses fewer migrations but more servers to reduce SLA violations while the greedy algorithm (for the graphic matroid) uses more migrations in fewer servers to eliminate the violations. Both find optimal solutions in convergence times in line with operational systems requirements with a clear advantage for b-matching.