Camul: Online Caching on Multiple Caches with Relaying and Bypassing

Haisheng Tan, Shaofeng H.C. Jiang, Zhenhua Han*, Liuyan Liu, Kai Han, Qinglin Zhao

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

7 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 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.

Original languageEnglish
Title of host publicationINFOCOM 2019 - IEEE Conference on Computer Communications
Number of pages9
ISBN (Electronic)9781728105154
Publication statusPublished - Apr 2019
MoE publication typeA4 Article in a conference publication
EventIEEE Conference on Computer Communications - Paris, France
Duration: 29 Apr 20192 May 2019
Conference number: 38

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


ConferenceIEEE Conference on Computer Communications
Abbreviated titleINFOCOM


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

Cite this