基于最小生成树的vSDN故障快速恢复算法

doi:10.11896/jsjkx.211200034

摘要/Abstract

摘要： 针对虚拟软件定义网络的故障恢复问题,提出了基于最小生成树的虚拟软件定义网络故障恢复算法,以期解决虚拟软件定义网络故障恢复时间长这一难点。该算法一方面是根据节点与链路的资源和拓扑属性,设定节点与链路重要度,并据此对节点与链路进行等级划分;在此基础上,针对不同的物理网络,调整备份与迁移的比例,从而在提升请求接受率的同时减少故障后的完全恢复时间,达成对物理网络资源的充分利用;另一方面是对虚拟网络进行连通性分析,运用最小生成树算法优先恢复虚拟网络的连通性,然后完成剩余链路的故障恢复,在保障虚拟网络连通性的基础上进一步减少故障恢复时间。仿真实验表明,该算法能在保障较高虚拟网络请求接受率与故障恢复率的基础上,缩减故障恢复时间。

关键词: 网络虚拟化, 虚拟软件定义网络, 故障恢复, 连通性, 最小生成树

Abstract: Aiming at the problem of fault recovery of virtual software-defined network,a fault recovery algorithm of virtual software-defined network based on minimum spanning tree is proposed to solve the difficulty of long recovery time of virtual software-defined network.On the one hand,the algorithm sets the importance of nodes and links according to the resources and topological attributes of nodes and links,and classifies nodes and links accordingly.On this basis,according to different physical networks,adjusting the ratio of backup and migration,improving the request acceptance rate and reducing the full recovery time after failure,so as to make full use of physical network resources.On the other hand,it analyzes the connectivity of virtual network,and uses the minimum spanning tree algorithm to restore the connectivity of virtual network first,and then completes the fault recovery of the remaining links,further reducing the fault recovery time on the basis of ensuring the connectivity of virtual network.Simulation results show that the algorithm can reduce the recovery time of virtual network on the basis of ensuring high request acceptance rate and recovery rate.

Key words: Network virtualization, Virtual software-defined network, Failure recovery, Connectivity, Minimum spanning tree

中图分类号:

TP393

陈港, 孟相如, 康巧燕, 翟东. 基于最小生成树的vSDN故障快速恢复算法[J]. 计算机科学, 2022, 49(11A): 211200034-7. https://doi.org/10.11896/jsjkx.211200034

CHEN Gang, MENG Xiang-ru, KANG Qiao-yan, ZHAI Dong. vSDN Fault Recovery Algorithm Based on Minimum Spanning Tree[J]. Computer Science, 2022, 49(11A): 211200034-7. https://doi.org/10.11896/jsjkx.211200034

参考文献

[1]LI Q,LIN Y,ZHU Z J,et al.BOND:Flexible Failure Recovery in Software Defined Networks[J].Computer Networks,2018,149:1-12.
[2]LIU X R.Research on Virtual Network Mapping Strategy based on survivability [D].Beijing:Beijing University of Posts and Telecommunications,2018.
[3]SUN G,YU H,LI L,et al.Efficient algorithms for survivable virtual network embedding[C]//Asia Communications and Photonics Conference and Exhibition.2010:531-532.
[4]GHALEB A M,KHALIFA T,SHABAN K B.Enhancing theperformance of post-failure restoration schemes in multi-tenant networks[C]//2016 12th International Conference on Network and Service Management (CNSM).2016:359-362.
[5]SWARNA D B,MUTHUMANIKANDAN V.Nested FailureDetection and Recovery in Software Defined Networks[C]//2019 IEEE International Conference on Electrical,Computer and Communication Technologies (ICECCT).2019:1-6.
[6]HE F,SATO T,OKI E.Master and Slave Controller Assignment Model Against Multiple Failures in Software Defined Network[C]//2019 IEEE International Conference on Communications(ICC 2019).2019:1-6.
[7]KIM W,HONG J W,SUH Y.T-DCORAL:A Threshold-Based Dynamic Controller Resource Allocation for Elastic Control Plane in Software-Defined Data Center Networks[C]//IEEE Communications Letters.2019:198-201.
[8]ALOWA A,FEVENS T.A Dynamic Recovery Module for In-band Control Channel Failure In Software Defined Networking[C]//2020 6th IEEE Conference on Network Software Virtua-lization(NetSoft).2020:209-217.
[9]YANG K,ZHANG B,GUO D,et al.Partitioned ControllerPlacement in SDWANs for Reliability Maximization with Latency Constraints[C]//2019 IEEE Globecom Workshops (GC Wkshps).2019:1-6.
[10]CHEN S,SUN W,HU W.On Dynamic Hypervisor Placement in Virtualized Software Defined Networks (vSDNs)[C]//2020 22nd International Conference on Transparent Optical Networks (ICTON).2020:1-5.
[11]BLENK A,BASTA A,ZERWAS J,et al.Pairing SDN with network virtualization:The network hypervisor placement problem[C]//2015 IEEE Conference on Network Function Virtualization and Software Defined Network (NFV-SDN).2015:198-204.
[12]XIE F,MENG X R,MENG Q W,et al.Virtual network reconfiguration algorithm based on dynamic path splitting [J].Fire & Command Control,2019,44(11):29-34,40.
[13]SANDHU A K,SINGH BATTH R,NAGPAL A.ImprovedQoS Using Novel Fault Tolerant Shortest Path Algorithm in Virtual Software Defined Network (VSDN)[C]//2019 International Conference on Automation,Computational and Techno-logy Management(ICACTM).2019:383-388.
[14]RAN J P,ZHAO S H,WANG X,et al.Survivability virtual network mapping algorithm for SDN [J].Systems Engineering and Electronics,2020,42(5):1182-1189.
[15]ZHAO J H,WU D D,QU Y,et al.Reliability virtual network mapping guarantee mechanism based on software-defined network [J].Computer Applications,2020,40(3):770-776.
[16]LI R,ZHANG J,TAN Y,et al.An enhanced virtual cluster embedding strategy with virtualized SDN[C]//2017 IEEE 9th International Conference on Communication Software and Networks (ICCSN).2017:974-981.
[17]LI R,ZHANG J,TAN Y,et al.Topology-aware VSDN embedding approach on shared software defined networks[C]//2016 5th International Conference on Computer Science and Network Technology (ICCSNT).2016:455-460.
[18]REN Z M.Research progress of node influence in dynamic complex networks [J].Acta Physica Sinica,2020,69(4):24-32.
[19]LIU Y Y,LI L J,SHAN N,et al.Link prediction method based on fusion aggregation coefficient[J].Computer Applications,2020,40(1):28-35.
[20]LIU S Q.Research on Similarity Measurement of NetworkNodes Based on Relative Entropy [D].Taiyuan:Shanxi University,2020.
[21]LI F,MA J Z,ZHU P C,et al.Review of reliability evaluation methods for complex network [J].Measurement & Control Technology,2017,36(4):1-5,10.
[22]WANG Z X,JIANG D L,QI L,et al.Complex Network Invulnerability and Node Importance Evaluaction Model Based on Redundancy[J].Complex Systems and Complexity Science,2020,17(3):78-85.

