Internet protocol (IP) address proximity detection and application to peer provider location

• US 20020143918A1
• Filed: 07/18/2001
• Published: 10/03/2002
• Est. Priority Date: 03/27/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Teodosiu, Dan, Boyen, Xavier, Soles, L. Roger
• Granted Patent: US 7,720,996 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/35 involving non-standard use of addresses for implementing network functionalities, e.g. coding subscription information within the address or functional addressing, i.e. assigning an address to a function
• CPC Class Codes: H04L 61/45 Network directories; Name-to-address mapping
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1021 based on client or server locations
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1063 Discovery through centralising entities
• CPC Class Codes: H04L 67/1072 Discovery involving ranked list compilation of candidate peers
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

Internet Protocol (IP) address assignment information is collected from Address Allocation Tables (AATs) of a plurality of IP address assigning registrars. The information is processed and stored into one or more data structures. The information is accessed to determine a proximity measure for any two given IP addresses. In one embodiment, the proximity determination includes the determination of superblock memberships of the IP addresses, comparison of the assigning registrars, as well as the location countries of the IP addresses. In one embodiment, the proximity detection is applied to locating IP addresses of peer providers of a resource. In one embodiment, Autonomous System (AS) numbers and IP addresses for a plurality of peer providers for a plurality of resources are also collected and organized into one or more data structures; this organized information of the peer providers is also used in locating the closest peer providers of a resource in terms of network topology.

Claims

1. A method comprising:

accessing Address Allocation Tables (AATs) of a plurality of Internet Protocol (IP) address assigning registrars, and retrieving from said AATs IP address assignment information;

processing and storing said retrieved IP address assignment information into one or more data structures;

receiving a first IP address; and

determining a proximity measure for said first IP address and a second IP address, based at least in part on said IP address assignment information collected from said AATs of said IP address assigning registrars and stored in said one or more data structures.

2. The method of claim 1, wherein said processing and storing comprises storing geographical location information for various IP address superblocks.

3. The method of claim 2, wherein said storing of geographical location information for various IP address blocks comprises storing base addresses of superblocks, country identifications of countries within which IP addresses of said superblocks reside, and community information assigned to said IP addresses.

4. The method of claim 1, wherein said processing and storing comprises sort-merging said retrieved IP address assignment information into a data structure based on superblock base addresses.

5. The method of claim 1, wherein said processing and storing comprises organizing and storing said retrieved IP address assignment information into a plurality of prefix trees.

6. The method of claim 1, wherein said determining of a proximity measure for said first and second IP addresses comprises identifying geographical locations of said first and second IP addresses.

7. The method of claim 6, wherein said identifying of the geographical locations of said first and second IP addresses comprises identifying the registrars responsible for assigning said first and second IP addresses.

8. The method of claim 7, wherein said identifying of the registrars responsible for assigning said first and second IP addresses comprises identifying superblock memberships for said first and second IP addresses.

9. The method of claim 1, wherein the method further comprises

retrieving an AS number for said first IP address;

and

retrieving an AS number for said second IP address.

10. The method of claim 9, wherein the method further comprises pre-collecting AS numbers and IP addresses for a plurality of peer providers for a plurality of resources.

11. A method comprising:

determining superblock membership for a first and a second IP address;

determining a proximity measure for said first and second IP address based at least in part on the result of said superblock membership determination.

12. The method of claim 11, wherein said determining a proximity measure comprises performing a bit-wise comparison of said first and second IP addresses, from the most significant bit to the least significant bit, to determine the first bit position said first and second IP addresses differ, and assigning a distance metric based at least in part on said first bit position, when the result of said superblock membership determination indicates that at least one said first and second IP address does not have a superblock membership.

13. The method of claim 11, wherein said determining a proximity measure comprises determining whether a single registrar assigned both said first and said second IP address, when the result of said superblock membership determination indicates that both said first and second. IP addresses does have superblock memberships.

14. The method of claim 13, wherein said determining a proximity measure further comprises assigning a distance measure reflective of the fact that different registrars assigned said first and second IP addresses, if it is determined that not a single registrar assigned both of said first and second IP addresses.

15. The method of claim 13, wherein said determining a proximity measure further comprises determining whether a single country hosts both said first and said second IP address, when the result of said registrar determination indicates that a single registrar assigned both said first and second IP addresses.

16. The method of claim 15, wherein said determining a proximity measure further comprises assigning a distance measure reflective of the fact that different countries host said first and second IP addresses, if it is determined that not a single country hosts both of said first and second IP addresses.

