Inter-domain TE-LSP selection

• US 7,646,719 B2
• Filed: 12/02/2004
• Issued: 01/12/2010
• Est. Priority Date: 12/02/2004
• 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 B.
• Primary Examiner(s): Moore, Jr.; Michael J
• Application Number:
  US11/001,784
• Publication Number:
  US 20060120288A1
• Time in Patent Office: 1,867 Days
• Field of Search: None
• US Class Current: 370/238
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/24 Multipath
• 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/125 by balancing the load, e.g. traffic engineering

Abstract

A technique selects a traffic engineering (TE) label switched path (LSP) from among a plurality of TE-LSPs, each of which spans multiple domains of a computer network from a head-end node of a local domain to a tail-end node of a remote domain, in order to reach one or more address prefixes within the remote domain. The inter-domain TE-LSP selection technique comprises a selection algorithm executed by the head-end node and based on predetermined TE-LSP attributes (e.g., bandwidth, cost, etc.) and/or address prefix reachability attributes (e.g., cost from a tail-end node to the prefix) to select an appropriate inter-domain TE-LSP for the reachable address prefix. The selection algorithm is embodied in one of two modes: (i) a hierarchical selection mode, or (ii) a weighted selection mode. In addition, the technique comprises a load balancing aspect that cooperates with the selection algorithm to enable the head-end node to balance traffic loads among the multiple TE-LSPs based on the results of the selection algorithm.

Claims

1. A method for selecting a traffic engineering (TE) label switched path (LSP) from among a plurality of TE-LSPs, each TE-LSP spanning multiple domains of a computer network from a local domain to a remote domain in order to reach one or more address prefixes within the remote domain, the method comprising:

executing a hierarchical selection algorithm at a head-end node of the local domain, the hierarchical selection algorithm based on predetermined TE-LSP attributes of the inter-domain TE-LSPs and configured to select one or more appropriate TE-LSPs for the reachable address prefix by

examining attributes in a hierarchical manner by order of predetermined preference for each address prefix reachable by the TE-LSPs, and

selecting one or more appropriate TE-LSPs for a preferred TE-LSP attribute to reach the address prefix in the remote domain; and

invoking load balancing, in cooperation with the hierarchical selection algorithm, to enable the head-end node to balance traffic loads among the one or more appropriate selected TE-LSPs.

2. The method of claim 1, further comprising:

randomly selecting one or more appropriate TE-LSPs in the event all examined attributes are similar to more than one TE-LSP.

17. The method of claim 1, wherein the predetermined TE-LSP attributes comprise bandwidth and cost attributes.

18. The method of claim 1, further comprising:

executing the hierarchical selection algorithm based on predetermined prefix attributes of reaching the address prefix from a tail-end node of the TE-LSPs.

3. A method for selecting a traffic engineering (TE) label switched path (LSP) from among a plurality of TE-LSPs, each TE-LSP spanning multiple domains of a computer network from a local domain to a remote domain in order to reach one or more address prefixes within the remote domain, the method comprising:

executing a weighted selection algorithm at a head-end node of the local domain, the weighted selection algorithm based on predetermined TE-LSP attributes of the inter-domain TE-LSPs and configured to select one or more appropriate TE-LSPs for the reachable address prefix by

evaluating an objective polynomial function for each of the TE-LSPs, the polynomial function configured to characterize the overall preference of the TE-LSPs, and

selecting the one or more TE-LSPs with the highest overall preference to reach the address prefix in the remote domain; and

invoking load balancing, in cooperation with the weighted selection algorithm, to enable the head-end node to balance traffic loads among the one or more appropriate selected TE-LSPs.

4. The method of claim 3, wherein the polynomial function comprises a plurality of sub-functions, wherein each sub-function is configured to characterize the preference of a TE-LSP attribute.

5. The method of claim 4, wherein each sub-function includes a variable that characterizes a configurable weight applied to the attribute.

6. The method of claim 3, further comprising:

randomly selecting one or more appropriate TE-LSPs in the event all examined attributes are similar to more than one TE-LSP.

7. The method of claim 3, wherein the predetermined TE-LSP attributes comprise bandwidth and cost attributes.

8. The method of claim 3, further comprising:

executing the weighted selection algorithm based on predetermined prefix attributes of reaching the address prefix from a tail-end node of the TE-LSPs.

9. A system for selecting a traffic engineering (TE) label switched path (LSP) from among a plurality of TE-LSPs, each TE-LSP spanning multiple domains of a computer network from a local domain to a remote domain in order to reach one or more address prefixes within the remote domain, the system comprising:

a head-end node of the TE-LSPs in the local domain; and

a routing information base (RIB) of the head-end node, the RIB executing (i) a hierarchical selection algorithm based on predetermined TE-LSP attributes of the inter-domain TE-LSPs and configured to select one or more appropriate TE-LSPs for the reachable address prefix by examination of attributes in a hierarchical manner by order of predetermined preference for each address prefix reachable by the TE-LSPs, and selection of one or more appropriate TE-LSPs for a preferred TE-LSP attribute to reach the address prefix in the remote domain and (ii) a load balancing algorithm, in cooperation with the hierarchical selection algorithm, to enable the head-end node to balance traffic loads among the one or more appropriate selected TE-LSPs.

