LFA算法的一种高效实现方法

作     者：耿海军 施新刚 王之梁 尹霞 尹少平 GENG Hai-Jun;SHI Xin-Gang;WANG Zhi-Liang;YIN Xia;YIN Shao-Ping

作者机构：山西大学软件学院山西太原030006 网络与交换技术国家重点实验室(北京邮电大学)北京100876 清华大学网络科学与网络空间研究院北京100084 清华大学计算机科学与技术系北京100084 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2018年第29卷第12期

页      面：3904-3920页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金(61702315 61402253 61872226) 网络与交换技术国家重点实验室(北京邮电大学)开放课题(SKLNST-2018-1-19) 国家高技术研究发展计划(863)(2015AA015603 2015AA016105) 

主　　题：网路故障 IP快速重路由 路由保护 路径拉伸度 故障保护率 

摘      要：研究表明,网络中的故障不可避免而且频繁出现.当故障发生时,目前互联网部署的域内路由协议需要经历收敛过程.在此过程中,路由信息可能不一致,从而导致报文丢失,降低了路由可用性.因此,业界提出了利用LFA(loop free alternates)应对网络中发生的单故障情形,从而提高路由可用性.然而,已有的LFA实现方式算法时间复杂度大,需要消耗大量的路由器CPU资源.针对该问题严格证明了当网络中出现单故障时,只需要为特定的节点计算备份下一跳,其余受该故障影响节点的备份下一跳和该特定节点的备份下一跳是相同的.基于上述性质,分别讨论了对称链路权值和非对称链路权值中对应的路由保护算法.实验结果表明:与LFA相比较,该算法的执行时间降低了90%以上,路径拉伸度降低了15%以上,并且与LFA具有同样的故障保护率.