Technique for efficiently routing IP traffic on CE-CE paths across a provider network

• US 7,522,603 B2
• Filed: 03/14/2006
• Issued: 04/21/2009
• Est. Priority Date: 03/14/2006
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe
• Primary Examiner(s): ABELSON, RONALD B
• Application Number:
  US11/375,216
• Publication Number:
  US 20070217419A1
• Time in Patent Office: 1,134 Days
• Field of Search: 370/238, 370/238.1, 370/252
• US Class Current: 370/392
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/44 Distributed routing

Abstract

A technique efficiently routes Internet Protocol (IP) traffic on paths between customer edge devices (CEs) across a provider network (“CE-CE paths”) in a computer network. According to the novel technique, a path computation element (PCE), e.g., a provider edge device (PE), may learn dynamic link attribute information of remote links from the provider network to one or more remote CEs (e.g., “PE-CE links” or “CE-PE links”). A multi-homed requesting CE requests from the PCE a set of CE-CE path metrics (e.g., costs) to one or more remote destination address prefixes, e.g., via each multi-homed CE-PE link from the requesting CE. In response to the request, the PCE computes the set of available CE-CE paths and current metrics to the remote destination address prefixes and returns the corresponding CE-CE path metrics to the requesting CE. The requesting CE modifies its IP forwarding entries accordingly in order to perform IP traffic routing corresponding to the CE-CE path metrics (e.g., asymmetrical load balancing) across its multi-homed CE-PE links.

Claims

1. A method for efficiently routing Internet Protocol (IP) traffic on paths between customer edge devices (CEs) across a provider network (“

CE-CE paths”

) in a computer network, the method comprising;

requesting from a path computation element (PCE), at a multi-homed CE, a set of CE-CE path metrics to one or more remote destination address prefixes;

in response, computing, at the PCE, a set of available CE-CE paths and current metrics to the remote destination address prefixes;

returning the corresponding CE-CE path metrics to the requesting CE; and

utilizing the CE-CE path metrics to load balance, by the requesting CE, IP traffic across links coupled to the requesting CE.

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

learning, at the PCE, dynamic link attribute information of remote links from the provider network to one or more remote CEs.

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

learning, at the PCE, dynamic link attribute information of links of the provider network.

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

modifying IP forwarding entries of the requesting CE accordingly in order to perform IP traffic routing corresponding to the CE-CE path metrics.

5. The method as in claim 4, wherein utilizing the CE-CE path to load balance comprises:

an operation selected from the group comprising;

asymmetrically load balancing according to the corresponding CE-CE path metrics;

selecting a best path;

removing a worst path and load balancing traffic on remaining paths; and

removing any paths having CE-CE path metrics configurably worse than a best path and load balancing traffic on remaining paths.

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

specifying the remote destination address prefixes in an access control list (ACL) of a request message.

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

requesting the set of CE-CE path metrics by a Path Computation Element (PCE) Communication Protocol (PCEP) request message.

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

returning corresponding CE-CE path metrics to the requesting CE selected from a group comprising;

path costs;

utilized bandwidth;

link utilization; and

weighted values corresponding to path metrics.

9. The method as in claim 1, wherein the step of requesting further comprises:

requesting from the PCE, at the multi-homed CE, a set of CE-CE path metrics to one or more remote destination address prefixes along CE-CE paths that meet a set of requested path attributes.

10. The method as in claim 9, wherein the requested path attributes are selected from a group comprising:

a maximum number of paths;

diversity;

maximum cost; and

maximum delay.

11. The method as in claim 9, wherein the corresponding CE-CE path metrics returned to the requesting CE are selected from a group comprising:

CE-CE path metrics corresponding to CE-CE paths that meet the set of requested path attributes;

CE-CE path metrics corresponding to all CE-CE paths, along with an indication of CE-CE paths that do not meet the set of requested path attributes; and

CE-CE path metrics corresponding to all CE-CE paths, along with an indication of corresponding requested path attributes for each of the CE-CE paths.

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

in response to receiving a request from the CE, determining at the PCE whether to process the request based on one or more policies prior to computing the set of available CE-CE paths and current metrics.

13. The method as in claim 12, wherein the one or more policies define rules selected from a group comprising:

dampening the requests;

allowing requests from selected CEs;

allowing requests to selected destination address prefixes;

denying requests from selected CEs; and

denying requests to selected destination address prefixes.

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

in response to determining at the PCE not to process the request based on one or more policies, performing an action selected from a group comprising;

rejecting the request;

notifying the requesting CE of one or more policy violations; and

ignoring the request.

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

computing, at the PCE, the set of available CE-CE paths and current metrics to the remote destination address prefixes by i) selecting a set of provider edge devices (PEs) having advertised routes to the remote destination address prefixes, and ii) computing a set of best CE-CE paths and respective metrics to each PE of the set.

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

storing, at the PCE, received requests along with corresponding computed CE-CE paths and current metrics;

returning the stored CE-CE path metrics to the requesting CE in the event there are no changes to the CE-CE paths and metrics; and

returning re-computed CE-CE path metrics to the requesting CE in the event there are changes to the CE-CE paths and metrics.

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

requesting, at the requesting CE, that the PCE update the requesting CE of changes to CE-CE path metrics; and

returning re-computed CE-CE path metrics to the requesting CE in the event there are changes to the CE-CE paths and metrics.

18. The method as in claim 1, wherein the step of requesting further comprises:

requesting from the PCE, at the requesting CE, a set of CE-CE path metrics to one or more remote destination address prefixes, the requested set comprising CE-CE path metrics for a single best CE-CE path.

19. The method as in claim 1, wherein the PCE is a provider edge device (PE) locally attached to the requesting CE.

20. The method as in claim 1, wherein the PCE is an ingress PCE, the method further comprising:

requesting from an egress PCE, at the ingress PCE, a set of remote PE-CE path metrics to the remote destination address prefixes;

in response, computing, at the egress PCE, a set of available remote PE-CE paths and current metrics to the remote destination address prefixes; and

returning the corresponding remote PE-CE path metrics to the ingress PCE;

wherein the ingress PCE computes the set of available CE-CE paths and current metrics to the remote destination address prefixes based on the returned remote PE-CE paths and current metrics.

21. A system for efficiently routing Internet Protocol (IP) traffic on paths between customer edge devices (CEs) across a provider network (“

CE-CE paths”

) in a computer network, the system comprising;

means for requesting from a path computation element (PCE), at a multi-homed CE, a set of CE-CE path metrics to one or more remote destination address prefixes;

in response, means for computing, at the PCE, a set of available CE-CE paths and current metrics to the remote destination address prefixes;

means for returning the corresponding CE-CE path metrics to the requesting CE; and

means for utilizing the CE-CE path metrics to load balance, at the requesting CE, IP traffic across links coupled to the requesting CE.

22. The system as in claim 21, further comprising:

means for learning, at the PCE, dynamic link attribute information of remote links from the provider network to one or more remote CEs.

23. The system as in claim 21, further comprising:

means for modifying IP forwarding entries of the requesting CE accordingly in order to perform IP traffic routing corresponding to the CE-CE path metrics.

24. A computer readable medium containing executable program instructions for efficiently routing Internet Protocol (IP) traffic on paths between customer edge devices (CEs) across a provider network (“

CE-CE paths”

) in a computer network, the executable program instructions comprising program instructions for;

requesting from a path computation element (PCE), at a multi-homed CE, a set of CE-CE path metrics to one or more remote destination address prefixes;

in response, computing, at the PCE, a set of available CE-CE paths and current metrics to the remote destination address prefixes;

returning the corresponding CE-CE path metrics to the requesting CE; and

utilizing the CE-CE path metrics to load balance, by the requesting CE, IP traffic across links coupled to the requesting CE.

25. The computer readable medium as in claim 24, the executable program instructions further comprising program instructions for:

learning, at the PCE, dynamic link attribute information of remote links from the provider network to one or more remote CEs.

26. The computer readable medium as in claim 24, the executable program instructions further comprising program instructions for:

modifying IP forwarding entries of the requesting CE accordingly in order to perform IP traffic routing corresponding to the CE-CE path metrics.

27. A node adapted to efficiently route Internet Protocol (IP) traffic on paths between customer edge devices (CEs) across a provider network (“

CE-CE paths”

) in a computer network, the node comprising;

one or more network interfaces;

a processor coupled to the one or more network interfaces and adapted to execute software processes; and

a memory adapted to store a Path Computation Element (PCE) process executable by the processor, the PCE process configured to;

i) receive from a multi-homed requesting CE, a request for a set of CE-CE path metrics to one or more remote destination address prefixes, ii) in response, compute a set of available CE-CE paths and current metrics to the remote destination address prefixes, iii) return the corresponding CE-CE path metrics to the requesting CE to allow the requesting CE to load balance IP traffic across links of the requesting CE.

28. The node as in claim 27, the PCE process further configured to:

learn dynamic link attribute information of remote links from the provider network to one or more remote CEs.

29. A node configured to efficiently route Internet Protocol (IP) traffic on paths between customer edge devices (CEs) across a provider network (“

CE-CE paths”

) in a computer network, the node comprising;

two or more network interfaces, the network interfaced multi-homed to the provider network;

a processor coupled to the network interfaces and adapted to execute software processes; and

a memory adapted to store one or more IP forwarding entries corresponding to the network interfaces, the memory also adapted to store a customer edge device (CE) process executable by the processor, the CE process configured to;

i) request from a Path Computation Element (PCE) a set of CE-CE path metrics to one or more remote destination address prefixes, ii) receive from the PCE returned corresponding CE-CE path metrics, and iii) modify IP forwarding entries accordingly in order to load balance IP traffic on the paths corresponding to the CE-CE path metrics.