Backup BGP paths for non-multipath BGP fast convergence

• US 20070214280A1
• Filed: 03/09/2006
• Published: 09/13/2007
• 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
• Granted Patent: US 7,813,265 B2
• Time in Patent Office: Days
• US Class Current: 709/239
• 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 a best BGP path to a destination prefix;

calculating one or more backup BGP paths to 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.

2. The method as claim 1, the steps of calculating the best and backup BGP paths further comprising:

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

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; and

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

3. The method as claim 2, 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.

4. The method as claim 3, 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.

5. The method as claim 1, the steps of calculating the best and backup BGP paths further comprising:

comparing two BGP paths to the destination prefix based on a best BGP path selection algorithm;

calculating the best BGP path of the two BGP paths (a selected best BGP path); and

calculating the backup BGP path as the BGP path other than the best BGP path (a selected backup BGP path).

6. The method as claim 5, further comprising:

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

recalculating the best BGP path from the selected best BGP path and the next available BGP path based on the selection algorithm (a new selected best BGP path).

7. The method as claim 6, 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 (a new selected backup BGP path).

8. The method as claim 6, 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 (a stored number).

9. The method as claim 8, 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 (a compared number) with the stored number, and

ii) in response to the compared number being greater than the stored number, a) recalculating the selected backup BGP path as the next available BGP path, and b) storing the compared number as the stored number.

10. The method as claim 6, 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 (first step) with a step of the selection algorithm at which the selected backup BGP path was calculated (second step), and

ii) in response to the first step being further along the selection algorithm than the second step, a) recalculating the selected backup BGP path as the next available BGP path.

11. The method as claim 6, further comprising:

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

12. 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.

13. 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), IGP convergence, and BGP session connectivity detection.

14. The method as claim 1, further comprising:

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

15. The method as claim 14, further comprising:

requiring BGP next-hop node diversity.

16. The method as claim 1, further comprising:

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

17. The method as claim 16, further comprising:

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

18. The method as claim 16, further comprising:

storing the best and backup BGP paths asynchronously.

19. 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;

means for calculating one or more backup BGP paths to 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

, in response

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

20. 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;

calculating one or more backup BGP paths to 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.

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

one or more network interfaces;

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

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

i) calculate a best BGP path to a destination prefix, ii) calculate one or more backup BGP paths to the destination prefix, iii) select the best path as a utilized path for the destination prefix, iv) determine that the best BGP path has failed; and

, in response v) select one of the backup BGP paths as the utilized path for the destination prefix.