Adaptive bitrate video cache

Patent metadata

Field	Value
Publication number	US-11758203-B2
Application number	US-201916714229-A
Country	US
Kind code	B2
Filing date	Dec 13, 2019
Priority date	Dec 13, 2019
Publication date	Sep 12, 2023
Grant date	Sep 12, 2023

Abstract

Devices, computer-readable media, and methods for making a cache admission decision regarding a video chunk are described. For instance, a processing system including at least one processor may obtain a request for a first chunk of a first video, determine that the first chunk is not stored in a cache, and apply, in response to the determining that the first chunk is not stored in the cache, a classifier to predict whether the first chunk will be re-requested within a time horizon, where the classifier is trained in accordance with a set of features associated with a plurality of chunks of a plurality of videos. When it is predicted via the classifier that the first chunk will be re-requested within the time horizon, the processing system may store the first chunk in the cache.

First claim

What is claimed is:

1. A method comprising:
obtaining, by a processing system including at least one processor, a request for a first chunk of a first video;
determining, by the processing system, that the first chunk is not stored in a cache;
applying, by the processing system in response to the determining that the first chunk is not stored in the cache, a machine learning classifier to predict whether the first chunk will be re-requested within a time horizon, wherein the machine learning classifier is trained in accordance with a set of features associated with a plurality of chunks of a plurality of videos;
storing, by the processing system, the first chunk in the cache, when it is predicted via the machine learning classifier that the first chunk will be re-requested within the time horizon; and
evicting, by the processing system, at least a second chunk from the cache in accordance with an eviction process, wherein the eviction process includes:
identifying the second chunk as having a longest next request estimate as compared to next request estimates of a plurality of chunks in the cache, wherein for a given chunk of the plurality of chunks in the cache, the eviction process weights a next request estimate for the given chunk in accordance with a relative popularity of a track of the given chunk as compared to other tracks for a same video to which the given chunk belongs; and
evicting the second chunk from the cache when it is determined that the second chunk has the longest next request estimate.

2. The method of claim 1 , wherein the time horizon is based upon a size of the cache.

3. The method of claim 2 , wherein the time horizon comprises an estimate of a time to replace contents of the cache at a full capacity in accordance with a first-in-first-out policy.

4. The method of claim 1 , wherein the set of features comprises:
a chunk size;
a chunk index; and
a chunk bitrate.

5. The method of claim 4 , wherein the set of features further comprises:
a number of sessions for streaming the first video;
an average number of sessions for streaming the first video within a given time period;
a session inter-arrival time for the first video; and
a time since a start of a last session for streaming the first video.

6. The method of claim 5 , wherein the set of features further comprises:
a time of day; and
a day of week.

7. The method of claim 1 , wherein the machine learning classifier outputs a probability estimate for a future request for the first chunk within the time horizon, wherein the first chunk is stored in the cache when it is predicted via the machine learning classifier that the first chunk will be re-requested within the time horizon and when the probability estimate complies with a threshold.

8. The method of claim 1 , further comprising:
obtaining a request for a third chunk of the first video or of a second video;
determining that the third chunk is not stored in the cache;
applying, in response to the determining that the third chunk is not stored in the cache, the machine learning classifier to predict whether the third chunk will be re-requested within the time horizon; and
declining to store the third chunk in the cache, when it is predicted via the machine learning classifier that the third chunk will not be re-requested within the time horizon.

9. The method of claim 1 , further comprising:
determining, in response to selecting to store the first chunk in the cache, whether a storage of the first chunk in the cache will cause the cache to exceed an occupancy threshold, wherein the evicting the at least the second chunk is performed in response to determining that the storage of the first chunk in the cache will cause the cache to exceed the occupancy threshold.

10. The method of claim 1 , further comprising:
obtaining a request for a third chunk of a second video;
determining that the third chunk is not stored in the cache;
determining that a session inter-arrival time of the second video exceeds a threshold; and
determining to not store the third chunk in the cache, in response to the determining that the session inter-arrival time of the second video exceeds the threshold.

11. A non-transitory computer-readable medium storing instructions which, when executed by a processing system including at least one processor, cause the processing system to perform operations, the operations comprising:
obtaining a request for a first chunk of a first video;
determining that the first chunk is not stored in a cache;
applying, in response to the determining that the first chunk is not stored in the cache, a machine learning classifier to predict whether the first chunk will be re-requested within a time horizon, wherein the machine learning classifier is trained in accordance with a set of features associated with a plurality of chunks of a plurality of videos;
storing the first chunk in the cache, when it is predicted via the machine learning classifier that the first chunk will be re-requested within the time horizon; and
evicting at least a second chunk from the cache in accordance with an eviction process, wherein the eviction process includes:
identifying the second chunk as having a longest next request estimate as compared to next request estimates of a plurality of chunks in the cache, wherein for a given chunk of the plurality of chunks in the cache, the eviction process weights a next request estimate for the given chunk in accordance with a relative popularity of a track of the given chunk as compared to other tracks for a same video to which the given chunk belongs; and
evicting the second chunk from the cache when it is determined that the second chunk has the longest next request estimate.

12. The non-transitory computer-readable medium of claim 11 , wherein the time horizon is based upon a size of the cache.

13. The non-transitory computer-readable medium of claim 12 , wherein the time horizon comprises an estimate of a time to replace contents of the cache at a full capacity in accordance with a first-in-first-out policy.

14. The non-transitory computer-readable medium of claim 11 , wherein the set of features comprises:
a chunk size;
a chunk index; and
a chunk bitrate.

15. The non-transitory computer-readable medium of claim 14 , wherein the set of features further comprises:
a number of sessions for streaming the first video;
an average number of sessions for streaming the first video within a given time period;
a session inter-arrival time for the first video; and
a time since a start of a last session for streaming the first video.

16. The non-transitory computer-readable medium of claim 15 , wherein the set of features further comprises:
a time of day; and
a day of week.

17. The non-transitory computer-readable medium of claim 11 , wherein the machine learning classifier outputs a probability estimate for a future request for the first chunk within the time horizon, wherein the first chunk is stored in the cache when it is predicted via the machine learning classifier that the first chunk will be re-requested within the time horizon and when the probability estimate complies with a threshold.

18. The non-transitory computer-readable medium of claim 11 , wherein the operations further comprise:
obtaining a request for a third chunk of the first video or of a second video;
determining that the third chunk is not stored in the cache;
applying, in response to the determining that the third chunk is not stored in the cache, the machine learning classifier

Assignees

• At & T Ip I Lp
• Univ Southern California

Inventors

• Hao Shuai
• Sen Subhabrata
• Halepovic Emir
• Akhtar Zahaib
• Govindan Ramesh
• Li Yaguang

Classifications

• H04N21/23106 Primary

  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

• H04N21/2393

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

• H04N21/251

  Learning process for intelligent management, e.g. learning user preferences for recommending movies (details of learning user preferences for the retrieval of video data in a video database G06F16/739; computer systems using learning methods G06N3/08) · CPC title

• H04N21/8456

  by decomposing the content in the time domain, e.g. in time segments · CPC title

• H04L67/568

  Storing data temporarily at an intermediate stage, e.g. caching · CPC title