Decentralized adaptive management of distributed resource replicas in a peer-to-peer network based on QoS

• US 7,885,928 B2
• Filed: 03/08/2007
• Issued: 02/08/2011
• Est. Priority Date: 03/08/2007
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Harrington, Steven J., Liu, Hua
• Primary Examiner(s): Mahmoudi, Tony
• Assistant Examiner(s): McCue, Brittany N
• Application Number:
  US11/683,758
• Publication Number:
  US 20080222154A1
• Time in Patent Office: 1,433 Days
• Field of Search: 707/200, 707/614, 707/637
• US Class Current: 707/637
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/1834 implemented based on peer-to-peer networks, e.g. gnutella p2p communication protocols H04L67/104
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1019 Random or heuristic server selection
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1076 Resource dissemination mechanisms or network resource keeping policies for optimal resource availability in the overlay network
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

Methods and systems are provided relating to a decentralized algorithm for managing replicas of a resource in a peer-to-peer network to satisfy quality of service requirements. Individual nodes within the network storing a resource replica continually monitor the node performance against quality of service (QoS) parameters and when necessary, take appropriate action to either add or delete the resource, all the while informing the other nodes within the network that maintain a replica of the resource of the particular action for dynamic fluctuation of the count of resource replicas therein.

Claims

1. A method for distributing a plurality of replicas of a resource entity in a peer-to-peer node network for enhanced quality of service access by a resource entity requestor, comprising:

providing a first plurality of replicas of the resource entity in selected nodes of a first plurality of nodes;

designating the selected nodes by hashing a resource entity replica identifier to generate a distributed hash table correspondence between the selected nodes and hashed resource entity replica identifiers;

requesting by the requester for a requested resource entity from a selected one node, including;

communicating a local copy count of the requestor for a number of replicas to the selected one node,

estimating an extent of awareness of a current total number N of replicas by observing an awareness of local requests, and,

assessing by the selected one node whether the requestor is aware of the current total number N of replicas; and

,

responding to the request, including;

locally assessing a quality of service measure to the request by the selected one node,

when the quality of service measure meets a predetermined standard, replicating or removing the resource entity at a non-requesting node to provide a second plurality of replicas of the resource entity in additional or fewer ones of the nodes, respectively, for enhanced distributed access thereto, and,

appending a variable number identifier associated with each corresponding replica of the first plurality of replicas after and in response to the replicating or the removing of the resource entity;

wherein the variable number identifier is based on a value of the current total number (N) of replicas.

2. The method of claim 1 wherein the resource entity comprises one of a music, video, data, or software processing file.

3. The method of claim 1 wherein the assessing comprises a dynamic determining of the quality of service measure at each of the selected ones of the nodes of the first plurality.

4. The method of claim 1 wherein the assessing comprises a real time determining by at least one of the selected ones of the nodes of the first plurality.

5. The method of claim 1, wherein the requesting further includes:

requesting a desired replica by randomly selecting a number between 1 and N;

associating the randomly selected number with a resource entity identifier to form a resource entity replica identifier;

hashing the resource entity replica identifier for identifying the selected one node within the first plurality having the requested replica; and

,

addressing the requesting to the selected node.

6. The method of claim 5 wherein the assessing the quality of service measure of the request comprises detecting one of request response time, node queue length, node storage space consumption, node service competition, node resource utilization, node load balancing, request scheduling, processing cycles consumption or peripheral availability.

7. The method of claim 5 further including providing the desired one of the resource entity replicas with an indication of the number N of replicas within the node networks.

8. The method of claim 5 wherein if a requested resource entity replica is unavailable, the requester resubmits the request by selecting no more than one untried selected number between 1 and N, associating the untried selected number with the resource entity identifier to form the resource entity replica identifier, hashing the associated resource entity replica identifier for identifying a selected node within the first plurality of nodes having the requested replica, and addressing the requesting of the desired one of the resource entity replicas to the selected node.

