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

• US 6,484,204 B1
• Filed: 05/24/2001
• Issued: 11/19/2002
• Est. Priority Date: 05/06/1997
• Status: Expired due to Fees

• 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): SALAD, ABDULLAHI ELMI
• Application Number:
  US09/863,518
• Time in Patent Office: 544 Days
• Field of Search: 709/241, 709/226, 709/217, 709/210, 709/238, 709/239, 709/214, 709/216, 709/105, 709/235, 709/224, 711/118, 711/122
• US Class Current: 709/226
• 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 placing replicas of an object in a network, comprising the steps of:

a. establishing a deletion threshold u and a replication threshold m for a first host such that vu is less than m, v being a real number;

b. for each host at which a replica is stored, determining a request metric for the replica;

c. if the request metric is less than u, and if the replica is not the sole replica, then deleting the replica from the first host;

.

d. if the request metric is above u, and if it is determined that there is a second host to which it is beneficial to migrate the replica, then migrating the replica to the second host; and

e. if the request metric is above m and no migration occurred in step d, then

i. determining if there is a second host to which it is beneficial to replicate the replica of the requested object stored at the first host; and

ii. if a second host is determined to be beneficial to which to replicate the replica stored at the first host, then replicating the replica stored at the first host at the second host.

2. The method of claim 1, further comprising the steps of:

f. estimating the expected value of the smallest load at the first server after performing steps a through e of claim 1;

g. determining if the value of the smallest load determined in step f is larger than a predetermined value hw;

h. if the value of the smallest load determined in step f is larger than hw, then offloading the first host.

3. The method of claim 2, wherein offloading the first host comprises the steps of:

i. identifying a second host whose load is below a predetermined value lw such that lw is smaller than hw;

j. for each replica of an object stored at the first host, if the request metric of the object is between u and m, then migrating the object to the second host identified in step i;

k. for each replica of an object stored at the first host, if the request metric of the object is above m, then replicating the object at the second host identified in step i.

4. The method of claim 1, wherein determining if there is a host to which it is beneficial to migrate the replica stored at the first host comprises the steps of:

a. determining if a second host has a better distance metric than the first host in relation to more than half of the requesters for the object and if the second host has a load that is less than lw, and estimating the highest possible load on second host after a migration, and determining if this estimation is less than hw;

b. if the second host has a better distance metric than the first host to more than half of the requesters for the object, and if the second host has a load that is less than lw, and if the estimated highest load of the second host after the migration is less than hw, then determining that it is beneficial to migrate the replica stored at the first host to the second host.

5. The method of claim 1, wherein determining if there is a host to which it is beneficial to replicate a requested object comprises the steps of:

a. determining if the load prior to replication at the second host is less than lw;

b. if the load prior to replication at the second host is less than hw, then;

i. determining if a second host has a better distance metric in relation to at least 1/(2k+1) of the requesters than the first host, where k is the same as the value of k in claim 1;

ii. determining if the second host has a better distance metric in relation to the requesters for at least m/2 requests for the object than the first host, where m is the replication threshold; and

iii. if the second host has a better distance metric in relation to at least 1/(2k+1) of the requesters than the first host, where k is the same as the value of k in claim 1, or if the second host has a better distance metric in relation to the requesters for at least m/2 requests for the object than the first host, then determining that it is beneficial to replicate the replica stored at the first host to the second host.

8. The medium of claim 6, wherein said replica management instructions are adapted to be executed by a processor to perform the steps of:

a. determining if the load prior to replication at the second host is less than lw;

b. if the load prior to replication at the second host is less than hw, then;

i. determining if a second host has a better distance metric in relation to at least 1/(2k+1) of the requesters than the first host, where k is the same as the value of k in claim 1;

ii. determining if the second host has a better distance metric in relation to the requesters for at least m/2 requests for the object than the first host, where m is the replication threshold; and

iii. if the second host has a better distance metric in relation to at least 1/(2k+1) of the requesters than the first host, where k is the same as the value of k in claim 1, or if the second host has a better distance metric in relation to the requesters for at least m/2 requests for the object than the first host, then determining that it is beneficial to replicate the replica stored at the first host to the second host.

6. A medium that stores replica management instructions adapted to be executed by a processor to perform the steps of:

a. establishing a deletion threshold u and a replication threshold m for a first host such that vu is less than m, v being a real number;

b. determining a request metric for the replica of the requested object stored at the first host;

c. if the request metric is less than u, and if the replica is not the sole replica, then deleting the replica from the first host;

d. if the request metric is above u, and if it is determined that there is a second host to which it is beneficial to migrate the replica, then migrating the replica to the second host; and

e. if the request metric is above m and no migration occurred in step d, then

i. determining if there is a second host to which it is beneficial to replicate the replica of the requested object stored at the first host; and

ii. if a second host is determined to be beneficial to which to replicate the replica stored at the first host, then replicating the replica stored at the first host at the second host.

7. The medium of claim 6, wherein said replica management instructions are adapted to be executed by a processor to perform the steps of:

a. determining if a second host has a better distance metric than the first host in relation to more than half of the requesters for the object and if the second host has a load that is less than lw, and estimating the highest possible load on second host after a migration, and determining if this estimation is less than hw;

b. if the second host has a better distance metric than the first host to more than half of the requesters for the object, and if the second host has a load that is less than lw, and if the estimated highest load of the second host after the migration is less than hw, then determining that it is beneficial to migrate the replica stored at the first host to the second host.