计算机应用研究

作者：耿海军,郭小英,尹霞,

单位：1.山西大学软件学院,太原030006；2.清华大学计算机科学与技术,北京100084；

关键词：增量最短路径优先,LFA规则,网络故障,

基金：国家自然科学基金资助项目(61702315)；；

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

来源：2020年第3期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2020年第3期