Algorithm for backup PE selection

• US 7,535,828 B2
• Filed: 03/18/2005
• Issued: 05/19/2009
• Est. Priority Date: 03/18/2005
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Filsfils, Clarence, Raszuk, Robert, Guichard, Jim
• Primary Examiner(s): Rao; Seema S
• Assistant Examiner(s): DUONG, CHRISTINE T
• Application Number:
  US11/084,838
• Publication Number:
  US 20060209682A1
• Time in Patent Office: 1,523 Days
• Field of Search: 370/216, 370/217, 370/218, 370/219, 370/220, 370/221, 370/222, 370/223, 370/224, 370/225, 370/226, 370/227, 370/228, 370/395.2, 370/395.21, 370/395.41, 370/395.42, 370/395.43
• US Class Current: 370/219
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/502 Frame based

Abstract

A fast reroute (FRR) technique is implemented at the edge of a computer network. If an edge device detects a node or link failure that prevents it from communicating with a neighboring routing domain, the edge device reroutes at least some data packets addressed to that domain to a backup edge device which, in turn, forwards the packets to the neighboring domain. The backup edge device is not permitted to reroute the packets a second time. According to the inventive technique, the edge device first identifies a group one or more possible backup edge devices and then selects at least one preferred backup edge device from the group. The edge device makes its selection based on the values of one or more metrics associated with the possible backup edge devices. The metrics are input to a novel selection algorithm that selects the preferred backup edge device(s) using a hierarchical selection process or a weighted-metric selection process, or some combination thereof.

Claims

1. A method for performing fast reroute (FRR) operations at the edge of a computer network, the computer network having an edge device coupled to a neighboring routing domain, the method comprising:

identifying a set of multiple possible backup edge devices for an address prefix advertised by a device in the neighboring routing domain;

associating one or more metrics with each of the address prefix'"'"'s identified possible backup edge devices;

detecting a loss of communication between the edge device and the neighboring routing domain;

selecting a preferred backup edge device from the address prefix'"'"'s identified set of possible backup edge devices based on the value of at least one of the metrics associated with the possible backup edge devices;

receiving a data packet at the edge device, the received data packet containing a destination address matching the address prefix;

determining whether the received data packet was previously rerouted in accordance with FRR operations; and

rerouting, in response to determining that the received data packet was not previously rerouted, the received data packet to the preferred backup edge device for forwarding to the neighboring routing domain.

2. The method of claim 1, wherein the step of selecting the preferred backup edge device further comprises:

performing a hierarchical selection process that inputs the metrics associated with each possible backup edge device into a sequence of selection criteria, each criterion in the sequence being applied to the metrics until the preferred backup edge device is identified by a criterion or the selection process is terminated.

3. The method of claim 2, wherein the hierarchical selection process further comprises:

(a) assigning a relative preference level for each type of metric associated with the possible backup edge devices;

(b) evaluating, for each possible backup edge device, a value of the metric having the greatest relative preference level;

(c) identifying the preferred backup edge device as the possible backup edge device having the greatest evaluated metric value;

(d) if multiple preferred backup edge devices are identified at step (c), then evaluating the next most-preferred metric for each of the identified preferred backup edge devices; and

(e) repeating steps (c) and (d) until a single preferred backup edge device is identified or every type of metric input to the hierarchical selection process has been evaluated.

4. The method of claim 2, further comprising:

terminating the hierarchical selection process before a single preferred backup edge device is identified; and

load balancing rerouted network traffic among each of the possible backup edge devices that satisfied the selection criteria at the time the selection process was terminated.

5. The method of claim 2, further comprising:

terminating the hierarchical selection process before a single preferred backup edge device is identified; and

randomly selecting a preferred backup edge device from among the possible backup edge devices that satisfied the selection criteria at the time the selection process was terminated.

6. The method of claim 1, wherein the step of selecting the preferred backup edge device further comprises:

performing a weighted-metric selection process that inputs the metrics associated with each possible backup edge device into a predetermined mathematical function, the predetermined mathematical function generating a value for each possible backup edge device, each value representing a weighted combination of a possible backup device'"'"'s inputted metrics; and

identifying the preferred backup edge device based on the values generated by the predetermined mathematical function.

7. The method of claim 6, wherein the predetermined mathematic function is an objective polynomial function F(PE):

