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

来源：软件学报杂志2018年第12期北京时间：

作者：耿海军,施新刚,王之梁,尹霞,尹少平

单位：耿海军，山西大学 软件学院, 山西 太原 030006;网络与交换技术国家重点实验室(北京邮电大学), 北京 10087611,施新刚，清华大学 网络科学与网络空间研究院, 北京 10008402,王之梁，清华大学 网络科学与网络空间研究院, 北京 10008403,尹霞，清华大学 计算机科学与技术系, 北京 10008404,尹少平，山西大学 软件学院, 山西 太原 03000605

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

关键词：网路故障;IP快速重路由;路由保护;路径拉伸度;故障保护率

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