Method and system for determining the geographic location of a network block

• US 9,037,694 B2
• Filed: 11/06/2007
• Issued: 05/19/2015
• Est. Priority Date: 11/06/2007
• Status: Active Grant

• Current Assignee: NeuStar IP Intelligence, Inc. (Neustar Incorporated)
• Original Assignee: NeuStar IP Intelligence, Inc. (Neustar Incorporated)
• Inventors: Winkler, Adam
• Primary Examiner(s): Desrosiers, Evans
• Assistant Examiner(s): COSBY, LAWRENCE V
• Application Number:
  US11/935,598
• Publication Number:
  US 20090119394A1
• Time in Patent Office: 2,751 Days
• Field of Search: 709/223, 709/238
• US Class Current: 709/223
• 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

Abstract

Described herein are a method and a system to assign geographic locations to network blocks. A particular embodiment of the system includes a set of intermediate assignment generators, each intermediate assignment generator being associated with at least one of a plurality of network data sources, each intermediate assignment generator being configured to generate an intermediate assignment for at least one of the plurality of network data sources, a set of classifiers each coupled to at least one of the intermediate assignment generators, each classifier being associated with at least one of the plurality of network data sources, each classifier being configured to generate at least one classification based on at least one of the intermediate assignments and corresponding training data, and an intermediate assignment selector to select a best intermediate assignment based on the classifications generated by the set of classifiers, the best intermediate assignment corresponding to a geographic location of a network block.

Claims

1. A method of assigning a geographic location to a network block comprising:

obtaining geo-location data from a plurality of network data sources;

generating, for each data source, intermediate assignments associated with a network block, each intermediate assignment corresponding to geo-location assignment of the network block based on at least one of the network data sources;

generating a plurality of feature vectors, each feature vector including a plurality of attributes associated with a different network data source of the plurality of network data sources, a value for a particular attribute of the plurality of attributes representing a degree to which that attribute is present or absent in a corresponding network data source of the plurality of network data sources;

classifying and/or regressing each intermediate assignment using the plurality of feature vectors to generate classifications and/or regressions based on training data, the classifications being a mapping from a discrete or continuous feature space to a discrete set of labels, the training data including a set of feature vectors and corresponding desired outputs for each of the feature vectors of the set of feature vectors; and

determining a geographic location of the network block based upon at least one of the intermediate assignment classifications and/or regressions.

2. The method of claim 1 wherein the intermediate assignment classifications are selected from a group including a correct classification and an incorrect classification, the method including generating an error rate estimate and/or expected error for each intermediate assignment classified as correct and using the error rate estimate and/or expected error in the determination of the geographic location.

3. The method of claim 2 wherein the determined geographic location is associated with a lowest error rate estimate among the intermediate assignment classifications.

4. The method of claim 1 including providing a plurality of intermediate assignment generators, each being associated with at least one data source.

5. The method of claim 4 including providing a plurality of classifiers, each being associated with at least one of the plurality of intermediate assignment generators.

6. The method of claim 1 wherein the values for a particular attribute include values from the group:

real number and a discrete item.

7. The method of claim 1 wherein the plurality of network data sources are selected from a group including:

a location of the registry information for a network, hand mapped assignments, a location assignment from a hostname label, a top level domain of a country, a complete traceroute, an incomplete traceroute, and a previous assignment associated with the network block.

8. The method of claim 1 wherein the geographic location is assigned on a country level, a state level, a city level, a zip code level, and/or a specific coordinate level.

9. The method of claim 1 including using supervised learning techniques to classify and/or regress each intermediate assignment to generate classifications and or regressions based on training data.

10. The method of claim 1 wherein the determined geographic location of the network block is based upon an interpolation between at least two of the intermediate assignment classifications and/or regressions.

11. A network block geo-locator system comprising:

a set of intermediate assignment generators, each intermediate assignment generator being associated with at least one of a plurality of network data sources, each intermediate assignment generator being configured to generate an intermediate assignment for at least one of the plurality of network data sources, the intermediate assignment corresponding to geo-location assignment of a network block based on the at least one network data source;

