# A New Upper Bound on Cache Hit Probability for Non-anticipative Caching
Policies

Nitish K. Panigrahy  University of Massachusetts Amherst Amherst, MA 01003USA
<EMAIL_ADDRESS>,  Philippe Nain  Inria Grenoble – Rhône-AlpesLyon
69364France<EMAIL_ADDRESS>,  Giovanni Neglia  Inria Sophia Antipolis
– Méditerranée, UCAFrance<EMAIL_ADDRESS>and  Don Towsley
University of Massachusetts Amherst Amherst, MA 01003USA<EMAIL_ADDRESS>
††copyright: none

Caching systems have long been crucial for improving the performance of a wide
variety of network and web based online applications. In such systems, end-to-
end application performance heavily depends on the fraction of objects
transfered from the cache, also known as the _cache hit probability_. Many
caching policies have been proposed and implemented to improve the hit
probability. In this work, we propose a new method to compute an upper bound
on hit probability for all non-anticipative caching policies, i.e., for
policies that have no knowledge of future requests. Our key insight is to
order the objects according to the ratio of their Hazard Rate (HR) function
values to their sizes and place in the cache the objects with the largest
ratios till the cache capacity is exhausted. Under some statistical
assumptions, we prove that our proposed HR to size ratio based ordering model
computes the maximum achievable hit probability and serves as an upper bound
for all non-anticipative caching policies. We derive closed form expressions
for the upper bound under some specific object request arrival processes. We
also provide simulation results to validate its correctness and to compare it
to the state-of-the-art upper bounds. We find it to be tighter than state-of-
the-art upper bounds for a variety of object request arrival processes.

##  1\. Introduction

Caches are pervasive in computing systems, and their importance is reflected
in many networks and distributed environments including _content delivery
networks_ (CDNs). In such networks, the end user quality of experience
primarily depends on whether the requested object is cached near the user.
Thus the cache _hit probability_ , i.e., the percentage of requests satisfied
by the cache, plays an important role in determining the end-to-end
application performance. In general, the number of objects available in a
system is much larger than the cache capacity. Hence, the design of caching
algorithms typically focuses on maximizing the overall cache hit probability.
Also, maximizing the cache hit probability corresponds to minimizing the
expected retrieval time, the load on the server and on the network when object
sizes are equal.

One possible way to improve cache hit probability is by increasing cache
capacity. However, increasing cache capacity only logarithmically improves
cache hit probability(Breslau et al., 1999; Almeida et al., 1996). Thus
improving caching policies seems to be more effective for maximizing the
overall cache hit probability. In practice, most caches employ _least-recently
used_ (LRU) or its variants often coupled with call admission or prefetching
(Berger et al., 2018). Apart from LRU, other well known eviction policies
include LFU, FIFO, RANDOM. There has been plethora of work (Jiang and Zhang,
2002; Megiddo and Modha, 2003; Tanenbaum, 2001; Arlitt et al., 2000; Beckmann
et al., 2018; Cao and Irani, 1997; Jaleel et al., 2010) on improving cache hit
probabilities in the literature. In order to gauge the potential effectiveness
of these eviction policies, an upper bound on maximum achievable cache hit
probability for a given cache capacity has been widely adopted (Arlitt et al.,
2000).

###  1.1. Offline upper bound

For equal size object, Bélády’s algorithm or MIN (Aho et al., 1971) has been
widely used as an upper bound for cache hit probability among all feasible on
demand and online caching policies, togetherly known as _non-anticipative_
policies. However, Bélády’s algorithm is an offline algorithm, i.e., it
assumes exact knowledge of future requests. Offline upper bounds on object hit
probability have been proposed for variable (different) size object (Berger et
al., 2018). Often system designers do not have access to the exact request
trace, but can estimate the statistical properties of the object request
process such as the _inter-request time_ (irt) distribution. Also, caching
studies typically include model driven simulations. Thus the following natural
question arises. With limited knowledge of the object arrival process and no
look ahead option, can we provide an upper bound on the cache hit probability
for any feasible online caching policy?

###  1.2. Our Approach: Hazard Rate based upper bound

When object requests follow the Independent Reference Model (IRM), i.e., when
objects are referenced independently with fixed probabilities, ideal Least-
Frequently Used (LFU) caching policy is asymptotically optimal in terms of
object hit probability. However, general request processes are more complex
and correlated.

In this work, we assume a larger class of statistical models for object
reference streams, see Section 2.1 and Section 2.2 for more details. We also
assume that the hazard rate (HR) function (or conditional intensity)
associated with this point process is well defined and can be computed at all
points of time $t$. Here, the HR function is the conditional density of the
occurrence of an object request at time $t$, given the realization of the
request process over the interval $[0,t)$ (Daley and Vere-Jones, 2003).

We now propose the HR based upper bound as follows. When objects have equal
size, at any time $t$ we determine the HR values of each object and place in
the cache the $B$ objects which have the largest HR values. When objects have
different sizes, we sort the objects according to the ratio of their HR values
at time $t$ to their sizes in decreasing order. Note that, an ideal LFU policy
keeps track of number of times an object is referenced and order them
accordingly in the cache. Similarly, in our upper bound, we keep an ordered
list but on the basis of ratio of HR values to object sizes. We then place in
the cache the objects with the largest ratios till the cache capacity is
exhausted. We emphasize that we do not provide new caching policies that would
outperform all other policies but instead we provide various upper bounds on
the cache hit probability.

Our contributions are summarized below:

  1. (1)

We present a new upper bound for cache hit probability among all non-
anticipative caching policies:

     * •

When objects have equal sizes, a simple HR based ordering for the objects
provides an upper bound on cache hit probability.

     * •

For variable size objects, we order the objects with respect to the ratio of
their HR function values to their objects sizes and provide upper bounds on
the byte and object hit probabilities.

  2. (2)

We derive closed form expressions for the upper bound under some specific
object request arrival processes.

  3. (3)

We evaluate and compare the HR based upper bound with different cache
replacement policies for both synthetic and real world traces.

The rest of this paper is organized as follows. In Section 2 we formally
present the HR based upper bound for equal size objects. In Section 3 we
develop HR based upper bound for variable size objects. We discuss the HR
based upper bound for specific object request arrival processes in Section 4.
We perform simulation experiments to compare HR based upper bound with other
policies in Section 5. Finally, the conclusion of this work and potential
future works are given in Section 7.

##  2\. Equal Size Objects

We consider a cache of capacity $B$ serving $n$ distinct equal size objects.
Without loss of generality we assume that all objects have size one. Later in
Section 3, we also consider objects with different sizes. Let
$\mathcal{D}=\\{1,\cdots,n\\}$ be the set of objects. We denote by
$\mathbb{N}=\\{0,1,2,\ldots\\}$ the set of all nonnegative integers,
$\mathbb{N}^{*}=\mathbb{N}-\\{0\\}$, and by $\mathbb{Z}=\\{0,\pm 1,\pm
2,\ldots\\}$ the set of all integers.

###  2.1. Number of Hits for General object Arrival Processes

Let $\\{0<T_{i,1}<T_{i,2}<\cdots\\}$ be the successive time epochs when object
$i$ is requested. Assume $\\{T_{i,k}\\}_{k}$ is a regular point process (Daley
and Vere-Jones, 2003). Define $X_{i,k}=T_{i,k}-T_{i,k-1}$ for $k\geq 2$ and
$X_{i,1}=T_{i,1}$. Let $\\{0<T_{1}<T_{2}<\cdots\\}$ be the point process
resulting from the superposition of the point processes $\\{T_{i,k}\\}_{k}$,
$i=1,\ldots,n$. For $t>0$, define
$\mathcal{H}_{i,t}=\\{T_{i,k},k\in\mathbb{N}^{*}:T_{i,k}<t\\}$ the history of
the point process $\\{T_{i,k}\\}_{k}$ up to time $t$ and
$\mathcal{H}_{t}=\cup_{i=1}^{n}\mathcal{H}_{i,t}$ the entire history of all
point processes $\\{T_{1,k}\\}_{k},\ldots,\\{T_{n,k}\\}_{k}$ up to time $t$.
Notice that $\mathcal{H}_{i,t}$ is left-continuous for all $i$ and so is
$\mathcal{H}_{t}$. In particular, $T_{k}\not\in\mathcal{H}_{T_{k}}$ for all
$k$. Define $k_{i}(t)=\max\\{k\geq 1:T_{i,k-1}<t\\}$, so that exactly
$k_{i}(t)-1$ requests for object $i$ have been made in $[0,t)$.

Assume that the request object processes $\\{T_{i,k}\\}_{k}$, $i=1,\ldots,n$,
are conditionally independent $\forall t>0$, in the sense that

(1)
$\displaystyle\mathbb{P}(T_{1,k_{1}(t)}\geq\,t_{1},\cdots,T_{n,k_{n}(t)}\geq\,t_{n}\,|\,\mathcal{H}_{t})=\prod_{i=1}^{n}\mathbb{P}(T_{i,k_{i}(t)}\geq\,t_{i}\,|\,\mathcal{H}_{i,t}),$

for all $t_{1}\geq t,\ldots,t_{n}\geq t$.

Given $T_{i,k}=t_{i,k}$ for $k\geq 1$, the hazard rate function of
$\\{T_{i,k}\\}_{k}$ at time $t$ is defined by the piecewise function (Daley
and Vere-Jones, 2003, Definition 7.2.II, p. 231)

