一种线性时间复杂度的高效路由保护方法

作     者：耿海军 张琪栋 尹霞 Geng Haijun;Zhang Qidong;Yin Xia

作者机构：山西大学计算机与信息技术学院太原030006 山西大学自动化与软件学院太原030006 山西大学大数据科学与产业研究院太原030006 清华大学计算机科学与技术系北京100048 

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

出 版 物：《计算机应用研究》 (Application Research of Computers)

年 卷 期：2023年第40卷第6期

页      码：1794-1800页

摘      要：如何高效快速地应对网络中的故障是设计路由协议的基本要求和主要任务。由于动态路由协议在应对网络中的故障时,在协议动态收敛的过程中将会有大量的报文被丢弃。因此,目前路由器厂商普遍采用路由保护方法来克服网络故障,在众多的路由保护方法中,DC(downstream criterion)规则是一种被普遍认可的方法。然而,已有的实现DC规则算法的时间复杂度普遍较高,并且复杂度随着网络节点平均度的增加而迅速增加。为了应对上述问题,提出一种线性时间复杂度的高效路由保护方案ERPLR(efficient routing protection method with linear time complexity),该方法首先提出了备份下一跳计算规则,然后在已有最短路径树的基础上,根据备份下一跳计算规则为所有的源目的节点对计算备份下一跳。在计算备份下一跳的过程中,每个节点和其邻居最多被访问一次,因此ERPLR的时间复杂度为O(V+E)。实验结果表明,与已有的实现DC规则相比较,ERPLR在故障保护率和路径拉伸度两个度量指标结果相似的情况下,在真实网络拓扑和模拟拓扑中,ERPLR分别降低了大约74.93%和78.91%的计算开销,该方法可以极大地降低DC规则的计算开销。

主 题 词：网络故障 路由保护算法 DC规则 路径拉伸度 故障保护率 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 08[工学] 081201[081201] 0812[工学-测绘类] 

D　O　I：10.19734/j.issn.1001-3695.2022.11.0521

馆 藏 号：203117045...