Caching Performance Under Constraints on Cache Updates

Abstract

Caching is a fundamental component of content delivery systems such as cloud services and edge networks. Most existing analytical studies of caching assume that the cache can be updated after every file request; however, this assumption is impractical in real systems due to computational constraints. In this paper, we study an online caching framework in which cache updates occur only at prescribed intervals, resulting in bunched request arrivals between successive updates. We analyze the performance of the Follow-The-Perturbed-Leader (FTPL) algorithm under such constraints while incorporating computation cost into the regret metric. For various combinations of adversarial and stochastic request and arrival processes, we derive upper bounds on regret as a function of the cache update frequency. Our results show that both the regret and the total computation cost can be made sublinear in the time horizon with appropriately chosen update intervals. In particular, significantly tighter bounds are obtained when arrivals follow stochastic processes such as the Poisson distribution.