System and method for determining the geographic location of internet hosts

• US 7,296,088 B1
• Filed: 05/04/2001
• Issued: 11/13/2007
• Est. Priority Date: 11/17/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Subramanian, Lakshminarayanan, Padmanabhan, Venkata N.
• Primary Examiner(s): Flynn; Nathan J.
• Assistant Examiner(s): PATEL, ASHOKKUMAR B
• Application Number:
  US09/849,662
• Time in Patent Office: 2,384 Days
• Field of Search: None
• US Class Current: 709/238
• CPC Class Codes: H04L 2101/69 using geographic information, e.g. room number
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04W 4/02 Services making use of location information

Abstract

A system and methodologies are disclosed for determining the geographic location of an Internet host. A first method infers host location based on the DNS names of the host of interest or other nearby network nodes. A second method employs network delay measurements from geographically distributed locations to triangulate the coordinates of the host. A third method couples partial host-to-location mapping information obtained from one or more sources with BGP or other routing information in order to infer location of the host of interest.

Claims

1. A computer implemented method of determining the location of an Internet host using a computer system, comprising the following computer executable acts:

obtaining route information relating to one or more network paths between a host IP address associated with the Internet host and the computer system, wherein the network paths comprise the computer system, the Internet host, and at least one intermediate network node, and wherein the route information comprises a plurality of router labels associated with the host IP address and the at least one intermediate network node;

extracting one or more location codes from the route information corresponding to a router label associated with one of the Internet host and one or more intermediate network nodes proximate the Internet host;

consulting a data store comprising at least one data set having location codes and corresponding location information;

obtaining location information from the data store corresponding to the one or more location codes associated with the one of the Internet host and the one or more intermediate network nodes proximate the Internet host;

providing a location estimate of the location of the Internet host according to the location information from the data store corresponding to the location code;

determining a dispersion metric representative of the accuracy of the location estimate of the location of the Internet host and selectively providing the location estimate; and

selectively correcting the location estimate according to the dispersion metric.

2. The method of claim 1, further comprising extracting the location code by examining the router labels in route order along the path from the host to the computer system until a location code is found that is usable to obtain location information from the data store.

3. The method of claim 2, further comprising:

determining a confidence metric representative of the accuracy of the location estimate; and

selectively providing the location estimate of the location of the Internet host if the confidence metric exceeds a threshold.

4. The method of claim 3, further comprising:

determining a confidence metric representative of the accuracy of the location estimate based upon the delay time between the Internet host and the network node associated with the location estimate.

5. The method of claim 1, further comprising:

obtaining route information relating to each network path between the host IP address and each of a plurality of computer systems, wherein the route information comprises a plurality of router labels associated with the host IP address, and each of the plurality of computer systems, and at least one intermediate network node in each network path;

extracting a location code for each network path from the route information corresponding to a router label associated with one of the Internet host and the at least one intermediate network node in each network path;

obtaining location information from the data store corresponding to each location code;

providing a plurality of location estimates of the location of the Internet host according to the location information from the data store corresponding to each location code; and

correlating at least two of the location estimates to provide an improved location estimate of the location of the Internet host.

6. The method of claim 1, wherein the location code comprises one of a city code, and airport code, and a country code, and wherein obtaining the route information comprises using a traceroute tool.

7. A software tool stored on a computer readable storage medium for determining the location of an Internet host using a computer system, comprising the following computer executable components:

a route trace component that obtains route information relating to one or more network paths between a host IP address associated with the Internet host and the computer system, wherein first network paths comprises the computer system, the Internet host, and at least one intermediate network node, and wherein the route information comprises a plurality of router labels associated with the host IP address and the at least one intermediate network node;

an extraction component that extracts one or more location codes from the route information corresponding to one or more router labels associated with one of the Internet host and the at least one intermediate network node proximate the Internet host;

a data store comprising at least one data set having location codes and corresponding location information;

an estimation component that obtains location information from the data store corresponding to the location codes associated with the one of the Internet host and the at least one intermediate network node proximate the Internet host, and to provide a location estimate of the location of the Internet host according to the location information from the data store corresponding to the location code;

a correction component that determines a dispersion metric representative of the accuracy of the location estimate of the location of the Internet host and selectively correcting the location estimate according to the dispersion metric, wherein the location estimate is at least one of stored on a computer readable storage medium or displayed on an display device.

8. A computer-readable medium having computer-executable instructions for:

