High Performance LFA Path Algorithms

A network element executing a method to improve efficiency of loop free alternative (LFA) path computation by caching data from a shortest path first calculation for use in the LFA path calculation, the shortest path first calculation to determine a shortest path from a source vertex to each vertex in a network topology graph representing the network in which the network element operates, where an endpoint for each shortest path is the shortest path vertex, where each shortest path determined by the shortest path first calculation is stored, the network element comprising:

• at least one forwarding element to forward data traffic along a primary path until a network event and to forward the data traffic along the backup LFA path after the network event;
• a route processor coupled to the at least one forwarding element, the route processor configured to execute a primary path calculation module and a backup path calculation module, the backup path calculation module configured to generate a candidate path set with each candidate path being a stored shortest path from a source vertex to the shortest path vertex joined with an edge originating at the shortest path vertex of the stored shortest path, to prioritize each candidate path in a priority queue using a distance of each candidate path, to select and removing a next candidate path from the priority queue, to check whether the candidate path is a loop free alternative path using stored data from the shortest path first calculation, to discard the candidate path where the candidate path is not a loop free alternative path, where the candidate path meets applicable conditions, to select and store the candidate path as the LFA path, to store the first hop edge along the LFA path, to store a distance of the LFA path, the backup path module further configured to check whether the priority queue is empty, to check whether all shortest path vertices in the network topology have LFA paths, and to end the LFA path calculation when the priority queue is empty or all shortest path vertices have LFA paths.