Cache management in a video content distribution network

Patent metadata

Field	Value
Publication number	US-12407879-B2
Application number	US-202117317526-A
Country	US
Kind code	B2
Filing date	May 11, 2021
Priority date	Dec 20, 2010
Publication date	Sep 2, 2025
Grant date	Sep 2, 2025

Abstract

Cache management techniques are described for a content distribution network (CDN), for example, a video on demand (VOD) system supporting user requests and delivery of video content. A preferred cache size may be calculated for one or more cache devices in the CDN, for example, based on a maximum cache memory size, a bandwidth availability associated with the CDN, and a title dispersion calculation determined by the user requests within the CDN. After establishing the cache with a set of assets (e.g., video content), an asset replacement algorithm may be executed at one or more cache devices in the CDN. When a determination is made that a new asset should be added to a full cache, a multi-factor comparative analysis may be performed on the assets currently residing in the cache, comparing the popularity and size of assets and combinations of assets, along with other factors to determine which assets should be replaced in the cache device.

First claim

The invention claimed is:

1. A method comprising:
causing, by a computing device, storage of a plurality of content items in a first storage location by:
determining, based on request history information, a first target percentage of content item requests to be serviced by the first storage location;
ranking a plurality of unique titles, in the request history information, to generate a list of top ranked unique titles, wherein each unique title corresponds to a percentage of a total number of historical content item requests;
iteratively selecting, after determining the first target percentage, by starting from a top of the list of top ranked unique titles, a quantity of unique titles until a sum of the percentages for each of the iteratively selected unique titles satisfies the first target percentage; and
causing storage, based on the selecting and in the first storage location, of the iteratively selected unique titles.

2. The method of claim 1 , wherein causing the storage of the iteratively selected unique titles is further based on a plurality of distribution curves at a plurality of different time intervals associated with the first storage location.

3. The method of claim 1 , wherein causing the storage of the iteratively selected unique titles is further based on:
an available bandwidth between the first storage location and a second storage location, and
a cache size of the first storage location.

4. The method of claim 1 , wherein causing the storage of the iteratively selected unique titles is further based on a quantity of target unique titles satisfying the first target percentage of content item requests, and wherein the first target percentage is based on a time of day.

5. The method of claim 1 , wherein causing the storage of the iteratively selected unique titles is further based on a quantity of target unique titles satisfying the first target percentage of content item requests, and wherein the quantity of target unique titles is based on a time of day.

6. The method of claim 1 , wherein causing the storage of the iteratively selected unique titles is further based on giving different weights to requests from different users in the request history information.

7. The method of claim 1 , further comprising:
causing the storage of the iteratively selected unique titles further based on:
rankings of unique titles in the request history information; and
frequencies of access.

8. The method of claim 1 , wherein for each iterative selection of unique titles, a running sum of percentages is updated and compared against the first target percentage.

9. The method of claim 1 , further comprising:
receiving title dispersion criteria for the first storage location, wherein the title dispersion criteria comprise:
a minimal quantity of target unique titles that are to account for a percentage of requests;

selecting, based on the title dispersion criteria and to be stored in the first storage location, the minimal quantity of target unique titles from the request history information; and
sending an instruction to cause the minimal quantity of target unique titles to be stored in the first storage location.

10. The method of claim 1 , wherein causing the storage of the iteratively selected unique titles comprises causing storage of a subset of the iteratively selected unique titles in the first storage location.

11. The method of claim 1 , wherein the iteratively selecting further comprises:
sequentially moving down from the top of the list of top ranked unique titles;
maintaining a running total of percentages of previously selected unique titles until the sum of the percentages for each of the iteratively selected unique titles satisfies the first target percentage; and
delivering the iteratively selected unique titles to a plurality of client devices.

12. The method of claim 1 , wherein causing the storage of the iteratively selected unique titles is further based on:
an available bandwidth between the first storage location and a second storage location at different time instances of a time interval.

13. A method comprising:
receiving, by a computing device, title dispersion criteria for a cache, wherein the title dispersion criteria comprise:
a quantity of target unique titles, and
a quantity of requests;

receiving, by the computing device, request history information for a plurality of unique titles;
selecting, based on the title dispersion criteria, a subset of the plurality of unique titles to be stored in the cache by:
determining, based on the request history information, a first quantity of requests to be serviced by the cache; and
iteratively selecting, after determining the first quantity of requests and starting from a top of a list of top ranked unique titles that are ranked according to a frequency of access, the subset of the plurality of the unique titles until a sum of quantities of historical requests for each of the unique titles in the iteratively selected subset satisfies the first quantity of requests; and
sending an instruction to cause the iteratively selected subset to be stored in the cache.

14. The method of claim 13 , wherein the title dispersion criteria are based on:
the quantity of target unique titles satisfying the quantity of requests.

15. The method of claim 13 , wherein iteratively selecting the subset of the plurality of the unique titles comprises selecting a minimal quantity of target unique titles satisfying the first quantity of requests to be serviced by the cache.

16. The method of claim 13 , wherein iteratively selecting the subset of the plurality of the unique titles comprises:
ranking the plurality of unique titles, of the request history information, to generate the list of top ranked unique titles, wherein each of the plurality of unique titles corresponds to a percentage of a total number of historical content item requests; and
comparing the sum of the quantities for each of the unique titles in the iteratively selected subset with the first quantity of requests.

17. The method of claim 13 , wherein the title dispersion criteria are based on the quantity of target unique titles satisfying the quantity of requests, and wherein the quantity of requests is based on a time of day.

18. The method of claim 13 , wherein the title dispersion criteria are based on the quantity of target unique titles satisfying the quantity of requests, and wherein the quantity of target unique titles is based on a time of day.

19. The method of claim 13 , wherein the title dispersion criteria are based on:
rankings of the plurality of unique titles; and
frequencies of access.

20. The method of claim 13 , wherein for each iterative selection of unique titles, a running sum of the percentages is updated and compared against a first target percentage.

21. A system comprising:
a first computing device;
wherein the first computing device comprises:
one or more processors; and
memory storing instructions that, when executed by the one or more processors of the first computing device, cause the first computing device to:
cause storage of a plurality of content items in a first storage location by:
determining, based on request history information, a first target percentage of content item requests to be serviced by the first storage location;
ranking a plurality of unique titles, in the request history information, to generate a list of top ranked unique titles, wherein each unique title corresponds to a percentag

Assignees

• Comcast Cable Comm Llc

Inventors

• Whyte Volnie
• Garg Amit
• Brown Tom
• Gaydos Robert
• Muehl Mark

Classifications

• H04N21/47202

  for requesting content on demand, e.g. video on demand · CPC title

• H04N21/2393

  involving handling client requests (scheduling or organising the servicing of application requests H04L67/60) · CPC title

• H04N21/23106

  involving caching operations (prefetching while addressing of a memory level in which the access to the desired data or data block requires associative addressing means within memory systems or architectures G06F12/0862; caching at an intermediate stage in a data network H04L67/568) · CPC title

• H04N7/17336

  Handling of requests in head-ends · CPC title

• H04N21/2407

  Monitoring of transmitted content, e.g. distribution time, number of downloads (arrangements for monitoring programmes for broadcast or for distribution combined with broadcast H04H20/14) · CPC title