Dynamic Cache Replacement Policy Selection Using Experts

Abstract

In recent years, researchers proposed several universal caching policies. These universal caching policies aim to work well with any request sequence. However, with this universal well-working property, these caching policies sometimes do not work as well as conventional caching policies such as Least-Recently-Used and Least-Frequently-Used. This thesis introduces an online learning approach to dynamically switch between caching policies. The dynamical switching selects the most suitable caching policy for the request sequence and thus ensures the best of both worlds, working well under any request sequence and having comparable performance to the conventional caching policies. The Dynamic Expert Caching (DEC) policy designed in this thesis uses algorithms from the expert selection problem to achieve the dynamic caching policy selection. The DEC policy is evaluated using various datasets where it is shown to have comparable performance to the best caching policies in the simulations. The DEC policy is also adapted to work in a network of caches, named MultiDEC. In this setting, MultiDEC has significant advantages over other universal caching policies where each caching node can have a different caching policy that is optimal.