计算机科学 ›› 2019, Vol. 46 ›› Issue (12): 114-119.doi: 10.11896/jsjkx.181001981

• 网络与通信 • 上一篇    下一篇

基于禁忌遗传优化的离线静态虚拟网映射算法

余建军1, 吴春明2   

  1. (衢州职业技术学院 浙江 衢州324000)1;
    (浙江大学计算机科学与技术学院 杭州310027)2
  • 收稿日期:2018-10-25 出版日期:2019-12-15 发布日期:2019-12-17
  • 通讯作者: 余建军(1969-),男,硕士,教授,主要研究方向为网络虚拟化技术以及算法设计与分析,E-mail:yjj691121@126.com。
  • 作者简介:吴春明(1967-),男,博士,教授,主要研究方向为互联网体系结构、柔性可重构网络、网络资源弹性管控与虚拟化、网络试验床、网络安全主动防御等。
  • 基金资助:
    本文受浙江省自然科学基金资助项目(LY14F020010),国家863高技术研究发展计划项目(2015AA015602,2015AA016013)资助。

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

摘要: 离线静态虚拟网映射问题是NP难问题,其任务是以物理网提供商收益最大化为目标,在物理网上完成虚拟网子集的映射。文中对离线静态虚拟网映射问题及其研究现状进行介绍,指出当前离线静态虚拟网映射算法仅适用于小规模问题或特殊问题的求解,进而提出了一种适用于中大规模的一般离线静态虚拟网映射问题的求解算法。首先,基于收益优先的虚拟网映射顺序策略、节点等级匹配的虚拟节点映射策略以及最小化资源消耗量的虚拟链路映射策略,提出离线静态虚拟网映射问题的贪婪算法;然后,基于遗传算法和禁忌搜索混合的优化策略,提出离线静态虚拟网映射问题的禁忌遗传算法。实验表明,所提出的禁忌遗传算法具有较高的虚拟网构建完成率和物理网提供商收益,虚拟网构建完成率和物理网提供商收益分别比基线算法提高了34%和42%。

关键词: NP难问题, 禁忌遗传算法, 离线虚拟网映射, 贪婪算法

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

中图分类号: 

  • 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] 孙志强, 万良, 丁红卫.
基于深度自编码网络的Android恶意软件检测方法
Android Malware Detection Method Based on Deep Autoencoder Network
计算机科学, 2020, 47(4): 298-304. https://doi.org/10.11896/jsjkx.190700132
[2] 廖勇, 杨馨怡, 夏茂菡, 王博, 李守智, 沈轩帆.
高速移动场景下基于贪婪算法的改进模代数预编码
Improved Tomlinson-Harashima Precoding Based on Greedy Algorithm in High-speed Mobile Scenarios
计算机科学, 2019, 46(8): 121-126. https://doi.org/10.11896/j.issn.1002-137X.2019.08.020
[3] 郑斐峰, 蒋娟, 梅启煌.
最小化集装箱运输成本的配载优化
Study on Stowage Optimization in Minimum Container Transportation Cost
计算机科学, 2019, 46(6): 239-245. https://doi.org/10.11896/j.issn.1002-137X.2019.06.036
[4] 杜秀丽,顾斌斌,胡兴,邱少明,陈波.
用于图像重构的基于行间支撑集相似度的CoSaMP算法
Support Similarity between Lines Based CoSaMP Algorithm for Image Reconstruction
计算机科学, 2018, 45(4): 306-311. https://doi.org/10.11896/j.issn.1002-137X.2018.04.052
[5] 余建军, 吴春明.
虚拟网映射问题的计算复杂性分析
Computational Complexity Analysis of Virtual Network Mapping Problem
计算机科学, 2018, 45(11): 87-91. https://doi.org/10.11896/j.issn.1002-137X.2018.11.012
[6] 魏霖静,练智超,王联国,侯振兴.
基于词条与语意差异度量的文档聚类算法
Term and Semantic Difference Metric Based Document Clustering Algorithm
计算机科学, 2016, 43(12): 229-233. https://doi.org/10.11896/j.issn.1002-137X.2016.12.042
[7] 刘 梓,宋晓宁,唐振民.
整合原始人脸图像和其虚拟样本的人脸分类算法
Integrating Original Images and its Virtual Samples for Face Recognition
计算机科学, 2015, 42(5): 289-294. https://doi.org/10.11896/j.issn.1002-137X.2015.05.059
[8] 蔡旭,谢正光,蒋小燕,黄宏伟.
基于压缩感知的步长自适应前向后向追踪重建算法
Adaptive Step Length Forward-backward Pursuit Algorithm for Signal Reconstruction Based on Compressed Sensing
计算机科学, 2014, 41(11): 169-174. https://doi.org/10.11896/j.issn.1002-137X.2014.11.033
[9] 杨云,章国安,邱恭安.
认知无线Mesh网络中基于概率的贪婪频谱决策技术研究
Research of Probability-based Greedy Spectrum Decision in Cognitive Wireless Mesh Networks
计算机科学, 2012, 39(Z6): 163-165.
[10] 周伟 王建新 谢民主 陈建二.
单体型组装问题计算模型的比较与分析

计算机科学, 2008, 35(11): 166-169.
[11] 刘云龙 王建新 陈建二.
彩色编码技术的研究进展及应用

计算机科学, 2008, 35(1): 15-18.
[12] 马振宇 王建新 冯启龙 陈建二.
Set Packing问题的研究进展

计算机科学, 2007, 34(9): 12-15.
[13] 李庆华 潘军 李肯立.
背包问题的二分网格算法

计算机科学, 2005, 32(6): 217-220.
[14] 龚卫华 王元珍.
基于三角环的顶点着色问题解法

计算机科学, 2005, 32(4): 77-78.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!