软件学报

作者：耿海军，胡睿乾，胡治国，尹霞

单位：耿海军，山西大学 自动化与软件学院, 山西 太原 030006;山西大学 计算机与信息技术学院, 山西 太原 03000611,胡睿乾，山西大学 计算机与信息技术学院, 山西 太原 03000602,胡治国，山西大学 计算机与信息技术学院, 山西 太原 030006;嵌入式系统与服务计算教育部重点实验室(同济大学), 上海 20009203,尹霞，清华大学 计算机科学与技术系, 北京 10008404

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

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

互联网服务提供商采用路由保护算法来满足实时性、低时延和高可用应用的需求. 然而已有路由保护算法存在下面3个方面的问题: (1)在不改变传统路由协议转发机制的前提下, 故障保护率普遍较低; (2)为了追求较高的故障保护率, 通常需要改变传统路由协议的转发机制, 实际部署难度较大; (3)无法同时利用最优下一跳和备份下一跳, 从而导致网络负载均衡能力较差. 针对上述3个问题, 提出一种基于最短路径序列化图的路由保护算法, 所提算法不需要改变转发机制, 支持增量部署, 同时使用最优下一跳和备份下一跳不会出现路由环路, 并且具有较高的故障保护率. 所提算法主要包括下面两个步骤: (1)为每个节点计算一个序号, 构造最短路径正序化图; (2)利用最短路径正序化图和反序搜索规则构造最短路径序列化图, 在此基础上根据备份下一跳计算规则计算节点对之间的备份下一跳集合. 在真实和模拟网络拓扑上进行测试, 实验结果表明, 与其他路由保护算法相比, 所提算法在平均备份下一跳数量、故障保护率和路径拉伸度3个指标方面均具有显著的优势.

来源：2025年第2期

《软件学报》期刊编辑部

查看软件学报杂志2025年第2期