4WWW95: proxies: limitations and potentials

authors:

• marc abrams, virginia tech
• charles r. standridge, FMAU-FSU college of engineering, tallahasse FL
• ghaleb abdulla, virginia tech
• stephen williams, virginia tech
• edward a. fox, virginia tech

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.
   
   
3. 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

• detailed information about these experiments
• multimedia traffic analysis using chitra95
• an assessment of the impact of caching documents from NCSA's Web server

back to 4WWW95 main document.