5 - Paging

Summary

Introduction

In this chapter, we consider a classical online problem, called paging, where a file request sequence is served from two memories – one fast, called the cache, with finite size, and the other slow, which contains all the files. On a file request, if that file is not found in the cache, then it is loaded from the large memory into the cache by ejecting one of the existing files of the cache. Each such ejection is called a fault and the goal is to minimize the total number of faults without knowing the future file request sequence.

The paging problem is directly relevant for the critical question of what to store in the random access memory (RAM) of a computer system so as to minimize the number of memory overwrites. It has also received renewed attention recently with the advent of large content distribution networks (CDNs), e.g., Youtube, where multiple limited-sized caches serve fastevolving contents that are located closer to the end-users.

For the paging problem, we first consider the deterministic setting, for which we first find a lower bound on the competitive ratio of any online algorithm and then describe an algorithm whose competitive ratio matches the lower bound. Similar strategy is adopted for randomized algorithms, where we first derive a lower bound, and then discuss an almost optimal randomized algorithm. Machine learning augmented algorithms are also considered, where prediction about the future request arrivals is available, albeit with uncertain accuracy. The goal in this paradigm is to design online algorithms that are close to optimal when the accuracy of prediction is very good, and have a reasonable competitive ratio otherwise. We also discuss the randomized input setting, where we show that all natural deterministic algorithms perform poorly, and non-trivial algorithms are required to achieve close to optimal competitive ratios.

To address the modern application of paging in CDNs, we finally consider the multiple cache paging problem, where the input at each time is a vector of file requests that are served by multiple caches parallely.