虚拟网映射问题的计算复杂性分析
|
摘要
虚拟网映射是实现网络虚拟化的关键环节,其任务是在满足虚拟网构建约束的前提下,把虚拟网的虚拟节点和虚拟链路分别映射到底层物理网的节点和路径上。文中根据虚拟节点映射是否已知、物理网是否支持路径分割、物理节点是否支持重复映射等特征,对虚拟网映射问题进行分类,并针对一般网络拓扑模型和某些特殊网络拓扑模型完成各类虚拟网映射可行问题和优化问题的计算复杂性分析。
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.
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.
引文
[1]CHOWDHURY N,BOUTABA R.A survey of network virtualization[J].Computer Networks,2010,54(5):862-876.
[2]LIU C X,LU G Q,TANG H B,et al.Adaptive Deployment Method for Virtualized Network Function Based on Viterbi Algorithm[J].Journal of Electronics&Information Technology,2016,38(11):2922-2930.(in Chinese)刘彩霞,卢干强,汤红波,等.一种基于Viterbi算法的虚拟网络功能自适应部署方法[J].电子与信息学报,2016,38(11):2922-2930.
[3]YE Z L,ZHU Y Q,JI P N,et al.Virtual infrastructure mapping in software-defined elastic optical networks[J].Photonic Network Communications,2017,34(1):34-44.
[4]WEN X M,HAN Y N,YU B,et al.A Topology-Aware VDCEmbedding Algorithm in Software-Defined Datacenter[J].Journal of Computer Research and Development,2016,53(4):785-797.(in Chinese)文学敏,韩言妮,于冰,等.软件定义数据中心内一种基于拓扑感知的VDC映射算法[J].计算机研究与发展,2016,53(4):785-797.
[5]HOUIDI I,LOUATI W,ZEGHLACHE D.Exact Multi-Objective Virtual Network Embedding in Cloud Environments[J].The Computer Journal,2015,58(3):403-415.
[6]FISCHER A,BOTERO J F,BECK M T,et al.Virtual Network Embedding:A Survey[J].IEEE Communications Surveys and Tutorials,2013,15(4):1888-1906.
[7]AMALDI E,CONIGLIO S,KOSTER A,et al.On the computational complexity of the virtual network embedding problem[J].Electronic Notes in Discrete Mathematics,2016,52:213-220.
[8]YU J J,WU C M.Virtual network mapping strategy and competitive analysis based on cost constraint[J].Telecommunications Science,2016,32(2):47-54.(in Chinese)余建军,吴春明.基于成本约束的虚拟网映射策略及竞争分析[J].电信科学,2016,32(2):47-54.
[9]SU Y Z,MENG X R,MENG Q W,et al.Environment Adaptive and Joint Topology Aware Virtual Network Embedding Algorithm[J].Journal of Electronics&Information Technology,2018,40(1):79-86.(in Chinese)苏玉泽,孟相如,孟庆微,等.环境自适应的拓扑联合感知虚拟网映射算法[J].电子与信息学报,2018,40(1):79-86.
[10]HU Y,ZHUANG L,LAN J L,et al.Energy Aware Virtual Network Embedding Using Particle Swarm Optimization Algorithm Based on Adaptive Cooperative Coevolution[J].Journal of Electronics&Information Technology,2016,38(10):2660-2666.(in Chinese)胡颖,庄雷,兰巨龙,等.基于自适应协同进化粒子群算法的虚拟网节能映射研究[J].电子与信息学报,2016,38(10):2660-2666.
[11]WANG C,YUAN Y,PENG S C,et al.Fair Virtual Network Embedding Algorithm with Topology Pre-Configuration[J].Journal of Computer Research and Development,2017,54(1):212-220.(in Chinese)王聪,苑迎,彭三城,等.基于拓扑预配置的公平虚拟网络映射算法[J].计算机研究与发展,2017,54(1):212-220.
[12]LI W,WU C M,CHEN J,et al.Virtual Network Mapping Algorithm with Repeatable Mapping over Substrate Nodes[J].Journal of Electronics&Information Technology,2011,33(4):908-914.(in Chinese)李文,吴春明,陈健,等.物理节点可重复映射的虚拟网映射算法[J].电子与信息学报,2011,33(4):908-914.
[13]ANDERSEN D.Theoretical approaches to node assignment[EB/OL].http://www.cs.cmu.edu/~dga/papers/andersenassign.ps,2002.
[14]YU M,YI Y,REXFORD J,et al.Rethinking virtual network embedding:Substrate Support for path splitting and migration[J].ACM SIGCOMM on Computer Communication Review,2008,38(2):17-29.
[15]YU J J,WU C M.Design and Analysis of Virtual Network Mapping Competitive Algorithms[J].Computer Science,2015,42(2):33-38.(in Chinese)余建军,吴春明.虚拟网映射竞争算法设计与分析[J].计算机科学,2015,42(2):33-38.
[16]YU J J,WU C M.Virtual Network Mapping Approximation Algorithm with Admission Control[J].Journal of Electronics&Information Technology,2014,36(5):1235-1241.(in Chinese)余建军,吴春明.支持接入控制的虚拟网映射近似算法[J].电子与信息学报,2014,36(5):1235-1241.
[17]LIU X G,HUAI J P,GAO Q Y,et al.A Virtual Network Embedding Approach to Preserving Node Closeness[J].Chinese Journal of Computers,2012,35(12):2492-2504.(in Chinese)刘新刚,怀进鹏,高庆一,等.一种保持结点紧凑的虚拟网络映射方法[J].计算机学报,2012,35(12):2492-2504.
[18]KLEINBERG J M.Approximation algorithms for disjoint paths problems[J].Operations Research Letters,1996,35(4):533-540.
[19]GAREY M R,JOHNSON D S.“Strong”NP-Completeness Results:Motivation,Examples,and Implications[J].Journal of the Association for Computing Machinery,1978,25(3):499-508.
[20]HOU Y,ZAFER M,LEE K,et al.On the mapping between logical and physical topologies[C]∥Proceedings of the 1st International Conference on Communication Systems and Networks(COMSNETS’09).Bangalore:IEEE Press,2009:483-492.
[21]QI Y H,CAI Y G,CAI H,et al.Chaotic Hybrid Discrete Bat Algorithm for Traveling Salesman Problem[J].Acta Electronica Sinica,2016,44(10):2543-2547.(in Chinese)戚远航,蔡延光,蔡颢,等.旅行商问题的混沌混合离散蝙蝠算法[J].电子学报,2016,44(10):2543-2547.
[22]YU J J,WU C M.Design of Virtual Network Mapping Algorithm Based on K-Best Perfect Matchings of Bipartite Graph[J].Telecommunications Science,2014,30(2):70-75.(in Chinese)余建军,吴春明.基于二分图K优完美匹配的虚拟网映射算法设计[J].电信科学,2014,30(2):70-75.
[23]GAREY M R,JOHNSON D S.Computers and Intractability:AGuide to The Theory of NP-Completeness[M].New York:W.H.Freeman and Company,1979:190-218.
[24]ZHONG Y W,CAI R Y.Discrete Particle Swarm Optimization Algorithm for QAP[J].Acta Automatica Sinica,2007,33(8):871-874.(in Chinese)钟一文,蔡荣英.求解二次分配问题的离散粒子群优化算法[J].自动化学报,2007,33(8):871-874.
[25]BAIER G,SKUTELLA M.On the k-Splittable Flow Problem[J].European Symposium on Algorithms,2002,42(3):101-113.
[2]LIU C X,LU G Q,TANG H B,et al.Adaptive Deployment Method for Virtualized Network Function Based on Viterbi Algorithm[J].Journal of Electronics&Information Technology,2016,38(11):2922-2930.(in Chinese)刘彩霞,卢干强,汤红波,等.一种基于Viterbi算法的虚拟网络功能自适应部署方法[J].电子与信息学报,2016,38(11):2922-2930.
[3]YE Z L,ZHU Y Q,JI P N,et al.Virtual infrastructure mapping in software-defined elastic optical networks[J].Photonic Network Communications,2017,34(1):34-44.
[4]WEN X M,HAN Y N,YU B,et al.A Topology-Aware VDCEmbedding Algorithm in Software-Defined Datacenter[J].Journal of Computer Research and Development,2016,53(4):785-797.(in Chinese)文学敏,韩言妮,于冰,等.软件定义数据中心内一种基于拓扑感知的VDC映射算法[J].计算机研究与发展,2016,53(4):785-797.
[5]HOUIDI I,LOUATI W,ZEGHLACHE D.Exact Multi-Objective Virtual Network Embedding in Cloud Environments[J].The Computer Journal,2015,58(3):403-415.
[6]FISCHER A,BOTERO J F,BECK M T,et al.Virtual Network Embedding:A Survey[J].IEEE Communications Surveys and Tutorials,2013,15(4):1888-1906.
[7]AMALDI E,CONIGLIO S,KOSTER A,et al.On the computational complexity of the virtual network embedding problem[J].Electronic Notes in Discrete Mathematics,2016,52:213-220.
[8]YU J J,WU C M.Virtual network mapping strategy and competitive analysis based on cost constraint[J].Telecommunications Science,2016,32(2):47-54.(in Chinese)余建军,吴春明.基于成本约束的虚拟网映射策略及竞争分析[J].电信科学,2016,32(2):47-54.
[9]SU Y Z,MENG X R,MENG Q W,et al.Environment Adaptive and Joint Topology Aware Virtual Network Embedding Algorithm[J].Journal of Electronics&Information Technology,2018,40(1):79-86.(in Chinese)苏玉泽,孟相如,孟庆微,等.环境自适应的拓扑联合感知虚拟网映射算法[J].电子与信息学报,2018,40(1):79-86.
[10]HU Y,ZHUANG L,LAN J L,et al.Energy Aware Virtual Network Embedding Using Particle Swarm Optimization Algorithm Based on Adaptive Cooperative Coevolution[J].Journal of Electronics&Information Technology,2016,38(10):2660-2666.(in Chinese)胡颖,庄雷,兰巨龙,等.基于自适应协同进化粒子群算法的虚拟网节能映射研究[J].电子与信息学报,2016,38(10):2660-2666.
[11]WANG C,YUAN Y,PENG S C,et al.Fair Virtual Network Embedding Algorithm with Topology Pre-Configuration[J].Journal of Computer Research and Development,2017,54(1):212-220.(in Chinese)王聪,苑迎,彭三城,等.基于拓扑预配置的公平虚拟网络映射算法[J].计算机研究与发展,2017,54(1):212-220.
[12]LI W,WU C M,CHEN J,et al.Virtual Network Mapping Algorithm with Repeatable Mapping over Substrate Nodes[J].Journal of Electronics&Information Technology,2011,33(4):908-914.(in Chinese)李文,吴春明,陈健,等.物理节点可重复映射的虚拟网映射算法[J].电子与信息学报,2011,33(4):908-914.
[13]ANDERSEN D.Theoretical approaches to node assignment[EB/OL].http://www.cs.cmu.edu/~dga/papers/andersenassign.ps,2002.
[14]YU M,YI Y,REXFORD J,et al.Rethinking virtual network embedding:Substrate Support for path splitting and migration[J].ACM SIGCOMM on Computer Communication Review,2008,38(2):17-29.
[15]YU J J,WU C M.Design and Analysis of Virtual Network Mapping Competitive Algorithms[J].Computer Science,2015,42(2):33-38.(in Chinese)余建军,吴春明.虚拟网映射竞争算法设计与分析[J].计算机科学,2015,42(2):33-38.
[16]YU J J,WU C M.Virtual Network Mapping Approximation Algorithm with Admission Control[J].Journal of Electronics&Information Technology,2014,36(5):1235-1241.(in Chinese)余建军,吴春明.支持接入控制的虚拟网映射近似算法[J].电子与信息学报,2014,36(5):1235-1241.
[17]LIU X G,HUAI J P,GAO Q Y,et al.A Virtual Network Embedding Approach to Preserving Node Closeness[J].Chinese Journal of Computers,2012,35(12):2492-2504.(in Chinese)刘新刚,怀进鹏,高庆一,等.一种保持结点紧凑的虚拟网络映射方法[J].计算机学报,2012,35(12):2492-2504.
[18]KLEINBERG J M.Approximation algorithms for disjoint paths problems[J].Operations Research Letters,1996,35(4):533-540.
[19]GAREY M R,JOHNSON D S.“Strong”NP-Completeness Results:Motivation,Examples,and Implications[J].Journal of the Association for Computing Machinery,1978,25(3):499-508.
[20]HOU Y,ZAFER M,LEE K,et al.On the mapping between logical and physical topologies[C]∥Proceedings of the 1st International Conference on Communication Systems and Networks(COMSNETS’09).Bangalore:IEEE Press,2009:483-492.
[21]QI Y H,CAI Y G,CAI H,et al.Chaotic Hybrid Discrete Bat Algorithm for Traveling Salesman Problem[J].Acta Electronica Sinica,2016,44(10):2543-2547.(in Chinese)戚远航,蔡延光,蔡颢,等.旅行商问题的混沌混合离散蝙蝠算法[J].电子学报,2016,44(10):2543-2547.
[22]YU J J,WU C M.Design of Virtual Network Mapping Algorithm Based on K-Best Perfect Matchings of Bipartite Graph[J].Telecommunications Science,2014,30(2):70-75.(in Chinese)余建军,吴春明.基于二分图K优完美匹配的虚拟网映射算法设计[J].电信科学,2014,30(2):70-75.
[23]GAREY M R,JOHNSON D S.Computers and Intractability:AGuide to The Theory of NP-Completeness[M].New York:W.H.Freeman and Company,1979:190-218.
[24]ZHONG Y W,CAI R Y.Discrete Particle Swarm Optimization Algorithm for QAP[J].Acta Automatica Sinica,2007,33(8):871-874.(in Chinese)钟一文,蔡荣英.求解二次分配问题的离散粒子群优化算法[J].自动化学报,2007,33(8):871-874.
[25]BAIER G,SKUTELLA M.On the k-Splittable Flow Problem[J].European Symposium on Algorithms,2002,42(3):101-113.