基于软件定义网络的高故障保护率的路由保护方案  

Routing Protection Scheme with High Failure Protection Ratio Based on Software-defined Network

作　　者：耿海军 王威[1,3] 张晗 王玲 GENG Haijun;WANG Wei;ZHANG Han;WANG Ling(School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China;School of Automation and Software Engineering,Shanxi University,Taiyuan 030006,China;Institute of Big Data Science and Industry,Shanxi University,Taiyuan 030006,China;Department of Computer Science Technology,Tsinghua University,Beijing 100084,China)

机构地区：[1]山西大学计算机与信息技术学院,太原030006 [2]山西大学自动化与软件学院,太原030006 [3]山西大学大数据科学与产业研究院,太原030006 [4]清华大学计算机科学与技术系,北京100084

出　　处：《计算机科学》2023年第9期337-346,共10页Computer Science

基　　金：山西省应用基础研究计划(20210302123444);山西省高等学校科技创新项目(2022L002);中国高校产学研创新基金(2021FNA02009);国家自然科学基金(61702315);山西省重点研发计划(201903D421003,202202020101004);国家高技术研究发展计划(863)(2018YFB1800401)。

摘　　要：软件定义网络(Software Defined Network,SDN)以其强大的可编程性和集中控制的优势得到了学术界的广泛关注。现有的SDN设备在执行报文转发时仍然使用最短路径协议,当最短路径中的结点发生故障时,网络仍然需要重新收敛,在此期间报文可能会被丢弃,进而无法传递至目的结点,给实时性应用的流畅性造成了冲击,影响用户体验。学术界普遍采用路由保护的方案来应对网络故障,现有的路由保护方案存在以下两个方面的问题:(1)故障保护率低;(2)当网络出现故障时,备份路径可能会出现路由环路。为了解决上述两个问题,首先提出了备份下一跳计算规则;然后基于此规则设计了一种软件定义网络下的高故障保护率的路由保护算法(Routing Protection Algorithm with High Failure Protection Ratio,RPAHFPR),该算法融合了路径生成算法(Path Generation Algorithm,PGA)、旁支优先算法(Side Branch First Algorithm,SBF)和环路规避算法(Loop Avoidance Algorithm,LAA),可以同时解决已有路由保护方法面临的故障保护率低和路由环路问题;最后在大量的真实网络拓扑和模拟网络拓扑中验证了RPAHFPR方案的性能。与经典的NPC和U-TURN相比,RPAHFPR的故障保护率分别提高了20.85%和11.88%,并且在86.3%的拓扑中可以达到100%的故障保护率,在所有拓扑中可以达到99%以上的故障保护率。RPAHFPR的路径拉伸度基本接近1,不会引入过多的时间延迟。SDN has attracted extensive attention from academia for its advantages of strong programmability and centralized control.Existing SDN devices still use the shortest path protocol when performing packet forwarding.When a node in the shortest path fails,the network re-convergence is still required.During this period,packets may be discarded and thus cannot be delivered to the destination node,which has an impact on the flow of real-time applications and affects the user experience.The academia generally adopts the routing protection schemes to deal with network failures.The existing routing protection schemes have the following two problems:(1)the failure protection ratio is low;(2)when the network fails,the backup path may have routing loops.In order to solve the above two problems,a backup next hop calculation rule is proposed.Then,based on this rule,a routing protection algorithm with high hailure protection ratio(RPAHFPR)is designed,which combines the path generation algorithm(PGA),side branch first algorithm(SBF)and loop avoidance algorithm(LAA).It can simultaneously solve the low failure protection rate and routing loop problems faced by existing routing protection methods.Finally,the performance of RPAHFPR scheme is verified in a large number of real network topologies and simulated network topologies.Compared with the classic NPC and U-TURN,the failure protection rate of RPAHFPR is increased by 20.85%and 11.88%respectively,and it can achieve 100%fai-lure protection rate in 86.3%topology,and more than 99%failure protection rate in all topology.The path stretching degree of RPAHFPR is basically close to 1,without introducing too much time delay.

关 键 词：软件定义网络 路由保护算法 反向最短路径树 LFA规则 备份路径 网络单故障 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]