System and method for allocating requests for objects and managing replicas of objects on a network

• US 6,256,675 B1
• Filed: 05/06/1998
• Issued: 07/03/2001
• Est. Priority Date: 05/06/1997
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Rabinovich, Michael
• Primary Examiner(s): Dinh, Dung C.
• Assistant Examiner(s): TRIM, NKOSI N
• Application Number:
  US09/073,439
• Time in Patent Office: 1,154 Days
• Field of Search: 709/241, 709/239, 709/217, 709/218, 709/219, 709/228, 709/225
• US Class Current: 709/241
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• 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/101 based on network conditions
• CPC Class Codes: H04L 67/1029 using data related to the state of servers by a load balancer
• CPC Class Codes: H04L 67/1031 Controlling of the operation of servers by a load balancer, e.g. adding or removing servers that serve requests
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A system and method for distributing requests for objects to hosts that store replicas of the objects, and for managing the placement of the replicas among hosts. Metrics for the historical demand of a replica at a host and the distance of the host from the requester of the object are evaluated and used to make decisions as to where to forward the request substantially independently from any input provided by a host to which a request is forwarded. This simplifies autonomous replica placement decisions made by hosts. A host substantially autonomously uses request metric and load information to select a replica to be deleted, migrated or replicated, and to delete, migrate or replicate a selected replica.

Claims

1. A method for dynamically distributing requests for an object, comprising the steps of:

a. receiving a request for an object at a request distributor;

b. determining the value of a request metric for each replica of the request object, where the request metric is a historical measure of the requests for the object that have been forwarded to the host that stores the replica of the requested object, wherein the request metric is determined substantially independently from any input from any host that stores a replica of any object to which a request for an object is forwarded; and

where the value of the request metric is the count of the replica at the host divided by an affinity value, the count being the number of times the replicas have been requested at the host, and the affinity value being a real number assigned to the host;

c. determining the value of a distance metric for each host at which the requested replica is stored, wherein the distance metric measures the cost of communicating between the requester and the host; and

d. selecting a host to respond to the request for the object based upon the values of the request metric of the host and the value of the distance metric of the host.

2. The method of claim 1, wherein the request metric is based upon the time elapsed since the last request.

3. The method of claim 1, wherein the distance metric for a host increases as the latency between the requester and the host increases.

4. The method of claim 1, wherein the distance metric for a host decreases as the bandwidth between the requester and the host increases.

5. The method of claim 1, wherein the distance metric for a host increases as the cost of communicating between the requester and the host increases.

6. The method of claim 1, wherein the distance metric for a host increases as the geographical distance between the requester and the host increases.

7. A method for dynamically distributing requests for an object, comprising the steps of:

a. receiving a request for an object at a request distributor;

b. determining the value of a request metric for each replica of the request object, where the request metric is a historical measure of the requests for the object that have been forwarded to the host that stores the replica of the requested object, and wherein the request metric is determined substantially independently from any input from any host that stores a replica of any object to which a request for an object is forwarded;

c. determining the value of a distance metric for each host at which the requested replica is stored, wherein the distance metric measures the cost of communicating between the requester and the host; and

d. selecting a host to respond to the request for the object based upon the values of the request metric of the host and the value of the distance metric of the host;

wherein step d comprises the steps of;

i. identifying the host p that stores a replica of the requested object and that has the best distance metric m in relation to the requester;

ii. determining the value x of the request metric x for host p;

iii. identifying the host f that stores a replica of the requested object and that indicates the least usage;

iv. if the value x corresponds to less usage than the value ky, then sending the request to host p, where k is a real number; and

v. if the value x corresponds to usage higher than or equal to the usage indicated by the value ky, then sending the request to host f.

8. A method for dynamically distributing requests for an object, comprising the steps of:

a. receiving a request for an object at a request distributor;

b. determining the value of a request metric for each replica of the request object, where the request metric is a historical measure of the requests for the object that have been forwarded to the host that stores the replica of the requested object, and wherein the request metric is determined substantially independently from any input from any host that stores a replica of any object to which a request for an object is forwarded;

c. determining the value of a distance metric for each host at which the requested replica is stored, wherein the distance metric measures the cost of communicating between the requester and the host; and

d. selecting a host to respond to the request for the object based upon the values of the request metric of the host and the value of the distance metric of the host;

wherein step d comprises the steps of;

i. ranking each host that stores a replica of the requested object in decreasing of distance metric in relation to the requester, where if replicas are stored on n hosts, the closest host is assigned a rank of n and the most distant host is assigned a rank of 1;

