Proxy cache algorithms: design, implementation, and performance

Junho Shim, Peter Scheuermann, Radek Vingralek

Research output: Contribution to journalArticlepeer-review

155 Scopus citations

Abstract

Caching at proxy servers is one of the ways to reduce the response time perceived by World Wide Web users. Cache replacement algorithms play a central role in the response time reduction by selecting a subset of documents for caching, so that a given performance metric is maximized. At the same time, the cache must take extra steps to guarantee some form of consistency of the cached documents. Cache consistency algorithms enforce appropriate guarantees about the staleness of the cached documents. We describe a unified cache maintenance algorithm, LNC-R-W3-U, which integrates both cache replacement and consistency algorithms. The LNC-R-W3-U algorithm evicts documents from the cache based on the delay to fetch each document into the cache. Consequently, the documents that took a long time to fetch are preferentially kept in the cache. The LNC-R-W3-U algorithm also considers in the eviction consideration the validation rate of each document, as provided by the cache consistency component of LNC-R-W3-U. Consequently, documents that are infrequently updated and thus seldom require validations are preferentially retained in the cache. We describe the implementation of LNC-R-W3-U and its integration with the Apache 1.2.6 code base. Finally, we present a trace-driven experimental study of LNC-R-W3-U performance and its comparison with other previously published algorithms for cache maintenance.

Original languageEnglish (US)
Pages (from-to)549-562
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume11
Issue number4
DOIs
StatePublished - Jul 1999

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Proxy cache algorithms: design, implementation, and performance'. Together they form a unique fingerprint.

Cite this