research-article

DR-Cache: Distributed Resilient Caching with Latency Guarantees

Authors:

Truong Khoa Phan,

Wei Koong Chai,

Miguel RioAuthors Info & Claims

IEEE INFOCOM 2018 - IEEE Conference on Computer Communications

Pages 441 - 449

https://doi.org/10.1109/INFOCOM.2018.8486316

Published: 16 April 2018 Publication History

Abstract

The dominant application in today's Internet is content streaming, which is increasingly relying on caches to meet the stringent conditions on the latency between content servers and end-users. These systems routinely face the challenges of limited bandwidth capacities and network server failures, which degrade caching performance. In this paper, we study the problem of optimally allocating content over a resilient caching network, in which each cache may fail under some situations. Given content request rates and multiple routing paths, we formulate an optimization problem to maximize the expected caching gain, i.e., the reduction of latency due to intermediate caching. The offline version of this problem is NP-hard. We first propose a centralized, offline algorithm and show that a solution with (1-1/e) approximation ratio to the optimal can be constructed. We then propose a distributed ascent algorithm based on the concave relaxation of the expected gain. Informed by the results of our analysis, we finally propose a distributed resilient caching algorithm (DR-Cache) that is simple and adaptive to network failures. We show numerically that DR-Cache significantly outperforms other candidate algorithms under synthetic requests, as well as real world traces over a class of network topologies.

References

[1]

http://www.networkcomputing.com/networking/high-price-it-downtime/856595126

[2]

D. Applegate, A. Archer, V. Gopalakrishnan, S. Lee, and K. K. Ramakrishnan. Optimal Content Placement for a Large-Scale VoD System. IEEE/ACM Transactions on Networking, 24: 2114–2127, 2016.

Digital Library

[3]

I. Baev, R. Rajaraman, and C. Swamy. Approximation Algorithms for Data Placement Problems. SIAM Jour. Comp., 38 (4): 1411–1429, 2008.

Digital Library

[4]

G. Bianchi, A. Detti, A. Caponi, and N. Blefari Melazzi. Check before Storing: What is the Performance Price of Content Integrity Verification in LRU Caching? ACM SIGCOMM CCR, 2013.

[5]

S. Borst, V. Gupta, and A. Walid. Distributed Caching Algorithms for Content Distribution Networks. In IEEE INFOCOM, 2010.

[6]

W. K. Chai, V. Sourlas, and G. Pavlou. Providing Information Resilience Through Modularity-based Caching in Perturbed Information-centric Networks. In IEEE/ACM International Teletraffic Congress, 2017.

[7]

H. Che, Y. Tung, and Z. Wang. Hierarchical Web Caching Systems: Modeling, Design and Experimental Results. Selected Areas in Communications. IEEE Journal on. 20 (7): 1305–1314. 2002.

Digital Library

[8]

C. Chekuri, J. Vondrak, and R. Zenklusen. Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures. In IEEE FOCS, 2010.

[9]

E. Cohen and S. Shenker. Replication Strategies in Unstructured Peer-to-Peer Networks. In ACM SIGCOMM, 2002.

[10]

M. Dehghan, A. Seetharam, B. Jiang, T. He, T. Salonidis, J. Kurose, D. Towsley, and R. Sitaraman. On the Complexity of Optimal Routing and Content Caching in Heterogeneous Networks. In IEEE INFOCOM, 2015.

[11]

S. Ghemawat, H. Gobioff, and S.-T. Leung. The Google File System. In ACM SIGOPS Operating Systems Review, 2003.

[12]

P. Gill, N. Jain, and N. Nagappan Understanding Network Failures in Data Centers: Measurement, Analysis, and Implications. In ACM SIGCOMM. 2011.

[13]

N. Golrezaei, K. Shanmugam, A. G. Dimakis, A. F. Molisch, and G. Caire. Femtocaching: Wireless Video Content Delivery Through Distributed Caching Helpers. In IEEE INFOCOM, 2012.

[14]

I. Hou, T. Zhao, S. Wang, and K. Chan. Asymptotically Optimal Algorithm for Online Reconfiguration of Edge-Clouds. In ACM MobiHoc, 2016.

[15]

S. Ioannidis and E. Yeh. Adaptive Caching Networks with Optimality Guarantees. In ACM SIGMETRICS, 2016.

[16]

V. Jacobson, D. K. Smetters, J. D. Thornton, M. F. Plass, N. H. Briggs, and R. L. Bravnard. Networking Named Content. In CoNEXT. 2009.

[17]

J. Li, S. Shakkottai, J. C. S. Lui, and V. Subramanian. Accurate Learning or Fast Mixing? Dynamic Adaptability of Caching Algorithms. Arxiv nrenrint arXiv:. 2017.

