Managed object replication and delivery

• US 9,167,036 B2
• Filed: 02/14/2002
• Issued: 10/20/2015
• Est. Priority Date: 02/14/2002
• Status: Active Grant

• Current Assignee: Digital Impact Incorporated (Liberty Latin America Ltd.), Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Inventors: Seed, Steven L., Hobbs, Kevin, Glynn, Shane M., Foraker, Isaac W., Jones, Peter J., Chen, Homer H., Greer, William Patrick
• Primary Examiner(s): BILGRAMI, ASGHAR H
• Application Number:
  US10/073,938
• Publication Number:
  US 20060015574A1
• Time in Patent Office: 4,996 Days
• Field of Search: 709/203, 709/246, 711/122
• US Class Current: 1/1
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• 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 67/2885 Hierarchically arranged intermediate devices, e.g. for hierarchical caching
• CPC Class Codes: H04L 67/563 Data redirection of data network streams
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data

Abstract

A method, system and computer program product for managed object replication and delivery redirects, directly or indirectly, a client'"'"'s request for an object that is not available at a best or optimal handling edge server of a network to a parent server that has the requested object. So, where the requested object is not available at the handling edge server, the client'"'"'s request is redirected directly to the parent server that can provide the requested object to the client or indirectly via one or more parent servers to a parent server that can provide the requested object to the client. The method, system and computer program product further intelligently replicates the object to the edge server if the object is popular enough. Likewise, an object is removed from an edge server when it is no longer popular. All redirection and replication operations are preferably transparent to the end-user and do not degrade the quality of service.

Claims

1. A method for managed object replication and delivery of objects maintained on at least one origin server site in a system comprising a network having one or more edge server sites and one or more parent server sites distinct from said edge server sites, the one or more edge server sites and the one or more parent server sites being distinct from the at least one origin server site, the method comprising:

(A) directing a first request by a first client for a first object to a first edge server site in the network, regardless of whether said first edge server site has the first object, said first edge server site having been selected for said first request based on network traffic conditions and on server load; and

(B) if the first edge server site does not have the first object, then

(b1) said first edge server site redirecting the first request to a first server site distinct from the first edge server site; and

(b2) when the first edge server site does not have the first object, conditionally replicating a of the first object on the first edge server site for use in serving future client requests, said replicating being based at least in part on a dynamic measure of popularity of the first object, wherein the portion of the first object is replicated on the first edge server site when the dynamic measure of popularity of the first object exceeds a first dynamic replication threshold, said first dynamic replication threshold being associated with said first object, said first dynamic replication threshold being based at least in part on at least one dynamic measure of capacity, and wherein the first object is served to the first client from a server site other than the first edge server site;

(C) directing a second request b a second client for a second object to a second edge server site in the network, regardless of whether said second edge server site has the second object, said second edge server site having been selected for said second request based on network traffic conditions and on server load; and

(D) if the second edge server site does not have the second object, then

(d1) said second edge server site redirecting the second request to a second server site distinct from the second edge server site; and

(d2) when the second edge server site does not have the second object, conditionally replicating a portion of the second object on the seconded edge server site for use in serving future client requests for said second object from said second edge server site, said replicating being based at least in part on a dynamic measure of popularity of the second object, wherein the portion of the second object is replicated on the second edge server site when the dynamic measure of popularity of the second object exceeds a second dynamic replication threshold, said second dynamic replication threshold being associated with said second object said second dynamic replication threshold being distinct from said first dynamic replication threshold and wherein the second object is served to the second client from another server site other than the second edge server site.

2. The method of claim 1, wherein redirecting the first request to said first server site comprises said first edge server site redirecting the first request to a parent server site in the network.

3. The method of claim 2, wherein if that parent server site does not have the first object, then recursively redirecting the first request until a parent server site in the network having the first object is reached, and then serving the first object to the first client from the parent server site that has the first object.

4. The method of claim 1, wherein directing a request by the first client for an object to a first edge server site comprises directing the request by the first client for the object to a best or optimal edge server site.

5. The method of claim 4, wherein a best or optimal edge server site comprises an edge server site selected using at least one of a determination based on a best repeater selector, the likelihood of a copy of the first object being available at the edge server site, and the bandwidth between the edge server site and the first client.

6. The method of claim 1, wherein said step of conditionally replicating the portion of the first object to the first edge server site comprises replicating the portion of the first object to the first edge server site from a parent server site.

7. The method of claim 1, wherein said step of conditionally replicating comprises:

if the first object is determined to be popular based on said dynamic measure of popularity, and if the first object is unavailable on parent server sites in the network, then replicating the portion of the first object to a parent server site in the network from an origin server site.

8. The method of claim 1, wherein said step of conditionally replicating the portion of the first object to the first edge server site comprises, if the first object is unavailable on parent server sites in the network, replicating the portion of the first object to the first edge server site from an origin server site.

9. The method of claim 1, wherein said dynamic measure of popularity of the first object is determined using at least a request rate for the first object.

10. The method of claim 1, further comprising:

if an object on the first edge server site is no longer popular, as determined based on said dynamic measure of popularity of said object, deleting at least some part of the object from the first edge server site.

11. The method of claim 1, further comprising:

if an object on the parent server site is no longer popular, as determined based on said dynamic measure of popularity of said object, and if the object is available on an origin server site, then deleting at least some part of the object from the parent server site.

12. The method of claim 1, wherein said step of conditionally replicating the portion of the first object on said first edge server site comprises:

replicating the portion of the first object when said dynamic measure of popularity of the first object is greater than a the first dynamic replication threshold and there is enough storage on said first edge server site to replicate the portion of the first object;

otherwise, if there is not enough storage on said first edge server site to replicate the portion of the first object, then

i) comparing the dynamic measure of popularity of the first object against a dynamic measure of popularity of a least popular object in storage on said first edge server site,

ii) if the dynamic measure of popularity of the first object exceeds the dynamic measure of popularity of the least popular object in the storage, deleting at least some part of the least popular object from the storage, and then

iii) repeating i) and ii) until enough storage is available for the portion of the first object or until the dynamic measure of popularity of the first object is less than the dynamic measure of popularity of the least popular object in the storage, and then

iv) replicating the portion of the first object on said first edge server site if there is enough storage on said first edge server site.

13. The method of claim 1, wherein the step of serving the first object is performed separately from the step of conditionally replicating the portion of the first object.

14. The method of claim 1 wherein the server site from which the first object is served to the client is a peer server site of the first edge server site.

15. The method of claim 1 wherein the server site from which the first object is served to the client is the first server site.

16. The method of claim 1 wherein the server site from which the first object is served to the client is a peer of the first server site.

17. The method of claim 1 wherein the step of conditionally replicating the portion of the first object on the first edge server site replicates the portion of the first object from a peer server site of the first edge server site.

18. The method of claim 1 wherein the step of conditionally replicating the portion of the first object on the first edge server site replicates the portion of the first object from a server site.

19. The method of claim 1 wherein the dynamic measure of popularity of the first object is based at least in part on one or more of:

(a) a local dynamic measure of popularity of the object; and

(b) information regarding the popularity of the object on other servers.

20. The method of claim 1 wherein the first object comprises chunks, including initial chunks and remaining chunks, and wherein the portion of the first object comprises only initial chunks of the object.

21. A method as recited in claim 1, wherein the at least one dynamic measure of capacity represents available capacity on the first edge server.