Web Caching and Replication

11.2. Replacement Policy Algorithms

After describing some of the metrics of interest, let us now turn to the replacement algorithms. Broadly, they can be grouped into three categories as proposed by Aggarwal et al. [1999]. The first group of algorithms includes the classic replacement algorithms, of which the main representatives are Least Recently Used (LRU) and Least Frequently Used (LFU). As their names indicate, LRU replaces the object that was used least recently and LFU replaces the object that was used least frequently. Both algorithms can be implemented fairly easily and are used in many applications outside the Web. LFU and LRU often serve as the basis of comparison for newly proposed replacement algorithms.

The second class of algorithms ...