SAcache: A Strongly Adaptive Online Caching Scheme for Non-Stationary Environments

Online caching at the network edge is becoming increasingly important for alleviating the transmission pressure on backbone networks. Previous studies on online caching policies mainly use the static regret as the performance metric, which relies on a fixed benchmark and lacks the capacity to ensure optimal performance in non-stationary environments. In this letter, we introduce the strongly adaptive regret into online caching and propose a Strongly Adaptive online caching scheme (SAcache). Our SAcache scheme focuses on the performance over time intervals with a length between <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\tau _{\min }$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\tau _{\max }$ </tex-math></inline-formula>, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\tau _{\min }$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\tau _{\max }$ </tex-math></inline-formula> are the lower and upper bound on how long the environment changes, respectively. SAcache consists of multiple interval caches operating in a lazy restart mode to make candidate caching decisions, and an aggregated cache that weights the these candidate decisions to determine the final caching decision. We prove that the regret upper bound is sub-linear with respect to the time interval’s length <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\tau $ </tex-math></inline-formula>, i.e., <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\sqrt {\tau \log (\tau _{\max }/\tau _{\min })})$ </tex-math></inline-formula>. Our experiment results demonstrate that SAcache achieves the highest cache hit ratio and the lowest regret compared to other caching policies in non-stationary environments.