19. The system of claim 9, wherein the predetermined TE-LSP attributes comprise bandwidth and cost attributes.

20. The system of claim 9, wherein the hierarchical selection algorithm is based on predetermined prefix attributes of reaching the address prefix from a tail-end node of the TE-LSPs.

10. A system for selecting a traffic engineering (TE) label switched path (LSP) from among a plurality of TE-LSPs, each TE-LSP spanning multiple domains of a computer network from a local domain to a remote domain in order to reach one or more address prefixes within the remote domain, the system comprising:

a head-end node of the TE-LSPs in the local domain; and

a routing information base (RIB) of the head-end node, the RIB executing (i) a weighted selection algorithm based on predetermined TE-LSP attributes of the inter-domain TE-LSPs and configured to select one or more appropriate TE-LSPs for the reachable address prefix with an objective polynomial function to be evaluated for each of the TE-LSPs, the polynomial function configured to characterize the overall preference of the TE-LSPs, wherein the head-end node selects the one or more TE-LSPs with the highest overall preference to reach the address prefix in the remote domain and (ii) a load balancing algorithm, in cooperation with the selection algorithm, to enable the head-end node to balance traffic loads among the appropriate selected TE-LSPs.

11. The system of claim 10, further comprising:

a plurality of sub-functions within the polynomial function, wherein each sub-function is configured to characterize the preference of a TE-LSP attribute.

12. The system of claim 11, wherein each sub-function includes a variable that characterizes a configurable weight applied to the attribute.

13. The system of claim 10, wherein the predetermined TE-LSP attributes comprise bandwidth and cost attributes.

14. The system of claim 10, wherein the weighted selection algorithm is based on predetermined prefix attributes of reaching the address prefix from a tail-end node of the TE-LSPs.

15. An apparatus for selecting a traffic engineering (TE) label switched path (LSP) from among a plurality of TE-LSPs, each TE-LSP spanning multiple domains of a computer network from a local domain to a remote domain in order to reach one or more address prefixes within the remote domain, the apparatus comprising:

means for executing a weighted selection algorithm at a head-end node of the local domain, the selection algorithm based on predetermined TE-LSP attributes of the inter-domain TE-LSPs and configured to select one or more appropriate TE-LSPs for the reachable address prefix by evaluation of an objective polynomial function for each of the TE-LSPs, the polynomial function configured to characterize the overall preference of the TE-LSPs, and selection of the one or more TE-LSPs with the highest overall preference to reach the address prefix in the remote domain; and

means for invoking load balancing, in cooperation with the weighted selection algorithm, to enable the head-end node to balance traffic loads among the one or more appropriate selected TE-LSPs.

16. A computer readable medium containing executable program instructions for selecting a traffic engineering (TE) label switched path (LSP) from among a plurality of TE-LSPs, each TE-LSP spanning multiple domains of a computer network from a local domain to a remote domain in order to reach one or more address prefixes within the remote domain, the executable program instructions comprising program instructions for:

executing a hierarchical selection algorithm at a head-end node of the local domain, the selection algorithm based on predetermined TE-LSP attributes of the inter-domain TE-LSPs and configured to select one or more appropriate TE-LSPs for the reachable address prefix by examination of attributes in a hierarchical manner by order of predetermined preference for each address prefix reachable by the TE-LSPs, and selection of one or more appropriate TE-LSPs for a preferred TE-LSP attribute to reach the address prefix in the remote domain; and

invoking load balancing, in cooperation with the hierarchical selection algorithm, to enable the head-end node to balance traffic loads among the one or more appropriate selected TE-LSPs.

21. A method comprising

executing a hierarchical selection algorithm, at a head-end node of a local domain, to select a traffic engineering (TE) label switched path (LSP) from among a plurality of TE-LSPs, each TE-LSP spanning multiple domains of a computer network from the local domain to a remote domain in order to reach one or more address prefixes within the remote domain, the hierarchical selection algorithm

examining predetermined TE-LSP attributes of the inter-domain TE-LSPs in a hierarchical manner by order of predetermined preference for each address prefix reachable by the TE-LSPs, and

selecting one or more appropriate TE-LSPs for a preferred TE-LSP attribute to reach the address prefix in the remote domain;

and

sending, by the head-end node, traffic over the one or more appropriate selected TE-LSPs.

22. A method comprising

executing a weighted selection algorithm, at a head-end node of a local domain, to select a traffic engineering (TE) label switched path (LSP) from among a plurality of TE-LSPs, each TE-LSP spanning multiple domains of a computer network from the local domain to a remote domain in order to reach one or more address prefixes within the remote domain, the weighted selection algorithm

evaluating an objective polynomial function for each of the TE-LSPs, the polynomial function configured to characterize the overall preference of the TE-LSPs, and

selecting the one or more TE-LSPs with the highest overall preference to reach the address prefix in the remote domain;

and

sending, by the head-end node, traffic over the one or more appropriate selected TE-LSPs.