Article

Cooperative leases: scalable consistency maintenance in content distribution networks

Authors:

Purushottam Kulkarni,

Prashant Shenoy,

Krithi Ramamritham,

Renu TewariAuthors Info & Claims

WWW '02: Proceedings of the 11th international conference on World Wide Web

Pages 1 - 12

https://doi.org/10.1145/511446.511448

Published: 07 May 2002 Publication History

Abstract

In this paper, we argue that cache consistency mechanisms designed for stand-alone proxies do not scale to the large number of proxies in a content distribution network and are not flexible enough to allow consistency guarantees to be tailored to object needs. To meet the twin challenges of scalability and flexibility, we introduce the notion of cooperative consistency along with a mechanism, called cooperative leases, to achieve it. By supporting Δ-consistency semantics and by using a single lease for multiple proxies, cooperative leases allows the notion of leases to be applied in a flexible, scalable manner to CDNs. Further, the approach employs application-level multicast to propagate server notifications to proxies in a scalable manner. We implement our approach in the Apache web server and the Squid proxy cache and demonstrate its efficacy using a detailed experimental evaluation. Our results show a factor of 2.5 reduction in server message overhead and a 20% reduction in server state space overhead when compared to original leases albeit at an increased inter-proxy communication overhead.

References

[1]

L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web Caching and Zipf-like Distributions: Evidence and Implications. In Proceedings of Infocom'99, New York, NY, March 1999.

[2]

M. Busari and C. Williamson. On the Sensitivity of Web Proxy Cache Performance to Workload Characteristics. In Proceedings of IEEE Infocom'01, Anchorage, Alaska, April 2001.

[3]

P. Cao and C. Liu. Maintaining Strong Cache Consistency in the World-Wide Web. In Proceedings of the Seventeenth International Conference on Distributed Computing Systems, May 1997.

Digital Library

[4]

V. Cate. Alex: A Global File System. In Proceedings of the 1992 USENIX File System Workshop, pages 1--12, May 1992.

[5]

John Dilley, Martin Arlitt, Stephane Perret, and Tai Jin. The Distributed Object Consistency Protocol. Technical report, Hewlett-Packard Labs Technical Reports, 1999.

[6]

V. Duvvuri, P. Shenoy, and R. Tewari. Adaptive Leases: A Strong Consistency Mechanism for the World Wide Web. In Proceedings of the IEEE Infocom'00, Tel Aviv, Israel, March 2000.

[7]

L. Fan, P. Cao, J. Almeida, and A Z. Broder. Summary Cache: A Scalable Wide-area Web Cache Sharing Protocol. In Proceedings ACM SIGCOMM'98, Vancouver, BC, pages 254--265, September 1998.

Digital Library

[8]

Z. Fei. A Novel Approach to Managing Consistency in Content Distribution Networks. In Proceedings of the 6th Workshop on Web Caching and Content Distribution, Boston, MA, June 2001.

[9]

P. Francis. Yoid: Extending the Internet Multicast Architecture. Technical report, AT&T Center for Internet Research at ICSI (ACIRI), April 2000.

[10]

S. Gadde, J. Chase, and M. Rabinovich. Web Caching and Content Distribution: A View From the Interior. In Proceedings of the 5th International Web Caching and Content Delivery Workshop, 2000.

[11]

C. Gray and D. Cheriton. Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency. In Proceedings of the Twelfth ACM Symposium on Operating Systems Principles, pages 202--210, 1989.

Digital Library

[12]

M. Gritter and D. R. Cheriton. An Architecture for Content Routing Support in the Internet. In Proceedings of the USENIX Symposium on Internet Technologies, San Francisco, CA, March 2001.

Digital Library

[13]

J. Gwertzman and M. Seltzer. World-Wide Web Cache Consistency. In Proceedings of the 1996 USENIX Technical Conference, January 1996.

Digital Library

[14]

D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, and R. Panigrahy. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. In Proceedings of the Twenty-ninth ACM Symposium on Theory of Computing, 1997.

