TTL approximations of the cache replacement algorithms LRU(m) and h-LRU

Autor: Nicolas Gast, Benny Van Houdt
Přispěvatelé: Performance analysis and optimization of LARge Infrastructures and Systems (POLARIS ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Universiteit Antwerpen [Antwerpen], Universiteit Antwerpen = University of Antwerpen [Antwerpen]
Rok vydání: 2017
Předmět:
LRU
Computer Networks and Communications
Computer science
CPU cache
02 engineering and technology
Parallel computing
Caching
Fixed point
01 natural sciences
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]
010104 statistics & probability
0202 electrical engineering
electronic engineering
information engineering
Network performance
Markovian arrival process
[MATH]Mathematics [math]
0101 mathematics
Cache algorithms
TTL approximations
Computer. Automation
Hardware_MEMORYSTRUCTURES
Adaptive replacement cache
020206 networking & telecommunications
Partition (database)
[MATH.MATH-PR]Mathematics [math]/Probability [math.PR]
[INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF]
Hardware and Architecture
Modeling and Simulation
[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Cache
Algorithm
Software
Zdroj: Performance Evaluation
Performance Evaluation, Elsevier, 2017, ⟨10.1016/j.peva.2017.09.002⟩
Performance Evaluation, 2017, ⟨10.1016/j.peva.2017.09.002⟩
Performance evaluation
ISSN: 0166-5316
DOI: 10.1016/j.peva.2017.09.002
Popis: 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: 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 use this approximation and trace-based simulation to compare the performance of h-LRU and LRU(m). First, we show that they perform alike, while the latter requires less work when a hit/miss occurs. Second, we show that as opposed to LRU, h-LRU and LRU(m) are sensitive to the correlation between consecutive inter-request times. Last, we study cache partitioning. In all tested cases, the hit probability improved by partitioning the cache into different parts each being dedicated to a particular content provider. However, the gain is limited and the optimal partition sizes are very sensitive to the problem's parameters. (C) 2017 Elsevier B.V. All rights reserved.
Databáze: OpenAIRE
Externí odkaz: