MODEL-DRIVEN SIMULATION OF WORLD-WIDE-WEB CACHE POLICIES
Ying Shi
Edward Watson
Ye-sho Chen
Department of Information Systems and Decision Sciences
E. J. Ourso College of Business Administration
Louisiana State University
Baton Rouge, LA 70803, U.S.A.
ABSTRACT
The World Wide Web (WWW) has experienced a
dramatic increase in popularity since 1993. Many reports
indicate that its growth will continue at an exponential
rate. This growth has created a tremendous increase in
network loads and user response times. The complexity
and diversity of many WWW documents (e.g., texts,
images, video, audio, etc.) and the diversity of user
requested WWW information require sophisticated
WWW cache management strategies. Several popular
WWW cache algorithms perform rather poorly and lack
mathematical or empirical foundations. As a result,
WWW system administrators and browser users are
forced to arbitrarily define certain important cache
parameters. Typically, such systems perform sub-
optimally averaging hit rates below 55%. Our objective
in this study is to develop a cache management strategy
that is based on sound theory and principles from the
information sciences and that can be utilized on-line, in
real-time. Our approach is to study current cache
algorithms and utilize actual empirical data to develop
efficient and effective self-adaptive cache management
strategies to handle anticipated Web growth.
1 INTRODUCTION
Increased user response times has left many web users
cynically referring to WWW as the World-Wide-Wait
(Abrams, 1997). Long wait times are attributed to an
Internet bandwidth that has not increased at the same rate
as the growth in demand being placed upon it.
Bandwidth and response time problems will most likely
increase as more people use the Internet. Thus, saving
bandwidth, improving response time and reducing server
load is a major research interest. The National Science
Foundation states that a critical research topic for the
National Information Infrastructure is to “develop new
technologies for organizing cache memories and other
buffering schemes to alleviate memory and network
latency and increase bandwidth” (Bestavros 1995).
A cache is nothing more than a computer storage
medium where certain documents are stored, often based
on frequency and recency of document usage. The cache
maintains a copy of certain documents from the origin
servers to machines residing closer to clients. This can
reduce the transmission distance significantly. Abrams
(1995) states that without caching the WWW would
become a victim of its own success.
Unlike a CPU cache, where a file is divided into many
blocks that are homogeneous in size, a WWW cache
contains documents of a widely varying size and type
and the document is stored as a whole (Abrams 1995).
Variable document sizes and types allow a rich variety of
policies to select a document for removal, in contrast to
policies for CPU caches that manage homogeneous
documents (Williams, et al. 1996).
2. WEB CACHE PERFORMANCE, REMOVAL
POLICIES AND USER ACCESS PATTERNS
2.1 Web Cache Performance
Several metrics are commonly used when evaluating
Web caching policies. These include the following
(Abrams, et al. 1997).
a) Hit rate - The hit rate is generally a percentage ratio
of documents obtained through using the caching
mechanism versus the total documents requested. In
addition, if measurement focuses on byte transfer
efficiency, weighted hit rate is a better performance
measurement (Abrams, 1995).
b) Bandwidth Utilization - An efficiency metric. A
reduction in the amount of bandwidth consumed
shows the cache is better.
c) Response time/access time - The response time is
the time it takes for a user to get a document.
Proceedings of the 1997 Winter Simulation Conference
ed. S. Andradóttir, K. J. Healy, D. H. Withers, and B. L. Nelson