Optimal Caching for Dynamic Content Through Strategic Information Sharing

Abstract

We study how to update cache content to efficiently serve demands for dynamic data items that are frequently refreshed at backend servers. A significant challenge for optimizing this new type of cache systems with dynamic content is the following "information barrier". Because the precise data refresh events happening at the backend are not known to the cache, it is difficult for the cache to decide how to update cache content effectively. To overcome this information barrier, we introduce a new model that allows caches to observe data-item freshness at backend servers occasionally by paying an observation cost. A caching optimization problem is then formulated, aiming at strategically utilizing the observation option to balance the trade-off between providing fresh content and reducing data traffic to the backend. Although this optimization problem can be cast as a multi-action Restless Multi-Armed Bandit (RMAB) problem, it unfortunately does not satisfy the standard notion of multi-action indexability, preventing the use of standard Whittle index policies. We address this difficulty by introducing two new concepts of super-action indexability and sub-action indexability. These new notions of indexability significantly generalize the classical notion of multi-action indexability, and they enable us to develop low-complexity and asymptotically-optimal index-like policies for this otherwise intractable problem. Extensive numerical simulations verify that the proposed new policies benefit from more informed decision-making through strategic observation and significantly outperform existing benchmarks that do not exploit observation opportunities.