Computer Science ›› 2019, Vol. 46 ›› Issue (12): 114-119.doi: 10.11896/jsjkx.181001981

• Network & Communication • Previous Articles     Next Articles

Offline Static Virtual Network Mapping Algorithm Based on Tabu Search Genetic Optimization

YU Jian-jun1, WU Chun-ming2   

  1. (Quzhou College of Technology,Quzhou,Zhejiang 324000,China)1;
    (College of Computer Science and Technology,Zhejiang University,Hangzhou 310027,China)2
  • Received:2018-10-25 Online:2019-12-15 Published:2019-12-17

Abstract: The offline static virtual network mapping problem is an NP-hard problem.It is to map the subset of virtual networks onto the physical network aimed to maximize the profit of physical network provider.This paper reviewed the offline static virtual network mapping problem and the current research progress for this problem and pointed out that the current offline static virtual network mapping algorithm is only suitable for solving small-scale problems or special problems.Therefore,this paper proposed a general offline static virtual network mapping algorithm suitable for solving medium and large scale.The virtual network mapping order strategy based on revenue priority,the virtual node mapping strategy by node rank matching and the virtual link mapping strategy that minimizes resource consumption are used to complete the greedy algorithm design for offline static virtual network mapping problem.Then,the optimization strategy based on the hybrid algorithm of genetic algorithm and tabu search are used to complete the tabu search genetic algorithm design for offline static virtual network mapping problem.Experiments show that the proposed algorithm has higher virtual network construction completion rate and gets better physical network provider revenue,and the virtual network construction completion rate and physical network provider revenue are 34% and 42% higher than the baseline algorithm,respectively.

Key words: Greedy algorithm, NP-hard problem, Offline virtual network mapping, Tabu search genetic algorithm

CLC Number: 

  • TP393
