Path Reconstruction and Interconnection Modeling (PRIM)

Abstract

Internet data such as Border Gateway Protocol routing information and traceroute measurements are processed to create realistic predictive models of the paths IP traffic is likely to take between any two points on the Internet, even when direct measurements of the paths is not feasible. The prediction includes three categories: topology (what paths may exist), weighting (which paths are more or less likely to be taken under varying operational circumstances), and performance (latency, loss, jitter, etc. across the predicted paths).

What is claimed is: 
     
         1 . A method comprising:
 obtaining a plurality of round-trip latency measurements between each of a plurality of router interfaces in the computer network and each of a plurality of collectors;   generating a graph based on the round-trip latency measurements, the graph having a plurality of nodes and a plurality of edges, each node in the plurality of nodes representing a corresponding router interface in the plurality of router interfaces and each edge in the plurality of edges representing a corresponding path between a pair of router interfaces in the plurality of router interfaces;   creating a model of latency across each edge in the plurality of edges; and   predicting performance of a path between the first endpoint and the second endpoint based on the model of latency,   wherein the method is performed by at least one device including a hardware processor.   
     
     
         2 . The method of  claim 1 , wherein obtaining the plurality of round-trip latency measurements comprises measuring a round-trip latency between a first collector in the plurality of collectors and a first router interface in the plurality of router interfaces, the first router interface disposed along a path between the first endpoint and the second endpoint. 
     
     
         3 . The method of  claim 1 , wherein obtaining the plurality of round-trip latency measurements comprises measuring timing to each router-level hop between the first endpoint and a collector in the plurality of collectors. 
     
     
         4 . The method of  claim 1 , wherein creating the model of latency comprises:
 accounting for delay associated with each edge in the plurality of edges; and   accounting for delay associated with each node in the plurality of nodes.   
     
     
         5 . The method of  claim 4 , wherein accounting for the delay associated with each edge in the plurality of edges comprises assigning a fixed propagation delay to each edge in the plurality of edges. 
     
     
         6 . The method of  claim 4 , wherein accounting for the delay associated with each node in the plurality of nodes comprises assigning a variable queuing delay to each node in the plurality of nodes. 
     
     
         7 . The method of  claim 6 , further comprising: varying the variable queuing delay as a function of time. 
     
     
         8 . The method of  claim 1 , wherein creating the model of latency comprises performing a convolution of successive individual latency distributions along a path between two nodes in the plurality of nodes. 
     
     
         9 . The method of  claim 1 , wherein creating the model of latency comprises weighting different paths at a branching point in the graph. 
     
     
         10 . The method of  claim 1 , wherein creating the model of latency comprises adding incoming latency distributions at a merging point in the graph. 
     
     
         11 . The method of  claim 1 , further comprising:
 adjusting the model of latency based on a measurement of actual latency along a path in the computer network.   
     
     
         12 . The method of  claim 1 , further comprising:
 estimating a geographic proximity of two router interfaces in the plurality of router interfaces based on the performance of the path between the first endpoint and the second endpoint.   
     
     
         13 . The method of  claim 1 , further comprising:
 predicting a fitness of the path between the first endpoint and the second endpoint for at least one of asynchronous file transfer, email, voice applications, video applications, or real-time applications based on the performance of the path between the first endpoint and the second endpoint.   
     
     
         14 . One or more non-transitory computer readable media comprising instructions which, when executed by one or more hardware processors, causes performance of operations comprising:
 obtaining a plurality of round-trip latency measurements between each of a plurality of router interfaces in the computer network and each of a plurality of collectors;   generating a graph based on the round-trip latency measurements, the graph having a plurality of nodes and a plurality of edges, each node in the plurality of nodes representing a corresponding router interface in the plurality of router interfaces and each edge in the plurality of edges representing a corresponding path between a pair of router interfaces in the plurality of router interfaces;   creating a model of latency across each edge in the plurality of edges; and   predicting performance of a path between the first endpoint and the second endpoint based on the model of latency.   
     
     
         15 . The one or more media of  claim 14 , wherein obtaining the plurality of round-trip latency measurements comprises measuring a round-trip latency between a first collector in the plurality of collectors and a first router interface in the plurality of router interfaces, the first router interface disposed along a path between the first endpoint and the second endpoint. 
     
     
         16 . The one or more media of  claim 14 , wherein obtaining the plurality of round-trip latency measurements comprises measuring timing to each router-level hop between the first endpoint and a collector in the plurality of collectors. 
     
     
         17 . The one or more media of  claim 14 , wherein creating the model of latency comprises:
 accounting for delay associated with each edge in the plurality of edges; and   accounting for delay associated with each node in the plurality of nodes.   
     
     
         18 . The one or more media of  claim 14 , wherein creating the model of latency comprises performing a convolution of successive individual latency distributions along a path between two nodes in the plurality of nodes. 
     
     
         19 . The one or more media of  claim 14 , wherein the operations further comprise:
 adjusting the model of latency based on a measurement of actual latency along a path in the computer network.   
     
     
         20 . A system comprising:
 at least one device including a hardware processor;   the system being configured to perform operations comprising:   obtaining a plurality of round-trip latency measurements between each of a plurality of router interfaces in the computer network and each of a plurality of collectors;   generating a graph based on the round-trip latency measurements, the graph having a plurality of nodes and a plurality of edges, each node in the plurality of nodes representing a corresponding router interface in the plurality of router interfaces and each edge in the plurality of edges representing a corresponding path between a pair of router interfaces in the plurality of router interfaces;   creating a model of latency across each edge in the plurality of edges; and   predicting performance of a path between the first endpoint and the second endpoint based on the model of latency.