一种改进的高可靠性虚拟网络映射算法研究

摘要

对多个数据中心虚拟机分配时的高可靠性虚拟网络映射(RVNM)问题进行研究,目的是在满足各数据中心容量约束和各条链路带宽容量约束的同时,使虚拟网络的总体可靠性最大。为此,首先描述了虚拟网络和物理网络的图模型,以及包括链路可靠性和节点可靠性的可靠性函数。然后,重新定义了高可靠性虚拟网络映射(RVNM)问题并证明该问题是NP难题。将该问题建模为整数线性规划问题,并采用匈牙利算法获得小规模网络条件下的求解结果。最后,文中还提出了一种面向大规模网络的基于双阶段博弈的链路映射优先算法,并从理论上证明了该算法的收敛性。仿真实验结果表明,所提算法在小规模网络条件下的可靠性较高且接近于最优解,在大规模网络条件下的性能优于当前最新的节点映射优先算法。