CONTENT DISTRIBUTION NETWORK SUPPORTING POPULARITY-BASED CACHING

• US 20130204961A1
• Filed: 08/21/2012
• Published: 08/08/2013
• Est. Priority Date: 02/02/2012
• Status: Active Grant

• Current Assignee: Comcast Cable Communications LLC (Comcast Corporation)
• Original Assignee: Comcast Cable Communications LLC (Comcast Corporation)
• Inventors: Broome, Gregory Allen, Fliam, Richard, Flanagan, Kevin Christopher, Burgess, Jason, Commeau, Gabriel
• Granted Patent: US 9,167,049 B2
• Time in Patent Office: Days
• US Class Current: 709/214
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/263 Network storage, e.g. SAN or NAS
• CPC Class Codes: G06F 2212/314 In storage network, e.g. network attached cache
• CPC Class Codes: G06F 2212/464 Multimedia object, e.g. image, video
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0649 Lifecycle management
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/2885 Hierarchically arranged intermediate devices, e.g. for hierarchical caching
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

A content delivery network may provide content items to requesting devices using a popularity-based distribution hierarchy. A central analysis system may determine popularity data for a content item stored in a first caching device. At a later time, the central analysis system may determine that a change in the popularity data is beyond a threshold value. The central analysis system may then transmit an instruction to move the content item from the first caching device to a second caching device in a different tier of caching devices than the first caching device. The central analysis system may update a content index to indicate that the content item has been moved to the second caching device. A user device may then be redirected to request the content item directly from the second caching device.

Claims

1. A method comprising:

determining, by a computing device, popularity data for a content item stored in a first caching device in a first tier of one or more first caching devices;

determining, by the computing device, that the popularity data is beyond a threshold value;

transmitting, by the computing device, an instruction to move the content item from the first caching device to a second caching device in a second tier of one or more second caching devices, wherein the second tier is different from the first tier; and

updating, by the computing device, a content index to indicate that the content item has been moved to the second caching device.

2. The method of claim 1, further comprising

receiving, from a user device, an HTTP request for the content item;

and

transmitting, to the user device, an HTTP redirect instruction to redirect the user device to request the content item from the second caching device.

3. The method of claim 1, wherein:

determining the popularity data comprises determining a popularity ranking value; and

determining that the popularity data is beyond a threshold value comprises determining that the popularity ranking value is beyond a popularity ranking threshold value.

4. The method of claim 1, wherein the threshold value is a dynamic threshold value based on one of a cache size of the first caching device, a number of content items storable in the first caching device, a cache size of the second caching device, a number of content items storable in the second caching device, and a combination thereof.

5. The method of claim 1, further comprising:

in response to moving the content item from the first caching device to the second caching device, transmitting an instruction to delete the content item from the first caching device.

6. The method of claim 1, wherein each caching device stores a plurality of content items, the method further comprising

receiving, at the computing device from each caching device, respective popularity data for each of the plurality of content items.

7. The method of claim 1, wherein a proximity of the second caching device to a user device is farther than a proximity of the first caching device to the user device.

8. The method of claim 1, wherein the content item is not replicated across the first tier and the second tier.

9. The method of claim 1, wherein:

the transmitting the instruction to move the content item from the first caching device to the second caching device comprises transmitting an instruction to move the content item from the first caching device to the second caching device after a portion of the content item has been transmitted from the first caching device to a user device.

10. A computing device comprising:

a processor; and

a memory storing instructions that, when executed by the processor, cause the computing device to;

receive, at a first time, information indicating that first popularity data for a content item is beyond a first threshold value, wherein at the first time the content item is stored in a first caching device in a first tier of one or more first caching devices;

transmit an instruction to move the content item from the first caching device to a second caching device in a second tier of one or more second caching devices, wherein the second tier is different from the first tier;

receive, at a second time later than the first time, information indicating that second popularity data for the content item is beyond a second threshold value, wherein at the second time the content item is stored in the second caching device in the second tier of one or more second caching devices; and

