Dynamic TE-LSP priority and preemption

• US 20060250961A1
• Filed: 05/04/2005
• Published: 11/09/2006
• Est. Priority Date: 05/04/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe
• Granted Patent: US 8,107,379 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• 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]
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/245 using preemption
• CPC Class Codes: H04L 47/2458 Modification of priorities while in transit
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: H04L 47/801 Real time traffic
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/825 Involving tunnels, e.g. MPLS

Abstract

A technique dynamically assigns priorities to traffic engineering (TE) label switched paths (LSPs) from a head-end node of a computer network. The novel technique increases the ability to place TE-LSPs that would be otherwise blocked by bandwidth fragmentation. Specifically, a head-end node allocates a range of priority values for groups of possible TE-LSP configurations, such as, e.g., groups by type and/or size of the possible TE-LSPs. When requesting a TE-LSP, the head-end node attempts to establish the TE-LSP by dynamically increasing a priority value of the TE-LSP within the corresponding range of priority values until adequate resources are available, at which time the head-end node may establish the TE-LSP. Upon expiration of a configurable timer, the head-end node dynamically decreases the priority value of the established TE-LSP within the corresponding range of priority values and determines whether the established TE-LSP can lower its priority yet still obtain adequate resources along a path with an acceptable cost. If so, the head-end node may reestablish the TE-LSP at the lower priority value.

Claims

1. A method for dynamically assigning priorities to traffic engineering (TE) label switched paths (LSPs) from a head-end node of a computer network, the method comprising:

allocating a range of priority values for groups of possible TE-LSP configurations;

dynamically increasing a priority value of a TE-LSP within the corresponding range of priority values until adequate resources are available; and

establishing the TE-LSP at the priority value resulting in adequate available resources.

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

dynamically decreasing the priority value of the established TE-LSP within the corresponding range of priority values;

determining whether the established TE-LSP can still obtain adequate resources at the decreased priority value; and

if so reestablishing the TE-LSP at the decreased priority value.

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

waiting until the expiration of a timer prior to the steps of dynamically decreasing, determining, and reestablishing.

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

determining the cost of the reestablished TE-LSP prior to reestablishing the TE-LSP; and

reestablishing the TE-LSP based on an acceptable cost as compared to a cost of the established TE-LSP.

5. The method as in claim 1, wherein the groups of possible TE-LSP configurations are separated by types of TE-LSPs.

6. The method as in claim 1, wherein the groups of possible TE-LSP configurations are separated by sizes of TE-LSPs.

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

allocating higher priority to TE-LSPs with a larger size than to TE-LSPs with a lower size.

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

allocating higher priority to voice TE-LSP types than to data TE-LSP types.

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

allocating non-overlapping priorities to different TE-LSP types.

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

determining whether adequate resources are available using internally stored information.

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

receiving notifications of a burden resulting from preemption from remote headend nodes; and

deciding whether to retract the establishment of the TE-LSP based on the notifications.

12. The method as in claim 11, wherein the notifications are embodied as Interior Gateway Protocol (IGP) messages.

13. An apparatus for dynamically assigning priorities to traffic engineering (TE) label switched paths (LSPs) from a head-end node of a computer network, the apparatus comprising:

means for allocating a range of priority values for groups of possible TE-LSP configurations;

means for dynamically increasing a priority value of a TE-LSP within the corresponding range of priority values until adequate resources are available; and

means for establishing the TE-LSP at the priority value resulting in adequate available resources.

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

means for dynamically decreasing the priority value of the established TE-LSP within the corresponding range of priority values;

means for determining whether the established TE-LSP can still obtain adequate resources at the decreased priority value; and

if so means for reestablishing the TE-LSP at the decreased priority value.

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

means for receiving notifications of a burden resulting from preemption from remote head-end nodes; and

means for deciding whether to retract the establishment of the TE-LSP based on the notifications.

16. A computer readable medium containing executable program instructions for dynamically assigning priorities to traffic engineering (TE) label switched paths (LSPs) from a head-end node of a computer network, the executable program instructions comprising program instructions for:

allocating a range of priority values for groups of possible TE-LSP configurations;

dynamically increasing a priority value of a TE-LSP within the corresponding range of priority values until adequate resources are available; and

establishing the TE-LSP at the priority value resulting in adequate available resources.

17. The computer readable medium as in claim 16, further comprising:

dynamically decreasing the priority value of the established TE-LSP within the corresponding range of priority values;

determining whether the established TE-LSP can still obtain adequate resources at the decreased priority value; and

if so

reestablishing the TE-LSP at the decreased priority value.

18. The computer readable medium as in claim 16, further comprising:

receiving notifications of a burden resulting from preemption from remote headend nodes; and

deciding whether to retract the establishment of the TE-LSP based on the notifications.

19. A system for dynamically assigning priorities to traffic engineering (TE) label switched paths (LSPs) of a computer network, the system comprising:

a head-end node of the TE-LSP adapted to i) allocate a range of priority values for groups of possible TE-LSP configurations, ii) dynamically increase a priority value of a TE-LSP within the corresponding range of priority values until adequate resources are available, and iii) establish the TE-LSP at the priority value resulting in adequate available resources.