ii. calculating a decision metric for each host proportionately related to the value of the requested metric of the host and inversely related to the rank of the host;

iii. sending the request to the host with the smallest decision metric.

9. A request distributor, comprising:

a processor;

a memory that stores request distribution instructions adapted to be executed by said processor to receive a request for an object, determine the value of a request metric for the requested object, where the request metric is a historical measure of the requests for the object that have been forwarded to the host that stores the replica of the requested object, wherein the request metric is determined substantially independently from any input from any host that stores a replica of any object to which a request for an object is forwarded, where the value of the request metric is the count of the replica at the host divided by an affinity value, the count being the number of times the replicas have been requested at the host, and the affinity value being a real number assigned to the host, and determine the value of a distance metric for a host at which a replica of the requested object is stored, and select a host to respond to the request based upon the values of the request metric and the distance metric, said memory coupled to said processor; and

a port adapted to be coupled to a network, said port coupled to said processor and said memory.

10. The request distributor of claim 9, wherein said request distribution instructions are further adapted to forward a request for an object to a host.

11. An article of manufacture comprising a computer-readable medium having stored thereon request distribution instructions adapted to be executed by a circuit, the instructions which, when executed, cause the circuit to perform the steps of:

a. receiving a request for an object at a request distributor;

b. determining the value of a request metric for each replica of the request object, where the requested metric is a measure of the demand for the replica of the requested object, wherein the request metric is determined substantially independently from any input from any host that stores a replica of any object to which a request for an object is forwarded; and

where the value of the request metric is the count of the replica at the host divided by an affinity value, the count being the number of times the replicas have been requested at the host, and the affinity value being a real number assigned to the host;

c. identifying a distance metric for each host at which the requested replica is stored, wherein the distance metric measures the cost of communicating between the requester and the host; and

d. selecting a host to respond to the request for the object based upon the request metric of the host and the distance metric of the host.

12. An article of manufacture comprising a computer-readable medium having stored thereon request distribution instructions adapted to be executed by a circuit, the instructions which, when executed, cause the circuit to perform the steps of:

a. receiving a request for an object at a request distributor;

b. determining the value of a request metric for each replica of the requested object, where the requested metric is a measure of the demand for the replica of the requested object, wherein the requested metric is determined substantially independently from any input from any host that stores a replica of any object,

c. identifying a distance metric for each host at which the requested replica is stored, wherein the distance metric measures the cost of communicating between the requester and the host; and

d. selecting a host to respond to the request for the object based upon the request metric of the host and the distance metric of the host; and

wherein said request distribution instructions are adapted to be executed by a processor to perform the steps of;

i. identifying the host p that stores a replica of the requested object and that has the best distance metric m in relation to the requester;

ii. determining the value x of the request metric x for host p;

iii. identifying the host f that stores a replica of the requested object and that indicates the least usage;

iv. if the value x corresponds to less usage than the value ky, then sending the request to host p, where k is a real number; and

iv. if the value x corresponds to usage higher than or equal to the usage indicated by the value ky, then sending the request to host f.

13. An article of manufacture comprising a computer-readable medium having stored thereon request distribution instructions adapted to be executed by a circuit, the instructions which when executed, cause the circuit to perform the steps of:

a. receiving a request for an object at a request distributor;

b. determining the value of a request metric for each replica of the requested object, where the requested metric is a measure of the demand for the replica of the requested object, wherein the requested metric is determined substantially independently from any input from any host that stores a replica of any object,

c. identifying a distance metric for each host at which the requested replica is stored, wherein the distance metric measures the cost of communicating between the requester and the host; and

d. selecting a host to respond to the request for the object based upon the request metric of the host and the distance metric of the host; and

wherein said request distribution instructions are adapted to be executed by a processor to perform the steps of;

i. ranking each host that stores a replica of the requested object in decreasing of distance metric in relation to the requester, where if replicas are stored on n hosts, the closest host is assigned a rank of n and the most distant host is assigned a rank of 1;

ii. calculating a decision metric for each host proportionately related to the value of the requested metric of the host and inversely related to the rank of the host;

iii. sending the request to the host with the smallest decision metric.

14. A system for distributing requests for objects, comprising:

a. means for receiving a request for an object;

b. means for selecting a host to which to forward the request for the object substantially independently from any input received from any host that stores any object to which a request is forwarded, said means including means for determining a value of a request metric for the requested object, where the value of the request metric is the count of the replica at the host divided by an affinity value, the count being the number of times the replicas have been requested at the host, and the affinity value being a real number assigned to the host, said means selecting a host to respond the request based upon the value of the requested metric; and

c. means for forwarding a request for an object to a selected host.