Backup BGP paths for non-multipath BGP fast convergence

• US 7,813,265 B2
• Filed: 03/09/2006
• Issued: 10/12/2010
• Est. Priority Date: 03/09/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Filsfils, Clarence, Raszuk, Robert, Patel, Keyur P.
• Primary Examiner(s): Phan; Tri H
• Application Number:
  US11/371,522
• Publication Number:
  US 20070214280A1
• Time in Patent Office: 1,678 Days
• Field of Search: 370216-228, 709232-235, 709238-244
• US Class Current: 370/217
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A technique institutes backup Border Gateway Protocol (BGP) paths for non-multipath BGP Fast Convergence in a computer network. According to the novel technique, a protecting node, e.g., a border router, calculates a best BGP path to a destination prefix, and also calculates one or more backup BGP paths (i.e., non-multipath paths) to the destination prefix. The best path is selected as a utilized path for the destination prefix, e.g., the path over which to send traffic destined for the prefix from the border router. Upon determining that the best BGP path has failed, one of the backup BGP paths is selected as the utilized path for the destination prefix.

Claims

1. A method for instituting backup Border Gateway Protocol (BGP) paths for non-multipath BGP Fast Convergence in a computer network, the method comprising:

calculating, by a processor, a best BGP path to a destination prefix from a plurality of available BGP paths to the destination prefix;

removing the best BGP path from the plurality of available BGP paths to the destination prefix;

recalculating a next-best BGP path to the destination prefix from the plurality of available BGP paths;

storing the next-best BGP path as a backup BGP path for the destination prefix;

selecting the best BGP path as a utilized path for the destination prefix;

determining that the best BGP path has failed; and

, in response

selecting the backup BGP path as the utilized path for the destination prefix.

2. The method as claim 1, further comprising:

calculating additional backup BGP paths by

i) removing the next-best BGP path from the plurality of available BGP paths to the destination prefix,

ii) recalculating a next-best BGP path to the destination prefix from the plurality of available BGP paths, and

iii) storing the next-best BGP path as an additional backup BGP path for the destination prefix.

3. The method as claim 2, further comprising:

calculating additional backup BGP paths until the occurrence of one of a configurable number of additional backup paths has been calculated and determining that no available BGP paths remain for the destination prefix.

4. The method as claim 1, further comprising:

determining a set of all destination prefixes to protect; and

instituting backup BGP paths for non-multipath BGP Fast Convergence for each destination prefix of the set.

5. The method as claim 1, further comprising:

determining that the best BGP path has failed in response to a connectivity verification protocol selected from a group comprising;

Bidirectional Forwarding Detection (BFD), Interior Gateway Protocol (IGP) convergence, and BGP session connectivity detection.

6. The method as claim 1, further comprising:

requiring that the backup BGP path be diverse from the best BGP path.

7. The method as claim 6, further comprising:

requiring BGP next-hop node diversity.

8. The method as claim 1, further comprising:

storing the best and backup BGP path in a routing table.

9. The method as claim 8, further comprising:

including an indication designating the backup BGP path in the routing table.

10. The method as claim 8, further comprising:

storing the best and backup BGP path asynchronously.

11. A method for instituting backup Border Gateway Protocol (BGP) paths for non-multipath BGP Fast Convergence in a computer network, the method comprising:

comparing, by a processor, two BGP paths to a destination prefix based on a best BGP path selection algorithm;

calculating a best BGP path of the two BGP paths to produce a selected best BGP path;

calculating a backup BGP path as the BGP path of the two BGP paths other than the best BGP path to produce a selected backup BGP path;

comparing the selected best BGP path with a next available BGP path to the destination prefix;

recalculating a best BGP path from the selected best BGP path and the next available BGP path based on the selection algorithm to produce a new selected best BGP path;

selecting a finally-determined best BGP path as a utilized path for the destination prefix;

determining that the finally-determined best BGP path has failed; and

, in response

selecting a finally-determined backup BGP path as the utilized path for the destination prefix.

12. The method as claim 11, further comprising:

in response to the next available BGP path being recalculated as the new selected best BGP path, recalculating the selected backup BGP path as the selected best BGP path to produce a new selected backup BGP path.

13. The method as claim 11, further comprising:

assigning a number to each step of the best BGP path selection algorithm; and

storing the number corresponding to the step of the selection algorithm at which the selected backup BGP path was calculated to produce a stored number.

14. The method as claim 13, further comprising:

in response to the selected best BGP path remaining as the new selected best BGP path,

i) comparing a number corresponding to the step of the selection algorithm at which the new selected best BGP path was recalculated with the stored number, and

ii) in response to the number corresponding to the step of the selection algorithm at which the new selected best BGP path was recalculated being greater than the stored number, a) recalculating the selected backup BGP path as the next available BGP path, and b) storing the number corresponding to the step of the selection algorithm at which the new selected best BGP path was recalculated as the stored number.

15. The method as claim 11, further comprising:

in response to the selected best BGP path remaining as the new selected best BGP path,

i) comparing a step of the selection algorithm at which the new selected best BGP path was recalculated with a step of the selection algorithm at which the selected backup BGP path was calculated, and

