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

• US 20050168380A1
• Filed: 01/30/2004
• Published: 08/04/2005
• 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: Banerjee, Sujata, Xu, Zhichen, Lee, Sung-Ju
• Granted Patent: US 8,677,017 B2
• Time in Patent Office: Days
• US Class Current: 342/126
• 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 node in a network, the method comprising:

determining a first distance from the node to at least one global landmark node;

determining a second distance from the node to at least one local landmark node proximally located to the node; and

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

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 distance and the second distance.

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

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 a first distance from the node to at least one global landmark node comprises:

transmitting a probe packet to the at least one global landmark node; and

measuring round-trip-time to the at least one global landmark node using the transmitted probe packet.

7. The method of claim 6, wherein determining a second distance from the node to at least one local landmark node comprises:

receiving an acknowledge message from the at least one local landmark node receiving the probe packet, wherein the at least one landmark node is in a routing path between the node and the at least one global landmark node; and

determining the second distance to the at least one local landmark node in response to receiving the acknowledge message.

8. The method of claim 1, wherein determining a second distance comprises:

selecting a plurality of 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 a first distance from the node to at least one global landmark node comprises determining distances to all of the global landmark nodes in the network.

15. The method of claim 14, wherein determining a second distance from the node to at least one local landmark node proximally located to the node comprises determining distances to each of a plurality of local landmark nodes proximally located to the node.

16. The method of claim 1, wherein the at least one local landmark node includes a plurality of local landmark nodes in a routing path between the node and the at least one global landmark node and determining a second distance comprises determining distances to each of the plurality of local landmark nodes.

17. The method of claim 16, wherein the plurality of local landmark nodes includes a plurality of routers in the routing path between the node and the at least one global landmark node.

18. The method of claim 17, wherein the plurality of routers is less than a total number of routers in the routing path between the node and the at least one global landmark node.

19. A node in a network comprising:

means for determining a first distance from the node to at least one global landmark node;

means for determining a second distance from the node to at least one local landmark node proximally located to the node and the at least one global landmark node; and

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

20. The node of claim 19, further comprising:

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

means for transmitting the location information to a node at the identified location to store the location information.

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

a processor operable to determine a physical location of the computer system in the peer-to-peer network by determining distances to at least one global landmark node and at least one local landmark node proximally located to the computer system in the peer-to-peer network; and

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

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

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

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

25. Computer software embedded on a computer readable medium, the computer software comprising instructions performing:

determining a first distance from a node in a network to at least one global landmark node in the network;

determining a second distance from the node to at least one local landmark node in the network, wherein the local landmark node is proximally located to the node; and

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

26. The computer software of claim 25, further comprising instructions performing:

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

27. The computer software of claim 25, wherein instructions performing identifying a location in an overlay network comprise instructions performing hashing the location information to identify a location in the overlay network to store the location information.

28. The computer software of claim 25, wherein instructions performing determining a first distance from a node in a network to at least one global landmark node in the network comprise instructions performing determining distances from the node to each of a plurality of global landmark nodes in the network.

29. The computer software of claim 28, wherein instructions performing determining a second distance from the node to at least one local landmark node in the network comprise instructions performing:

determining distances from the node to each of a plurality of local landmark nodes proximally located to the node in the network.

30. The computer software of claim 29, wherein the plurality of local landmark nodes are located on routing paths between the node and the plurality of global landmark nodes.

31. The computer software of claim 29, wherein the plurality of local landmark nodes are located within a predetermined distance to the node.