Stochastic Bounds on Inter-Miss Times from TTL Caches

摘要

Because caching is a pervasive technology in modern computing and networks, characterizing the performance of caches is an important aspect of system performance and scalability analysis. However, analytical models even for the hit ratio of single caches proved to be challenging and many configurations already encompass hierarchies of caches. We build on previous work which showed that Time-to-live (TTL) based caches are more general than (e.g.) LRU, FIFO, or RND cache models. This work introduces an appropriate mathematical abstraction of TTL cache models by constructing a stopping time representation which allows to address these models in a unified manner. We derive an exact equation for the first moment and bounds on all moments of the miss process of a TTL-based cache for which we report preliminary simulation results. Our approach yields explicit closed-form formulas in many cases but is still general enough to capture different previously introduced TTL-based caching models.