INFORMATION PLANE FOR DETERMINING PERFORMANCE METRICS OF PATHS BETWEEN ARBITRARY END-HOSTS ON THE INTERNET

• US 20090122697A1
• Filed: 11/08/2007
• Published: 05/14/2009
• Est. Priority Date: 11/08/2007
• Status: Active Grant

• Current Assignee: University Of Massachusetts, University of Washington
• Original Assignee: University of Washington
• Inventors: Anderson, Thomas, Venkataramani, Arun, Madhyasha, Harsha V, Krisnamurty, Arvind
• Granted Patent: US 7,778,165 B2
• Time in Patent Office: Days
• US Class Current: 370/229
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/087 Jitter
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 43/50 Testing arrangements

Abstract

Performance metrics between any two arbitrary end-hosts are predicted based upon previous measurements on the Internet between a plurality of geographically dispersed vantage points and clusters of end-hosts. Each cluster comprises end-hosts that are related based upon their IP address prefixes. In response to a central agent that stores the measured data for each of a plurality of predicted paths on the Internet, the vantage points use traceroute software to measure and periodically update performance metrics such as latency, bottleneck capacity, bandwidth, and packet loss rate for links comprising the predicted paths between the vantage points and one (or more) destination points associated with each cluster, and gather such data using distributed application systems. A user or client application can subsequently request predicted performance metrics for communication between specific end-hosts, based upon the previous measurement data.

Claims

1. A method for automatically predicting performance metrics for communication between any two arbitrary end-hosts on a network, comprising the steps of:

(a) initiating measurements of the network from a plurality of geographically distributed vantage points, each vantage point comprising a computing device that is coupled to the network;

(b) using traceroute data obtained for links between a plurality of destination points on the network and the plurality of vantage points, automatically inferring information defining a structure of the network;

(c) using the traceroute data, automatically determining routing policies applied by routers on the network during communication between the plurality of vantage points and the plurality of destination points;

(d) automatically determining the performance metrics for each link identified by the traceroute data;

(e) employing the information defining the structure, and the routing policies to predict paths between any arbitrary end-hosts on the network; and

(f) determining the performance metrics for links comprising each predicted path in the network.

2. The method of claim 1, further comprising the step of automatically selecting the plurality of destination points so that each destination point of the plurality of destination points represents a cluster of end-hosts on the network, each cluster including end-hosts selected as a function of network addresses assigned to the end-hosts.

3. The method of claim 2, further comprising the step of accessing routing tables employed by routers on the network, to define the clusters of end-hosts represented by the plurality of destination points.

4. The method of claim 3, further comprising the steps of:

(a) enabling a user to select two arbitrary end-hosts on the network, in order to enable prediction of the performance metrics for communication between the two arbitrary end-hosts that were selected;

(b) identifying clusters that include the two arbitrary end-hosts that were selected;

(c) automatically selecting a most likely path between the destination points representing the clusters that were identified; and

(d) using the performance metrics previously determined for the links comprising the most likely path to predict the performance metrics for communication between the two arbitrary end-hosts that were selected.

5. The method of claim 4, wherein the step of selecting the most likely path comprises the step of automatically selecting a path where a latency from a source to a point where the path from the source exits a first-hop AS is a minimum.

6. The method of claim 1, further comprising the step of clustering the routers handling the links on the network by identifying routers that are at a common location and are operated by a common autonomous system.

7. The method of claim 1, further comprising the step of resolving aliases for routers on the network, to reduce the number of routers handling different links.

8. The method of claim 1, wherein the step of predicting the performance metrics for each of the predicted paths comprises the steps of:

(a) evaluating network latencies for each link of the predicted path connecting a vantage point to a destination point, for each vantage point and each destination point; and

(b) storing the network latency for each link.

9. The method of claim 1, wherein the step of predicting the performance metrics for each of the predicted paths comprises the steps of:

(a) measuring a bandwidth of each link of the predicted path connecting a vantage point to a destination point, for each vantage point and each destination point; and

(b) storing the bandwidth for each link.

10. The method of claim 1, wherein the step of predicting the performance metrics for each of the predicted paths comprises the steps of:

(a) measuring a packet loss rate of each link of the predicted path connecting a vantage point to a destination point, for each vantage point and each destination point; and

(b) storing the packet loss rate of each link.

11. A system for automatically predicting performance metrics for communication between any two arbitrary end-hosts on a network, comprising:

(a) a memory in which machine instructions and data are stored;

(b) a network interface for communicating over the network; and

(c) a processor that is coupled to the memory and the network interface, the processor executing the machine instructions to carry out a plurality of functions, including;

(i) initiating measurements of the network from a plurality of geographically distributed vantage points, each vantage point comprising a computing device that is coupled to the network, the processor communicating with the computing device at each vantage point over the network through the network interface;

