主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第9期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
耿海军,施新刚,王之梁,尹霞,尹少平.LFA算法的一种高效实现方法.软件学报,2018,29(12):3904-3920
LFA算法的一种高效实现方法
Efficient Implementation Method for LFA
投稿时间:2016-11-01  修订日期:2017-01-03
DOI:10.13328/j.cnki.jos.005426
中文关键词:  网路故障  IP快速重路由  路由保护  路径拉伸度  故障保护率
英文关键词:network failure  IP fast re-route  routing protection  path stretch  protection ratio
基金项目:国家自然科学基金(61702315,61402253,61872226);网络与交换技术国家重点实验室(北京邮电大学)开放课题(SKLNST-2018-1-19);国家高技术研究发展计划(863)(2015AA015603,2015AA016105)
作者单位E-mail
耿海军 山西大学 软件学院, 山西 太原 030006
网络与交换技术国家重点实验室(北京邮电大学), 北京 100876 
ghj123025449@163.com 
施新刚 清华大学 网络科学与网络空间研究院, 北京 100084  
王之梁 清华大学 网络科学与网络空间研究院, 北京 100084  
尹霞 清华大学 计算机科学与技术系, 北京 100084  
尹少平 山西大学 软件学院, 山西 太原 030006  
摘要点击次数: 1691
全文下载次数: 1209
中文摘要:
      研究表明,网络中的故障不可避免而且频繁出现.当故障发生时,目前互联网部署的域内路由协议需要经历收敛过程.在此过程中,路由信息可能不一致,从而导致报文丢失,降低了路由可用性.因此,业界提出了利用LFA(loop free alternates)应对网络中发生的单故障情形,从而提高路由可用性.然而,已有的LFA实现方式算法时间复杂度大,需要消耗大量的路由器CPU资源.针对该问题严格证明了当网络中出现单故障时,只需要为特定的节点计算备份下一跳,其余受该故障影响节点的备份下一跳和该特定节点的备份下一跳是相同的.基于上述性质,分别讨论了对称链路权值和非对称链路权值中对应的路由保护算法.实验结果表明:与LFA相比较,该算法的执行时间降低了90%以上,路径拉伸度降低了15%以上,并且与LFA具有同样的故障保护率.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利