(4)
$\displaystyle\lambda^{*}_{i}(t)=\left\\{\begin{array}[]{ll}\frac{\frac{d}{dt}P(X_{i,1}<t)}{P(X_{i,1}>t)}&\mbox{for
$0<t\leq t_{i,1}$,}\\\
\frac{\frac{d}{dt}P(X_{i,k}<t-t_{i,k-1}\,|\,T_{i,j}=t_{i,j},j\leq
k-1)}{P(X_{i,k}>t-t_{i,k-1}\,|\,T_{i,j}=t_{i,j},j\leq k-1)}&\mbox{for
$t_{i,k-1}<t\leq t_{i,k}$, $k\geq 2$.}\\\ \end{array}\right.$

In (4) the existence of $\frac{d}{dt}P(X_{i,1}<t)$ and
$\frac{d}{dt}P(X_{i,k}<t-t_{i,k-1}\,|\,T_{i,j}=t_{i,j},j\leq k-1)$ for $k\geq
2$, follows from the assumption that $\\{T_{i,k}\\}_{k}$ is a regular point
process (Daley and Vere-Jones, 2003).

We assume that the cache is empty at time $t=0$ to avoid unnecessary
notational complexity but all results in the paper hold without this
assumption as long as the state of the cache is known at time $t=0$. A caching
policy $\pi$ determines at any time $t$ which $B$ objects among the $n$
available objects are cached. Formally, $\pi$ is a measurable deterministic
mapping from $\mathbb{R}\times(\mathbb{R}\times\mathbb{R})^{\infty}\to S_{B}$,
where $S_{B}$ is the set of subsets of $\\{1,\ldots,n\\}$ which contain $B$
elements. In this setting, $\pi(t,\mathcal{H}_{t})$ gives the $B$ objects that
are cached at time $t$ based on the knowledge of the overall request process
up to $t$. Let $\Pi$ be the collection of all such policies. Note that
policies in $\Pi$ are non-anticipative policies, in the sense that they do not
know when future requests will occur.

We will only consider deterministic policies although the setting can easily
be extended to random policies (in this case
$\pi:\mathbb{R}\times(\mathbb{R}\times\mathbb{R})^{\infty}\to\mathcal{Q}(S_{B})$
where $\mathcal{Q}(S_{B})$ is the set of probability distributions on
$S_{B}$).

We introduce the hazard rate (HR) based rule for equal-size objects,
abbreviated as HR-E. At any time $t$ and given $\mathcal{H}_{t}$, HR-E (i)
determines the hazard rate function of each object and (ii) places in the
cache the $B$ documents which have the largest hazard rate functions, i.e. if
$\lambda^{*}_{i_{1}}(t)\geq\cdots\geq\lambda^{*}_{i_{n}}(t)$ then objects
$i_{1},\ldots,i_{B}$ are cached at time $t$ (ties between equal rates are
broken randomly). We call it a rule, not a policy and will use it as a way to
upper-bound various performance metrics (see next), which is the goal of this
paper.

Let $B^{\pi}_{k}\in S_{B}$ be the state of the cache just before time $T_{k}$
(sometimes abbreviated to $T_{k}-$) under $\pi$. Call $R_{k}$ the object
requested at time $T_{k}$ under $\pi$ and define

(5) $H^{\pi}_{k}={\bf 1}(R_{k}\in B^{\pi}_{k}),$

i.e., $H^{\pi}_{k}=1$ if the $k$-th requested object is in the cache and
$H^{\pi}_{k}=0$ otherwise. Denote by $N^{\pi}_{K}=\sum_{k=1}^{K}H^{\pi}_{k}$
the number of hits during the first $K$ requests for an object.

The following lemma holds,

###### Lemma 0 (Expected number of hits).

(6)
$\mathbb{E}\left[N^{HR-E}_{K}\right]\geq\mathbb{E}\left[N^{\pi}_{K}\right],\quad\forall\pi\in\Pi,\;\forall
K\geq 1.$

###### Proof.

Fix $\pi\in\Pi$. Given that a request for an object is made at time $t$ and
given that the history $\mathcal{H}_{t}$ is known, this request is for object
$i$ with the probability

(7) $p_{i}(t)=\frac{\lambda^{*}_{i}(t)}{\sum_{j=1}^{n}\lambda^{*}_{j}(t)},$

Proof of (7) is given in the Appendix 8.1. This result relies on the
conditional independence of the point processes $\\{T_{i,k},k=1,2,\ldots\\}$,
$i=1,\ldots,n$. Observe that $p_{i}(t)$ does not depend on the caching policy
in use.

By the definition of the HR-E policy

$\sum_{i\in B^{HR-E}_{k}}\lambda^{*}_{i}(T_{k})\geq\sum_{i\in
B^{\pi}_{k}}\lambda^{*}_{i}(T_{k}),$

for $k=1,2,\ldots$. Therefore, for $k\geq 1$,

(8)
$\displaystyle\mathbb{E}\left[H^{HR-E}_{k}\,|\,\mathcal{H}_{T_{k}}\right]=\sum_{i\in
B^{HR-E}_{k}}\frac{\lambda^{*}_{i}(T_{k})}{\sum_{j=1}^{n}\lambda^{*}_{j}(T_{k})}\geq\sum_{i\in
B^{\pi}_{k}}\frac{\lambda^{*}_{i}(T_{k})}{\sum_{j=1}^{n}\lambda^{*}_{j}(T_{k})}=\mathbb{E}\left[H^{\pi}_{k}\,|\,\mathcal{H}_{T_{k}}\right].$

Taking expectation on both sides of (8) to remove the conditioning yields
$\mathbb{E}\left[H^{HR-E}_{k}\right]\leq\mathbb{E}\left[H^{\pi}_{k}\right]$.
Summing both sides of the latter inequality for $k=1,\ldots,K$ gives (6) from
the definition of $N^{\pi}_{K}$. ∎

It is worth noting that Lemma 1 holds for any non-stationary request object
processes. We now study a more specific request arrival process and derive an
upper bound on the object hit probability.

###  2.2. Upper Bound on the Hit Probability for Stationary and Ergodic Object
Arrival Processes

Let $\\{\cdots<T_{i,-1}<T_{i,0}\leq 0<T_{i,1}<\cdots\\}$ be the successive
time epochs when object $i$ is requested. Define $X_{i,k}=T_{i,k}-T_{i,k-1}$
and introduce the two-sided sequence $\\{X_{i,k},k\in\mathbb{Z}\\}$ of inter-
request times to object $i$. We assume that $\\{X_{i,k},k\in\mathbb{Z}\\}$ is
a stationary and ergodic sequence, and that $X_{i,k}$ has a finite mean given
by $\mathbb{E}[X_{i,k}]=\frac{1}{\lambda_{i}}$. We further assume that the
point processes $\\{T_{i,k},k\in\mathbb{Z}\\}$, $i=1,\ldots,n$, are mutually
independent.

Define the point process $\\{\cdots<T_{-1}<T_{0}<0\leq T_{1}<T_{2}<\cdots\\}$
obtained as the superposition of the $n$ point processes
$\\{T_{i,k},k\in\mathbb{Z}\\}$, $i=1,\ldots,n$, Define $X_{k}:=T_{k}-T_{k-1}$,
so that $\\{X_{k},k\in\mathbb{Z}\\}$ is the sequence of inter-request times
for the point process $\\{T_{k},k\in\mathbb{Z}\\}$.

The stationarity, ergodicity, and independence assumptions placed on point
processes $\\{T_{i,k},k\in\mathbb{Z}\\}$, $i=1,\ldots,n$, imply that the
sequence $\\{(X_{k},R_{k}),k\in\mathbb{Z}\\}$ is stationary and ergodic (see
e.g. (Baccelli and Brémaud, 2003, pp. 33-34)).

The stationary hit probability of policy $\pi\in\Pi$ is defined as (cf. (5))

(9)
$h^{\pi}=\lim_{K\to\infty}\frac{1}{K}\sum_{k=1}^{K}H^{\pi}_{k}\quad\hbox{a.s.,}$

whenever this limit exists.

For any $\pi\in\Pi$, there exists a measurable mapping $\varphi^{\pi}:(R\times
R)^{\infty}\to\\{0,1\\}$ such that
$H^{\pi}_{k}=\varphi^{\pi}((T_{j},R_{j}),j\leq k-1)$, which shows that the
sequence $\\{H^{\pi}_{k},k\in\mathbb{Z}\\}$ is stationary and ergodic (e.g.
see (Phillips, 1992, Thm p. 62)). The ergodic theorem then yields the
stationary hit probability (see e.g. (Kingman, 1968, Thm 1))

(10) $h^{\pi}=\mathbb{P}(H^{\pi}_{k}),$

under $\pi$. We are now in position to state and prove the main result of the
paper.

###### Theorem 2 (Stationary hit probability).

$h^{HR-E}\geq\max\limits_{\pi\in\Pi}h^{\pi}.$

###### Proof.

Taking the expectation on both sides of (9), using the fact that $h^{\pi}$ is
a constant from (10), and then invoking the dominated convergence theorem,
gives

(11)
$h^{\pi}=\lim_{K\to\infty}\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}[H^{\pi}_{k}]=\lim_{K\to\infty}\frac{\mathbb{E}[N^{\pi}_{K}]}{K},$

with $N^{\pi}_{K}=\sum_{k=1}^{K}H^{\pi}_{k}$ (see Section 2.1) the number of
hits in $[0,T_{K}]$ or, equivalently due to the stationary, the number of hits
in $K$ consecutive requests. Proof is concluded by using Lemma 1. ∎

###### Remark 1.

The computation of the HR-E based upper bound does not require the simulation
of any caching policy. At each request for an object, one can evaluate the HR
values for all objects. One can then treat the request $R_{k}$ as a hit if the
hazard rate of $R_{k}$ is among the top $B$ hazard rates at time $T_{k}$.

##  3\. Variable Size Objects

We now assume object $i$ has size $s_{i}\in\mathbb{R^{+}}$ for all
$i\in\mathcal{D}$ and the capacity of the cache is $B$ bytes.

###  3.1. Number of byte hits and fractional knapsack problem

The setting and assumptions are that of Section 2.1 but fractional caching
(FC) is now allowed. We denote by $\Pi_{FC}$ the set of all FC policies.

