Patent ID: 7778165

Claim:
A method for automatically predicting performance metrics for communication between any two arbitrary end-hosts on a network in response to a query, 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) using a central computing device that is also coupled to the network, for coordinating the determination of the performance metrics for communications between the vantage points and selected destination points, the central computing device automatically determining the performance metrics for each link identified by the traceroute data; (e) upon receiving a query that specifies a source and a destination of a communication link over the network, employing the information defining the structure, and the routing policies to predict a path between the source and the destination that were specified in the query; and (f) in response to the query, determining and returning the performance metrics for links between the source and the destination comprising the predicted path in the network, the step of determining the performance metrics further including the step of growing a frontier rooted at each vantage point, each vantage point measuring only links within the frontier rooted at the vantage point, the central computing device performing in parallel a breadth-first-search of traceroute paths originating at each vantage point, the central computing device assigning links to the vantage point found in the breadth-first-search that are not yet assigned to another vantage point, and the central computing device continuing the breadth-first-search and link assignment process until all link measurements have been assigned to a vantage point.