17. The method of claim 15, wherein said determining a proximity measure further comprises determining whether said first and second IP addresses have the same superblock membership, when the result of said country determination indicates that a single country hosts both said first and second IP addresses.

18. The method of claim 17, wherein said determining a proximity measure further comprises assigning a distance measure reflective of the fact that said first and second IP addresses have different superblock memberships, if it is so determined.

19. The method of claim 17, wherein said determining a proximity measure comprises performing a bit-wise comparison of said first and second IP addresses, from the most significant bit to the least significant bit, to determine the first bit position said first and second IP addresses differ, if it is determined that said first and second IP addresses have the same superblock membership.

20. The method of claim 11, wherein said method further comprises determining whether said first and second IP addresses correspond to a common AS number, and conditionally modifying said determined proximity measure based on the result of said AS number determination.

21. The method of claim 11, wherein said method further comprises determining whether said first and second IP addresses correspond to a common community, and conditionally modifying said determined proximity measure based on the result of said community determination.

22. A method comprising:

performing a bit-wise comparison of a first and a second IP address, from the most significant bit to the least significant bit, to determine the first bit position said first and second IP addresses differ, and assigning a distance metric based at least in part on said first bit position;

determining a proximity measure for said first and second IP address based at least in part on said assigned distance metric.

24. The method of claim 23, wherein said organizing comprises for each of said plurality of resources, sorting the IP addresses of peer providers of the resource by the AS numbers, and inserting the IP addresses of peer providers into a storing data structure based on there AS numbers.

26. The method of claim 25, wherein said method further comprises receiving a specification for a number of peer providers desired, and determining if the number of IP addresses of peer providers of the target resource retrieved meets or exceeds said specified number of peer providers desired.

27. The method of claim 26, wherein said method further comprises selecting a subset of said retrieved IP addresses of peer providers based on the proximity of said retrieved IP addresses of peer providers to said received target address if the number of IP addresses of peer providers of the target resource retrieved meets or exceeds said specified number of peer providers desired.

28. The method of claim 27, wherein said method further comprises retrieving an IP address of a peer provider that is a member of a different network community, and determining the proximity of the retrieved IP address of the peer provider that is a member of a different network community to said received target address, if the number of IP addresses of peer providers of the target resource retrieved does not reach said specified number of peer providers desired.

29. The method of claim 28, wherein said method further comprises at least temporarily discarding said retrieved IP address of a peer provider that is a member of a different network community if the retrieved IP address of a peer provider that is a member of a different network community is not within a predetermined proximity distance from said received target address of the target resource.

30. The method of claim 29, wherein the method further comprises repeating said conditional retrieving and proximity determining of claim 28 to strive to select the desired number of IP addresses of peer providers of the target resource.

31. The method of claim 30, wherein the method further comprises caching said temporarily discarded IP addresses of peer providers, and selecting a subset of said cached IP addresses of peer providers based on their proximities to said received target address, if the specified number of peer providers desired remains unmet.

23. A method comprising:

collecting AS numbers and IP addresses for a plurality of peer providers for a plurality of resources;

organizing said IP addresses of said peer providers for the plurality of resources into one or more data structures by said resources and said AS numbers;

receiving an IP address of a client;

determining an AS number associated with said IP address of said client; and

retrieving IP addresses of peer providers of said target resource from said one or more data structures based at least in part on said determined AS number associated with said received IP address of said client.

25. A method comprising:

receiving an IP address of a client;

determining a network community associated with the received IP address of the client;

determining if there are peer providers of a target resource with the same network community; and

retrieving IP addresses of said peer providers of the target resource that are members of the same network community, if it is determined there are peer providers of the target resource that are members of the same network community.

32. A method comprising:

requesting for a plurality of IP addresses of peer providers for a target resource of interest;

receiving a plurality of IP addresses of peer providers for said target resource of interest;

selecting a first of said peer providers whose IP address is among those received;

accessing said first peer provider for said target resource of interest;

monitoring said accessing; and

conditionally switching to a second of said peer provider whose IP address is among those received, and accessing said second peer provider for said target resource of interest if a switching condition is met in accordance with the results of said monitoring.

33. The method of claim 32, wherein said received IP addresses of peer providers are provided based at least in part on proximities of the peer providers to a requestor making said requesting per their respective IP addresses.

34. The method of claim 32, wherein said monitoring comprises monitoring for at least a selected one of access success/failure and a performance indicator.

36. The apparatus of claim 35, wherein said programming instructions are designed to enable the apparatus to perform said processing and storing by storing geographical location information for various IP address blocks.

