Virtual machine placement for minimizing connection cost in data center networks

We consider an optimization problem for finding efficient placement of virtual machines (VMs) in a data center network. In this problem, we receive requests of VMs from customers, and seek to determine those physical machines in the network that host the requested VMs under capacity constraints. The objective of the problem is to minimize the total connection cost of the VM placement. We propose two models of the connection cost, called the centralized and the distributed models. In the former model, the connection cost for each request is defined as the minimum length of networks connecting all physical host machines and a specified root node, while the network does not connect the root node in the latter model. We present approximation algorithms for this optimization problem. For the centralized model, we present an O(logθ)-approximation algorithm, where θ is the ratio of the largest to the smallest requests. For the distributed model with uniform requests, we present an O(logn)-approximation algorithm for networks on n nodes. We also present a heuristic-based algorithm for the distributed model with non-uniform requests, and verify the performance of our algorithms through computational experiments.