Virtual Machine Assignment Algorithm With Minimal Communication Delay

As Data Center is rapidly developing and Mapreduce/Hadoop architecture becomes increasingly significant in recent years, more and more big data is processed in cloud systems. In the modern data centers based on virtualization, virtual machine (VM) assignment is the primary research topic to efficiently schedule the cloud resources. In cloud systems the big data is partitioned and then stored over several data nodes (DNs) for being processed by VMs. Thus, there is access latency among DNs and their assigned VMs. Meanwhile, the access latency among the pairs of assigned VMs also exists for the computing result collection. Different assignment strategies of VMs for DNs result in different maximum access latency. It has been proved that the assignment problem of VMs for DNs to minimize the maximum access latency is of NP-hard.This paper proposes three new algorithms for virtual machine assignment. The first two proposed algorithms initially determine if there exists enough number of VMs which can communicate with each other under a certain threshold limit in access latency. If yes, an efficient backtrack algorithm or branch and bound algorithm is then employed to find cliques consisted of VMs under this threshold. After that, the Hopcroft-Karp algorithm is used to assign the VMs in the clique for DNs, in order to improve the quality ofthe solution by significantly reducing the solution space. Extensively experimental results show that the maximum access latency is reduced 10.39%,5.68%,9.09%,5.45% on average, respectively, on the popular four network architectures, Tree, VL2,Fat-Tree and BCube, in comparison to the state-of-the-art of approximation algorithms.This paper proposes another algorithm for virtual machine assignment in order to reduce algorithm complexity. The proposed algorithm initially selects a group of VMs which communicate with each other under a certain threshold limit in access latency. Then, it utilizes an efficient heuristic algorithm, that is also proposed in this paper, to find a clique containing a certain number of VMs from the obtained group of VMs. After that, the proposed algorithm employs the Hopcroft-Karp algorithm to assign the VMs in the clique for DNs.This algorithm is faster by 8.33% on average than the existing heuristic algorithm.