计算机科学 ›› 2019, Vol. 46 ›› Issue (12): 114-119.doi: 10.11896/jsjkx.181001981
余建军1, 吴春明2
YU Jian-jun1, WU Chun-ming2
摘要: 离线静态虚拟网映射问题是NP难问题,其任务是以物理网提供商收益最大化为目标,在物理网上完成虚拟网子集的映射。文中对离线静态虚拟网映射问题及其研究现状进行介绍,指出当前离线静态虚拟网映射算法仅适用于小规模问题或特殊问题的求解,进而提出了一种适用于中大规模的一般离线静态虚拟网映射问题的求解算法。首先,基于收益优先的虚拟网映射顺序策略、节点等级匹配的虚拟节点映射策略以及最小化资源消耗量的虚拟链路映射策略,提出离线静态虚拟网映射问题的贪婪算法;然后,基于遗传算法和禁忌搜索混合的优化策略,提出离线静态虚拟网映射问题的禁忌遗传算法。实验表明,所提出的禁忌遗传算法具有较高的虚拟网构建完成率和物理网提供商收益,虚拟网构建完成率和物理网提供商收益分别比基线算法提高了34%和42%。
中图分类号:
[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. |
|