计算机应用研究

作者：耿海军,张琪栋,尹霞,

单位：1.山西大学a.计算机与信息技术学院;b.自动化与软件学院;c.大数据科学与产业研究院,太原030006；2.清华大学计算机科学与技术系,北京100048；

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

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

如何高效快速地应对网络中的故障是设计路由协议的基本要求和主要任务。由于动态路由协议在应对网络中的故障时，在协议动态收敛的过程中将会有大量的报文被丢弃。因此，目前路由器厂商普遍采用路由保护方法来克服网络故障，在众多的路由保护方法中，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规则的计算开销。

来源：2023年第6期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2023年第6期