4WWW95: proxies: limitations and potentials


this paper presented four experiments with caching proxy servers.

workload used in this study:

the study was done using a workload simulation. actually, they used three different workloads, based on the usage of three different groups of workstations:

  1. "undergrad" (U): workstations in an undergraduate computer science lab representing about 150 different users.
  2. "graduate" (G): a popular host used by at least 25 graduate computer science students.
  3. "classroom" (C): 26 workstations in a classroom on which students run a Web browser during sessions of a class on multimedia.

workloads U and G represent a mixture of Web usage, while in workload C the instructor often directs students to look at certain URLs.

caching algorithms studied:

they compared three different replacement policies:

  1. LRU:
    this is the classic "Least Recently Used" replacement policy. when the space in the cache is smaller than the document to be cached, documents will be removed from the cache until there is enough space in the cache, starting with the oldest document. this policy may remove many small documents from the cache to make room for one large document.

  2. LRU-MIN:
    a variant of the LRU policy that tries to minimize the number of documents replaced. it first tries to remove the least recent document from the cache that is at least of the size of the new document to be cached. if this fails, smaller least recent documents will be removed.

    a variant of the LRU policy that avoids the replacement of many smaller documents by a large document by introducing a maximum document size that will be cached. documents larger than this threshold will NOT be cached, even if there IS enough room in the cache.

experiment: maximum possible hit rate for a caching proxy:

experiment: optimal threshold for the LRU-THOLD replacement policy:

experiment: comparison of cache replacement algorithms:

experiment: impact of other caching parameters:

for more information, see

back to 4WWW95 main document.

4WWW95 caching 2 / 28-jan-1999 (ra) / reto ambühler