More Like this

1. Learning to Cache and Caching to Learn: Regret Analysis of Caching Algorithms

   https://doi.org/10.1109/TNET.2021.3105880  

   Bura, Archana; Rengarajan, Desik; Kalathil, Dileep; Shakkottai, Srinivas; Chamberland, Jean-Francois (January 2021, IEEE/ACM Transactions on Networking)

   null (Ed.)

   Crucial performance metrics of a caching algorithm include its ability to quickly and accurately learn a popularity distribution of requests. However, a majority of work on analytical performance analysis focuses on hit probability after an asymptotically large time has elapsed. We consider an online learning viewpoint, and characterize the ``regret'' in terms of the finite time difference between the hits achieved by a candidate caching algorithm with respect to a genie-aided scheme that places the most popular items in the cache. We first consider the Full Observation regime wherein all requests are seen by the cache. We show that the Least Frequently Used (LFU) algorithm is able to achieve order optimal regret, which is matched by an efficient counting algorithm design that we call LFU-Lite. We then consider the Partial Observation regime wherein only requests for items currently cached are seen by the cache, making it similar to an online learning problem related to the multi-armed bandit problem. We show how approaching this ``caching bandit'' using traditional approaches yields either high complexity or regret, but a simple algorithm design that exploits the structure of the distribution can ensure order optimal regret. We conclude by illustrating our insights using numerical simulations. 

   more » « less
2. Caching with Time Windows and Delays

   https://doi.org/10.1137/20M1346286  

   Gupta, Anupam; Kumar, Amit; Panigrahi, Debmalya (August 2022, SIAM Journal on Computing)
3. Fair caching networks

   https://doi.org/10.1016/j.peva.2020.102138  

   Liu, Yuezhou; Li, Yuanyuan; Ma, Qian; Ioannidis, Stratis; Yeh, Edmund (November 2020, Performance Evaluation)

   null (Ed.)
4. Fair Caching Networks

   https://doi.org/10.1145/3453953.3453973  

   Liu, Yuezhou; Li, Yuanyuan; Ma, Qian; Ioannidis, Stratis; Yeh, Edmund (March 2021, ACM SIGMETRICS Performance Evaluation Review)

   null (Ed.)

   We study fair content allocation strategies in caching networks through a utility-driven framework, where each request achieves a utility of its caching gain rate. The resulting problem is NP-hard. Submodularity allows us to devise a deterministic allocation strategy with an optimality guarantee factor arbitrarily close to 1-1/e. When 0 < α ≤ 1, we further propose a randomized strategy that attains an improved optimality guarantee, (1 - 1/e)1-α, in expectation. Through extensive simulations over synthetic and real-world network topologies, we evaluate the performance of our proposed strategies and discuss the effect of fairness. 

   more » « less
5. Writeback-Aware Caching

   https://doi.org/10.1137/1.9781611976021.1  

   Beckmann, Nathan; Gibbons, Phillip B.; Haeupler, Bernhard; McGuffey, Charles (January 2020, Symposium on Algorithmic Principles of Computer Systems (APOCS 2020))