Topology aware route control

• US 20060182034A1
• Filed: 12/12/2003
• Published: 08/17/2006
• Est. Priority Date: 12/13/2002
• Status: Active Grant

• Current Assignee: Internap Holding LLC
• Original Assignee: Internap Network Services Corporation
• Inventors: Klinker, Eric, Crabbe, Edward, Johnson, Jeremy T., Grady, Brian Douglas
• Granted Patent: US 7,584,298 B2
• Time in Patent Office: Days
• US Class Current: 370/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 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;

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;

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

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

identifying a plurality of paths, including a first path that begins at a first source and terminates at the destination address space and a second path that begins at a second source and terminates at the destination address space;

identifying a first proxy point for the first path and a second proxy point for the second path, wherein the first proxy point is an intermediate point between the first source and the destination address space and the second proxy point is an intermediate point between the second source and the destination address space;

associating the first proxy point and the second proxy point with the destination address space;

determining a path performance for the first path and the second path, wherein the path performances are based on a path performance from the source of each path to the proxy point for each path; and

analyzing the first path and the second path.

15. The method of claim 14, wherein analyzing the first path and the second path comprises:

selecting a route to the destination address space based upon the relative path performances for the first path and the second path.

16. The method of claim 14, wherein a portion of the first path from the first source to the first proxy point and a portion of the second path from the second source to the second proxy point are diverse.

17. The method of claim 14, further comprising:

determining an aggregated address space that includes the destination address space and is associated with the first proxy point and the second proxy point.

18. The method of claim 14, wherein the first source is associated with a router.

19. The method of claim 14, wherein the first source is associated with a single entity.

20. The method of claim 14, wherein the first source is associated with a location.

21. The method of claim 14, wherein the first proxy point and the second proxy point are located within a diverse portion of a network.

22. The method of claim 14, wherein analyzing the first path and the second path comprises determining diversity for the first path and the second path.

23. The method of claim 22, further comprising analyzing path length for the first path and the second path.

24. The method of claim 14, wherein analyzing the first path and the second path provides network topology information and is used in connection with network planning activities.

25. The method of claim 14, wherein analyzing the first path and the second path provides information used to evaluate distance and volume for a plurality of destinations, including the destination address space.

26. The method of claim 14, further comprising:

associating the first proxy point with additional destination address spaces;

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