Optimality of Static Caching

Assume that exactly n documents reside in the Web server which are requested at rates r₁ $\geq$ r₂ $\geq$ $\cdots$ $\geq$ r_n . Assume that the sizes of the documents are identically distributed random variables. Moreover, we shall assume that the cache can hold a fixed number m of documents at any time (note that this assumption clearly does not hold for the ``smallest size'' caching policy). Let X_i denote the index of the document of the i -th request, and Y_k,i the indicator function of whether document k is in the cache at the i -th request. We shall assume that {X_i}_i is a sequence of independent and identically distributed random variables. Then, the empirical hit rate of caching policy $\pi$ , denoted by H_$\pi$ , can be expressed as

H_$\pi$ = $$\lim_{T\to\infty}^{}$$$${\textstyle\frac{1}{T}}$$$$\sum_{i=1}^{T}$$$$\sum_{k=1}^{n}$$$$\bf$$1(X_i = k)Y_k,i.

Assume that the sequence {X_i,Y_k,i}_i is (jointly) stationary and ergodic so that the theorem of Kingman [6] applies. Then,

H_$\pi$ = $$\lim_{T\to\infty}^{}$$$${\textstyle\frac{1}{T}}$$$$\sum_{i=1}^{T}$$$$\sum_{k=1}^{n}$$E$$\left[ {\bf 1}(X_i=k) Y_{k,i} \right].$$

For any non-anticipative caching policy $\pi$ (i.e., $\pi$ has no knowledge of future requests), Y_k,i depends only on the previous requests X₁,...,X_{i - 1} for any i . Thus,

$$\pi \lim_{T\to\infty}^{} {\textstyle\frac{1}{T}} \sum_{i=1}^{T} \sum_{k=1}^{n} \pi \left[ {\bf 1}(X_i=k) Y_{k,i} \right]$$ =

$$\lim_{T\to\infty}^{} {\textstyle\frac{1}{T}} \sum_{i=1}^{T} \sum_{k=1}^{n} \pi \left[ {\bf 1}(X_i=k) \right]E \pi \left[ Y_{k,i} \right]$$ =

$$\lim_{T\to\infty}^{} {\textstyle\frac{1}{T}} \sum_{i=1}^{T} \sum_{k=1}^{n} \pi \left[ Y_{k,i} \right]$$ =

$$\sum_{k=1}^{n} \pi$$ =

where the last equality comes from the stationarity of {Y_k,i}_i , and q_k($\pi$) : = E_$\pi$$\left[ Y_{k,i} \right]$ is the probability that document k is kept in the cache.

Note that $\sum_{k=1}^{n}$q_k($\pi$) = $\sum_{k=1}^{n}$E_$\pi$$\left[ Y_{k,i} \right]=$m , and that for all k , 0 $\leq$ q_k($\pi$) $\leq$ 1 . Let r_{n + 1} = 0 . Then,

$$\pi \sum_{k=1}^{n} \pi$$ =

$$\sum_{k=1}^{n} \sum_{i=k}^{n} \pi$$ =

$$\sum_{i=1}^{n} \sum_{k=1}^{i} \pi$$ =

$$\leq \sum_{i=1}^{n}$$

$$\sum_{i=1}^{m}$$ =

By definition, the hit rate of the static policy H_s is H_s = $\sum_{i=1}^{m}$r_i . Thus, H_$\pi$ $\leq$ H_s .

Note that under the above assumptions (in particular, the documents have identical size), the ``request hit rate'' and the ``byte hit rate'' (see definitions below) coincide.

We assume now that the documents have different sizes, say b_i bytes for document i . As in the previous case, we assume that r_i is decreasingly ordered. Let B be the size of the cache. Then, the optimal static caching can be formulated as a 0-1 programming problem:

$$\begin{array} {ll} \max & \sum_{i=1}^{n}r_ib_iZ_i \ & \ \text{s.t.:} & \sum_{i=1}^{n}b_iZ_i\leq B, \ & \forall i, Z_i=0\ or\ 1\end{array}$$

where Z_i is the indicator function of whether document i is in the cache. The cost to be maximized is proportional to the byte hitrate

$${\frac{\sum_{i=1}^{n}r_ib_iZ_i}{\sum_{i=1}^{n}r_ib_i}}$$.

Let S denote the cost of the solution of this problem. It is easy to see that such a problem is the well-known knapsack problem, which is NP-hard in general. Thus, in our implementation, we consider an approximate solution resulting from relaxation. Indeed, by relaxing the 0-1 constraint on Z_i , i.e., by assuming that Z_i is a real number ( Z_i $\in$ [0,1] ), we can easily see that an optimal solution is {Z₁ = 1,Z₂ = 1,,Z_k = 1 , Z_{k + 1} = (B - $\sum_{i=1}^{k}$b_i)/b_k),Z_{k + 2} = 0,,Z_n = 0} , where k = max {j $\leq$ n|$\sum_{i=1}^{j}$b_iZ_i $\leq$ B} .

Let S_r be the hitrate of the static caching (using a cache whose size possibly exceeds B ) of documents 1,2,,k + 1 . It is clear that S $\leq$ S_r .

Our approximate solution, denoted by S_a , is obtained by caching documents 1,2,,k and some further documents after k that can be filled in the cache. Again, it is clear that S_a $\leq$ S $\leq$ S_r .

This approximate solution is suboptimal. In practice, however, with the data of WWW documents access, this approximate solution S_a turns out to be very close to the upper bound S_r (the differences being smaller than 0.01% in our numerical experimentation). Therefore, we shall simply take the approximate solution as the optimal static solution. In section 4, the performance of this solution will be reported.