For $\pi\in\Pi_{FC}$, let $V^{\pi}_{k}$ denote the number of bytes served from
the cache at the $k$th request for an object. Let $x_{i,k}$ denote the
fraction of object $i$ in the cache at the time of the $k$-th request. Then
$V^{\pi}_{k}=s_{i}x^{\pi}_{i,k}$ if the request is for object $i$. Let
$W^{\pi}_{K}=\sum_{k=1}^{K}V^{\pi}_{k}$ denote the total number of bytes
served from the cache during the first $K$ requests for an object.

Given a request for an object is made at time $t$ and that the history
$\mathcal{H}_{t}$ is known, we have already observed (see (7)) that this
request is for object $i$ with the probability
$\lambda^{*}_{i}(t)/\sum_{j=1}^{n}\lambda^{*}_{j}(t)$. Therefore,

(12)
$\mathbbm{E}[V^{\pi}_{k}\,|\,\mathcal{H}_{T_{k}}]=\sum_{i=1}^{n}\mathbbm{E}[V^{\pi}_{k}\,|\,\mathcal{H}_{T_{k}},\text{object
$i$ is
requested}]\times\frac{\lambda^{*}_{i}(T_{k})}{\sum_{j=1}^{n}\lambda^{*}_{j}(T_{k})}=\frac{\sum_{i=1}^{n}s_{i}x^{\pi}_{i,k}\lambda^{*}_{i}(T_{k})}{\sum_{j=1}^{n}\lambda^{*}_{j}(T_{k})}.$

Our goal is to find $\pi\in\Pi_{FC}$ that maximizes
$\mathbbm{E}[V^{\pi}_{k}\,|\,\mathcal{H}_{T_{k}}]$ subject to the capacity
constraint on the size of the cache. This can be done by solving the
optimization problem,

(13a) $\displaystyle\max\quad$
$\displaystyle\sum\limits_{i=1}^{n}s_{i}x_{i}\lambda^{*}_{i}(t)$ (13b) subject
to $\displaystyle\sum\limits_{i=1}^{n}s_{i}x_{i}\leq B$ (13c) $\displaystyle
0\leq x_{i}\leq 1,\quad i=1,\cdots,n,$

which is nothing but the Fractional Knapsack Problem (FKP) (Goodrich and
Tamassia, 2002, Chapter 5.1). It is well known that its solution depends on
the respective values of the ratios
$s_{i}\lambda_{i}^{*}(t)/s_{i}=\lambda_{i}^{*}(t)$ for $i=1,\ldots,n$. More
specifically, assume that

(14)
$\displaystyle\lambda^{*}_{i_{1}}(t)\geq\lambda^{*}_{i_{2}}(t)\geq\cdots\geq\lambda^{*}_{i_{n}}(t),$

Then, the solution of (13) is given by $x_{i_{j}}=1$ for $1\leq j\leq
a:=\max\left\\{a:s_{i_{1}}+s_{i_{2}}+\cdots+s_{i_{a}}\leq B\right\\}$,
$x_{i_{a+1}}=(B-s_{i_{1}}-s_{i_{2}}-\cdots-s_{i_{a}})/s_{i_{a+1}}$, and
$x_{i_{j}}=0$ for $j=a+2,\ldots,n$.

Call HR-VB the rule which at any time $t$ places entirely in the cache objects
with the highest hazard rates until an object cannot fit; if object $k$ is the
first one that cannot entirely fit in the cache and objects
$i_{1},\ldots,i_{j}$ are already in the cache, then $B-\sum_{l=1}^{j}s_{l}$
bytes of object $k$ are cached. All other objects are not cached. Then, by
(12), for any policy $\pi\in\Pi_{FC}$,

$\mathbbm{E}[V^{HR-
VB}_{k}\,|\,\mathcal{H}_{T_{k}}]\geq\frac{\sum_{i=1}^{n}s_{i}x^{\pi}_{i,k}\lambda^{*}_{i}(T_{k})}{\sum_{j=1}^{n}\lambda^{*}_{j}(T_{k})}=\mathbbm{E}[V^{\pi}_{k}\,|\,\mathcal{H}_{T_{k}}].$

Removing the conditioning on $\mathcal{H}_{T_{k}}$ yields $\mathbbm{E}[V^{HR-
VB}_{k}]\geq\mathbbm{E}[V^{\pi}_{k}]$. Summing both sides of this inequality
for $k=1,\ldots,K$ gives

$\mathbbm{E}[W^{HR-VB}_{K}]\geq\mathbbm{E}[W^{\pi}_{K}].$

###  3.2. Number of object hits and $0$-$1$ knapsack problem

The setting and assumptions are still that of Section 2.1 but we now assume
that objects are indivisible (IC). In particular, every object hit counts the
same (i.e., a hit for a large 1GB object and hit for a small 10B object both
count as a ”hit”). Denote by $\Pi_{IC}$ the set of all IC policies. Recall the
definition of $H^{\pi}_{k}$ ($1$ if hit at $T_{k}$ and $0$ otherwise) and
$N^{\pi}_{K}$ (number of hits in first $K$ requests) under $\pi\in\Pi_{IC}$.

Fix $\pi\in\Pi_{IC}$. We have by using (7)

$\displaystyle\mathbbm{E}[H^{\pi}_{k}\,|\,\mathcal{H}_{T_{k}}]$
$\displaystyle=\sum_{i=1}^{n}\mathbbm{E}[H^{\pi}_{k}\,|\,\mathcal{H}_{T_{k}},\text{object
$i$ is requested at
$T_{k}$}]\times\frac{\lambda^{*}_{i}(T_{k})}{\sum_{j=1}^{n}\lambda^{*}_{j}(T_{k})}$
(15)
$\displaystyle=\frac{1}{\sum_{j=1}^{n}\lambda^{*}_{j}(T_{k})}\sum_{i=1}^{n}{\bf
1}(i\in B^{\pi}_{k})\lambda^{*}_{i}(T_{k}),$

where we recall that $B^{\pi}_{k}$ is the set of objects in the cache just
before $T_{k}$ under $\pi$.

Hence, $\mathbbm{E}[H^{\pi}_{k}\,|\,\mathcal{H}_{T_{k}}]$ can be maximized by
solving the following 0-1 knapsack problem (KP),

(16a) $\displaystyle\max\quad$
$\displaystyle\sum\limits_{i=1}^{n}x_{i}\lambda^{*}_{i}(t)$ (16b) subject to
$\displaystyle\sum\limits_{i=1}^{n}s_{i}x_{i}\leq B$ (16c) $\displaystyle
x_{i}\in\\{0,1\\},\quad i=1,\cdots,n.$

Solving KP is NP-hard. However, the solution to the corresponding relaxed
problem where the constraints in (16c) are replaced by $x_{i}\in[0,1]$ for
$i=1,\ldots,n$, serves as an upper bound for
$\sum_{i=1}^{n}x_{i}\lambda^{*}_{i}(t)$. The latter is achieved if the ratios
$\\{\lambda^{*}_{i}(t)/s_{i}\\}_{i}$ are arranged in decreasing order, say
$\lambda^{*}_{i_{1}}(t)/s_{i_{1}}\geq\cdots\geq\lambda^{*}_{i_{n}}(t)/s_{i_{n}}$
and $x_{i_{j}}=1$ for $1\leq j\leq a$ where $a$ is defined in Section 3.1,
$x_{i_{a+1}}=(B-s_{i_{1}}-s_{i_{2}}-\cdots-s_{i_{a}})/s_{i_{a+1}}$, and
$x_{i_{j}}=0$ for $j>a+1$ (Goodrich and Tamassia, 2002, Chapter 5.1).

Call HR-VC the rule which, at any time $t$, places in the cache the objects in
decreasing order of the ratios $\\{\lambda^{*}_{i}(t)/s_{i}\\}_{i}$ until an
object does not fit in the cache; if object $i_{a+1}$ is the first one that
cannot entirely fit in the cache and objects $i_{1},\ldots,i_{a}$ are already
in the cache, then with probability
$p_{i_{a+1}}=(B-s_{i_{1}}-s_{i_{2}}-\cdots-s_{i_{a}})/s_{i_{a+1}}$ object
$i_{a+1}$ is cached. All subsequent objects according to this decreasing
ordering are not cached. Note that HR-VC does not meet the cache size
constraint as there is not enough room in the cache to fit entirely object
$i_{a+1}$. However, as mentioned in Section 2, our goal is to upper bound
$\mathbb{E}[H^{\pi}_{k}]$ and $\mathbb{E}[N^{\pi}_{k}]$. Let
$x^{*}=(x^{*}_{1},\ldots,x^{*}_{n})$ be the solution of (16). We have

$\displaystyle\mathbbm{E}[H^{HR-VC}_{k}\,|\,\mathcal{H}_{T_{k}}]$
$\displaystyle=\frac{1}{\sum_{j=1}^{n}\lambda^{*}_{j}(T_{k})}\left[\sum_{j=1}^{a_{k}}\lambda^{*}_{i_{j}}(T_{k})+p_{i_{a_{k}+1}}\lambda^{*}_{i_{a_{k}+1}}(T_{k})\right]\quad$
$\displaystyle\geq\frac{1}{\sum_{j=1}^{n}\lambda^{*}_{j}(T_{k})}\sum\limits_{i=1}^{n}x^{*}_{i}\lambda^{*}_{i}(t)$
(17)
$\displaystyle\geq\frac{1}{\sum_{j=1}^{n}\lambda^{*}_{j}(T_{k})}\sum_{i=1}^{n}{\bf
1}(i\in
B^{\pi}_{k})\lambda^{*}_{i}(T_{k})=\mathbbm{E}[H^{\pi}_{k}\,|\,\mathcal{H}_{T_{k}}],$

