More Like this

1. Inferring Causal Relationships to Improve Caching for Clients with Correlated Requests: Applications o VR

   Bari, Agrim; Zhou, Yuqi; de_Veciana, Gustavo (July 2026, The 35th International Conference on Computer Communications and Networks (ICCCN 2026))

   Collaborative VR and social-metaverse applicationspresent a unique challenge for edge caching due to highly correlated client request patterns. Unlike typical web browsing whererequests are independent, VR users might navigate spaces in groups. This generates sequential “leader-follower” requests that defy the traditional Independent Reference Model (IRM) used to design most caches. In this paper, we introduce the Grouped Client Request Model to formally capture these dependencies between client requests. Our analysis shows that standard policies like Least Recently Used (LRU) fail to adapt to these dynamics, often evicting content right before a follower needs it. To solve this, we propose Least Following and Recently Used (LFRU), a policy that dynamically learns the causal relationships driving these request patterns. By prioritizing objects based on inferred dependencies rather than just recency, LFRU significantly improves the cache hit ratio. Evaluations using emulated VR traces show that, in structured following scenarios, LFRU achieves up to 2.9x higher hit ratios than LRU and 1.9x higher than LFU. 

   more » « less
2. LRU Caching with Dependent Competing Requests

   https://doi.org/10.1109/INFOCOM.2018.8485891  

   Quan, Guocong; Ji, Kaiyi; Tan, Jian (April 2018, IEEE INFOCOM)

   Caching systems using the Least Recently Used (LRU) principle have now become ubiquitous. A fundamental question for these systems is whether the cache space should be pooled together or divided to serve multiple flows of data item requests in order to minimize the miss probabilities. In this paper, we show that there is no straight yes or no answer to this question, depending on complex combinations of critical factors, including, e.g., request rates, overlapped data items across different request flows, data item popularities and their sizes. To this end, we characterize the performance of multiple flows of data item requests under resource pooling and separation for LRU caching when the cache size is large. Analytically, we show that it is asymptotically optimal to jointly serve multiple flows if their data item sizes and popularity distributions are similar and their arrival rates do not differ significantly; the self-organizing property of LRU caching automatically optimizes the resource allocation among them asymptotically. Otherwise, separating these flows could be better, e.g., when data sizes vary significantly. We also quantify critical points beyond which resource pooling is better than separation for each of the flows when the overlapped data items exceed certain levels. Technically, for a broad class of heavy-tailed distributions we derive the asymptotic miss probabilities of multiple flows of requests with varying data item sizes in a shared LRU cache space. It also validates the characteristic time approximation under 

   more » « less
3. Mithril: mining sporadic associations for cache prefetching

   https://doi.org/10.1145/3127479.3131210  

   Yang, Juncheng; Karimi, Reza; Sæmundsson, Trausti; Wildani, Avani; Vigfusson, Ymir (January 2017, ACM Symposium on Cloud Computing)

   The growing pressure on cloud application scalability has accentuated storage performance as a critical bottleneck. Although cache replacement algorithms have been extensively studied, cache prefetching - reducing latency by retrieving items before they are actually requested - remains an underexplored area. Existing approaches to history-based prefetching, in particular, provide too few benefits for real systems for the resources they cost. We propose Mithril, a prefetching layer that efficiently exploits historical patterns in cache request associations. Mithril is inspired by sporadic association rule mining and only relies on the timestamps of requests. Through evaluation of 135 block-storage traces, we show that Mithril is effective, giving an average of a 55% hit ratio increase over LRU and Probability Graph, and a 36% hit ratio gain over Amp at reasonable cost. Finally, we demonstrate the improvement comes from Mithril being able to capture mid-frequency blocks. 

   more » « less
4. TRAGEN: a synthetic trace generator for realistic cache simulations

   https://doi.org/10.1145/3487552.3487845  

   Sabnis, Anirudh; Sitaraman, Ramesh K. (November 2021, Proceedings of the 21st ACM Internet Measurement Conference (IMC'21))

   Traces from production caching systems of users accessing con- tent are seldom made available to the public as they are considered private and proprietary. The dearth of realistic trace data makes it difficult for system designers and researchers to test and validate new caching algorithms and architectures. To address this key problem, we present TRAGEN, a tool that can generate a synthetic trace that is “similar” to an original trace from the production system in the sense that the two traces would result in similar hit rates in a cache simulation. We validate TRAGEN by first proving that the synthetic trace is similar to the original trace for caches of arbitrary size when the Least-Recently-Used (LRU) policy is used. Next, we empirically validate the similarity of the synthetic trace and original trace for caches that use a broad set of commonly-used caching policies that include LRU, SLRU, FIFO, RANDOM, MARKERS, CLOCK and PLRU. For our empirical validation, we use original request traces drawn from four different traffic classes from the world’s largest CDN, each trace consisting of hundreds of millions of requests for tens of millions of objects. TRAGEN is publicly available and can be used to generate synthetic traces that are similar to actual pro- duction traces for a number of traffic classes such as videos, social media, web, and software downloads. Since the synthetic traces are similar to the original production ones, cache simulations performed using the synthetic traces will yield similar results to what might be attained in a production setting, making TRAGEN a key tool for cache system developers and researchers. 

   more » « less
5. Asymptotic Miss Ratio of LRU Caching with Consistent Hashing

   https://doi.org/10.1109/INFOCOM.2018.8485860  

   Ji, Kaiyi; Quan, Guocong; Tan, Jian (April 2018, IEEE INFOCOM)

   To efficiently scale data caching infrastructure to support emerging big data applications, many caching systems rely on consistent hashing to group a large number of servers to form a cooperative cluster. These servers are organized together according to a random hash function. They jointly provide a unified but distributed hash table to serve swift and voluminous data item requests. Different from the single least-recently-used (LRU) server that has already been extensively studied, theoretically characterizing a cluster that consists of multiple LRU servers remains yet to be explored. These servers are not simply added together; the random hashing complicates the behavior. To this end, we derive the asymptotic miss ratio of data item requests on a LRU cluster with consistent hashing. We show that these individual cache spaces on different servers can be effectively viewed as if they could be pooled together to form a single virtual LRU cache space parametrized by an appropriate cache size. This equivalence can be established rigorously under the condition that the cache sizes of the individual servers are large. For typical data caching systems this condition is common. Our theoretical framework provides a convenient abstraction that can directly apply the results from the simpler single LRU cache to the more complex LRU cluster with consistent hashing. 

   more » « less