Topics: SDNs and network programming; Flow and congestion control, routing, scheduling, and buffer management
Authors: Nicolas Gast (Inria, France); Benny Van Houdt (University of Antwerp, Belgium)
Presenter bio:
Nicolas Gast is a research associate at Inria, Grenoble. He
graduated from Ecole Normale Supérieure, Paris, in 2007 and obtained his
PhD from Univ. Grenoble-Alpes in 2010. From 2010 to 2014, he was a
post-doctoral researcher at EPFL, Lausanne, Switzerland. He joined Inria
in 2014. His research focuses on the development and the use of
stochastic models and optimization methods for the design of control
algorithms in large-scale systems.
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.