相关文章 15

[1]	朱国晖, 张茵, 刘秀霞, 孙天骜. 节点拓扑感知的高效节能虚拟网络映射算法 Energy Efficient Virtual Network Mapping Algorithms Based on Node Topology Awareness 计算机科学, 2020, 47(9): 270-274. https://doi.org/10.11896/jsjkx.190700162
[2]	李振涛, 孟相如, 赵志远, 苏玉泽. 一种面向节点负载均衡的虚拟网络重构算法 Virtual Network Reconfiguration Algorithm for Nodes Load Balancing 计算机科学, 2018, 45(7): 95-98. https://doi.org/10.11896／j.issn.1002-137X.2018.07.015
[3]	徐涛,杜昱萱,吕宗磊. 基于线性规划的传感器节点布局模型 Sensor Node Deployment Model Based on Linear Programming 计算机科学, 2018, 45(7): 110-115. https://doi.org/10.11896／j.issn.1002-137X.2018.07.018
[4]	秦梦娜, 陈俊杰, 郭浩. 基于高阶最小生成树脑网络的多特征融合分类方法 Multi-feature Fusion Classification Method Based on High-order Minimum Spanning Tree Brain Network 计算机科学, 2018, 45(7): 293-298. https://doi.org/10.11896／j.issn.1002-137X.2018.07.050
[5]	洪睿, 康晓东, 李博, 王亚鸽. 一种基于复杂网络的图像形状及纹理描述方法 Image Shape and Texture Description Method Based on Complex Network 计算机科学, 2018, 45(11A): 244-246.
[6]	吴果,房礼国,徐晓辉. 基于网络收缩的节点可复用虚拟网络映射算法 Node Reusable Virtual Network Embedding Algorithm Based on Network Shrinking 计算机科学, 2017, 44(6): 91-93. https://doi.org/10.11896/j.issn.1002-137X.2017.06.015
[7]	张芳,邓畅霖,王之,郭薇. 软件定义卫星网络的链路故障检测和恢复方案 Link Failure Detection and Fast Recovery in Software-defined Satellite Network 计算机科学, 2017, 44(6): 63-67. https://doi.org/10.11896/j.issn.1002-137X.2017.06.010
[8]	朱庆生,段浪军,杨力军. 基于自然邻居和最小生成树的原型选择算法 Prototype Selection Algorithm Based on Natural Neighbor and MST 计算机科学, 2017, 44(4): 241-245. https://doi.org/10.11896/j.issn.1002-137X.2017.04.051
[9]	郭贺彬. 基于虚拟网节点迁移的虚拟网映射优化算法 Virtual Network Mapping Optimization Algorithm Based on Virtual Network Node Migration 计算机科学, 2014, 41(Z11): 224-227.
[10]	陈铎龙,孟相如,梁霄,袁荣坤. 基于免疫原理的多拓扑路由生成算法 Multi-topology Routing Generation Algorithm Based on Immune Mechanism 计算机科学, 2014, 41(1): 212-216.
[11]	刘宴涛,汪博,安建平,刘珩. 采用随机移动模型的无线自组织仿真网络连通性分析 Analysis to Connectivity of Wireless Ad hoc Simulating Networks with Random Mobility Models 计算机科学, 2013, 40(Z6): 287-290.
[12]	袁关伟，赵家刚. 基于“断弦护枝”思想的MST构造算法的设计与分析 Design and Analysis of MST Constructing Algorithm Based on the Idea that is Named as Pruning Bowstrings and Protecting Branches 计算机科学, 2012, 39(Z6): 437-440.
[13]	尹栋，慕德俊，戴冠中. 用户模式下虚拟路由器的优化 Optimized User Mode Virtual Router 计算机科学, 2011, 38(8): 38-41.
[14]	李燕君,朱艺华. 衰落信道下无线多跳网络的连通性研究 Connectivity of Wireless Multi-hop Networks under Fading Channel 计算机科学, 2011, 38(3): 93-96.
[15]	侯孟书,李玉军,卢显良,屈鸿,任立勇. 动态频谱访问无线网络的连通性分析 On the Connectivity Analysis over Dynamic Spectrum Access Networks 计算机科学, 2010, 37(7): 62-65.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed