Topology aware route control

• US 7,584,298 B2
• Filed: 12/12/2003
• Issued: 09/01/2009
• Est. Priority Date: 12/13/2002
• Status: Active Grant

• Current Assignee: Internap Holding LLC
• Original Assignee: Internap Network Services Corporation
• Inventors: Crabbe, Edward, Johnson, Jeremy T., Klinker, Eric, Grady, Brian Douglas
• Primary Examiner(s): Jean; Frantz B
• Application Number:
  US10/735,589
• Publication Number:
  US 20060182034A1
• Time in Patent Office: 2,090 Days
• Field of Search: 709/238, 709/239, 709/242, 709/223, 370/229, 370/232, 370/235
• US Class Current: 709/238
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/12 Network monitoring probes
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/1283 with disjoint links
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/247 using M:N active or standby paths
• CPC Class Codes: H04L 45/3065 for real time traffic
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/70 Routing based on monitoring results

Abstract

The present invention uses proxy points for measuring different routes to a destination address space. Multiple paths to the desired destination address space are identified. Each path begins at a source and terminates at the destination address space. Proxy points are identified for each path and are associated with a point between the source and the destination address space. Measurements of the path performance from each source to the appropriate proxy point are compared to determine an optimum route.

Claims

1. A method for analyzing routes to a destination address space, comprising:

identifying a plurality of paths, each path beginning at a different source and terminating at a common destination address space;

identifying a plurality of nodes for each of the plurality of paths;

identifying at least one convergence point between at least two of the paths, wherein the convergence point is a common node for the at least two paths, said at least two paths being non-diverse from the convergence point to the destination address space;

associating the convergence point with the destination address space;

determining a path performance for each of the at least two paths, wherein the path performance is based on a path performance from the source of each path to the convergence point; and

analyzing the at least two paths to the destination address space.

2. The method of claim 1, wherein analyzing the at least two paths to the destination address space, comprises selecting a route to the destination address space based upon the relative path performances for the at least two paths.

3. The method of claim 2, wherein the at least two paths include a first path and a second path and wherein selecting a route to the destination address space based upon the relative path performances for the at least two paths comprises selecting the first path, further comprising:

determining a current path performance for the first path;

comparing the current path performance to the path performance for the first path; and

based upon the comparison, selecting the second path as the route to the destination address space.

4. The method of claim 1, wherein analyzing the at least two paths to the destination address space, comprises determining diversity for the at least two paths.

5. The method of claim 4, further comprising analyzing path length for the at least two paths.

6. The method of claim 1, wherein analyzing the at least two paths to the destination address space provides network topology information that is used in connection with network planning activities.

7. The method of claim 1, wherein analyzing the at least two paths to the destination address space provides information used to evaluate distance and volume for a plurality of destinations, including the destination address space.

8. The method of claim 1, further comprising:

periodically determining the path performance for each of the at least two paths.

9. The method of claim 1, further comprising:

determining an aggregated address space that includes the destination address space and that is associated with the convergence point.

10. The method of claim 1, further comprising:

determining an aggregated address space that includes the destination address space, that is associated with multiple convergence points and that shares a common next hop.

11. The method of claim 1 wherein identifying a plurality of paths comprises using an active path trace probe.

12. The method of claim 1 wherein identifying a plurality of paths comprises using a passive flow analyzer.

13. The method of claim 1, wherein the at least two paths include a first path, further comprising:

associating the convergence point with additional destination address spaces; and

obtaining path performance information for the destination address space and the additional destination address spaces using a single measurement of the first path.

14. The method of claim 1, wherein the plurality of paths pass through at least one public Internet Protocol network.

15. The method of claim 14 wherein the at least one Internet Protocol network is a network of an Internet Service Provider.

16. The method of claim 14 wherein the at least one Internet Protocol network is a Local Area Network.