Check out the new USENIX Web site. next up previous
Next: Fixed ThresholdVariable Modem Up: Experimental Results Previous: Replacement vs. Fixed Timeouts

Comparison of Replacement Algorithms

A more interesting experiment concerns the comparison of different replacement algorithms. The first question to be answered is whether a simple replacement algorithm, like RANDOM, is good enough. RANDOM corresponds to the simple idea of replacing any user who has been idle for more than tex2html_wrap_inline490 seconds. The point of reference for the comparison is the LRU algorithm--a common benchmark in replacement problems. LRU replaces the user who has been idle the longest (as long as this is more than tex2html_wrap_inline490 seconds, in our case). The LRU algorithm has been used in replacement settings ranging widely (e.g., from virtual memory to web caching [ASA tex2html_wrap_inline498 95]). The next step is to see whether a specialized algorithm can perform better than LRU. As we will see, the CIRG algorithm meets this test.





Yannis Smaragdakis
Tue Apr 25 15:09:47 EDT 2000