###
Journal of Software:2018.29(12):3904-3920

LFA算法的一种高效实现方法
耿海军,施新刚,王之梁,尹霞,尹少平
(山西大学 软件学院, 山西 太原 030006;网络与交换技术国家重点实验室(北京邮电大学), 北京 100876;清华大学 网络科学与网络空间研究院, 北京 100084;清华大学 计算机科学与技术系, 北京 100084)
Efficient Implementation Method for LFA
GENG Hai-Jun,SHI Xin-Gang,WANG Zhi-Liang,YIN Xia,YIN Shao-Ping
(School of Software Engineering, Shanxi University, Taiyuan 030006, China;State Key Laboratory of Networking and Switching Technology(Beijing University of Posts and Telecommunications), Beijing 100876, China;Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing 100084, China;Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 1048   Download 730
Received:November 01, 2016    Revised:January 03, 2017
> 中文摘要: 研究表明,网络中的故障不可避免而且频繁出现.当故障发生时,目前互联网部署的域内路由协议需要经历收敛过程.在此过程中,路由信息可能不一致,从而导致报文丢失,降低了路由可用性.因此,业界提出了利用LFA(loop free alternates)应对网络中发生的单故障情形,从而提高路由可用性.然而,已有的LFA实现方式算法时间复杂度大,需要消耗大量的路由器CPU资源.针对该问题严格证明了当网络中出现单故障时,只需要为特定的节点计算备份下一跳,其余受该故障影响节点的备份下一跳和该特定节点的备份下一跳是相同的.基于上述性质,分别讨论了对称链路权值和非对称链路权值中对应的路由保护算法.实验结果表明:与LFA相比较,该算法的执行时间降低了90%以上,路径拉伸度降低了15%以上,并且与LFA具有同样的故障保护率.
Abstract:Lots of related researches have shown that network failures occur inevitably and frequently on the Internet. When network failures occur, the currently deployed intra-domain routing protocol need to re-convergent. During the process of re-convergence, the packets may be lost due to inconsistent routing information, thus greatly reducing the Internet routing availability. LFA was proposed to cope with all the single failure scenarios. However, the existing LFA implementation algorithms are time-consuming and require a large amount of router CPU resources. This paper proves that when a single fault occurs in a network, it only needs to calculate the backup next hop for a specific node. The backup next hop of all the other affected nodes by the fault is the same as that of the specific node. Based on the above property, the paper proposes two routing protection algorithms to provide protection for networks with symmetric and asymmetric. The results show that these approaches reduce more than 90% computation overhead compared to LFA, and achieve less than 15% path stretch. Moreover, they can provide comparable protection ratio with LFA.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61702315,61402253,61872226);网络与交换技术国家重点实验室(北京邮电大学)开放课题(SKLNST-2018-1-19);国家高技术研究发展计划(863)(2015AA015603,2015AA016105) 国家自然科学基金(61702315,61402253,61872226);网络与交换技术国家重点实验室(北京邮电大学)开放课题(SKLNST-2018-1-19);国家高技术研究发展计划(863)(2015AA015603,2015AA016105)
Foundation items:National Natural Science Foundation of China (61702315, 61402253, 61872226); Open Foundation of State KeyLaboratory of Networking and Switching Technology(Beijing University of Posts and Telecommunications) (SKLNST-2018-1-19);National High Technology Research and Development Program of China (863) (2015AA015603, 2015AA016105)
Reference text:

耿海军,施新刚,王之梁,尹霞,尹少平.LFA算法的一种高效实现方法.软件学报,2018,29(12):3904-3920

GENG Hai-Jun,SHI Xin-Gang,WANG Zhi-Liang,YIN Xia,YIN Shao-Ping.Efficient Implementation Method for LFA.Journal of Software,2018,29(12):3904-3920