基于最短路径序列化图的域内路由保护算法  

Intra-domain Routing Protection Algorithm Based on Shortest Path Serialization Graph

作　　者：耿海军[1,2] 胡睿乾 胡治国 尹霞[4] GENG Hai-Jun;HU Rui-Qian;HU Zhi-Guo;YIN Xia(School of Automation and Software Engineering,Shanxi University,Taiyuan 030006,China;School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China;The Key Laboratory of Embedded System and Service Computing(Tongji University),Ministry of Education,Shanghai 200092,China;Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China)

机构地区：[1]山西大学自动化与软件学院,山西太原030006 [2]山西大学计算机与信息技术学院,山西太原030006 [3]嵌入式系统与服务计算教育部重点实验室(同济大学),上海200092 [4]清华大学计算机科学与技术系,北京100084

出　　处：《软件学报》2025年第2期680-697,共18页Journal of Software

基　　金：山西省应用基础研究计划(20210302123444,20210302123455);山西省高等学校科技创新项目(2022L002);中国高校产学研创新基金(2021FNA02009);同济大学嵌入式系统与服务计算教育部重点实验室开放课题(ESSCKF 2021-04);山西省重点研发计划(202202020101004);国家自然科学基金(61702315);国家重点研发计划(2018YFB1800401)。

摘　　要：互联网服务提供商采用路由保护算法来满足实时性、低时延和高可用应用的需求.然而已有路由保护算法存在下面3个方面的问题:(1)在不改变传统路由协议转发机制的前提下,故障保护率普遍较低;(2)为了追求较高的故障保护率,通常需要改变传统路由协议的转发机制,实际部署难度较大;(3)无法同时利用最优下一跳和备份下一跳,从而导致网络负载均衡能力较差.针对上述3个问题,提出一种基于最短路径序列化图的路由保护算法,所提算法不需要改变转发机制,支持增量部署,同时使用最优下一跳和备份下一跳不会出现路由环路,并且具有较高的故障保护率.所提算法主要包括下面两个步骤:(1)为每个节点计算一个序号,构造最短路径正序化图;(2)利用最短路径正序化图和反序搜索规则构造最短路径序列化图,在此基础上根据备份下一跳计算规则计算节点对之间的备份下一跳集合.在真实和模拟网络拓扑上进行测试,实验结果表明,与其他路由保护算法相比,所提算法在平均备份下一跳数量、故障保护率和路径拉伸度3个指标方面均具有显著的优势.Internet service providers employ routing protection algorithms to meet real-time,low-latency,and high-availability application needs.However,existing routing protection algorithms have the following three problems.(1)The failure protection ratio is generally low under the premise of not changing the traditional routing protocol forwarding mechanism.(2)The traditional routing protocol forwarding mechanism should be changed to pursue a high failure protection ratio,which is difficult to deploy in practice.(3)The optimal next hop and backup next hop cannot be utilized simultaneously,which causes poor network load balancing capability.For the three problems,this study proposes a routing protection algorithm based on the shortest path serialization graph,which does not need to change the forwarding mechanism,supports incremental deployment and adopts both optimal next hop and backup next hop without routing loops,with a high failure protection ratio.The proposed algorithm mainly includes the following two steps.(1)A sequence number for each node is calculated,and the shortest path sequencing graph is generated.(2)The shortest path serialization graph is generated based on the node sequence number and reverse order search rules,and the next hop set between node pairs is calculated according to the backup next hop calculation rules.Tests on real and simulated network topologies show that the proposed scheme has significant advantages over other routing protection schemes in the average number of backup next hops,failure protection ratio,and path stretch.

关 键 词：网络故障 路由保护 最短路径序列化图 故障保护率 路径拉伸度 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]