37. The apparatus of claim 36, wherein said programming instructions are designed to enable the apparatus to perform said storing of geographical location information for various IP address blocks by storing base addresses of superblocks, country identifications of countries within which IP addresses of said superblocks reside, and community information assigned to said IP addresses.

38. The apparatus of claim 35, wherein said programming instructions are designed to enable the apparatus to perform said processing and storing by sort-merging said retrieved IP address assignment information into a data structure based on superblock base addresses.

39. The apparatus of claim 35, wherein said programming instructions are designed to enable the apparatus to perform said processing and storing by organizing and storing said retrieved IP address assignment information into a plurality of prefix trees.

40. The apparatus of claim 35, wherein said programming instructions are designed to enable the apparatus to perform said determining of a proximity measure for said first and second IP addresses by identifying geographical locations of said first and second IP addresses.

41. The apparatus of claim 40, wherein said programming instructions are designed to enable the apparatus to perform said identifying of the geographical locations of said first and second IP addresses by identifying the registrars responsible for assigning said first and second IP addresses.

42. The apparatus of claim 41, wherein said programming instructions are designed to enable the apparatus to perform said identifying of the registrars responsible for assigning said first and said second IP addresses by identifying superblock memberships for said first and second IP addresses.

43. The apparatus of claim 35, wherein said programming instructions are further designed to enable the apparatus to retrieve an AS number for said first IP address, and to retrieve an AS number for said second IP address.

44. The apparatus of claim 43, wherein said programming instructions are further designed to enable the apparatus to pre-collect AS numbers and IP addresses for a plurality of peer providers for a plurality of resources.

46. The apparatus of claim 45, wherein said programming instructions are designed to enable the apparatus to perform said determining of a proximity measure by performing a bit-wise comparison of said first and second IP addresses, from the most significant bit to the least significant bit, to determine the first bit position said first and second IP addresses differ, and to assign a distance metric based at least in part on said first bit position, when the result of said superblock membership determination indicates that at least one said first and second IP address does not have a superblock membership.

47. The apparatus of claim 45, wherein said programming instructions are designed to enable the apparatus to perform said determining of a proximity measure by determining whether a single registrar assigned both said first and said second IP address, when the result of said superblock membership determination indicates that both said first and second IP addresses does have superblock memberships.

48. The apparatus of claim 47, wherein said programming instructions are designed to enable the apparatus to assign a distance measure reflective of the fact that different registrars assigned said first and second IP addresses, if it is determined that not a single registrar assigned both of said first and second IP addresses, when performing said determining of a proximity measure.

49. The apparatus of claim 47, wherein said programming instructions are designed to enable the apparatus to determine whether a single country hosts both said first and said second IP address, when the result of said registrar determination indicates that a single registrar assigned both said first and second IP addresses, when determining a proximity measure.

50. The apparatus of claim 47, wherein said programming instructions are designed to enable the apparatus to assign a distance measure reflective of the fact that different countries host said first and second IP addresses, if it is determined that not a single country hosts both of said first and second IP addresses, when determining a proximity measure.

51. The apparatus of claim 49, wherein said programming instructions are designed to enable the apparatus to determine whether said first and second IP addresses have the same superblock membership, when the result of said country determination indicates that a single country hosts both said first and second IP addresses, when determining a proximity measure.

52. The apparatus of claim 41, wherein said programming instructions are designed to enable the apparatus to assign a distance measure reflective of the fact that said first and second IP addresses have different superblock memberships, if it is so determined, when determining a proximity measure.

53. The apparatus of claim 51, wherein said programming instructions are designed to enable the apparatus to perform a bit-wise comparison of said first and second IP addresses, from the most significant bit to the least significant bit, to determine the first bit position said first and second IP addresses differ, if it is determined that said first and second IP addresses have the same superblock membership, when determining a proximity measure.

54. The apparatus of claim 55, wherein said programming instructions are further designed to enable the apparatus to determine whether said first and second IP addresses correspond to a common Autonomous System (AS) number, and to conditionally modify said determined proximity measure based on the result of said AS number determination.

55. The apparatus of claim 45, wherein said programming languages further enable the apparatus to determine whether said first and second IP addresses correspond to a common community, and conditionally modify said determined proximity measure based on the result of said community determination.

58. The apparatus of claim 57, wherein said programming instructions are designed to enable the apparatus to perform said organizing for each of said plurality of resources by sorting the IP addresses of peer providers of the resource by the AS numbers, and inserting the IP addresses of peer providers into a data structure.

