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

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)
[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)
[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)
[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)
[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)
[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)
[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)
[13]ANDERSEN D.Theoretical approaches to node assignment [EB/OL].,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)
[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)
[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)
[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)
[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)
[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)
[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.
Full text



No Suggested Reading articles found!