4WWW95: proxies:
limitations and potentials
authors:
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:
- "undergrad" (U): workstations in an undergraduate computer
science lab representing about 150 different users.
- "graduate" (G): a popular host used by at least 25 graduate
computer science students.
- "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:
- 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.
- 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.
- LRU-THOLD:
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:
- PURPOSE:
identify the maximum possible hit rate for the three different workloads,
assuming an infinite cache size (no documents will be removed from the cache).
- RESULTS:
there is no need for an infinite cache ! for the three workloads, they found an
optimal cache size of approximately 120 MB. also, the hit rate declined over
time because of the local cache of the browsers !
experiment: optimal threshold for the LRU-THOLD replacement policy:
- PURPOSE:
find the best possible value for the LRU-THOLD threshold. they varied the
workload, the size of the cache and the threshold value.
- RESULTS:
if the cache is 10% of the optimal cache size found in experiment 1, the
optimal threshold is 16 kB for all workloads. if the cache size is 50% of the
optimal cache size, the optimal threshold is between 64 kB and 1024 kB
depending on the workload.
experiment: comparison of cache replacement algorithms:
- PURPOSE:
compare the three different cache replacement policies.
- RESULTS:
if the size of the cache is large enough compared to the optimal cache size,
LRU-MIN achieved the highest hit rate. on the other hand, LRU-THOLD achieved
dramatically smaller cache sizes with a smaller penalty in the hit rate. both
policies achieved better results than the classic LRU.
experiment: impact of other caching parameters:
- PURPOSE:
find the effect of the following factors:
- caching off campus documents only versus caching all documents
- caching non-text documents only versus caching all document types
- RESULTS:
the highest hit rate was achieved if everything was cached. this is true for
all three types of workload. the penalty for not caching all documents was a
dramatic drop in the hit rate, from at least 10% to almost 50% depending on the
workload.
for more information, see
back to 4WWW95 main document.
4WWW95 caching 2 / 28-jan-1999 (ra) /
reto ambühler
!!! Dieses Dokument stammt aus dem
ETH Web-Archiv und wird nicht mehr gepflegt !!!
!!! This document is stored in the
ETH Web archive and is no longer maintained !!!