Efficient constrained shortest path first optimization technique

• US 20070047469A1
• Filed: 08/24/2005
• Published: 03/01/2007
• Est. Priority Date: 08/24/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Previdi, Stefano
• Granted Patent: US 7,995,461 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/028 Dynamic adaptation of the update intervals, e.g. event-triggered updates
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

A technique performs an efficient constrained shortest path first (CSPF) optimization of Traffic Engineering (TE) Label Switched Paths (LSPs) in a computer network. The novel CSPF technique is triggered upon the detection of an event in the computer network that could create a more optimal path, such as, e.g., a new or restored network element or increased path resources. Once the novel CSPF technique is triggered, the computing node (e.g., a head-end node of the TE-LSP or a Path Computation Element, PCE) determines the set of nodes adjacent to the event, and further determines which of those adjacent nodes are within the TE-LSP (“attached nodes”). The computing node performs a CSPF computation rooted at the closest attached node to determine whether a new computed path cost is less than a current path cost (e.g., by a configurable amount), and if so, triggers optimization of the TE-LSP along the new path.

Claims

1. A method for performing an efficient constrained shortest path first (CSPF) optimization of Traffic Engineering (TE) Label Switched Paths (LSPs) in a computer network, the method comprising:

detecting an event in the computer network that could create a more optimal path for TE-LSPs;

selecting a root node based on its adjacency to the event and its location along a particular TE-LSP; and

performing a CSPF computation for the particular TE-LSP rooted at the root node.

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

determining a set of nodes adjacent to the event (adjacent nodes);

determining a subset of adjacent nodes that are attached along the particular TE-LSP (attached nodes); and

selecting an attached node that is closest to a head-end node of the particular TE-LSP as the root node.

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

determining if the CSPF computation has a lower new cost than a current cost of the particular TE-LSP; and

if so

optimizing the TE-LSP over the path computed by the CSPF computation.

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

determining during the CSPF computation that a higher new cost than a current cost of the particular TE-LSP is reached; and

if so

stopping the CSPF computation.

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

applying a configurable margin to the current cost of the particular TE-LSP prior to determining during the CSPF computation that a higher new cost than a current cost of the particular TE-LSP is reached.

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

detecting the event through an Interior Gateway Protocol (IGP) advertisement.

7. The method as in claim 1, wherein the step of detecting an event further comprises:

determining if a received notification indicates increased available resources.

8. The method as in claim 7, wherein the increased available resources are selected from the group consisting of:

a new link, a restored link, a new node, a restored node, and increased bandwidth on a link.

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

asserting an optimization flag in response to detecting the event; and

selecting the root node and performing the CSPF computation in response to the asserted optimization flag.

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

configuring a threshold number of TE-LSPs, wherein the steps of selecting the root node and performing the CSPF computation are abandoned in the event the threshold is surpassed by the number of TE-LSPs at the root node.

11. An apparatus for performing an efficient constrained shortest path first (CSPF) optimization of Traffic Engineering (TE) Label Switched Paths (LSPs) in a computer network, the apparatus comprising:

means for detecting an event in the computer network that could create a more optimal path for TE-LSPs;

means for selecting a root node based on its adjacency to the event and its location along a particular TE-LSP; and

means for performing a CSPF computation for the particular TE-LSP rooted at the root node.

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

means for determining a set of nodes adjacent to the event (adjacent nodes);

means for determining a subset of adjacent nodes that are attached along the particular TE-LSP (attached nodes); and

means for selecting an attached node that is closest to a head-end node of the particular TE-LSP as the root node.

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

means for determining if the CSPF computation has a lower new cost than a current cost of the particular TE-LSP; and

if so

means for optimizing the TE-LSP over the path computed by the CSPF computation.

14. A computer readable medium containing executable program instructions for performing an efficient constrained shortest path first (CSPF) optimization of Traffic Engineering (TE) Label Switched Paths (LSPs) in a computer network, the executable program instructions comprising program instructions for:

detecting an event in the computer network that could create a more optimal path for TE-LSPs;

selecting a root node based on its adjacency to the event and its location along a particular TE-LSP; and

performing a CSPF computation for the particular TE-LSP rooted at the root node.

15. A system for performing an efficient constrained shortest path first (CSPF) optimization of Traffic Engineering (TE) Label Switched Paths (LSPs) in a computer network, the system comprising:

one or more nodes adjacent to an event in the computer network (adjacent nodes) configured to detect the event and to notify other nodes of the event;

a root node attached along a particular TE-LSP, the root node being one of the one or more adjacent nodes that is closest to a head-end node of the particular TE-LSP; and

a computing node to receive notification of the event and configured to determine that the event could create a more optimal path for TE-LSPs, the computing node performing a CSPF computation for the particular TE-LSP rooted at the root node.

16. The system as in claim 15, wherein the computing node is further configured to determine the adjacent nodes, determine a subset of adjacent nodes that are attached along the particular TE-LSP (attached nodes), and select the root node.

17. The system as in claim 15, wherein the computing node is further configured to determine if the CSPF computation has a lower new cost than a current cost of the particular TE-LSP, and if so to optimize the TE-LSP over the path computed by the CSPF computation.

18. A computing node for performing an efficient constrained shortest path first (CSPF) optimization of Traffic Engineering (TE) Label Switched Paths (LSPs) in a computer network, the computing node comprising:

a network interface adapted to receive notification of an event in the computer network that could create a more optimal path for TE-LSPs;

a memory to store a set of nodes within the network and their locations within the network; and

a processor adapted to select a root node based on its adjacency to the event and its location along a particular TE-LSP, and perform a CSPF computation for the particular TE-LSP rooted at the root node.

19. The computing node as in claim 18, wherein the processor is further adapted to determine a set of nodes adjacent to the event (adjacent nodes), determine a subset of adjacent nodes that are attached along the particular TE-LSP (attached nodes), and selecting an attached node that is closest to a head-end node of the particular TE-LSP as the root node.

20. The computing node as in claim 18, wherein the processor is further adapted to determine if the CSPF computation has a lower new cost than a current cost of the particular TE-LSP, and if so optimize the TE-LSP over the path computed by the CSPF computation.

21. The computing node as in claim 18, further comprising:

an optimization flag, the optimization flag asserted in response to detecting the event, wherein the processor is further configured to select the root node and perform the CSPF computation in response to the asserted optimization flag.

22. The computing node as in claim 18, wherein the computing node is a head-end node of the particular TE-LSP.