The Model

  Consider a cache that receives a stream of requests for Web pages. Let N be the total number of Web pages in the universe. Let P_N(i) be the conditional probability that, given the arrival of a page request, the arriving request is made for page i. Let all the pages be ranked in order of their popularity where page i is the i'th most popular page. We assume that P_N(i), defined for $i=1, 2, \ldots, N$, has a ``cut-off'' Zipf distribution given by

$$P_N(i) = \frac{\Omega}{i},$$

where

$$\Omega = \left( \sum_{i=0}^N \frac{1}{i} \right)^{-1}$$

Each page request is drawn independently from the Zipf distribution, so we are neglecting any other source of correlations in the request stream. Moreover, we assume that, over the course of time, no pages are invalidated by the cache. We realize that this is an artificial model, but our goal here is to ask what results we can obtain from such a simple assumption.

We calculate the hit-ratio for the cache in two extreme limiting cases and the interrival times in a limiting case, which we consider in the following three sections.