9. The method of claim 8 wherein the untried selected number is selected at random from the untried numbers between 1 and N.

10. The method of claim 8 wherein the untried selected number is selected as the closest integer less than the average of the last selected number and 1.

11. The method of claim 1 further comprising estimating an extent of awareness of the current total number N of replicas in the decision to further replicate or reduce the number of resource entity replicas.

12. The method of claim 1 further comprising incrementing the set of selected nodes and the set of resource entity replicas by selecting the node based on the N+1 resource entity replica identifier as an additional selected node for containing an additional resource entity replica, wherein the additional selected node is selected as corresponding to the N+1 resource entity replica based on the quality of service measure.

13. The method of claim 1 further comprising decrementing the set of selected nodes and the set of resource entity replicas by selecting the node corresponding to the N^th resource entity replica identifier as a deselected node undergoing the deactivation or removal of the resource entity replica.

14. The method of claim 13, wherein the decrementing includes:

decreasing a minimum replica count requirement when a predetermined threshold is met;

marking for removal the replicas having indexes higher than the requirement, wherein the marked replicas are included at a node other than a requested node initiating a decrement request;

delaying a removal of the marked replicas until an instance when services compete for resources of the marked replicas; and

,

decrementing the local replica count at the node storing the marked replica.

15. The method of claim 1 wherein each of the replicas of the resource entity is identified by a resource entity replica identifier.

16. The method of claim 15 wherein the resource entity replica identifier is computed using a resource entity identifier and the current total number N of replicas.

17. The method of claim 1 further including associating with each of the replicas the current total number N indicative of a total number of the replicas within the node networks.

18. The method of claim 17 further comprising communicating by a service replica response data and the current total number N indicative of a total number of the replicas within the node networks to the requestor with each request of a resource entity.

19. The method of claim 1 further comprising an indication of the replication or removal process to prevent attempted multiple simultaneous replications and removals.

20. A system for adjusting a number N of replicas of a resource within a distributed network wherein a network node dynamically and independently adds or deletes a replica based on demand for the resource,

wherein addition of the replica is performed when a response time exceeds a predetermined threshold, the addition including:

appending a current total number N of replicas of a resource to a new total number N+1;

finding a service provider for an N+1 replica using a hashing function;

duplicating service on a new node;

notifying other replicas to increment their local replica count by 1; and

,

delaying updating the local replica count at a requester to the new total number N+1 until after a request is made;

wherein deletion of the replica is performed when the response time does not exceed the predetermined threshold, the deletion including;

decreasing a minimum replica count requirement;

marking for removal the replicas having indexes higher than the requirement, wherein the marked replicas are included at a node other than a requesting node initiating a decrement request;

delaying a removal of the marked replicas until an instance when services compete for resources of the marked replicas; and

,

decrementing the local replica count at the nodes storing the marked.

21. A distributed network of peer-to-peer nodes wherein a variable identifier based on a current total number N′

of replicas of a resource is stored in a selected set of the nodes and wherein each of the selected set of the nodes associates the number N with the resource stored therein, the system comprising;

(a) identifying by a requester a resource name and a local count of replicas N within a network

(b) randomly selecting by the requestor a first instance number i, wherein the first instance number is selected between 1 and N

(c) sending by the requestor a request to a first node in the set;

(d) updating a local knowledge of the requestor if the first node is maintaining copy of the resource, including;

appending i to modify the resource name,

hashing the modified resource name,

returning to the requestor the resource and a current total number N′

of available replicas, and,

replacing the local count of replicas N with the current total number N′

of available replicas; and

,

(e) responding to a failure to supply the resource and the current total number N′

if the first node is not maintaining a copy of the resource, including;

randomly selecting by the requestor a second instance number i₂, wherein the second instance number i₂, corresponds to a closest integer less than an average of the first instance number i and 1;

sending by the requestor the request to a second node of the set, and,

repeating actions (d) and (e) for the second node.