(ii) using traceroute data obtained over the network for links between a plurality of destination points on the network and the plurality of vantage points, automatically inferring information defining a structure of the network;

(iii) using the traceroute data, automatically determining routing policies applied by routers on the network during communication between the plurality of vantage points and the plurality of destination points;

(iv) automatically determining the performance metrics for each link identified by the traceroute data;

(v) employing the information defining the structure, and the routing policies to predict paths between any arbitrary end-hosts on the network; and

(vi) determining the performance metrics for links comprising each predicted path in the network.

12. The system of claim 11, wherein the machine instructions executed by the processor further cause the processor to select the plurality of destination points so that each destination point represents a cluster of end-hosts on the network, each cluster including end-hosts selected as a function of network addresses assigned to the end-hosts.

13. The system of claim 12, wherein the machine instructions executed by the processor further cause the processor to access routing tables employed by the routers on the network to define the clusters of end-hosts represented by the plurality of destination points.

14. The system of claim 13, wherein the machine instructions executed by the processor further cause the processor to:

(a) enable a user to select two arbitrary end-hosts on the network, to enable the performance metrics to be predicted for communication between the two arbitrary end-hosts that were selected;

(b) identify clusters that include the two arbitrary end-hosts that were selected;

(c) automatically select a most likely path between the destination points representing the clusters that were identified; and

(d) use the performance metrics previously determined for the links comprising the most likely path to predict the performance metrics for communication between the two arbitrary end-hosts that were selected.

15. The system of claim 14, wherein the machine instructions executed by the processor further cause the processor to select the most likely path by automatically selecting a path where a latency from a source to a point where the path from the source exits a first-hop AS is a minimum.

16. The system of claim 11, wherein the machine instructions executed by the processor further cause the processor to cluster the routers handling the links on the network by identifying routers that are at a common location and are operated by a common autonomous system.

17. The system of claim 11, wherein the machine instructions executed by the processor further cause the processor to resolve aliases for routers on the networks, to reduce the number of routers handling different links.

18. The system of claim 11, wherein the machine instructions executed by the processor cause the processor to predict the performance metrics for each of the predicted paths by evaluating network latencies for each link of the predicted path connecting a vantage point to a destination point, for each vantage point and each destination point, and then store the network latency for each link in the memory.

19. The system of claim 11, wherein the machine instructions executed by the processor cause the processor to predict the performance metrics for each of the predicted paths by measuring a bandwidth of each link of the predicted path connecting a vantage point to a destination point, and then store the bandwidth for each link in the memory.

20. The system of claim 11, wherein the machine instructions executed by the processor cause the processor to predict the performance metrics for each of the predicted paths by measuring a packet loss rate of each link of the predicted path connecting a vantage point to a destination point, for each vantage point and each destination point, and then store the packet loss rate of each link in the memory.

21. The system of claim 11, wherein each of the plurality of vantage points comprises a virtual machine that is running on a computing device and is accessible over the network.

22. A memory medium on which are stored machine readable and executable instructions, which when executed by a processor, cause the processor to carry out a plurality of functions used for automatically predicting performance metrics for communication between any two arbitrary end-hosts on a network, the functions including:

(a) initiating measurements of the network from a plurality of geographically distributed vantage points, each vantage point comprising a computing device that is coupled to the network;

(b) using traceroute data obtained for links between a plurality of destination points on the network and the plurality of vantage points, automatically inferring information defining a structure of the network;

(c) using the traceroute data, automatically determining routing policies applied by routers on the network during communication between the plurality of vantage points and the plurality of destination points;

(d) automatically determining the performance metrics for each link identified by the traceroute data;

(e) employing the information defining the structure, and the routing policies to predict paths between any arbitrary end-hosts on the network; and

(f) determining the performance metrics for links comprising each predicted path in the network.

23. The memory medium of claim 22, wherein the machine readable and executable instructions, when executed by a processor, further cause the processor to automatically select the plurality of destination points so that each destination point of the plurality of destination points represents a cluster of end-hosts on the network, each cluster including end-hosts selected as a function of network addresses assigned to the end-hosts.

24. The memory medium of claim 23, wherein the machine readable and executable instructions, when executed by a processor, further cause the processor to access router tables employed by routers on the network, to define the clusters of end-hosts represented by the plurality of destination points.

25. The memory medium of claim 24, wherein the machine readable and executable instructions, when executed by a processor, further cause the processor to:

(a) enable a user to select two arbitrary end-hosts on the network, in order to enable prediction of the performance metrics for communication between the two arbitrary end-hosts that were selected;

(b) identify clusters that include the two arbitrary end-hosts that were selected;

(c) automatically select a most likely path between the destination points representing the clusters that were identified; and

(d) use the performance metrics previously determined for the links comprising the most likely path to predict the performance metrics for communication between the two arbitrary end-hosts that were selected.