Content distribution network supporting popularity-based caching

• US 10,356,202 B2
• Filed: 09/17/2015
• Issued: 07/16/2019
• 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: Fliam, Richard, Flanagan, Kevin Christopher, Broome, Gregory Allen, Burgess, Jason, Commeau, Gabriel
• Primary Examiner(s): Hoang, Hieu T
• Application Number:
  US14/857,281
• Publication Number:
  US 20160248879A1
• Time in Patent Office: 1,398 Days
• 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 system comprising:

a computing device comprising;

one or more first processors; and

first memory, the first memory storing first instructions that, when executed by the one or more first processors, cause the computing device to;

determine popularity data for a content item stored in a first caching device in a first tier of a hierarchy of caching devices,

determine that the popularity data satisfies a threshold value, and

transmit an instruction to move the content item from the first caching device to a second caching device in a second tier of the hierarchy of caching devices after at least a portion of the content item has been transmitted from the first caching device to a user device, wherein the second tier is different from the first tier; and

a content router comprising;

one or more second processors; and

second memory, the second memory storing second instructions that, when executed by the one or more second processors, cause the content router to;

update a content index to indicate that the content item has been moved to the second caching device, and

transmit the content index to the user device before the content item has been fully transmitted to the user device.

2. The system of claim 1, wherein the second instructions, when executed by the one or more second processors, cause the content router to:

receive, from the user device, a Hypertext Transfer Protocol (HTTP) request for the content item; and

transmit, 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 system of claim 1, wherein the first instructions, when executed by the one or more first processors, cause the computing device to:

determine the popularity data by determining a popularity ranking value; and

determine that the popularity data satisfies the threshold value by determining that the popularity ranking value is beyond a popularity ranking threshold value.

4. The system of claim 3, wherein the first instructions, when executed by the one or more first processors, cause the computing device to:

calculate a first portion of the popularity data for a first time and a second portion of the popularity data for a second time; and

determine the popularity ranking value by summing the first portion and the second portion.

5. The system of claim 1, wherein the threshold value is a dynamic threshold value based on one or more 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, or a number of content items storable in the second caching device.

6. The system of claim 1, wherein the first instructions, when executed by the one or more first processors, cause the computing device to transmit, based on moving the content item from the first caching device to the second caching device, an instruction to delete the content item from the first caching device.

7. The system of claim 1, the first instructions, when executed by the one or more first processors, cause the computing device to:

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

8. The system of claim 1, wherein the first instructions, when executed by the one or more first processors, cause the computing device to:

compare respective proximities of a plurality of caching devices to the user device; and

select, based on the respective proximities to the user device, the first caching device or the second caching device.

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

10. A system comprising:

a computing device comprising;

one or more first processors; and

first memory, the first memory storing first instructions that, when executed by the one or more first processors, cause the computing device to;

receive, at a first time, information indicating that a first popularity value 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 a hierarchy of 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 the hierarchy of caching devices, wherein the second tier is different from the first tier,

receive, at a third time later than the first time, information indicating that a second popularity value for the content item is beyond a second threshold value, wherein at a second time, later than the first time and before the third time, the content item is stored in the second caching device in the second tier of the hierarchy of 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 the hierarchy of caching devices,

wherein the third tier is different from the second tier; and

a content router comprising;

one or more second processors; and

second memory, the second memory storing second instructions that, when executed by the one or more second processors, cause the content router;

receive, from a user device at 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 fourth time later than the third 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.

11. The system of claim 10, wherein the second instructions, when executed by the one or more second processors, cause the content router to:

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

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

12. The system of claim 10, wherein the first threshold value is a dynamic threshold value based on one or more 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, or a combination thereof.

13. The system of claim 10, wherein the first instructions, when executed by the one or more first processors, cause the computing device to:

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

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

14. The system of claim 10, wherein each of the caching devices stores a plurality of content items, and wherein the first instructions, when executed by the one or more first processors, cause the computing device to:

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

15. The system of claim 10, wherein the first instructions, when executed by the one or more first processors, cause the computing device to:

compare respective proximities of a plurality of caching devices to the user device; and

select, based on the respective proximities to the user device, the first caching device, the second caching device, and the third caching device.

16. The system 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.

17. The system of claim 10, wherein the first instructions, when executed by the one or more first processors, cause the computing device to:

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

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

18. The system of claim 10, wherein the instruction comprises a content index associated with the content item, and wherein the second instructions, when executed by the one or more second processors, cause the content router to:

update the content index to indicate that the content item has been moved to the second caching device; and

update the content index to indicate that the content item has been moved to the third caching device.

19. The system of claim 10, wherein the first instructions, when executed by the one or more first processors, cause the computing device to receive, at the second time, information indicating that a second popularity value for the content item is beyond a second threshold value by:

multiplying the first popularity value by a first number to obtain a first weighted value;

multiplying an additional popularity value by a second number, wherein the second number is greater than the first number to obtain a second weighted value; and

obtaining the second popularity value by adding the first weighted value to the second weighted value.