Heuristics for migration with consolidation of ensembles of Virtual Machines

Virtualization has lead to great energy efficiency in data center networks through consolidation of computing and other resources. Despite this, there is still room for innovation when considering the off-peak hours and the consolidation required to power down some of the physical machines. Migration of Virtual Machines (VMs) without consideration of network traffic patterns between these VM can lead to inefficiency. There have been algorithms in literature that have considered traffic or other resource consumption to migrate VMs singly or as an ensemble. But, very few algorithms consider migration of ensembles with consolidation based on the traffic pattern of the migrating VMs. In this paper, we present two heuristics for migration with consolidation of VMs based on their communication graph and other resource requirements such as CPU, memory etc.. The heuristics are based on Prim´s Maximum Spanning Tree and a Modified Bread-First Search (MBFS) of the communication graph of VMs identified for migration. The algorithms work by identifying the connected components of the communication graph and placing the VMs of a component in physical machines that are in proximity to each other if it cannot be entirely migrated to a single machine. The MBFS and modified Prim´s algorithms are used to partition a component that does not fit entirely into a single machine, such that the partitions can fit into a single physical machine.