$F<br><br>\left(\mathrm{PE}\right)=\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>w_i·<br><br>M_i<br><br>\left(\mathrm{PE}\right),$

where M_i(PE) is the value of the i^th metric associated with a possible backup device PE and w_i is a numerical weight assigned to the i^th metric.

8. The method of claim 6, further comprising:

identifying multiple preferred backup edge devices based on the values generated by the predetermined mathematical function; and

load balancing rerouted network traffic among each of the multiple preferred backup edge devices.

9. The method of claim 6, further comprising:

identifying multiple preferred backup edge devices based on the values generated by the predetermined mathematical function; and

randomly selecting a preferred backup edge device from among the multiple preferred backup edge devices.

10. The method of claim 6, further comprising:

identifying multiple preferred backup edge devices based on the values generated by the predetermined mathematical function; and

selecting a preferred backup edge device based on the value of one or more selected metrics associated with the multiple preferred backup edge devices.

13. The method of claim 1, wherein at least one of the metrics is based on an interior gateway protocol (IGP) cost value associated with a possible backup edge device.

14. The method of claim 1, wherein at least one of the metrics is based on an inter-domain link bandwidth capacity associated with a possible backup edge device.

15. The method of claim 1, wherein at least one of the metrics is based on a link or node shared risk link group (SRLG) membership associated with a possible backup edge device.

16. The method of claim 1, wherein the step of identifying a possible backup edge device at the edge device further comprises:

receiving the address prefix from a device in the neighboring routing domain;

receiving the address prefix from another edge device in the computer network; and

identifying the other edge device in the computer network as a possible backup edge device for the address prefix.

17. The method of claim 1, wherein the step of identifying a possible backup edge device at the edge device further comprises:

statically configuring the address prefix'"'"'s set of possible backup edge devices at the edge device.

11. A method for performing fast reroute (FRR) operations at the edge of a computer network, the computer network having an edge device coupled to a neighboring routing domain, the method comprising:

identifying a set of multiple possible backup edge devices for an address prefix;

determining whether the address prefix is reachable to the edge device via an interior route;

in response to determining that the address prefix is not reachable, determining that none of the address prefix'"'"'s identified possible backup edge devices are to be used as a preferred backup edge device; and

in response to determining that the address prefix is reachable, removing from the address prefix'"'"'s identified set of possible backup edge devices any possible backup edge device that is not capable of functioning as a backup edge device, and

associating one or more metrics with each of the address prefix'"'"'s identified possible backup edge devices,

detecting a loss of communication between the edge device and the neighboring routing domain,

selecting the preferred backup edge device from the address prefix'"'"'s identified set of possible backup edge devices based on the value of at least one of the metrics associated with the possible backup edge devices,

receiving a data packet at the edge device, the received data packet containing a destination address matching the address prefix, and

rerouting, in response to determining that the received data packet was not previously rerouted, the received data packet to the preferred backup edge device for forwarding to the neighboring routing domain.

12. The method of claim 11, further comprising:

determining the backup capability of a possible backup edge device based on the contents of an interior gateway protocol (IGP) advertisement or a Border Gateway Protocol (BGP) update message previously received at the edge device.

18. A network node configured to perform fast reroute (FRR) operations at the edge of a computer network, the network node comprising:

a processor;

a first network interface adapted to receive an address prefix advertised by a device in a neighboring routing domain;

a second network interface adapted to receive a data packet containing a destination address matching the address prefix; and

a memory adapted to store instructions which are executable by the processor for performing the steps;

identifying a set of multiple possible backup edge devices for the address prefix;

associating one or more metrics with each of the address prefix'"'"'s identified possible backup edge devices;

detecting a loss of communication over the first network interface;

selecting a preferred backup edge device from the address prefix'"'"'s identified set of possible backup edge devices based on the value of at least one of the metrics associated with the possible backup edge devices;

determining whether the data packet received at the second network interface was previously rerouted in accordance with FRR operations; and

rerouting, in response to determining that the received data packet was not previously rerouted, the received data packet to the preferred backup edge device for forwarding to the neighboring routing domain.

19. The network node of claim 18, wherein the memory is further adapted to store instructions for:

performing a hierarchical selection process that inputs the metrics associated with each possible backup edge device into a sequence of selection criteria, each criterion in the sequence being applied to the metrics until the preferred backup edge device is identified by a criterion or the selection process is terminated.

20. The network node of claim 19, wherein the memory is further adapted to store instructions for:

(a) assigning a relative preference level for each type of metric associated with the possible backup edge devices;

(b) evaluating, for each possible backup edge device, a value of the metric having the greatest relative preference level;

(c) identifying the preferred backup edge device as the possible backup edge device having the greatest evaluated metric value;

(d) if multiple preferred backup edge devices are identified at step (c), then evaluating the next most-preferred metric for each of the identified preferred backup edge devices; and

(e) repeating steps (c) and (d) until a single preferred backup edge device is identified or every type of metric input to the hierarchical selection process has been evaluated.

21. The network node of claim 18, wherein the memory is further adapted to store instructions for:

performing a weighted-metric selection process that inputs the metrics associated with each possible backup edge device into a predetermined mathematical function, the predetermined mathematical function generating a value for each possible backup edge device, each value representing a weighted combination of a possible backup device'"'"'s inputted metrics; and

identifying the preferred backup edge device based on the values generated by the predetermined mathematical function.

22. The network node of claim 21, wherein the predetermined mathematic function is an objective polynomial function F(PE):

$F<br><br>\left(\mathrm{PE}\right)=\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>w_i·<br><br>M_i<br><br>\left(\mathrm{PE}\right),$

where M_i(PE) is the value of the i^th metric associated with a possible backup device PE and w_i is a numerical weight assigned to the i^th metric.

23. A network node configured to perform fast reroute (FRR) operations at the edge of a computer network, the network node comprising:

a processor;

a first network interface configured to receive an address prefix advertised by a device in a neighboring routing domain;

a second network interface configured to receive a data packet containing a destination address matching the address prefix; and

a memory configured to store instructions which are executable by the processor for performing the steps;

identifying a set of multiple possible backup edge devices for the address prefix;

determining whether the address prefix is reachable to the network node via an interior route;

in response to determining that the address prefix is not reachable, determining that none of the address prefix'"'"'s identified possible backup edge devices are to be used as a preferred backup edge device; and

in response to determining that the address prefix is reachable, removing from the address prefix'"'"'s identified set of possible backup edge devices any possible backup edge device that is not capable of functioning as a backup edge device, and

associating one or more metrics with each of the address prefix'"'"'s identified possible backup edge devices,

detecting a loss of communication over the first network interface,

selecting the preferred backup edge device from the address prefix'"'"'s identified set of possible backup edge devices based on the value of at least one of the metrics associated with the possible backup edge devices, and

rerouting, in response to determining that the received data packet was not previously rerouted, the received data packet to the preferred backup edge device for forwarding to the neighboring routing domain.

24. A network node configured to perform fast reroute (FRR) operations at the edge of a computer network, the network node being coupled to a neighboring routing domain, the network node comprising:

means for identifying a set of multiple possible backup edge devices for an address prefix advertised by a device in the neighboring routing domain;

means for associating one or more metrics with each of the address prefix'"'"'s identified possible backup edge devices;

means for detecting a loss of communication with the neighboring routing domain;

means for selecting a preferred backup edge device from the address prefix'"'"'s identified set of possible backup edge devices based on the value of at least one of the metrics associated with the possible backup edge devices;

means for receiving a data packet containing a destination address matching the address prefix;

means for determining whether the received data packet was previously rerouted in accordance with FRR operations; and

means for rerouting, in response to determining that the received data packet was not previously rerouted, the received data packet to the preferred backup edge device for forwarding to the neighboring routing domain.

25. The network node of claim 24, wherein the means for selecting the preferred backup edge device further comprises:

means for performing a hierarchical selection process that inputs the metrics associated with each possible backup edge device into a sequence of selection criteria, each criterion in the sequence being applied to the metrics until the preferred backup edge device is identified by a criterion or the selection process is terminated.

26. The network node of claim 25, further comprising:

means for assigning a relative preference level for each type of metric associated with the possible backup edge devices;

means for evaluating, for each possible backup edge device, a value of the metric having the greatest relative preference level;

means for identifying the preferred backup edge device as the possible backup edge device having the greatest evaluated metric value; and

means for evaluating the next most-preferred metric for each of the identified preferred backup edge devices if multiple preferred backup edge devices are identified by the means for identifying the preferred backup edge device.

27. The network node of claim 24, wherein the means for selecting the preferred backup edge device further comprises:

