Optimization of distributed tunnel rerouting in a computer network with path computation at an intermediate node

• US 8,369,213 B2
• Filed: 02/20/2007
• Issued: 02/05/2013
• Est. Priority Date: 12/22/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Le Faucheur, Francois, Charny, Anna
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): Sloms, Nicholas
• Application Number:
  US11/676,675
• Publication Number:
  US 20080151746A1
• Time in Patent Office: 2,177 Days
• Field of Search: 370/242, 370/216
• US Class Current: 370/228
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 12/5691 Access to open networks; Ingress point selection, e.g. ISP selection
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

In one embodiment, an intermediate node computes paths for a set of tunnels that do not include a particular link (e.g., and possibly a scaled-down bandwidth for each tunnel), considering all of the tunnels of the set. The intermediate node informs head-end nodes of the tunnels of the computed paths (e.g., and scaled bandwidth) and/or a time to reroute the tunnels.

Claims

1. A method, comprising:

determining a set of two or more tunnels traverse a particular link of an intermediate node, wherein the particular link of the intermediate node extends from the intermediate node;

in response to determining the set of two or more tunnels traverse the particular link of the intermediate node, computing, at the intermediate node, reroute paths for the set of tunnels, the computed reroute path for each tunnel extending from a respective head-end node of the tunnel to a respective tail-end node of the tunnel and not including the particular link, the computed reroute path for each tunnel computed by considering each of the tunnels of the set and applying a rerouting policy that coordinates path computation of each of the tunnels of the set based on information available at the intermediate node adjacent to the particular link;

determining an order in which the set of tunnels are to be rerouted to result in the computed reroute paths; and

informing respective head-end nodes of the computed reroute paths and of timestamps corresponding to the order in which the set of tunnels are to be rerouted on the computed reroute paths, wherein the respective head-end nodes are adapted to reroute their respective tunnels over the computed reroute paths at times substantially equal to the timestamps in response to determining the particular link has failed.

2. The method as in claim 1, further comprising:

allowing tunnels not otherwise protected against an inability to use the particular link to be rerouted prior to tunnels that are protected.

3. The method as in claim 2, wherein the protected tunnels have established fast reroute (FRR) backup paths for the particular link.

4. The method as in claim 1, wherein the set of two or more tunnels is a subset of all tunnels that had traversed the particular link.

5. The method as in claim 1, further comprising:

applying a bandwidth scaling factor to compute reroute paths for the set of tunnels.

6. The method as in claim 5, further comprising:

using a same bandwidth scaling factor for all tunnels in the set.

7. The method as in claim 5, further comprising:

using a different bandwidth scaling factor for one or more tunnels in the set.

8. The method as in claim 5, further comprising:

utilizing a path computation technique that attempts to find a solution that has minimum bandwidth scaling for the tunnels of the set.

9. The method as in claim 5, further comprising:

determining that a first bandwidth scaling factor does not produce acceptable reroute paths for all tunnels of the set; and

, in response

applying a second bandwidth scaling factor to compute reroute paths for all tunnels in the set that is greater than the first scaling factor.

10. The method as in claim 1, further comprising:

proactively performing the step of computing prior to determining the particular link has failed.

11. The method as in claim 1, further comprising:

reactively performing the step of computing in response to determining the particular link has failed.

12. The method as in claim 1, further comprising:

proactively performing the step of computing prior to determining the particular link has failed; and

reactively performing the step of informing in response to determining the particular link has failed.

13. An intermediate node, comprising:

one or more network interfaces adapted to communicate with one or more head-end nodes;

at least one network interface from which extends a particular link;

one or more processors adapted to execute one or more processes; and

a memory adapted to store a rerouting process executable by each processor, the rerouting process when executed operable to;

i) determine a set of two or more tunnels traverse the particular link which extends from the at least one network interface, ii) in response to determination the set of two or more tunnels traverse the particular link which extends from the at least one network interface, compute reroute paths for the set of tunnels, the computed reroute paths for each tunnel to extend from a respective head-end node of the tunnel to a respective tail-end node of the of the tunnel and to not include the particular link, the computed reroute path for each tunnel computed by consideration of each of the tunnels of the set and application of a rerouting policy that coordinates path computation of each of the tunnels of the set based on information available at the intermediate node, iii) determine an order in which the set of tunnels are to be rerouted to result in the computed reroute paths, and iv) inform respective head-end nodes of the computed reroute paths and of timestamps corresponding to the order in which the set of tunnels are to be rerouted on the computed reroute paths, wherein the respective head-end nodes are adapted to reroute their respective tunnels over the computed reroute paths at times substantially equal to the timestamps in response to determination the particular link has failed.

15. The intermediate node as in claim 13, wherein the set of two or more tunnels is a subset of all tunnels that had traversed the particular link.

16. The intermediate node as in claim 13, wherein the rerouting process, when executed, is further operable to apply a bandwidth scaling factor in computation of reroute paths for the set of tunnels.

17. The intermediate node as in claim 16, wherein the rerouting process, when executed, is further operable to determine that a first bandwidth scaling factor does not produce reroute paths for all tunnels of the set, and, in response to the first bandwidth scaling factor not producing reroute paths for all tunnels of the set, to apply a second bandwidth scaling factor in computation of reroute paths for all tunnels in the set that is greater than the first scaling factor.

14. A method, comprising:

determining, at an intermediate node, a set of two or more tunnels traverse a particular link of the intermediate node, wherein the particular link of the intermediate node extends from the intermediate node;

in response to determining the set of two or more tunnels traverse the particular link of the intermediate node, computing, at the intermediate node, reroute paths for the set of tunnels that do not include the particular link, the computed reroute path for each tunnel computed by considering each of the tunnels of the set and applying a rerouting policy that coordinates path computation of each of the tunnels of the set based on information available at the intermediate node connected to the particular link;

determining an order in which the set of tunnels are to be rerouted to result in the computed reroute paths; and

informing, by the intermediate node, a head-end node of each of the tunnels of a timestamp corresponding to a respective tunnel to indicate the order in which the set of tunnels are to be rerouted, wherein the head-end nodes are adapted to reroute their respective tunnels over their own computed reroute paths at a time substantially equal to the timestamp in response to an inability to use the particular link.

18. An intermediate node, comprising:

one or more network interfaces configured to communicate with one or more head-end nodes;

at least one network interface from which extends a particular link;

one or more processors configured to execute one or more processes; and

a memory configured to store a rerouting process executable by the one or more processors, the rerouting process when executed operable to;

determine a set of two or more tunnels traverse the particular link which extends from the at least one network interface,

response to determination the set of two or more tunnels traverse the particular link which extends from the at least one network interface, compute reroute paths for the set of tunnels that do not include the particular link to reroute around the particular link, the computed reroute path for each tunnel computed by considering each of the tunnels of the set and applying a rerouting policy that coordinates path computation of each of the tunnels of the set based on information available at the intermediate node,

determine an order in which the set of tunnels are to be rerouted to result in the computed reroute paths, and

inform a head-end node of each of the tunnels of the set of a timestamp associated with a respective tunnel, the timestamp to indicate when the head-end node is to attempt to reroute the respective tunnel over its own computed reroute path to have the set of tunnels rerouted in the determined order.