research-article

Proactive Cache Placement on Cooperative Client Caches for Online Social Networks

Authors:

Stavros Nikolaou,

Robbert Van Renesse,

Nicolas SchiperAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 27, Issue 4

Pages 1174 - 1186

https://doi.org/10.1109/TPDS.2015.2425398

Published: 01 April 2016 Publication History

Abstract

This paper investigates cache placement on a cooperative cache built from individual client caches in an online social network or web service. We use a service that maintains a mapping between content and the clients that cache it, and propose cache placement schemes that leverage relationships between clients (for example, social links) and workload statistics, proactively placing content on clients that are likely to access it. We evaluate efficacy through simulation, comparing our schemes against commonly used cache placement algorithms as well as optimal placement. We synthesize a workload to match characteristics of online social networks. Simulation results of our proposed caching schemes impose moderate network overhead and show considerable improvement to the client's cache hit ratio, even under churn.

References

[1]

S. Iyer, A. Rowstron, and P. Druschel, “Squirrel: A decentralized peer-to-peer web cache,” in Proc. 21st Annu. Symp. Principles Distrib. Comput., 2002, pp. 213–222.

[2]

L. Zhang, F. Zhou, A. Mislove, and R. Sundaram, “Maygh: Building a CDN from client web browsers,” in Proc. 8th ACM Eur. Conf. Comput. Syst., 2013, pp. 281–294.

[3]

T. Stading, P. Maniatis, and M. Baker, “Peer-to-peer caching schemes to address flash crowds,” in Proc. Revised Papers 1st Int. Workshop Peer-to-Peer Syst., 2002, pp. 203–213.

Digital Library

[4]

S. Nikolaou, R. van Renesse, and N. Schiper, “ Cooperative client caching strategies for social and web applications,” presented at the Large-Scale Distributed Systems and Middleware, Farmington, PA, USA, Nov. 2013.

[5]

L. Ramaswamy, L. Liu, and A. Iyengar, “Cache clouds: Cooperative caching of dynamic documents in edge networks,” in Proc. 25th IEEE Int. Conf. Distrib. Comput. Syst., 2005, pp. 229–238.

[6]

B. Atikoglu, Y. Xu, E. Frachtenberg, S. Jiang, and M. Paleczny, “Workload analysis of a large-scale key-value store, ” in Proc. 12th ACM Sigmetrics/Perform. Joint Int. Conf. Meas. Model. Comput. Syst., 2012, pp. 53–64.

Digital Library

[7]

A. Sala, L. Cao, C. Wilson, R. Zablit, H. Zheng, and B. Y. Zhao, “Measurement-calibrated graph models for social network experiments,” in Proc. 19th Int. Conf. World Wide Web, 2010, pp. 861–870.

Digital Library

[8]

F. Benevenuto, T. Rodrigues, M. Cha, and V. Almeida, “Characterizing user behavior in online social networks,” in Proc. 9th ACM SIGCOMM Conf. Internet Meas. Conf., 2009, pp. 49–62.

Digital Library

[9]

N. Megiddo and D. S. Modha, “ARC: A self-tuning, low overhead replacement cache,” in Proc. 2nd USENIX Conf. File Storage Technol., 2003, pp. 115–130.

Digital Library

[10]

R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM, vol. 21, no. 2, pp. 120–126, Feb. 1978.

Digital Library

[11]

L. A. Belady, “A study of replacement algorithms for virtual storage, ” IBM Syst. J., vol. 5, pp. 78–101, 1966.

Digital Library

[12]

Q. Huang, K. Birman, R. van Renesse, W. Lloyd, S. Kumar, and H. C. Li, “An analysis of facebook photo caching,” in Proc. 24th ACM Symp. Operating Syst. Principles, 2013, pp. 167–181.

[13]

J. Leskovec, J. Kleinberg, and C. Faloutsos, “Graphs over time: Densification laws, shrinking diameters and possible explanations,” in Proc. 11th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2005, pp. 177– 187.

[14]

M. E. J. Newman, S. H. Strogatz, and D. J. Watts, “ Random graphs with arbitrary degree distributions and their applications,” Phys. Rev. E, vol. 64, no. 2, p. 026118, Jul. 2001.

[15]

D. Chakrabarti and C. Faloutsos, “Graph mining: Laws, generators, and algorithms,” ACM Comput. Surv., vol. 38, no. 1, Jun. 2006.

[16]

[Online] Available: http://snap.stanford.edu/data/, Jun. 2014.

[17]

[Online] Available: http://www.w3schools.com/html/html5_webstorage.asp, 2015.

[18]

H. Geng and R. Renesse, “Sprinkler—reliable broadcast for geographically dispersed datacenters, ” in Proc. ACM/IFIP/USENIX 14th Int. Middleware Conf., 2013, vol. 8275, pp. 247–266.

[19]

A. Wolman, M. Voelker, N. Sharma, N. Cardwell, A. Karlin, and H. M. Levy, “On the scale and performance of cooperative web proxy caching,” in Proc. 17th ACM Symp. Operating Syst. Principles, 1999, pp. 16–31.

[20]

J. Wang, “A survey of web caching schemes for the Internet, ” SIGCOMM Comput. Commun. Rev., vol. 29, no. 5, pp. 36 –46, Oct. 1999.

Digital Library

