LRU Caching with Dependent Competing Requests

Least-recently-used (LRU) caching systems have been widely used, and are increasingly deployed driven by emerging trends for big data. In a typical scenario, these systems are used to serve multiple flows of dependent data item requests that are also correlated over time. These flows compete for the limited cache space. Characterizing the miss ratios of these competing flows can facilitate the design and improve the system performance. The existing asymptotic analyses for correlated requests give explicit results for Zipf's distributions with the index greater than a critical value (one). Consequently, the asymptotic result is inaccurate around this critical point, which notably is also the typical parameter region reported by many empirical measurements. In contrast, we derive the asymptotic miss ratios of multiple flows for a large class of truncated heavy-tailed data item popularity distributions with time dependency. Importantly, it significantly improves the accuracy in numerical computations when the index of a Zipf's distribution is close to one. Moreover, the result generalizes beyond Zipf's distributions, e.g., to Weibull, for multiple flows of correlated data item requests. Our asymptotic result directly exploits the critical properties of the distribution and the truncated support region. As our versatile expression is explicit, it avoids the numerical computations required by the characteristic time approximation. Interestingly, it also validates the characteristic time approximation with new forms for multiple flows of competing requests that are correlated over time under certain conditions.