Peer-to-peer system and method with prefix-based distributed hash table

• US 20050135381A1
• Filed: 03/30/2004
• Published: 06/23/2005
• Est. Priority Date: 04/09/2003
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Dubnicki, Cezary, Ungureanu, Cristian
• Granted Patent: US 7,304,994 B2
• Time in Patent Office: Days
• US Class Current: 370/395.320
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• 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/1072 Discovery involving ranked list compilation of candidate peers
• CPC Class Codes: H04L 67/108 characterised by resources being split in blocks or fragments
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

An architecture for a peer-to-peer network is disclosed which advantageously is able to maintain short fixed path length routing as the network grows.

Claims

1. A method for routing in a peer-to-peer network, the method comprising the steps of:

receiving a message comprising a hash key of a hash function, the hash key further comprising a fixed portion which is associated with one of a plurality of zones in the peer-to-peer network and where the fixed portion comprises a string of bits that is further grouped into a number of disjoint groupings of bits;

consulting a jump table which associates combinations of the groupings of bits with routing destination zones in the peer-to-peer network; and

if an entry is found on the jump table which associates a destination zone with a next unresolved grouping of bits in the fixed portion of the hash key, then routing the message to the destination zone in the peer-to-peer network so that the message can be routed in a fixed path length to a final destination zone associated with the fixed portion of the hash key.

2. The method of claim 1 wherein if an entry is not found on the jump table, then a next destination zone is selected which partially resolves the next unresolved grouping of bits in the fixed portion of the hash key so as to reduce a distance metric to the final destination zone in the peer-to-peer network.

3. The method of claim 2 wherein the next destination zone is selected by consulting the jump table to partially resolve some bits in the next unresolved grouping of bits in the fixed portion of the hash key.

4. The method of claim 2 wherein the next destination zone is selected by consulting a table of neighboring zones to resolve at least one bit in the next unresolved grouping of bits in the fixed portion of the hash key.

5. The method of claim 2 wherein, if an optimal next destination zone cannot be selected, a blacklist of destination zones already tried by the message is maintained with the message and the message is routed to a destination zone not on the blacklist.

6. The method of claim 2 wherein the distance metric is based on a lexicographical order distance from the string of bits in the fixed portion of the hash key.

7. The method of claim 1 wherein, if the jump tables are up-to-date, the message is routed to the final destination zone in the peer-to-peer network in a number of hops equal to the number of groupings of bits.

8. The method of claim 7 wherein the jump table can be recomputed when changes occur in the peer-to-peer network by resizing the groupings of bits so that the number of hops remains constant.

9. The method of claim 1 wherein the fixed portion of the hash key is a prefix of the hash key.

10. A method for use in a peer-to-peer network, the method comprising the steps of:

associating a fixed portion of hash keys of a hash function with one of a plurality of zones in the peer-to-peer network, where each hash key generated from the hash function is associated with an object in the peer-to-peer network and where the fixed portion of the hash key comprises a string of bits that is further grouped into a number of disjoint groupings of bits; and

maintaining state for each zone in the peer-to-peer network regarding the groupings of bits so as to route messages to a destination zone in the peer-to-peer network in a fixed path length.

11. The method of claim 10 wherein the state for each zone of the peer-to-peer network is recomputed if the peer-to-peer network changes so as to maintain the fixed path length.

12. The method of claim 10 wherein the fixed path length has a number of hops equal to the number of groupings of bits.

13. The method of claim 10 wherein the state maintained for a zone further comprises a jump table which associates combinations of the groupings of bits with destination zones in the peer-to-peer network.

14. The method of claim 10 wherein a zone in the peer-to-peer network may be split into a first and second children zones by expanding the fixed portion of the hash key by at least one bit and associating the hash keys associated with the zone to either the first or second children zones.

15. The method of claim 10 wherein the fixed portion of the hash key is a prefix of the hash key.

16. A computer-readable medium comprising instructions for routing in a peer-to-peer network, the instructions when executed on a computer perform the method of:

receiving a message comprising a hash key of a hash function, the hash key further comprising a fixed portion which is associated with one of a plurality of zones in the peer-to-peer network and where the fixed portion comprises a string of bits that is further grouped into a number of groupings of bits;

consulting a jump table which associates combinations of the groupings of bits with routing destination zones in the peer-to-peer network; and

if an entry is found on the jump table which associates a destination zone with a next unresolved grouping of bits in the fixed portion of the hash key, then routing the message to the destination zone in the peer-to-peer network so that the message can be routed in a fixed path length to a final destination zone associated with the fixed portion of the hash key.

17. The computer-readable medium of claim 16 wherein if an entry is not found on the jump table, then a next destination zone is selected which partially resolves the next unresolved grouping of bits in the fixed portion of the hash key so as to reduce a distance metric to the final destination zone in the peer-to-peer network.

18. The computer-readable medium of claim 17 wherein the next destination zone is selected by consulting the jump table to partially resolve some bits in the next unresolved grouping of bits in the fixed portion of the hash key.

19. The computer-readable medium of claim 17 wherein the next destination zone is selected by consulting a table of neighboring zones to resolve at least one bit in the next unresolved grouping of bits in the fixed portion of the hash key.

20. The computer-readable medium of claim 17 wherein, if an optimal next destination zone cannot be selected, a blacklist of destination zones already tried by the message is maintained and the message is routed to a destination zone not on the blacklist.

21. The computer-readable medium of claim 17 wherein the distance metric is based on a lexicographical order distance from the string of bits in the fixed portion of the hash key.

22. The computer-readable medium of claim 16 wherein, if the jump tables are up-to-date, the message is routed to the final destination zone in the peer-to-peer network in a number of hops equal to the number of groupings of bits.

23. The computer-readable medium of claim 22 wherein the jump table can be recomputed when changes occur in the peer-to-peer network by resizing the groupings of bits so that the number of hops remains constant.

24. The computer-readable medium of claim 16 wherein the fixed portion of the hash key is a prefix of the hash key.

25. A node for a peer-to-peer network comprising:

a first interface for communication with other nodes in the peer-to-peer network;

a second interface to at least one storage device, the second interface storing objects on the storage device where each object stored at the node is associated with a hash key of a hash function where each hash key has a fixed portion associated with a zone of the peer-to-peer network hosted at the node;

a memory unit for storing state for the zone in the peer-to-peer network hosted at the node, the state comprising associations between groupings of bits in the fixed portion of the hash key and destination zones in the peer-to-peer network a routing processor which can route messages in the peer-to-peer network using the first interface and the state stored on the memory unit so that a message can be routed to a destination zone in the peer-to-peer network in a fixed path length.

26. The node of claim 25 wherein the state stored in the memory unit can be recomputed if the peer-to-peer network changes so as to maintain the fixed path length.

27. The node of claim 25 wherein the fixed path length has a number of hops equal to a number of the groupings of bits in the fixed portion of the hash key.

28. The node of claim 25 wherein the fixed portion of the hash key is a prefix of the hash key.