Computer Science

Computer Science ›› 2018, Vol. 45 ›› Issue (11): 87-91.doi: 10.11896／j.issn.1002-137X.2018.11.012

• Network & Communication • Previous Articles     Next Articles

Computational Complexity Analysis of Virtual Network Mapping Problem

YU Jian-jun1, WU Chun-ming2   

  1. (Quzhou College of Technology,Quzhou,Zhejiang 324000,China)1
    (Institute of Computer System and Network Security,Zhejiang University,Hangzhou 310027,China)2
  • Received:2018-02-12 Published:2019-02-25

PDF (PC)

579

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

CLC Number: 

  • TP393
[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.
[1] HUANG Hua-wei, LI Chun-hua. Security Analysis of A Key Exchange Protocol Based on Tropical Semi-ring [J]. Computer Science, 2022, 49(6A): 571-574.
[2] HUANG Guo-xing, YANG Ze-ming, LU Wei-dang, PENG Hong, WANG Jing-wen. Solve Data Envelopment Analysis Problems with Particle Filter [J]. Computer Science, 2022, 49(6A): 159-164.
[3] HAN Jie, CHEN Jun-fen, LI Yan, ZHAN Ze-cong. Self-supervised Deep Clustering Algorithm Based on Self-attention [J]. Computer Science, 2022, 49(3): 134-143.
[4] PAN Yan-na, FENG Xiang, YU Hui-qun. Competitive-Cooperative Coevolution for Large Scale Optimization with Computation Resource Allocation Pool [J]. Computer Science, 2022, 49(2): 182-190.
[5] YOU Ling, GUAN Zhang-jun. Low-complexity Subcarrier Allocation Algorithm for Underwater OFDM Acoustic CommunicationSystems [J]. Computer Science, 2021, 48(6A): 387-391.
[6] ZHANG Qiang, HUANG Zhang-can, TAN Qing, LI Hua-feng, ZHAN Hang. Pyramid Evolution Strategy Based on Dynamic Neighbor Lasso [J]. Computer Science, 2021, 48(6): 215-221.
[7] LI Li, LI Guang-peng, CHANG Liang, GU Tian-long. Survey of Constrained Evolutionary Algorithms and Their Applications [J]. Computer Science, 2021, 48(4): 1-13.
[8] ZHU Kai, WU Guo-qing, YUAN Meng-ting. On Hardness of Approximation for Optimized Problem of Synchronizing Partially Specified Deterministic Finite Automata [J]. Computer Science, 2020, 47(5): 14-21.
[9] WANG Ya-hui, LIU Bo, YUAN Xiao-tong. Distributed Convolutional Neural Networks Based on Approximate Newton-type Mothod [J]. Computer Science, 2019, 46(7): 180-185.
[10] DONG Ming-gang,LIU Bao,JING Chao. Multi-objective Differential Evolution Algorithm with Fuzzy Adaptive Ranking-based Mutation [J]. Computer Science, 2019, 46(7): 224-232.
[11] YU Jian-jun, WU Chun-ming. Offline Static Virtual Network Mapping Algorithm Based on Tabu Search Genetic Optimization [J]. Computer Science, 2019, 46(12): 114-119.
[12] LAI Wen-xing, DENG Zhong-min. Improved NSGA2 Algorithm Based on Dominant Strength [J]. Computer Science, 2018, 45(6): 187-192.
[13] DING Shu-yang, LI Bing and SHI Hong-bo. Study on Flexible Job-shop Scheduling Problem Based on Improved Discrete Particle Swarm Optimization Algorithm [J]. Computer Science, 2018, 45(4): 233-239.
[14] WANG Ming, ZHUANG Lei, WANG Guo-qing, ZHANG Kun-li. Virtual Network Mapping Algorithm Based on Cellular Genetic Mechanism [J]. Computer Science, 2018, 45(12): 66-70.
[15] XIE Yong-hao, GAO Song-feng and DAI Ming-zhu. Virtual Network Mapping Optimization Based on Improved Ant Colony Algorithm [J]. Computer Science, 2017, 44(Z6): 312-313.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.