虚拟网映射问题的计算复杂性分析  

Computational Complexity Analysis of Virtual Network Mapping Problem

作　　者：余建军[1] 吴春明[2] YU Jian-jun;WU Chun-ming(Quzhou College of Technology,Quzhou,Zhejiang 324000,China;Institute of Computer System and Network Security,Zhejiang University,Hangzhou 310027,China)

机构地区：[1]衢州职业技术学院,浙江衢州324000 [2]浙江大学计算机系统结构与网络安全研究所,杭州310027

出　　处：《计算机科学》2018年第11期87-91,共5页Computer Science

基　　金：浙江省自然科学基金资助项目(LY14F020010);国家863高技术研究发展计划项目(2015AA015602;2015AA016013)资助

摘　　要：虚拟网映射是实现网络虚拟化的关键环节,其任务是在满足虚拟网构建约束的前提下,把虚拟网的虚拟节点和虚拟链路分别映射到底层物理网的节点和路径上。文中根据虚拟节点映射是否已知、物理网是否支持路径分割、物理节点是否支持重复映射等特征,对虚拟网映射问题进行分类,并针对一般网络拓扑模型和某些特殊网络拓扑模型完成各类虚拟网映射可行问题和优化问题的计算复杂性分析。Virtual network mapping plays a central role in network virtualization,which maps the virtual nodes and virtual links to the underlying substrate network nodes and paths,respectively,while satisfying the constraint of virtual network construction.This paper categorized the virtual network mapping problem according to whether all the virtual nodes are already mapped,whether the substrate network supports path splitting and whether the substrate nodes support repeatable mapping,and then completed the computational complexity analysis of the feasibility and optimization problem of various virtual network mapping for the general network topology model and some special network topology models.

关 键 词：虚拟网映射 计算复杂性 强NP难问题 优化问题 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]