Replacement policies for a proxy cache

In this paper, we analyze access traces to a Web proxy, looking at statisti cal parameters to be used in the design of a replacement policy for documen ts held in the cache. In the first part of this paper, we present a number of properties of the lifetime and statistics of access to documents, derive d from two large trace sets coming from very different proxies and spanning over time intervals of up to five months. In the second part, we propose a novel replacement policy, called LRV, which selects for replacement the do cument with the lowest relative value among those in cache. In LRV, the val ue of a document is computed adaptively based on information readily availa ble to the proxy server. The algorithm has no hardwired constants, and the computations associated with the replacement policy require only a small co nstant time. We show how LRV outperforms LRU and other policies and can sig nificantly improve the performance of the cache, especially for a small one .