Optimum caching versus LRU and LFU: Comparison and combined limited look-ahead strategies
| Autor: | Gerhard Hasslinger, Juho Heikkinen, Oliver Hohlfeld, Konstantinos Ntougias, Frank Hasslinger |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Hardware_MEMORYSTRUCTURES
Zipf's law Computer science Computation Markov process 020206 networking & telecommunications 02 engineering and technology computer.software_genre symbols.namesake 0202 electrical engineering electronic engineering information engineering Hit rate symbols Range (statistics) 020201 artificial intelligence & image processing Data mining Look-ahead computer Cache algorithms Least frequently used |
| Zdroj: | WiOpt |
| DOI: | 10.23919/wiopt.2018.8362880 |
| Popis: | We compare web caching strategies based on the least recently used (LRU) and the least frequently used (LFU) replacement principles with optimum caching according to Belady's algorithm. The achievable hit rates of the strategies are shown to improve with the exploited knowledge about the request pattern while the computation effort is also increasing. The results give an overview of performance tradeoffs in the whole relevant range for web caching with Zipf request pattern. In a second part, we study a combined approach of the optimum strategy for a limited look-ahead with LRU, LFU or other non-predictive methods. We evaluate the hit rate gain depending on the extent of the look-ahead for request traces and for the independent reference model (IRM) via simulation and derive an analytic confirmation of the observed behaviour. It is shown that caching for video streaming can benefit from the proposed look-ahead technique, when replacement decisions can be partly revised due to new requests being encountered during long lasting content updates. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|