SYSTEM AND METHOD FOR DETERMINING THE GEOGRAPHIC LOCATION OF INTERNET HOSTS

• US 20080037536A1
• Filed: 07/16/2007
• Published: 02/14/2008
• Est. Priority Date: 11/17/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Padmanabhan, Venkata, Subramanian, Lakshminarayanan
• Granted Patent: US 7,711,846 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• 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-18. -18. (canceled)

19. A computer implemented method of determining the 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;

an d

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;

20. The method of claim 19, 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 the router labels in route order along the path 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.

21. The method of claim 19, 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.

22. The method of claim 21, :

wherein determining a confidence metric representative of the accuracy of the location estimate is based upon a delay time between the Internet host and the computer system.

23. The method of claim 19, 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.

24. The method of claim 19, wherein the location code comprises one of a city code, and airport code, and a country code.

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

providing a location estimate of the location of the Internet host according to the first delay time; 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, employed by a process executing on a processes, displayed on an display device, or transmitted between one or more processes executing on one or more computers.

26. The method of claim 25, 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; and

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

28. The method of claim 26, 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.

29. The method of claim 28, 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.

30. The method of claim 26, 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.

31. The method of claim 30, 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.

32. The method of claim 31, 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.

33. The method of claim 31, 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.

34. A system for determining the location of an Internet host, comprising:

means for 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;

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

means for 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, employed by a process executing on a processes, displayed on an display device, or transmitted between one or more processes executing on one or more computers.

35. The system of claim 34, further comprising:

means for 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;

means for 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;

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

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

36. The system of claim 35, wherein correlating the first, second, and third delay times comprises triangulating the first, second, and third delay measurements.

37. The system of claim 35, wherein correlating the first, second, and third delay times comprises:

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

means for 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;

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

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

38. The system of claim 34, further comprising means for selectively correcting the location estimate based upon the dispersion metric.