Camul: Online Caching on Multiple Caches with Relaying and Bypassing

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

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

4 Sitaatiot (Scopus)

Abstrakti

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.

AlkuperäiskieliEnglanti
OtsikkoINFOCOM 2019 - IEEE Conference on Computer Communications
KustantajaIEEE
Sivut244-252
Sivumäärä9
ISBN (elektroninen)9781728105154
DOI - pysyväislinkit
TilaJulkaistu - huhtikuuta 2019
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaIEEE Conference on Computer Communications - Paris, Ranska
Kesto: 29 huhtikuuta 20192 toukokuuta 2019
Konferenssinumero: 38

Julkaisusarja

NimiProceedings - IEEE INFOCOM
Vuosikerta2019-April
ISSN (painettu)0743-166X

Conference

ConferenceIEEE Conference on Computer Communications
LyhennettäINFOCOM
MaaRanska
KaupunkiParis
Ajanjakso29/04/201902/05/2019

Sormenjälki Sukella tutkimusaiheisiin 'Camul: Online Caching on Multiple Caches with Relaying and Bypassing'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä