US6484204B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for allocating requests for objects and managing replicas of objects on a network
Assignee: AT&T Inc
•
Filing: 2001-05-24
•
Granted: 2002-11-19
•
Expires: 2021-05-24
Abstract
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.
Inventors
- 👤 Michael Rabinovich
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 16:01
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/12; H04L47/00; H04L47/10; H04L47/12; H04L47/125; H04L47/29; H04L67/00; H04L67/01; H04L67/10; H04L67/1001; H04L67/1004; H04L67/1008; H04L67/101; H04L67/1031; H04L67/1095; H04L69/00; H04L69/30; H04L69/32; H04L69/322; H04L69/329; H04L9/00; H04L9/40; H04L67/1029
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
199 words
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.
Claim 2
Independent Claim
199 words
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.
Claim 3
Dependent Claim
75 words
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.
Claim 4
Dependent Claim
105 words
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.
Claim 5
Dependent Claim
165 words
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.
Claim 6
Dependent Claim
215 words
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.
Claim 7
Independent Claim
203 words
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.
Claim 8
Independent Claim
203 words
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.
Claim 9
Dependent Claim
158 words
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.
Claim 10
Dependent Claim
212 words
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.
References Cited (Backward Citations)
US5341477A
Cited
US5588147A
Cited
US5896506A
Cited
US5787247A
Cited
US6138162A
Cited
US5924116A
Cited
US6256675B1
Cited
US6167438A
Cited
US6128701A
Cited
US6167427A
Cited
US6317778B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-11-18 | 2006-05-20 | 2006-11-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-11-18 | 2010-05-20 | 2010-11-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-11-18 | 2014-05-20 | 2014-11-19 | $7700.00 | Window Closed / Lapsed |