obtaining route information relating to one or more network paths between a host IP address associated with an Internet host and a computer system, wherein the network paths comprise the computer system, the Internet host, and at least one intermediate network node, and wherein the route information comprises a plurality of router labels associated with the host IP address and the at least one intermediate network node;

extracting one or more location codes from the route information corresponding to a router label associated with one of the Internet host and one or more intermediate network nodes proximate the Internet host;

consulting a data store comprising at least one data set having location codes and corresponding location information;

obtaining location information from the data store corresponding to the location codes associated with the one of the Internet host and the one or more intermediate network nodes proximate the Internet host;

providing a location estimate of the location of the Internet host according to the location information from the data store corresponding to the location code;

determining a dispersion metric representative of the accuracy of the location estimate of the location of the Internet host; and

selectively correcting the location estimate according to the dispersion metric.

9. A system executing on one or more processors for determining the location of an Internet host, comprising the following computer executable components:

a first component operating in a computer system that obtains route information relating to one or more network paths between a host IP address associated with the Internet host and the computer system, wherein the network paths comprises the computer system, the Internet host, and at least one intermediate network node, and wherein the route information comprises a plurality of router labels associated with the host IP address and the at least one intermediate network node;

a second component operating in the computer system that extracts one or more location codes from the route information corresponding to a router label associated with one of the Internet host and one or more intermediate network nodes proximate the Internet host;

a third component operating in the computer system that consults a data store comprising at least one data set having location codes and corresponding location information;

a fourth component operating in the computer system to obtain location information from the data store corresponding to the location codes associated with the one of the Internet host and the one or more intermediate network nodes proximate the Internet host;

a fifth component operating in the computer system that determines a location estimate of the location of the Internet host according to the location information from the data store corresponding to the location code; and

a sixth component operating in the computer system that determines a dispersion metric representative of the accuracy of the location estimate of the location of the internet host and selectively provide the location estimate according to dispersion metric.

10. Geographical location estimate data associated with an Internet host, the estimate data resulting from a process executing on a computer system, comprising the following computer executable acts:

obtaining route information relating to one or more network paths between a host IP address associated with the Internet host and a computer system, wherein the network paths comprise the computer system, the Internet host, and at least one intermediate network node, and wherein the route information comprises a plurality of router labels associated with the host IP address and the at least one intermediate network node;

extracting one or more location codes from the route information corresponding to a router label associated with one of the Internet host and one or more intermediate network nodes proximate the Internet host;

consulting a data store comprising at least one data set having location codes and corresponding location information;

obtaining location information from the data store corresponding to the one or more location codes associated with the one of the Internet host and the one or more intermediate network nodes proximate the Internet host; and

providing a location estimate of the location of the Internet host according to the location information from the data store corresponding to the location code;

determining a dispersion metric representative of the accuracy of the location estimate of the location of the Internet host; and

selectively correcting the location estimate according to the dispersion metric, wherein the location estimate is at least one of stored on a computer readable storage medium or displayed on an display device.

11. A computer implemented method of determining the location of an Internet host using multiple computer systems, comprising the following computer executable acts:

obtaining route information relating to a plurality of network paths between a host IP address associated with the Internet host and a corresponding plurality of computer systems, respectively, wherein the plurality of network paths individually comprise a corresponding computer system, the Internet host, and at least one intermediate network node, and wherein the route information comprises a plurality of router labels associated with the host IP address and an intermediate network node;

extracting one or more location codes from the route information corresponding to a router label associated with one of the Internet host and one or more intermediate network nodes proximate the Internet host;

consulting a data store comprising at least one data set having location codes and corresponding location information;

obtaining location information from the data store corresponding to the one or more location codes associated with the one of the Internet host and the one or more intermediate network nodes proximate the Internet host;

providing a location estimate of the location of the Internet host according to the location information;

determining a dispersion metric representative of the accuracy of the location estimate of the location of the Internet host; and

selectively correcting the location estimate according to the dispersion metric.

12. A computer implemented method of determining the location of an Internet host using a first computer system, comprising the following computer executable acts:

measuring a first delay time relating to a transmission from the first computer system to receipt of the transmission at the Internet host along a first network path between a host IP address associated with the Internet host and the first computer system;

measuring a second delay time relating to a transmission from a second computer system to receipt of the transmission at the Internet host along a second network path between the host IP address and the second computer system;

measuring a third delay time relating to a transmission from a third computer system to receipt of the transmission at the Internet host along a third network path between the host IP address and the third computer system, at least one of the first, second, and third network paths containing at least one intermediate node;

