TWO-LEVEL STRUCTURED OVERLAY DESIGN FOR CLUSTER MANAGEMENT IN A PEER-TO-PEER NETWORK

• US 20080183891A1
• Filed: 01/22/2008
• Published: 07/31/2008
• 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, Sharma, Naveen, Harrington, Steven J., Lin, Jie
• Granted Patent: US 9,015,342 B2
• Time in Patent Office: Days
• 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 the storage locations in a network for copies of a resource, comprising:

(a) determining a number of copies of the resource to be stored and selecting which nodes of the network should store a copy of the resource;

said determining and selecting is based upon a probability that a node will be down.

2. The method as claimed in claim 1, wherein said determining and selecting is also based upon a capacity of nodes to store the resources.

3. The method as claimed in claim 1, wherein said determining and selecting is also based upon a storage cost.

4. The method as claimed in claim 2, wherein said determining and selecting is also based upon a storage cost.

5. The method as claimed in claim 1, wherein said determining and selecting is also based upon a transfer cost.

6. The method as claimed in claim 2, wherein said determining and selecting is also based upon a transfer cost.

7. The method as claimed in claim 3, wherein said determining and selecting is also based upon a transfer cost.

8. The method as claimed in claim 4, wherein said determining and selecting is also based upon a transfer cost.

9. The method as claimed in claim 1, wherein said determining and selecting is also based upon an expected request rate for a resource.

10. The method as claimed in claim 2, wherein said determining and selecting is also based upon an expected request rate for a resource.

11. The method as claimed in claim 3, wherein said determining and selecting is also based upon an expected request rate for a resource.

12. The method as claimed in claim 4, wherein said determining and selecting is also based upon an expected request rate for a resource.

13. The method as claimed in claim 5, wherein said determining and selecting is also based upon an expected request rate for a resource.

14. The method as claimed in claim 6, wherein said determining and selecting is also based upon an expected request rate for a resource.

15. The method as claimed in claim 7, wherein said determining and selecting is also based upon an expected request rate for a resource.

16. 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.

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

18. The method as claimed in claim 1, wherein said selecting of nodes is based upon a minimization of the storage and transfer costs.

19. The method as claimed in claim 1, wherein said selecting of nodes is applied to resources in order of the request rates for those resources.

20. The method as claimed in claim 1, wherein said selecting of nodes is random.

21. The method as claimed in claim 1, wherein said selecting of nodes for storage locations is dynamic and adaptive.

22. The method as claimed in claim 15, wherein said expected request rate for a resource is dynamically calculated by channeling a request through an index node and collecting request statistics.

23. The method as claimed in claim 1, wherein when a resource first enters the system the number of copies is determined such as to meet a predefined probability that a request can be satisfied.

24. The method as claimed in claim 1, wherein when a resource first enters the system the nodes at which the resource is stored are selected randomly.

25. The method as claimed in claim 1, wherein when a resource request rate has be established, the nodes on which the resource is stored is recalculated so as to minimize costs.