基于二分图最优匹配的虚拟网络映射算法

Virtual network embedding algorithm based on bipartite graph optimal matching

针对现有虚拟网络映射存在开销较大、资源利用不够合理的问题,提出了一种基于二分图最优匹配的虚拟网络映射算法。首先以虚拟节点和物理节点为顶点构建二分图,将节点映射问题转化为二分图最优匹配问题;其次将节点资源评价最高的物理节点与节点需求评价最高的虚拟节点优先匹配,并利用Kuhn-Munkres算法求解二分图最优匹配,依据匹配结果进行节点映射;最后利用k-最短路径算法实现链路映射。实验表明,与以往的映射算法相比,提出的映射算法在保持较高映射成功率的同时,提高了长期收益开销比,且资源利用更加合理。

To reduce the cost of network embedding and promote better utilization of resource, a virtual network embedding algorithm based on bipartite graph optimal matching is proposed. First, a bipartite graph is established with the virtual nodes and physical nodes as graph vertexes. Hence the problem of node embedding is converted to the optimization of the bipartite graph. Second, the node with the highest resource value is matched with the node with the highest demand value, then the Kuhn-Munkres algorithm is used for the bipartite graph optimal matching solution, and the node embedding is completed based on the matching results. The link embedding is finally realized via the k-shortest path algorithm. Experimental results show that the proposed algorithm significantly improves the long-term average revenue to cost ratio and is more reasonable in utilizing resource while maintaining a high rate of acceptance ratio.