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

作者：耿海军^*; 尹霞

来源：计算机科学, 2019, 46(08): 116-120.

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

学术界提出利用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拥有相同的故障保护率。

• 单位
  山西大学; 清华大学