Responsibility-based cache peering

• US 9,686,148 B2
• Filed: 03/13/2013
• Issued: 06/20/2017
• Est. Priority Date: 12/13/2012
• Status: Active Grant

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Inventors: Varney, Lewis Robert, Lipstone, Laurence R., Crowder, William, Swart, Andrew, Newton, Christopher
• Primary Examiner(s): Srivastava, Vivek
• Assistant Examiner(s): Khan, Atta
• Application Number:
  US13/802,366
• Publication Number:
  US 20140173132A1
• Time in Patent Office: 1,560 Days
• Field of Search: 709240
• 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, operable in a network comprising multiple delivery service endpoints running on a plurality of devices. Each delivery service endpoint delivers resources. A plurality of the multiple delivery service endpoints comprise a group, each node in the group having at least one kind of responsibility relating to delivery of resources. The method includes receiving, at the node, a request relating to a particular resource. The kind of responsibility the node has for the request is determined based on at least one kind responsibility assigned to the node for requests relating to the particular resource. Based on the determining, an attempt is made to process the request in accordance with kind responsibility assigned to the node for requests relating to the particular resource.

Claims

1. A computer-implemented method, in a content delivery (CD) network (CDN) comprising multiple delivery service endpoints running on a plurality of devices, each of said delivery service endpoints constructed and adapted to deliver resources on behalf of one or more content providers, a plurality of said multiple delivery service endpoints comprising a group, wherein each node in said group has at least one kind of responsibility relating to delivery of resources, the method comprising:

(A) receiving, at said node, a request relating to a particular resource;

(B) determining what kind of responsibility said node has for said request, said determining being based on at least one kind of responsibility assigned to said node for requests relating to said particular resource, wherein the kind of responsibility the node has for the particular resource is defined in a policy associated with the particular resource, wherein the policy is defined for a group of resources, wherein the group of resources comprises a property, wherein a property comprises one or more resources associated with a particular content provider of said one or more content providers and delivered by the CDN on behalf of the particular content provider; and

(C) based on said determining in (B), attempting to process said request in accordance with kind responsibility assigned to said node for requests relating to said particular resource,

wherein the policy is based on one or more of;

cacheability, and size of the resource; and

wherein the kind of responsibility that can be assigned to a node is taken from a discrete set of responsibilities comprising of;

non responsible, cache responsible, and fill responsible; and

wherein there is a responsibility set corresponding to each kind of responsibility in said discrete set of responsibilities, and wherein each node in the group is assigned to at least one responsibility set.

2. The method of claim 1 wherein said determining what kind of responsibility said node has for said request in (B) comprises:

(B)(1) determining said node'"'"'s membership in said responsibility sets.

3. The method of claim 2 wherein:

(i) said node is determined to be non-responsible for said request when said node is in the non-responsible set for said particular resource; and

(ii) said node is determined to be cache-responsible for said request when said node is in the cache-responsible set for said particular resource; and

(iii) said node is determined to be fill-responsible for said request when said node is in the fill-responsible set for said particular resource.

4. The method of claim 1 wherein each resource is assigned a resource type and wherein said attempting to process in (C) is also based on a resource type of said particular resource.

5. The method of claim 1 wherein each resource is assigned a resource type from a discrete set of resource policy types comprising the types:

rejectable, redirectable, and servable, and wherein said attempting to process in (C) is also based on a resource type of said particular resource.

6. The method of claim 5 wherein, when

(i) it is determined that said node is not responsible for said resource, and

(ii) said resource policy type indicates that said request is rejectable,

said attempting to process said request in (C) comprises:

(D)(0) said node rejecting said request.

7. The method of claim 5 wherein, when:

(i) it is determined that no node in said group has responsibility for said request, and

(ii) said resource policy type indicates that said request is redirectable,

said attempting to process said request in (C) comprises;

(D)(1) redirecting the request to a remote fill target outside the group.

8. The method of claim 5 wherein each resource of the type servable has a sub-type selected from the group consisting of:

cacheable and non-cacheable, and wherein, when;

(i) it is determined that no node in said group has responsibility for said request, and

(ii) said resource policy type indicates that said request is servable, and

(iii) said resource sub-type indicates that said resource is non-cacheable,

said attempting to process said request in (C) comprises;

(D)(2) proxying the request to a remote fill target outside the group.

9. The method of claim 5 wherein each resource of the type servable has a sub-type selected from the group consisting of:

cacheable and non-cacheable, and wherein, when

(i) said resource policy type indicates that said request is servable, and

(ii) said resource sub-type indicates that said resource is cacheable, and

(iii) it is determined that said node is not cache-responsible or fill-responsible for said request,

said attempting to process said request in (C) comprises;

(D)(3) proxying the request to a cache-responsible node of the group.

10. The method of claim 9 wherein said attempting in (C) comprises said proxying in (D)(3) when:

(iv) said particular resource is not in a cache of said node.

11. The method of claim 5 wherein each resource of the type servable has a sub-type selected from the group consisting of:

cacheable and non-cacheable, and wherein, when;

(i) said resource policy type indicates that said request is servable, and

(ii) said resource sub-type indicates that said resource is cacheable, and

(iii) it is determined that said node is not cache-responsible or fill-responsible for said request,

said attempting to process said request in (C) comprises;

(D)(4) transferring the request to a cache-responsible node of the group.

12. The method of claim 9 wherein said attempting in (C) comprises said proxying in (D)(3) when:

(iv) said particular resource is not in a cache of said node.

13. The method of claim 5 wherein each resource of the type servable has a sub-type selected from the group consisting of:

cacheable and non-cacheable, and wherein, when;

(i) said resource policy type indicates that said request is servable, and

(ii) said resource sub-type indicates that said resource is cacheable, and

(iii) it is determined that said node is cache-responsible and not fill-responsible for said request, and

(iv) said particular resource is not in a cache of said node,

said attempting to process said request in (C) comprises;

(D)(5) attempting to obtain the resource from a fill-responsible node of the group.

14. The method of claim 5 wherein each resource of the type servable has a sub-type selected from the group consisting of:

cacheable and non-cacheable, and wherein, when;

(i) said resource policy type indicates that said request is servable, and

(ii) said resource sub-type indicates that said resource is cacheable, and

(iii) it is determined that said node is fill-responsible for said request, and

(iii) said particular resource is not in a cache of said node,

said attempting to process said request in (C) comprises;

(D)(6) attempting to obtain the resource from a remote fill target outside the group.

15. The method of claim 1 wherein a number of cache-responsible nodes for a resource is set based on a measure of popularity of the resource.

16. The method of claim 1 wherein said attempting to process in (C) is based on at least one of:

(i) whether said node is considered to be non-responsible for said resource,

(ii) whether said node is considered to be cache-responsible for said resource, and

(iii) whether said node is considered to be fill-responsible for said resource.

17. The method of claim 16 wherein said attempting to process in (C) is also based on whether said resource is considered to be at least one of:

(i) rejectable, (ii) redirectable, and (iii) servable.

18. The method of claim 17 wherein said attempting to process in (C) comprises one of said node:

(D)(i) rejecting said request;

(D)(ii) redirecting the request to a remote fill target outside the group;

(D)(iii) proxying the request;

(D)(iv) transferring the request to a cache-responsible node of the group;

(D)(v) attempting to obtain the resource.

19. The method of claim 18 wherein, said attempting to process in (C) is also based on whether said resource is considered to be cacheable or non-cacheable.

20. The method of claim 19 wherein said proxying the request in (D)(iii) comprises one of:

(D)(iii)(1) proxying the request to a remote fill target outside the group;

or

(D)(iii)(2) proxying the request to a cache-responsible node of the group.

21. The method of claim 19 wherein said attempting to obtain the resource in (D)(v) comprises one of:

(D)(v)(i) attempting to obtain the resource from a fill-responsible node of the group;

or

(D)(v)(ii) attempting to obtain the resource from a remote fill target outside the group.

22. The method of claim 1 wherein the group comprises a peer group of said multiple delivery service endpoints.

23. The method of claim 22 wherein said peer group comprises a super-cluster of said plurality of nodes of said multiple delivery service endpoints.

24. A device, in a content delivery (CD) network (CDN) comprising multiple delivery service endpoints running on a plurality of devices, each of said delivery service endpoints constructed and adapted to deliver resources on behalf of one or more content providers, a plurality of said multiple delivery service endpoints comprising a group, wherein each node in said group has at least one kind of responsibility relating to delivery of resources,

the 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 a node, a request relating to a particular resource;

(B) determine what kind of responsibility said node has for said request, said determining being based on at least one kind responsibility assigned to said node for requests relating to said particular resource, wherein the kind of responsibility the node has for the particular resource is defined in a policy associated with the particular resource, wherein the policy is defined for a group of resources, wherein the group of resources comprises a property, wherein a property comprises one or more resources associated with a particular content provider of said one or more content providers and delivered by the CDN on behalf of the particular content provider; and

(C) based on said determining in (B), attempt to process said request in accordance with kind responsibility assigned to said node for requests relating to said particular resource,

wherein the policy is based on one or more of;

cacheability, and size of the resource; and

wherein the kind of responsibility that can be assigned to a node is taken from a discrete set of responsibilities comprising of;

non responsible, cache responsible, and fill responsible; and

wherein there is a responsibility set corresponding to each kind of responsibility in said discrete set of responsibilities, and wherein each node in the group is assigned to at least one responsibility set.

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

26. A computer program product having computer readable instructions stored on non-transitory computer readable media, 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 in a content delivery (CD) network (CDN) comprising multiple delivery service endpoints running on a plurality of devices, each of said delivery service endpoints constructed and adapted to deliver resources on behalf of one or more content providers, a plurality of said multiple delivery service endpoints comprising a group, wherein each node in said group has at least one kind of responsibility relating to delivery of resources,

said method comprising:

(A) receiving, at said node, a request relating to a particular resource;

(B) determining what kind of responsibility said node has for said request, said determining being based on at least one kind responsibility assigned to said node for requests relating to said particular resource, wherein the kind of responsibility the node has for the particular resource is defined in a policy associated with the particular resource, wherein the policy is defined for a group of resources, wherein the group of resources comprises a property, wherein a property comprises one or more resources associated with a particular content provider of said one or more content providers and delivered by the CDN on behalf of the particular content provider; and

(C) based on said determining in (B), attempting to process said request in accordance with kind responsibility assigned to said node for requests relating to said particular resource,

wherein the policy is based on one or more of;

cacheability, and size of the resource; and

wherein the kind of responsibility that can be assigned to a node is taken from a discrete set of responsibilities comprising of;

non responsible, cache responsible, and fill responsible; and

wherein there is a responsibility set corresponding to each kind of responsibility in said discrete set of responsibilities, and wherein each node in the group is assigned to at least one responsibility set.