Clustering based virtual machines placement in distributed cloud computing

Resource virtualization is one of the most prominent characteristics of cloud computing. The placement of virtual machines (VMs) in the physical machines determines the resource utilization efficiency and service quality. Especially for distributed cloud computing, where the data centers (DCs) span a large number of geographical areas and all DCs are connected by high speed internet, the placement of VMs of one big task or of one organization focuses on minimizing the distances and bandwidths between DCs. This minimizes communication latency and improves availability. A data center cluster should be found firstly to accommodate the requested VMs. The purpose is to minimize the maximum inter-DC distance. In contrast to existing method that only considers the distances between data centers, a more efficient clustering based 2-approximation algorithm is developed by taking full use of the topology and the density property of cloud network. The simulation shows the proposed algorithm is especially appropriate for very large scale problems. Then, the requested VMs should be partitioned to the DC cluster, so that the expensive inter-DC bandwidth is saved and the availability is improved. With the introduction of a half communication model, a novel heuristic algorithm which further cuts down the used bandwidths is presented to partition VMs. Its time complexity is reduced to O(n²) by a factor of O(logn) and it runs 3 times faster than the existing method.