Virtual connection route selection apparatus and techniques

• US 8,345,552 B2
• Filed: 02/27/2007
• Issued: 01/01/2013
• Est. Priority Date: 02/27/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Dolganow, Andrew, Aissaoui, Mustapha
• Primary Examiner(s): Thier, Michael
• Assistant Examiner(s): LOUIS, VINNCELAS
• Application Number:
  US11/679,582
• Publication Number:
  US 20080205271A1
• Time in Patent Office: 2,135 Days
• Field of Search: 370/216, 370/221, 370/225, 370/228, 370/231, 370/238, 370/232, 370/255, 370/409, 370/227, 370/400, 709/225, 709/223, 709/238, 365/185.29
• US Class Current: 370/235
• 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/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/44 Distributed routing
• 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

Abstract

Virtual connection route selection apparatus and techniques are disclosed. At a communication traffic routing apparatus, metric information associated with multiple different routes for a virtual connection, such as a PseudoWire, toward a destination is collected. The metric information may be collected from one or more remote route computation elements capable of computing routes for virtual connections between the routing apparatus and other routing apparatus over an underlying communication system, or during actual establishment of the virtual connections, for example. An initial or re-optimized route for a virtual connection can then be selected at the routing apparatus based on the collected metric information. In some embodiments, although the virtual connection routes are paths computed by Path Computation Elements (PCEs), actual path selection decisions are distributed to routers.

Claims

1. A communication traffic routing apparatus comprising:

a metric information collector operable to collect, from metric information generated by at least one remote route computation element that is capable of computing routes for virtual connections between the routing apparatus and other routing apparatus over an underlying communication system, metric information associated with a plurality of different computed routes for a virtual connection with a destination; and

a selection module operatively coupled to the metric information collector and operable to select, from the different computed routes, based on the collected metric information, a route for a virtual connection with the destination,

the different computed routes comprising a currently selected route of an existing virtual connection that has been established with the destination; and

the selection module being operable to re-optimize the currently selected route by selecting, based on the collected metric information, between the currently selected route and another one of the different computed routes that provides at least a minimum margin of improvement over the currently selected route,

wherein the at least one remote route computation element comprises a route computation element that applies an optimal route selection mechanism to its generated metric information, and the selection module applies a different optimal route selection mechanism to the collected metric information.

2. The routing apparatus of claim 1, further comprising:

an interface operatively coupled to the metric information collector and operable to enable the routing apparatus to communicate with the at least one remote route computation element,

wherein the metric information collector is operable to collect metric information by receiving the metric information from the at least one remote route computation element through the interface.

3. The routing apparatus of claim 2, wherein the metric information collector is further operable to receive through the interface, from any of the at least one remote route computation element, information indicative of each of the different computed routes.

4. The routing apparatus of claim 1, wherein each of the at least one remote route computation element comprises a Path Computation Element (PCE) for computing Label Switched Paths (LSPs), and wherein the metric information collector comprises a Path Computation Client (PCC).

5. The routing apparatus of claim 1, wherein the virtual connections comprise PseudoWires.

6. The routing apparatus of claim 5, further comprising:

an interface operatively coupled to the metric information collector and operable to enable the metric information collector to communicate with the at least one remote route computation element,

wherein the metric information collector is operable to collect metric information by receiving the metric information through the interface, from the at least one remote route computation element.

7. The routing apparatus of claim 5, further comprising:

a routing module operatively coupled to the metric information collector and operable to cause any of the PWs to be established,

wherein the metric information collector is further operable to collect metric information associated with a PW route of each of the PWs during establishment of the PWs.

8. The routing apparatus of claim 7, wherein the routing module is further operable to cause each established PW having a PW route other than the PW route selected by the selection module for subsequently exchanging communication traffic with the destination to be released.

9. The routing apparatus of claim 1, wherein at least one of the virtual connections comprises a multi-segment virtual connection having a plurality of segments.

10. The routing apparatus of claim 1, wherein the metric information associated with each computed route of the plurality of different computed routes comprises information indicative of a route cost.

11. The routing apparatus of claim 1, wherein the metric information associated with each computed route of the plurality of different computed routes comprises information indicative of cumulative delay to reach the destination from the routing apparatus over each computed route.

12. The routing apparatus of claim 1, wherein the metric information associated with each computed route of the plurality of different computed routes comprises information indicative of an amount of available bandwidth on each computed route after establishing the virtual connection over the computed route.

13. The routing apparatus of claim 1, wherein the selection module is operable to select the route for the virtual connection with the destination based on a combination of metric information for different metrics.

14. The routing apparatus of claim 13, wherein the combination of metric information comprises a weighted combination.

15. The routing apparatus of claim 1, wherein the at least one remote route computation element comprises a plurality of remote route computation elements in respective different communication system administrative boundaries.

16. The routing apparatus of claim 1, wherein the minimum margin of improvement comprises a minimum margin of improvement in a metric for which the collected metric information is collected.

17. A method comprising:

collecting at a routing apparatus, from metric information generated by at least one remote route computation element that is capable of computing routes for virtual connections between the routing apparatus and other routing apparatus over an underlying communication system, metric information associated with a plurality of different computed routes for a virtual connection with a destination; and

selecting at the routing apparatus, from the different computed routes, based on the collected metric information, a route for a virtual connection with the destination,

the different computed routes comprising a currently selected route of an existing virtual connection that has been established with the destination; and

the selecting comprising re-optimizing the currently selected route by selecting, based on the collected metric information, between the currently selected route and another one of the different computed routes that provides at least a minimum margin of improvement over the currently selected route,

wherein the at least one remote route computation element comprises a route computation element that applies an optimal route selection mechanism to its generated metric information, and wherein the selecting comprises applying a different optimal route selection mechanism to the collected metric information.

18. The method of claim 17, wherein collecting comprises receiving the metric information from the at least one remote route computation element.

19. The method of claim 17, wherein each of the at least one remote route computation element comprises a Path Computation Element (PCE) for computing Label Switched Paths (LSPs), and wherein receiving comprises receiving the metric information at a Path Computation Client (PCC) of the routing apparatus.

20. The method of claim 17, wherein the metric information associated with each computed route of the plurality of different computed routes comprises information indicative of at least one of:

a route cost, cumulative delay to reach the destination from the routing apparatus over each computed route, and an amount of available bandwidth on each computed route after establishing the virtual connection over the computed route.

21. A method comprising:

The method of claim 17, wherein the virtual connections comprise PseudoWires (PWs).