EVALUATION OF PROXY CACHE REPLACEMENT ALGORITHMS FOR IMPROVING INTERNET PERFORMANCE

Abstract

The enormous popularity of the World Wide Web has caused tremendous increase in network traffic due to HTTP requests. The problem of managing Internet traffic can be handled by caching them at various points of the network. A key component of a cache is its replacement policy. The problem of document replacement in proxy caches has received much attention in recent research. It has been observed that "least recently used" document replacement policy used in processor-cache performs poorly in proxy caches. Algorithms for proxy cache replacement have been developed on the basis of a deterministic (GD-Size, HYBRID etc) or probabilistic (LRV) cost function, or on the basis of the past history (HLRU, HSLRU) of the document, or by merging two policies into a single one (RANDOMIZED). Previously, all these algorithms were implemented and compared with deterministic algorithms such as LRU, GD-Size, FIFO etc. However there has been no comparison between them. This dissertation work presents a performance comparison of the proxy replacement algorithms, namely HLRU, HSLRU, LRV and RANDOMIZED. LRU threshold has been implemented, as it is a standard algorithm used in almost all proxy caches. We have developed a proxy cache simulator where all the above mentioned algorithms are implemented. The performance metrics used are cache hit rate (CHR), byte hit rate (BHR), relative CHR, relative BHR and errors in discarding documents. This has been done by using as input a daily trace log which has been downloaded from the SQUID proxy cache server [