Trace-Driven Simulation

We have developed a simulator which models the behavior of a cache manager for a Web server. We use the approach of trace-driven simulation: the request arrivals of the simulator are taken from a log file. When a new request arrives in the simulator, it checks the contents of the cache to see whether the corresponding documents is already in it (according to its URL). If yes, the cache is left unchanged and the hit counter of the document is increased by one. Otherwise, the reference of the file corresponding to the request is fetched into the cache, provided the cache is not full. In the case where the cache is full, some documents are removed from the cache according to a predefined removal policy, until there is sufficient room for the new file. We also use a threshold: documents with a size greater than 50% of the cache size are never put in the cache.

We analyze two measures of efficiency of the removal policies, where the second one seems to be more relevant to the performance of the Web server.

• request hit rate: percentage of requested documents that are in the cache.
• byte hit rate: percentage of bytes transferred from the cache.

Different cache removal policies have been investigated:

• LRU (Least Recently Used). This policy removes the files that have not been used for the longest period of time.
• LFU (Least Frequently Used). The documents being referenced less frequently are removed first. In our simulation we use a simple approximation which maintains a reference counter on the number of accesses to each document in the cache. The documents having the smallest number of references are removed.
• SIZE. Biggest files are removed first. This policy tend to be good for the request hit rate (removing large documents leaves a lot of space for smaller documents). However, it can have worse byte hit rate (although it outperforms LFU and LRU on proxy caches according to [10])
• LFU*-aging, a policy proposed in [1]. It is a more complex removal policy and seems to be quite efficient in terms of request hit rate.
• Static policy: files are never removed from the cache. The documents are placed in the cache according to the previous day's (or hours, weeks ... ) statistics.

In order to compare the efficiency in a fair way, we run the simulation with log files for several consecutive days. For each day, we have run the simulator and have looked at the hit rate and weighted hit rate during this day. For the static policy, we have filled up the cache with the most popular documents of the previous day. For the others policies, the cache is initialized with the documents that were in the cache at the end of the previous simulation. We have done this both with the W3C and the INRIA traces.