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

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