Cache Management In A Video Content Distribution Network

• US 20120159558A1
• Filed: 12/20/2010
• Published: 06/21/2012
• Est. Priority Date: 12/20/2010
• Status: Active Grant

• Current Assignee: Comcast Cable Communications LLC (Comcast Corporation)
• Original Assignee: Comcast Cable Communications LLC (Comcast Corporation)
• Inventors: Garg, Amit, Brown, Tom, Gaydos, Robert, Whyte, Volnie, Muehl, Mark
• Granted Patent: US 8,863,204 B2
• Time in Patent Office: Days
• US Class Current: 725/95
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 2212/263 Network storage, e.g. SAN or NAS
• CPC Class Codes: G06F 2212/284 being distributed
• CPC Class Codes: H04N 21/222 Secondary servers, e.g. proxy server, cable television Head-end provisioning of proxy services in data packet switching networks H04L67/56
• CPC Class Codes: H04N 21/23103 using load balancing strategies, e.g. by placing or distributing content on different disks, different memories or different servers storage management G06F3/0604; allocation of resources considering the load in multiprogramming arrangements G06F9/505; techniques for rebalancing the load in a distributed system G06F9/5083; access to distributed or replicated servers, e.g. load balancing, in data networks H04L67/1001
• CPC Class Codes: H04N 21/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 Class Codes: H04N 21/23113 involving housekeeping operations for stored content, e.g. prioritizing content for deletion because of storage space restrictions storage management, e.g. defragmentation G06F3/0604; snloading stored programs G06F9/445; housekeeping operations in file systems, e.g. deletion policies G06F16/10; buffering arrangements in a network node or in an end terminal in packet networks H04L49/90
• CPC Class Codes: H04N 21/2393 involving handling client requests scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04N 21/2402 Monitoring of the downstream path of the transmission network, e.g. bandwidth available traffic monitoring in data switching networks H04L43/00; monitoring data switching networks utilization H04L43/0876
• CPC Class Codes: H04N 21/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 Class Codes: H04N 21/2408 Monitoring of the upstream path of the transmission network, e.g. client requests monitoring data switching networks utilization H04L43/0876; scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04N 21/47202 for requesting content on demand, e.g. video on demand
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

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.

Claims

1. A method comprising:

determining a title dispersion value associated with a content distribution network comprising a content library;

determining a preferred cache size for a first cache device in the content distribution network based on the determined title dispersion value; and

configuring the first cache device to operate in accordance with the determined preferred cache size.

2. The method of claim 1, further comprising determining a bandwidth availability value for the content distribution network, wherein determining the preferred cache size for the first cache device is further based on the determined bandwidth availability value.

3. The method of claim 2, wherein the bandwidth availability value for the content distribution network comprises a target bandwidth allocated for content transfers between the content library and the first cache device at a peak network utilization time period in the content distribution network.

4. The method of claim 3, wherein the title dispersion value comprises a count of unique assets estimated to be requested at the first cache device over a period of time proximate to the peak network utilization time period.

5. The method of claim 4, wherein determining the title dispersion value comprises accessing a title dispersion function corresponding to a statistical distribution of the requests for titles in the content library.

6. The method of claim 2, wherein determining the preferred cache size comprises:

performing a first calculation of a maximum number of assets transferrable from the content library during a period of time, the first calculation based on the bandwidth availability value;

performing a second calculation of a minimum number of assets required to be stored in the first cache device, the second calculation based on a number of unique assets estimated to be requested at the first cache device during the period of time, the calculated maximum number of assets transferrable from the content library over the period of time, and a statistical distribution of the requests for titles in the content library; and

performing a third calculation of the preferred cache size, the third calculation based on the calculated minimum number of assets required to be stored in the first cache device, and an estimated average asset size.

7. The method of claim 6, wherein the estimated average asset size is based on an estimated ratio of standard definition assets to high definition assets.

8. The method of claim 2, wherein the content distribution network comprises a multi-tiered video delivery architecture and the first cache device is an edge cache in said multi-tiered video delivery architecture.

