Resource invalidation in a content delivery network

• US 8,060,613 B2
• Filed: 10/31/2007
• Issued: 11/15/2011
• Est. Priority Date: 02/10/1998
• Status: Expired due to Fees

• Current Assignee: Sandpiper CDN, LLC (Theseus LF Asset Holdings, LLC)
• Original Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Inventors: Greer, Richard E., Farber, David A., Swart, Andrew D., Balter, James A.
• Primary Examiner(s): BLAIR, DOUGLAS B
• Application Number:
  US11/980,401
• Publication Number:
  US 20080215735A1
• Time in Patent Office: 1,476 Days
• Field of Search: 709/226
• US Class Current: 709/226
• CPC Class Codes: G06F 16/957 Browsing optimisation, e.g. caching or content distillation
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/10015 Access to distributed or replicated servers, e.g. using brokers
• CPC Class Codes: H04L 67/1006 with static server selection, e.g. the same server being selected for a specific client
• 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/1012 based on compliance of requirements or conditions with available server resources
• 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/1025 Dynamic adaptation of the criteria on which the server selection is based
• 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/2895 Intermediate processing functionally located close to the data provider application, e.g. reverse proxies
• CPC Class Codes: H04L 67/561 Adding application-functional data or data for application control, e.g. adding metadata
• CPC Class Codes: H04L 67/563 Data redirection of data network streams
• CPC Class Codes: H04L 67/564 Enhancement of application control based on intercepted application data
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A repeater server in a content delivery network (CDN) maintains a list of resources that are no longer valid. When the server gets a request for a resource, it checks whether that resource is on the list, and, if so, it replicates the resource from a content provider'"'"'s content source such as an origin server. Otherwise the repeater server tries to serve a copy of the requested resource or to obtain a copy from another location in the CDN.

Claims

1. A method, in a system in which a plurality of content providers provide multiple resources to multiple clients, wherein each content provider provides at least some resources via one or more content sources associated with that content provider, and wherein at least some of said resources are to be served to clients from a shared content delivery network (CDN) formed by a plurality of repeater servers, the method comprising,

at a particular repeater server in said CDN:

(A) receiving, from a master server, an indication that at least one resource is no longer valid, and, in response to said receiving, causing said at least one resource to be listed as invalidated;

(B) responsive to a request of the particular repeater server to serve a particular resource of a particular content provider to a particular client, determining whether said particular resource is listed as invalidated, and

(C1) if the particular resource is listed as invalidated, then attempting to replicate an updated copy of the particular resource on the particular repeater server from at least one content sources associated with the particular content provider, and then serving the updated copy of the particular resource to the particular client; and

(C2) if the particular resource is not listed as invalidated, then

(c21) if a copy of the particular resource is not available on the particular repeater server, attempting to replicate a copy of the particular resource on the particular repeater server from another location in the system, and then serving the copy of the particular resource to the particular client, said another location in the system being another server in the CDN or at least one content source associated with the particular content provider;

otherwise

(c22) if a copy of the particular resource is available on the particular repeater server, serving the copy of the particular resource to the particular client.

2. A method as recited in claim 1, wherein said indication that said at least one resource is no longer valid is determined from a resource invalidation message identifying said at least one resource that is no longer valid.

3. A method as recited in claim 2, wherein said message identifies said at least one resource that is no longer valid using an identifier of the at least one resource.

4. A method as recited in claim 2, wherein said message identifies said at least one resource that is no longer valid using one or more patterns.

5. A method as recited in claim 2, further comprising:

sending an acknowledgement message for said resource invalidation message.

6. A method as recited in claim 2, further comprising:

causing said resource invalidation message to propagate to other repeater servers in said CDN.

7. A method as recited in claim 1, wherein a resource is no longer valid if the resource is stale.

8. A method as recited in claim 1, wherein a resource is no longer valid if the resource has changed.

9. A method as recited in claim 1, further comprising:

deleting at least some of said resources that are no longer valid prior to any request for said at least some of said resources.

10. The method of claim 1, further comprising:

selecting the particular repeater server to serve the particular resource to the particular client using, at least in part, an analysis of network distance between the particular client and the plurality of repeater servers.

11. A method as recited in claim 10, wherein the selecting comprises:

a step for determining Group Reduction Tables and Link Cost Tables; and

a step for using the Group Reduction Tables and the Link Cost Tables to identify the particular repeater server.

12. A method as recited in claim 1, wherein the master server comprises a repeater.

13. A method, in a system in which a plurality of content providers provide multiple resources to multiple clients, wherein each content provider provides at least some resources via one or more content sources associated with that content provider, and wherein at least some of said resources are to be served to clients from a shared content delivery network (CDN) formed by a plurality of repeater servers, the method comprising:

(A) receiving, at a particular repeater server, a first message from a master server identifying at least one resource that is stale; and

(B) in response to said first message, said particular repeater server listing said at least one resource as pending invalidation;

(C) responsive to a request of said particular repeater server from a client to serve the at least one resource that has been listed as pending invalidation, the request being the first request for said at least one resource that is received by said particular repeater server after said first message has been received, attempting to replicate an updated copy of the particular resource on the particular repeater server from at least one content source associated with the content provider, and said particular repeater server then attempting to serve the updated copy of the particular resource to the client.

14. A method as recited in claim 13, further comprising:

responsive to said step of receiving, said first particular repeater server propagating said first message to other servers in said CDN.

15. A method as recited in claim 13, wherein said first message identifies said at least one resource that is stale using an identifier of the at least one resource.

16. A method as recited in claim 13, wherein said first message identifies said at least one resource that is stale using one or more patterns.

17. The method of claim 16 wherein said one or more patterns comprise regular expressions.

18. The method of claim 17 wherein said regular expressions describe one or more sets of resources to be invalidated.

19. The method of claim 13 further comprising, after listing said at least one resource as pending invalidation:

said particular repeater server sending an acknowledgement message indicating that said particular repeater server has listed said at least one resource as pending invalidation.

20. The method of claim 13 further comprising:

causing said first message to be sent to others of said plurality of repeater servers in said CDN.

21. The method of claim 20 further comprising:

waiting for said others of said plurality of repeater servers to acknowledge the first message.

22. The method of claim 21 further comprising:

if a repeater server in said CDN fails to acknowledge the first message within a given period, disconnecting said repeater server.

23. The method of claim 22, further comprising:

when said repeater server reconnects, instructing said repeater server to flush its entire cache.

24. The method of claim 21, further comprising:

if a repeater server in said CDN fails to acknowledge the first message within a given period, then instructing said repeater server to flush at least some of its cache.

25. The method of claim 21 further comprising:

when all repeater servers have either acknowledged the first message or have timed out,

broadcasting a second message comprising an invalidation request to all repeaters servers to cause the repeater servers to remove the corresponding resource identifiers from the list of resource identifiers pending invalidation.

26. A method as recited in claim 13, wherein the master server comprises a repeater.

27. A method, in a system in which a plurality of content providers provide multiple resources to multiple clients, wherein each content provider provides at least some resources via one or more content sources associated with that content provider, and wherein at least some of said resources are to be served to clients from a shared content delivery network (CDN) formed by a plurality of repeater servers, the method comprising:

(A) receiving, from a master server, a first message identifying at least one resource of a content provider that is no longer valid; and

then

(B) responsive to the next request from a client of a repeater server to serve the at least one resource that has been identified as no longer valid, obtaining an updated copy of the particular resource on the repeater server from at least one content sources associated with the content provider.

28. A method as recited in claim 27, further comprising:

after said updated copy of said particular resource has been obtained, serving the updated copy of the particular resource to the client.

29. A method as recited in claim 27, wherein the master server comprises a repeater.