LFA算法的一种高效实现方法
作者:
作者单位:

作者简介:

耿海军(1983-),男,山西灵石人,博士,讲师,CCF专业会员,主要研究领域为软件定义网络,路由算法,网络体系结构;施新刚(1980-),男,博士,高级工程师,主要研究领域为路由协议,网络测量;王之梁(1978-),男,博士,副研究员,主要研究领域为下一代互联网,路由算法;尹霞(1972-),女,博士,教授,博士生导师,CCF高级会员,主要研究领域为下一代互联网,协议测试;尹少平(1965-),男,硕士,副教授,CCF专业会员,主要研究领域为软件定义网络,路由算法,网络体系结构.

通讯作者:

耿海军,E-mail:ghj123025449@163.com

中图分类号:

基金项目:

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


Efficient Implementation Method for LFA
Author:
Affiliation:

Fund Project:

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)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    研究表明,网络中的故障不可避免而且频繁出现.当故障发生时,目前互联网部署的域内路由协议需要经历收敛过程.在此过程中,路由信息可能不一致,从而导致报文丢失,降低了路由可用性.因此,业界提出了利用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.

    参考文献
    相似文献
    引证文献
引用本文

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

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2016-11-01
  • 最后修改日期:2017-01-03
  • 录用日期:
  • 在线发布日期: 2018-03-14
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号