Asymptotically Exact TTL-Approximations of the Cache Replacement
Algorithms LRU(m) and h-LRU
N. Gast, und B. Houdt. 28th International Teletraffic Congress (ITC 28), Würzburg, Germany, (September 2016)
Zusammenfassung
Computer system and network performance can be significantly
improved by caching frequently used information. When the cache size
is limited, the cache replacement algorithm has an important impact
on the effectiveness of caching. In this paper we introduce
time-to-live (TTL) approximations to determine the cache hit
probability of two classes of cache replacement algorithms: the
recently introduced h-LRU and LRU(m). These approximations
only require the requests to be generated according to a general
Markovian arrival process (MAP). This includes phase-type renewal
processes and the IRM model as special cases.
We provide both numerical and theoretical support for the claim that
the proposed TTL approximations are asymptotically exact. In
particular, we show that the transient hit probability converges to
the solution of a set of ODEs (under the IRM model), where the fixed
point of the set of ODEs corresponds to the TTL approximation. We
further show, by using synthetic and trace-based workloads, that
h-LRU and LRU(m) perform alike, while the latter requires less work
when a hit/miss occurs. We also show that, as opposed to LRU, h-LRU
and LRU(m) are sensitive to the correlation between consecutive
inter-request times.
%0 Conference Paper
%1 Gast2016
%A Gast, Nicolas
%A Houdt, Benny Van
%B 28th International Teletraffic Congress (ITC 28)
%C Würzburg, Germany
%D 2016
%K itc itc28
%T Asymptotically Exact TTL-Approximations of the Cache Replacement
Algorithms LRU(m) and h-LRU
%U https://gitlab2.informatik.uni-wuerzburg.de/itc-conference/itc-conference-public/-/raw/master/itc28/Gast2016.pdf?inline=true
%X Computer system and network performance can be significantly
improved by caching frequently used information. When the cache size
is limited, the cache replacement algorithm has an important impact
on the effectiveness of caching. In this paper we introduce
time-to-live (TTL) approximations to determine the cache hit
probability of two classes of cache replacement algorithms: the
recently introduced h-LRU and LRU(m). These approximations
only require the requests to be generated according to a general
Markovian arrival process (MAP). This includes phase-type renewal
processes and the IRM model as special cases.
We provide both numerical and theoretical support for the claim that
the proposed TTL approximations are asymptotically exact. In
particular, we show that the transient hit probability converges to
the solution of a set of ODEs (under the IRM model), where the fixed
point of the set of ODEs corresponds to the TTL approximation. We
further show, by using synthetic and trace-based workloads, that
h-LRU and LRU(m) perform alike, while the latter requires less work
when a hit/miss occurs. We also show that, as opposed to LRU, h-LRU
and LRU(m) are sensitive to the correlation between consecutive
inter-request times.
@inproceedings{Gast2016,
abstract = {Computer system and network performance can be significantly
improved by caching frequently used information. When the cache size
is limited, the cache replacement algorithm has an important impact
on the effectiveness of caching. In this paper we introduce
time-to-live (TTL) approximations to determine the cache hit
probability of two classes of cache replacement algorithms: the
recently introduced h-LRU and LRU(m). These approximations
only require the requests to be generated according to a general
Markovian arrival process (MAP). This includes phase-type renewal
processes and the IRM model as special cases.
We provide both numerical and theoretical support for the claim that
the proposed TTL approximations are asymptotically exact. In
particular, we show that the transient hit probability converges to
the solution of a set of ODEs (under the IRM model), where the fixed
point of the set of ODEs corresponds to the TTL approximation. We
further show, by using synthetic and trace-based workloads, that
h-LRU and LRU(m) perform alike, while the latter requires less work
when a hit/miss occurs. We also show that, as opposed to LRU, h-LRU
and LRU(m) are sensitive to the correlation between consecutive
inter-request times.},
added-at = {2016-08-31T16:30:53.000+0200},
address = {Würzburg, Germany},
author = {Gast, Nicolas and Houdt, Benny Van},
biburl = {https://www.bibsonomy.org/bibtex/243fde879130b579233747d77285927fa/itc},
booktitle = {28th International Teletraffic Congress (ITC 28)},
days = {12},
interhash = {1a6925d9a0f8ee092cd37e9a4c099af1},
intrahash = {43fde879130b579233747d77285927fa},
keywords = {itc itc28},
month = {Sept},
timestamp = {2020-05-26T16:53:35.000+0200},
title = {Asymptotically Exact TTL-Approximations of the Cache Replacement
Algorithms LRU(m) and h-LRU},
url = {https://gitlab2.informatik.uni-wuerzburg.de/itc-conference/itc-conference-public/-/raw/master/itc28/Gast2016.pdf?inline=true},
year = 2016
}