means for performing a weighted-metric selection process that inputs the metrics associated with each possible backup edge device into a predetermined mathematical function, the predetermined mathematical function generating a value for each possible backup edge device, each value representing a weighted combination of a possible backup device'"'"'s inputted metrics; and

means for identifying the preferred backup edge device based on the values generated by the predetermined mathematical function.

28. The network node of claim 27, wherein the predetermined mathematic function is an objective polynomial function F(PE):

$F<br><br>\left(\mathrm{PE}\right)=\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>w_i·<br><br>M_i<br><br>\left(\mathrm{PE}\right),$

where M_i(PE) is the value of the i^th metric associated with a possible backup device PE and w_i is a numerical weight assigned to the i^th metric.

29. A network node configured to perform fast reroute (FRR) operations at the edge of a computer network, the network node being coupled to a neighboring routing domain, the network node comprising:

means for identifying a set of multiple possible backup edge devices for an address prefix advertised by a device in the neighboring routing domain;

means for determining whether the address prefix is reachable to the network node via an interior route;

means for determining, in response to determining that the address prefix is not reachable, that none of the address prefix'"'"'s identified possible backup edge devices are to be used as a preferred backup edge device;

means for removing, in response to determining that the address prefix is reachable, from the address prefix'"'"'s identified set of possible backup edge devices any possible backup edge device that is not capable of functioning as a backup edge device;

means for associating one or more metrics with each of the address prefix'"'"'s identified possible backup edge devices;

means for detecting a loss of communication with the neighboring routing domain;

means for selecting the preferred backup edge device from the address prefix'"'"'s identified set of possible backup edge devices based on the value of at least one of the metrics associated with the possible backup edge devices;

means for receiving a data packet containing a destination address matching the address prefix; and

means for rerouting, in response to determining that the received data packet was not previously rerouted, the received data packet to the preferred backup edge device for forwarding to the neighboring routing domain.

30. A computer network, comprising:

a first edge device coupled to a neighboring routing domain; and

a second edge device coupled to the neighboring routing domain, the second edge device being configured to;

identify a set of multiple possible backup edge devices for an address prefix advertised by a device in the neighboring routing domain, the first edge device being identified as one of the possible backup edge devices for the address prefix;

associate one or more metrics with each of the address prefix'"'"'s identified possible backup edge devices;

detect a loss of communication with the neighboring routing domain;

select the first edge device as a preferred backup edge device from among the address prefix'"'"'s identified set of possible backup edge devices based on the value of at least one of the metrics associated with the possible backup edge devices;

receive a data packet containing a destination address matching the address prefix;

determine whether the received data packet was previously rerouted in accordance with FRR operations; and

reroute, in response to determining that the received data packet was not previously rerouted, the received data packet to the first edge device for forwarding to the neighboring routing domain.

31. The computer network of claim 30, wherein the second edge device is further configured to:

perform a hierarchical selection process that inputs the metrics associated with each possible backup edge device into a sequence of selection criteria, each criterion in the sequence being applied to the metrics until a criterion identifies the first edge device as the preferred backup edge device.

32. The computer network of claim 30, wherein the second edge device is further configured to:

perform a weighted-metric selection process that inputs the metrics associated with each possible backup edge device into a predetermined mathematical function, the predetermined mathematical function generating a value for each possible backup edge device, each value representing a weighted combination of a possible backup device'"'"'s inputted metrics; and

identifying the first edge device as the preferred backup edge device based on the values generated by the predetermined mathematical function.

33. A computer-readable medium storing instructions for execution on a processor for the practice of a method of performing fast reroute (FRR) operations at the edge of a computer network, the network having an edge device coupled to a neighboring routing domain, the method comprising:

identifying a set of multiple possible backup edge devices for an address prefix advertised by a device in the neighboring routing domain;

associating one or more metrics with each of the address prefix'"'"'s identified possible backup edge devices;

detecting a loss of communication between the edge device and the neighboring routing domain;

selecting a preferred backup edge device from the address prefix'"'"'s identified set of possible backup edge devices based on the value of at least one of the metrics associated with the possible backup edge devices;

receiving a data packet at the edge device, the received data packet containing a destination address matching the address prefix;

determining whether the received data packet was previously rerouted in accordance with FRR operations; and

rerouting, in response to determining that the received data packet was not previously rerouted, the received data packet to the preferred backup edge device for forwarding to the neighboring routing domain.