correlating the first, second, and third delay times; and

providing a location estimate of the location of the Internet host according to the correlation of the first, second, and third delay times; and

computing a dispersion metric representative of the accuracy of the location estimate of the location of the Internet host and selectively providing the location estimate based upon the dispersion metric, wherein the location estimate is at least one of stored on a computer readable storage medium or displayed on an display device.

13. The method of claim 12, wherein correlating the first, second, and third delay times comprises triangulating the first, second, and third delay measurements.

14. The method of claim 12, wherein correlating the first, second, and third delay times comprises:

consulting a data store comprising N sets of first, second, and third delay measurements between the first, second, and third computer systems, respectively, and N known hosts, as well as location information associated with the N known hosts, wherein N is an integer;

performing a comparison of the first, second, and third delay times with the N sets of first, second, and third delay measurements in the data store;

determining a nearest set of first, second, and third delay measurements according to the comparison; and

providing a location estimate of the Internet host according to the nearest set of first, second, and third delay measurements.

15. The method of claim 14, wherein performing the comparison of the first, second, and third delay times with the N sets of first, second, and third delay measurements in the data store comprises determining N Euclidian distances corresponding to the Euclidian distances between the N sets of first, second, and third delay measurements in the data store and the first, second, and third delay times, and wherein providing a location estimate of the Internet host according to the nearest set of first, second, and third delay measurements comprises selecting location information associated with the set of first, second, and third delay measurements in the data store associated with the smallest Euclidian distance as the location estimate.

16. The method of claim 12,

wherein correlating the first, second, and third delay times comprises:

computing a first probability density function establishing a relationship between a first network delay associated with the first computer system and a first distance from the first computer system;

determining a first distance estimate representative of the distance between the first computer system and the location of the Internet host using the first delay time and the first probability density function;

computing a second probability density function establishing a relationship between a second network delay associated with the second computer system and a second distance from the second computer system;

determining a second distance estimate representative of the distance between the second computer system and the location of the Internet host using the second delay time and the second probability density function;

computing a third probability density function establishing a relationship between a third network delay associated with the third computer system and a third distance from the third computer system; and

determining a third distance estimate representative of the distance between the third computer system and the location of the Internet host using the third delay time and the third probability density function;

and wherein providing the location estimate comprises triangulating the first, second, and third distance estimates.

17. The method of claim 16, wherein determining the first, second, and third distance estimates further comprises computing an error function over a location space, and determining coordinates within the location space where the error function is minimized.

18. The method of claim 17, wherein determining coordinates within the location space where the error function is minimized comprises minimizing the error function across a list of known city locations, and wherein providing the location estimate comprises providing the known city location corresponding with the minimum value of the error function.

19. The method of claim 18, wherein computing the error function comprises using a weighted least mean squares algorithm to optimize the location estimate.

20. The method of claim 18, wherein computing the error function comprises using a probability density estimation to optimize the location estimate.

21. The method of claim 18, wherein computing the error function comprises using a weighted least mean squares algorithm to prune a solution space, and using a probability density estimation to optimize the location estimate from the pruned solution space.

22. The method of claim 18, wherein computing the error function comprises using a probability density estimation to prune a solution space, and using a weighted least mean squares algorithm to optimize the location estimate from the pruned solution space.

23. A software tool stored on a computer readable storage medium for determining the location of an Internet host using a first computer system, comprising the following computer executable components:

a first delay component that measures a first delay time relating to a transmission from the first computer system to receipt of the transmission at the Internet host along a first network path between a host IP address associated with the Internet host and the first computer system;

a second delay component that measures a second delay time relating to a transmission from a second computer system to receipt of the transmission at the Internet host along a second network path between the host IP address and the second computer system;

a third delay component that measures a third delay time relating to a transmission from a third computer system to receipt of the transmission at the Internet host along a third network path between the host IP address and the third computer system, at least one of the first, second, and third network paths containing at least one intermediate node;

a correlation component that correlates the first, second, and third delay times;

an estimation component that provides a location estimate of the location of the Internet host according to the correlation of the first, second, and third delay times; and

a correction component that computes a dispersion metric representative of the accuracy of the location estimate of the location of the Internet host and selectively provides the location estimate based upon the dispersion metric, wherein the location estimate is at least one of stored on a computer readable storage medium or displayed on an display device.

24. A computer-readable medium having computer-executable instructions for:

measuring a first delay time relating to a transmission from a first computer system to receipt of the transmission at an Internet host along a first network path between a host IP address associated with the Internet host and the first computer system;

