基于增量最短路径优先算法的高效LFA实现方法

Efficient LFA implementation method based on incremental shortest path first algorithm

针对已有LFA实现方式计算开销大和部署难度高的问题,提出了一种基于增量最短路径优先算法的LFA实现方法(LFA implementation method based on incremental shortest path first algorithm,ERPISPF)。首先将快速实现LFA的问题转换为如何在以计算节点为根的最短路径树上高效地计算其所有邻居节点到网络其余所有节点的最小代价问题;然后提出了计算该代价的定理并且证明了它的正确性,最后从理论上分析了算法的时间复杂度。仿真结果表明,ERPISPF不仅计算开销小,并且与LFC的故障保护率是相同的。

This paper proposed an efficient LFA implementation method based on incremental shortest path first algorithm(ERPISPF)to reduce the computational overhead and deployment difficulty of the existing LFA algorithm.The paper first turned the problem of quick implementation of LFA into how to efficiently calculate the minimum cost of all its neighbors to all other nodes of the network on the shortest path tree rooted at the compute node.Then it presented a theorem for calculating the cost and proved its correctness.Finally,it theoretically analyzed the time complexity of the algorithm.Experiments show that compared with LFA algorithm,ERPISPF not only has less computation overhead,but also provides the same failure protection rate as LFA.