Migration-based virtual machine placement in cloud systems

Cloud computing is an emerging technology that greatly shapes our lives, where users run jobs on virtual machines (VMs) on physical machines (PMs) provided by a cloud provider, saving the investment in upfront infrastructures. Due to the heterogeneity of various jobs, different VMs on the same PM can have different job completion times. Meanwhile, the PMs are also heterogeneous. Therefore, different VM placements have different job completion times. Our objective is to minimize the total job completion time of the input VM requests through a reasonable VM placement schedule. This problem is NP-hard, since it can be reduced to a knapsack problem. We propose an off-line VM placement method through emulated VM migration, while the on-line VM placement is solved by a real VM migration process. The migration algorithm is a heuristic approach, where we place the VM to its best PM directly, as long as it has enough capacity. Otherwise, if the migration constraint is satisfied, we migrate another VM from this PM to accommodate the new VM. Furthermore, we study a hybrid scheme where a batch is employed to accept upcoming VMs for the on-line scenario. Evaluation results prove the high efficiency of our algorithms.