Digital Library

[15]

B. Krishnamurthy and C. Wills. Study of Piggyback Cache Validation for Proxy Caches in the WWW. In Proceedings of the 1997 USENIX Symposium on Internet Technology and Systems, Monterey, CA, pages 1--12, December 1997.

Digital Library

[16]

D. Li, P. Cao, and M. Dahlin. WCIP: Web Cache Invalidation Protocol. IETF Internet Draft, November 2000.

[17]

J. C. Mogul, F. Douglis, A. Feldmann, and B. Krishnamurthy. Potential Benefits of Delta Encoding and Data Compression for HTTP. In Proceedings of ACM SIGCOMM Conference, 1997.

Digital Library

[18]

A. Ninan. Maintaining Cache Consistency in Content Distribution Networks. Master's thesis, Department of Computer Science, Univ. of Massachusetts, June 2001.

[19]

R. Srinivasan, C. Liang, and K. Ramamritham. Maintaining Temporal Coherency of Virtual Warehouses. In Proceedings of the 19th IEEE Real-Time Systems Symposium (RTSS98), Madrid, Spain, December 1998.

Digital Library

[20]

R. Tewari, M. Dahlin, H. M. Vin, and J. Kay. Beyond Hierarchies: Design Considerations for Distributed Caching on the Internet. In Proceedings of the 19th International Conference on Distributed Computing Systems (ICDCS), June 1999.

Digital Library

[21]

B. Urgaonkar, A. Ninan, M. Raunak, P. Shenoy, and K. Ramamritham. Maintaining Mutual Consistency for Cached Web Objects. In Proceedings of the 21st International Conference on Distributed Computing Systems (ICDCS-21), Phoenix, AZ, pages 371--380, April 2001.

Digital Library

[22]

A. Venkataramani, P. Yalagandula, R. Kokku, S. Sharif, and M. Dahlin. Potential Costs and Benefits of Long-term Prefetching for Content Distribution. In Proceedings of the Web Caching Workshop, Boston, MA, June 2001.

[23]

J. Yin, L. Alvisi, M. Dahlin, and A. Iyengar. Engineering Server-driven Consistency for Large-scale Dynamic Web Services. In Proceedings of the 10th World Wide Web Conference, Hong Kong, May 2001.

Digital Library

[24]

J. Yin, L. Alvisi, M. Dahlin, and C. Lin. Volume Leases for Consistency in Large-Scale Systems. IEEE Transactions on Knowledge and Data Engineering, January 1999.

Digital Library

[25]

Jian Yin, Lorenzo Alvisi, Mike Dahlin, and Calvin Lin. Hierarchical Cache Consistency in a WAN. In Proceedings of the USENIX Symposium on Internet Technologies and Systems, Boulder, Colorado, October 1999.

Digital Library

[26]

H. Yu, L. Breslau, and S. Shenker. A Scalable Web Cache Consistency Architecture. In Proceedings of the ACM SIGCOMM'99, Boston, MA, September 1999.

Digital Library

Cited By

Liu GShen HChandler HLi J(2016)Measuring and Evaluating Live Content Consistency in a Large-Scale CDNIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2015.247922227:7(2074-2090)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1109/TPDS.2015.2479222
Kurian JSarac K(2010)A survey on the design, applications, and enhancements of application-layer overlay networksACM Computing Surveys10.1145/1824795.182480043:1(1-34)Online publication date: 3-Dec-2010
https://dl.acm.org/doi/10.1145/1824795.1824800
Roy MKar PMukherjee N(2010)Determining JINI leasing time limits using the random waypoint mobility model in mobile ad hoc networks2010 International Conference on Networking and Information Technology10.1109/ICNIT.2010.5508558(64-69)Online publication date: Jun-2010
https://doi.org/10.1109/ICNIT.2010.5508558
Show More Cited By

Index Terms

Cooperative leases: scalable consistency maintenance in content distribution networks

Recommendations

