Adaptive Caching with Follow The Perturbed Leader Replacement Policy

Bachelor Thesis (2022)
Authors

M. Mäkelä (TU Delft - Electrical Engineering, Mathematics and Computer Science)

Supervisors

George Iosifidis (TU Delft - Embedded Systems)

Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright
© 2022 Mikkel Mäkelä
More Info
expand_more
Publication Year
2022
Language
English
Copyright
© 2022 Mikkel Mäkelä
Graduation Date
24-06-2022
Awarding Institution
Delft University of Technology
Project
CSE3000 Research Project
Programme
Computer Science and Engineering
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Abstract

Caching is a widely relevant problem in the world of ever-growing online traffic. In recent years, on-line learning methods have inspired algorithms that outperform more traditional, widely used policies such as LRU and LFU. Furthermore, some of these newly proposed policies have proven upper regret bounds, offering guarantees on arbitrary request se-quences. In this paper, we inspect one such policy named Follow the Perturbed Leader (FTPL), which we found to perform reasonably well among dif-ferent traces but showcases poor ability to adapt to changing file popularities. We propose a modifi-cation to the algorithm which addresses this issue, and although it comes with no performance guar-antees, we leverage the expert problem to maintain such a guarantee. More precisely, we utilize dif-ferent configurations of FTPL, including the one with a tight upper bound, as experts in an Incre-mentally Adaptive Weighted Majority (IAWM) al-gorithm. Our findings include simulation results on the MovieLens trace, as well as multiple syn-thetic traces, some with adversarial properties. We record these in a setting where a single user is con-nected to a single cache, which is then connected to a server, but also in a bipartite network where mul-tiple clients execute traces against multiple caches.

Files

License info not available