Patent ID: 9253079
Filing Date: 2016-02-02
CPC Classification: H04L

Claim Text:
1. A method implemented by a first network device 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 representing the first network device to each vertex in a network topology graph representing a plurality of network devices in a network in which the first network device operates, where an endpoint for each shortest path is a shortest path vertex representing a second network device in the network, where each shortest path determined by the shortest path first calculation is stored, the method comprising the steps of: generating a candidate path set with each candidate path being a stored shortest path from a source vertex, the first network device, to the shortest path vertex, the second network device, with an addition of a link originating at the shortest path vertex of the stored shortest path to a neighbor node of the shortest path vertex representing a third network device in the network; prioritizing each candidate path in a priority queue using a distance of each candidate path; selecting and removing a next candidate path from the priority queue; checking whether the candidate path is a loop free alternative path using stored data from the shortest path first calculation; discarding the candidate path where the candidate path is not a loop free alternative path; where the candidate path meets applicable conditions, checking whether the priority queue is empty; checking whether all shortest path vertices in the network topology have LFA paths; and ending the LFA path calculation when the priority queue is empty or all shortest path vertices have LFA paths.