Online coded caching

Ramtin Pedarsani, Mohammad Ali Maddah-Ali, Urs Niesen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

56 Scopus citations

Abstract

We consider a basic content distribution scenario consisting of a single origin server connected through a shared bottleneck link to a number of users each equipped with a cache of finite memory. The users issue a sequence of content requests from a set of popular files, and the goal is to operate the caches as well as the server such that these requests are satisfied with the minimum number of bits sent over the shared link. Assuming a basic Markov model for renewing the set of popular files, we characterize approximately the optimal long-term average rate of the shared link. We further prove that the optimal online scheme has approximately the same performance as the optimal offline scheme, in which the cache contents can be updated based on the entire set of popular files before each new request. To support these theoretical results, we propose an online coded caching scheme termed coded least-recently sent (LRS) and simulate it for a demand time series derived from the dataset made available by Netflix for the Netflix Prize. For this time series, we show that the proposed coded LRS algorithm significantly outperforms the popular least-recently used (LRU) caching algorithm.

Original languageEnglish (US)
Title of host publication2014 IEEE International Conference on Communications, ICC 2014
PublisherIEEE Computer Society
Pages1878-1883
Number of pages6
ISBN (Print)9781479920037
DOIs
StatePublished - 2014
Externally publishedYes
Event2014 1st IEEE International Conference on Communications, ICC 2014 - Sydney, NSW, Australia
Duration: Jun 10 2014Jun 14 2014

Publication series

Name2014 IEEE International Conference on Communications, ICC 2014

Other

Other2014 1st IEEE International Conference on Communications, ICC 2014
Country/TerritoryAustralia
CitySydney, NSW
Period6/10/146/14/14

Fingerprint

Dive into the research topics of 'Online coded caching'. Together they form a unique fingerprint.

Cite this