with $a_{k}$ the last job that can be entirely cached at time $T_{k}-$
according to the decreasing ordering of the ratios
$\\{\lambda^{*}_{i}(T_{k})/s_{i}\\}_{i}$. Removing the conditioning on
$\mathcal{H}_{T_{k}}$ yields $\mathbbm{E}[H^{HR-
VC}_{k}]\geq\mathbbm{E}[H^{\pi}_{k}]$. Summing both sides of this inequality
for $k=1,\ldots,K$ gives

(18) $\displaystyle\mathbbm{E}[N^{HR-VC}_{K}]\geq\mathbbm{E}[N^{\pi}_{K}].$

###  3.3. Upper Bound on Object Hit Probability for Stationary and Ergodic
Object Arrival Processes

Using similar arguments as discussed in Section 2.2, one can define the object
hit probability under HR-VC (cf. Section 3.2) as

(19) $h^{HR-VC}=\lim_{K\to\infty}\frac{1}{K}\sum_{k=0}^{K-1}\mathbbm{E}[H^{HR-
VC}_{k}]=\lim_{K\to\infty}\frac{\mathbbm{E}[N^{HR-VC}_{K}]}{K},$

Now combining (18) and (19) we obtain

(20)
$h^{\pi}=\lim_{K\to\infty}\frac{\mathbb{E}[N^{\pi}_{K}]}{K}\leq\lim_{K\to\infty}\frac{\mathbbm{E}[N^{HR-
VC}_{K}]}{K}=h^{HR-VC}.$

##  4\. Specific Request Arrival Processes

Below we consider four specific object request processes each with equal size,
some of which explicitly account for the temporal locality in requests for
objects. Note that unlike in Sections 4.1, 4.2, 4.4 (Poisson, on-off, shot
noise) requests to different objects are correlated in Section 4.3 (MMPP).

###  4.1. Poisson Process

We consider the case when successive requests to object $i$ ($i=1,\ldots,n$)
occur according to a Poisson process with rate $\lambda_{i}>0$ and these $n$
Poisson processes are mutually independent. This is the standard Independence
Reference Model (see Section 1.2) where references to all objects are
independent rvs. Without loss of generality assume that
$\lambda_{1}\geq\cdots\geq\lambda_{n}$.

Under HR , at any time only objects $1,\ldots,B$ are in the cache. Therefore,
the hit probability $h^{HR}_{i}$ for object $i$ is $h^{HR}_{i}={\bf 1}(i\leq
B)$ and the hit rate $r^{HR}_{i}$ for object $i$ is
$r^{HR}_{i}=\lambda_{i}{\bf 1}(i\leq B)$. The overall hit probability $h^{HR}$
and hit rate $r^{HR}$ are given by

$h^{HR}=\frac{1}{\Lambda}\sum_{i=1}^{B}\lambda_{i},\quad
r^{HR}=\sum_{i=1}^{B}\lambda_{i},$

where $\Lambda:=\sum_{i=1}^{n}\lambda_{i}$.

###  4.2. On-Off Request Process

Figure 1. On-Off Request Process

The object popularity dynamics in caching systems can be effectively captured
by using a stationary, on-off traffic model (Garetto et al., 2015). More
specifically, we assume that successive requests to object $i$ occur according
to a Poisson process with rate $\lambda_{i}>0$ when the underlying on-off
process depicted in Figure 1 is in state $1$ ($X_{i}=1$) and that no request
occurs when this process is in state $0$ ($X_{i}=0$). The stationary
distribution of this on-off process is given by
$\boldsymbol{\pi}_{i}:=[\pi_{i,0},\pi_{i,1}]=[\beta_{i}/(\alpha_{i}+\beta_{i}),\alpha_{i}/(\alpha_{i}+\beta_{i})]$.
We assume that these $n$ on-off processes are mutually independent. Without
loss of generality, assume that
$\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{n}$ and define
$\Lambda=\sum_{i=1}^{n}\lambda_{i}$. Below, we derive expressions for the hit
rate and hit probability under HR.

Due to the way HR behaves, we may assume without loss of generality that
object $i$ is never in the cache when $X_{i}=0$. With this, at any time at
most $B$ of the most popular objects are in the cache among all objects whose
associated on-off process is in state $1$. Therefore, if $i>B$ the hit
probability $h_{i}^{HR}$ for object $i$ is given by

$\displaystyle h^{HR}_{i}$ $\displaystyle=\mathbb{P}(\text{at most $B-1$ on-
off processes are in state $1$ among on-off processes $1,\ldots,i-1$})$
$\displaystyle=\sum_{k=0}^{B-1}\mathbb{P}(\text{exactly $k$ on-off processes
are in state $1$ among on-off processes $1,\ldots,i-1$})$
$\displaystyle=\sum_{k=0}^{B-1}\sum_{i_{1},\ldots,i_{k}\in\\{1,2,\ldots,i-1\\}\atop
i_{1}<i_{2}<\cdots<i_{k}}\prod_{l=1}^{k}\pi_{i_{l},1}\prod_{m\in\\{1,\ldots,i-1\\}-(i_{1},\ldots,i_{k})}\pi_{i_{m},0},$

and $h^{HR}_{i}=1$ if $i\leq B$. The hit rate $r^{HR}_{i}$ for object $i$ is
$r^{HR}_{i}=\lambda_{i}\pi_{i,1}h^{HR}_{i}$.

The overall hit probability $h^{HR}$ and the overall hit rate $r^{HR}$ are
given by

(21)
$h^{HR}=\sum_{i=1}^{n}\frac{\lambda_{i}\pi_{i,1}}{\sum_{j=1}^{n}\lambda_{j}\pi_{j,1}}h^{HR}_{i}\quad\hbox{and}\quad
r^{HR}=h^{HR}\sum_{i=1}^{n}\lambda_{i}\pi_{i,1}.$

Assume that the ratios $\alpha_{i}/(\alpha_{i}+\beta_{i})$ and
$\beta_{i}/(\alpha_{i}+\beta_{i})$ do not depend on $i$ and define
$\rho=\alpha_{i}/(\alpha_{i}+\beta_{i})$ for all $i$. This occurs, for
instance, if all $n$ on-off processes have the same transition rates with
$\alpha_{i}=\alpha$ and $\beta_{i}=\beta$ or if $\alpha_{i}=\alpha\theta_{i}$
and $\beta_{i}=\beta\theta_{i}$ for all $i$. Then, for $i>B$,

$\displaystyle h^{HR}_{i}$
$\displaystyle=\sum_{k=0}^{B-1}\sum_{i_{1},\ldots,i_{k}\in\\{1,2,\ldots,i-1\\}\atop
i_{1}<i_{2}<\cdots<i_{k}}\rho^{k}(1-\rho)^{i-1-k}=(1-\rho)^{i-1}\sum_{k=0}^{B-1}\left(\frac{\rho}{1-\rho}\right)^{k}{i-1\choose
k},$

so that

$h^{HR}=\frac{\sum_{i=1}^{B}\lambda_{i}}{\Lambda}+\frac{1}{\Lambda}\sum_{i=B+1}^{n}\lambda_{i}(1-\rho)^{i-1}\sum_{k=0}^{B-1}\left(\frac{\rho}{1-\rho}\right)^{k}{i-1\choose
k},$

and
$r^{HR}=\rho\sum_{i=1}^{B}\lambda_{i}+\rho\sum_{i=B+1}^{n}\lambda_{i}(1-\rho)^{i-1}\sum_{k=0}^{B-1}\left(\frac{\rho}{1-\rho}\right)^{k}{i-1\choose
k}$.

We now propose a recursive approach for computing the hit probability and the
hit rate with a much lower computational complexity than the general formulas
in (21).

The recursions are based on available objects in the catalog, starting from
the situation where only object $1$ is available, moving to the situation
where objects $1$ and $2$ are available, etc. up to the final situation where
all $n$ objects are available. Introduce the following variables,

$\displaystyle p_{l,k}$ $\displaystyle=\mathbb{P}[\text{cache occupancy is
}k\,|\,\text{catalog is composed of $l$ more popular objects}],$
$\displaystyle r_{l,k}$ $\displaystyle=\text{Hit rate when cache occupancy is
$k$ given catalog is composed of $l$ more popular objects }.$

When $l=1$ then $p_{1,0}=\pi_{1,0}$, $p_{1,1}=\pi_{1,1}$, $r_{1,0}=0$, and
$r_{1,1}=\lambda_{1}$ from our convention that object $1$ is not in the cache
when $X_{1}=0$. It is easy to verify that under HR the following recursions
hold true for the occupancy probabilities,

$\displaystyle p_{l,0}$ $\displaystyle=p_{l-1,0}\pi_{l,0},\quad l=2,\cdots,n,$
$\displaystyle p_{k,k}$ $\displaystyle=p_{k-1,k-1}\pi_{k,1},\quad
k=1,\ldots,B,$ $\displaystyle p_{l,k}$
$\displaystyle=p_{l-1,k-1}\pi_{l,1}+p_{l-1,k,}\pi_{l,0},\quad
0<k<\min(l,B),l=1,\cdots,n,$ (22) $\displaystyle p_{l,B}$
$\displaystyle=p_{l-1,B-1}\pi_{l,1}+p_{l-1,B},\quad l=B+1,\cdots,n.$

Similarly, the following recursions hold true for the hit rates,

$\displaystyle r_{l,0}$ $\displaystyle=0,\quad l=2,\cdots,n,$ $\displaystyle
r_{k,k}$ $\displaystyle=r_{k-1,k-1}+\lambda_{k},\quad k=2,\ldots B,$
$\displaystyle r_{l,k}$
$\displaystyle=\frac{p_{l-1,k-1}\pi_{l,1}(r_{l-1,k-1}+\lambda_{l})+p_{l-1,k}\pi_{l,0}r_{l-1,k}}{p_{l-1,k-1}\pi_{l,1}+p_{l-1,k}\pi_{l,0}},\quad
0<k<\min(l,B),l=1,\cdots,n,$ (23) $\displaystyle r_{l,B}$
$\displaystyle=\frac{p_{l-1,B-1}\pi_{l,1}(r_{l-1,B-1}+\lambda_{l})+p_{l-1,B}r_{l-1,B}}{p_{l-1,B-1}\pi_{l,1}+p_{l-1,B}},\quad
l=B+1,\cdots,n.$

Once the above recursions have been solved, the overall hit rate $r^{H}$ and
hit probability $h^{HR}$ under HR are given by

(24) $\displaystyle
r^{HR}=\sum\limits_{k=1}^{B}p_{n,k}r_{n,k}\quad\hbox{and}\quad
h^{HR}=\frac{r^{HR}}{\sum\limits_{l=1}^{n}\lambda_{l}\pi_{l,1}}.$

###  4.3. Markov Modulated Poisson Process

We assume that the environment is modulated by a stochastic process
$\\{X(t),t\geq 0\\}$ taking values in a denumerable set ${\mathcal{E}}$. Let
$0<t_{1}<t_{2}<\cdots$ be the successive jump times of the process
$\\{X(t)\\}_{t}$. We assume that $X(0)$ is known.

Let $0<T_{i,1}<T_{i,2}<\cdots<T_{i,k}<\cdots$ be the sucessive times when
object $i$ is requested for $k=1,2,\ldots$. We assume that (by convention
$T_{i,0}=0$ for all $i$)

$\displaystyle\mathbb{P}\left(T_{1,k}-T_{1,k-1}>y_{1},\ldots,T_{n,k}-T_{n,k-1}>y_{n}\,|\,T_{1,k-1},\ldots,T_{n,k-1},X(s),0\leq
s\leq\max_{1\leq i\leq n}(T_{i,k-1}+y_{i})\right)$ (25)
$\displaystyle=\prod_{i=1}^{n}\exp\left(-\int_{T_{i,k-1}}^{T_{i,k-1}+y_{i}}\lambda_{i}({X(s))}ds\right),$

with $\lambda_{i}(x)>0$ for all $i=1,\ldots,n$ and $x\in{\mathcal{E}}$.

In words, in $[t_{m},t_{m+1})$ the object request processes
$\\{T_{1,k}\\}_{k},\ldots,\\{T_{n,k}\\}_{k}$ are mutually independent Poisson
processes with intensities
$\lambda_{1}(X(t_{m})),\ldots,\lambda_{n}(X(t_{m}))$, respectively.

We assume that the cache policy knows the state of the environment at any
time. Given that a request is made at time $t$, the object requested at time
$t$ is object $i$ with the probability

(26) $p_{i}(t)=\frac{\lambda_{i}(x)}{\sum_{j=1}^{n}\lambda_{j}(x)},$

if $X(t)=x$.

We denote by ${\rm HR}$ the cache policy which at any time $t$ caches the $B$
objects with the largest $\lambda_{i}(X(t))$. Let $B_{k}^{\pi}$ denote the
state of the cache just before the $k$th object is requested at time $T_{k}$
under policy $\pi$.

Under $\pi$ there is a hit at time $T_{k}$ if the requested object is in the
cache ($H^{\pi}_{k}=1$) and a miss if not ($H^{\pi}_{k}=0$). Hence, under
$\pi$ the number of hits, $N^{\pi}_{K}$, after $K$ requests is
$N_{K}^{\pi}=\sum_{k=1}^{K}H^{\pi}_{k}$.

###### Lemma 0.

For any admissible caching policy $\pi$,

$\mathbb{E}[N^{\rm HR}_{K}]\geq\mathbb{E}[N^{\pi}_{K}],\quad\forall K\geq 1.$

Proof. Proof is given in Appendix 8.2.

Assume that $\\{X(t)\\}_{t}$ has a stationary distribution independent of its
initial state, denoted by $\\{\gamma(x),x\in{\mathcal{E}}\\}$. Let $h^{\pi}$
denote the stationary hit probability under $\pi$. We have

(27) $\displaystyle h^{\pi}$ $\displaystyle=$
$\displaystyle\lim_{k\to\infty}\mathbb{E}[H^{\pi}_{k}]=\lim_{k\to\infty}\sum_{x\in{\mathcal{E}}}\int_{t=0}^{\infty}dP(T_{k}<t|X(T_{k}-)=x)\mathbb{P}(X(T_{k}-)=x)\frac{\sum_{i\in
B_{k}^{\pi}}\lambda_{i}(x)}{\sum_{j=1}^{n}\lambda_{j}(x)}$ $\displaystyle=$
$\displaystyle\lim_{k\to\infty}\sum_{x\in{\mathcal{E}}}\mathbb{P}(X(T_{k}-)=x)\frac{\sum_{i\in
B_{k}^{\pi}}\lambda_{i}(x)}{\sum_{j=1}^{n}\lambda_{j}(x)}$ $\displaystyle=$
$\displaystyle\sum_{x\in{\mathcal{E}}}\gamma(x)\frac{\sum_{i\in
B^{\pi}}\lambda_{i}(x)}{\sum_{j=1}^{n}\lambda_{j}(x)},$

with $B^{\pi}$ the stationary version of $B^{\pi}_{k}$.

###### Theorem 2.

$h^{\rm HR}\geq\max_{\pi}h^{\pi}.$

Proof. Follows from (27) and $\sum_{i\in B^{\rm
HR}}\lambda_{i}(x)\geq\sum_{i\in B^{\pi}}\lambda_{i}(x)$ for all
$x\in{\mathcal{E}}$.

We also obtain the following analytic expression for hit probability for
hazard rate based upper bound,

(28) $\displaystyle h^{\rm
HR}=\sum_{x\in{\mathcal{E}}}\gamma(x)\frac{\sum_{i=1}^{B}\lambda_{[i]}(x)}{\sum_{j=1}^{n}\lambda_{j}(x)},$

where $\lambda_{[1]}(x)\geq\lambda_{[2]}(x)\geq\cdots\geq\lambda_{[n]}(x)$ for
all $x\in{\mathcal{E}}.$

###  4.4. Shot Noise Model

Another traffic model, named Shot Noise Model (SNM) (Traverso et al., 2015),
has been proposed to capture the temporal locality observed in real traffic in
caching systems e.g. in Video on Demand (VoD) systems. The primary idea of the
SNM is to represent the overall request process as the superposition of many
independent time inhomogeneous Poisson processes or shots, each referring to
an individual object. In particular, the request process for object $i$ is
described by an inhomogeneous Poisson process of instantaneous rate

(29) $\displaystyle\lambda_{i}^{inst}(t)=V_{i}\lambda_{i}(t-\tau_{i}),$

where $\tau_{i}$ is the time instant at which object $i$ is first requested,
$V_{i}$ denotes the expected number of requests generated by object $i$ and
$\lambda_{i}(x)$ is the popularity profile of object $i$ over time. It is easy
to check that the instantaneous hazard rate associated with object $i$ can be
calculated as

(30) $\displaystyle\lambda_{i}^{*}(t)=\lambda_{i}^{inst}(t),$

Thus the results from Sections 2.1 and 3.2 directly apply with
$\lambda_{i}^{*}(t)=\lambda_{i}^{inst}(t).$

##  5\. Numerical Results

Via simulations we compare the stationary object hit probabilities of various
online policies (Section 5.1.1) to that of our proposed upper bound – referred
to as HR (based) upper bound – to Bélády’s upper bound (BELADY) and to a third
bound (FOO – see Section 5.1.2). This is done for a number of arrival
processes of object requests (Section 5.1.3), for equal and different sized
objects (Section 5.1.4), and for several cache sizes. We first present the
experimental setup and then discuss the results.

###  5.1. Experimental setup

####  5.1.1. Investigated online policies

Several caching policies have been used to generate Figures 2-7. The well-
known LRU, FIFO, and RANDOM cache replacement policies discard the least
recently used items first, evicts objects in the order they were added, and
randomly selects an object and discards it to make space when necessary,
respectively. The STATIC policy keeps forever in the cache the $B$ objects
which have the largest arrival rates. Notice that the HR based bound and the
hit probability under STATIC are equal when successive requests for each
object follow a Poisson process (Section 4.1). We also consider the Greedy-
Dual-Size-Frequency (GDSF) policy (Cherkasova, 1998) which combines recency
with frequency and size to improve upon LRU. Last, the AdaptSize policy
(Berger et al., 2017) uses an adaptive size threshold with admission control
preferring admission of small sized objects.

####  5.1.2. Upper bounds on object hit probability

Aside our HR based upper bound which applies to both equal and variable sized
objects, two other upper bounds on the object hit probability proposed in
literature are used, Bélády’s offline upper bound (BELADY, Section 1.1) for
equal sized objects and a flow based offline optimal (FOO) (Berger et al.,
2018) for different sized objects. FOO upper bound is computed by representing
caching as a min-cost flow problem.

####  5.1.3. Arrival process of object requests in Figures 2-7

In each display in Figures 2-3, request processes for objects $i=1,\ldots,n$
are independent renewal processes with IRT distributions shown in Table 1.
More specifically, in Figure 2(a) (resp. Figures 2(b)-2(f)) the request
process for object $i=1,\ldots,n$ has an exponential IRT (resp. Generalized
Pareto, Uniform, Hyperexponential, Gamma, Erlang) with arrival rate
$\lambda_{i}$ drawn from a Zipf distribution with parameter $0.8$ (see last
column of Table 1); similarly, in Figure 3(a) (resp. Figures 3(b)-(c)) the IRT
has an exponential (resp. Generalized Pareto, Uniform) distribution with
arrival rate $\lambda_{i}$ drawn from a Zipf distribution with parameter
$0.8$.