ii) in response to the step of the selection algorithm at which the new selected best BGP path was recalculated being further along the selection algorithm than the step of the selection algorithm at which the selected backup BGP path was calculated, recalculating the selected backup BGP path as the next available BGP path.

16. The method as claim 11, further comprising:

recalculating the best BGP path until no next available BGP paths remain for the destination prefix.

17. An apparatus for instituting backup Border Gateway Protocol (BGP) paths for non-multipath BGP Fast Convergence in a computer network, the apparatus comprising:

means for calculating a best BGP path to a destination prefix from a plurality of available BGP paths to the destination prefix and for removing the best BGP path from the plurality of available BGP paths to the destination prefix;

means for calculating one or more backup BGP paths to the destination prefix by recalculating one or more next-best BGP paths to the destination prefix from the plurality of available BGP paths;

means for storing the one or more next-best BGP paths as backup BGP paths for the destination prefix;

means for selecting the best path as a utilized path for the destination prefix;

means for determining that the best BGP path has failed; and

means for selecting one of the backup BGP paths as the utilized path for the destination prefix, in response to determination that the best BGP path has failed.

18. A computer readable medium containing executable program instructions for instituting backup Border Gateway Protocol (BGP) paths for non-multipath BGP Fast Convergence in a computer network, the executable program instructions comprising program instructions for:

calculating a best BGP path to a destination prefix from a plurality of available BGP paths to the destination prefix;

removing the best BGP path from the plurality of available BGP paths to the destination prefix;

calculating one or more backup BGP paths to the destination prefix by recalculating one or more next-best BGP paths to the destination prefix from the plurality of available BGP paths;

storing the one or more next-best BGP paths as backup BGP paths for the destination prefix;

selecting the best path as a utilized path for the destination prefix;

determining that the best BGP path has failed; and

, in response

selecting one of the backup BGP paths as the utilized path for the destination prefix.

19. A node comprising:

one or more network interfaces;

a processor coupled to the one or more network interfaces and configured to execute software processes; and

a memory configured to store a BGP Fast Convergence process executable by the processor, the BGP Fast Convergence process configured to;

calculate a best BGP path to a destination prefix, remove the best BGP path to the destination prefix from a plurality of available BGP paths to the destination prefix, calculate one or more backup BGP paths to the destination prefix by calculation of a next-best BGP path to the destination prefix from the plurality of available BGP paths after the best BGP path was removed, select the best path as a utilized path for the destination prefix, determine that the best BGP path has failed, and, in response, select one of the backup BGP paths as the utilized path for the destination prefix.

20. The node as claim 19, wherein the BGP Fast Convergence process is further configured to determine that the best BGP path has failed in response to a connectivity verification protocol selected from a group comprising:

Bidirectional Forwarding Detection (BFD), Interior Gateway Protocol (IGP) convergence, and BGP session connectivity detection.

21. The node as claim 19, wherein the BGP Fast Convergence process is further configured to calculate an additional backup BGP path by removal of the next-best BGP path from the plurality of available BGP paths to the destination prefix and recalculation of an other next-best BGP path to the destination prefix from the plurality of available BGP paths.

22. The node as claim 19, wherein the BGP Fast Convergence process is further configured to require that the one or more backup BGP paths be diverse from the best BGP path.

23. A node comprising:

one or more network interfaces;

a processor coupled to the one or more network interfaces and configured to execute software processes; and

a memory configured to store a BGP Fast Convergence process executable by the processor, the BGP Fast Convergence process configured to;

compare two BGP paths to a destination prefix based on a best BGP path selection algorithm, calculate a best BGP path of the two BGP paths to produce a selected best BGP path, calculate a backup BGP path as the BGP path of the two BGP paths other than the best BGP path, compare the selected best BGP path with a next available BGP path to the destination prefix, recalculate a best BGP path from the selected best BGP path and the next available BGP path based on the selection algorithm, select a finally-determined best BGP path as a utilized path for the destination prefix, determine that the finally-determined best BGP path has failed; and

, in response select a finally-determined backup BGP path as the utilized path for the destination prefix.

24. The node as claim 23, wherein the BGP Fast Convergence process is further configured to, in response to the next available BGP path being recalculated as the new selected best BGP path, recalculate the selected backup BGP path as the selected best BGP path to produce a new selected backup BGP path.

25. The node as claim 23, wherein the best BGP path selection algorithm includes a plurality of ordered steps and the BGP Fast Convergence process is further configured to store an indication of a step in the plurality of ordered steps at which the selected backup BGP path was calculated.

26. The node as claim 25, wherein the BGP Fast Convergence process is further configured to compare an indication of a step in the plurality of ordered steps at which the new selected best BGP path was recalculated with the stored indication of the step in the plurality of ordered steps at which the selected backup BGP path was calculated, and in response to the step in the plurality of ordered steps at which the new selected best BGP path was recalculated being prior to the step in the plurality of ordered steps at which the selected backup BGP path was calculated, recalculate the selected backup BGP path as the next available BGP path.