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

作     者：韩晓阳 孟相如 康巧燕 苏玉泽 HAN Xiaoyang;MENG Xiangru;KANG Qiaoyan;SU Yuze

作者机构：空军工程大学研究生院陕西西安710051 空军工程大学信息与导航学院陕西西安710077 

出 版 物：《系统工程与电子技术》 (Systems Engineering and Electronics)

年 卷 期：2019年第41卷第12期

页      面：2891-2898页

核心收录：

学科分类：0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0839[工学-网络空间安全] 0802[工学-机械工程] 0811[工学-控制科学与工程] 

基　　金：国家自然科学基金(61871313 61401499)资助课题 

主　　题：网络虚拟化 虚拟网络映射 二分图 最优匹配 Kuhn-Munkres算法 

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