System and method for providing a peer indexing service

• US 7,478,120 B1
• Filed: 04/27/2004
• Issued: 01/13/2009
• Est. Priority Date: 04/27/2004
• Status: Expired due to Fees

• Current Assignee: Orinno Software Co., Ltd.
• Original Assignee: Orinno Software Co., Ltd.
• Inventors: Zhang, Xiaohai
• Primary Examiner(s): Wassum; Luke S.
• Assistant Examiner(s): Badawi; Sherief
• Application Number:
  US10/832,657
• Time in Patent Office: 1,722 Days
• Field of Search: None
• US Class Current: 709/201
• 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 67/1089 Hierarchical topologies

Abstract

A peer graph is formed by assigning published identifiers to peer nodes that each map to network addresses. A signed number space is defined based on the published identifiers. Given a key, a closest peer node is determined by maintaining data identifying other peer nodes. Index information identifying the key and an associated value are stored as a pair on a storing peer node. Further key and value pairs are maintained in a local indexing database. Hierarchically structured levels are organized in a peer indexing database as a factor of the number space size. A group identifier is stored at a peer indexing database level determined as a function of the storing peer node, level and number space size factor. The key is hashed as a function of the initial group identifier and number space size factor to identify a closest peer node. Key and value pairs are transiently maintained.

Claims

1. A system for providing a peer indexing service, comprising:

a peer graph formed by assigning published identifiers to each of one or more peer nodes that each map to network addresses and defining a signed number space over the peer graph based on the published identifiers;

a peer name service to determine a closest peer node given a key by maintaining data identifying other peer nodes in the peer graph; and

a storing peer node in the peer graph to maintain index information identifying the key and an associated value stored as a pair, comprising;

a local indexing database maintaining further key and value pairs;

a peer indexing database comprising a plurality of hierarchically structured levels as a factor of the number space size, comprising;

a level group identifier at a level of the peer indexing database and determined as a function of the published identifier of the storing peer node, the level and the number space size factor;

a hash function to hash the key as a function of the initial level group identifier and the number space size factor to identify a closest peer node sharing the initial level group identifier; and

a peer index cache transiently maintaining key and value pairs.

2. A system according to claim 1, further comprising:

a count of each instance of the index information at the storing peer node, wherein the index information is published to an initial group indexing peer node by evaluating the instance count change relative to a threshold or a baseline.

3. A system according to claim 2, wherein the index information is unpublished from the initial group indexing peer node by evaluating the instance count change relative to a further threshold or the baseline.

4. A system according to claim 2, further comprising:

a storage module to store one or more of the further key and value pairs on the initial group indexing peer node.

5. A system according to claim 1, further comprising:

a subsequent level group identifier determined as a function of the published identifier of the storing peer node, a factor of the number space size and a level number subsequent to the initial level; and

an identifier to identify a subsequent group indexing peer node sharing the subsequent level group identifier, wherein the index information is published to the subsequent group indexing peer node.

6. A system according to claim 5, further comprising:

a count of each instance of the index information, wherein the index information is published to the subsequent group indexing peer node by evaluating the instance count change relative to a threshold or a baseline.

7. A system according to claim 6, wherein the index information is unpublished from the subsequent group indexing peer node by evaluating the instance count relative to a further threshold or the baseline.

8. A system according to claim 5, wherein the group identifier G_J(P) for each peer node P at one such level number J is determined in accordance with the equation:

$G_J<br><br>\left(P\right)=\lfloor <br><br>\frac{P}{2^{J\times <br><br>T}}\rfloor <br><br>$

for J=0, 1 . . . , S/T, where S is the number space size and T is the number space size factor.

9. A system according to claim 8, wherein each peer node P belongs to a group R_J(P) at one such level number J determined in accordance with the equation:

$R_J<br><br>\left(P\right)=\left[\lfloor <br><br>\frac{P}{2^{J\times <br><br>T}}\rfloor <br><br>\times <br><br>2^{J\times <br><br>T},\left(\lfloor <br><br>\frac{P}{2^{J\times <br><br>T}}\rfloor <br><br>+1\right)\times <br><br>2^{J\times <br><br>T}\right)$

for J=0, 1, . . . , S/T, where S is the number space size and T is the number space size factor.

10. A system according to claim 9, wherein the hashing function H_J(P,K) for a given key K stored at a peer node P at one such level number J is determined in accordance with the equation:

$H_J<br><br>\left(P,K\right)=\left(\mathrm{Hash}<br><br>\left(K\right)<br><br>{\mathrm{\%2}}^{J\times <br><br>T}\right)+\lfloor <br><br>\frac{P}{2^{J\times <br><br>T}}\rfloor <br><br>\times <br><br>2^{J\times <br><br>T}$

for J=0, 1, . . . , S/T, where S is the number space size and T is the number space size factor.

11. A system according to claim 10, wherein the level group indexing peer node P_J is determined in accordance with the equation:

P_J=C_J(H_J(P,K))=C_J(H_J(G_J,K)).

12. A system according to claim 1, further comprising:

a storing peer node to process a query received for a key and value pair, wherein the stored key and value pair is provided.

13. A system according to claim 1, further comprising:

one of a group indexing peer node and a subsequent group indexing peer node to process a query received from a receiving group indexing peer node for a key and value pair, wherein the query is forwarded to one other such subsequent group indexing peer node at a subsequent level if the level of the query is higher than the level of the receiving group indexing peer node.

14. A system according to claim 13, further comprising:

a query processor to process a query for a key and value pair received at one such group indexing peer node comprising providing an authoritative answer if the level of receiving group indexing peer node matches the level of the query and the receiving group indexing peer node is in the same level group as a group identifier in the query.

15. A system according to claim 13, further comprising:

a query processor to process a query for a key and value pair received at one such group indexing peer node comprising forwarding the query to a level group indexing peer node identified by a group identifier provided in the query if the group identifier of the receiving group indexing peer node does not match the group identifier provided in the query and the level of the query matches the level of the receiving group indexing peer node.

16. A system according to claim 1, further comprising:

a time-to-live value assigned to each key and value pair stored in the local index cache, wherein the key and value pair is discarded upon an expiration of the time-to-live value.

17. A system according to claim 1, wherein the level number is bounded by the number space size, further comprising:

a subsequent peer node at a bounded level number to process a query received for a key and value pair, wherein the query is forwarded to the storing peer node.

18. A system according to claim 1, wherein each network address comprises one of an IP version 4 network address and IP version 6 IP network address.

19. A system according to claim 1, wherein the data comprises an address certificate defining the mapping between the published identifier and the network address.

20. A system according to claim 1, wherein each publisher identifier comprises a hash of a crypto key assigned to the peer node and an instance identifier assigned to the peer graph.

21. A method for providing a peer indexing service, comprising:

forming a peer graph by assigning published identifiers to each of one or more peer nodes that each map to network addresses and defining a signed number space over the peer graph based on the published identifiers;

determining a closest peer node given a key by maintaining data identifying other peer nodes in the peer graph; and

maintaining index information identifying the key and an associated value stored as a pair on a storing peer node in the peer graph, comprising;

maintaining further key and value pairs in a local indexing database;

organizing a plurality of hierarchically structured levels in a peer indexing database as a factor of the number space size, comprising;

storing a level group identifier at a level of the peer indexing database determined as a function of the published identifier of the storing peer node, the level and the number space size factor;

hashing the key as a function of the initial level group identifier and the number space size factor to identify a closest peer node sharing the initial level group identifier; and

transiently maintaining key and value pairs in a peer index cache.

22. A method according to claim 21, further comprising:

tracking a count of each instance of the index information at the storing peer node, wherein the index information is published to the an initial group indexing peer node by evaluating the instance count change relative to a threshold or a baseline.

23. A method according to claim 22, wherein the index information is unpublished from the initial group indexing peer node by evaluating the instance count change relative to a further threshold or the baseline.

24. A method according to claim 22, further comprising:

storing one or more of the further key and value pairs on the initial group indexing peer node.

25. A method according to claim 21, further comprising:

determining a subsequent level group identifier as a function of the published identifier of the storing peer node, a factor of the number space size and a level number subsequent to the initial level; and

identifying a subsequent group indexing peer node sharing the subsequent level group identifier; and

publishing the index information to the subsequent group indexing peer node.

26. A method according to claim 25, further comprising:

tracking a count of each instance of the index information, wherein the index information is published to the subsequent group indexing peer node by evaluating the instance count relative to a threshold or a baseline.

27. A method according to claim 26, wherein the index information is unpublished from the subsequent group indexing peer node by evaluating the instance count relative to a further threshold or the baseline.

