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

• US 7,827,279 B2
• Filed: 01/30/2004
• Issued: 11/02/2010
• 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
• Primary Examiner(s): Hamza; Faruk
• Application Number:
  US10/767,285
• Publication Number:
  US 20050198286A1
• Time in Patent Office: 2,468 Days
• Field of Search: 709/200, 709/203, 709217-219, 709/223, 709/225, 709226-229
• 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, comprising:

selecting a set of candidate nodes from a plurality of nodes based on location information for the candidate nodes and the first node, wherein the selection is made based on comparing a distance from the first node and a distance from each node of the plurality of nodes to each one of a plurality of global landmark nodes;

applying a clustering algorithm, using a computer processor, 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.

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 comprises a distance from the first node and a distance from each node of the plurality of nodes to 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 2, 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, wherein the selection is made based on comparing a distance from the first node and a distance from each node of the plurality of nodes to each one of a plurality of global landmark nodes;

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 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. Computer software embedded on a non-transitory 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, wherein the selection is made based on comparing a distance from the first node and a distance from each node of the plurality of nodes to each one of a plurality of global landmark nodes;

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.

19. The computer software of claim 18, 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.

20. The computer software of claim 18, wherein the location information 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.