Enhanced procedure to compute LFAs with IGP max metric

• US 9,407,534 B2
• Filed: 05/27/2014
• Issued: 08/02/2016
• Est. Priority Date: 05/27/2014
• Status: Active Grant

• Current Assignee: Vivo Mobile Communication Co., Ltd. (Vivo Communication Technology Co. Ltd.)
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Chunduri, Uma S., Lu, Wenhu, Patil, Vasant
• Primary Examiner(s): Huynh, Dung B
• Application Number:
  US14/288,211
• Publication Number:
  US 20150350059A1
• Time in Patent Office: 798 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities

Abstract

A method and implementing system calculates a loop free alternative (LFA) next hop as a backup for a primary path next hop for an interior gateway protocol (IGP). The method enables consideration of the LFA next hop where a link to the next hop has a reverse cost that has a maximum value. The method includes selecting a next candidate next hop from a set of candidate next hops in the network, checking whether a link to the next candidate next hop is an administratively allowable link, and checking whether the link has a maximum forward cost. The method further checks whether the link is bi-directional and computes the LFA using the next candidate next hop where the link is administratively allowable link, where the link does not have a maximum forward cost and where the link is bi-directional without consideration of reverse cost of the link.

Claims

1. A method implemented by a network device in a network having a plurality of nodes, the method to calculate a loop free alternative (LFA) next hop as a backup for a next hop of a primary path for an interior gateway protocol (IGP), where the method enables consideration of the LFA next hop where a link to the next hop has a reverse cost that has a maximum value, where the maximum value is a maximum link metric defined for the network, a forward cost is a metric for an outbound direction from the network device on the link, the reverse cost is a metric for an inbound direction toward the network device on the link, the method comprising the steps of:

selecting a next candidate next hop from a set of candidate next hops in the network;

checking whether a link to the next candidate next hop is an administratively allowable link;

checking whether the link has a maximum forward cost, where the maximum forward cost is a value defined for the network as a maximum possible value for a forward link cost;

checking whether the link is bi-directional;

computing LFA using the next candidate next hop where the link is administratively allowable link, where the link does not have the maximum forward cost, where the link is bi-directional, and where the link is considered for the LFA when the link has a reverse cost with the maximum value; and

updating a local routing information base of the network device to enable forwarding of data traffic using the computed LFA where the primary path has failed.

2. The method of claim 1, further comprising the step of:

checking whether a neighbor node corresponding to the link is overloaded where the IGP is intermediate system-intermediate system (IS-IS).

3. The method of claim 1, further comprising the step of:

checking whether the set of candidate next hops has been exhausted.

4. The method of claim 1, wherein the maximum forward cost is defined by intermediate system to intermediate system (IS-IS).

5. The method of claim 1, wherein the maximum forward cost is defined by open shortest path first (OSPF).

6. The method of claim 1, wherein the IGP is for internet protocol version 4 (IPv4).

7. The method of claim 1, wherein the IGP is for internet protocol version 6 (IPv6).

8. A network device in a network having a plurality of nodes, the network device to implement a method to calculate a loop free alternative (LFA) next hop as a backup for a next hop of a primary path for an interior gateway protocol (IGP), where the method enables consideration of the LFA next hop where a link to the next hop has a reverse cost that has a maximum value, where the maximum value is a maximum link metric defined for the network, a forward cost is a metric for an outbound direction from the network device on the link, the reverse cost is a metric for an inbound direction toward the network device on the link, the network device comprising:

a non-transitory storage medium to store networking software; and

a network processor communicatively coupled to the non-transitory storage medium, the network processor configured to execute an IGP module, the IGP module configured to select a next candidate next hop from a set of candidate next hops in the network, to check whether a link to the next candidate next hop is an administratively allowable link, to check whether the link has a maximum forward cost, where the maximum forward cost is a value defined for the network as a maximum possible value for a forward link cost, to check whether the link is bi-directional, to compute LFA using the next candidate next hop where the link is administratively allowable link, the link does not have the maximum forward cost and the link is bi-directional, and where the link is considered for the LFA when the link has a reverse cost with the maximum value, and to update a local routing information base of the network device to enable forwarding of data traffic using the computed LFA where the primary path has failed.

9. The network device of claim 8, wherein the network processor is further configured execute the IGP module and to check whether a neighbor node corresponding to the link is overloaded where the IGP is intermediate system-intermediate system (IS-IS).

