Maximizing Cache Hit Ratios by Variance Reduction

TTL cache models provide an attractive unified approximation framework for caching policies like LRU and FIFO, whose exact analysis is notoriously hard. In this paper, we advance the understanding of TTL models by explicitly considering stochastic capacity constraints. We find in particular that reducing the variance of the cache occupancy is instrumental to optimize the cache hit ratio in an online setting. To enforce such a desired low variance, we propose a novel extension of the TTL model by rewarding popular objects with longer TTLs. An attractive feature of the proposed model is that it remains closed under an exact network analysis.