Simulation Assignment 4 - Web Cache Replacement Policies

Due Date

This assignment is due by 2:00 p.m. on Monday, 4 April at 2:00 p.m..

See the assignment turn-in page (last modified on 9 February 2004) for instructions on turning in your assignment.

A web cache is a cache for objects retrieved from the World Wide Web. A web cache has two main objectives. The first is to reduce a site's external bandwidth requirements; the second is to provide better response times to browsers hosted at the site.

A web cache is a proxy that sits between a site's browsers (or other requesters of web services) and the site's gateway to the Internet. When the web cache gets an HTTP request, it examines its cache to see if the request can be satisfied by an object in the cache. If it can, the request is flushed and the web cache responds with the object on behalf of the server, reducing external bandwidth and improving the requester's response time.

If the request can't be satisfied, the web cache re-issues the request on behalf of requester. When the server responds, the web cache stores the response object in the cache and then behaves as described in the previous paragraph.

Like all caches, web caches have finite cache space, which means at some point the cache becomes sufficiently occupied that objects of reasonable size can be no longer be cached. When this happens, the web cache uses a replacement policy to determine which, if any, of the cache-resident objects should be removed from the cache to make room for new objects.

Successful caching of any kind depends on adapting to context, particularly access patterns, but also other characteristics related to, for example, the objects being cached and the cache itself. Web-retreived objecs are complex and heterogenuous, which presents a wide range of characteristics, making web caching more difficult.

The complexity of web caching is reflected in the number of cache replacement policies that have been developed. The readings for this assignment (A survey of Web cache replacement strategies by Stefan Podlipnig and Laszlo Boszormenyi, ACM Computing Surveys, December 2003 (vol. 34 no. 4), pages 374-398.) give an overview of the various web-cache replacement policies that have been developed.

The Problem

Pick at least three different replacement policies from Podlipnig and Boszormenyi and develop a simulation to characterize their effectiveness on benchmark web traffic.

Input

The only required input to your simulation should be the web-traffic characterization to be used by the simulation. The form of the characterization is up to you; it may be actual trace data, or more compact distributions. You simulation should be able to handle several different characterizations of the same form.

There will be some sample web-traffic characterizations in the assignment directory as soon as I can find some.

Output

The output of your simulation is up to you, but it should be complete enough (and understandable enough) to support the conclusions drawn in your report.

Grading

Each simulation will be graded independently of all other simulations for this assignment; there is no grade rationing.

Turn-In

You should turn-in your simulation code. You should also turn-in a report describing about your simulation. The report should describe

Your model. A description of the problem analysis and the general structure of your simulation model.
Your experiments. The experiment inputs and parameters used, and how you varied them to conduct your experiments.
Your results. Your experiment results and how you interpret them to answer the questions asked in the Problem Section above.

This report will be the basis for your presentation. The report should be in a generic format, such as plain text, PostScript, or Portable Document Format (pdf). Get in touch with me if you want to use something else.

You should include a makefile among the files you turn in, either for testing or to turn-in. Your makefile should understand two targets: go and clean. The go target should build your assignment. The clean target should delete all unnecessary files. Unnecessary files are any files generated by the makefile itself; such files include the .o files for C++, class files for Java, and any executables built by the makefile.

When you test or turn-in your project, the turn-in script runs (among other things) the following commands:

$ make clean

$ make go

You should make sure this works correctly.