Inter-request time | Hazard Rate | $\mathbb{P}(IRT_{i}<t)$ | Arr. rate $\lambda_{i}$ ($=1/\mathbb{E}[IRT_{i}]$)
---|---|---|---
distribution (IRT) |  |  | drawn from Zipf (0.8)
Exponential | CHR | $1-e^{-\lambda_{i}t}$ | $\lambda_{i}$
Generalized Pareto | DHR |  $1-(1+\frac{k_{i}t}{\sigma_{i}})^{-\frac{1}{k_{i}}}$, $k_{i}=0.48$ | $\frac{1-k_{i}}{\sigma_{i}}$
Hyperexponential⋆ | DHR | $1-\sum\limits_{j=1}^{2}p_{ji}e^{-\theta_{j,i}t}$ |
|  | $p_{1,i}+p_{2,i}=1$ | $\frac{1}{2\nu_{i}}$
|  | $p_{1,i}/\theta_{1,i}=p_{2,i}/\theta_{2,i}:=\nu_{i}$ |
|  | $SCV_{i}=\text{var}(IRT_{i})/\mathbb{E}[IRT_{i}]^{2}=2$ |
Uniform | IHR | $\frac{t}{b_{i}}$ | $\frac{2}{b_{i}}$
Gamma | DHR ($k_{i}<1$) |  $\frac{1}{\Gamma(k_{i})}\gamma(k_{i},\frac{t}{\theta_{i}})$, $k_{i}=0.5$ | $\frac{2}{\theta_{i}}$
Erlang | IHR |  $\frac{\gamma(k_{i},\mu_{i}t)}{(k_{i}-1)!}$, $k_{i}=0.2$ | $\frac{\mu_{i}}{2}$

Table 1. Inter-request time (IRT) distributions of the renewal request arrival
processes in Figures 2-3 and their properties (CHR = Constant hazard rate, IHR
= Increasing hazard rate, DHR = Decreasing hazard rate). ⋆Once arrival rate
$\frac{1}{2\nu_{i}}$ is known one finds
$p_{1,i}=(1-\sqrt{(SCV_{i}-1)/(SCV_{i}+1)})/2$ under the constraints.

In Figure 4(a)-(b) the arrival request process for object $i$ ($i=1,\ldots,n$)
is generated via an on-off process (see Section 4.2) and these $n$ on-off
processes are mutually independent. The transition rates for on-off process
$i$ are $\alpha_{i}=1/T_{OFF}$ and $\beta_{i}=1/T_{ON}$, with $T_{ON}=7$
(days) and $T_{OFF}=9T_{ON}$. The arrival rate $\lambda_{i}$ in the on-state
is given by $\lambda_{i}=V/T_{ON}$, where $V$ is drawn from a Pareto
distribution with pdf $f_{V}(v)=\beta V_{min}^{\beta}/v^{1+\beta}$,
$\mathbb{E}[V]=10$, and $\beta=2$ (Garetto et al., 2015).

In Figure 5 requests for objects are generated according to a two-state MMPP
(see Section 4.3). Without loss of generality (W.l.o.g.), call $1$ and $2$
these two states. Let $\alpha$ and $\beta$ be the state transition rate from
state $1$ to $2$ and from state $2$ to $1$, respectively. The stationary state
probabilities are $\gamma(1)=\beta/(\alpha+\beta)$ and
$\gamma(2)=\alpha/(\alpha+\beta).$ In the simulations, we took $\alpha=2\times
10^{-3}$ and $\beta=1.6\times 10^{-3}$. In state $j$, successive requests for
object $i$ are generated according to a Poisson process with rate
$\lambda_{i}(j)$ for $j=1,2$. In state $1$, we assume that object arrival
rates $\lambda_{i}(1),\ldots,\lambda_{n}(1)$ each follows a Zipf distribution
with parameter $0.8$; W.l.o.g assume that
$\lambda_{1}(1)>\lambda_{2}(1)>\cdots>\lambda_{n}(1)$. In state $2$, we assume
that object arrival rates are given by $\lambda_{i}(2)=\lambda_{n+1-i}(1)$ for
$i=1,\cdots,n$.

In Figure 6 requests for objects are generated by $n$ independent shot noise
processes (see Section 4.4). Objects belong to four different classes. Objects
in class $c$ ($c=1,\ldots,4$) become available in the system at times
$\tau_{1}(c)<\cdots<\tau_{n_{c}}(c)$ of a homogeneous Poisson process with
rate $\gamma_{c}=\mathbb{E}[V_{c}]/\mathbb{E}[L_{c}]$. The SNM associated with
the $i$th object of class $c$, which becomes available at time $\tau_{i}(c)$,
has intensity
$\lambda_{i}(t)=(V_{i}/\alpha_{c})e^{-(t-\tau_{i}(c))/\alpha_{c}}$, with
$\alpha_{c}=\frac{0.5}{0.8}\mathbb{E}[L_{c}]$ and where $V_{i}$ is chosen
according to a Poisson distribution with rate $\mathbb{E}[V_{c}]$. Values of
$\mathbb{E}[V_{c}]$ (expected number of requests for a class $c$ object) and
$\mathbb{E}[L_{c}]$ (expected lifespan of a class $c$ object) are given in
Table 2. This model has been obtained by the authors of (Traverso et al.,
2013) from their so-called Trace 1, which contains
$n=\sum_{c=1}^{4}n_{c}=143871$ objects (cf. $4$th column of Table 2).

Class id (c) | $\mathbb{E}[L_{c}]$ | $\mathbb{E}[V_{c}]$ | Catalog size ($n_{c}$)
---|---|---|---
Class 1 | $1.14$ | $86.4$ | $29481$
Class 2 | $3.36$ | $41.9$ | $45570$
Class 3 | $6.40$ | $59.5$ | $27435$
Class 4 | $10.53$ | $36.9$ | $41385$
Table 2. Parameters of the shot-noise models in Figure 6.

In Figure 7 we use requests from a Web access trace collected from a gateway
router at IBM research lab (Zerfos et al., 2013). We filter the trace such
that each object has been requested at least a hundred times. The filtered
trace contains $3.5\times 10^{6}$ requests with an object catalog of size
$n=5638$. Various parametric and non-parametric estimators have been developed
in the literature to estimate the hazard rate (Wang, 2005; Singpurwalla and
Wong, 1983). Here, we adopt a parametric estimator model and assume that the
inter-request times for each object are independent and identically
distributed non-negative random variables. Note that the Web and storage
traffic inter-request times and access patterns are well modeled by heavy-
tailed distributions (Downey, 2005; Gracia-Tinedo et al., 2015). Hence, we fit
the density of inter-request times of each object to a Generalized-Pareto
distribution using the maximum likelihood estimation technique and estimate
the hazard rate for each object accordingly.

####  5.1.4. Size of objects

Both objects of equal size and variable size are considered. In the former the
size of each object is equal to $1$ and in the latter the size of each object
is drawn independently according to a bounded Pareto distribution with Pareto
shape parameter $1.8$, minimum object size of $5$Mb and maximum object size of
$15$Mb. When all objects have same size the size of the cache is expressed in
number of objects and it is expressed in Mb when objects have different sizes.

###  5.2. Discussion

(a) Exponential (CHR)

(b) Generalized Pareto (DHR)

(c) Uniform (IHR)

(d) Hyperexponential (DHR)

(e) Gamma (DHR)

(f) Erlang (IHR)

Figure 2. Simulation results for HR based upper bound and various caching
policies under different inter request arrival distributions ($n=1000$, all
objects of size $1$).

As a general comment, we note from Figure 2-7 that, as expected, that the HR
based upper bound serves as an upper bound on the hit probability among all
online caching policies. Further comments are given below on each figure.

####  5.2.1. Figure 2: Renewal request processes and equal size objects

Request processes used to generate plots in Figure 2 are presented in Section
5.1.3. These plots are obtained for $1000$ objects and all objects have size
$1$. Notice (see discussion in Section 4.1) that results coincide in Figure
2(a) for the STATIC policy and the HR based upper bound when inter-request
times (IRTs) are exponential distributed. We observe that when IRTs are either
CHR or DHR, the HR based upper bound is much tighter than Bélády’s upper bound
and that both bounds are close when IRTs are IHR. STATIC consistently yields
the highest hit probability and is always close to the HR upper bound. For
exponential IRTs or, equivalently for the independence reference model, the
optimality of STATIC is well known (Liu et al., 1998).

####  5.2.2. Figure 3: Renewal request processes and variable size objects

Request processes used to generate plots in Figure 3 are presented in Section
5.1.3. Objects have variable sizes (see Section 5.1.4) and there are $100$
objects. We observe that when IRTs have exponential or Generalized Pareto
distributions the HR based upper bound is much tighter than the FOO upper
bound (Figure 3(a)-(b)) and that both bounds are close when IRTs are uniformly
distributed rvs (Figure 3(c)). For exponential and Generalized Pareto IRT
distributions the GDSF policy performs well (close to HR); one way of
interpreting the gap between HR (resp. FOO) and GDSF in Figure 3(c) is to say
that there is room for improvement in caching policy performance when IRTs are
uniformly distributed rvs.

(a) Exponential (CHR)

(b) Generalized Pareto (DHR)

(c) Uniform (IHR)

Figure 3. Simulation Results for HR based upper bound and various caching
policies under different inter request arrival distributions for variable
object sizes ($n=100$).

(a) Equal Size ($n=1000$)

(b) Variable Size ($n=100$)

Figure 4. Performance comparison under on-off request process

####  5.2.3. Figure 4: on-off request arrivals and equal/variable size objects

The parameters of the on-off process used to generate arrival times of
requests of object $i$ ($i=1,\ldots,n$) are given in Section 5.1.3. There are
$1000$ objects in the catalog for equal sized objects and $100$ objects for
variable sized objects. The average arrival rate for object $i$ is
$\lambda_{i}\pi_{i,1}$ with $\pi_{i,1}=\alpha_{i}/(\alpha_{i}+\beta_{i})$
(Section 4.2). The STATIC policy permanently stores in the cache the $B$
objects in decreasing order of $\\{\lambda_{i}\pi_{i,1}\\}_{i}$.

For equal sized objects (resp. variable size objects) the HR bound is tighter
than BELADY (resp. FOO) for low cache sizes whereas for higher cache sizes,
BELADY (resp. FOO) becomes tighter. LRU performs the best for both equal sized
and variable sized objects and STATIC policy performs the worst for equal
sized objects.

####  5.2.4. Figure 5: MMPP request arrivals and equal/variable size objects

The parameters of the two-state MMPP (states $1$ and $2$) used to generate
arrival times of requests are given in Section 5.1.3. There are $1000$ objects
in the catalog for equal sized objects and $100$ objects for variable sized
objects. The average arrival rates for object $i$ is
$\lambda_{i}(1)\gamma(1)+\lambda_{i}(2)\gamma(2)=(\lambda_{i}(1)\beta+\lambda_{i}(2)\alpha)/(\alpha+\beta)$.
The STATIC caching policy permanently stores in the cache the $B$ objects with
the highest average arrival rates.

Unlike in Figures 2-4, BELADY is tighter than the HR based upper bound for
equal sized objects (Figure 5(a)) but the latter upper bound is tighter than
the FOO upper bound for variable sized objects (Figure 5(b)). STATIC performs
the best among all online caching policies. Note that, in our simulations,
$\gamma(1)=\beta/(\alpha+\beta)$ and $\gamma(2)=\alpha/(\alpha+\beta)$ are
comparable. We postulate that the performance of STATIC will further improve
when $\gamma(1)\gg\gamma(2)$ or $\gamma(1)\ll\gamma(2).$ For example, when
$\gamma(1)\gg\gamma(2),\lambda_{i}^{STATIC}\sim\lambda_{i}(1)\gamma(1)$; in
this case the STATIC policy will permanently store the popular objects in
state $1$, thus always getting a hit when the MMPP is in state $1$.

(a) Equal Size ($n=1000$)

(b) Variable Size ($n=100$)

Figure 5. Performance comparison under two-state MMPP request arrivals

(a) Equal Size

(b) Variable Size

Figure 6. Performance comparison under shot noise model ($n=143871$).

####  5.2.5. Figure 6: Shot noise request arrivals and equal/variable size
objects

