Write a web-page simulator and evaluate the impact of cache size on the hit rate using a synthetic workload
The project is designed to further programming skills and to initiate the students to the design and conduct of experiments (based on simulation). (ABET Criterion 3(b)).
Build a simulator for a web page cache. Web pages come in different sizes. A web page cache contains recently visited pages. Whenever the user asks for a new web page, the browser first looks into the cache to see whether the request can be fulfilled from the cache. This counts as a hit. If the request cannot be fulfilled from the cache, then this is a miss. The cost of the miss depends on the size of the web page missed. If the browser has to fetch a webpage from the net, and it still fits into the cache, then the browser puts the page into the cache. However, cache size is not unlimited, and eventually the cache will be filled up. The interesting design problem is the replacement policy. Least recently used (LRU) however might not be the best one, since a really big webpage could force all residents of the cache to be evicted in order to make room for it. That would really limit the number of subsequent hits.Your task is:
- To design measures for cache performance. One such measure would be the number of hits, another would be the amount of bandwidth used.
- To develop three different reasonable cache replacement strategies.
- To run simulation experiments, document your findings, and draw conclusions. You need to vary the cache size as well.
You should use ProWGen, which generates synthetic workloads for a web cache. You can download ProWGen as a Unix tar file from http://www.cs.usask.ca/faculty/carey/software or here.
- Detailed description of your cache policies, measures, and measurements (including bibliography, if appropriate).
- Documentation of your simulator algorithm .
- Documentation of your results including figures of your measurements.
- Exposition and explanation of results.
- Listing of code.
- Simulator 50% (needs to run on the input implementing at least one cache size and one cache replacement policy yielding at least one meaningful measurement.)
- Design of Cache Policies and Measurements 20%
- Results 15%
- Quality of Documentation 15%
- Teams of two or three students, but everyone on a team has to document their share in the project on a separate sheet.
- Deadline is the day of the final, though students are advised to start very soon in the quarter. This is particularly important for students involved in a senior design project and / or engaged in the search of work.
|© 2003 Thomas Schwarz, S.J., COEN, SCU SCU COEN T. Schwarz COEN 180|