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

• 作者: 尹少平 尹霞 施新刚 王之梁 耿海军
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 网路故障 IP快速重路由 路由保护 路径拉伸度 故障保护率
• 年，卷（期）: 2018,（12）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 3904-3920
• 页数: 17页
• 分类号: TP393
• 字数: 14384字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005426

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王之梁	清华大学网络科学与网络空间研究院	19	87	5.0	9.0
2	尹霞	清华大学计算机科学与技术系	52	329	9.0	16.0
3	施新刚	清华大学网络科学与网络空间研究院	15	55	4.0	6.0
4	尹少平	山西大学软件学院	20	97	5.0	9.0