Accurate Learning or Fast Mixing? Dynamic Adaptability of Caching Algorithms
Publication in refereed journal


Times Cited
Altmetrics Information
.

Other information
AbstractTypical analysis of content caching algorithms using the metric of steady state hit probability under a stationary request process does not account for performance loss under a variable request arrival process. In this paper, we instead conceptualize caching algorithms as complexity-limited online distribution learning algorithms and use this vantage point to study their adaptability from two perspectives: 1) the accuracy of learning a fixed popularity distribution and 2) the speed of learning items' popularity. In order to attain this goal, we compute the distance between the stationary distributions of several popular algorithms with that of a genie-aided algorithm that has the knowledge of the true popularity ranking, which we use as a measure of learning accuracy. We then characterize the mixing time of each algorithm, i.e., the time needed to attain the stationary distribution, which we use as a measure of learning efficiency. We merge both the above mentioned measures to obtain the "learning error" representing both how quickly and how accurately an algorithm learns the optimal caching distribution and use this to determine the trade-off between these two objectives of many popular caching algorithms. Informed by the results of our analysis, we propose a novel hybrid algorithm, adaptive-least recently used, that learns both faster and better the changes in the popularity. We show numerically that it also outperforms all other candidate algorithms when confronted with either a dynamically changing synthetic request process or using real world traces.
Acceptance Date18/04/2018
All Author(s) ListJian Li, Srinivas Shakkottai, John C. S. Lui, Vijay Subramanian
Journal nameIEEE Journal on Selected Areas in Communications
Year2018
Month6
Volume Number36
Issue Number6
PublisherIEEE
Pages1314 - 1330
ISSN0733-8716
eISSN1558-0008
LanguagesEnglish-United States

Last updated on 2020-23-03 at 02:45