极小通讯延迟的虚拟机分配算法

来源：计算机科学与探索杂志2016年第7期北京时间：

作者：高任飞，武继刚，周莹，张耀国

单位：1. 天津工业大学 计算机科学与软件学院，天津 3003872. 广东工业大学 计算机科学与技术学院，广州 510006

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

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