面向多链路故障的生存性虚拟网络映射算法

doi:10.19678/j.issn.1000-3428.0055914

摘要/Abstract

摘要： 针对物理网络发生多链路故障情况下的虚拟网络映射问题，提出一种生存性虚拟网络映射算法。该算法为物理链路提供备份资源，并采用多路径选择算法创建备份路由集合。根据目标函数求解整数线性规划，从故障链路备份路由集中选择带宽资源平衡度最大的路径，为受链路故障影响的虚拟链路进行重映射。仿真结果表明，该算法可有效缩短故障恢复时延，提高长期平均收益开销比与平均故障恢复率。

关键词: 生存性虚拟网络映射, 多链路故障, 链路重映射, 平均故障恢复率, 故障恢复时延

Abstract: To address the Virtual Network Embedding(VNE) problem in the case of multiple link failures in physical networks,this paper proposes a Survivable Virtual Network Embedding(SVNE) algorithm.This algorithm provides backup resources for physical links and uses a multiple path selection algorithm to create a backup route set.According to the objective function,the integer linear programming is solved.The path with the largest bandwidth resource balance is selected from the backup route set of the failed link to implement re-embedding for the virtual links that are affected by the link failure.Simulation results show that the proposed algorithm can effectively shorten the failure recovery delay,and improve the long-term average revenue-to-expense ratio and average failure recovery rate.

Key words: Survivable Virtual Network Embedding(SVNE), multiple link failure, link re-embedding, average failure recovery rate, failure recovery delay

中图分类号:

TP393.01

朱国晖, 刘秀霞, 张茵. 面向多链路故障的生存性虚拟网络映射算法[J]. 计算机工程, 2020, 46(10): 182-187,192.

ZHU Guohui, LIU Xiuxia, ZHANG Yin. Survivable Virtual Network Embedding Algorithm for Multiple Link Failures[J]. Computer Engineering, 2020, 46(10): 182-187,192.

http://www.ecice06.com/CN/Y2020/V46/I10/182

图/表 8

20201023092817

20201023092837

20201023092840

20201023092844

20201023092847

20201023092850

20201023092853

20201023092856

参考文献

