A survey of Web cache replacement strategies
ACM Computing SurveysPublished 1 December 2003
Stefan Podlipnig, László Böszörményi
Citations754
SJR quartileQ1
SJR score5.80
SNIP11.03
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This article proposes a classification for proposals for cache replacement that subsumes prior classifications and discusses the importance of cache replacement strategies in modern proxy caches and outlines potential future research topics.
Abstract
Web caching is an important technique to scale the Internet. One important performance factor of Web caches is the replacement strategy. Due to specific characteristics of the World Wide Web, there exist a huge number of proposals for cache replacement. This article proposes a classification for these proposals that subsumes prior classifications. Using this classification, different proposals and their advantages and disadvantages are described. Furthermore, the article discusses the importance of cache replacement strategies in modern proxy caches and outlines potential future research topics.
Keywords
Computer ScienceMaterials Science
Web caching and Zipf-like distributions: evidence and implications
3,486 Citations1999Lee Breslau, Pei Cao +3 more
This paper investigates the page request distribution seen by Web proxy caches using traces from a variety of sources and considers a simple model where the Web accesses are independent and the reference probability of the documents follows a Zipf-like distribution, suggesting that the various observed properties of hit-ratios and temporal locality are indeed inherent to Web accesse observed by proxies.
Minds at UW (University of Wisconsin)Cost-aware WWW proxy caching algorithms
919 Citations1997Pei Cao, Sandy Irani
ACM SIGCOMM Computer Communication ReviewA survey of web caching schemes for the Internet
683 Citations1999Jia Wang
This paper first describes the elements of a Web caching system and its desirable properties, then the state-of-art techniques which have been used in Web caching systems are surveyed, and the research frontier in Web cache is discussed.
Proxy prefix caching for multimedia streams
512 Citations1999Subhabrata Sen, Jennifer Rexford +1 more
This work proposes a prefix caching technique whereby a proxy stores the initial frames of popular clips, and describes how to construct a smooth transmission schedule, based on the size of the prefix, smoothing, and playback buffers, without increasing client playback delay.
Characterizing reference locality in the WWW
465 Citations2002Virgı́lio Almeida, Azer Bestavros +2 more
The authors propose models for both temporal and spatial locality of reference in streams of requests arriving at Web servers and show that temporal locality can be characterized by the marginal distribution of the stack distance trace, and proposed models for typical distributions and compare their cache performance to the traces.
Caching Proxies: Limitations and Potentials
445 Citations1995Marc Abrams, Charles R. Standridge +3 more
This work assesses the potential of proxy servers to cache documents retrieved with the HTTP, GOPHER, FTP, and WAIS protocols using World Wide Web browsers to find that with workloads over a one-semester period, a proxy has a 30--50% maximum possible hit rate.
Removal policies in network caches for World-Wide Web documents
437 Citations1996Marc Abrams, Charles R. Standridge +3 more
Surprisingly, the criteria used by several proxy-server removal policies are among the worst performing criteria in the authors' simulation; instead, replacing documents based on size maximizes hit rate in each of the studied workloads.
World Wide WebChanges in Web client access patterns: Characteristics and caching implications
377 Citations1999Paul Barford, Azer Bestavros +2 more
This study compares two measurements of Web client workloads separated in time by three years, both captured from the same computing facility at Boston University and finds that for the computing facility represented by traces between 1995 and 1998, the benefits of using size‐based caching policies have diminished and the potential for caching requested files in the network has declined.
IEEE Transactions on Knowledge and Data EngineeringCaching on the World Wide Web
352 Citations1999Charų C. Aggarwal, Joel L. Wolf +1 more
This paper gives an overview of caching policies designed specifically for Web objects and provides a new algorithm of their own, regarded as a generalization of the standard LRU algorithm.
CERN Document Server (European Organization for Nuclear Research)Web Caching and Replication
345 Citations2001Michael Rabinovich, Oliver Spatschek
This comprehensive examination of caching, replication, and load-balacing practices for the Web brings together information from and for the commercial world, including real-life products; technical standards communities, such as IETF and W3C; and academic research.
IEEE Communications MagazineWorld Wide Web caching: trends and techniques
339 Citations2000Greg Barish, K. Obraczka
The state of the art in caching designs is surveyed, presenting a taxonomy of architectures and describing a variety of specific trends and techniques.
IEEE/ACM Transactions on NetworkingReplacement policies for a proxy cache
306 Citations2000Luigi Rizzo, L. Vicisano
This paper proposes a novel replacement policy, called LRV, which selects for replacement the document with the lowest relative value among those in cache, and shows how LRV outperforms least recently used (LRU) and other policies and can significantly improve the performance of the cache, especially for a small one.
On the existence of a spectrum of policies that subsumes the least recently used (LRU) and least frequently used (LFU) policies
274 Citations1999Donghee Lee, Jongmoo Choi +5 more
The L RFU policy is applied to buffer caching, and results from trace-driven simulations show that the LRFU performs better than previously known policies for the workloads the authors considered.
ACM SIGMETRICS Performance Evaluation ReviewEvaluating content management techniques for Web proxy caches
270 Citations2000Martin Arlitt, Ludmila Cherkasova +3 more
A trace of client requests to a busy Web proxy in an ISP environment is utilized to evaluate the performance of several existing replacement policies and of two new, parameterless replacement policies that are introduced in this paper.
Segment-based proxy caching of multimedia streams
223 Citations2001Kun‐Lung Wu, Philip S. Yu +1 more
This paper presents and evaluates a segment-based management approach to proxy caching of large media streams, and shows that segment- based caching is especially advantageous when the cache size is limited, when the set of hot media objects changes over time, and when the media size is large.
Rules of thumb in data engineering
192 Citations2000Jodi Gray, Prashant Shenoy
The rules of thumb for the design of data storage systems are reexamines with a particular focus on performance and price/performance, and the 5-minute rule for disk caching becomes a cache-everything rule for Web caching.
Computer Networks and ISDN SystemsProxy caching that estimates page load delays
190 Citations1997Roland Peter Wooster, Marc Abrams
Two new caching algorithms that keep in the cache documents that take the longest to retrieve are explored, and are compared to the best three existing policies—LRU, LFU, and SIZE—using three measures-user response time and ability to minimize Web server loads and network bandwidth consumed.
IEEE/ACM Transactions on NetworkingVideo staging: a proxy-server-based approach to end-to-end video delivery over wide-area networks
164 Citations2000Zhi-Li Zhang, Yuewei Wang +2 more
The results demonstrate that the proposed proxy-server-based approach provides an effective and scalable solution to the problem of the end-to-end video delivery over WANs.
Computer CommunicationsGreedyDual∗ Web caching algorithm: exploiting the two sources of temporal locality in Web request streams
158 Citations2001Shengwei Jin, Azer Bestavros
A novel cache replacement algorithm, GreedyDual^*, is proposed, which is a generalization ofGreedyDual-Size and shows the superior performance of Greedy dual-Size when compared to other Web cache replacement policies proposed in the literature.
Web Caching
146 Citations2001Duane Wessels, Nathan Torkington
Internet service providers, large corporations, or educational institutionsin short, any network that provides connectivity to a wide variety of userscan reap enormous benefit from running a well-tuned web caching service.
IEEE Transactions on Knowledge and Data EngineeringCoordinated placement and replacement for large-scale distributed caches
133 Citations2002Madhukar Korupolu, Michael Dahlin
IEEE Transactions on ComputersDistributing layered encoded video through caches
129 Citations2002Jussi Kangasharju, Felix Hartanto +2 more
IEEE Internet ComputingA Web caching primer
118 Citations2001Brian D. Davison
The article provides a primer on Web resource caching, one technology used to make the Web scalable and a high-level argument for the value of Web caching to content consumers and producers.
Differentiated caching services; a control-theoretical approach
116 Citations2002Ying Lü, A. Saxena +1 more
An architecture for differentiated content caching services as a key element of the Internet infrastructure and a control-theoretical approach that lays well-understood theoretical foundations for resource management to achieve performance differentiation in proxy caches are described.
ACM SIGMETRICS Performance Evaluation ReviewWorkload characterization of a Web proxy in a cable modem environment
113 Citations1999Martin Arlitt, Rich Friedrich +1 more
It is found that when presented with faster access speeds users are willing to download extremely large files, which increases the importance of caching for ensuring the scalability of the Web.
Optimal proxy cache allocation for efficient streaming media distribution
111 Citations2003Bing Wang, Subhabrata Sen +2 more
This paper develops a technique to analytically determine the optimal proxy prefix cache allocation to the videos that minimizes the aggregate network bandwidth cost and finds that carefully designed proxy-assisted reactive transmission schemes can produce significant cost savings even in predominantly unicast environments such as the Internet.
A Simple Yet Robust Caching Algorithm Based on Dynamic Access Patterns
102 Citations1994James E. Pitkow, Mimi Recker
An apparatus and method for towing a pipeline in a body of water to a place where the pipeline is to be laid on the bed of theBody of water, the pipeline having a positive buoyancy and being provided with trail-ropes distributed therealong, optimally comprising means for penetrating the bed so as to offer increased resistance to drift.
Computer Networks and ISDN SystemsA case for delay-conscious caching of Web documents
101 Citations1997Peter Scheuermann, Junho Shim +1 more
This paper presents a new, delay-conscious cache replacement algorithm LNC-R-W3 which maximizes a performance metric called delay-savings-ratio and compares it with other existing cache replacement algorithms, namely LRU and LRU-MIN.
Computer Networks and ISDN SystemsPerformance engineering of the World Wide Web: Application to dimensioning and cache design
101 Citations1996Jean-Chrysostome Bolot, Philipp Hoschka
This paper considers performance issues related to dimensioning and caching, and advocates the use of novel cache replacement algorithms that explicitly take document size and network load into account so as to minimize the retrieval time perceived by clients.
Mocha
101 Citations2001Reza Rejaie, Jussi Kangasharju
The design and implementation of Mocha, a quality adaptive multimedia proxy cache for layered encoded streams with ability to adjust quality of cached streams based on their popularity and on the available bandwidth between proxy and interested clients are presented.
ComputerEfficient replacement of nonuniform objects in Web caches
93 Citations2002Hyokyung Bahn, Kern Koh +2 more
The authors present the least-unified value algorithm, which performs better than existing algorithms for replacing nonuniform data objects in wide-area distributed environments.
Performance EvaluationProbabilistic methods for web caching
89 Citations2001David Starobinski, David Tse
This work introduces and analyzes new randomized policies for the management of web caches based on an extended version of the independent reference model, and derives closed-form expressions for the stationary probabilities of finding each possible arrangement of the documents within the cache.
Performance EvaluationTemporal locality and its impact on Web proxy cache performance
83 Citations2000Anirban Mahanti, Derek L. Eager +1 more
It is established that temporal locality arising out of the correlations between document references in the recent-past and near-future does exist for popular documents, and whether or not Web document references at proxy caches can be modeled as independent and identically distributed random events is determined.
The structural cause of file size distributions
79 Citations2002Allen B. Downey
A user model is proposed that explains the shape of the distribution of file sizes in local file systems and in the World Wide Web, and it is found that this model is an accurate description of these systems.
Performance EvaluationPerformance evaluation of Web proxy cache replacement policies
79 Citations2000Martin Arlitt, Rich Friedrich +1 more
Analysis of different Web proxy workload characteristics in making good cache replacement decisions indicates that size-based replacement policies maximize request hit rates while frequency-based policies maximize byte hit rates.
A randomized Web-cache replacement scheme
69 Citations2002Konstantinos Psounis, Balaji Prabhakar
This work proposes randomized algorithms for approximating any existing Web-cache replacement scheme and thereby avoid the need for any data structures and finds that retaining a small number of samples from one iteration to the next leads to an exponential improvement in performance as compared to retaining no samples at all.
Design and implementation of a caching system for streaming media over the Internet
64 Citations2002E. Bommaiah, K. Guo +2 more
A design and implementation of a caching system for streaming media, which utilizes its local memory and disk resources to reduce network and server load, while also improving the video and audio quality perceived by end users is proposed.
On the intrinsic locality properties of Web reference streams
63 Citations2004Rúbia Santos Fonseca, Virgı́lio Almeida +2 more
A framework for describing how reference streams are transformed as they pass through the Internet is proposed, based on three operations: aggregation, disaggregation, and filtering, and it is argued that these metrics are more natural and more useful than previously proposed metrics for temporal locality.
A caching and streaming framework for mulitmedia
58 Citations2000Shantanu Paknikar, Mohan Kankanhalli +3 more
The paper describes a design for a streaming and caching architecture to be deployed on broadband networks using the proposed Internet standard, Real Time Streaming Protocol, likely to be the de-facto standard for web-based A/V caching and streaming in the near future.
Lecture notes in computer sciencePerformance Evaluation of Web Proxy Cache Replacement Policies
55 Citations1998Martin Arlitt, Rich Friedrich +1 more
ComputerProxy servers for scalable interactive video support
54 Citations2001H. Fabmi, M. Latif +4 more
Targeting scalability, load balance and resource efficiency in streaming multimedia applications, proxy servers facilitate faster real-time access to cached objects and reduce response time to document requests.
Lecture notes in computer scienceRole of Aging, Frequency, and Size in Web Cache Replacement Policies
53 Citations2001Ludmila Cherkasova, Gianfranco Ciardo
This paper proposes a generalization of Greedy-Dual-Frequency-Size policy which allows to balance the emphasis on size vs. frequency, and performs a sensitivity study to derive the impact of size and frequency on file and byte hit ratio.
Computer NetworksProtocol considerations for a prefix-caching proxy for multimedia streams
48 Citations2000S. Gruber, Jennifer Rexford +1 more
This paper analyzes the challenges of realizing a prefix-caching service in the context of the IETF's Real-Time Streaming Protocol (RTSP), a multimedia streaming protocol that derives from HTTP, and proposes extensions to RTSP that would ease the development of new multimedia proxy services.
LRU-SP: a size-adjusted and popularity-aware LRU replacement algorithm for web caching
46 Citations2002Kai Cheng, Yumi Kambayashi
This paper presents LRU-SP, a size-adjusted and popularity-aware extension to Least Recently Used for caching web objects that can achieve higher hit rates and byte hit rates than the standard LRU.
IEEE Transactions on MultimediaReducing bandwidth requirement for delivering video over wide area networks with proxy server
46 Citations2002Wei-Hsiu Ma, D.H.C. Du
Streaming media caching algorithms for transcoding proxies
44 Citations2003Xueyan Tang, Fan Zhang +1 more
This paper proposes a new adaptive algorithm that dynamically selects an appropriate metric for adjusting the management policy and investigates partitioning a video object into sections based on frame type and handling them individually for proxy caching.
Proxy cache coherency and replacement-towards a more complete picture
43 Citations2003Balachander Krishnamurthy, Craig E. Wills
The use of access frequency in cache replacement, along with temporal locality and size information, results in a simple and better performing policy than found in previously published work.
Static caching in Web servers
42 Citations2002Igor Tatarinov, Alex Rousskov +1 more
This paper uses log files from four Web servers and proposes and evaluates static caching, a novel cache policy for Web servers that incur no CPU overhead and does not suffer from memory fragmentation.
Lecture notes in computer scienceEvaluating Server-Assisted Cache Replacement in the Web
41 Citations1998Edith Cohen, Balachander Krishnamurthy +1 more
The experiments show that utilizing the server knowledge of access patterns can greatly improve the effectiveness of proxy caches and propose a caching policy utilizing statistics on resource inter-request times.
Replacement strategies for quality based video caching
37 Citations2003Stefan Podlipnig, László Böszörményi
Replacement strategies for video caches that incorporate quality reduction and the use of metadata given by the content provider are presented and evaluated by simulation.
Taylor series prediction: a cache replacement policy based on second-order trend analysis
35 Citations2005Qiang Yang, H.H. Zhang +1 more
This paper extends the well-known GDSF caching policies to include not only access trend information, but also the dynamics of the access trend itself to the trends on access trends, to provide more accurate prediction on future accessing trends when the access patterns vary greatly.
ACM SIGMOD RecordReview of Web caching and replication by Michael Rabinovich and Oliver Spatscheck. Addison Wesley 2002.
35 Citations2003Qiang Wang, Brian D. Davison
This book, by two leading researchers at AT&T Labs, presents the state-of-the-art in Web caching and replication from and for both industry and academic research.
Popularity-based partial caching for VOD systems using a proxy server
32 Citations2005Seong Ho Park, Eun Ji Lim +1 more
A PPC (Populari@-based Partial Caching) scheme for continuous media objects on the proxy servers, which outperforms other well-known caching schemes in hit ratios and replacement overhead.
Web caching framework: analytical models and beyond
31 Citations2003Jiuyang Zhang, Rauf Izmailov +2 more
By using a framework within which Web caching algorithms can be consistently analyzed and empirically examined, this work is able to better understand the performance discrepancies exhibited by different algorithms and develop more efficient new algorithms.
Prefix caching assisted periodic broadcast for streaming popular videos
28 Citations2003Yang Guo, Subhabrata Sen +1 more
A scalable and flexible framework integrating proxy-based prefix caching with periodic broadcast of the suffix of a video from the server, for efficiently streaming a set of popular videos to a large number of asynchronous clients is proposed.
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE<title>Static caching of Web servers</title>
27 Citations1997Zhen Liu, Philippe Nain +2 more
It turns out that static caching is more efficient in terms of hit rate than those analyzed in the literature.
Lecture notes in computer scienceLRU-based algorithms for Web Cache Replacement
27 Citations2000Athena Vakali
This paper proposes an extension to the conventional LRU algorithm by considering the number of references to Web objects as a critical parameter for the cache content replacement, and shows that the proposed cache replacement algorithms improve cache content.
Computer Networks and ISDN SystemsDesign and implementation of a soft caching proxy
25 Citations1998Jussi Kangasharju, Young Gap Kwon +1 more
This paper addresses a set of modifications to classical proxy caching algorithms which allow the implementation of a soft caching proxy system based on the Squid proxy, details the modifications made and the experiences obtained.
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE<title>Proxy caching mechanisms with video quality adjustment</title>
20 Citations2001Masahiro Sasabe, Naoki Wakamiya +2 more
This paper proposes proxy caching mechanisms that can achieve a high-quality video transfer considering the user's demand and the available bandwidth and evaluates their performance in terms of the required buffer size, the play-out delay and the video quality.
SSRN Electronic JournalVariable Qos from Shared Web Caches: User-Centered Design and Value-Sensitive Replacement
19 Citations1999Terence Kelly, Sugih Jamin +1 more
A novel value-sensitive LFU/LRU hybrid is introduced which biases the allocation of cache space toward documents whose origin servers value caching most highly, and is compared with others from the Web caching literature.
Lecture notes in computer scienceThe Impact of Replacement Granularity on Video Caching
16 Citations2002Elias Balafoutis, Antonis Panagakis +2 more
It is shown, that a higher byte hit ratio (BHR) can be achieved through partial replacement, and it is demonstrated that this problem could be addressed by a hybrid caching scheme that employs variable sized chunks.
Systematic multiresolution and its application to the World Wide Web
14 Citations1999Swarup Acharya, Henry F. Korth +1 more
This work addresses two key problems facing the Web: high latencies and heterogeneity of client resources and requirements by dynamically generating the "required version" of a Web object based on client preferences and capabilities through systematic multiresolution.
Lecture notes in computer scienceImproving the Effectiveness of Web Caching
14 Citations2000Jean-Marc Menaud, Valérie Issarny +1 more
The solutions to improving the effectiveness of Web caching concerning both cache management and cache cooperation are presented, including two novel algorithms that exploit the latest results about Web usage, enabling us to undertake replacement decisions that are more accurate than the one taken by existing algorithms.
A new document placement scheme for cooperative caching on the Internet
13 Citations2003Lakshmish Ramaswamy, Ling Liu
A new document placement scheme, called the Expiration Age based scheme (EA scheme), which takes into account the contentions at individual caches in order to limit the replication of documents within a cache group and increase document hit ratio.
Lecture notes in computer scienceGenerational replacement schemes for a WWW caching proxy server
12 Citations1997Noritaka Osawa, Toshitsugu Yuba +1 more
This paper proposes and evaluates generational replacement schemes that suit access patterns to the World Wide Web proxy server cache that partition a cache into generations and put frequently accessed data into older generations where entries are less likely to be replaced.
Research Commons (University of Waikato)The LRU*WWW proxy cache document replacement algorithm
12 Citations1999Chung-yi Chang, Anthony James McGregor +1 more
This paper validates the work of other authors by reproducing their studies of proxy cache document replacement algorithms and proposes a new algorithm, LRU*, that consistently performs well across all traces.
The International Journal of Periodontics & Restorative DentistryInvestigation of generalized caching
12 Citations1998Saied Hosseini-Khayat
This dissertation explores the replacement problem that arises in caching data objects of non-uniform size, and formulates the problem as a discrete optimization problem, proves that it is NP-complete, and proposes an optimal solution for the off-line variant of the problem.
stor-serv: Adding Quality-of-Service to Network Storage
10 Citations1999Coshall John, I-Hsun Chuang +1 more
The stor-serv framework, inspired by the intserv and diffserv frameworks in the data transmission domain, brings the concept of Quality-of-Service (QoS) to the network storage domain and supports multiple service classes, each with varying degrees of QoS.
Transcoding-enabled Caching Proxy for Video Delivery in Heterogeneous Network Environments.
9 Citations2002Bo Shen, Sung-Ju Lee
Simulation results indicate that by incorporating transcoding capability at the network edges, the traffic to the content origin server is reduced 20% and the cache hit ratio is improved.
Lecture notes in computer scienceA Web Proxy Cache Coherency and Replacement Approach
5 Citations2001José Aguilar, Ernst L. Leiss
An adaptive cache coherence-replacement scheme for web proxy cache systems that is based on several criteria about the system and applications to provide an effective utilization of the distributed cache memory and a good application performance.
International Conference on Internet ComputingEssence of an Effective Web Caching Algorithm.
5 Citations2000Annie Foong, Yu Hu +1 more
The concept of a cache demand function was introduced and the size and lifespan of an object as important components of any web caching strategy were identified.
SIMULATIONConcurrent Evaluation of Web Cache Replacement and Coherence Strategies
4 Citations2002Adam Belloum, L.O. Hertzberger
The authors’ aim in this study is to outline using simulation the impact of some cache coherence techniques such as the invalidation protocol, the TTL-based strategies, and prefetching on the efficiency of the cache replacement strategies.
IEICE Transactions on CommunicationsA Cache Replacement Policy for Transcoding Proxy Servers
4 Citations2004K.H. Yeung, C.M. Wong +2 more
Simulation results show the proposed cache replacement policy outperforms the conventional LRU in both the cache hit rate and the average object transcoding time.
Infoscience (Ecole Polytechnique Fédérale de Lausanne)Scalable content distribution in the Internet
3 Citations2000Pablo Rodríguez
An Adaptive MPEG-4 Proxy Cache
1 Citations2002Peter Schojer, László Böszörményi +1 more
With the availability of MPEG-4 it is possible to develop a standard compliant proxy that allows fast and efficient adaptation and a promising approach to improve caching efficiency is to adapt videos.
…