9. The method of claim 8, wherein the bandwidth availability value corresponds to content transfers between a middle-tier cache device in said multi-tiered video delivery architecture and the edge cache.

10. A method comprising:

receiving a request for a first asset at a first cache device in a content distribution network comprising a multi-tiered video delivery architecture, wherein the content distribution network comprises a content library storing a set of assets, and wherein the first cache device comprises a memory storing a subset of the set of assets stored in the content library;

determining that the first asset is not stored in the memory of the first cache device;

requesting the first asset from a higher level storage device in the multi-tiered video delivery architecture;

receiving the first asset at the first cache device;

performing a comparative analysis on a plurality of assets stored in the memory of the first cache device, wherein said comparative analysis is based on cache management criteria comprising one or more of;

popularity of the asset at the first cache device, popularity of the asset at a higher level device in the multi-tiered video delivery architecture, popularity of the asset within a time window;

size of the asset, and the size distribution of assets at the first cache device;

identifying a second asset to be removed from the memory of the first cache device, based on the comparative analysis;

removing the second asset from the memory of the first cache device; and

storing the first asset in the memory of the first cache device.

11. The method of claim 10, wherein identifying the second asset to be removed from the memory of the first cache device comprises:

determining the size of the requested first asset;

determining that multiple assets, each smaller than the requested first asset, are to be removed from the first cache device; and

identifying a plurality of assets, including the second asset, to be removed from the memory of the first cache device, wherein the sum size of the identified plurality of assets is greater than or equal to the size of the requested first asset.

12. The method of claim 11, wherein the determination that multiple assets are to be removed from the first cache is based on a size distribution analysis of the plurality of assets stored in the memory of the first cache device.

13. The method of claim 10, wherein performing the comparative analysis comprises comparing popularity values of at least two assets stored in the memory of the first cache device over a relevant time window, wherein the relevant time window is at least one of a current day of the week or a current daypart.

14. The method of claim 10, wherein performing the comparative analysis comprises receiving popularity values for at least two assets stored in the memory of the first cache device from a higher level device in the multi-tiered video delivery architecture, the popularity values corresponding to numbers of times that the at least two assets have been requested by users of other cache devices in the multi-tiered video delivery architecture.

15. The method of claim 10, wherein identifying the second asset to be removed from the memory is based on a determination of the bit rate of the second asset.

16. The method of claim 10, wherein identifying the second asset to be removed from the memory is based on a determination that the requested first asset has been requested at the first cache device at least a predetermined number of times.

17. An apparatus comprising:

a processor controlling at least some operations of the apparatus;

a memory storing computer executable instructions that, when executed by the processor, cause the apparatus to perform;

determining a title dispersion value associated with a content distribution network comprising a content library;

determining a preferred cache size for a first cache device in the content distribution network based on the determined title dispersion value; and

configuring the first cache device to operate in accordance with the determined preferred cache size.

18. The apparatus of claim 17, the memory storing further computer executable instructions that causes the apparatus to perform:

determining a bandwidth availability value for the content distribution network, and

wherein determining the preferred cache size for the first cache device is further based on the determined bandwidth availability value.

19. The apparatus of claim 18, wherein the bandwidth availability value for the content distribution network comprises a target bandwidth allocated for content transfers between the content library and the first cache device at a peak network utilization time period in the content distribution network,

wherein the title dispersion value comprises a count of unique assets estimated to be requested at the first cache device over a period of time proximate to the peak network utilization time period, and

wherein determining the title dispersion value comprises accessing a title dispersion function corresponding to a statistical distribution of the requests for titles in the content library.

20. The apparatus of claim 18, wherein determining the preferred cache size comprises:

performing a first calculation of a maximum number of assets transferrable from the content library during a period of time, the first calculation based on the bandwidth availability value;

performing a second calculation of a minimum number of assets required to be stored in the first cache device, the second calculation based on a number of unique assets estimated to be requested at the first cache device during the period of time, the calculated maximum number of assets transferrable from the content library over the period of time, and a statistical distribution of the requests for titles in the content library; and

performing a third calculation of the preferred cache size, the third calculation based on the calculated minimum number of assets required to be stored in the first cache device, and an estimated average asset size.