高性能LFA路径算法

摘要

一种方法，由网络元件实现，从而通过缓存来自最短路径优先运算的数据以用于在无环备选(LFA)路径运算中使用来提高所述LFA路径运算效率。所述最短路径优先运算确定在表示所述网络元件操作所在的网络的网络拓扑图中从源顶点到每个顶点的最短路径，其中每个最短路径的端点是最短路径顶点，以及其中由所述最短路径优先运算确定的每个最短路径被存储。

主权项

一种通过缓存来自最短路径优先运算的数据以用于在无环备选(LFA)路径运算中使用来提高所述LFA路径运算效率的由网络元件实现的方法，所述最短路径优先运算确定在表示所述网络元件操作所在的网络的网络拓扑图中从源顶点到每个顶点的最短路径，其中每个最短路径的端点是最短路径顶点，其中由所述最短路径优先运算确定的每个最短路径被存储，所述方法包括以下步骤：生成(111)备选路径集合，每个备选路径是从源顶点到所述最短路径顶点的存储的最短路径，所述最短路径由源于所述存储的最短路径的所述最短路径顶点的边缘所加入；使用每个备选路径的距离在优先队列中对每个备选路径排序(113)；从所述优先队列中选择和移除(115)下一个备选路径；使用来自所述最短路径优先运算的存储的数据来验证(117)所述备选路径是否是无环备选路径；在所述备选路径不是无环备选路径的情况下丢弃(119)所述备选路径；在所述备选路径满足可适用条件的情况下，选择并存储(125)所述备选路径作为所述LFA路径，存储(127)沿着所述LFA路径的第一跳边缘，存储(129)所述LFA路径的距离；验证(135)所述优先队列是否为空；验证(133)是否所述网络拓扑中所有的最短路径顶点具有LFA路径；以及当所述优先队列为空或者所有最短路径顶点具有LFA路径时终止所述LFA路径运算。