# US 2015/0103671 A1 · High Performance LFA Path Algorithms > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2015/0103671 A1 - Document ID: US20150103671A1 - Status: Published application - Kind: A1 - Application number: 14/052,414 - Filed: 2013-10-11 - Published: 2015-04-16 - Earliest claimed: 2013-10-11 - Assignees: Telefonaktiebolaget L M Ericsson (publ) - Applicants: Telefonaktiebolaget L M Ericsson (publ) - Inventors: Lars Ernström; Alfred C. Lindem, III; Pramodh D'Souza; Evgeny Tantsura - Web page: https://patentgrep.com/patent/US20150103671A1 ## CPC - H04L 45/18: Loop-free operations - H04L 41/0659: by isolating or reconfiguring faulty entities - H04L 45/122: by minimising distances, e.g. by selecting a route with minimum of number of hops - H04L 45/28: using route fault recovery - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A method is implemented by a network element 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 determines 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, and where each shortest path determined by the shortest path first calculation is stored. ## Claims ### Claim 1 A method implemented by a network element 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 method comprising the steps of: generating 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; 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, selecting and storing the candidate path as the LFA path, storing the first hop edge along the LFA path, storing a distance of the LFA path; 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. ### Claim 2 (depends on 1) The method of claim 1, further comprising the step: checking a set of secondary conditions in combination with the checking of the candidate path to be a loop free alternative path. ### Claim 3 (depends on 2) The method of claim 2, wherein checking the set of secondary conditions further comprises the step of: checking a node protection condition to determine a validity of a candidate path as a node protecting path. ### Claim 4 (depends on 3) The method of claim 3, wherein checking the node protection condition further comprises the step of: calculating a shortest distance from a first hop vertex to the end of a candidate path. ### Claim 5 (depends on 2) The method of claim 2, wherein checking the set of secondary conditions further comprises the step of: determining validity of candidate path based links of the candidate path being part of different administratively assigned protection group than the shortest path. ### Claim 6 (depends on 2) The method of claim 2, further comprising the steps of: generating another candidate path set with each candidate path being a stored shortest path, or the LFA path, joined with an edge originating at the shortest path vertex of the stored shortest path; 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 remote loop free alternative path using stored data from the shortest path first calculation and LFA path calculation; discarding the candidate path where the candidate path is not a remote loop free alternative path; where the candidate path meets applicable conditions, selecting and storing the candidate path as the remote LFA path, storing the first hop edge along the remote LFA path, storing a distance of the remote LFA path, storing a remote LFA tunnel target vertex storing a remote LFA type; 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. ### Claim 7 (depends on 6) The method of claim 6, further comprising the step of: calculating a second set of secondary conditions ### Claim 8 (depends on 7) The method of claim 7, wherein calculating the second set of secondary conditions further comprises the step of: determining a shortest distance from a remote LFA tunnel target vertex back to the source vertex for use in calculation of the loop free condition of the remote LFA path. ### Claim 9 (depends on 7) The method of claim 7, wherein calculating the second set of secondary conditions further comprises the step of: determining a validity of a remote LFA path based links of the remote LFA path being part of different administratively assigned protection group compared to the links of the shortest path. ### Claim 10 (depends on 7) The method of claim 7, wherein calculating the second set of secondary conditions further comprises the step of: determining a shortest distance from a remote LFA tunnel target vertex to a source vertex for use of in evaluation of node protection condition of remote LFA paths. ### Claim 11 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. ### Claim 12 (depends on 11) The network element of claim 11, wherein the route processor is further configured to check a set of secondary conditions in combination with the checking of the candidate path to be a loop free alternative path. ### Claim 13 (depends on 12) The network element of claim 12, wherein the route processor is further configured to check a node protection condition to determine a validity of a candidate path as a node protecting path. ### Claim 14 (depends on 13) The network element of claim 13, wherein the route processor is further configured to calculate a shortest distance from a first hop vertex to the end of the candidate path. ### Claim 15 (depends on 12) The network element of claim 12, wherein the route processor is further configured to determine validity of candidate path based links of the candidate path being part of different administratively assigned protection group than the shortest path. ### Claim 16 (depends on 12) The network element of claim 12, wherein the route processor is further configured to generate another candidate path set with each candidate path being a stored shortest path, or the LFA path, 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 remote loop free alternative path using stored data from the shortest path first calculation and LFA path calculation, to discard the candidate path where the candidate path is not a remote loop free alternative path, where the candidate path meets applicable conditions, to select and to store the candidate path as the remote LFA path, to store the first hop edge along the remote LFA path, to store a distance of the remote LFA path, to store a remote LFA tunnel target vertex, to store a remote LFA type, the router processor 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. ### Claim 17 (depends on 16) The network element of claim 16, wherein the route processor is further configured to perform a validation of a second set of secondary conditions. ### Claim 18 (depends on 17) The network element of claim 17, wherein the route processor is further configured to determine a shortest distance from a remote LFA tunnel target vertex back to the source vertex for use in calculation of the loop free condition of the remote LFA path. ### Claim 19 (depends on 17) The network element of claim 17, wherein the route processor is further configured to determine a validity of a remote LFA path based links of the remote LFA path being part of different administratively assigned protection group compared to the links of the shortest path. ### Claim 20 (depends on 17) The network element of claim 17, wherein the route processor is configured to determining a shortest distance from a remote LFA tunnel target vertex to a source vertex for use of in evaluation of node protection condition of remote LFA paths.