measuring a second delay time relating to a transmission from a second computer system to receipt of the transmission at the Internet host along a second network path between the host IP address and the second computer system;

measuring a third delay time relating to a transmission from the Internet host to receipt of the transmission at a third computer system along a third network path between the host IP address associated with the Internet host and a third computer system, at least one of the first, second, and third network paths containing at least one intermediate node;

correlating the first, second, and third delay times;

providing a location estimate of the location of the Internet host according to the correlation of the first, second, and third delay times; and

computing a dispersion metric representative of the accuracy of the location estimate of the location of the Internet host and selectively providing the location estimate based upon the dispersion metric, wherein the location estimate is at least one of stored on a computer readable storage medium or displayed on an display device.

25. A computer implemented system for determining the location of an Internet host, comprising the following computer executable components:

a first component operating in a first computer system to measure a first delay time relating to a transmission from the first computer system to receipt of the transmission at the Internet host along a first network path between a host IP address associated with the Internet host and the first computer system;

a second component operating to measure a second delay time relating to a transmission from a second computer system to receipt of the transmission at the Internet host along a second network path between the host IP address and the second computer system;

a third component operating to measure a third delay time relating to a transmission from a third computer system to receipt of the transmission at the Internet host along a third network path between the host IP address and the third computer system, at least one of the first, second, and third network paths containing at least one intermediate node;

a fourth component operating to correlate the first, second, and third delay times; and

a fifth component operating in a first computer system to provide a location estimate of the location of the Internet host according to the correlation of the first, second, and third delay times; and

a sixth component that computes a dispersion metric representative of the accuracy of the location estimate of the location of the Internet host and selectively provides the location estimate based upon the dispersion metric, wherein the location estimate is at least one of stored on a computer readable storage medium or displayed on an display device.

26. Geographical location estimate data associated with an Internet host, the estimate data resulting from a process executing on a computer system, comprising the following computer executable acts:

measuring a first delay time relating to a transmission from a first computer system to receipt of the transmission at the Internet host along a first network path between a host IP address associated with the Internet host and the first computer system;

measuring a second delay time relating to a transmission from a second computer system to receipt of the transmission at the Internet host along a second network path between the host IP address and the second computer system;

measuring a third delay time relating to a transmission from a third computer system to receipt of the transmission at the Internet host along a third network path between the host IP address and the third computer system, at least one of the first, second, and third network paths containing at least one intermediate node;

correlating the first, second, and third delay times;

providing a location estimate of the location of the Internet host according to the correlation of the first, second, and third delay times; and

computing a dispersion metric representative of the accuracy of the location estimate of the location of the Internet host and selectively providing the location estimate based upon the dispersion metric, wherein the location estimate is at least one of stored on a computer readable storage medium or displayed on an display device.

27. A method of determining the location of an Internet host using a first computer system, comprising the following computer executable acts:

obtaining partial IP-to-location mapping information from a data source;

obtaining network routing information;

clustering together IP addresses corresponding to hosts in the same geographic location according to network routing information to obtain cluster information;

correlating the partial IP-to-location information with the cluster information;

providing a location estimate of the location of the Internet host according to the correlation of the partial IP-to-location information and the cluster information; and

computing a dispersion metric representative of the accuracy of the location estimate of the location of the Internet host and selectively providing the location estimate based upon the dispersion metric.

28. The method of claim 27, wherein obtaining network routing information comprises using a routing protocol.

29. The method of claim 28, wherein the routing protocol is one of BGP, RIP, OSPF, IGRP, and EGP.

30. The method of claim 27, wherein clustering together IP addresses corresponding to hosts in the same geographic location according to network routing information to obtain cluster information comprises associating an address prefix used by a routing protocol with a geographical location.

31. The method of claim 30, further comprising:

sub-dividing the geographical location associated with the address prefix into at least two clusters according to a geographical spread associated with the geographical location.

32. The method of claim 27, further comprising sub-dividing the cluster information according to a geographical spread associated with the geographical location.

33. The method of claim 27, further comprising selectively providing the location estimate if the dispersion metric is less than a threshold value.

34. The method of claim 33, further comprising a threshold value that is dependent on the size of the cluster.

35. The method of claim 27, further comprising:

obtaining route information relating to a first network path between a host IP address associated with the Internet host and the first computer system, wherein the first network path comprises the first computer system, the Internet host, and at least one intermediate network node, and wherein the route information comprises a plurality of router labels associated with the host IP address and the at least one intermediate network node;

