Reliable Virtual Machine placement in distributed clouds

In nowadays cloud computing systems, leveraging the virtualization technology, the customer's requested data computing or storing service is accommodated by a set of mutual-communicated Virtual Machines (VM) in a scalable and elastic manner. These VMs are placed in one or more datacenter nodes according to nodes' capacities, failure probabilities, etc. The VM placement availability refers to the probability that at least one set of the whole customer's requested VMs operates during the entire requested lifetime. The placed VMs should obey the agreed-upon availability, otherwise the cloud provider may face revenue loss. In this paper, we study the problem of placing at most H sets of k requested VMs on minimum number of datacenter nodes, such that the VM placement availability requirement is satisfied and each VM pair has a communication delay no greater than the specified. We prove that this problem is NP-hard. We subsequently propose an exact Integer Nonlinear Program (INLP) and an efficient heuristic to solve this problem. Finally, we conduct simulations to compare the proposed algorithms with two existing heuristics in terms of acceptance ratio, average number of used nodes and running time.