Asymptotically Optimal Online Caching on Multiple Caches with Relaying and Bypassing

Haisheng Tan*, Shaofeng H.C. Jiang, Zhenhua Han, Mingxia Li

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)


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 can also choose to fetch files from the memory to caches and conduct file replacement if necessary. 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 costs. We propose an $O(\log {K})$ -competitive randomized online multiple caching algorithm (named Camul) and an $O(K)$ -competitive deterministic algorithm (named Camul-Det), where $K$ is the total number of slots in all caches. Both of them achieve asymptotically optimal competitive ratios. Moreover, our algorithms 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 state-of-the-art 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 performs consistently well on various settings of experiment parameters.

Original languageEnglish
Article number9426958
Pages (from-to)1841-1852
Number of pages12
JournalIEEE/ACM Transactions on Networking
Issue number4
Publication statusPublished - Aug 2021
MoE publication typeA1 Journal article-refereed


  • edge computing
  • online algorithm
  • Online caching


Dive into the research topics of 'Asymptotically Optimal Online Caching on Multiple Caches with Relaying and Bypassing'. Together they form a unique fingerprint.

Cite this