Distributed storing of network position information for nodes

• US 20060209717A1
• Filed: 03/16/2005
• Published: 09/21/2006
• Est. Priority Date: 03/16/2005
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Fonseca, Rodrigo, Banerjee, Sujata, Basu, Sujoy, Lee, Sung-Ju, Sharma, Puneet
• Application Number:
  US11/082,135
• Publication Number:
  US 20060209717A1
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal

Abstract

Network position information for a node in a network is determined. An infrastructure node in the network is identified for storing the network position information for the node based on a network distance to the infrastructure node.

Claims

1. A method of distributing the storing of network position information in a network, the method comprising:

determining network position information for nodes in a network; and

storing the network position information in a plurality of infrastructure nodes in the network based on network distances between the nodes in the network and the plurality of infrastructure nodes.

2. The method of claim 1, wherein storing the network position information in a plurality of infrastructure nodes in the network further comprises:

storing the network position information in a distributed database, wherein portions of the distributed database are provided at each of the plurality of infrastructure nodes.

3. The method of claim 1, wherein storing the network position information in the plurality of infrastructure nodes further comprises:

for each of the nodes, identifying a closest infrastructure node to the node and transmitting the network position information for the node to the identified infrastructure node.

4. The method of claim 1, further comprising:

wherein determining network position information for nodes in a network further comprises determining network position information for service nodes in the network; and

storing the network position information further comprises storing the network position information for each service node in at least one infrastructure node of the plurality of infrastructure nodes based on network distance.

5. The method of claim 1, wherein determining network position information for nodes in a network further comprises determining network position information for each of the plurality of infrastructure nodes.

6. The method of claim 5, wherein storing the network position further comprises storing the network position for each of the plurality of infrastructure nodes in at least one other infrastructure node of the plurality of infrastructure nodes based on network distance.

7. The method of claim 5, further comprising:

storing the network position information for each of the plurality of infrastructure nodes in all other infrastructure nodes of the plurality of infrastructure nodes.

8. The method of claim 5, further comprising:

storing the network position information for each of the plurality of infrastructure nodes in at least one other infrastructure node such that network position information for a node in the network or a query is operable to be routed to a closest infrastructure node.

9. The method of claim 4, further comprising:

storing node profiles for the service nodes in the plurality of infrastructure nodes.

10. A method of searching a distributed database in a network, wherein network position information for nodes in the network is stored in the distributed database which is distributed among a plurality of infrastructure nodes in the network based on network distances between the nodes in the network and the plurality of infrastructure nodes, the method comprising:

receiving a query from a first node in the network at a first infrastructure node of the plurality of infrastructure nodes wherein the first infrastructure node is a closest infrastructure node of the plurality of infrastructure nodes to the first node, the query including network position information for the first node;

searching information stored in a portion of the distributed database at the first infrastructure node in response to the query; and

transmitting search results to the first node.

11. The method of claim 10, further comprising:

identifying at least one other infrastructure node of the plurality of infrastructure nodes next closest to the first node; and

expanding the search to include at least one other infrastructure node.

12. The method of claim 11, further comprising:

searching another portion of the distributed database at the at least one other infrastructure node; and

transmitting search results to the first node.

13. The method of claim 10, wherein the first infrastructure node is one of a set of closest infrastructure nodes of the plurality of infrastructure nodes substantially equidistant to the first node, the method further comprising:

identifying at least one other infrastructure node in the set; and

expanding the search to include at least one other infrastructure node in the set such that the query is operable to be executed on a portion of the distributed database stored at the at least one other infrastructure node in the set.

14. The method of claim 10, wherein the query comprises a query for a service node and searching a portion of the distributed database at the first infrastructure node in response to the query further comprises:

searching the portion of the distributed database at the first infrastructure node using the network position information for the first node to identify a service node closest to the first node satisfying the query.

15. A method comprising:

determining network position information for a node;

hashing the network position information to identify a DHT node in a DHT overlay network for storing the network position information; and

transmitting the network position information to the DHT node.

16. The method of claim 15, wherein hashing the network position information to identify a DHT node in a DHT overlay network for storing the network position information further comprises:

using a hash function operable to map a point in a higher dimensional space to a lower dimensional space.

17. The method of claim 16, wherein the hash function comprises at least one of a space-filling curve and a recursive partitioning algorithm.

18. A method of searching a distributed database, the method comprising:

determining network position information for a node;

hashing the network position information to identify a DHT node in a DHT overlay network; and

transmitting a query to the DHT node to search a portion of the distributed database.

19. The method of claim 18, further comprising:

expanding the search to include at least one other portion of the distributed database at least one other DHT node.

20. The method of claim 19, wherein the at least one other DHT node is in close proximity in the overlay network to the DHT node.

21. The method of claim 18, wherein the query includes a query for a service node closest to the node transmitting the query.

22. A system comprising:

a plurality of infrastructure nodes; and

a plurality of service nodes, wherein each of the plurality of infrastructure nodes stores network position information for at least one of the plurality of service nodes based on network position information for the service nodes.

23. The system of claim 22, wherein each of the plurality of infrastructure nodes stores network position information for at least one of the plurality of service nodes based on network distances between the service nodes and the plurality infrastructure nodes.

24. The system of claim 22, wherein the plurality of infrastructure nodes comprise DHT nodes in a DHT overlay network storing network position information for the plurality of service nodes.

25. The system of claim 24, wherein each of the plurality of service nodes hashes network position information for the respective service node to identify a DHT node for storing the network position information.

26. The system of claim 25, wherein a hash function operable to map a point from a higher dimensional space to a lower dimensional space is used to hash the network position information for the service nodes.

27. The system of claim 22, wherein each of the plurality of infrastructure nodes stores a portion of a distributed database for storing network position information for the service nodes.

28. The system of claim 22, wherein each of the plurality of infrastructure nodes stores network position information for at least one other infrastructure node.

29. An apparatus comprising:

means for determining network position information of a node;

means for identifying an infrastructure node for storing the network position information based on the network position information for the node; and

means for transmitting the network position information to the identified infrastructure node.

30. The apparatus of claim 29, further comprising:

means for generating a query for a closest node to the node; and

the means for transmitting is operable to transmit the query to the identified infrastructure node.

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

determining network position information of a node; and

identifying an infrastructure node for storing the network position information based on the network position information for the node.

32. The computer software of claim 31, wherein instructions performing identifying an infrastructure node for storing the network position information based on the network position information for the node further comprise:

identifying a closest infrastructure node of a plurality of infrastructure nodes for storing the network position information based on network distances between the node and the plurality of infrastructure nodes.

33. The computer software of claim 31, wherein instructions performing identifying an infrastructure node for storing the network position information based on the network position information for the node further comprise:

hashing the network position information to identify the infrastructure node.

34. The computer software of claim 33, wherein hashing the network position information to identify the infrastructure node further comprises:

using a hash function operable to map a point from a higher dimensional space to a lower dimensional space.

35. The computer software of claim 31, further comprising instructions performing:

generating a query for a closest node to the node for transmission to the identified infrastructure node.