基于增量最短路径优先的域内高效路由保护算法  

Efficient Intra-domain Routing Protection Algorithm Based on i-SPF

作　　者：耿海军 尹霞[2] GENG Hai-jun;YIN Xia(School of Software Engineering,Shanxi University,Taiyuan 030006,China;Department of Computer Science&Technology,School of Information Science and Technology,Tsinghua University,Beijing 100084,China)2)

机构地区：[1]山西大学软件学院,太原030006 [2]清华大学信息科学技术学院计算机科学与技术系,北京100084

出　　处：《计算机科学》2019年第8期116-120,共5页Computer Science

基　　金：国家自然科学基金(61702315);网络与交换技术国家重点实验室(北京邮电大学)开放课题(SKLNST-2018-1-19)资助

摘　　要：学术界提出利用LFC(Loop-Free Criterion,LFC)规则来解决网络中所有可能出现的单链路故障情形,但是已有的针对LFC的实现方式的计算开销随着网络节点平均度的增加而增加,给路由器带来了大量的额外负担。针对该问题,文中研究如何降低LFC实现方式的计算开销,提出了一种基于增量最短路径优先(Incremental Shortest Path First,i-SPF)的域内高效路由保护算法(Efficient Intra-domain Routing Protection Algorithm Based on i-SPF,ERPISPF)。理论证明ERPISPF的计算开销远远小于构造一棵最短路径树的计算开销,并且可以为任意源-目的对计算出所有符合LFC规则的下一跳集合。实验结果表明,与LFC方案相比,ERPISPF的计算开销降低了93%左右,并且与LFC拥有相同的故障保护率。LFC(Loop-Free Criterion)has been proposed to cope with all the single link failure scenarios.However,the existing LFC implementation algorithms are time-consuming and require a large amount of router CPU resources.Therefore,this paper studied how to reduce the computational overhead of the LFC implementation,and proposed an efficient Intra-domain routing protection algorithm based on i-SPF(ERPISPF).Theoretical analysis indicates that the time complexity of ERPISPF is less than that of constructing a shortest path tree,and ERPISPF can compute all the valid LFC next-hop sets for any source-destination pairs.The experiment results show that ERPISPF reduce more than 93%computation overhead compared with the LFC,and can provide the same protection ratio with LFC.

关 键 词：实时应用 路由保护 最短路径树 增量最短路径优先 LFC规则 网络故障 路由可用性 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]