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

doi:10.11896／j.issn.1002-137X.2018.11.012

摘要/Abstract

摘要： 虚拟网映射是实现网络虚拟化的关键环节,其任务是在满足虚拟网构建约束的前提下,把虚拟网的虚拟节点和虚拟链路分别映射到底层物理网的节点和路径上。文中根据虚拟节点映射是否已知、物理网是否支持路径分割、物理节点是否支持重复映射等特征,对虚拟网映射问题进行分类,并针对一般网络拓扑模型和某些特殊网络拓扑模型完成各类虚拟网映射可行问题和优化问题的计算复杂性分析。

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

Abstract: 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.

Key words: Computational complexity, Optimization problem, Strongly NP-hard problems, Virtual network mapping

中图分类号:

TP393

余建军, 吴春明. 虚拟网映射问题的计算复杂性分析[J]. 计算机科学, 2018, 45(11): 87-91. https://doi.org/10.11896／j.issn.1002-137X.2018.11.012

YU Jian-jun, WU Chun-ming. Computational Complexity Analysis of Virtual Network Mapping Problem[J]. Computer Science, 2018, 45(11): 87-91. https://doi.org/10.11896／j.issn.1002-137X.2018.11.012

参考文献

[1]CHOWDHURY N,BOUTABA R.A survey of network virtuali- zation[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 VDC Embedding 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/andersena-ssign.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 logi- cal 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:A Guide 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.

相关文章 15

[1]	黄国兴, 杨泽铭, 卢为党, 彭宏, 王静文. 利用粒子滤波方法求解数据包络分析问题 Solve Data Envelopment Analysis Problems with Particle Filter 计算机科学, 2022, 49(6A): 159-164. https://doi.org/10.11896/jsjkx.210600110
[2]	潘燕娜, 冯翔, 虞慧群. 基于自适应资源分配池的竞争合作群协同优化算法 Competitive-Cooperative Coevolution for Large Scale Optimization with Computation Resource Allocation Pool 计算机科学, 2022, 49(2): 182-190. https://doi.org/10.11896/jsjkx.201200012
[3]	李笠, 李广鹏, 常亮, 古天龙. 约束进化算法及其应用研究综述 Survey of Constrained Evolutionary Algorithms and Their Applications 计算机科学, 2021, 48(4): 1-13. https://doi.org/10.11896/jsjkx.200600151
[4]	朱凯, 毋国庆, 袁梦霆. 关于同步部分规约的有限自动机的优化问题的近似难度 On Hardness of Approximation for Optimized Problem of Synchronizing Partially Specified Deterministic Finite Automata 计算机科学, 2020, 47(5): 14-21. https://doi.org/10.11896/jsjkx.200200073
[5]	王雅慧, 刘博, 袁晓彤. 基于近似牛顿法的分布式卷积神经网络训练 Distributed Convolutional Neural Networks Based on Approximate Newton-type Mothod 计算机科学, 2019, 46(7): 180-185. https://doi.org/10.11896/j.issn.1002-137X.2019.07.028
[6]	董明刚,刘宝,敬超. 模糊自适应排序变异多目标差分进化算法 Multi-objective Differential Evolution Algorithm with Fuzzy Adaptive Ranking-based Mutation 计算机科学, 2019, 46(7): 224-232. https://doi.org/10.11896/j.issn.1002-137X.2019.07.034
[7]	余建军, 吴春明. 基于禁忌遗传优化的离线静态虚拟网映射算法 Offline Static Virtual Network Mapping Algorithm Based on Tabu Search Genetic Optimization 计算机科学, 2019, 46(12): 114-119. https://doi.org/10.11896/jsjkx.181001981
[8]	赖文星, 邓忠民. 基于支配强度的NSGA2改进算法 Improved NSGA2 Algorithm Based on Dominant Strength 计算机科学, 2018, 45(6): 187-192. https://doi.org/10.11896/j.issn.1002-137X.2018.06.033
[9]	丁舒阳,黎冰,侍洪波. 基于改进的离散PSO算法的FJSP的研究 Study on Flexible Job-shop Scheduling Problem Based on Improved Discrete Particle Swarm Optimization Algorithm 计算机科学, 2018, 45(4): 233-239. https://doi.org/10.11896/j.issn.1002-137X.2018.04.039
[10]	安悦瑄, 丁世飞, 胡继普. 孪生支持向量机综述 Twin Support Vector Machine:A Review 计算机科学, 2018, 45(11): 29-36. https://doi.org/10.11896／j.issn.1002-137X.2018.11.003
[11]	马庆. 基于多目标进化算法的MOEA/D权重向量产生方法 Multi-objective Evolutionary Algorithm Based Weight Vectors Generation Method of MOEA/D 计算机科学, 2016, 43(Z11): 117-122. https://doi.org/10.11896/j.issn.1002-137X.2016.11A.025
[12]	苏丁为,周创明,王毅. 基于直觉模糊熵的粒子群多目标优化 Particle Swarm Algorithm for Multi-objective Optimization Based on Intuitionistic Fuzzy Entropy 计算机科学, 2016, 43(8): 262-266. https://doi.org/10.11896/j.issn.1002-137X.2016.08.053
[13]	余建军,吴春明. 虚拟网映射竞争算法设计与分析 Design and Analysis of Virtual Network Mapping Competitive Algorithms 计算机科学, 2015, 42(2): 33-38. https://doi.org/10.11896/j.issn.1002-137X.2015.02.007
[14]	余建军,吴春明. 基于负载均衡的虚拟网映射随机算法 Randomized Algorithm for Virtual Network Mapping Problem Based on Load Balancing 计算机科学, 2014, 41(6): 69-74. https://doi.org/10.11896/j.issn.1002-137X.2014.06.014
[15]	陈亚瑞. Ising图模型概率推理的计算复杂性 Computational Complexity of Probabilistic Inference in Icing Graphical Model 计算机科学, 2013, 40(2): 253-256.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed