Two-level structured overlay design for cluster management in a peer-to-peer network

• US 9,015,342 B2
• Filed: 01/22/2008
• Issued: 04/21/2015
• Est. Priority Date: 01/22/2007
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc., Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Ni, Jian, Lin, Jie, Harrington, Steven J., Sharma, Naveen
• Primary Examiner(s): Lazaro, David
• Assistant Examiner(s): SHAW, ROBERT A
• Application Number:
  US12/017,534
• Publication Number:
  US 20080183891A1
• Time in Patent Office: 2,646 Days
• Field of Search: 709/239, 709/223
• US Class Current: 709/239
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1053 with pre-configuration of logical or physical connections with a determined number of other peers
• CPC Class Codes: H04L 67/1059 Inter-group management mechanisms, e.g. splitting, merging or interconnection of groups
• 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

Abstract

A method and system for designing file replication schemes in file sharing systems consider node storage constraints and node up/down statistics, file storage costs, and file transfer costs among the nodes, user request rates for the files, and user specified file availability requirements. Based on these considerations, a systematic method for designing file replication schemes can be implemented. The method first determines the number of copies of the files to be stored in the system to achieve the desired goal (e.g., to satisfy file availability requirements, or to maximize the system hit rate), and then selects the nodes at which to store the file copies to minimize the total expected cost. The file replication scheme for a peer-to-peer file sharing system in a distributed and adaptive manner can scale to a large number of nodes and files and can handle changes in the user request pattern over time.

Claims

1. A method for determining storage locations for a resource and copies thereof, a storage location being associated with a node in a network of nodes, the network of nodes forming a system, comprising:

(a) determining, when a resource first enters the system for storage thereof, a number of copies of the resource to be stored, based upon a probability that a node will be down, the copies of the resource to be stored being determined copies;

(b) randomly selecting, when the resource first enters the system for storage thereof, a number of nodes to store the determined copies thereon, the number of nodes being equal to the number of determined copies;

(c) storing the determined copies on the randomly selected nodes, the determined copies stored on the randomly selected nodes being stored determined copies;

(d) reselecting, when a predetermined number of requests have been received for the stored resource, nodes to store the stored determined copies thereon, based upon a minimization of a storage cost; and

(e) storing the stored determined copies on the reselected nodes, the stored determined copies being the determined copies previously stored on the randomly selected nodes.

2. The method as claimed in claim 1, wherein the storage cost includes a capacity of nodes to store the resources.

3. The method as claimed in claim 1, wherein said reselecting the nodes to store the stored determined copies thereon is based upon a minimization of a storage cost and a minimization of a transfer cost.

4. The method as claimed in claim 2, wherein said reselecting the nodes to store the stored determined copies thereon is based upon a minimization of a storage cost and a minimization of a transfer cost.

5. The method as claimed in claim 1, wherein said determining the number of copies is based upon calculating the sufficient number of copies to meet a predefined probability that a request for a resource can be satisfied.

6. The method as claimed in claim 1, wherein said determining the number of copies is based upon maximizing a hit rate of the system.