General Algorithm for Fault-Tolerant Virtual Machine Assignments
Jigang Wu, Zinan He, Yaoguo Zhang, Renfei Gao, Siew-Kei Lam · 2017
In the modern data centers based on virtualization, virtual machine assignment (VMA) is the primary research topic to efficiently schedule the cloud resources. It has been proved that the problem of VMA to minimize the maximum access latency is of NP-hard. Most existing works focus on how to assign the virtual machines to the data nodes, but few works are reported on fault-tolerant techniques that is indispensable for the security and reliability of the data center network. This paper presents fault-tolerant algorithms to minimize the maximum data access latency for the problem of VMA with fault virtual machines. The proposed algorithm searches the clique with controllable redundancy in the set of the available virtual machines, and then it selects the machines from the redundant clique and assigns them for the data nodes of the data center network. In the proposed algorithm, the number of redundant virtual machines is controllable. Extensively experimental results show that the maximum access latency is reduced by 10.39%, 5.68%, 9.09%, 5.45% on average, on the popular four network architectures, Tree, VL2, Fat-Tree and BCube, respectively, in comparison to the state-of-the-art of approximation algorithms. For the case of redundancy degree less than 40%, the proposed algorithm can accelerate the assignment for the virtual machines by up to 24% in comparison to the existing algorithm, on the mentioned four popular network architectures.