Exact analysis of TTL cache networks

Daniel S. Berger, Philipp Gland, Sahil Singla, Florin Ciucu

Research output: Contribution to journalArticle

47 Scopus citations

Abstract

TTL caching models have recently regained significant research interest due to their connection to popular caching policies such as LRU. This paper advances the state-of-the-art analysis of TTL-based cache networks by developing two exact methods with orthogonal generality and computational complexity. The first method generalizes existing results for line networks under renewal requests to the broad class of caching policies whereby evictions are driven by stopping times; in addition to classical policies used in DNS and web caching, our stopping time model captures an emerging new policy implemented in SDN switches and Amazon web services. The second method further generalizes these results to feedforward networks with Markov arrival process (MAP) requests. MAPs are particularly suitable for non-line networks because they are closed not only under superposition and splitting, as known, but also under caching operations with phase-type (PH) TTL distributions. The crucial benefit of the two closure properties is that they jointly enable the first exact analysis of TTL feedforward cache networks in great generality. Moreover, numerical results highlight that existing Poisson approximations in binary-tree topologies are subject to relative errors as large as 30%, depending on the tree depth.

Original languageEnglish (US)
Pages (from-to)2-23
Number of pages22
JournalPerformance Evaluation
Volume79
DOIs
StatePublished - Sep 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Modeling and Simulation
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • Cache networks
  • Markov arrival process
  • TTL caches

Fingerprint Dive into the research topics of 'Exact analysis of TTL cache networks'. Together they form a unique fingerprint.

  • Cite this