[21]

S. Annapureddy, M. J. Freedman, and D. Mazières, “ Shark: scaling file servers via cooperative caching,” in Proc. 2nd Conf. Symp. Netw. Syst. Design Implementation, 2005, pp. 129–142.

[22]

L. Qiu, V. Padmanabhan, and G. Voelker, “On the placement of web server replicas,” in Proc. IEEE Comput. Commun. Soc. 20th Annu. Joint Conf., 2001, vol. 3, pp. 1587–1596.

[23]

B. Li, M. Golin, G. Italiano, X. Deng, and K. Sohraby, “On the optimal placement of web proxies in the Internet,” in Proc. IEEE Comput. Commun. Soc. 18th Annu. Joint Conf., 1999, vol. 3, pp. 1282–1290.

[24]

S. Borst, V. Gupta, and A. Walid, “Distributed caching algorithms for content distribution networks,” in Proc. 29th Conf. Inform. Commun., 2010, pp. 1478–1486.

Digital Library

[25]

K. Ranganathan and I. T. Foster, “Identifying dynamic replication strategies for a high-performance data grid, ” in Proc. 2nd Int. Workshop Grid Comput., 2001, pp. 75– 86.

[26]

D. A. Tran, K. Nguyen, and C. Pham. (2012). S-clone: Socially-aware data replication for social networks. Comput. Netw. [Online]. 56(7), pp. 2001–2013. Available: http://www.sciencedirect.com/science/article/pii/S1389128612000746

Cited By

Aldailamy AMuhammed ALatip RHamid NIsmail W(2024)Online dynamic replication and placement algorithms for cost optimization of online social networks in two-tier multi-cloudJournal of Network and Computer Applications10.1016/j.jnca.2024.103827224:COnline publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1016/j.jnca.2024.103827
Qiao DGuo SLiu DLong SZhou PLi Z(2022)Adaptive Federated Deep Reinforcement Learning for Proactive Content Caching in Edge ComputingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.320198333:12(4767-4782)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1109/TPDS.2022.3201983
Chen TGao XLiao TChen G(2020)Pache: A Packet Management Scheme of Cache in Data Center NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2019.293190531:2(253-265)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1109/TPDS.2019.2931905
Show More Cited By

Index Terms

Proactive Cache Placement on Cooperative Client Caches for Online Social Networks

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

Recommendations

Exploiting client caches to build large Web caches

New demands brought by the continuing growth of the Internet will be met in part by more effective and comprehensive use of caching. This paper proposes to exploit client browser caches in the context of cooperative proxy caching by constructing the ...
A graph theoretic approach to cache-conscious placement of data for direct mapped caches
ISMM '10: Proceedings of the 2010 international symposium on Memory management

Caches were designed to amortize the cost of memory accesses by moving copies of frequently accessed data closer to the processor. Over the years the increasing gap between processor speed and memory access latency has made the cache a bottleneck for ...
Reducing Cache Miss Rates Using Prediction Caches

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 27, Issue 4

April 2016

312 pages

ISSN:1045-9219

Issue’s Table of Contents

Copyright © 2015.

Publisher

IEEE Press

Publication History

Published: 01 April 2016

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Aldailamy AMuhammed ALatip RHamid NIsmail W(2024)Online dynamic replication and placement algorithms for cost optimization of online social networks in two-tier multi-cloudJournal of Network and Computer Applications10.1016/j.jnca.2024.103827224:COnline publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1016/j.jnca.2024.103827
Qiao DGuo SLiu DLong SZhou PLi Z(2022)Adaptive Federated Deep Reinforcement Learning for Proactive Content Caching in Edge ComputingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.320198333:12(4767-4782)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1109/TPDS.2022.3201983
Chen TGao XLiao TChen G(2020)Pache: A Packet Management Scheme of Cache in Data Center NetworksIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2019.293190531:2(253-265)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1109/TPDS.2019.2931905
Zhou KSun SWang HHuang PHe XLan RLi WLiu WYang T(2019)Improving Cache Performance for Large-Scale Photo Stores via Heuristic Prefetching SchemeIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2019.290239230:9(2033-2045)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1109/TPDS.2019.2902392
Li CZhang JTang H(2019)Replica-aware task scheduling and load balanced cache placement for delay reduction in multi-cloud environmentThe Journal of Supercomputing10.1007/s11227-018-2695-975:5(2805-2836)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s11227-018-2695-9
Zhou KSun SWang HHuang PHe XLan RLi WLiu WYang T(2018)Demystifying Cache Policies for Photo Stores at ScaleProceedings of the 2018 International Conference on Supercomputing10.1145/3205289.3205299(284-294)Online publication date: 12-Jun-2018
https://dl.acm.org/doi/10.1145/3205289.3205299
Liu JWang XYue GShen S(2018)Data sharing in VANETs based on evolutionary fuzzy gameFuture Generation Computer Systems10.1016/j.future.2017.10.03781:C(141-155)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1016/j.future.2017.10.037
Machado KBoukerche ACerqueira ELoureiro A(2017)A Socially-Aware In-Network Caching Framework for the Next Generation of Wireless NetworksIEEE Communications Magazine10.1109/MCOM.2017.170024455:12(38-43)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1109/MCOM.2017.1700244

View Options

View options

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 Issue’s Table of Contents