Path selection in a network

• US 7,643,426 B1
• Filed: 04/27/2006
• Issued: 01/05/2010
• Est. Priority Date: 04/27/2006
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Banerjee, Sujata, Basu, Sujoy, Lee, Sung-Ju, Sharma, Puneet
• Primary Examiner(s): Ferris; Derrick W
• Assistant Examiner(s): YEUNG, MANG HANG
• Application Number:
  US11/412,442
• Time in Patent Office: 1,349 Days
• Field of Search: 370231-235, 370/238, 370/386, 370/252, 370/254, 370/395.21, 709/220, 709/225
• US Class Current: 370/238
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/128 for finding disjoint paths
• CPC Class Codes: H04L 45/64 using an overlay routing layer

Abstract

A path in a network is selected by selecting candidate overlay paths between two nodes in the network based on a static network metric determined for each of a plurality of overlay paths. A time sensitive network metric is determined for each of the candidate overlay paths, and a path is selected from the candidate overlay paths based on the time sensitive network metrics.

Claims

1. A method of selecting a path in a network, the method comprising:

determining a static network metric for each of a plurality of overlay paths between two nodes in the network, wherein the two nodes comprise a source node and a destination node, wherein the network is divided into a plurality of regions based on a network metric and the plurality of overlay paths include overlay nodes in a region of the plurality of regions of the network that also includes the source node;

selecting a subset of a plurality of overlay paths as candidate paths based on the determined static network metrics, and the selecting a subset of the plurality of overlay paths further includes determining whether any of the plurality of overlay paths is a candidate path of the candidate paths based on a comparison of the static network metrics for the plurality of overlay paths to a path switching threshold;

if no overlay paths including an overlay node from the region of the source node are selected as candidate paths, determining the static network metrics for a second plurality of overlay paths between the source node and the destination node, wherein the second plurality of overlay paths include overlay nodes in a neighboring region to the region of the source node; and

selecting a subset of the second plurality of overlay paths as candidate paths based on a comparison of the static network metrics for the second plurality of overlay paths to the path switching threshold;

determining a time sensitive network metric for each of the candidate paths; and

selecting by a device an overlay path from the candidate paths for transmitting data between the two nodes based on the determined time sensitive network metric for each of the candidate paths.

2. The method of claim 1, wherein selecting a subset of a plurality of overlay paths as candidate paths further comprises:

comparing the static network metrics for the plurality of overlay paths to a path switching threshold to select the subset of a plurality of overlay paths.

3. The method of claim 1, further comprising:

determining a snapshot including the static network metrics for the plurality of overlay paths; and

selecting a subset of a plurality of overlay paths as candidate paths comprises selecting the subset of the plurality of overlay paths using the static network metrics from the snapshot.

4. The method of claim 3, wherein the snapshot also comprises the time sensitive network metric for overlay paths in the network;

and

determining a time sensitive network metric for each of the candidate paths comprises determining the time sensitive metric for each of the candidate paths from the snapshot.

5. The method of claim 3, further comprising:

for each path of the plurality of overlay paths, measuring the static network metric when a change in an underlying path for the overlay path is detected; and

determining a snapshot of the static network metrics comprises determining the snapshot of the static network metrics using the static network metrics measured when the changes are detected.

6. The method of claim 1, wherein the static metric comprises capacity.

7. The method of claim 1, wherein the time sensitive metric comprises at least one of available bandwidth and latency.

8. The method of claim 1, wherein selecting a path from the candidate paths for transmitting data between the two nodes comprises:

selecting the path based on at least one other network metric for the candidate paths.

9. The method of claim 8 wherein the time sensitive metric comprises latency and the at least one other network metric comprises available bandwidth, the method further comprising:

determining an available bandwidth only for the candidate paths having a latency less than a predetermined threshold.

10. The method of claim 1, wherein a distributed information node is associated with each of the plurality of regions in the network and stores the static network metrics for nodes in an associated region, the method further comprising:

determining the static network metrics for the plurality of overlay paths from the static network metrics stored in the distributed information node for the region where the overlay nodes of the plurality of overlay paths reside; and

determining the static network metrics of the second plurality of overlay paths from the static network metrics stored in the distributed information node for the neighboring region.

11. The method of claim 1, wherein the two nodes comprise a source node and a destination node the method further comprising:

determining a bottleneck link in a currently used network path between the source node and the destination node; and

determining closest overlay nodes to a node at a head of the bottleneck link, wherein at some of the closest overlay nodes comprises overlay nodes in the candidate paths.

12. A computer program embedded on a non-transitory tangible computer readable storage medium, the computer program including instructions that when executed by a processor implement a method comprising:

selecting a subset of a plurality of overlay paths as candidate paths between two nodes in the network based on a static network metric determined for each of the plurality of overlay paths, wherein the two nodes comprise a source node and a destination node, wherein the network is divided into a plurality of regions based on a network metric and the plurality of overlay paths include overlay nodes in a region of the plurality of regions of the network that also includes the source node, and the selecting a subset of the plurality of overlay paths further includes

determining whether any of the plurality of overlay paths is a candidate path of the candidate paths based on a comparison of the static network metrics for the plurality of overlay paths to a path switching threshold;

if no overlay paths including an overlay node from the region of the source node are selected as candidate paths, determining the static network metrics for a second plurality of overlay paths between the source node and the destination node, wherein the second plurality of overlay paths include overlay nodes in a neighboring region to the region of the source node; and

selecting a subset of the second plurality of overlay paths as candidate paths based on a comparison of the static network metrics for the second plurality of overlay paths to the path switching threshold;

determining a time sensitive network metric for each of the candidate paths; and

selecting by a device a path from the candidate paths for transmitting data between the two nodes based on determined time sensitive network metrics.

13. The computer program of claim 12, wherein selecting a subset of a plurality of overlay paths as candidate paths further comprises:

comparing the static network metrics for the plurality of overlay paths to a path switching threshold to select the subset of a plurality of overlay paths.

14. The computer program of claim 12, wherein selecting a path from the candidate paths for transmitting data between the two nodes comprises:

selecting the path based on the available bandwidths and latency for each of the candidate paths.

15. The computer program of claim 12, wherein selecting a subset of a plurality of overlay paths as candidate paths comprises:

selecting the subset of the plurality of overlay paths as candidate paths based on capacities for the plurality of overlay paths.

16. The computer program of claim 12, wherein the two nodes comprise a source node and a destination node and the method further comprises:

determining a bottleneck link in a currently used network path between the source node and the destination node; and

determining closest overlay nodes to a node at a head of the bottleneck link, wherein at some of the closest overlay nodes comprises overlay nodes in the candidate paths.

17. A node in a network, the node comprising:

a memory storing a static network metric for each of a plurality of overlay paths and storing a time sensitive network metric for at least some of the overlay paths;

a processor operable to select a subset of the overlay paths as candidate paths for transmitting data to a destination node from a source node based on the stored static network metrics for the overlay paths,

wherein the network is divided into a plurality of regions based on a network metric and the plurality of overlay paths include overlay nodes in a region of the plurality of regions of the network that also includes the source node, and the selection of the candidate paths further includes

determining whether any of the plurality of overlay paths is a candidate path of the candidate paths based on a comparison of the static network metrics for the plurality of overlay paths to a path switching threshold;

if no overlay paths including an overlay node from the region of the source node are selected as candidate paths, determining the static network metrics for a second plurality of overlay paths between the source node and the destination node, wherein the second plurality of overlay paths include overlay nodes in a neighboring region to the region of the source node; and

selecting a subset of the second plurality of overlay paths as candidate paths based on a comparison of the static network metrics for the second plurality of overlay paths to the path switching threshold,

the processor being further operable to select an overlay path from the candidate paths as a new path for transmitting data to the destination node based on the stored time sensitive network metrics for the candidate paths.