Proxy Cache Design: Algorithms, Implementation and Performance

Caching at proxy servers is one of the ways to reduce the response time perceived by 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-RW3 -U, which integrates both cache replacement and consistency algorithms. The LNC-R-W3-U algorithm evicts documents from the cache based on the the delay to fetch each document into the cache. Consequently, the documents which 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 LNCR ..