Reducing Access Latency in Virtual Machine Assignments
Renfei Gao, Jigang Wu, Guiyuan Jiang, Siew-Kei Lam, Thambipillai Srikanthan · 2016
In cloud systems, big data must be partitioned and then stored over several data nodes (DNs) for being processed by virtual machines(VMs). Thus, there exists access latency among DNs and their assigned VMs. Meanwhile, the access latency also exists among the pairs of assigned VMs for the computing result collection. Different VM assignment strategies for DNs result in different access latency. It has been proved that how to assign VMs for DNs to minimize the maximum access latency is the problem of NP-hard. This paper proposes a new algorithm for virtual machine assignment. 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. 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. In addition, the proposed algorithm is faster by 7.42% than the existing algorithm in clique finding.