60. The apparatus of claim 59, wherein said programming instructions are further designed to enable the apparatus to receive a specification for a number of peer providers desired, and determine if the number of IP addresses of peer providers of the target resource retrieved meets or exceeds said specified number of peer providers desired.

61. The apparatus of claim 60, wherein said programming instructions are further designed to enable the apparatus to select a subset of said retrieved IP addresses of peer providers based on the proximity of said retrieved IP addresses of peer providers to said received target address if the number of IP addresses of peer providers of the target resource retrieved meets or exceeds said specified number of peer providers desired.

62. The apparatus of claim 61, wherein said programming instructions are further designed to enable the apparatus to retrieve an IP address of a peer provider with a different network community, and determine the proximity of the retrieved IP address of the peer provider with the different network community to said received target address, if the number of IP addresses of peer providers of the target resource retrieved does not reach said specified number of peer providers desired.

63. The apparatus of claim 62, wherein said programming instructions are further designed to enable the apparatus to discard said retrieved IP address of a peer provider with a different network community if the retrieved IP address of a peer provider with a different network community is not within a predetermined proximity distance from said received target address of the target resource.

64. The apparatus of claim 63, wherein said programming instructions are further designed to enable the apparatus to repeat said conditional retrieving and proximity determining of claim 62 to strive to select the number of IP addresses of peer providers for the target resource.

35. An apparatus comprising:

storage medium having stored therein a plurality of programming instructions designed to enable said apparatus to

access AATs of a plurality of IP address assigning registrars, and retrieve from said AATs IP address assignment information,

process and store said retrieved IP address assignment information into one or more data structures,

receive a first IP address,

determine a proximity measure for said first IP address and a second IP address, based at least in part on said IP address assignment information collected from said AATs of said IP address assigning registrars and stored in said one or more data structures; and

at least one processor coupled to the storage medium to execute the programming instructions.

45. An apparatus comprising:

storage medium having stored therein a plurality of programming instructions designed to enable said apparatus to

determine superblock membership for a first and a second IP address,

determine a proximity measure for said first and second IP address based at least in part on the result of said superblock membership determination; and

at least one processor coupled to the storage medium to execute the programming instructions.

56. An apparatus comprising:

storage medium having stored therein a plurality of programming instructions designed to enable said apparatus to

perform a bit-wise comparison of a first and a second IP address, from the most significant bit to the least significant bit, to determine the first bit position said first and second IP addresses differ, and assign a distance metric based at least in part on said first bit position, and

determine a proximity measure for said first and second IP address based at least in part on said assigned distance metric; and

at least one processor coupled to the storage medium to execute the programming instructions.

57. An apparatus comprising:

storage medium having stored therein a plurality of programming instructions designed to enable said apparatus to

collect AS numbers and IP addresses for a plurality of peer providers for a plurality of resources,

organize said IP addresses of said peer providers for the plurality of resources into one or more data structures by said resources and said AS numbers,

receive an IP address of a client,

determine an AS number associated with said IP address of said client, and

retrieve IP addresses of peer providers of a target resource from said one or more data structures based at least on part on said determined AS number associated with said IP address of said client; and

at least one processor coupled to the storage medium to execute the programming instructions.

59. An apparatus comprising:

storage medium having stored therein a plurality of programming instructions designed to enable said apparatus to

receive an IP address of a client,

determine a network community associated with the IP address of the client,

determine if there are peer providers of a target resource with the samenetwork community, and

retrieve IP addresses of said peer providers of the target resource having the same network community, if it is determined there are peer providers of the target resource with the same network community; and

at least one processor coupled to the storage medium to execute the programming instructions.

65. An apparatus comprising:

storage medium having stored therein a plurality programming instructions designed to enable the apparatus to

request for a plurality of IP addresses of peer providers for a target resource of interest,

receive a plurality of IP addresses of peer providers for said target resource of interest,

select a first of said peer providers whose IP address is among those received,

access said first peer provider for said target resource of interest;

monitor said accessing, and

conditionally switch to a second of said peer provider whose IP address is among those received, and access said second peer provider for said target resource of interest if a switching condition is met in accordance with the results of said monitoring; and

at least one processor coupled to the storage medium to execute the programming instructions.

66. The apparatus of claim 65, wherein the apparatus has associated IP address, and said received IP addresses of peer providers are provided based at least in part on proximities of the peer providers to the apparatus per their respective IP addresses.

67. The apparatus of claim 65, wherein the programming instructions enable the apparatus to monitor for at least a selected one of access success/failure and a performance indicator.