Selecting nodes close to another node in a network using location information for the nodes

• US 20050198286A1
• Filed: 01/30/2004
• Published: 09/08/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 7,827,279 B2
• Time in Patent Office: Days
• US Class Current: 709/225
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/126 minimising geographical or physical path length
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

A network includes a plurality of nodes. A set of candidate nodes from the plurality of nodes is selected based on location information for the candidate nodes and a first node also in the network. A clustering algorithm is applied to the location information for the candidate nodes and the first node, and a subset of the set of candidate nodes closest to the first node is identified based on the results of applying the clustering algorithm.

Claims

1. A method of identifying at least one node close to a first node in a network, the method comprising:

selecting a set of candidate nodes from a plurality of nodes based on location information for the candidate nodes and the first node;

applying a clustering algorithm to the location information for the candidate nodes and the first node; and

identifying a subset of the set of candidate nodes closest to the first node based on results of applying the clustering algorithm.

2. The method of claim 1, wherein selecting a set of candidate nodes comprises:

comparing location information for the plurality of nodes to the location information for the first node to select the set of candidate nodes from the plurality of nodes closest to the first node.

3. The method of claim 2, further comprising:

receiving the location information for the first node at a node in a distributed hash table overlay network, the distributed hash table overlay network being a logical representation of the network including the first node and the plurality of nodes; and

storing the location information for the first node at the node in the distributed hash table overlay network.

4. The method of claim 3, further comprising:

the first node hashing the location information for the first node to identify a location in the distributed hash table overlay network to store the location information for the first node, wherein the node in the distributed hash table overlay network is approximately at the identified location.

5. The method of claim 3, further comprising:

receiving the location information for the plurality of nodes at the node in the distributed hash table overlay network; and

storing the received location information for the plurality of nodes at the node in the distributed hash table overlay network.

6. The method of claim 5, further comprising:

retrieving the location information for the plurality of nodes and the first node from stored location information at the node in the distributed hash table overlay network; and

comparing the retrieved location information to select the set of candidate nodes proximally located to the first node from the plurality of nodes.

7. The method of claim 1, wherein the location information for the first node and the plurality of nodes comprises landmark vectors for each of the first node and the plurality of nodes, the landmark vectors for each of the first node and the plurality of nodes including distances measured to a plurality of global landmark nodes and at least one local landmark node proximally located to a respective one of the first node and the plurality of nodes.

8. The method of claim 7, wherein comparing location information for the plurality of nodes to the location information for the first node comprises:

comparing global landmark vector portions of the landmark vectors for the first node and the plurality of nodes; and

selecting candidate nodes from the plurality of nodes having landmark vectors with a predetermined similarity to the landmark vector for the first node.

9. The method of claim 7, wherein the at least one local landmark node proximally located to a respective one of the first node and the plurality of nodes is one of on a routing path between the respective node and one of the plurality of global landmark nodes and within a predetermined distance to the respective node.

10. The method of claim 1, further comprising:

determining distances to each of the subset of candidate nodes from the first node; and

selecting a closest node to the first node from the subset of candidate nodes based on the determined distances.

11. The method of claim 1, further comprising:

selecting a node from the subset of nodes based on at least one of distances to each of the subset of candidate nodes from the first node and quality of service characteristics associated with the subset of nodes.

12. The method of claim 1, wherein the clustering algorithm is an algorithm operable to identify similarities between the location information for the first node and the candidate nodes.

13. The method of claim 12, wherein the clustering algorithm comprises at least one a min_sum, max_diff, order, inner product algorithm, k-means, principal component analysis, and latent semantic indexing.

14. A node in a network comprising:

means for selecting a set of candidate nodes from a plurality of nodes based on location information for the candidate nodes and a first node;

means for applying a clustering algorithm to the location information for the candidate nodes and the first node; and

means for identifying a subset of the set of candidate nodes closest to the first node based on the results of applying the clustering algorithm.

15. The node of claim 14, further comprising:

means for receiving the location information for the plurality of nodes and the first node; and

means for storing the location information for the plurality of nodes and the first node.

16. The node of claim 15, further comprising:

means for retrieving the location information for the plurality of nodes and the first node from the means for storing; and

means for comparing the location information for the plurality of nodes and the first node to select the candidate nodes.

17. The node of claim 14, further comprising means for transmitting a list of the subset of candidate nodes to the first node.

18. A computer system operable to connect to a peer-to-peer network and operable to function as a distributed hash table node in a distributed hash table overlay network, the distributed hash table overlay network being a logical representation of the peer-to-peer network, wherein the computer system comprises:

a memory operable to store location information for a plurality of nodes in the peer-to-peer network that are physically close in the network; and

a processor operable to compare the location information for the plurality of nodes to location information for a first node to identify a set of nodes from the plurality of nodes that are physically close to the first node in the peer-to-peer network.

19. The computer system of claim 18, wherein the processor is operable to apply a clustering algorithm to the location information for the set of nodes to identify a subset of nodes closest to the first node.

20. The computer system of claim 18, wherein the location information for the first node and the plurality of nodes comprises distances measured from each of the first node and the plurality of nodes to a plurality of global landmark nodes and to at least one local landmark node proximally located to a respective one of the first node and the plurality of nodes.

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

selecting a set of candidate nodes from a plurality of nodes based on location information for the candidate nodes and a first node;

applying a clustering algorithm to the location information for the candidate nodes and the first node; and

identifying a subset of the set of candidate nodes closest to the first node based on the results of applying the clustering algorithm.

22. The computer software of claim 21, wherein instructions performing selecting a set of candidate nodes comprises:

comparing location information for the plurality of nodes to the location information for the first node to select the set of candidate nodes physically close to the first node.

24. A method of storing information in a node in a network, wherein the node is operable to function as a distributed hash table node in a distributed hash table overlay network, the distributed hash table overlay network being a logical representation of the network, wherein the method comprises:

receiving location information for a plurality of nodes, the nodes being located physically close in the network; and

storing the location information in a table, wherein the location information for the plurality of nodes comprises distances measured from each of the plurality of nodes to a plurality of global landmark nodes and to at least one local landmark node.

23. The computer software of claim 26, wherein the location information for the first node and the plurality of nodes comprises distances measured from each of the first node and the plurality of nodes to a plurality of global landmark nodes and to at least one local landmark node proximally located to a respective one of the first node and the plurality of nodes.

25. The method of claim 24, further wherein the at least one local landmark node is proximally located to a respective node of the plurality of nodes.

26. The method of claim 24, further comprising:

storing measured network metrics associated with at least one of the plurality of nodes in the table.