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

摘要

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