OPTIMIZATION OF DISTRIBUTED TUNNEL REROUTING IN A COMPUTER NETWORK WITH PATH COMPUTATION AT AN INTERMEDIATE NODE

• US 20080151746A1
• Filed: 02/20/2007
• Published: 06/26/2008
• 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, Charny, Anna, Faucheur, Francois Le
• Granted Patent: US 8,369,213 B2
• Time in Patent Office: Days
• 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, at an intermediate node, a set of one or more tunnels that traverse a particular link of the intermediate node

computing, at the intermediate node, paths for the set of tunnels that do not include the particular link, the computed path for each tunnel considering all of the tunnels of the set; and

informing respective head-end nodes of the tunnels of the set of the computed paths, wherein each respective head-end node is adapted to reroute their respective tunnels over the computed paths in response to an inability of the set of tunnels to use the particular link.

2. The method as in claim 1, wherein the step of informing further comprises:

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

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

3. The method as in claim 1, wherein the step of informing further comprises:

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

informing respective head-end nodes of the tunnels of a timestamp corresponding to the order in which the tunnels are to be rerouted, wherein each respective head-end node is adapted to compute a path for its respective tunnel, and to reroute their respective tunnels over the computed paths at a time substantially equal to the timestamp in response to an inability to use the particular link.

4. The method as in claim 1, wherein the inability is due to a failure of the particular link.

5. The method as in claim 1, wherein the inability is due to a preemption of tunnels.

6. The method as in claim 5, wherein the step of computing further comprises:

determining an inability of a head-end node to reroute a preempted tunnel; and

selecting other tunnels to preempt.

7. The method as in claim 5, wherein the step of computing further comprises:

anticipating a preemption cascading effect caused by a preempted tunnel; and

selecting other tunnels to preempt.

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

informing downstream intermediate nodes along each tunnel'"'"'s path as to which tunnels have been selected for preemption.

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

10. The method as in claim 1, wherein the set of one or more tunnels is a subset of all tunnels traversing the particular link.

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

applying a bandwidth scaling factor to one or more tunnels of the set of tunnels in order to compute paths for the set of tunnels.

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

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

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

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

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

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

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

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

, in response

applying a second bandwidth scaling factor that is greater than the first scaling factor to one or more tunnels of the set in order to compute paths for all tunnels in the set.

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

proactively performing the steps of determining, computing, and informing prior to the inability to use the particular link.

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

reactively performing the steps of determining, computing, and informing in response to the inability to use the particular link.

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

proactively performing the steps of determining and computing prior to the inability to use the particular link; and

reactively performing the step of informing in response to the inability to use the particular link.

19. An intermediate node, comprising:

one or more network interfaces adapted to communicate with one or more head-end nodes, at least one network interface corresponding to a particular link of the intermediate node;

one or more processors coupled to the network interfaces and 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 one or more tunnels that traverse the particular link, ii) compute paths for the set of tunnels that do not include the particular link, the computed path for each tunnel considering all of the tunnels of the set, and iii) inform respective head-end nodes of the tunnels of the set of the computed paths, wherein each respective head-end node is adapted to reroute their respective tunnels over the computed paths in response to an inability of the set of tunnels to use the particular link.

20. A method, comprising:

determining, at an intermediate node, a set of one or more tunnels that traverse a particular link of the intermediate node

computing, at the intermediate node, paths for the set of tunnels that do not include the particular link, the computed path for each tunnel considering all of the tunnels of the set;

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

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