Online Coded Caching

By Ramtin Pedarsani, Mohammad Ali Maddah-Ali, Urs Niesen. IEEE/ACM Transactions on Networking, 2013

315 citations recorded by the source corpus.

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 caching algorithm.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/98f01f67d5ca3f9c073933a838a7748648b46d28

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Fundamental Limits of Caching (2012, background): “For a probabilistic model of user requests, this update rule is shown to be approximately optimal in [17].”
Wireless caching: technical misconceptions and business barriers (2016, background): “This promising idea has sprung a wealth of research efforts, some of them in parallel or right after, such as device-to-device (D2D) networks [30], [31], non-uniform content popularities [32], online caching policies [33], multi-servers [34], multi-library [35] and multihop wireless networks with co”
Hierarchical Edge Caching in Device-to-Device Aided Mobile Networks: Modeling, Optimization, and Design (2018, background): “…Caching (MPC) , derived by caching most popular content in the bottom level and upper level; 3) Least Recently Used (LRU) Caching , derived from [43] to address the same case in the paper; 4) Hierarchical Uncoded Edge Caching (HUEC) , derived by carefully modifying the proposed hierarchical…”
Speeding Up Distributed Machine Learning Using Codes (2015, unknown): “Coded caching has been studied in many scenarios such as decentralized coded caching [67], online coded caching [68], hierarchical coded caching for wireless communication [69], and device-to-device coded caching [70].”
The Exact Rate-Memory Tradeoff for Caching With Uncoded Prefetching (2016, methodology): “The caching problem has also been extended in various directions, including decentralized caching [17], online caching [18], caching with nonuniform demands [19]–[22], hierarchical caching [23]–[25], device-to-device caching [26], cache-aided interference channels [27]–[30], caching on file selectio”
Optimal and Scalable Caching for 5G Using Reinforcement Learning of Space-Time Popularities (2017, background): “Finally, recent studies have investigated the role of coding for enhancing performance in cache-enabled networks [18]–[20]; see also [21], [22], and [23], where device-to-device “structure-”