28. A method according to claim 25, wherein the group identifier G_J(P) for each peer node P at one such level number J is determined in accordance with the equation:

$G_J<br><br>\left(P\right)=\lfloor <br><br>\frac{P}{2^{J\times <br><br>T}}\rfloor <br><br>$

for J=0, 1, . . . , S/T, where S is the number space size and T is the number space size factor.

29. A method according to claim 28, wherein each peer node P belongs to a group R_J(P) at one such level number J determined in accordance with the equation:

$R_J<br><br>\left(P\right)=\left[\lfloor <br><br>\frac{P}{2^{J\times <br><br>T}}\rfloor <br><br>\times <br><br>2^{J\times <br><br>T},\left(\lfloor <br><br>\frac{P}{2^{J\times <br><br>T}}\rfloor <br><br>+1\right)\times <br><br>2^{J\times <br><br>T}\right)$

for J=0, 1, . . . , S/T, where S is the number space size and T is the number space size factor.

30. A method according to claim 29, wherein the hashing function H_J(P,K) for a given key K stored at a peer node P at one such level number J is determined in accordance with the equation:

$H_J<br><br>\left(P,K\right)=\left(\mathrm{Hash}<br><br>\left(K\right)<br><br>{\mathrm{\%2}}^{J\times <br><br>T}\right)+\lfloor <br><br>\frac{P}{2^{J\times <br><br>T}}\rfloor <br><br>\times <br><br>2^{J\times <br><br>T}$

for J=0, 1, . . . , S/T, where S is the number space size and T is the number space size factor.

31. A method according to claim 30, wherein the level group indexing peer node P_J is determined in accordance with the equation:

P_J=C_J(H_J(P,K))=C_J(H_J(G_J,K)).

32. A method according to claim 21, further comprising:

processing a query for a key and value pair received at a storing peer node comprising providing the stored key and value pair.

33. A method according to claim 21, further comprising:

processing a query for a key and value pair received at one of a group indexing peer node and a subsequent group indexing peer node from a receiving group indexing peer node comprising forwarding the query to one other such subsequent group indexing peer node at a subsequent level if the level of the query is higher than the level of the receiving group indexing peer node.

34. A method according to claim 33, further comprising:

processing a query for a key and value pair received at one such group indexing peer node comprising providing an authoritative answer if the level of receiving group indexing peer node matches the level of the query and the receiving group indexing peer node is in the same level group as a group identifier in the query.

35. A method according to claim 33, further comprising:

processing a query for a key and value pair received at one such group indexing peer node comprising forwarding the query to a level group indexing peer node identified by a group identifier provided in the query if the group identifier of the receiving group indexing peer node does not match the group identifier provided in the query and the level of the query matches the level of the receiving group indexing peer node.

36. A method according to claim 21, further comprising:

assigning a time-to-live value to each key and value pair stored in the local index cache; and

discarding the key and value pair upon an expiration of the time-to-live value.

37. A method according to claim 21, wherein the level number is bounded by the number space size, further comprising:

processing a query for a key and value pair received at a subsequent peer node at a bounded level number comprising forwarding the query to the storing peer node.

38. A method according to claim 21, wherein each network address comprises one of an IP version 4 network address and IP version 6 IP network address.

39. A method according to claim 21, wherein the data comprises an address certificate defining the mapping between the published identifier and the network address.

40. A method according to claim 21, wherein each publisher identifier comprises a hash of a crypto key assigned to the peer node and an instance identifier assigned to the peer graph.

41. A computer-readable storage medium holding code for performing the method according to claim 21.

42. An apparatus for providing a peer indexing service, comprising:

means for forming a peer graph by means for assigning published identifiers to each of one or more peer nodes that each map to network addresses and means for defining a signed number space over the peer graph based on the published identifiers;

means for determining a closest peer node given a key by means for maintaining data identifying other peer nodes in the peer graph; and

means for maintaining index information identifying the key and an associated value stored as a pair on a storing peer node in the peer graph, comprising;

means for maintaining further key and value pairs in a local indexing database;

means for organizing a plurality of hierarchically structured levels in a peer indexing database as a factor of the number space size, comprising;

means for storing a level group identifier at a level of the peer indexing database determined as a function of the published identifier of the storing peer node, the level and the number space size factor;

means for hashing the key as a function of the initial level group identifier and the number space size factor to identify a closest peer node sharing the initial level group identifier; and

means for transiently maintaining key and value pairs in a peer index cache.