transmit an instruction to move the content item from the second caching device to a third caching device in a third tier of one or more third caching devices, wherein the third tier is different from the second tier.

11. The computing device of claim 10, wherein the memory further stores instructions that, when executed by the processor, cause the computing device to:

receive, from a user device at a time later than the first time and before the second time, a first request for a first portion of the content item;

transmit, to the user device, an instruction to redirect the user device to request the first portion of the content item from the second caching device;

receive, from the user device at a time later than the second time, a second request for a second portion of the content item; and

transmit, to the user device, an instruction to redirect the user device to request the content item from the third caching device.

12. The computing device of claim 10, wherein the memory further stores instructions that, when executed by the processor, cause the computing device to:

responsive to transmitting the instruction to move the content item from the first caching device to the second caching device, update a content index to indicate that the content item has been moved to the second caching device; and

responsive to transmitting the instruction to move the content item from the second caching device to the third caching device, update the content index to indicate that the content item has been moved to the third caching device.

13. The computing device of claim 10, wherein the first threshold value is a dynamic threshold value based on one of a cache size of the first caching device, a number of content items storable in the first caching device, a cache size of the second caching device, a number of content items storable in the second caching device, and a combination thereof.

14. The computing device of claim 10, wherein the memory further stores instructions that, when executed by the processor, cause the computing device to:

responsive to transmitting the instruction to move the content item from the first caching device to the second caching device, transmit an instruction to delete the content item from the first caching device; and

responsive to transmitting the instruction to move the content item from the second caching device to the third caching device, transmit an instruction to delete the content item from the second caching device.

15. The computing device of claim 10, wherein each caching device stores a plurality of content items, and wherein the memory further stores instructions that, when executed by the processor, cause the computing device to:

receive, from each caching device, respective popularity data for each of the plurality of content items.

16. The computing device of claim 10, wherein a proximity of the second caching device to a user device is farther than a proximity of the first caching device to the user device, and wherein a proximity of the third caching device to the user device is farther than the proximity of the second caching device to the user device.

17. The computing device of claim 10, wherein at the first time the content item is not replicated across the first tier and the second tier, and wherein at the second time the content item is not replicated across the second tier and the third tier.

18. The computing device of claim 10, wherein the memory stores further instructions that, when executed by the processor, cause the computing device to:

transmit the instruction to move the content item from the first caching device to the second caching device after a first portion of the content item has been transmitted from the first caching device to a user device; and

transmit the instruction to move the content item from the second caching device to the third caching device after a second portion of the content item has been transmitted from the second caching device to the user device.

19. A non-transitory computer readable storage medium storing computer readable instructions which, when read by a computer, instruct the computer to:

determine popularity data for a content item based on a first number of requests for the content item received during a first time duration and a second number of requests for the content item received during a second time duration, wherein the content item is stored in a first caching device in a first tier of one or more first caching devices;

determine that the content item is a popular content item when the popularity data is greater than or equal to a first threshold value;

determine that the content item is a modestly popular content item when the popularity data is less than the first threshold value and greater than or equal to a second threshold value;

determine that the content item is an unpopular content item when the popularity data is less than the second threshold value;

in response to determining that the content item is a popular content item, store the popular content item in a first caching device in a first tier of one or more caching devices;

in response to determining that the content item is a modestly popular content item, store the modestly popular content item in a second caching device in a second tier of one or more caching devices; and

in response to determining that the content item is an unpopular content item, store the unpopular content item in a third caching device in a third tier of one or more caching devices,

wherein the first tier is different from the second tier, wherein the first tier is different from the third tier, and wherein the second tier is different from the third tier.

20. The non-transitory computer readable storage medium of claim 19, wherein the popularity data is first popularity data determined at a first time, and wherein the computer readable storage medium stores further computer readable instructions which, when read by the computer, instruct the computer to:

determine, at a second time later than the first time, second popularity data for the content item;

determine that a difference between the first popularity data and the second popularity data is beyond a threshold value; and

transmit an instruction to move the content item to a different caching device in a different tier of one or more caching devices.