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

• US 8,756,253 B2
• Filed: 01/22/2008
• Issued: 06/17/2014
• Est. Priority Date: 01/22/2007
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Lin, Jie, Ni, Jian, Hernandez, Andres Quiroz
• Primary Examiner(s): LU, KUEN S
• Application Number:
  US12/017,530
• Publication Number:
  US 20080177767A1
• Time in Patent Office: 2,338 Days
• Field of Search: 707/802, 707/640
• US Class Current: 707/802
• 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 comprising:

a plurality of nodes forming a logical network structure of nodes, each node including a processor and memory, an ordering of the nodes being defined;

said plurality of nodes including a first cluster of nodes and a second cluster of nodes, said first cluster of nodes having a ring-based topology, said second cluster of nodes having a ring-based topology, each node within said first cluster containing a point-to-point link to a previous node in said first cluster and a point-to-point link to a successor node in said first cluster, said previous node being different from said successor node, a node within said first cluster containing a virtual link to a node in said second cluster of nodes;

said virtual link between said node within said first cluster and said node within said second cluster including a first virtual point-to-point link to a successor node selected from the nodes of said second cluster and a second virtual point-to-point link to a predecessor node selected from the nodes of said second cluster, said successor node selected from the nodes of said second cluster having a point-to-point link to said predecessor node selected from the nodes of said second cluster.

2. The network, as claimed in claim 1, wherein the plurality of nodes includes a plurality of clusters, the plurality of clusters being ordered.

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

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

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

6. The network, as claimed in claim 1, wherein the plurality of nodes includes multiple levels of clusters.

7. The network, as claimed in claim 6, wherein a node contains a virtual link for a cluster at a different level.

8. The network, as claimed in claim 6, wherein the multiple levels of clusters are ordered.

9. The network, as claimed in claim 6, 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.

10. The network, as claimed in claim 9, wherein the first level and the second level are different.

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

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

13. A resource storage and retrieval method, comprising:

(a) storing a number of instances of a resource within a peer-to-peer network, the peer-to-peer network including a plurality of nodes, each node including a processor and memory, the number of instances of a resource stored within the peer-to-peer network being dependent upon an up probability of nodes within the peer-to-peer network;

(b) storing locations of the stored instances of the resource in a first index node, the first index node including a first processor and a first memory;

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

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

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

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

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

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

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

19. A resource storage and retrieval method, comprising:

(a) storing more than one instance of a resource within a peer-to-peer network, the peer-to-peer network including a plurality of nodes, each node including a processor and memory; and

(b) storing locations of the stored instances of the resource in a number of index nodes within the peer-to-peer network, each index node including a processor and memory, the number of index nodes storing the locations of the stored instances of the resource being dependent upon an up probability of nodes within the peer-to-peer network.