Page replacement with multi-size pages and applications to Web caching
Sandy Irani · 1997
We consider the paging problem where the pages have varying size.This problem has applications to page replacement policies for caches containing World Wide Web documents.We consider two models for the cost of an algorithm on a request sequence.In this first, (the FAULT model) the goal is to minimize the number of page faults.In the second, (the BIT model) the goal is to minimize the total number of bits which have to be read into the cache.We show offline algorithms for both cost models which obtain approximation factors of O(log k), where k is the ratio of the size of the cache to the size of the smallest page.We show randomized online algorithms for both cost models which are O(log2 k)-competitive.In addition, if the input sequence is generated by a known distribution, we show algorithms for both cost models whose expected cost is within a factor of O(log k) of any other online algorithm.