Systems, methods, and devices for gradual invalidation of resources

• US 10,608,894 B2
• Filed: 03/13/2013
• Issued: 03/31/2020
• Est. Priority Date: 12/13/2012
• Status: Active Grant

• Current Assignee: Sandpiper CDN, LLC (Theseus LF Asset Holdings, LLC)
• Original Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Inventors: Newton, Christopher, Varney, Lewis Robert, Lipstone, Laurence R., Crowder, William, Swart, Andrew
• Primary Examiner(s): Louie, Oscar A
• Assistant Examiner(s): Gidado, Oluwatosin M
• Application Number:
  US13/802,093
• Publication Number:
  US 20140173097A1
• Time in Patent Office: 2,575 Days
• Field of Search: 709224
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence
• CPC Class Codes: G06F 15/173 using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
• CPC Class Codes: G06F 15/177 Initialisation or configuration control processor initialisation G06F9/4405
• CPC Class Codes: G06F 9/5055 considering software capabilities, i.e. software resources associated or available to the machine
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H04L 41/0813 characterised by the conditions triggering a change of settings
• CPC Class Codes: H04L 41/0816 the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 41/0823 characterised by the purposes of a change of settings, e.g. optimising configuration for enhancing reliability for optimising operational conditions of wireless networks H04W24/02
• CPC Class Codes: H04L 41/0869 Validating the configuration within one network element
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/50 Network service management, e.g. ensuring proper service fulfilment according to agreements
• CPC Class Codes: H04L 41/5041 characterised by the time relationship between creation and deployment of a service
• CPC Class Codes: H04L 41/509 wherein the managed service relates to media content delivery, e.g. audio, video or TV
• CPC Class Codes: H04L 43/04 Processing captured monitoring data, e.g. for logfile generation
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/83 based on usage prediction
• CPC Class Codes: H04L 61/10 of different types
• CPC Class Codes: H04L 61/2503 : Translation of Internet protocol [IP] addresses
• CPC Class Codes: H04L 61/4511 : using domain name system [DNS]
• CPC Class Codes: H04L 61/4535 : using an address exchange platform which sets up a session between two nodes, e.g. rendezvous servers, session initiation protocols [SIP] registrars or H.323 gatekeepers
• CPC Class Codes: H04L 61/58 : Caching of addresses or names
• CPC Class Codes: H04L 65/403 : Arrangements for multi-party communication, e.g. for conferences data switching systems for conference H04L12/18; arrangements for connecting several subscribers to a common circuit, i.e. affording conference facilities H04M3/56; television conferencing systems H04N7/15
• CPC Class Codes: H04L 65/60 : Network streaming of media packets
• CPC Class Codes: H04L 67/01 : Protocols
• CPC Class Codes: H04L 67/06 : specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/1078 : Resource delivery mechanisms
• CPC Class Codes: H04L 67/2885 : Hierarchically arranged intermediate devices, e.g. for hierarchical caching
• CPC Class Codes: H04L 67/289 : Intermediate processing functionally located close to the data consumer application, e.g. in same machine, in same home or in same sub-network
• CPC Class Codes: H04L 67/51 : Discovery or management thereof, e.g. service location protocol [SLP] or web services
• CPC Class Codes: H04L 67/55 : Push-based network services
• 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
• CPC Class Codes: H04L 67/60 : Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70
• CPC Class Codes: H04L 69/03 : Protocol definition or specification protocol conformance testing H04L1/244

Abstract

A computer-implemented method includes receiving, at a service, invalidation information relating to at least one resource. Based on the invalidation information, a staleness trigger of the at least one resource is set as a function of an invalidation period. The at least one resource is considered to be not useable based on the function of the invalidation period and the staleness trigger.

Claims

1. A computer-implemented method comprising:

(A) receiving, at a service, invalidation information relating to at least one resource;

(B) based on said invalidation information, setting a staleness trigger of said at least one resource as a function of an invalidation period, wherein the invalidation period defines a time interval within which invalidation of said at least one resource is to take place, and wherein the function of the invalidation period is based on a length of the invalidation period and an amount of time elapsed since the invalidation information was received, and wherein the function of the invalidation period is based on a random number relative to the amount of time elapsed since the invalidation information was received; and

(C) said service treating said at least one resource as not useable based on said staleness trigger, wherein said treating said at least one resource as not useable comprises;

marking said at least one resource as stale and/or deleting said at least one resource from a cache at said service.

2. The method of claim 1 wherein the staleness trigger of the at least one resource is based on how much time has elapsed since the invalidation information was received.

3. The method of claim 1 wherein the invalidation period is based on a threshold value and begins after said invalidation information is received by said service.

4. The method of claim 1 wherein the invalidation information is received at said service as part of an invalidation manifest.

5. The method of claim 1 wherein the invalidation information received in (A) comprises one or more invalidation commands.

6. The method of claim 5 wherein an invalidation command is selected from:

(i) an invalidation command that specifies a single resource; and

(ii) an invalidation command that specifies a group of resources.

7. The method of claim 6 wherein, when an invalidation command specifies a group of resources, the group is specified by a pattern.

8. The method of claim 7 wherein the pattern is selected from:

regular expressions and glob patterns.

9. The method of claim 1 wherein said treating said at least one resource as not useable in (C) is also based said invalidation period.

10. The method of claim 1 wherein said at least one resource is invalidated by the end of the invalidation period.