Scalable Consistency Maintenance in Content Distribution Networks Using Cooperative Leases

In this paper, we argue that cache consistency mechanisms designed for stand-alone proxies do not scale to the large number of proxies in a content distribution network and are not flexible enough to allow consistency guarantees to be tailored to object ...
Adaptive Push-Pull: Disseminating Dynamic Web Data

An important issue in the dissemination of time-varying web data such as sports scores and stock prices is the maintenance of temporal coherency. In the case of servers adhering to the HTTP protocol, clients need to frequently pull the data based on the ...
Adaptive Leases: A Strong Consistency Mechanism for the World Wide Web

In this paper, we argue that weak cache consistency mechanisms supported by existing Web proxy caches must be augmented by strong consistency mechanisms to support the growing diversity in application requirements. Existing strong consistency mechanisms ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '02: Proceedings of the 11th international conference on World Wide Web

May 2002

754 pages

ISBN:1581134495

DOI:10.1145/511446

Conference Chairs:
David Lassner
University of Hawaii
,
Dave De Roure
University of Southampton
,
Arun Iyengar
IBM T.J. Watson Research Center

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 May 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

WWW02

Sponsor:

ACM

WWW02: Hypermedia Track of the Eleventh International World-Wide Web Conference

May 7 - 11, 2002

Hawaii, Honolulu, USA

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
740
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu GShen HChandler HLi J(2016)Measuring and Evaluating Live Content Consistency in a Large-Scale CDNIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2015.247922227:7(2074-2090)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1109/TPDS.2015.2479222
Kurian JSarac K(2010)A survey on the design, applications, and enhancements of application-layer overlay networksACM Computing Surveys10.1145/1824795.182480043:1(1-34)Online publication date: 3-Dec-2010
https://dl.acm.org/doi/10.1145/1824795.1824800
Roy MKar PMukherjee N(2010)Determining JINI leasing time limits using the random waypoint mobility model in mobile ad hoc networks2010 International Conference on Networking and Information Technology10.1109/ICNIT.2010.5508558(64-69)Online publication date: Jun-2010
https://doi.org/10.1109/ICNIT.2010.5508558
Goldberg D(2009)State considerations in distributed systemsXRDS: Crossroads, The ACM Magazine for Students10.1145/1525902.152590515:3(7-11)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1145/1525902.1525905
Chi CChua CSong W(2008)A novel ownership scheme to maintain web content consistencyProceedings of the 3rd international conference on Advances in grid and pervasive computing10.5555/1788754.1788795(352-363)Online publication date: 25-May-2008
https://dl.acm.org/doi/10.5555/1788754.1788795
Chang TZhuang ZVelayutham ASivakumar R(2008)WebAccelComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2008.02.00752:11(2129-2147)Online publication date: 1-Aug-2008
https://dl.acm.org/doi/10.1016/j.comnet.2008.02.007
Stamos KPallis GVakali A(2008)Caching Techniques on CDN Simulated FrameworksContent Delivery Networks10.1007/978-3-540-77887-5_5(127-153)Online publication date: 2008
https://doi.org/10.1007/978-3-540-77887-5_5
Chi CChua CSong W(2008)A Novel Ownership Scheme to Maintain Web Content ConsistencyAdvances in Grid and Pervasive Computing10.1007/978-3-540-68083-3_35(352-363)Online publication date: 2008
https://doi.org/10.1007/978-3-540-68083-3_35
Cai QLiberatore VGabow H(2007)Layered multicast scheduling for the L∞ objectiveProceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1283383.1283471(824-833)Online publication date: 7-Jan-2007
https://dl.acm.org/doi/10.5555/1283383.1283471
Hossein Sheikh Attar MTamer Özsu M(2006)Alternative Architectures and Protocols for Providing Strong Consistency in Dynamic Web ApplicationsWorld Wide Web10.1007/s11280-006-8563-19:3(215-251)Online publication date: 1-Oct-2006
https://dl.acm.org/doi/10.1007/s11280-006-8563-1
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents