Abstract
Reuther, Albert I., Ph.D., Purdue
University, August 2000. Distributed Multimedia Cache Replacement
Algorithms. Major Professor: David G. Meyer.
Implementation of caches in multimedia proxy servers can significantly
improve the delivery of media by reducing media retrieval latency,
reducing network bandwidth usage, increasing the number of clients that
can be served simultaneously, and increasing the fault tolerance of the
server system. An important component of proxy server caches is the
cache object replacement algorithm, which determines which objects are
removed from the cache when storage space is needed for placing new
objects into the cache. These algorithms must effectively predict which
currently cached objects are not expected to be accessed in the near
future so they can be removed. However, these algorithms must also be
fast; i.e. they cannot be too computationally complex, because these
algorithms must execute often on caches that usually contain a large
number of objects. Current implementations of proxy cache servers
(Squid, Inktomi Traffic Server, Novell Internet Caching System, etc.)
use the least-recently used cache replacement algorithm, but a number
of other object statistics could be used as part of the cache
replacement algorithm calculations.
This research presents the fully-associative, variable block size cache
replacement algorithm problem as a unique model which illuminates a new
method for looking at cache replacement algorithm issues. The study
then explores the use of a variety of cache object statistics and how
well these other statistics help predict the expected future demand for
cached objects. Simulations are used as the method of comparison, and
actual and stochastic data from WWW traces, commercial hotel video
system traces, and educational multimedia system video traces are used
as simulation input. Also, the effectiveness of admission policies and
caching large videos is explored.
Not only will the findings from this study impact the World-Wide Web
caching infrastructure and distributed multimedia system
implementations, but the findings can also influence the efficiency of
distributed databases and other distributed information systems.
The dissertation that I wrote to satisfy a portion of the requirements
of my dissertation for a Ph.D. in the School of Electrical and Computer
Engineering at Purdue University is available as a PDF
file. Also the manuscript of a paper that covers some of the work
in the dissertation is available in this PDF file.