[1] SONG Xue.Research on resource allocation mechanism of network function virtualization[D].Chengdu:University of Electronic Science and Technology of China,2018.(in Chinese) 宋雪.网络功能虚拟化的资源分配机制研究[D].成都:电子科技大学,2018.
[2] GUO Kailing.Virtual network resource allocation method based on application layer demand[D].Beijing:Beijing University of Posts and Telecommunications,2016.(in Chinese) 郭凯玲.基于应用层需求的虚拟网络资源分配方法[D].北京:北京邮电大学,2016.
[3] GONG Shuiqing,CHEN Jing,WANG Wei.Energy-aware virtual network embedding algorithm for heterogeneous nodes[J].Journal of Electronics & Information Technology,2015,37(8):2021-2027.(in Chinese) 龚水清,陈靖,王崴.面向节点异构的能耗感知虚拟网络映射算法[J].电子与信息学报,2015,37(8):2021-2027.
[4] ZHOU Zibo.Research on virtual network mapping algorithm for Google cloud dataset[D].Beijing:Beijing Jiaotong University,2018.(in Chinese) 周子博.面向谷歌云数据集的虚拟网络映射算法研究[D].北京:北京交通大学,2018.
[5] ZHU Qiang,WANG Huiqiang,MA Chunguang,et al.Reliable heuristic mapping method for survivable virtual network[J].Journal on Communications,2015,36(7):109-119.(in Chinese) 朱强,王慧强,马春光,等.虚拟网络可生存的启发式可靠映射算法[J].通信学报,2015,36(7):109-119.
[6] HUANG Liping,YANG Longxiang.A survey on survivable virtual network embedding algorithm[J].Computer Technology and Development,2018,28(7):144-148.(in Chinese) 黄丽萍,杨龙祥.可生存性虚拟网络映射算法的研究[J].计算机技术与发展,2018,28(7):144-148.
[7] CHEN Zhenhua.Research on virtual network mapping model and optimization algorithm based on energy perception[D].Jinan:Shandong Normal University,2016.(in Chinese) 陈振华.基于能耗感知的虚拟网络映射模型与优化算法研究[D].济南:山东师范大学,2016.
[8] RAHMAN M R,AIB I,BOUTABA R.Survivable virtual network embedding[M].Berlin,Germany:Springer,2010:40-52.
[9] RAHMAN M R,BOUTABA R.SVNE:survivable virtual network embedding algorithms for network virtualization[J].IEEE Transactions on Network and Service Management,2013,10(2):105-118.
[10] GUO Bingli,QIAO Chunming,WANG Jianping,et al.Survivable virtual network design and embedding to survive a facility node failure[J].Journal of Lightwave Technology,2014,32(3):483-493.
[11] SU Yuze,MENG Xiangru,KANG Qiaoyan,et al.Survivable virtual network link protection method based on network coding and protection circuit[J].IEEE Access,2018,6:67477-67493.
[12] AI Jianjian,CHEN Hongchang,GUO Zehua,et al.Defending against link failure in virtual network embedding using a hybrid scheme[J].China Communications,2019,16(1):135-144.
[13] XIAO Xiancui.Research on mapping model and algorithm of survivability virtual network[D].Jinan:Shandong Normal University,2017.(in Chinese) 肖宪翠.可生存性虚拟网络映射模型及算法研究[D].济南:山东师范大学,2017.
[14] WANG Zhiming,WU Jiangxing,WANG Yu,et al.Survivable virtual network mapping using optimal backup topology in virtualized SDN[J].China Communications,2014,11(2):26-37.
[15] QIANG Zhu,QIANG Wanghui,SHENG Fengguang,et al.Heuristic survivable virtual network embedding based on node migration and link remapping[C]// Proceedings of the 7th Joint International Information Technology and Artificial Intelligence Conference.Washington D.C.,USA:IEEE Press,2014:181-185.
[16] ZHANG S M,SANGAIAH A K.Reliable design for virtual network requests with location constraints in edge-of-things computing[J].EURASIP Journal on Wireless Communications and Networking,2018,2018:1-10.
[17] LIU Xiangru.Research on virtual network mapping strategy based on survivability[D].Beijing:Beijing University of Posts and Telecommunications,2018.(in Chinese)刘祥如.基于可生存性的虚拟网络映射策略的研究[D].北京:北京邮电大学,2018.
[18] LIU Xinbo,WANG Buhong,LIU Shuaiqi,et al.Heuristic algorithm for secure virtual network embedding[J].Systems Engineering and Electronics,2018,40(3):676-681.(in Chinese)刘新波,王布宏,刘帅琦,等.安全虚拟网络映射的启发式算法[J].系统工程与电子技术,2018,40(3):676-681.
[19] ZHU Guohui,KANG Xiaoxuan,LEI Lanjie.Virtual network mapping algorithm based on optimal subnet[J].Computer Engineering,2019,45(10):8-12.(in Chinese)朱国晖,康潇轩,雷兰洁.基于最优子网的虚拟网络映射算法[J].计算机工程,2019,45(10):8-12.
[20] GAO Fei,CHEN Deli,HONG Jiajun,et al.Virtual network mapping mechanism based on k shortest path algorithm optimization and load balance[J].Computer Engineering,2018,44(5):146-154.(in Chinese)高斐,陈德礼,洪家军,等.基于k最短路径算法优化与负载均衡的虚拟网络映射机制[J].计算机工程,2018,44(5):146-154.
[21] LU Meilian,GU Yun,LIU Tong.SDN-ScaSVNE:scalable survivable virtual network embedding algorithm in SDN[J].Journal of Beijing University of Posts and Telecommunications,2018,41(3):75-80.(in Chinese)卢美莲,顾云,刘通.SDN-ScaSVNE:可伸缩的SDN生存性虚拟网络映射算法[J].北京邮电大学学报,2018,41(3):75-80.
[22] LU Bo,HUANG Tao,SUN Xiaochuan,et al.Dynamic recovery for survivable virtual network embedding[J].The Journal of China Universities of Posts and Telecommunications,2014,21(3):77-84.

选择文件类型/文献管理软件名称

选择包含的内容