Virtual Machine Fault-tolerant Allocation Algorithm With Controllable Redundancy

In recent years,with the rapid growth of Data Center and the growing importance of the Mapreduce/Hadoop framework,more and more big data is processed in cloud systems.In the modern virtualized data center,virtual machine allocation is the primary consideration for scheduling resource efficiently in the cloud.In the cloud system,big data is divided and stored in data nodes waiting for processing.The problem of allocating virtual machines to data nodes by considering the access latency among virtual machines and data nodes,which minimizes the maximum access latency,has been proved to be NP-hard.But few works are reported on fault-tolerant algorithms for virtual machine assignment problems,that is very important for the security and reliability of the data center network.This paper has proposed two new algorithms for virtual machine fault-tolerant assignment,which can meet the requirements of fault-tolerance of any size.From the perspective of reducing the solution space and improving the quality of solutions,we propose a fault-tolerant assignment algorithm for virtual machines assignment with controllable redundancy.The algorithm uses the Turan theorem to judge whether there is a virtual Machine cluster meeting the fault-tolerant demand.If it exists,the branch sub-graph and the backtracking method are used to search the sub-graphs which satisfy the redundancy requirement and communicate with each other under the threshold.Then processing sub-graphs and removes redundant virtual machine.Finally,the Hopcroft-Karp algorithm is used to assign the virtual machine resources in the redundant group to the data nodes.The experimental results show that the proposed algorithm can reduce the maximum access latency by 9.09%,4.5%,4.5%and 4.5%,respectively,in the tree,VL2,Fat-Tree and BCube network topology compared with the latest approximation algorithms.The another algorithm,from the perspective of reducing the complexity of the algorithm,selects a group of VMs which communicate with each other under a certain threshold limit in access latency according to the trigonometric inequality principle.And then using the greedy method to to find a redundant clique containing a certain number of VMs from the obtained group of VMs.If the group is greater than or equal to the size of the redundant requirements,the needless nodes are deleted.Finally,the Hopcroft-Karp algorithm is used to assign the virtual machine resources in the redundant group to the data nodes.The experimental results show that the algorithm proposed in this paper can find a virtual machine cluster with controllable redundancy.At the same time the average running time is reduced by 12.8%comparing with the current heuristic algorithm.