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 Caching Policy.
  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.