1461096062-472f754f-360f-4553-a619-efc074bb0715

1. A method for efficiently routing Internet Protocol (IP) traffic on paths between customer edge devices (CEs) across a provider network (\u201cCE-CE paths\u201d) 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 (\u201cCE-CE paths\u201d) 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 (\u201cCE-CE paths\u201d) 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 (\u201cCE-CE paths\u201d) 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 (\u201cCE-CE paths\u201d) 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.

The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.

1. A method comprising:
receiving a plurality of flows, each flow comprising a plurality of packets, a first flow comprising a plurality of first packets, each first packet having the same source-destination address pair as the other first packets, a second flow comprising a plurality of second packets, each second packet having the same source-destination address pair as the other second packets; and
performing the following for each flow:
identifying a virtual path of a plurality of virtual paths for the each flow, each virtual path having a corresponding path record stored in a memory;
accessing the path record corresponding to the virtual path;
allocating one or more packet buffers to the each flow according to the corresponding path record;

determining, from a priority field of the path record of the virtual path of the first flow, a specific number of packets to send from the virtual path of the first flow before sending any packets from a next virtual path listed on a transmit list of virtual paths with packets pending for transmission, wherein the next virtual path is the virtual path of the second flow, the priority field of the path record designating the specific number;
sending the specific number of first packets before sending any of the second packets;
receiving a next packet;
determining that the next packet is not associated with a path record stored in the memory;
generating a new path record to process the next packet; and
storing the new path record in the memory, wherein if the memory has insufficient space to store the new path record, one or more of the plurality of path records are removed from the memory before storing the new path record.
2. The method of claim 1, further comprising:
receiving a next packet;
identifying a next virtual path of a plurality of virtual paths for the next packet; and
buffering the next packet in the one or more packet buffers allocated to the next virtual path.
3. The method of claim 1, the performing the following for each flow further comprising:
allocating bandwidth to the each flow according to the path record.
4. The method of claim 1, the performing the following for each flow further comprising:
controlling a flow between a plurality of network nodes according to the path record.
5. The method of claim 1, the performing the following for each flow further comprising:
selecting a multicast mode for the each flow according to the path record.
6. The method of claim 1, the performing the following for each flow further comprising:
selecting a snoop mode for the each flow according to the path record.
7. The method of claim 1, further comprising:
receiving a packet of a flow;
determining from the path record of the virtual path of the flow that the virtual path is in a snoop mode; and
sending a copy of the packet to a CPU for processing.
8. The method of claim 1, the performing the following for each flow further comprising:
selecting a priority for the each flow according to the path record.
9. An apparatus comprising:
one or more ports configured to receive a plurality of flows, each flow comprising a plurality of packets, a first flow comprising a plurality of first packets, each first packet having the same source-destination address pair as the other first packets, a second flow comprising a plurality of second packet, each second packet having the same source-destination address pair as the other second packets; and
switch hardware configured to perform the following for each flow:
identify a virtual path of a plurality of virtual paths for the each flow, each virtual path having a corresponding path record stored in a memory;
access the path record corresponding to the virtual path;
allocate one or more packet buffers to the each flow according to the corresponding path record;

determine, from a priority field of the path record of the virtual path of the first flow, a specific number of packets to send from the virtual path of the first flow before sending any packets from a next virtual path listed on a transmit list of virtual paths with packets pending for transmission, wherein the next virtual path is the virtual path of the second flow, the priority field of the path record designating the specific number;
send the specific number of first packets before sending any of the second packets;
receive a next packet;
determine that the next packet is not associated with a path record stored in the memory;
generate a new path record to process the next packet; and
store the new path record in the memory, wherein if the memory has insufficient space to store the new path record, one or more of the plurality of path records are removed from the memory before storing the new path record.
10. The apparatus of claim 9:
the one or more ports configured to:
receive a next packet; and

the switch hardware configured to:
identify a next virtual path of a plurality of virtual paths for the next packet; and
buffer the next packet in the one or more packet buffers allocated to the next virtual path.
11. The apparatus of claim 9, the switch hardware configured to perform the following for each flow:
allocate bandwidth to the each flow according to the path record.
12. The apparatus of claim 9, the switch hardware configured to perform the following for each flow:
control a flow between a plurality of network nodes according to the path record.
13. The apparatus of claim 9, the switch hardware configured to perform the following for each flow:
select a multicast mode for the each flow according to the path record.
14. The apparatus of claim 9, the switch hardware configured to perform the following for each flow:
select a snoop mode for the each flow according to the path record.
15. The apparatus of claim 9:
the one or more ports configured to:
receive a packet of a flow; and

the switch hardware configured to:
determine from the path record of the virtual path of the flow that the virtual path is in a snoop mode; and
send a copy of the packet to a CPU for processing.
16. The apparatus of claim 9, the switch hardware configured to perform the following for each flow:
select a priority for the each flow according to the path record.