Camul: Online Caching on Multiple Caches with Relaying and Bypassing

Motivated by practical scenarios in areas such as Mobile Edge Computing (MEC) and Content Delivery Networks (CDNs), we study online file caching on multiple caches, where a file request might be relayed to other caches or bypassed directly to the memory when a cache miss happens. We take the relaying, bypassing and fetching costs altogether into consideration. We first show the inherent difficulty of the problem even when the online requests are of uniform cost. We propose an O(log K)-competitive randomized algorithm Camul and an O(K)-competitive deterministic algorithm Camul-Det, where K is the total number of slots in all caches. Both online algorithms achieve asymptotically optimal competitive ratios, and can be implemented efficiently such that each request is processed in amortized constant time. We conduct extensive simulations on production data traces from Google and a benchmark workload from Yahoo. It shows that our algorithms dramatically outperform existing schemes, i.e., reducing the total cost by 85% and 43% respectively compared with important baselines and their strengthened versions with request relaying. More importantly, Camul achieves such a good total cost without sacrificing other performance measures, e.g., the hit ratio, and can perform consistently well on various settings of experiment parameters.