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

• 全文链接
• 请求原文

作   者：

耿海军;  施新刚;  王之梁;  尹霞;  尹少平; 

作者机构：

清华大学网络科学与网络空间研究院;  清华大学计算机科学与技术系;  网络与交换技术国家重点实验室(北京邮电大学);  山西大学软件学院; 

关键词：

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

期刊名称：

软件学报

基金项目：

基于关键节点路由保护的域内路由可用性研究
互联网前缀劫持的监测与防御研究
基于关键链路优先的网络性能测量与态势感知研究

i s s n：

1000-9825

年卷期：

2018 年 29 卷 12 期

页   码：

3904-3920

摘   要：

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