Peer-to-peer system and method with improved utilization

• US 7,870,218 B2
• Filed: 03/30/2004
• Issued: 01/11/2011
• 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
• Primary Examiner(s): Etienne; Ario
• Assistant Examiner(s): Todd; Gregory G
• Application Number:
  US10/813,484
• Publication Number:
  US 20040215622A1
• Time in Patent Office: 2,478 Days
• Field of Search: 709213-216, 709/218, 709/231, 709/223, 709/226, 709/229, 709/232, 707/10, 707/622, 707/620, 707/831
• US Class Current: 709/213
• 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

The present invention is directed to improving utilization in a peer-to-peer network. Each node in a peer-to-peer network is assigned a number of preferably fixed-size storage slots proportional to the node storage, a first portion of which is allocated to storage zones and a second portion of which is allocated as a free slot reserve. In accordance with an embodiment of an aspect of the invention, this split of a storage zone is delayed until the storage zone becomes full, referred to herein as “lazy splitting”. In accordance with an embodiment of another aspect of the invention, it is advantageous to allocate more storage slots at a node than its actual physical capacity referred to herein as “oversubscription”. In accordance with an embodiment of another aspect of the invention, each physical node is allocated at least one storage zone, even as a new node is added to the system.

Claims

1. A method for improving utilization in a peer-to-peer network having a plurality of nodes, the method comprising:

hosting one or more storage slots in each node in the peer-to-peer network;

wherein;

each node comprises a respective amount of physical storage capacity;

each storage slot represents a predefined amount of storage capacity;

each node hosts a number of storage slots representing a total amount of storage capacity greater than the node'"'"'s physical storage capacity, wherein each node is allocated 2×

N−

1 virtual slots, where N equals the physical storage capacity of the node divided by the predefined amount of storage capacity of a storage slot; and

at each node, a first portion of the storage slots host storage zones and any remaining storage slots are allocated as free slot reserve storage slots;

the method further comprising;

storing data in the storage slots hosting storage zones; and

when a storage slot hosting a storage zone reaches a full capacity of the storage zone,

splitting the data in the storage slot hosting the storage zone into a first and second portion,

converting a free slot reserve storage slot into a new storage slot hosting a storage zone, and

transferring the second portion of the data to the new storage slot hosting the storage zone.

2. The method of claim 1 wherein a storage zone at a node is transferred to another node in the peer-to-peer network if the data inserted into the storage zones at the node fills the actual physical capacity of the node.

3. The method of claim 2 where a local search for candidate nodes in a transfer set is conducted prior to transfer of the storage zone.

4. The method of claim 1 wherein the new storage zone is transferred to and hosted by a free slot reserve storage slot on a different node when the storage zones hosted at the node exceed the storage slots allocated at the node.

5. The method of claim 4 where a local search for candidate nodes in a transfer set is conducted prior to transfer of the new storage zone.

6. The method of claim 1 wherein the data is associated with hashkeys of a hash function and where each storage zone is responsible for a subset of all hashkeys.

7. The method of claim 6 wherein the hashkeys are uniformly distributed by the hash function.

8. The method of claim 1 wherein the storage slots are of a fixed-size.

9. The method of claim 1, wherein each storage zone is hosted by a storage slot located within a particular physical node.

10. The method of claim 1, wherein a zone is hosted within a slot and a size of the slot is a system wide constraint representing the limit size to which a zone can grow before it fills the slot and must be split.