System and method for determining the geographic location of internet hosts

• US 7,711,846 B2
• Filed: 07/16/2007
• Issued: 05/04/2010
• Est. Priority Date: 11/17/2000
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Subramanian, Lakshminarayanan, Padmanabhan, Venkata N.
• Primary Examiner(s): PATEL, ASHOKKUMAR B
• Application Number:
  US11/778,490
• Publication Number:
  US 20080037536A1
• Time in Patent Office: 1,023 Days
• Field of Search: 455/456.1, 455/457, 455/524, 455/525, 455/404.2, 342/457
• 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 a location of an Internet host using a computer system, comprising the following computer-executable acts:

obtaining a router label associated with a host IP address associated with the Internet host;

extracting a location code from the router label;

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 code;

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; and

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

2. The method of claim 1, further comprising:

obtaining route information relating to one or more network paths between a host IP address associated with the Internet host and the computer system; and

extracting the location code by examining router labels in route order along the one or more network paths from the Internet 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 1, further comprising:

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

selectively correcting the location estimate of the location of the Internet host if the confidence metric is below a threshold.

4. The method of claim 3, wherein determining the confidence metric representative of the accuracy of the location estimate is based upon a delay time between the Internet host and the computer system.

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

7. A method of determining a location of an Internet host, 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;

providing a location estimate of the location of the Internet host according to the first delay time; and

computing a dispersion metric representative of an 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, employed by a process executing on a processor, displayed on a display device, or transmitted between one or more processes executing on one or more computers.

8. The method of claim 7, further comprising:

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 the location estimate of the location of the Internet host according to the correlating of the first, second, and third delay times.

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

10. The method of claim 8, 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.

11. The method of claim 10, 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 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 a set of first, second, and third delay measurements in the data store associated with a smallest Luclidian distance as the location estimate.

12. The method of claim 8, 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 a 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 a 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 a distance between the third computer system and the location of the Internet host using the third delay time and the third probability density function;

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

13. The method of claim 12, 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.

14. The method of claim 13, 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 a known city location corresponding with a minimum value of the error function.

15. The method of claim 13, wherein computing the error function comprises using at least one of a weighted least mean squares algorithm to optimize the location estimate or a probability density estimation to optimize the location estimate.

16. A computer-readable storage medium storing instructions for determining a location of an Internet host, the instructions to, if executed by a computing device, cause the computing device to perform operations comprising:

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;

providing a location estimate of the location of the Internet host according to the first delay time; and

computing a dispersion metric representative of an 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, employed by a process executing on a processor, displayed on a display device, or transmitted between one or more processes executing on one or more computers.

17. The computer-readable storage medium of claim 16, the operations further comprising:

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 the location estimate of the location of the Internet host according to the correlation of the first, second, and third delay times.

18. The computer-readable storage medium of claim 17, wherein correlating the first, second, and third delay times comprises triangulating the first, second, and third delay measurements.

19. The computer-readable storage medium of claim 17, 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.

20. The computer-readable storage medium of claim 16, the operations further comprising selectively correcting the location estimate based upon the dispersion metric.