SwiftOGA: An Efficient and Swift Online Gradient Ascent Algorithm for Caching Replacement
Bin Dong, Tian Song, Qianyu Zhang · 2024
Content caching plays a crucial role in improving the efficient retrieval of content and enabling fast delivery to enhance the quality of service (QoS). Traditional caching replacement policies (e.g., LRU, LFU) usually depend on historical request patterns to decide which content to store. However, they struggle to handle adversarial request patterns and dynamically changing popular content. Online learning caching policies (e.g., OGA) are resilient to different request patterns and can be applied in intricate network environments to address the caching replacement problem. Nevertheless, these policies tend to become more computationally intensive over time due to the increasing amount of content, leading to higher computing consumption. Motivated by this, we propose SwiftOGA, an efficient and swift online gradient ascent algorithm for cache replacement. Compared to previous online learning caching policies, our proposal achieves a reduction in computational overhead of at least 74.9%. Furthermore, it exhibits a cache hit ratio improvement of 8.3% over OGA under a dynamic request pattern. We also demonstrate that the proposed policy still has sub-linear regret.