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).

Accordingly, I claim: 
     
       1. A method of estimating intra-mode paths, the method comprising the steps of:
 receiving in memory an at least a partial likely autonomous system (AS)-level path comprising a first AS and a second AS, the at least partial likely AS-level path corresponding to a mode of communication between a first endpoint and a second endpoint; 
 monitoring and analyzing by a processor border control gateway protocol (BGP) data received from at least one BGP observer; 
 inferring based on, at least in part, the analyzed BGP data, by the processor, at least one of: (i) a routing policy of the first AS and (ii) a routing policy of the second AS; 
 selecting by the processor a first hand off pair comprising an exit point from the first AS and an entry point into the second AS, the exit point being in communication with the entry point, the selection being based on, at least in part, at least one of: (i) the inferred routing policy of the first AS, (ii) the inferred routing policy of the second AS, and (iii) a statistical property of traffic associated with at least one of a proxy to the first endpoint and a proxy to the second endpoint, the traffic passing via the first AS; and 
 identifying by the processor a set of router-level paths within the first AS, from a first entry point into the first AS to the exit point from the first AS within the first hand off pair; and 
 generating a model of connectivity between the first endpoint and the second endpoint, based at least in part on identifying the set of router-level paths. 
 
     
     
       2. The method of  claim 1 , wherein the property of the first AS comprises at least one of: (i) a number of router-level hop counts within the first AS on a path from the first entry point into the first AS to the exit point from the first AS within the first hand off pair, (ii) a geographic distance between the first entry point into the first AS and the exit point from the first AS within the first hand off pair, and (iii) a number of points of presence associated with both the first AS and the second AS. 
     
     
       3. The method of  claim 1 , wherein the selection step comprises maximizing a first distance within the first AS, the distance comprising at least one of: (i) a number of hop counts on a path to the exit point from the first AS within the first hand off pair, and (ii) a geographic distance between the first entry point into the first AS and the exit point from the first AS within the first hand off pair. 
     
     
       4. The method of  claim 3 , further comprising minimizing a second distance from the exit point from the first AS within the first hand off pair to the proxy to the second endpoint, the second distance comprising at least one of: (i) a number of hop counts on a path from the exit point from the first AS within the first hand off pair to the proxy to the second endpoint, and (ii) a geographic distance between the exit point from the first AS within the first hand off pair and the proxy to the second endpoint. 
     
     
       5. The method of  claim 1 , wherein the selection of the first hand off pair comprises:
 selecting a candidate exit point from the first AS; 
 selecting a candidate entry point into the second AS such that a frequency of traversal of traffic between the candidate exit point and the candidate entry point is greater than a selected threshold; and 
 designating: (i) the selected candidate exit point as the exit point within the first hand off pair, and (ii) the selected candidate entry point as the entry point within the first hand off pair. 
 
     
     
       6. The method of  claim 5 , wherein the frequency of traversal of traffic comprises a frequency of traffic directed to at least one of the proxy to the first endpoint and the proxy to the second endpoint. 
     
     
       7. The method of  claim 1 , further comprising selecting a router-level path from the identified set of router-level paths such that a path metric corresponding to the selected router-level path satisfies a specified threshold. 
     
     
       8. The method of  claim 7 , wherein the path metric comprises at least one of a frequency of traversal of traffic via the selected router-level path, delay, jitter, reliability, and availability. 
     
     
       9. The method of  claim 7 , wherein at least one router-level path in the identified set comprises an intermediate router node, and the path metric comprises a frequency of traversal of traffic via an intermediate router node. 
     
     
       10. The method of  claim 9 , wherein the frequency of traversal of traffic via the intermediate router node comprises a frequency of traffic directed to at least one of the proxy to the first endpoint and the proxy to the second endpoint. 
     
     
       11. The method of  claim 1 , further comprising:
 selecting a second hand off pair comprising an exit point from the first AS and an entry point into the second AS, the exit point being in communication with the entry point, the selection being based on, at least in part, at least one of: (i) a property of the first AS, (ii) a property of the second AS, and (iii) a statistical property of traffic associated with at least one of the proxy to the first endpoint and the proxy to the second endpoint, the traffic passing via the first AS; and 
 identifying a set of router-level paths within the first AS, from a second entry point into the first AS to the exit point from the first AS within the second hand off pair. 
 
     
     
       12. The method of  claim 11 , wherein the second entry point into the first AS is the first entry point into the first AS. 
     
     
       13. A system for estimating intra-mode paths, the system comprising:
 a memory; and   a processor configured to:   receive at least a partial likely autonomous system (AS)-level path comprising a first AS and a second AS, the at least partial likely AS-level path corresponding to a mode of communication between a first endpoint and a second endpoint;   monitor and analyze border control gateway protocol (BGP) data received from at least one BGP observer;   infer based on, at least in part, the analyzed BGP data, at least one of: (i) a routing policy of the first AS and (ii) a routing policy of the second AS;   select a first hand off pair comprising an exit point from the first AS and an entry point into the second AS, the exit point being in communication with the entry point, the selection being based on, at least in part, at least one of: (i) the inferred routing policy of the first AS, (ii) the inferred routing policy of the second AS, and (iii) a statistical property of traffic associated with at least one of a proxy to the first endpoint and a proxy to the second endpoint, the traffic passing via the first AS; and   identify a set of router-level paths within the first AS, from a first entry point into the first AS to the exit point from the first AS within the first hand off pair.   
     
     
       14. The system of  claim 13 , wherein to select the first hand off pair, the processor is further configured to maximize a first distance within the first AS, the distance comprising at least one of: (i) a number of hop counts on a path to the exit point from the first AS within the first hand off pair, and (ii) a geographic distance between the first entry point into the first AS and the exit point from the first AS within the first hand off pair. 
     
     
       15. The system of  claim 14 , wherein the processor is further configured to minimize a second distance from the exit point from the first AS within the first hand off pair to the proxy to the second endpoint, the second distance comprising at least one of: (i) a number of hop counts on a path from the exit point from the first AS within the first hand off pair to the proxy to the second endpoint, and (ii) a geographic distance between the exit point from the first AS within the first hand off pair and the proxy to the second endpoint. 
     
     
       16. The system of  claim 13 , wherein to select of the first hand off pair the processor is configured to:
 select a candidate exit point from the first AS;   select a candidate entry point into the second AS such that a frequency of traversal of traffic between the candidate exit point and the candidate entry point is greater than a selected threshold; and   designate: (i) the selected candidate exit point as the exit point within the first hand off pair, and (ii) the selected candidate entry point as the entry point within the first hand off pair.   
     
     
       17. The system of  claim 13 , wherein the processor is further configured to select a router-level path from the identified set of router-level paths such that a path metric corresponding to the selected router-level path satisfies a specified threshold. 
     
     
       18. The system of  claim 13 , wherein the processor is further configured to:
 select a second hand off pair comprising an exit point from the first AS and an entry point into the second AS, the exit point being in communication with the entry point, the selection being based on, at least in part, at least one of: (i) the inferred routing policy of the first AS, (ii) the inferred routing policy of the second AS, and (iii) a statistical property of traffic associated with at least one of the proxy to the first endpoint and the proxy to the second endpoint, the traffic passing via the first AS; and   identify a set of router-level paths within the first AS, from a second entry point into the first AS to the exit point from the first AS within the second hand off pair.   
     
     
       19. An article of manufacture, comprising a A non-transitory machine-readable medium storing instructions that, when executed by a machine configure the machine, one or more hardware processors, cause performance of operations for estimating intra-mode paths, to comprising:
 receivereceiving an at least a partial likely autonomous system (AS)-level path comprising a first AS and a second AS, the at least partial likely AS-level path corresponding to a mode of communication between a first endpoint and a second endpoint; 
 monitormonitoring and analyzeanalyzing border control gateway protocol (BGP) data received from at least one BGP observer; 
 inferinferring based on, at least in part, the analyzed BGP data, at least one of: (i) a routing policy of the first AS and (ii) a routing policy of the second AS; 
 selectselecting a first hand off pair comprising an exit point from the first AS and an entry point into the second AS, the exit point being in communication with the entry point, the selection being based on, at least in part, at least one of: (i) the inferred routing policy of the first AS, (ii) the inferred routing policy of the second AS, and (iii) a statistical property of traffic associated with at least one of a proxy to the first endpoint and a proxy to the second endpoint, the traffic passing via the first AS; and 
 identifyidentifying a set of router-level paths within the first AS, from a first entry point into the first AS to the exit point from the first AS within the first hand off pair; and 
 generating a model of connectivity between the first endpoint and the second endpoint, based at least in part on identifying the set of router-level paths. 
 
     
     
       20. A method of identifying at least one plausible physical path between a first Internet Protocol (IP) address and a second IP address in a computer network, the method comprising:
 identifying a plurality of connectivity modes between the first IP address and the second IP address;   determining a probability of selection for each connectivity mode in the plurality of connectivity modes in each direction between the first IP address and the second IP address based on Border Gateway Protocol (BGP) data;   determining a probability of selection for each router-level path in a plurality of router-level paths that support at least one connectivity mode in the plurality of connectivity modes;   identifying the at least one plausible physical path based on the probability of selection for each connectivity mode and the probability of selection for each router-level path;   and generating a model of connectivity between the first IP address and the second IP address;   wherein the model comprises the at least one plausible physical path.   
     
     
       21. The method of claim 20, wherein predicting the probability of selection for each connectivity mode comprises predicting the probability of selection of at least one connectivity mode in the plurality of connectivity modes based on a BGP announcement. 
     
     
       22. The method of claim 20, wherein predicting the probability of selection for each connectivity mode comprises predicting the probability of selection of at least one connectivity mode in the plurality of connectivity modes based on a BGP peer relationship. 
     
     
       23. The method of claim 20, wherein predicting the probability of selection for each connectivity mode comprises predicting the probability of selection of at least one connectivity mode in the plurality of connectivity modes based on out-of-band information about at least one transit provider. 
     
     
       24. The method of claim 20, wherein determining the probability of selection of a plurality of router-level paths comprises choosing among a plurality of entry/exit paths between a pair of transit providers. 
     
     
       25. The method of claim 24, wherein choosing among the plurality of entry/exit paths comprises ranking entry/exit paths in the plurality of entry/exit paths based on relative frequency of traversal. 
     
     
       26. The method of claim 20, wherein determining the probability of selection of a plurality of router-level paths comprises evaluating competing router-level paths between a pair of cooperating transmit providers. 
     
     
       27. The method of claim 20, wherein determining the probability of selection of a plurality of router-level paths comprises weighting a router-level path in the plurality of router-level paths based on at least one of latency or geolocation of a router in the router-level path. 
     
     
       28. The method of claim 20, further comprising:
 obtaining the BGP data from a plurality of BGP observation points in the computer network.