Our recent work Performance analysis of list-based caches with non-uniform access about stochastic modelling of caches has been accepted for publication in IEEE/ACM Transactions on Networking. This is a collaboration with Nicolas Gast (INRIA). The journal paper extends an earlier work published at INFOCOM 2018.
Abstract: List-based caches can offer lower miss rates than single-list caches, but their analysis is challenging due to state space explosion. In this setting, we propose novel methods to analyze performance for a general class of list-based caches with tree structure, non-uniform access to items and lists, and random or first-in first-out replacement policies. Even though the underlying Markov process is shown to admit a product-form solution, this is difficult to exploit for large caches. Thus, we develop novel approximations for cache performance metrics, in particular by means of a singular perturbation method and a refined mean field approximation. We compare the accuracy of these approaches to simulations, finding that our new methods rapidly converge to the equilibrium distribution as the number of items and the cache capacity grow in a fixed ratio. We find that
they are much more accurate than fixed point methods similar to prior work, with mean average errors typically below 1:5% even for very small caches. Our models are also generalized to account for synchronous requests, fetch latency, and item sizes, extending the applicability of approximations for list-based caches.
