A Comparative study between cache replacement algorithms used in the scalable asynchronous cache consistency scheme. (c2006)

Abstract

The technology of PCs has been in progress in a fast rate for many years. Mobile computing is one of the technologies brought into the area of computers. Different problems have arisen from the narrow bandwidth and limited battery power of mobile clients. Therefore, algorithms have been proposed to provide cache consistency in mobile databases by using cache invalidation strategies. Scalable Asynchronous Cache Consistency Scheme (SACCS), a highly scalable, efficient and low complexity algorithm, is one of the cache consistency maintenance algorithms proposed. It counts on invalidation reports to maintain cache consistency between server databases and mobile user databases. Least-Recently-Used (LRU) is used as a cache replacement algorithm in SACCS. In this work, different cache replacement strategies are proposed to be applied in SACCS: MRU (Most-Recently-Used), MFU (Most MostFrequently- Used), LFU (Least-Frequently-Used), FIFO (First-In-First-Out). A simulation of SACCS with these cache replacement algorithms is done and produces results that will be compared to show the variation of the perfonnance of the system. Statistical results will point out the advantages and disadvantages of each algorithm concerning miss ratio, delay, total hit, and total miss.