11. The method of claim 1, wherein the service is a content delivery service in a content delivery network (CDN).

12. A computer-implemented method comprising:

(A) receiving, at a service, invalidation information relating to at least two resources, wherein said at least two resources comprise a first resource and a second resource;

(B) based on said invalidation information, setting a staleness trigger of said at least two resources as a function of an invalidation period, wherein the invalidation period defines a time interval within which invalidation of said at least two resources is to take place, and wherein the function of the invalidation period is based on a length of the invalidation period and on an amount of time elapsed since the invalidation information was received at said service, and wherein the function of the invalidation period is based on a random number relative to the amount of time elapsed since the invalidation information was received; and

(C) said service treating said first resource as not useable based on said staleness trigger, wherein said treating said first resource as not useable comprises;

marking said first resource as stale and/or deleting said first resource from a cache at said service, and wherein said first resource is invalidated at a first time within said invalidation period; and

(D) said service treating said second resource as not useable based on said invalidation period, wherein said treating said second resource as not useable comprises;

marking said second resource as stale and/or deleting said second resource from a cache at said service, and wherein said second resource is invalidated at a second time within said invalidation period,

wherein said first time is distinct from said second time.

13. The method of claim 12 wherein said treating said first resource as not useable in (C) is also based on said invalidation period.

14. The method of claim 12, wherein the service is a content delivery service in a content delivery network (CDN).

15. A computer-implemented method comprising:

obtaining, at a cache, invalidation information relating to a resource;

determining a first time value;

determining a staleness trigger of said resource based on said first time value and a time interval, wherein the time interval defines a period within which invalidation of said resource is to take place; and

said cache treating said resource as not useable based on said staleness trigger, wherein said treating said resource as not useable comprises;

marking said resource as stale and/or deleting said resource from said cache, and

wherein the first time value is based on a time since the invalidation information was obtained by the cache, and wherein staleness of the resource is determined as a random value, based on said first time value and said time interval.

16. The method of claim 15, wherein the time interval is an invalidation period.

17. The method of claim 15 wherein said treating said resource as not useable is also based on said time interval.

18. The method of claim 15, wherein the cache is in a content delivery network (CDN).

19. A computer-implemented method comprising:

(A) receiving, at a first service, invalidation information relating to a resource;

(B) receiving, at a second service, invalidation information relating to said resource;

(C) said first service, treating said resource as not usable based on an invalidation period, wherein said treating said resource as not useable by said first service comprises;

said first service marking said resource as stale and/or deleting said resource from a cache at said first service, and wherein said resource is invalidated at a first time in said invalidation period, wherein the first time is based on a first random number relative to a first amount of time elapsed since the invalidation information was received at said first service; and

(D) said second service, treating said resource as not usable based on said invalidation period, wherein said treating said resource as not useable by said second service comprises;

said second service marking said resource as stale and/or deleting said resource from a cache at said second service, and wherein said resource is invalidated at a second time in said invalidation period, wherein the second time is based on a second random number relative to a seconds amount of time elapsed since the invalidation information was received at said second service,

wherein the invalidation period defines a time interval within which invalidation of said resource is to take place, and

wherein said first time is distinct from said second time.

20. The method of claim 19, wherein the first service is first a content delivery service in a content delivery network (CDN), and the second service is second a content delivery service in the CDN.

21. An article of manufacture comprising non-transitory computer-readable media having computer-readable instructions stored thereon, the computer-readable instructions including instructions for implementing a computer-implemented method, said method operable on a device comprising hardware including memory and at least one processor and running a service on said hardware, said method comprising:

(A) receiving, at a service on said device, invalidation information relating to at least one resource;

(B) based on said invalidation information, setting a staleness trigger of said at least one resource as a function of an invalidation period, wherein the invalidation period defines a time interval within which invalidation of said at least one resource is to take place, and wherein the function of the invalidation period is based on a length of the invalidation period and an amount of time elapsed since the invalidation information was received, and wherein the function of the invalidation period is based on a random number relative to the amount of time elapsed since the invalidation information was received; and

(C) said service treating said at least one resource as not useable based on said staleness trigger, wherein said treating said at least one resource as not useable comprises;

marking said at least one resource as stale and/or deleting said at least one resource from a cache at said service.

22. The article of manufacture of claim 21, wherein said treating said at least one resource as not useable in (C) is also based on said invalidation period.

23. The article of manufacture of claim 21, wherein the service is a content delivery service in a content delivery network (CDN).

24. A device, comprising:

(a) hardware including memory and at least one processor, and

(b) a service running on said hardware, wherein said service is configured to;

(A) receive, at said service, invalidation information relating to at least one resource;

(B) based on said invalidation information, set a staleness trigger of said at least one resource as a function of an invalidation period, wherein the invalidation period defines a time interval within which invalidation of said at least one resource is to take place, and wherein the function of the invalidation period is based on a length of the invalidation period and an amount of time elapsed since the invalidation information was received, and wherein the function of the invalidation period is based on a random number relative to the amount of time elapsed since the invalidation information was received; and

(C) treat said at least one resource as not useable based on said staleness trigger by;

marking said at least one resource as stale and/or deleting said at least one resource from a cache at said service.

25. A system comprising at least two devices according to claim 24.

26. The device of claim 24 wherein said service is configured to treat said at least one resource as not useable based on said invalidation period and said staleness trigger.

27. The device of claim 24, wherein the service is a content delivery service in a content delivery network (CDN).