10. The network device of claim 8, wherein the network processor is further configured execute the IGP module and check whether the set of candidate next hops has been exhausted.

11. The network device of claim 8, wherein the maximum forward cost is defined by intermediate system to intermediate system (IS-IS).

12. The network device of claim 8, wherein the maximum forward cost is defined by open shortest path first (OSPF).

13. The network device of claim 8, wherein the IGP is for internet protocol version 4 (IPv4).

14. The network device of claim 8, wherein the IGP is for internet protocol version 6 (IPv6).

15. A control plane device configured to implement at least one centralized control plane for a software defined network (SDN), the centralized control plane configured to calculate a loop free alternative (LFA) next hop as a backup for a next hop of a primary path for an interior gateway protocol (IGP), where the centralized control plane enables consideration of the LFA next hop where a link to the next hop has a reverse cost that has a maximum value, where the maximum value is a maximum link metric defined for a network, a forward cost is a metric for an outbound direction from a network device on the link, the reverse cost is a metric for an inbound direction toward the network device on the link, the control plane device comprising:

a non-transitory storage medium to store centralized control plane software and an IGP module; and

a processor communicatively coupled to the non-transitory storage medium, the processor configured to execute the control plane software to implement the IGP module, the IGP module configured to select a next candidate next hop from a set of candidate next hops in the network, to check whether a link to the next candidate next hop is an administratively allowable link, to check whether the link has a maximum forward cost, where the maximum forward cost is a value defined for the network as a maximum possible value for a forward link cost, to check whether the link is bi-directional, to compute LFA using the next candidate next hop where the link is administratively allowable link, the link does not have the maximum forward cost and the link is bi-directional, and where the link is considered for the LFA when the link has a reverse cost with the maximum value, and to update a local routing information base of the network device to enable forwarding of data traffic using the computed LFA where the primary path has failed.

16. The control plane device of claim 15, wherein the processor is further configured execute the IGP module and to check whether a neighbor node corresponding to the link is overloaded where the IGP is intermediate system-intermediate system (IS-IS).

17. The control plane device of claim 15, wherein the processor is further configured execute the IGP module and check whether the set of candidate next hops has been exhausted.

18. The control plane device of claim 15, wherein the IGP is for internet protocol version 4 (IPv4).

19. The control plane device of claim 15, wherein the IGP is for internet protocol version 6 (IPv6).

20. A computing device implementing a plurality of virtual machines for implementing network function virtualization (NFV), wherein a virtual machine from the plurality of virtual machines is configured to calculate a loop free alternative (LFA) next hop as a backup for a next hop of a primary path for an interior gateway protocol (IGP), where the NFV enables consideration of the LFA next hop where a link to the next hop has a reverse cost that has a maximum value, where the maximum value is a maximum link metric defined for a network, a forward cost is a metric for an outbound direction from a network device on the link, the reverse cost is a metric for an inbound direction toward the network device on the link, the computing device comprising:

a non-transitory storage medium to store an IGP module; and

a processor communicatively coupled to the non-transitory storage medium, the processor configured to execute the IGP module, the IGP module configured to select a next candidate next hop from a set of candidate next hops in the network, to check whether a link to the next candidate next hop is an administratively allowable link, to check whether the link has a maximum forward cost, where the maximum forward cost is a value defined for the network as a maximum possible value for a forward link cost, to check whether the link is bi-directional, to compute LFA using the next candidate next hop where the link is administratively allowable link, the link does not have the maximum forward cost and the link is bi-directional, and where the link is considered for the LFA when the link has a reverse cost with the maximum value, and to update a local routing information base of the network device to enable forwarding of data traffic using the computed LFA where the primary path has failed.

21. The computing device of claim 20, wherein the processor is further configured execute the IGP module and to check whether a neighbor node corresponding to the link is overloaded where the IGP is intermediate system-intermediate system (IS-IS).

22. The computing device of claim 20, wherein the processor is further configured execute the IGP module and check whether the set of candidate next hops has been exhausted.

23. The computing device of claim 20, wherein the maximum forward cost is defined by open shortest path first (OSPF).

24. The computing device of claim 20, wherein the IGP is for internet protocol version 4 (IPv4).

25. The computing device of claim 20, wherein the IGP is for internet protocol version 6 (IPv6).