a feature vector generator to generate a plurality of feature vectors, each feature vector including a plurality of attributes associated with a different network data source of the plurality of network data sources, a value for a particular attribute of the plurality of attributes representing a degree to which that attribute is present or absent in a corresponding network data source of the plurality of network data sources;

a set of classifiers each coupled to the feature vector generator and at least one of the intermediate assignment generators, each classifier being associated with at least one of the plurality of network data sources, each classifier being configured to generate at least one classification and/or regression based on the plurality of feature vectors and at least one of the intermediate assignments and corresponding training data, the classification being a mapping from a discrete or continuous feature space to a discrete set of labels, the training data including a set of feature vectors and corresponding desired outputs for each of the feature vectors of the set of feature vectors; and

an intermediate assignment generator to determine a geographic location of the network block based on the at least one classification and/or regression generated by the set of classifiers.

12. The network block geo-locator system of claim 11 wherein the classifications are selected from a group including a correct classification and an incorrect classification, the set of classifiers being further configured to generate an error rate estimate and/or expected error for each intermediate assignment classified as correct and using the error rate estimate and/or expected error in the determination of the geographic location of the network block.

13. The network block geo-locator system of claim 11 wherein the determined geographic location of a network block is associated with a lowest error rate estimate among the intermediate assignment classifications.

14. The network block geo-locator system of claim 11 wherein the values for a particular attribute include values from the group:

real number and a discrete item.

15. The network block geo-locator system of claim 11 wherein the plurality of network data sources are selected from a group including:

a location of the registry information for a network, hand mapped assignments, a location assignment from a hostname label, a top level domain of a country, a complete traceroute, an incomplete traceroute, and a previous assignment associated with the network block.

16. The network block geo-locator system of claim 11 wherein the geographic location includes information associated with a country level, a state level, a city level, a zip code level, and/or a specific coordinate level.

17. The network block geo-locator system of claim 11 wherein the determined geographic location of the network block is based upon an interpolation between at least two of the intermediate assignment classifications and/or regressions.

18. An article of manufacture comprising a non-transitory machine-readable storage medium having machine executable instructions embedded thereon, which when executed by a machine, cause the machine to:

obtain geo-location data from a plurality of network data sources;

generate, for each data source, intermediate assignments associated with a network block, each intermediate assignment corresponding to geo-location assignment of the network block based on at least one of the network data sources;

generating a plurality of feature vectors, each feature vector including a plurality of attributes associated with a different network data source of the plurality of network data sources, a value for a particular attribute of the plurality of attributes representing a degree to which that attribute is present or absent in a corresponding network data source of the plurality of network data sources;

classify and/or regress each intermediate assignment using the plurality of feature vectors to generate classifications and/or regressions based on training data, the classifications being a mapping from a discrete or continuous feature space to a discrete set of labels, the training data including a set of feature vectors and corresponding desired outputs for each of the feature vectors of the set of feature vectors; and

determine a geographic location of the network block based upon at least one of the intermediate assignment classifications and/or regressions.

19. The article of manufacture of claim 18 wherein the intermediate assignment classifications are selected from a group including a correct classification and an incorrect classification, the article of manufacture being further configured to generate an error rate estimate and/or expected error for each intermediate assignment classified as correct and using the error rate estimate and/or expected error in the determination of the geographic location.

20. The article of manufacture of claim 19 wherein the determined geographic location is associated with a lowest error rate estimate among the intermediate assignment classifications.

21. The article of manufacture of claim 18 being further configured to provide a plurality of intermediate assignment generators, each being associated with at least one data source.

22. The article of manufacture of claim 21 being further configured to provide a plurality of classifiers, each being associated with at least one of the plurality of intermediate assignment generators.

23. The article of manufacture of claim 18 wherein the values for a particular attribute include values from the group:

real number and a discrete item.

24. The article of manufacture of claim 18 wherein the plurality of network data sources are selected from a group including:

a location of the registry information for a network, hand mapped assignments, a location assignment from a hostname label, a top level domain of a country, a complete traceroute, an incomplete traceroute, and a previous assignment associated with the network block.

25. The article of manufacture of claim 18 wherein the geographic location is assigned on a country level, a state level, a city level, a zip code level, and/or a specific coordinate level.