Web proxy caches are used to improve performance of the WWW. Since the
majority of Web documents are static documents, caching them at WWW
proxies reduces both network traffic and request response time. One
of the keys to better proxy cache performance is an efficient caching
policy which intends to keep in the cache popular documents and
replace rarely used ones. We introduce
Greedy-Dual-Size-Frequency caching policy to maximize hit and byte hit
rates for WWW proxies. Proposed caching strategy incorporates in a
simple way the most important characterizations of the file and its
accesses such as file size, file access frequency and recentness of
the last access. Greedy-Dual-Size-Frequency is an improvement of
Greedy-Dual-Size algorithm -- current champion among the replacement
strategies proposed for Web proxy caches.
The latest web cache replacement policies incorporate the document size,
frequency, and age in the decision process.
Greedy-Dual-Size (GDS) policy is based on document size and has an
elegant aging mechanism. Similarly, the Greedy-Dual-Frequency (GDF) policy
takes into account file frequency and exploits the aging mechanism to deal
with cache pollution. The efficiency of a cache replacement policy can be
evaluated along two popular metrics: file hit ratio and byte
hit ratio. Using four different web server logs, we show that GDS-like
replacement policies emphasizing size yield the best file
hit ratio but typically show poor byte hit ratio, while
GDF-like replacement policies emphasizing frequency have better
byte hit ratio but result in worse file hit ratio. We also
propose a generalization of Greedy-Dual-Frequency-Size policy which
allows to balance the emphasis on size vs.~frequency. We
perform a sensitivity study to derive the impact of size and
frequency on file and byte hit ratio, identifying
parameters that aim at optimizing both metrics.
Related Papers and Reports
- L. Cherkasova , G. Ciardo:
Role of Aging, Frequency, and Size in Web Cache Replacement Policies.
Lecture Notes in Computer Science, Springer-Verlag, vol. 2110, pp.114-123,
Proceedings on High Performance Computing and Networking, HPCN'01,
Amsterdam, June 25-27, 2001.
- L. Cherkasova: Improving WWW Proxies Performance with Greedy-Dual-Size-Frequency
HP Laboratories Report No. HPL-98-69R1, April, 1998.
- M. Arlitt, L. Cherkasova, J. Dilley, R. Friedrich, T. Jin:
Evaluating Content Management Techniques for Web Proxy Caches.
HP Laboratories Report No. HPL-98-173, 1998.
Also, in Proceedings of the 2nd Workshop on Internet Server Performance WISP'99, May, 1999, Atlanta, Georgia.