Clique Migration: Affinity Grouping of Virtual Machines for Inter-cloud Live Migration

Affinity is common among Virtual Machines (VMs) in cloud environments. If VMs collaborating on a job are split in geographically distributed clouds, the low bandwidth and high latency inter-cloud communication via a wide area network (WAN) will dramatically degrade the system performance. A potential solution is migrating all of the VMs collaborating on a job in parallel, so as to avoid wide area communication. However, if the job is too large, it becomes impractical to migrate all of the VMs simultaneously due to limited WAN bandwidth and high block dirty rate. We propose a migration optimization mechanism called Clique Migration to partition a large group of VMs into subgroups based on the traffic affinities among VMs. Then, subgroups are migrated one at a time. Based on Clique Migration, we propose and implement two algorithms called R-Min-Cut and Kmeans-SF. Analysis of the traffic trace of 68 VMs in an IBM production cluster shows that our algorithms can reduce inter-cloud traffic by 25% to 60%, when the degree of parallel migration is from 2 to 32. Tests of MPI multi-Ping Ping benchmark running on simulated inter-cloud environments, show that our algorithms can significantly shorten the period during which applications undergo performance degradation. Tests of MPI Reduce scatter benchmark show that R-Min-Cut can keep the performance during migration at 26% to 75% of the non-migration scenario.