The parameters of the SNM used to generate Figure 5.2.5 are given in Section
5.1.3. For equal sized objects (Figure 5.2.5(a)) our proposed HR bound not
only upper bounds the hit probability for existing online caching policies but
also provides a tighter bound than the state-of-the-art BELADY. STATIC policy
performs the worst while LRU performs the best among all online policies. For
variable sized objects ((Figure 5.2.5(b)) AdaptSize performs the best and GDSF
and LRU have similar performance. The difference in the object hit probability
between the HR upper bound and AdaptSize suggests that there is room for
improvement in caching policy performance.

####  5.2.6. Figure 7: Real-world trace

Characteristics of the real-world trace and its application to the production
of Figure 7 are discussed in Section 5.1.3. Upper bounds on the object hit
probability obtained with HR and BELADY are almost identical. LRU performs the
best and STATIC the worst.

Figure 7. Performance comparison under real world data trace ($n=5638$).

##  6\. Related Literature

Many previous work has focused on improving cache hit probability for equal
size objects (Jiang and Zhang, 2002; Megiddo and Modha, 2003; Tanenbaum, 2001;
Arlitt et al., 2000; Cao and Irani, 1997; Jaleel et al., 2010). Also, many
other policies have been proposed for variable size objects, for example:
_Least Recently Used_ (LRU), _Greedy Dual Size Frequency Caching Policy_
(GDSF) (Cherkasova, 1998) and AdaptSize (Berger et al., 2017). The primary
objective of these policies is to improve object hit probability as opposed to
the byte hit probability. The optimal policy for equal size objects was first
proposed by Belady et al. (Aho et al., 1971). Belady’s algorithm uses exact
knowledge of future requests, hence an offline policy. When object requests
follow the IRM, LFU achieves the maximum hit probability for equal sized
objects (Liu et al., 1998). Computing optimal policy for variable object sizes
is known to be NP-hard (Chrobak et al., 2012). Belady’s algorithm serves as an
upper bound on cache hit probability among all online demand based caching
policies for equal size objects. For variable sized objects, upper bounds on
object hit probability have also been proposed. Examples include Infinite-Cap
(Abrams et al., 1995), Flow-based offline optimal (FOO) and Practical Flow-
based offline optimal (PFOO) (Berger et al., 2018) policies. One major issue
with all previous work is that the proposed upper bounds are offline, i.e.
they assume exact knowledge of future requests. In this work, we proposed an
online upper bound for both equal and variable sized objects with limited
knowledge on object arrival process.

##  7\. Conclusion

In this paper, we developed an upper bound on the cache hit probability for
non-anticipative caching policies with equal object sizes. We showed that
hazard rate associated with the object arrival process can be used to provide
this upper bound. Inspired by the results for equal size objects, we extended
the HR based argument to obtain an upper bound on the byte and object hit
probability for variable size objects solving a knapsack problem. We derived
closed form expressions for the upper bound under some specific object request
arrival processes. We showed that HR based upper bound is tighter for a
variety of object arrival processes than those analyzed in the literature.
Future directions include to analyze the prefetching cost associated with any
realizable hazard rate based caching policy.

## References

  * (1)
  * Abrams et al. (1995) Marc Abrams, Charles R. Standridge, Ghaleb Abdulla, Stephen Williams, and Edward A. Fox. 1995\.  Caching Proxies: Limitations and Potentials.  Technical Report. USA.
  * Aho et al. (1971) Alfred V. Aho, Peter J. Denning, and Jeffrey D. Ullman. 1971\.  Principles of Optimal Page Replacement.  J. ACM 18, 1 (1971), 80–93.
  * Almeida et al. (1996) Virgilio Almeida, Azer Bestavros, Mark Crovella, and Adriana de Oliveira. 1996.  Characterizing Reference Locality in the WWW. In 4th IEEE Conf. on Parallel and Distributed Information Systems (PDSI’96). 92–103.  DOI:https://doi.org/10.1109/pdis.1996.568672
  * Arlitt et al. (2000) Martin Arlitt, Ludmila Cherkasova, John Dilley, Rich Friedrich, and Tai Jin. 2000.  Evaluating content management techniques for web proxy caches, In ACM SIGMETRICS 2000.  Performance Evaluation Review 27, 4, 3–11.  DOI:https://doi.org/10.1145/346000.346003
  * Baccelli and Brémaud (2003) François Baccelli and Pierre Brémaud. 2003.  Elements of Queueing Theory.  Springer.
  * Beckmann et al. (2018) Nathan Beckmann, Haoxian Chen, and Asaf Cidon. 2018.  LHD : Improving Cache Hit Rate by Maximizing Hit Density Relative Size. In NSDI’18. 389–404.
  * Berger et al. (2018) Daniel S. Berger, Nathan Beckmann, and Mor Harchol-Balter. 2018\.  Practical Bounds on Optimal Caching with Variable Object Sizes.  POMACS 2, 2 (2018), 1–32.
  * Berger et al. (2017) Daniel S. Berger, Ramesh K. Sitaraman, and Mor Harchol-Balter. 2017.  AdaptSize: Orchestrating the Hot Object Memory Cache in a Content Delivery Network. In NSDI’17. 483–498.
  * Breslau et al. (1999) Lee Breslau, Pei Cao, Li Fan, Graham Phillips, and Scott Shenker. 1999.  Web caching and zipf-like distributions: Evidence and implications. In IEEE INFOCOM 1999, Vol. 1. 126–134.  DOI:https://doi.org/10.1109/INFCOM.1999.749260
  * Cao and Irani (1997) Pei Cao and Sandy Irani. 1997.  Cost-aware WWW proxy caching algorithms. In USENIX Symposium on Internet Technologies and Systems (USITS’97). 18.  http://portal.acm.org/citation.cfm?id=1267297
  * Cherkasova (1998) Ludmila Cherkasova. 1998\.  Improving WWW proxies performance with Greedy-Dual-Size-Frequency caching policy.  HP Laboratories Technical Report 98 -69 (1998).
  * Chrobak et al. (2012) Marek Chrobak, Gerhard J. Woeginger, Kazuhisa Makino, and Haifeng Xu. 2012.  Caching is hard-even in the fault model.  Algorithmica 63, 4 (2012), 781–794.  DOI:https://doi.org/10.1007/s00453-011-9502-9
  * Daley and Vere-Jones (2003) Daryl J. Daley and David Vere-Jones. 2003.  An Introduction to the Theory of Point Processes: Elementary Theory and Methods.  Springer (2003).
  * Downey (2005) Allen B. Downey. 2005\.  Lognormal and Pareto distributions in the Internet.  Computer Communications 28, 7 (2005), 790 – 801.  DOI:https://doi.org/10.1016/j.comcom.2004.11.001
  * Garetto et al. (2015) Michele Garetto, Emilio Leonardi, and Stefano Traverso. 2015\.  Efficient analysis of caching strategies under dynamic content popularity. In IEEE INFOCOM 2015. 2263–2271.
  * Goodrich and Tamassia (2002) Michael T. Goodrich and Roberto Tamassia. 2002.  Algorithm Design: Foundations, Analysis, and Internet Examples.  John Wiley $\&$ Sons.
  * Gracia-Tinedo et al. (2015) Raúl Gracia-Tinedo, Yongchao Tian, Josep Sampé, Hamza Harkous, John Lenton, Pedro García-López, Marc Sánchez-Artigas, and Marko Vukolic. 2015\.  Dissecting UbuntuOne: Autopsy of a global-scale personal cloud back-end. In Internet Measurement Conference (IMC’15). 155–168.  DOI:https://doi.org/10.1145/2815675.2815677
  * Jaleel et al. (2010) Aamer Jaleel, Kevin B. Theobald, Simon C. Steely, and Jr Joel. 2010.  High Performance Cache Replacement Using Re-Reference Interval Prediction (RRIP). In 37th Int. Symposium on Computer Architecture (ISCA’10). Saint Malo, France.
  * Jiang and Zhang (2002) Song Jiang and Xiaodong Zhang. 2002.  LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance, In ACM SIGMETRICS 2002.  Performance Evaluation Review 30, 1, 31–42.  DOI:https://doi.org/10.1145/511399.511340
  * Kingman (1968) John F. C. Kingman. 1968\.  The Ergodic Theory of Subadditive Stochastic Processes.  Journal of the Royal Statistical Society: Series B (Methodological) 30, 3 (1968), 499–510.  DOI:https://doi.org/10.1111/j.2517-6161.1968.tb00749.x
  * Liu et al. (1998) Zhen Liu, Philippe Nain, Nicolas Niclausse, and Don Towsley. 1998\.  Static Caching of Web Servers. In Multimedia Computing And Networking (MCNC’98), SPIE Press (Ed.). San Jose, CA, USA.
  * Megiddo and Modha (2003) Nimrod Megiddo and Dharmendra S. Modha. 2003.  ARC: A Self-Tuning, Low Overhead Replacement Cache. In FAST’03: 2nd USENIX Conference on File and Storage Technologies. 115–130.
  * Phillips (1992) Peter C.B. Phillips. 1992\.  Lectures on Stationary and Nonstationary Times Series. (1992).  http://korora.econ.yale.edu/phillips/teach/notes/1988-lectures.pdf.
  * Singpurwalla and Wong (1983) Nozer D. Singpurwalla and Man Yuen Wong. 1983.  Kernel estimators of the failure-rate function and density estimation: An analogy.  J. Amer. Statist. Assoc. 78, 382 (1983), 478–481.  DOI:https://doi.org/10.1080/01621459.1983.10478000
  * Tanenbaum (2001) Andews S. Tanenbaum. 2001\.  Modern Operating Systems.  Prentice Hall Press.
  * Traverso et al. (2013) Stefano Traverso, Mohamed Ahmed, Michele Garetto, Paolo Giaccone, Emilio Leonardi, and Saverio Niccolini. 2013.  Temporal locality in today’s content caching: Why it matters and how to model it.  Computer Communication Review 43, 5 (2013), 5–12.
  * Traverso et al. (2015) Stefano Traverso, Mohamed Ahmed, Michele Garetto, Paolo Giaccone, Emilio Leonardi, and Saverio Niccolini. 2015\.  Unravelling the Impact of Temporal and Geographical Locality in Content Caching Systems.  IEEE Transactions on Multimedia 17, 10 (2015), 1839–1854.  DOI:https://doi.org/10.1109/TMM.2015.2458043
  * Wang (2005) Jane-Ling Wang. 2005\.  Smoothing Hazard Rate.  Encyclopedia of Biostatistics (2nd ed.) 7 (2005), 4986–4997.
  * Zerfos et al. (2013) Petros Zerfos, Mudhakar Srivatsa, Hao Yu, David Dennerline, Hubertus Franke, and Dakshi Agrawal. 2013\.  Platform and Applications for Massive-scale Streaming Network Analytics.  IBM Journal for Research and Development: Special Edition on Massive Scale Analytics 57, 136 (2013), 1–11.

##  8\. Appendix

###  8.1. Proof of Equation (7)

We drop the argument $t$ in $k_{i}(t)$ (see definition at the beginning of
Section 2.1 as no confusion may occur.). We have

$p_{i}(t)=\mathbb{P}\left(T_{i,k_{i}}<T_{j,k_{j}},\forall
j\not=i\,|\,\mathcal{H}_{t},\min_{j=1,\ldots,n}T_{j,k_{j}}=t\right).$

For $h>0$

$\displaystyle\mathbb{P}\bigg{(}T_{i,k_{i}}\in(t,t+h),T_{j,k_{j}}>t+h,\forall
j\not=i\,\bigg{|}\mathcal{H}_{t},\min_{j=1,\ldots,n}T_{j,k_{j}}\in(t,t+h)\bigg{)}$
(31)
$\displaystyle=\frac{\mathbb{P}\left(T_{i,k_{i}}\in(t,t+h),T_{j,k_{j}}>t+h,\forall
j\not=i\,|\,\mathcal{H}_{t}\right)}{\mathbb{P}\left(\min_{j=1,\ldots,n}T_{j,k_{j}}\in(t,t+h)\,|\,\mathcal{H}_{t}\right)}=\frac{\mathbb{P}(T_{i,k_{i}}\in(t,h)\,|\,\mathcal{H}_{i,t})\prod_{1\leq
j\leq n\atop
j\not=i}\mathbb{P}(T_{j,k_{j}}>t+h\,|\,\mathcal{H}_{j,t})}{\mathbb{P}\left(\min_{j=1,\ldots,n}T_{j,k_{j}}\in(t,t+h)\,|\,\mathcal{H}_{t}\right)},$

from the conditional independence assumption in (1). Let us focus on the
denominator in (31). It can be written as

$\displaystyle\mathbb{P}\left(\min_{j=1,\ldots,n}T_{j,k_{j}}\in(t,t+h)\,|\,\mathcal{H}_{t}\right)=\sum_{j=1}^{n}\mathbb{P}(T_{j,k_{j}}\in(t,t+h)>t+h,\forall
l\not=j\,|\,H_{t})+f(h),$

with $f(h)\to 0$ as $h\to 0$, since as $h\to 0$ there can be at least one
random variables (rvs) located in $(t,t+h)$ among the rvs
$T_{1,k_{1}},\ldots,T_{n,k_{n}}$ since these rvs are continous. Therefore,

$\displaystyle\mathbb{P}\bigg{(}T_{i,k_{i}}\in(t,t+h),T_{j,k_{j}}>t+h,\forall
j\not=i\bigg{|}\,\mathcal{H}_{t},\min_{j=1,\ldots,n}T_{j,k_{j}}\in(t,t+h)\bigg{)}$
$\displaystyle=\frac{\mathbb{P}(T_{i,k_{i}}\in(t,h)\,|\,\mathcal{H}_{i,t})\prod_{1\leq
j\leq n\atop
j\not=i}\mathbb{P}(T_{j,k_{j}}>t+h\,|\,\mathcal{H}_{j,t})}{\sum_{j=1}^{n}\mathbb{P}(T_{j,k_{j}}\in(t,d+t),T_{l,k_{l}}>t+h,\forall
l\not=j\,|\,H_{t})+f(h)}$
$\displaystyle=\mathbb{P}(T_{i,k_{i}}\in(t,h)\,|\,\mathcal{H}_{i,t})\prod_{1\leq
j\leq n\atop j\not=i}\mathbb{P}(T_{j,k_{j}}>t+h\,|\,\mathcal{H}_{j,t})$ (33)
$\displaystyle\times\Biggl{(}\sum_{j=1}^{n}\mathbb{P}(T_{j,k_{j}}\in(t,t+h)\,|\,\mathcal{H}_{l,t})\times\prod_{1\leq
l\leq n\atop
l\not=j}\mathbb{P}(T_{l,k_{l}}>t+h\,|\,\mathcal{H}_{l,t})+f(h)\Biggr{)}^{-1}$
(34)
$\displaystyle=\frac{\frac{\mathbb{P}(T_{i,k_{i}}\in(t,t+h)\,|\,\mathcal{H}_{i,t})}{\mathbb{P}(T_{i,k_{i}}>t+h\,|\,\mathcal{H}_{i,t})}}{\sum_{j=1}^{n}\frac{\mathbb{P}(T_{j,k_{j}}\in(t,t+h)\,|\,\mathcal{H}_{l,t})}{\mathbb{P}(T_{j,k_{j}}>t+h\,|\,\mathcal{H}_{l,t})}+f(h)}=\frac{\lambda^{*}_{i}(t+h)}{\sum_{j=1}^{n}\lambda^{*}_{j}(t+h)+f(h)},$

where (33) follows from (1) and (34) follows from (4). Letting $h\to 0$ in
(34) gives (7).

###  8.2. Proof of Lemma 1

Let $k\geq 1$. By definition of policy ${\rm HR}$

(35) $\sum_{i\in B_{k}^{\rm HR}}\lambda_{i}(X(T_{k}-))\geq\sum_{i\in
B_{k}^{\pi}}\lambda_{i}(X(T_{k}-)),$

since under ${\rm HR}$ the $B$ objects with the smallest
$\lambda_{i}(X(T_{k}-))$ are in the cache at time $T_{k}$. We have

$\displaystyle\mathbb{E}[H^{\rm HR}_{k}\,|\,T_{k}=t,X(T_{k}-)=x]$
$\displaystyle=$ $\displaystyle\frac{\sum_{i\in B_{k}^{\rm
HR}}\lambda_{i}(x)}{\sum_{j=1}^{n}\lambda_{j}(x)}$ $\displaystyle\geq$
$\displaystyle\frac{\sum_{i\in
B_{k}^{\pi}}\lambda_{i}(x)}{\sum_{j=1}^{n}\lambda_{j}(x)}\quad\hbox{from
}(\ref{inq})$ $\displaystyle=$
$\displaystyle\mathbb{E}[H^{\pi}_{k}\,|\,T_{k}=t,X(T_{k}-)=x].$

Removing the conditioning on $T_{k}$ and $x$ proves that

$\mathbb{E}[H^{\rm HR}_{k}]\geq\mathbb{E}[H^{\pi}_{k}].$

Hence,

$\mathbb{E}[N^{\rm HR}_{K}]=\sum_{k=1}^{K}\mathbb{E}[H^{\rm
HR}_{k}]\geq\sum_{k=1}^{K}\mathbb{E}[H^{\pi}_{k}]=\mathbb{E}[N^{\pi}_{K}].$