[1]CHOWDHURY N M M K,BOUTABA R.A survey of network virtualization[J].Computer Networks,2010,54(5):862-876.
[2]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.
[3]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.
[4]余建军.虚拟网映射问题及算法研究[M].杭州:浙江大学出版社,2018.
[5]YU J J,WU C M.Computational Complexity Analysis of Virtual Network Mapping Problem[J].Computer Science,2018,45(11):87-91.(in Chinese)
余建军,吴春明.虚拟网映射问题的计算复杂性分析[J].计算机科学,2018,45(11):87-91.
[6]AMALDI E,CONIGLIO S,KOSTER A M C A, et al.On the computational complexity of the virtual network embedding problem[J].Electronic Notes in Discrete Mathematics,2016,52(3):213-220.
[7]ROST M,SCHMID S.Charting the Complexity Landscape of Virtual Network Embeddings[C]//Proceedings IFIP Networking.Zurich,Switzerland,2018:1-9.
[8]ZHANG Z,SU S,ZHANG J,et al.Energy aware virtual net- work embedding with dynamic demands:Online and offline [J].Computer Networks,2015,93(P3):448-459.
[9]CONIGLIO S,KOSTER A,TIEVES M.Data Uncertainty in Virtual Network Embedding:Robust Optimization and Protection Levels[J].Journal of Network & Systems Management,2016,24(3):681-710.
[10]CONIGLIO S,GRIMM B,KOSTER A M C A,et al.Optimal offline virtual network embedding with rent-at-bulk aspects[J].Computer Science,2015,14(2):1-9.
[11]ROST M,SCHMID S.(FPT-) Approximation Algorithms for the Virtual Network Embedding Problem[EB/OL].(2018-03-12)[2018-10-25].https://arxiv.org/abs/1803.04452.
[12]KATOH N,IBARAKI T,MINE H.An efficient algorithm for K shortest simple paths[J].Networks,1982,12(4):411-427.
[13]CHENG X,SU S,ZHANG Z,et al.Virtual network embedding through topology-aware node ranking[J].ACM SIGCOMM Computer Communication Review,2011,41(2):38-47.
[14]GLOVER F,KELLY J P,LAGUNA M.Genetic algorithms and tabu search:Hybrids for optimization[J].Computers & Operations Research,1995,22(1):111-134.
[15]周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.
[16]CHOWDHURY M,RAHMAN M R,BOUTABA R.ViNE- Yard:virtual network embedding algorithms with coordinated node and link mapping[J].IEEE/ACM Transactions on Networking,2012,20(1):206-219.
[17]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.
[18]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.
[1] ZHANG Chong-yu, CHEN Yan-ming, LI Wei. Task Offloading Online Algorithm for Data Stream Edge Computing [J]. Computer Science, 2022, 49(7): 263-270.
[2] LIU Zhang-hui, ZHENG Hong-qiang, ZHANG Jian-shan, CHEN Zhe-yi. Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems [J]. Computer Science, 2022, 49(6A): 619-627.
[3] ZHANG Xin-ming, LI Shuang-qian, LIU Yan, MAO Wen-tao, LIU Shang-wang, LIU Guo-qi. Coyote Optimization Algorithm Based on Information Sharing and Static Greed Selection [J]. Computer Science, 2020, 47(5): 217-224.
[4] SUN Zhi-qiang, WAN Liang, DING Hong-wei. Android Malware Detection Method Based on Deep Autoencoder Network [J]. Computer Science, 2020, 47(4): 298-304.
[5] HU Jun-qin, ZHANG Jia-jun, HUANG Yin-hao, CHEN Xing, LIN Bing. Computation Offloading Scheduling Technology for DNN Applications in Edge Environment [J]. Computer Science, 2020, 47(10): 247-255.
[6] LIAO Yong, YANG Xin-yi, XIA Mao-han, WANG Bo, LI Shou-zhi, SHEN Xuan-fan. Improved Tomlinson-Harashima Precoding Based on Greedy Algorithm in High-speed Mobile Scenarios [J]. Computer Science, 2019, 46(8): 121-126.
[7] ZHENG Fei-feng, JIANG Juan, MEI Qi-huang. Study on Stowage Optimization in Minimum Container Transportation Cost [J]. Computer Science, 2019, 46(6): 239-245.
[8] LI Zhuo, XU Zhe, CHEN Xin, LI Shu-qin. Location-related Online Multi-task Assignment Algorithm for Mobile Crowd Sensing [J]. Computer Science, 2019, 46(6): 102-106.
[9] CHEN Jin-yin, HU Ke-ke,LI Yu-wei. Research on UAV Multi-point Navigation Algorithm Based on MB-RRT* [J]. Computer Science, 2018, 45(6A): 85-90.
[10] ZHU Rui-chao,QIAN Wen-hua,PU Yuan-yuan, XU Dan. Texture Synthesis Based on Self-similarity Matching [J]. Computer Science, 2018, 45(6A): 215-219.
[11] HU Qing-cheng, ZHANG Yong, XING Chun-xiao. K-clique Heuristic Algorithm for Influence Maximization in Social Network [J]. Computer Science, 2018, 45(6): 32-35.
[12] DU Xiu-li, GU Bin-bin, HU Xing, QIU Shao-ming and CHEN Bo. Support Similarity between Lines Based CoSaMP Algorithm for Image Reconstruction [J]. Computer Science, 2018, 45(4): 306-311.
[13] YU Jian-jun, WU Chun-ming. Computational Complexity Analysis of Virtual Network Mapping Problem [J]. Computer Science, 2018, 45(11): 87-91.
[14] SUN Tao and ZHU Xiao-ming. Computing Longest Common Subsequences Approximately Based on Lattice [J]. Computer Science, 2017, 44(2): 270-274.
[15] CAI Guo-yong and PEI Guang-zhan. Influence Maximization Based on LT+ Model in Social Networks [J]. Computer Science, 2016, 43(9): 99-102.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!