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

• US 20080177767A1
• Filed: 01/22/2008
• Published: 07/24/2008
• Est. Priority Date: 01/22/2007
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Hernandez, Andres Quiroz, Ni, Jian, Lin, Jie
• Granted Patent: US 8,756,253 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• 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 network overlay comprising:

a logical network structure of nodes, an ordering of the nodes being defined;

said logical network structure including a first cluster of nodes, each node within said first cluster contains a link to a previous node in said first cluster and a link to a successor node in said first cluster, a node within said first cluster contains a virtual link to a node in a second cluster of nodes.

2. The network overlay, as claimed in claim 1, wherein said virtual link includes a link to a predecessor node selected from the nodes of said second cluster.

3. The network overlay, as claimed in claim 1, wherein said virtual link includes a link to a successor node selected from the nodes of said second cluster.

4. The network overlay, as claimed in claim 2, wherein said virtual link includes a link to a successor node selected from the nodes of said second cluster.

5. The network overlay, as claimed in claim 1, wherein the logical network structure of nodes includes a plurality of clusters, the plurality of clusters being ordered.

6. The network overlay, as claimed in claim 1, wherein each node contains an identifier for itself and an identified for its cluster.

7. The network overlay, as claimed in claim 1, wherein each node and cluster ordering is based upon their respective identifiers.

8. The network overlay, as claimed in claim 1, wherein a node contains a virtual link to a previous cluster and a virtual link to a successor cluster.

9. The network overlay, as claimed in claim 1, wherein the logical network structure of nodes includes multiple levels of clusters.

10. The network overlay, as claimed in claim 9, wherein a node contains a virtual link for a cluster at a different level.

11. The network overlay, as claimed in claim 9, wherein the multiple levels of clusters are ordered.

12. The network overlay, as claimed in claim 9, wherein a node contains a virtual link for a previous cluster at a first level and a virtual link for a previous cluster at a second level.

13. The network overlay, as claimed in claim 12, wherein the first level and the second level are different.

14. The network overlay, as claimed in claim 1, wherein the logical network structure of nodes includes a single level of clusters.

15. The network overlay, as claimed in claim 1, wherein the clustering of nodes is based upon a locality metric.

16. A resource storage and retrieval method, comprising:

(a) storing more than one instance of a resource within a peer-to-peer network;

(b) storing locations of the stored instances of the resource in a first index node;

(c) storing locations of the stored instances of the resource in a second index node; and

(d) storing one instance of the resource at an optimal location within the peer-to-peer network.

17. The method as claimed in claim 16, wherein a number of stored resource instances is dependent upon an up probability of nodes within the peer-to-peer network.

18. The method as claimed in claim 16, wherein a number of index nodes storing the locations of the stored instances of the resource is dependent upon an up probability of nodes within the peer-to-peer network.

19. The method as claimed in claim 16, wherein the peer-to-peer network includes a cluster of nodes.

20. The method as claimed in claim 19, wherein the first index node is located in a same cluster of nodes as one instance of the stored resource.

21. The method as claimed in claim 19, wherein the first index node is located in accordance with a hash table.

22. The method as claimed in claim 19, wherein the first index node is located in accordance with hashing a name of the resource.

23. The method as claimed in claim 16, wherein the first index node and the second index node are successively ordered nodes within a cluster.