[18]

A. Markopoulou, G. Iannaccone, S. Bhattacharyya, C. Chuah, Y. Ganjali, and C. Diot. Characterization of Failures in an Operational IP Backbone Network. IEEE/ACM Transactions on Networking, 16: 749–762, 2008.

Digital Library

[19]

N. K. Panigrahy, J. Li, and D. Towsley. Hit rate vs. hit probability based cache utility maximization. In ACM MAMA, 2017.

[20]

N. K. Panigrahy, J. Li, and D. Towsley. Network Cache Design under Stationary Requests: Challenges, Algorithms and Experiments. Arxiv preprint arXiv:. 2017.

[21]

N. K. Panigrahy, J. Li, F. Zafari, D. Towsley, and P. Yu. What, When and Where to Cache: A Unified Optimization Approach. Arxiv preprint arXiv:, 2017.

[22]

T. K. Phan, D. Griffin, E. Maini, and M. Rio. Utility-maximizing Server Selection. In IFIP Networking, 2016.

[23]

T. K. Phan, D. Griffin, E. Maini, and M. Rio. Utility-centric Networking: Balancing Transit Costs with Quality of Experience. IEEE/ACM Transactions on Networking, 2018.

[24]

E. J. Rosensweig, D. S. Menasche, and J. Kurose. On the Steady-State of Cache Networks. In IEEE INFOCOM, 2013.

[25]

S. Saroiu, K. P. Gummadi, R. J. Dunn, S. D. Gribble, and H. M. Levy. An Analysis of Internet Content Delivery Systems. ACM SIGOPS. 2002.

[26]

L. Tong, Y. Li, and W. Gao. A Hierarchical Edge Cloud Architecture for Mobile Computing. In IEEE INFOCOM, 2016.

[27]

R. Van Renesse and F. B. Schneider. Chain Replication for Supporting High Throughput and Availability. In OSDI, 2004.

[28]

L. Wang, S. Bayhan, J. Ott, J. Kangasharju, S. A., and J. Crowcroft. Pro-Diluvian: Understanding Scoped-Flooding for Content Discovery in Information-Centric Networking. In ACM ICN, 2015.

Cited By

Li YSi Salem TNeglia GIoannidis S(2021)Online Caching Networks with Adversarial GuaranteesProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34910475:3(1-39)Online publication date: 15-Dec-2021
https://dl.acm.org/doi/10.1145/3491047
Wu QSun PHong XZhu XLiu B(2021)An Android Malware Detection and Malicious Code Location Method Based on Graph Neural NetworkProceedings of the 2021 4th International Conference on Machine Learning and Machine Intelligence10.1145/3490725.3490733(50-56)Online publication date: 17-Sep-2021
https://dl.acm.org/doi/10.1145/3490725.3490733

Index Terms

DR-Cache: Distributed Resilient Caching with Latency Guarantees
1. General and reference

Index terms have been assigned to the content through auto-classification.

Recommendations

Reducing Latency in an SRAM/DRAM Cache Hierarchy via a Novel Tag-Cache Architecture
DAC '14: Proceedings of the 51st Annual Design Automation Conference

Memory speed has become a major performance bottleneck as more and more cores are integrated on a multi-core chip. The widening latency gap between high speed cores and memory has led to the evolution of multi-level SRAM/DRAM cache hierarchies that ...
Selective Victim Caching: A Method to Improve the Performance of Direct-Mapped Caches

Although direct-mapped caches suffer from higher miss ratios as compared to set-associative caches, they are attractive for today's high-speed pipelined processors that require very low access times. Victim caching was proposed by Jouppi [1] as an ...
Location cache: a low-power L2 cache system
ISLPED '04: Proceedings of the 2004 international symposium on Low power electronics and design

While set-associative caches incur fewer misses than direct-mapped caches, they typically have slower hit times and higher power consumption, when multiple tag and data banks are probed in parallel. This paper presents the location cache structure which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

IEEE INFOCOM 2018 - IEEE Conference on Computer Communications

Apr 2018

2776 pages

Copyright © 2018.

Publisher

IEEE Press

Publication History

Published: 16 April 2018

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li YSi Salem TNeglia GIoannidis S(2021)Online Caching Networks with Adversarial GuaranteesProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34910475:3(1-39)Online publication date: 15-Dec-2021
https://dl.acm.org/doi/10.1145/3491047
Wu QSun PHong XZhu XLiu B(2021)An Android Malware Detection and Malicious Code Location Method Based on Graph Neural NetworkProceedings of the 2021 4th International Conference on Machine Learning and Machine Intelligence10.1145/3490725.3490733(50-56)Online publication date: 17-Sep-2021
https://dl.acm.org/doi/10.1145/3490725.3490733

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents