Dynamic topology transitions in a content delivery framework

• US 9,749,192 B2
• Filed: 12/03/2013
• Issued: 08/29/2017
• 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: Varney, Lewis Robert, Lipstone, Laurence R., Crowder, William, Swart, Andrew, Newton, Christopher
• Primary Examiner(s): Hussain, Tauqir
• Application Number:
  US14/095,079
• Publication Number:
  US 20140223016A1
• Time in Patent Office: 1,365 Days
• Field of Search: 709226
• 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 first group is defined from an arbitrary set of nodes comprising service instances. Each node in the first group assumes one or more responsibilities in processing a request across the first group. A second group is defined from an arbitrary set of nodes. Each node in the second group assumes one or more discrete responsibilities in processing a request across the second group. The second group has a topology distinct from that of the first group. Request processing is transitioned from the first group to the second group based on a responsibility adaptation policy.

Claims

1. A computer-implemented method, in a content delivery (CD) network comprising multiple CD service endpoints, said CD service endpoints running on a plurality of devices, the method operable on a device comprising hardware including memory and at least one processor, the method comprising:

(A) defining a first group from a first arbitrary set of nodes comprising CD service instances across the machines of one or more sub-clusters of said CD network (CDN), wherein each node in the first group assumes one or more discrete responsibilities involved in processing of a request across the first group, wherein, in response to a request made at a node of the first group, one or more nodes in said first group is selected to be responsible for processing of the request, said first group having a first topology; and

(B) in response to a change to a particular node in said CDN,

(B)(1) defining a second group from a second arbitrary set of nodes comprising CD service instances across the machines of said one or more sub-clusters of said CDN, wherein each node in the second group assumes one or more discrete responsibilities involved in processing of a request across the second group, wherein, in response to a request made at a node of the second group, one or more nodes in said second group is selected to be responsible for processing of the request, said second group having a second topology distinct from said first topology; and

(B)(2) transitioning request processing from the first group to the second group over a time period based on a responsibility adaptation policy, wherein said time period comprises a fade interval, and wherein nodes in both said first group and said second group share a particular responsibility for request processing during the time period, wherein said responsibility adaptation policy uses a fading function that fades to zero over said fade interval.

2. The method of claim 1 wherein said second group comprises nodes in said first group.

3. The method of claim 1

wherein said change to said particular node comprises a change in a capacity of said particular node, and

wherein said second group was defined in response to said change in said capacity of a particular node.

4. The method of claim 3 wherein the change in the capacity of the particular node comprises a decrease in the capacity of the particular node.

5. The method of claim 1

wherein said change to said particular node comprises a change in a responsibility of said particular node, and

wherein said second group was defined in response to said change in said responsibility of said particular node.

6. The method of claim 5 wherein the change in responsibility of the particular node resulted from a change in a capacity of the particular node.

7. The method of claim 5 wherein the change in responsibility of the particular node resulted from a change in a capacity of another node distinct from the particular node.

8. The method of claim 3 wherein said particular node is in the first group and said particular node is not in said second group.

9. The method of claim 7 wherein said other node is in said first group and wherein said particular node is not in said first group, and wherein said particular node is in said second group.

10. The method of claim 1 wherein defining said second group comprises one or more of:

(i) removing one or more nodes from the first group; and

(ii) adding one or more nodes to the first group.

11. The method of claim 10 wherein said defining comprises (i) removing one or more nodes from the first group, and wherein at least one of said one or more nodes removed from the first group is a node with a capacity that changed since the at least one node was included in the first group.

12. The method of claim 10 wherein said defining comprises (i) removing one or more nodes from the first group, and wherein at least one of said one or more nodes removed from the first group is a node with a responsibility that changed since the least one node was included in the group.

13. The method of claim 1 wherein said multiple CD service endpoints form one or more sub-clusters.

14. The method of claim 1 wherein the first group comprises a first peer group, and wherein the second group comprises second peer group.

15. The method of claim 14 wherein the first peer group is distinct from the second peer group.

16. The method of claim 1 wherein the multiple CD service endpoints comprise a plurality of delivery service endpoints each constructed and adapted to deliver resources.

19. The method of claim 1 wherein a probability of said fading function fades to zero over said fade interval.

20. The method of claim 1 wherein said defining said second group in (B)(1) comprises redefining the first group.

21. The method of claim 1 wherein the one or more discrete responsibilities are selected from a discrete set of responsibilities comprising:

non-responsible, cache-responsible, and fill-responsible.

17. A system, in a content delivery (CD) network comprising multiple CD service endpoints, said CD service endpoints running on a plurality of devices, the system comprising:

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

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

(A) define a first group from an arbitrary set of nodes comprising CD service instances across the machines of said one or more sub-clusters of said content delivery network (CDN), wherein each node in the first group assumes one or more discrete responsibilities involved in processing of a request across the first group, wherein, in response to a request made at a node of the first group, one or more nodes in said first group is selected to be responsible for processing of the request, said first group having a first topology; and

(B) in response to a change to a particular node in said CDN, define a second group from an arbitrary set of nodes comprising CD service instances across the machines of said one or more sub-clusters of said CDN, wherein each node in the second group assumes one or more discrete responsibilities involved in processing of a request across the second group, wherein, in response to a request made at a node of the second group, one or more nodes in said second group is selected to be responsible for processing of the request, said second group having a second topology distinct from said first topology; and

(C) transition request processing from the first group to the second group over a time period based on a responsibility adaptation policy, wherein said time period comprises a fade interval, and wherein nodes in both said first group and said second group share a particular responsibility for request processing during the time period, wherein said responsibility adaptation policy uses a fading function that fades to zero over said fade interval.

22. The system of claim 17 wherein a probability of said fading function fades to zero over said fade interval.

23. The system of claim 17 wherein defining said second group in (B) comprises redefining the first group.

24. The system of claim 17 wherein the one or more discrete responsibilities are selected from a discrete set of responsibilities comprising:

non-responsible, cache-responsible, and fill-responsible.

18. 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 on a device comprising hardware including memory and at least one processor and running a content delivery (CD) service on said hardware, said method, in a CD network comprising multiple CD service endpoints, said CD service endpoints running on a plurality of devices, and said method comprising:

(A) defining a first group from an arbitrary set of nodes comprising CD service instances across the machines of said one or more sub-clusters of said content delivery network (CDN), wherein each node in the first group assumes one or more discrete responsibilities involved in processing of a request across the first group, wherein, in response to a request made at a node of the first group, one or more nodes in said first group is selected to be responsible for processing of the request, said first group having a first topology;

(B) in response to a change to a particular node in said CDN, defining a second group from an arbitrary set of nodes comprising CD service instances across the machines of said one or more sub-clusters of said CDN, wherein each node in the second group assumes one or more discrete responsibilities involved in processing of a request across the second group, wherein, in response to a request made at a node of the second group, one or more nodes in said second group is selected to be responsible for processing of the request, said second group having a second topology distinct from said first topology; and

(C) transitioning request processing from the first group to the second group over a time period based on a responsibility adaptation policy, wherein said time period comprises a fade interval, and wherein nodes in both said first group and said second group share a particular responsibility for request processing during the time period, wherein said responsibility adaptation policy uses a fading function that fades to zero over said fade interval.

25. The article of manufacture of claim 18 wherein a probability of said fading function fades to zero over said fade interval.

26. The article of manufacture of claim 18 wherein defining said second group in (B) comprises redefining the first group.

27. The article of manufacture of claim 18 wherein the one or more discrete responsibilities are selected from a discrete set of responsibilities comprising:

non-responsible, cache-responsible, and fill-responsible.