关键词: 数据中心, 虚拟机分配, 通讯延迟, 完全子图

Abstract: 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 are 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 (VMA) to minimize the maximum access latency is of NP-hard. This paper proposes a new algorithm for VMA. The proposed algorithm initially determines 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 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 save the computing time by significantly reducing the solution space. Extensive 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 approximation algorithms.

Key words: data center, virtual machine assignment, access latency, complete subgraph