Determining location information for a node in a network using at least one local landmark node

• US 8,677,017 B2
• Filed: 01/30/2004
• Issued: 03/18/2014
• Est. Priority Date: 01/30/2004
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Xu, Zhichen, Banerjee, Sujata, Lee, Sung-Ju
• Primary Examiner(s): HOANG, HIEU T
• Application Number:
  US10/767,075
• Publication Number:
  US 20050168380A1
• Time in Patent Office: 3,700 Days
• Field of Search: 709238-243, 709/220, 709/222
• US Class Current: 709/242
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

Location information for a node in a network is determined. A first distance from the node to at least one global landmark node is determined and a second distance from the node to at least one local landmark node proximally located to the node is determined. Location information for the node based on the first distance and the second distance is generated.

Claims

1. A method of determining location information for a computer system node in a network, the method comprising:

determining, by a processor, first distances along routing paths from the node to global landmark nodes;

identifying local landmark nodes located in the routing paths between the node and the global landmark nodes;

determining, by the processor, second distances from the node to the identified local landmark nodes; and

determining location information for the node based on the first distances and the second distances.

2. The method of claim 1, wherein determining location information comprises determining location information associated with a physical location of the node in the network based on the first distances and the second distances.

3. The method of claim 1, wherein determining location information comprises generating a landmark vector including the first distances and the second distances.

4. The method of claim 3, further comprising transmitting the landmark vector to at least one other node in the network storing landmark vectors for a plurality of nodes in the network.

5. The method of claim 3, further comprising:

hashing at least a portion of the landmark vector to identify a location in an overlay network for storing the landmark vector, wherein the overlay network is a logical representation of the network; and

transmitting the landmark vector to a node at the identified location to store the landmark vector.

6. The method of claim 1, wherein determining first distances from the node to the global landmark nodes comprises:

transmitting a probe packet to each global landmark node; and

measuring round-trip-time to each global landmark node using the transmitted probe packet.

7. The method of claim 6, wherein determining second distances from the node to the local landmark nodes comprises:

receiving an acknowledge message from each local landmark node receiving the probe packet; and

determining the second distances to the local landmark nodes in response to receiving each acknowledge message.

8. The method of claim 1, further comprising:

querying a global information table that stores location information of nodes in the network to select a plurality of the local landmark nodes within a predetermined distance from the node; and

determining distances to each of the plurality of local landmark nodes.

9. The method of claim 1, further comprising selecting a predetermined number of nodes in the network to be global landmark nodes and local landmark nodes based on the number of nodes in the network.

10. The method of claim 9, wherein selecting a predetermined number of nodes in the network to be global landmark nodes comprises randomly selecting a predetermined number of nodes in the network to be global landmark nodes.

11. The method of claim 9, wherein selecting a predetermined number of nodes in the network to be local landmark nodes comprises randomly selecting a predetermined number of nodes in the network to be local landmark nodes.

12. The method of claim 9, wherein selecting a predetermined number of nodes in the network to be local landmark nodes comprises:

identifying nodes located near at least one gateway router or including the at least one gateway router in the network; and

selecting at least one of the identified nodes to be a local landmark node.

13. The method of claim 9, wherein a number of global landmark nodes in the network is less than a number of local landmark nodes in the network.

14. The method of claim 1, wherein determining first distances comprises determining distances to all of the global landmark nodes in the network.

15. The method of claim 1, wherein at least one of the local landmark nodes is a router.

16. A computer system node in a network comprising:

a processor; and

a memory storing computer readable instructions executable by the processor to;

determine first distances along routing paths from the node to global landmark nodes;

identify local landmark nodes located in the routing paths between the node and the global landmark nodes;

determine second distances from the node to the identified local landmark nodes; and

determine location information for the node based on the first distances and the second distances.

17. The computer system node of claim 16, wherein the computer readable instructions are further executable by the processor to:

identify a location in an overlay network for storing the location information, wherein the overlay network is a logical representation of the network; and

transmit the location information to a node at the identified location to store the location information.

18. A computer system operable to connect to a peer-to-peer network, the computer system comprising:

a processor to determine a physical location of the computer system in the peer-to-peer network by determining first distances along routing paths from the computer system to global landmark nodes, identifying local landmark nodes located in the routing paths between the node and the global landmark nodes, determining second distances from the computer system to the identified local landmark nodes, and determining the physical location of the computer system based on the first distances and the second distances; and

a memory to store location information associated with the physical location of the computer system.

19. The computer system of claim 18, wherein the memory is to store location information for a plurality of nodes in the peer-to-peer network that are physically close to the computer system.

20. The computer system of claim 18, wherein the processor is to identify a location in an overlay network for storing the location information, wherein the overlay network is a logical representation of the peer-to-peer network.

21. The computer system of claim 20, further comprising a network interface to connect the computer system to the peer-to-peer network, wherein the computer system is to transmit the location information to the identified location in the overlay network via the network interface.

22. A non-transitory computer readable storage medium storing machine readable instructions executable by at least one processor to:

determine first distances along routing paths from the node to global landmark nodes;

identify local landmark nodes located in the routing paths between the node and the global landmark nodes;

determine second distances from the node to the identified local landmark nodes; and

determine location information for the node based on the first distances and the second distances.

23. The non-transitory computer readable storage medium of claim 22, wherein the machine readable instructions are further executable by the at least one processor to:

identify a location in an overlay network to store the location information, wherein the overlay network is a logical representation of the network.

24. The non-transitory computer readable storage medium of claim 22, wherein the machine readable instructions to identify a location in an overlay network comprise instructions to hash the location information to identify a location in the overlay network to store the location information.

25. The non-transitory computer readable storage medium of claim 22, wherein the local landmark nodes are located within a predetermined distance from the node.