A new Web cache replacement algorithm

In recent research, the problem of document replacement in Web caches has received much interest. Web caches are different from system/processor caches because web caches have several additional criteria (frequency and recentness of pages, size of a document, cost of fetching a document etc.). It has been shown that, the classical LRU replacement policy performs poorly in Web caches because the above criteria decrease hit rate and increase eviction latency and access latency of Web request. Moreover, in order to implement the classical and novel schemes, one needs to maintain complex data structures and the operations of the data structures lead net traffic jam. The current randomized algorithms don´t perform constantly well. We propose a randomized algorithm that avoids the need for any data structure and performs constantly well. In this paper, a new randomized algorithm approximating random replacement (RR) and least recently used (LRU) scheme is introduced for page replacement in caches. The basic version of the new proposed algorithm performs as follows: bins are logical division in cache and number of bins depends on percentage of error acceptable for approximation. When a new page is to be evicted from the cache, the algorithm randomly selects a bin containing pages (old, new, or both type of pages). After searching for an old page randomly in the selected bin, it replaces the old page, if there any, with the new page. Otherwise it selects another bin randomly and continues in the same manner. The algorithm can easily be implemented without using any complex data structure. It also reduces the response time effectively. Experiment shows that the algorithm performs better while being used in Web caches.