# US 9,438,472 B2 · Extended remote LFA fast reroute > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,438,472 B2 - Document ID: US9438472B2 - Status: Granted - Kind: B2 - Application number: 13/946,827 - Filed: 2013-07-19 - Published: 2015-01-22 - Granted: 2016-09-06 - Earliest claimed: 2013-07-19 - Assignees: Telefonaktiebolaget LM Ericsson (publ) - Applicants: Telefonaktiebolaget L M Ericsson (publ) - Inventors: András Császár; Balázs Peter Gerö; Gabor Sandor Enyedi - Web page: https://patentgrep.com/patent/US9438472B2 ## CPC - H04L 45/28: using route fault recovery - H04L 41/0668: by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure - H04L 45/12: Shortest path evaluation - H04L 45/22: {Alternate routing} - H04L 45/50: using label swapping, e.g. multi-protocol label switch [MPLS] - 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 or controller for determining a backup path for a fast reroute process to be utilized in response to a network event invalidating a primary path to a destination node. The method identifies at least one intermediate node that has a backup loop free alternative (LFA) path to a destination node in a network where no path meeting LFA conditions can be found for a point of local repair (PLR). ## Claims ### Claim 1 A method implemented by a network element functioning as a point of local repair (PLR), the method for determining a backup path for a fast reroute (FRR) process to be utilized in response to a network event invalidating a primary path to a destination node, where the method identifies at least one intermediate node as an extended remote loop free alternative that has a backup loop free alternative (LFA) path to a destination node in a network where no path meeting LFA conditions can be found for the PLR, the method comprising the steps of: calculating shortest paths from the PLR to each destination node in the network using a normal topology; calculating shortest paths from the PLR to each destination node in the network using a unit cost topology; selecting a next destination node D in the network without a calculated backup path from the PLR; determining a primary path next hop node F for the destination node D; determining whether an LFA path or remote LFA (RLFA) path exists from the PLR to the destination node D where the backup LFA path or RLFA path does not traverse the primary path next hop node F in the calculated shortest paths using the normal topology; determining whether a remote RLFA path exists from the PLR to the destination node D where the backup LFA path or RLFA path does not traverse the primary path next hop node F in the calculated shortest paths using the unit cost topology; determining an intermediate node on a shortest path from the PLR to the destination node D using topology that excludes the primary next hop node F and that meets LFA conditions, in response to determining that no LFA path or RLFA path exists from the PLR to the destination node D that does not traverse the primary next hop node F in the calculated shortest paths using the normal topology and the unit cost topology; and selecting the intermediate node on the shortest path as an intermediate destination for data traffic for destination node D to be utilized as the backup path to the destination node D during the FRR process. ### Claim 2 (depends on 1) The method of claim 1, further comprising the step of: checking whether a backup LFA path has been calculated for each destination node; and progressing to a next destination node where the backup LFA path has been calculated. ### Claim 3 (depends on 1) The method of claim 1, further comprising the step of: selecting a next hop node of the LFA path from the PLR to the destination node D from the normal topology as the backup LFA path for the destination node D where the LFA path exists from the PLR node to the destination node D that does not traverse the next hop node F in the calculated shortest paths using the normal topology. ### Claim 4 (depends on 1) The method of claim 1, further comprising the step of: selecting a tunnel to the RLFA path from the PLR to the destination node D from the normal topology as the backup LFA path for the destination node D where the RLFA path exists from the PLR node to the destination node D that does not traverse the next hop node F in the calculated shortest paths using the normal topology. ### Claim 5 (depends on 1) The method of claim 1, further comprising the step of: selecting a next hop node of the LFA path from the PLR to the destination node D from the normal topology as backup LFA path for the destination node D where the LFA path exists from the PLR node to the destination node D that does not traverse the next hop node F in the calculated shortest paths using the unit cost topology. ### Claim 6 (depends on 1) The method of claim 1, wherein each node in the unit cost topology uses a separate address than used in the normal topology. ### Claim 7 A network element functioning as a point of local repair (PLR), the network element configured to implement a method for determining a backup path for a fast reroute (FRR) process to be utilized in response to a network event invalidating a primary path to a destination node, where the method identifies at least one intermediate node as an extended remote loop free alternative that has a backup loop free alternative (LFA) path to a destination node in a network where no path meeting LFA conditions can be found for the PLR, the network element comprising: at least one forwarding element to forward data traffic along a primary path until the network event and to forward the data traffic along the backup LFA path after the network event; a network processor coupled to the at least one forwarding element, the network processor configured to execute a primary path calculation module and a backup path calculation module, the primary path calculation module configured to calculate shortest paths from the PLR to each destination node in the network using a normal topology, and the backup path calculation module configured to calculate shortest paths from the PLR to each destination node in the network using a unit cost topology, to select a next destination node D in the network without a calculated backup path from the PLR, to determine a primary path next hop node F for the destination node D, to determine whether an LFA path or remote LFA (RLFA) path exists from the PLR to the destination node D where the backup LFA path or RLFA path does not traverse the primary path next hop node F in the calculated shortest paths using the normal topology, to determine whether a remote RLFA path exists from the PLR to the destination node D where the backup LFA path or RLFA path does not traverse the primary path next hop node F in the calculated shortest paths using the unit cost topology, to determine an intermediate node on a shortest path from the PLR to the destination node D using a topology that excludes the primary next hop node F and that meets LFA conditions, in response to determining that no LFA path or RLFA path exists from the PLR to the destination node D that does not traverse the primary next hop node F in the calculated shortest paths using the normal topology and the unit cost topology, and to select the intermediate node on the shortest path as an intermediate destination for data traffic for destination node D to be utilized as the backup path to the destination node D during the FRR process. ### Claim 8 (depends on 7) The network element of claim 7, wherein the backup path calculation module is further configured to check whether a backup LFA path has been calculated for each destination node, and to progress to a next destination node where the backup LFA path has been calculated. ### Claim 9 (depends on 7) The network element of claim 7, wherein the backup path calculation module is further configured to select a next hop node of the LFA path from the PLR to the destination node D from the normal topology as the backup LFA path for the destination node D where the LFA path exists from the PLR node to the destination node D that does not traverse the next hop node F in the calculated shortest paths using normal topology. ### Claim 10 (depends on 7) The network element of claim 7, wherein the backup path calculation module is further configured to select a tunnel to the RLFA path from the PLR to the destination node D from the normal topology as the backup LFA path for the destination node D where the RLFA path exists from the PLR node to the destination node D that does not traverse the next hop node F in the calculated shortest paths using the normal topology. ### Claim 11 (depends on 7) The network element of claim 7, wherein the backup path calculation module is further configured to select a next hop node of the LFA path from the PLR to the destination node D from the normal topology as the backup LFA path for the destination node D where the LFA path exists from the PLR node to destination node D that does not traverse the next hop node F in the calculated shortest paths using unit cost topology. ### Claim 12 (depends on 7) The network element of claim 7, wherein each node in the unit cost topology uses a separate address than used in the normal topology. ### Claim 13 A controller for a split-architecture network configured to implement a method for determining a backup path for a fast reroute (FRR) process to be utilized in response to a network event invalidating a primary path to a destination node, where the method identifies at least one intermediate node as an extended remote loop free alternative that has a backup loop free alternative (LFA) path to a destination node in a network where no path meeting LFA conditions can be found for a point of local repair (PLR), the controller comprising: a flow controller to configure the PLR to forward data traffic along a primary path before the network event and along the backup LFA path after the network event; a processor coupled to the flow controller, the processor configured to execute a primary path calculation module and a backup path calculation module, the primary path calculation module configured to calculate shortest paths from the PLR to each destination node in the network using a normal topology, and the backup path calculation module configured to calculate shortest paths from the PLR to each destination node in the network using a unit cost topology, to select a next destination node D in the network without a calculated backup path from the PLR, to determine a primary path next hop node F for the destination node D, to determine whether an LFA path or remote LFA (RLFA) path exists from the PLR to the destination node D where the backup LFA path or RLFA path does not traverse the primary path next hop node F in the calculated shortest paths using the normal topology, to determine whether a remote RLFA path exists from the PLR to the destination node D where the backup LFA path or RLFA path does not traverse the primary path next hop node F in the calculated shortest paths using the unit cost topology, to determine an intermediate node on a shortest path from the PLR to the destination node D using a topology that excludes the primary next hop node F and that meets LFA conditions, in response to determining that no LFA path or RLFA path exists from the PLR to the destination node D that does not traverse the primary next hop node F in the calculated shortest paths using the normal topology and the unit cost topology, and to select the intermediate node on the shortest path as an intermediate destination for data traffic for destination node D to be utilized as the backup path to the destination node D during the FRR process. ### Claim 14 (depends on 13) The controller of claim 13, wherein the backup path calculation module is further configured to check whether a backup LFA path has been calculated for each destination node, and to progress to a next destination node where the backup LFA path has been calculated. ### Claim 15 (depends on 13) The controller of claim 13, wherein the backup path calculation module is further configured to select a next hop node of the LFA path from the PLR to the destination node D from the normal topology as the backup LFA path for the destination node D where the LFA path exists from the PLR node to the destination node D that does not traverse the next hop node F in the calculated shortest paths using the normal topology. ### Claim 16 (depends on 13) The controller of claim 13, wherein the backup path calculation module is further configured to select a tunnel to the RLFA path from the PLR to the destination node D from the normal topology as the backup LFA path for the destination node D where the RLFA path exists from the PLR node to the destination node D that does not traverse the next hop node F in the calculated shortest paths using the normal topology. ### Claim 17 (depends on 13) The controller of claim 13, wherein the backup path calculation module is further configured to select a next hop node of the LFA path from the PLR to the destination node D from the normal topology as the backup LFA path for the destination node D where the LFA path exists from the PLR node to the destination node D that does not traverse the next hop node F in the calculated shortest paths using the unit cost topology. ### Claim 18 (depends on 13) The controller of claim 13, wherein each node in the unit cost topology uses a separate address than used in the normal topology.