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

摘要： 在现代基于虚拟化的数据中心上，虚拟机分配是实现云中资源有效调度的首要考虑。在云系统中，大数据被划分成多个数据存储在数据中心的数据结点上等待虚拟机处理，此时不仅存在虚拟机处理数据时的通讯延迟，也存在汇总计算结果时虚拟机之间的通讯延迟。虚拟机分配策略的不同将导致最大通讯延迟的不同。已经证明对数据结点分配虚拟机，并考虑虚拟机之间的通讯延迟，使得最大通讯延迟最小的问题是NP-hard问题。提出了一种新的虚拟机分配算法。该算法首先判断在通讯延迟的某一阈值内是否存在规模多于数据结点的能够互相通讯的虚拟机机群。若存在则用有效的回溯法寻找在此阈值下由虚拟机构成的完全子图，然后采用Hopcroft-Karp算法将完全子图中的虚拟机分配给数据结点。这种方法能够有效减小解空间，降低虚拟机分配的时间。实验结果表明，所提算法在Tree、VL2、Fat-Tree和BCube网络结构中，与当前最新的近似算法相比，平均情况下最大通讯延迟分别降低了10.39%、5.68%、9.09%、5.45%。

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