extracting a first location code from the route information corresponding to a router label associated with one of the Internet host and an intermediate network node proximate the Internet host;

consulting a data store comprising at least one data set having location codes and corresponding location information;

obtaining first location information from the data store corresponding to the first location code associated with the one of the Internet host and the intermediate network node proximate the Internet host; and

providing a first location estimate of the location of the Internet host according to the first location information from the data store corresponding to the first location code.

36. The method of claim 35, further comprising:

measuring a first delay time relating to a transmission from the first computer system to receipt of the transmission at the Internet host along a first network path between a host IP address associated with the Internet host and the first computer system;

measuring a second delay time relating to a transmission from a second computer system to receipt of the transmission at the Internet host along a second network path between the host IP address and the second computer system;

measuring a third delay time relating to a transmission from a third computer system to receipt of the transmission at the Internet host along a third network path between the host IP address and the third computer system, at least one of the first, second, and third network paths containing at least one intermediate node;

correlating the first, second, and third delay times; and

providing a location estimate of the location of the Internet host according to the correlation of the first, second, and third delay times.

37. The method of claim 27, further comprising:

measuring a first delay time relating to a transmission from the first computer system to receipt of the transmission at the Internet host along a first network path between a host IP address associated with the Internet host and the first computer system;

measuring a second delay time relating to a transmission from a second computer system to receipt of the transmission at the Internet host along a second network path between the host IP address and the second computer system;

measuring a third delay time relating to a transmission from a third computer system to receipt of the transmission at the Internet host along a third network path between the host IP address and the third computer system, at least one of the first, second, and third network paths containing at least one intermediate node;

correlating the first, second, and third delay times; and

providing a location estimate of the location of the Internet host according to the correlation of the first, second, and third delay times.

38. A software tool stored on a computer readable storage medium for determining the location of an Internet host using a first computer system, comprising the following computer executable components:

a first component that obtains partial IP-to-location mapping information from a data source;

a routing protocol component that obtains network routing information;

a clustering component that clusters together IP addresses corresponding to hosts in the same geographic location according to network routing information to obtain cluster information;

a correlation component that correlates the partial IP-to-location information with the cluster information;

an estimation component that provides a location estimate of the location of the Internet host according to the correlation of the partial IP-to-location information and the cluster information; and

a correction component that computes a dispersion metric representative of the accuracy of the location estimate of the location of the Internet host and selectively provides the location estimate based upon the dispersion metric, wherein the location estimate is at least one of stored on a computer readable storage medium or displayed on an display device.

39. A computer-readable medium having computer-executable instructions for:

obtaining partial IP-to-location mapping information from a data source;

obtaining network routing information;

clustering together IP addresses corresponding to hosts in the same geographic location according to network routing information to obtain cluster information;

correlating the partial IP-to-location information with the cluster information;

providing a location estimate of the location of the Internet host according to the correlation of the partial IP-to-location information and the cluster information; and

calculating a dispersion metric representative of the accuracy of the location estimate of the location of the Internet host and selectively providing the location estimate based upon the dispersion metric.

40. A system executing on one or more processors for determining the location of an Internet host, comprising the following computer executable components:

a first component that obtains partial IP-to-location mapping information from a data source;

a second component that obtains network routing information;

a third component that clusters together IP addresses corresponding to hosts in the same geographic location according to network routing information to obtain cluster information;

a fourth component operating that correlates the partial IP-to-location information with the cluster information;

a fifth component that provides a location estimate of the location of the Internet host according to the correlation of the partial IP-to-location information and the cluster information; and

a sixth component operating to that calculates a dispersion metric representative of the accuracy of the location estimate of the location of the Internet host and selectively providing the location estimate based upon the dispersion metric.

41. Geographical location estimate data associated with an Internet host, the estimate data resulting from a process executing on a computer system, comprising the following computer executable acts:

obtaining partial IP-to-location mapping information from a data source;

obtaining network routing information;

clustering together IP addresses corresponding to hosts in the same geographic location according to network routing information to obtain cluster information;

correlating the partial IP-to-location information with the cluster information;

providing a location estimate of the location of the Internet host according to the correlation of the partial IP-to-location information and the cluster information; and

computing a dispersion metric representative of the accuracy of the location estimate of the location of the Internet host and selectively providing the location estimate based upon the dispersion metric, wherein the location estimate is at least one of stored on a computer readable storage medium or displayed on an display device.