Optimal Local Storage Policy Based on Stochastic Intensities and Its Large-Scale Behavior

1. Introduction

In modern computing systems, a crucial component for improving performance at several layers is the use of a local memory, typically referred to as a cache. The rationale is that storing frequently used items at a readily available location can improve latency, reducing the cost of retrieval from a more remote location. This strategy is pervasive in computing systems: from local caching of instructions at the processor level to texture caching in graphics processing units, disk caching for quickly retrieving data from hard disks, content caching in web applications, geographically distributed caching in content delivery networks, and cloud storage gateways keeping readily available items stored in the cloud data centers.

A local memory consists of a certain amount of memory space that may store a subset of items locally and temporarily; the goal is to appropriately choose from a large catalog the subset of items more likely to be requested next. All of the aforementioned applications can be subsumed into this basic structure. In the case of homogeneous item sizes, the space constraint is reflected in the number of objects C that may be locally stored from the catalog of size $N\gg C$.

Classical analyses of local memory systems have focused on modeling the (discrete-time) sequence of item requests. Based on this empirical sequence, the system must determine which items are stored and which must be evicted from memory to make room for others. In a stationary regime, one natural strategy would be to store at all times the C items with the highest popularity measured by their mean intensity of requests; this simple static policy requires, however, popularities to be known. A practical approximation is the least frequently used (LFU) eviction policy; here, item request intensities are dynamically estimated from the arrival sequence, and the least popular ones are evicted. Under mild assumptions on stationary arrivals, LFU will eventually converge to the static policy.

A popular alternative is the least recently used (LRU) policy, which keeps in memory the C most recently requested items. Upon receiving a request, it will store the item if not already present, and in that case, it will evict the oldest item in the sequence of requests. This method is better suited to handle highly correlated demands, where a requested item is more likely to be fetched again (i.e., bursty request patterns). Smoother variants have been analyzed, and also, combinations of both approaches, such as Least Frequent Recently Used (cf. Bilal and Kang 2017), have been proposed. We review the relevant literature below.

A main drawback of the classical analysis is that relevant time (continuous-time) information is neglected; by focusing only on the sequence of requests, the models ignore interrequest times that are important characteristics of the request processes. An alternative approach that gives time the center stage is timer-based (time-to-live (TTL)) caching policies; here, items are stored upon request and evicted only after a certain amount of time has elapsed because their last appearance in the request stream. This is a common approach in internet-based systems, such as domain name system queries and web applications.

A crucial step toward incorporating time information is the seminal paper by Fofack et al. (2014), where the incoming request stream is assumed to be a stationary point process on the real line. The mean intensities of the underlying request processes for each item capture their relative popularity, whereas by modeling the interrequest times, we can express different types of behavior; for instance, heavy-tailed interrequest times are well adapted to bursty arrival patterns. This approach has led to new insights in the analysis of both replacement and timer-based caching policies, which we also review below.

Within this modeling framework, we ask a natural question. What is the optimal memory management policy? By this, we mean the one that maximizes the hit rate, which is the frequency of successful retrievals from local memory. In Ferragut et al. (2016, 2018), the optimality question for TTL caching policies was investigated; in particular, it was shown that if requests form a general stationary simple point process, optimality may be characterized by the hazard rate function of the interarrival distribution. Later, Panigrahy et al. (2022) analyzed optimal replacement policies (i.e., fixed memory systems), and they identified the optimal local storage policy in terms of the stochastic intensity, a generalization of the hazard rate function.

In this paper, our goal is to develop this connection more extensively, bringing to bear the machinery of stationary point processes as in Brémaud (2020) to formally characterize causal memory management policies and the condition for optimality, in particular for general stationary request processes and correlation structures. Subsequently, our aim is to understand the large-scale behavior of the optimal replacement policy for large N under some appropriate assumptions: namely, that request processes are independent and that interarrival times for different items are drawn from a scale family parametrized by a distribution of intensities that has an asymptotic limit. We characterize the optimal memory management as a threshold policy on the hazard rates observed by the system, and we prove that the threshold has a deterministic limit. We also obtain a closed expression for the optimal performance in the large-scale limit as a function of the fundamental parameters of the scale family and the popularity distribution. As a further contribution, we investigate the properties of threshold policies before the asymptotic limit, showing that under monotonicity of the hazard rate function, they become equivalent to timer-based policies. As a consequence, we obtain the convergence of the two types of policies (replacement or TTL) to a common optimum in the asymptotic limit, a striking connection between both approaches. Our results are illustrated by a series of parametric examples, and their properties are further exhibited through stochastic simulations.

1.1. Related Work

Being essential to modern computing systems, the performance analysis of caching and local memory management has a long history. The seminal work on replacement-based algorithms with a fixed memory size started in King (1971) and Gelenbe (1973). Despite its apparent simplicity, the analysis of replacement policies is complex, even for a single cache; King (1971) gives an explicit expression of the hit probability of the LRU policy with exponential complexity. In Gelenbe (1973), it is shown that under the so-called independent reference model (IRM) assumption, where requests are independent and identically distributed, replacement policies, such as first in, first out, achieve the same hit probability. Exact computation is, however, intractable. Dan and Towsley (1990) provide an approximate computational procedure. Their method has been further extended in Rosensweig et al. (2010) to the case of networks of cache systems. Also, in Gast and Houdt (2015), another approach is given for list-based replacement policies.

A related line of work that includes replacement policies is analyses based on the move-to-front (MTF) rule, which is equivalent to LRU. A first step in this direction is the work by Fill (1996), which addresses the limit cost of the move-to-front rule. By exploiting the connection between MTF and LRU, Jelenković (1999) and Jelenković and Radovanović (2008) provide asymptotic expressions for the hit probability under the IRM assumption and Zipf popularities with parameter $\beta$. With a fundamentally different approach, based on Laplace transforms, the same limit result is obtained in Barrera and Fontbona (2010). Our asymptotic limit assumptions are related to this latter approach. Few results on replacement policies move beyond the IRM assumptions, such as the works by Jelenković and Radovanović (2003, 2004) and Jelenković et al. (2006), which show some insensitivity properties of LRU in a large-scale regime and dependent requests. However, their approach is only valid for light-tailed popularities, and it is related to our result below on optimal performance for the nonuniformly integrable popularity limit. Extensions to a network of caches working cooperatively to optimize performance are proposed in Borst et al. (2010), Ioannidis et al. (2010), and Ioannidis and Yeh (2016).

Because exact analysis of LRU is difficult, the most popular technique for approximating its performance is the so-called “Che approximation” introduced in Che et al. (2002) for web caches. The crucial point is to define a characteristic time representing the average permanence time common to all files. This assumption is valid in a large-scale regime, and Fricker et al. (2012) perform a second-order analysis to explain why this is a good approximation.

On the other hand, the analysis of policies based on timers is more recent and associated with the growth of internet caches. A first contribution in this line is Jung et al. (2003), with expressions for the steady-state hit probabilities for web pages; this line of work was later extended in Bahat and Makowski (2005) to include update delay. However, a crucial contribution is the introduction of point process theory to capture request correlations and in particular, move beyond the sequence of requests to a continuous-time model with general arrival processes. The foundations for this approach were laid down in Fofack et al. (2012, 2014). In Berger et al. (2014), the analysis is extended to a family of TTL policies with the focus of approximating LRU performance in linear and tree networks, and a different policy is proposed in Berger et al. (2015) with the aim of maximizing hit ratios by variance reduction. In Bianchi et al. (2013), the Che approximation is analyzed in a more general setting, and in Martina et al. (2014), it is extended using TTL cache tools to renewal arrivals, showing good accuracy in the case of small caches and Zipf-law popularities and making the connection between replacement and timer-based policies. The fact that timer-based policies decouple the analysis over independent request streams has led to more amenable generalizations to the case of cache networks (Panigrahy et al. 2017, 2020; Dehghan et al. 2019).

The search for optimal policies with respect to the hit rate has received recent attention. In Ferragut et al. (2016, 2018), the problem of finding the optimal timer-based policy is formulated and related to the hazard rate function of the interrequest times. Using tools from convex optimization, Ferragut et al. (2016, 2018) show that decreasing hazard rates lead to a nontrivial timer-based policy that achieves optimality and characterize its large-scale behavior. However, more regular request traffic with increasing hazard rates does not benefit from caching at all, a striking result that highlights the role of traffic regularity in local memory management systems. More recently in Ferragut et al. (2024), a generalization of timer-based policies to consider prefetching was introduced, leading to a nontrivial optimal policy for increasing hazard rates. A parallel research line developed in Panigrahy et al. (2022) considers the optimality question for replacement-based policies; the structure of the optimal causal policy is identified, incorporating for the first time the notion of stochastic intensity of point processes, a generalization of the hazard rate function. The current paper builds on these immediate precursors.

1.2. Main Contributions

The first contribution of this paper is a general foundation for the problem of optimal causal policies for the local memory or caching problem. The setup is the same as the one considered in Panigrahy et al. (2022), but we provide here a more complete mathematical treatment within the framework of point processes in the real line following Brémaud (2020). In particular, this approach enables us to properly define predictable policies in terms of the underlying natural filtration of the involved processes, which is a key technical issue to be addressed in the proofs. We also aim at greater generality, determining the optimal causal policy for a general superposition of request processes, including the correlated case, as a function of stochastic intensities of the underlying request processes and their correlation structure. We then specialize this result to independent sources.

The second most significant part of the paper concerns the asymptotic behavior of the optimal policy under a large-scale regime (i.e., when the item catalog size goes to infinity). Assuming that the request processes for different items are independent with stochastic intensities from a common scale family and that their popularities have a limiting distribution, we prove that the optimal policy converges to a threshold policy in the stochastic intensities, with a deterministic threshold that follows closed-form expressions. Armed with this result, we characterize the limit of the optimal miss rate in large-scale systems through an explicit formula. Therefore, we provide a universal asymptotic bound on performance for any practical policy.

A third contribution concerns the behavior of deterministic threshold policies before the asymptotic limit; under renewal traffic and additional monotonicity assumptions of the hazard rate function of the interrequest times, it is shown that previously analyzed timer-based policies are, in fact, of the threshold type and in particular, that under renewal assumptions, the optimal timer policy for decreasing hazard rates identified in Ferragut et al. (2018) achieves the universal bound. For the dual case of increasing hazard rates, we further analyze the timer-based prefetching policy introduced in Ferragut et al. (2024) and prove that it also achieves the universal asymptotic bound.

Although the preceding theory is developed for the case of homogeneous item sizes, we also explore the generalization to the heterogeneous case.

In our simulations section, we extensively analyze certain concrete parametric examples that illustrate the theory and serve as a benchmark for classical caching policies in comparison with the optimal. Finally, we provide some remarks on the practical challenges in implementing the optimal policy.

1.3. Organization of the Paper

The paper is organized as follows. In Section 2, we lay out the main tools of point processes and stochastic intensities required to analyze our system. We then define our local memory model, establish the framework for causal policies, and characterize the optimal policy in Section 3. Our main theorem describing the large-scale limit is presented in Section 4, and the ensuing universal performance bound is presented in Section 5. In Section 6, we describe the connection between the optimal policy and timer-based policies. In Section 7, we discuss the extension of the results to heterogeneous item sizes. Simulations and examples are presented in Section 8, and conclusions are given in Section 9.

2. Preliminaries and Notation

Throughout this paper, we will consider stationary point processes defined on a common probability space $(\mathrm{\Omega },\mathcal{F},P)$. We recall now some basic concepts that will be useful in the following and introduce our notation; we refer the reader to Brémaud (2020) for a thorough treatment.

A simple and locally finite point process $\mathrm{\Phi }$ on the real line is a random and strictly increasing sequence of points $\mathrm{\Phi }={\{{\tau }_k\}}_{k\in \mathbb{Z}}$ satisfying ${\lim }_{k\to \pm \infty }{\tau }_k=\pm \infty$. More formally, $\mathrm{\Phi }$ can be cast as a random counting measure (i.e., $\mathrm{\Phi }={\sum }_k{\delta }_{{\tau }_k}$), a measurable map from $(\mathrm{\Omega },\mathcal{F})\to (M^{\#}(\mathbb{R}),{\mathcal{M}}^{\#}(\mathbb{R}))$. Here, $M^{\#}(\mathbb{R})$ is the space of locally finite measures on $\mathbb{R}$ taking values in $\mathbb{N}\cup \{\infty \}$, and ${\mathcal{M}}^{\#}(\mathbb{R})$ is the smallest $\sigma$-algebra such that for all Borel sets $B\in \mathcal{B}(\mathbb{R})$, $\mathrm{\Phi }(B)={\sum }_k{\mathbf{1}}_{\{{\tau }_k\in B\}}$ is measurable. Moreover, $\mathrm{\Phi }(B)$ is assumed to be finite for bounded B, and thus, it is a nonnegative integer-valued random variable. By definition, all points ${\tau }_k$ are different, and thus, $\mathrm{\Phi }(\{x\})⩽1$ P almost surely (a.s.) for all $x\in \mathbb{R}$. In order to label the points, we follow the usual convention (Brémaud 2020), where ${\tau }_0(\mathrm{\Phi })⩽0$ and ${\tau }_1(\mathrm{\Phi })>0$. With this convention, ${\tau }_0={\tau }_0(\mathrm{\Phi })$ represents the first point before the time origin of the process $\mathrm{\Phi }$.¹

Let $S_t(\mathrm{\Phi })$ denote the shift operator for measures in $\mathbb{R}$ (i.e., $S_t(\mathrm{\Phi })(B)≔\mathrm{\Phi }(B+t)$ for all Borel sets $B\subset \mathbb{R}$, where $B+t≔\{x+t:x\in B\}$). The point process $\mathrm{\Phi }$ is stationary if $S_t(\mathrm{\Phi })$ has the same distribution as $\mathrm{\Phi }$ for all $t\in \mathbb{R}$. The mean measure of the point process is $\lambda (B)≔\text{E}[\mathrm{\Phi }(B)]$. If the process is stationary, then this measure is translation invariant and thus, a multiple of the Lebesgue measure on $\mathbb{R}$ (i.e., $\lambda (B)=\lambda m(B)$). The constant $\lambda$ is called the (average) intensity of the stationary point process. In what follows, we assume $\lambda >0$ to avoid the trivial case where the process has no points.

For a simple stationary point process $\mathrm{\Phi }$, an important measure is the Palm probability $P_{\mathrm{\Phi }}^0$. This is a probability measure defined in $(\mathrm{\Omega },\mathcal{F})$ that captures the stochastic behavior of the point process when the observer is synchronized with it. In particular, $P_{\mathrm{\Phi }}^0({\tau }_0=0)=1$ (i.e., there is $P_{\mathrm{\Phi }}^0$-a.s. a point at the origin). We refer the reader to Brémaud (2020) for a formal definition.

The key relationship between the Palm probability and the stationary probability is the following inversion formula valid for any nonnegative real-valued measurable function $f:M^{\#}(\mathbb{R})\to {\mathbb{R}}_{+}$:

That is, in order to know the average value of a property in the stationary measure, we can integrate over one cycle of the process using the Palm measure and scale by $\lambda$.

The interarrival distribution of the point process $\mathrm{\Phi }$ is defined as $F_0(t)≔P_{\mathrm{\Phi }}^0({\tau }_1-{\tau }_0⩽t)=P_{\mathrm{\Phi }}^0({\tau }_1⩽t)$. Because the process is simple, $F_0$ has support in ${\mathbb{R}}_{+}$. Moreover, ${\text{E}}_{\mathrm{\Phi }}^0[{\tau }_1]=1/\lambda$, which follows from taking $f\equiv 1$ in (1).

A second important distribution is the age distribution, which is the age of the current interval when the process is observed at a point t not synchronized with it. Because the process is stationary, we can take without loss of generality $t=0$, and thus, the age distribution is just

a result that also follows from (1) with $f(\mathrm{\Phi })={\mathbf{1}}_{\{{\tau }_0(\mathrm{\Phi })⩾-t\}}$. Note that these distributions are different in general because of the bias toward larger intervals when sampling in the steady state. A depiction of this sampling effect is shown in Figure 1.

2.1. Stochastic Intensity

We now introduce the concept of stochastic intensity, which is crucial for the analysis in this paper. First, we need the following definition.

Definition 1.

A filtration ${\{{\mathcal{F}}_t\}}_{t\in \mathbb{R}}$ in $(\mathrm{\Omega },\mathcal{F})$ (i.e., an increasing family of $\sigma$-algebras contained in $\mathcal{F}$) is a history of the simple locally finite point process $\mathrm{\Phi }$ if $\mathrm{\Phi }((a,b])$ is ${\mathcal{F}}_t$ measurable for all $a<b⩽t$. The natural history of $\mathrm{\Phi }$ is ${\mathcal{F}}_t=\sigma (\mathrm{\Phi }((a,b]):a<b⩽t)$, the smallest filtration satisfying this property.

We define the stochastic intensity of a process for a given history (Brémaud 2020, definition 5.1.1).

Definition 2.

Let $\mathrm{\Phi }$ be a simple locally finite point process, and let ${\mathcal{F}}_t$ be a history of $\mathrm{\Phi }$. If there exists a locally integrable ${\mathcal{F}}_t$-adapted process $\phi (t)⩾0$ satisfying

$$\text{E}\left[\mathrm{\Phi }((s,t])|{\mathcal{F}}_s\right]=\text{E}\left[{\displaystyle {\int }_s^t\phi }(u)du|{\mathcal{F}}_s\right]\hspace{1em}\text{for} \text{all} s<t,$$(3)

then $\phi (t)$ is called an ${\mathcal{F}}_t$ stochastic intensity of $\mathrm{\Phi }$.

The process $\phi (t)$ acts as the local likelihood of a point appearing at time t given past information. This notion will play a key role in our particular application. Also, directly from the definition, one can prove that $\text{E}[\phi (t)]=\text{E}[\phi (0)]=\lambda$, the average intensity of the process.

As an example, the stationary Poisson process of intensity $\lambda$ with its natural history satisfies (3) with $\phi (t)\equiv \lambda$, a deterministic constant, and thus, the likelihood of a point appearing in time is independent of the past, reflecting the total randomness property of the Poisson process.

We now highlight some key properties of the stochastic intensity that will be useful for our later analysis. The first one is related to predictability; for this, we need the following definition.

Definition 3.

Let ${\{{\mathcal{F}}_t\}}_{t\in \mathbb{R}}$ be a filtration on $(\mathrm{\Omega },\mathcal{F})$. The predictable σ-algebra $\mathcal{P}(\mathcal{F}.)$ associated with ${\mathcal{F}}_t$ is the σ-algebra on $\mathbb{R}\times \mathrm{\Omega }$ generated by the sets of the form

$$(a,b]\times A,\hspace{0.17em}a<b,\hspace{0.17em}A\in {\mathcal{F}}_a.$$

A stochastic process $X(t,\omega )$ taking values on a measurable space $(E,\mathcal{E})$ is ${\mathcal{F}}_t$ predictable if the mapping $(t,\omega )\mapsto X(t,\omega )$ is $\mathcal{P}(\mathcal{F}.)$ measurable.

The following properties can be found in Brémaud (2020); any real-valued and left-continuous stochastic process adapted to ${\mathcal{F}}_t$ is ${\mathcal{F}}_t$ predictable. Moreover, the stochastic intensity of a point process $\mathrm{\Phi }$ if it exists can always be chosen to be a.s. predictable up to a set of Lebesgue measure 0, and thus, it is essentially unique. Also, the following result provides a smoothing formula for predictable processes based on the stochastic intensity.

Theorem 1.

Let $\mathrm{\Phi }$ be a simple point process in $\mathbb{R}$ with history ${\mathcal{F}}_t,$ and let $\phi (t)$ be an ${\mathcal{F}}_t$-adapted and a.s.-integrable process. Then, $\phi (t)$ is an ${\mathcal{F}}_t$-stochastic intensity of $\mathrm{\Phi }$ if and only if

$$\text{E}\left[{\displaystyle \int Z}(t)\mathrm{\Phi }(dt)\right]=\text{E}\left[{\displaystyle \int Z}(t)\phi (t)dt\right]$$(4)

holds for all ${\mathcal{F}}_t$-predictable processes $Z(t)$.

Finally, we quote the following result, known as Papangelou’s formula (Brémaud 2020, theorem 7.7.5).

Theorem 2.

Let $\mathrm{\Phi }$ be a simple point process in $\mathbb{R}$ with history ${\mathcal{F}}_t,$ stochastic intensity $\phi (t)$, and mean intensity $\lambda$. If $Z(t)$ is an ${\mathcal{F}}_t$-predictable process and $f(z)$ is a real-valued function, then

$$\text{E}\left[f(Z(0))\phi (0)\right]=\lambda {\text{E}}_{\mathrm{\Phi }}^0\left[f(Z(0))\right].$$(5)

For the purposes of our analysis, an important random variable is the stochastic intensity observed when sampling the renewal process at a fixed time; for convenience, it is chosen to be $t=0$. We call it the observed stochastic intensity (OSI) and denote it by $X≔\phi (0)$.

To find the distribution of the OSI, there are two underlying probability measures to consider.

Definition 4.

Let $X≔\phi (0)$ be the observed stochastic intensity at time 0. Define

$$G(x)≔\text{P}(X⩽x)=\text{E}\left[{\mathbf{1}}_{\{\phi (0)⩽x\}}\right];\hspace{1em}\hspace{1em}{G}_0(x)≔{\text{P}}_{\mathrm{\Phi }}^0(X⩽x)={\text{E}}_{\mathrm{\Phi }}^0\left[{\mathbf{1}}_{\{\phi (0)⩽x\}}\right].$$(6)

Here, $G(x)$ is the distribution of the stochastic intensity at a sampling point not synchronized with the process. $G_0$ is the distribution of the OSI at the time of a request; because the stochastic intensity can be chosen to be left continuous, $G_0$ identifies the stochastic intensity distribution prior to this arrival. A useful inequality that will be needed later is the following lemma.

Lemma 1.

The distribution of the OSI prior to arrival events satisfies

$$G_0(x)⩽\frac{x}{\lambda }.$$(7)

Proof.

The result follows from the formula of Papangelou; taking $Z(t)=\phi (t)$ and $f(z)=\mathbf{1}\{z⩽x\}$ in (5), we get

$$\lambda G_0(x)=\lambda {\text{E}}_{{\mathrm{\Phi }}_0}^0\left[{\mathbf{1}}_{\{\phi (0)⩽x\}}\right]=\text{E}\left[\phi (0){\mathbf{1}}_{\{\phi (0)⩽x\}}\right]⩽\text{E}\left[x{\mathbf{1}}_{\{\phi (0)⩽x\}}\right]⩽x.$$ □

2.2. Renewal Point Processes

As an important special case, consider now that $\mathrm{\Phi }$ is a stationary renewal process, meaning that the interrequest time sequence ${\{{\tau }_{k+1}-{\tau }_k\}}_{k\in \mathbb{Z}}$ includes ${\text{P}}_{\mathrm{\Phi }}^0$ independent and identically distributed random variables with common distribution $F_0$. We assume that $F_0$ has a density $f_0$ and recall the definition of the failure rate or hazard rate function associated with $F_0$:

Then, if ${\mathcal{F}}_t$ is the natural history of the process, the stochastic intensity of $\mathrm{\Phi }$ is given by Daley and Vere-Jones (2003, chapter 7):

where ${\tau }^{-}(t)=\sup \{{\tau }_k:{\tau }_k<t\}$ is the last point before t. Note that ${\tau }^{-}(t)$ is a left-continuous process. In particular, because of the renewal property, the local intensity of the process depends only on the age of the current interval and the hazard rate function of the interarrival distribution.

When $F_0$ is the exponential distribution as in the Poisson process, $\eta (t)\equiv \lambda$, so the stochastic intensity is constant as previously stated. Another interesting parametric example that we will use for illustration is the case of Pareto interarrival times; it is presented below in Section 2.3.

In the renewal case, we can provide more explicit formulas for the distribution of the observed stochastic intensity $X≔\phi (0)=\eta (-{\tau }^{-}(0))$. In particular, at a time not synchronized with arrivals, we will have

because $-{\tau }_0\sim F$, the age distribution. We note that the set ${\eta }^{-1}([0,x])$ will be an interval if the hazard rates are monotone.

If instead, we are evaluating the OSI at an arrival time, we must use the Palm probability ${\text{P}}_{\mathrm{\Phi }}^0$, for which ${\tau }_0\equiv 0$ a.s. and ${\tau }^{-}({\tau }_0)={\tau }^{-}(0)={\tau }_{-1}$. Therefore, $X=\eta (-{\tau }_{-1})$, and its distribution is given by

because $-{\tau }_{-1}\sim F_0$ under the Palm probability.

2.3. Pareto Interarrival Times

An interesting parametric example of stationary renewal processes, which is considered in Ferragut et al. (2016) for the same application, is when interarrival times follow a heavy-tailed Pareto distribution. In this case, all of the above magnitudes have explicit expressions, which we now compute.

Example 1

(Renewal Pareto Process). In the above setting, choose

$$F_0(t)=1-{\left(\frac{1}{1+\gamma t}\right)}^{\alpha },\hspace{1em}{f}_0(t)=\frac{\alpha \gamma }{{\left(1+\gamma t\right)}^{\alpha +1}}\hspace{1em}(t⩾0).$$(12)

Thus, $F_0$ is a Pareto distribution (starting at zero) with tail parameter $\alpha >1$. The number $\gamma$ acts as a scale parameter, and by direct computation, in order to have ${\text{E}}_{\mathrm{\Phi }}^0[{\tau }_1]=1/\lambda$, it should be chosen such that $\gamma =\frac{\lambda }{\alpha -1}$.

From Equations (2) and (8), we can compute

For this example, note that the hazard rate function is decreasing for any choice of the parameters. Therefore, at an arrival time ${\tau }_k$, the stochastic intensity increases (the hazard rate resets to $\eta (0)$ following (9)), and a subsequent arrival becomes more likely. This gives rise to bursty traffic as depicted in Figure 2.

For this process, we can also compute the distributions of the observed stochastic intensity at nonsynchronized or synchronized times:

In Figure 3, we depict the distributions $F_0$, F, G, and $G_0$ as well as the hazard rate function $\eta$ for the case $\alpha =2$ and $\gamma =1$ (with average intensity $\lambda =1$). In this particular case, the nonsynchronized OSI distribution is uniform in [0, 2].

3. Local Memory Systems and Optimal Storage Policy

We start by rigorously defining our model for a local memory system. Requests from a catalog of N equally sized items are received (we defer the discussion of heterogeneous sizes to Section 7). We model item requests by stationary stochastic point processes ${\mathrm{\Phi }}_i$, $i=1,\dots ,N$, which are defined on a common probability space and with finite intensity ${\lambda }_i>0$, a measure of the popularity of item i. By appropriate labeling, we can choose ${\lambda }_1⩾{\lambda }_2⩾\dots$ (i.e., the objects are ordered by decreasing popularities). Thus, the complete request process is the superposition $\mathrm{\Phi }≔{\sum }_{i=1}^N{\mathrm{\Phi }}_i$, and its total intensity is ${\lambda }^N={\sum }_{i=1}^N{\lambda }_i$.

The local memory is limited, and thus, it can only keep readily available a subset of size $C<N$ of the items. These items can upon request be served from the local memory with lower cost than retrieving them from a central repository. This formulation is quite general, and it subsumes the typical notion of caching, which is useful in many applications.² Mathematically, the local memory can keep at any point in time a subset

We call the process $\mathcal{C}:\mathrm{\Omega }\times \mathbb{R}\to P_C(N)$ the storage process of the system, where $P_C(N)$ denotes the subsets of $\{1,\dots ,N\}$ with size less than C.

For a given storage process, we can define the hit-counting process of the local memory system as

(i.e., the thinned process that counts the requests of objects only if they are stored in memory at the request time). The mean intensity $h_{\mathcal{C}}$ of the process ${\mathrm{\Psi }}_{\mathcal{C}}$ is called the hit rate, and accordingly, it satisfies $h_{\mathcal{C}}⩽{\lambda }^N$.

The natural objective in this setting is to maximize $h_{\mathcal{C}}$ (i.e., the rate at which requests can be served directly from the local memory) by choosing an appropriate policy that defines the storage process $\mathcal{C}(t)$. However, this policy should be causal (i.e., it cannot make use of future information). Otherwise, the policy that only stores the next arriving item achieves a maximum rate using only one unit of memory for any N, and the problem is trivial. This is where the predictability notion introduced in Section 2.1 becomes important.

Let us denote by ${\mathcal{F}}_t^{(i)}$ the natural history of the ith request process ${\mathrm{\Phi }}_i$, and ${\phi }_i(t)$ is its stochastic intensity with respect to ${\mathcal{F}}_t^{(i)}$. Define ${\mathcal{F}}_t=\sigma ({\mathcal{F}}_t^{(i)};\hspace{0.17em}i=1,\dots ,N)$ as the aggregated history (i.e., the information about all arrivals up to time t). Note that we are not assuming independence between the request processes. We have the following definition.

Definition 5.

Consider a local memory system with request processes $\{{\mathrm{\Phi }}_i:i=1\dots N\}$, aggregated natural history ${\mathcal{F}}_t$, and capacity C. A causal memory management policy is a stationary ${\mathcal{F}}_t$-predictable stochastic process $\mathcal{C}(t)$, with values in the space $P_C(N)$ of all subsets of $\{1,\dots ,N\}$ of size at most C (equipped with the discrete $\sigma$-algebra).

We would like to characterize the causal policy that maximizes the hit rate $h_{\mathcal{C}}$. We need the following assumption.

Assumption 1.

The aggregated process $\mathrm{\Phi }$ is simple, and each process ${\mathrm{\Phi }}_i$ admits a stochastic intensity ${\tilde{\phi }}_i(t)$ with respect to the aggregated natural history ${\mathcal{F}}_t$ for all $i=1,\dots ,N$.

Note that the stochastic intensity ${\tilde{\phi }}_i(t)$ need not be equal to the individual stochastic intensity ${\phi }_i(t)$ because of crossinformation across arrivals. However, the average intensity should still satisfy $E[{\tilde{\phi }}_i(0)]={\lambda }_i$. The following example illustrates this fact.

Example 2.

Consider the following process; objects $1\dots ,N$ are requested alternatively one after another. When a request for item i arrives, an exponential distribution with parameter ${\lambda }_i$ is started, and after expiration, the request for object $i+1$ arrives (with the cyclic convention $N+1\mapsto 1$). Let ${\mathrm{\Phi }}_i$ denote the requests for item i and $\mathrm{\Phi }$ denote the total request process. Then, it is clear that ${\mathrm{\Phi }}_i$ is a renewal process with interval length following a hypoexponential (phase-type) distribution (i.e., the sum of independent exponentials with parameters ${\lambda }_i$). In this case, by Equation (9), ${\phi }_i(t)=\eta (t-{\tau }_i^{-})$, where $\eta$ is the hazard rate function of the resulting hypoexponential, and it is the same for all i.

However, when looking at the aggregated history, it is clear that arrivals for item i can only come at rate ${\lambda }_i$ after a request from process $i-1$; therefore,

where ${\tau }^{-}(t)$ is the last point before t of the aggregated process.

Assumption 1 is also needed to guarantee the existence of $\tilde{\phi }$; as an extreme example, consider in particular two processes ${\mathrm{\Phi }}_1$ and ${\mathrm{\Phi }}_2=S_{t_0}({\mathrm{\Phi }}_1)$ (i.e., a delayed version of the first with $t_0>0$ fixed). Then, their stochastic intensities with respect to their own natural histories are just delayed versions of one another: ${\phi }_2(t)={\phi }_1(t-t_0)$. However, in the combined history of both processes, the stochastic intensity of process 2 is zero everywhere except that it degenerates into Dirac $\delta$ functions at the $t_0$-shifted points of process 1. Hence, these processes do not have a stochastic intensity in the sense of Definition 2 (which requires a proper stochastic function ${\phi }_i(t)$) with respect to the combined history of both processes. Assumption 1 ensures that these pathological examples with complete correlation are excluded.

We are now in position to compute the stochastic intensity of the hit process.

Lemma 2.

Let $\mathcal{C}(t)$ be a causal policy. The stochastic intensity of its associated hit process ${\mathrm{\Psi }}_{\mathcal{C}}(t)$ defined by (16) with respect to the aggregated history ${\mathcal{F}}_t$ is

$${\phi }_{\mathcal{C}}(t)={\displaystyle \sum _{i=1}^N{\tilde{\phi }}_i}(t){\mathbf{1}}_{\{i\in \mathcal{C}(t)\}}.$$(17)

Proof.

We apply the smoothing Equation (4) in Section 2.1. For an ${\mathcal{F}}_t$-predictable process $Z(t)$, we write

$$\begin{array}{l}\text{E}\left[{\displaystyle {\int }_{\mathbb{R}}Z}(t){\mathrm{\Psi }}_{\mathcal{C}}(dt)\right]={\displaystyle \sum _{i=1}^N\text{E}}\left[{\displaystyle {\int }_{\mathbb{R}}Z}(t){\mathbf{1}}_{\{i\in \mathcal{C}(t)\}}{\mathrm{\Phi }}_i(dt)\right]={\displaystyle \sum _{i=1}^N\text{E}}\left[{\displaystyle {\int }_{\mathbb{R}}Z}(t){\mathbf{1}}_{\{i\in \mathcal{C}(t)\}}{\tilde{\phi }}_i(t)\hspace{0.17em}dt\right]\hfill \\ =\text{E}\left[{\displaystyle {\int }_{\mathbb{R}}Z}(t)\left({\displaystyle \sum _{i=1}^N{\mathbf{1}}_{\{i\in \mathcal{C}(t)\}}}{\tilde{\phi }}_i(t)\right)\hspace{0.17em}dt\right]=\text{E}\left[{\displaystyle {\int }_{\mathbb{R}}Z}(t){\phi }_{\mathcal{C}}(t)\hspace{0.17em}dt\right].\hfill \end{array}$$

The second equality follows from the smoothing Equation (4) because by Assumption 1, the stochastic intensity of ${\mathrm{\Phi }}_i$ with respect ${\mathcal{F}}_t$ is ${\tilde{\phi }}_i(t)$. The last equality is because of the process $Z(t){\mathbf{1}}_{\{i\in \mathcal{C}(t)\}}$ being ${\mathcal{F}}_t$ predictable. This is the case because $\mathcal{C}(t)$ is causal and thus, $\mathcal{P}(\mathcal{F}.)$ measurable; therefore, $Z(t){\mathbf{1}}_{\{i\in \mathcal{C}(t)\}}$ is also $\mathcal{P}(\mathcal{F}.)$ measurable for all i.

Because the identity holds for any ${\mathcal{F}}_t$-predictable process $Z(t)$, the converse implication in the smoothing formula establishes (17). □

Define now the policy ${\mathcal{C}}^{*}(t)$ as follows. At any point in time, rank the items by decreasing stochastic intensities ${\tilde{\phi }}_i(t)$, and store the C highest; ties may be broken arbitrarily. Note that this policy maximizes the sum of the stochastic intensities of the items in memory

Theorem 3

(Optimal Causal Memory Management Policy). Given a local memory system with capacity C fed by a family of stationary point processes, $\{{\mathrm{\Phi }}_i:i=1,\dots ,N\}$ with aggregated natural history ${\mathcal{F}}_t$, satisfying Assumption 1. Then, for any causal policy $\mathcal{C}(t)$, its stationary hit rate $h_{\mathcal{C}}$ satisfies

$$h_{\mathcal{C}}=\text{E}\left[{\phi }_{\mathcal{C}}(0)\right]⩽\text{E}\left[{\phi }_{{\mathcal{C}}^{*}}(0)\right]=h_{{\mathcal{C}}^{*}},$$

with ${\phi }_{\mathcal{C}}(t)$ as in (17) and ${\mathcal{C}}^{*}$ as defined in (18). In addition, the hit process (16) is also simple, and the hit probability

$$H_{\mathcal{C}}≔{\text{P}}_{\mathrm{\Phi }}^0({\mathrm{\Psi }}_{\mathcal{C}}(\{0\})=1)$$

is maximized by the policy ${\mathcal{C}}^{*}$.

Proof.

Note from Equation (17) and the construction of ${\mathcal{C}}^{*}$ that for any realization,

$${\phi }_{\mathcal{C}}(0)={\displaystyle \sum _{i=1}^N{\tilde{\phi }}_i}(0){\mathbf{1}}_{\{i\in \mathcal{C}\}}⩽\underset{\{i_1,\dots ,i_C\}}{\max }{\displaystyle \sum _{i\in \{i_1.\dots ,i_C\}}{\tilde{\phi }}_i}(0)={\phi }_{{\mathcal{C}}^{*}}(0).$$(19)

The first inequality follows by taking expectations on both sides with respect to the joint probability measure $\text{P}$ of the arrival processes (nonsynchronized with arrivals).

To derive the second statement, we begin by observing that by definition (Equation (16)), ${\mathrm{\Psi }}_{\mathcal{C}}(B)⩽\mathrm{\Phi }(B)$ for any $B\in \mathcal{B}(\mathbb{R})$, so ${\mathrm{\Psi }}_{\mathcal{C}}$ must also be simple. Therefore, it suffices to show that for any causal policy, $h_{\mathcal{C}}={\lambda }^N{H}_{\mathcal{C}}$ (i.e., the hit rate is the total rate “thinned” by the hit probability). This is a natural property but nontrivial because the thinning is not independent of the arrival process.

From the superposition properties of stationary point processes (Brémaud 2020, example 7.2.11), under Assumption 1, the aggregated process is simple, and for any event A, we must have

$${\text{P}}_{\mathrm{\Phi }}^0(A)={\displaystyle \sum _{i=1}^N\frac{{\lambda }_i}{{\lambda }^N}}{\text{P}}_{{\mathrm{\Phi }}_i}^0(A).$$(20)

To interpret the above, note that given a point in $\mathrm{\Phi }$ occurring at time 0, ${\lambda }_i/{\lambda }^N$ is the probability that this point comes from process i. Now, apply (20) to the event $A=\{\omega :{\mathrm{\Psi }}_{\mathcal{C}}(\{0\})=1\}$:

$$H_{\mathcal{C}}={\text{P}}_{\mathrm{\Phi }}^0({\mathrm{\Psi }}_{\mathcal{C}}(\{0\})=1)={\displaystyle \sum _{i=1}^N\frac{{\lambda }_i}{{\lambda }^N}}{\text{P}}_{{\mathrm{\Phi }}_i}^0({\mathrm{\Psi }}_{\mathcal{C}}(\{0\})=1).$$

We now compute ${\text{P}}_{{\mathrm{\Phi }}_i}^0({\mathrm{\Psi }}_{\mathcal{C}}(\{0\})=1)$ as

$${\text{P}}_{{\mathrm{\Phi }}_i}^0({\mathrm{\Psi }}_{\mathcal{C}}(\{0\})=1)={\text{P}}_{{\mathrm{\Phi }}_i}^0\left({\displaystyle \underset{i}{\cup }\left\{{\mathrm{\Phi }}_i(\{0\})=1,i\in \mathcal{C}(0)\right\}}\right)={\text{P}}_{{\mathrm{\Phi }}_i}^0(i\in \mathcal{C}(0))$$

because under ${\text{P}}_{{\mathrm{\Phi }}_i}^0$, ${\text{P}}_{{\mathrm{\Phi }}_i}^0(\{{\mathrm{\Phi }}_i(\{0\})=1\})=1$ and ${\text{P}}_{{\mathrm{\Phi }}_i}^0(\{{\mathrm{\Phi }}_j(\{0\})=1\})=0$ for $j\ne i$ because of $\mathrm{\Phi }$ being simple. We conclude that

$$H_{\mathcal{C}}={\displaystyle \sum _{i=1}^N\frac{{\lambda }_i}{{\lambda }^N}}{\text{P}}_{{\mathrm{\Phi }}_i}^0(i\in \mathcal{C}(0)).$$(21)

Now, return to (17) and its expectation at $t=0$:

$$h_{\mathcal{C}}=\text{E}\left[{\displaystyle \sum _{i=1}^N{\tilde{\phi }}_i}(0){\mathbf{1}}_{\{i\in \mathcal{C}(0)\}}\right]={\displaystyle \sum _{i=1}^N\text{E}}\left[{\tilde{\phi }}_i(0){\mathbf{1}}_{\{i\in \mathcal{C}(0)\}}\right].$$

Because ${\mathbf{1}}_{\{i\in \mathcal{C}(t)\}}$ is F_t predictable for any causal policy, it follows from Papangelou’s formula (Equation (5)) that

$$\text{E}\left[{\tilde{\phi }}_i(0){\mathbf{1}}_{\{i\in \mathcal{C}(0)\}}\right]={\lambda }_i{\text{E}}_{{\mathrm{\Phi }}_i}^0\left[{\mathbf{1}}_{\{i\in \mathcal{C}(0)\}}\right]={\lambda }_i{\text{P}}_{{\mathrm{\Phi }}_i}^0(i\in \mathcal{C}(0)).$$

Summation over i gives together with (21), $h_{\mathcal{C}}={\lambda }^N{H}_{\mathcal{C}}$ as claimed, and the result follows. □

Thus, Theorem 3 gives a clean formulation of what the optimal policy is: just keep track of the most likely arrivals in the system given the complete past history of the arrival stream. In particular, this generalizes Panigrahy et al. (2022) to general (possibly correlated) superpositions that provided that they satisfy Assumption 1.

3.1. The Case of Independent Request Streams

In the preceding analysis, computing the optimal policy requires knowledge of the stochastic intensities $\{{\tilde{\phi }}_i(t):i=1,\dots ,N\}$ with respect to the aggregated history. This may require the knowledge of the underlying correlations. This is greatly simplified if the request processes are independent.

Consider now a local memory system with capacity C fed by N-independent stationary request processes ${\mathrm{\Phi }}_i$ with average intensities ${\lambda }_i>0$ as before (in decreasing order). Again, let ${\mathcal{F}}_t^{(i)}$ be the natural history of the ith process, and let ${\mathcal{F}}_t$ be the aggregated history. Again, let ${\text{P}}_{\mathrm{\Phi }}^0$ denote the Palm probability of the superposition process, and let ${\text{P}}_{{\mathrm{\Phi }}_i}^0$ be the Palm probability of the ith process.

The superposition of independent simple processes is simple (Baccelli and Brémaud 2013, property 1.1.1), and besides Equation (20), we also have (Brémaud 2020, example 7.2.8)

for any ${\mathrm{\Gamma }}_i\in {\mathcal{M}}^{\#}(\mathbb{R})$ and $i=1,\dots ,N$.

The interpretation of Equation (22) is the following; in order to compute Palm probabilities given that the point comes from process i, we must use the Palm probability for process i and the stationary probability for any other $j\ne i$, and the processes remain independent.

This, in turn, allows us to prove the following property.

Lemma 3.

If $\mathrm{\Phi }={\sum }_i{\mathrm{\Phi }}_i$ is the superposition process, then ${\mathcal{F}}_t$ is a history of $\mathrm{\Phi }$. Moreover, ${\phi }_i(t)$ is a stochastic intensity for process i with respect to the enlarged history ${\mathcal{F}}_t$, and the total stochastic intensity of $\mathrm{\Phi }$ is simply $\phi (t)={\sum }_{i=1}^N{\phi }_i(t)$.

Proof.

First, $\mathrm{\Phi }((a,b])$ is ${\mathcal{F}}_t$ measurable for all $a<b⩽t$ because the sum function is measurable and ${\mathcal{F}}_t^{(i)}\subset {\mathcal{F}}_t$. Second, ${\phi }_i(t)$ is the stochastic intensity of ${\mathrm{\Phi }}_i$ with respect to the shared history ${\mathcal{F}}_t$ because the conditional expectation given ${\mathcal{F}}_t^{(i)}$ coincides with the conditional expectation given ${\mathcal{F}}_t$ for any random variable independent of ${\mathcal{F}}_t^{(j)}$ with $j\ne i$. This fact is, in turn, a consequence of the independence of the filtrations ${\{{\mathcal{F}}_t^{(i)}\}}_{i=1}^N$ and that ${\mathcal{F}}_t$ is generated by events of the form ${\displaystyle {\cap }_{i=1}^N{A}_i}$ with $A_i\in {\mathcal{F}}_t^{(i)}$, $i=1,\dots ,N$. Finally, that $\phi (t)$ is the stochastic intensity of $\mathrm{\Phi }(t)$ with respect to ${\mathcal{F}}_t$ follows immediately by linearity of conditional expectation. □

The above lemma guarantees that the stochastic intensity of process i is not altered by superposition with other independent processes; there is no crossinformation between the processes. In particular, Assumption 1 is satisfied, and therefore, we can replace ${\tilde{\phi }}_i(t)$ by ${\phi }_i(t)$ in Theorem 3 to obtain Theorem 4.

Theorem 4

(Optimal Causal Memory Management Policy, Independent Case). Given a local memory system with capacity C fed by independent stationary point processes, $\{{\mathrm{\Phi }}_i:i=1,\dots ,N\}$ with individual stochastic intensities ${\phi }_i(t)$. Then, the optimal causal policy ${\mathcal{C}}^{*}$ corresponds to the following.

• At any point in time, rank the items in decreasing order of their individual stochastic intensities ${\phi }_i(t)$.

• Store in memory the first C objects in the ranking.

Any other causal policy $\mathcal{C}$ will satisfy $h_{\mathcal{C}}⩽h_{{\mathcal{C}}^{*}}$ and $H_{\mathcal{C}}⩽H_{{\mathcal{C}}^{*}}$.

The above theorem characterizes the structure of the optimal causal policy for any superposition of independent request processes (i.e., where no additional information is available about the future other than the natural history of the requests and where there is no crossinformation between them). If the processes are correlated among them, this statement will not be true in general, and we will have to keep track of the shared stochastic intensity with respect to the common history ${\tilde{\phi }}_i(t)$.

We now analyze some examples where the above policy can be further characterized. The simplest is the Poisson case.

Example 3

(Poisson Arrivals). In case all processes ${\mathrm{\Phi }}_i$ are Poisson with ${\lambda }_1⩾\dots ⩾{\lambda }_N$, ${\phi }_i(t)\equiv {\lambda }_i$. By Theorem 3, the optimal policy ${\mathcal{C}}^{*}$ is the static policy that stores the C objects with higher (average) intensities at all times. This is, of course, connected to the total independence property of Poisson processes, and it is also well known in the caching literature (see, e.g., Garetto et al. 2016) under the name independent reference model.

Example 4

(Renewal Arrivals). In the more general class of renewal arrival processes, by Equation (9), ${\phi }_i(t)={\eta }_i(t-{\tau }_i^{-}(t))$. In this case, the optimal policy can be recast in the following way.

• Rank all contents in decreasing order of the current interval hazard rates, ${\eta }_i(t-{\tau }_i^{-}(t))$.

• Store in memory the first C objects in the ranking.

As we can see, the role of the hazard rates is crucial as already identified in Ferragut et al. (2016) for timer-based caching. Different monotonicity assumptions on these hazard rates lead to completely different optimal policies as we shall see in Section 6.

An issue with the optimal policy is that its main performance metric, the hit rate, cannot be computed exactly except in some special cases. We now derive an asymptotic result that characterizes the optimal policy for large-scale systems and allows us to calculate asymptotic performance limits.

4. Large-Scale Analysis of the Optimal Causal Policy

In this section, we will present results concerning the asymptotic behavior of the optimal policy in a large-scale regime, where both the system load and the memory size scale appropriately to infinity. For this purpose, we need to introduce more structure into the problem; in particular, we will assume that requests for different items come from independent processes from a common scale family in the following sense.

Consider a base process with unit intensity ${\mathrm{\Phi }}_0$, natural history ${\mathcal{F}}_t^{(0)}$, and stochastic intensity ${\phi }_0(t)$ with respect to ${\mathcal{F}}_t^{(0)}$. In particular, $E[{\phi }_0(t)]=1$. For our asymptotic analysis, we specify our scale family as satisfying the following.

Assumption 2.

The request processes ${\mathrm{\Phi }}_i$ for items $i\in \{1,\dots ,N\}$ are independent with stochastic intensities

$${\phi }_i(t)\stackrel{d}{=}{\lambda }_i{\phi }_0({\lambda }_{i}t),$$

where ${\lambda }_i$ is the process average request rate. Without loss of generality, we will assume that these rates are decreasing (i.e., ${\lambda }_1⩾\dots ⩾{\lambda }_N>0$); equivalently, items are ordered in decreasing popularity.

A construction that generates processes ${\mathrm{\Phi }}_i$ satisfying this assumption is to take independent copies of ${\mathrm{\Phi }}_0$ and set ${\mathrm{\Phi }}_i(B)\hspace{0.17em}\stackrel{d}{=}\hspace{0.17em}{\mathrm{\Phi }}_0({\lambda }_{i}B)$ (i.e., rescale the time axis).

It is direct from Definition 6 and Assumption 2 that if $X_i={\phi }_i(0)$ is the observed stochastic intensity for process i, then the following scaling relationships hold:

Example 5

(Scaled Renewal Process). A simple example where all of the above assumptions hold is when the base process is renewal with some base distribution $F_0(t)$ with a mean of one. In this case, the interarrival distribution of the ith process is

$$F_0^{(i)}(t)=F_0({\lambda }_{i}t).$$

We can also express the age distribution $F^{(i)}(t)$ and hazard rate function ${\eta }^{(i)}(t)$ for the ith request process in terms of the base case $F(t)$, $\eta (t)$:

4.1. Threshold Characterization of the Optimal Policy

Under Assumption 2, the optimal policy of Theorem 4 can be recast as follows; at any given time, we have a sample of random variables $X_i,\hspace{0.17em}i=1,\dots ,N$, each representing the observed stochastic intensity (for the renewal case, hazard rate since the last request) of the ith request process. Because the processes are independent, the $X_i$’s are independent but nonidentically distributed; in fact, $X_i\sim G^{(i)}$.

According to Theorem 4, an item will be stored in memory if and only if its OSI is one of the C highest. An alternative way to cast this optimal policy is to consider the empirical distribution of the observed stochastic intensities defined by

then, object i is locally stored if and only if ${\widehat{G}}_N(X_i)⩾\frac{N-C}{N}=1-\frac{C}{N}$.

Introducing the quantile function (inverse of the empirical distribution)

the condition for storing item i in memory at a certain time may be expressed as

The random variable ${\widehat{\theta }}_N$ acts as a threshold in the OSI that determines the items to optimally store in local memory. Equivalently, ${\widehat{\theta }}_N=Y_{N-C}$, where $\{Y_i:i=1,\dots ,N\}$ are the order statistics of the sample $\{X_i,i=1,\dots ,N\}$.

We will pursue asymptotic results for a system with a very large catalog size N. If we can find a suitable limit for the empirical distribution ${\widehat{G}}_N(x)$ as $N\to \infty$ and if the memory size scales linearly with N such that $\frac{C}{N}{\to }_{N}c$, then the quantile ${\widehat{\theta }}_N$ should approach a limit (i.e., the large-scale behavior should resemble a policy with a fixed threshold in OSI).

Because the $X_i$’s are not identically distributed, we cannot use classical Glivenko–Cantelli arguments for empirical distribution convergence. Nevertheless, we will show that a suitable limit arises under Assumption 2 if the system load as defined by the request intensities also scales appropriately with N.

4.2. Scaling of the Request Intensities

We will construct a sequence of systems indexed by N, the number of arrival streams or in other words, items in its catalog. Denote by ${\{{\lambda }_i^{(N)}\}}_{i=1}^N$ the arrival rates of the system of size N, with the above convention that ${\lambda }_1^{(N)}⩾\cdots ⩾{\lambda }_N^{(N)}>0$. We may think of these points as a discrete measure on the axis $\lambda \in {\mathbb{R}}_{+}$ of possible process intensities. Normalizing this measure to total unit mass, we may write its distribution function

The total arrival rate for system of size N can then be expressed as

Our limit theorems will assume that this family of discrete distributions has a limit with $N\to \infty$.

Assumption 3.

There exists a fixed distribution L with no atoms at $\lambda =0$ such that $L_N\Rightarrow L$ when $N\to \infty$. Here, $\Rightarrow$ denotes usual weak convergence of probability distributions.

To gain some intuition on the above condition, we turn to the following important example.

Example 6

(Scaling for Zipf Popularities). A widely used model of popularity among different items is the so-called Zipf distribution with the request rates ${\lambda }_i\propto i^{-\beta }$, where $\beta ⩾0$ is the tail parameter of the Zipf law. Note that $\beta =0$ corresponds to a uniform distribution, whereas as for large $\beta$, relative popularities decay very fast.

In order to model this in our setting, we can use the following arrival rates for the Nth system:

with $\beta ⩾0$. Under this scaling, the least popular object has intensity 1 for all N. As N grows, larger intensities are included in the mix. Now, for any $\lambda >1$, we have

Because the above convergence is point wise and the limit is continuous, we have $L_N(\lambda )\Rightarrow L(\lambda )$ given by

In the limit, the popularities follow a continuous distribution over $[1,\infty )$: namely, a standard Pareto distribution with tail parameter $1/\beta$.

If $\beta ⩾1$ (i.e., the popularities are light tailed), some objects are extremely more popular than others; in this case, L does not have a finite mean. If instead, $0<\beta <1$, where popularities are heavy tailed and thus, more homogeneous, L has finite mean $1/(1-\beta )$. For $\beta =0$, the system degenerates into every object having the same popularity, and thus, L is the step function at $\lambda =1$.

It is also worth observing that the total arrival rate of the Nth system satisfies

where $S_N(\beta )$ is the generalized harmonic series partial sum. Using the well-known equivalents for this series, we have that

In particular, with our scaling, the total arrival rate ${\lambda }^N\to \infty$ as $N\to \infty$, albeit at different rates depending on the tail parameter $\beta$.

4.3. Asymptotic Behavior of the Optimal Causal Policy

We now return to our family of systems indexed by N with independent request streams coming from a common scale family with base distribution $F_0$ (Assumption 2) and incorporate the scaling in Assumption 3 on the arrival rates ${\{{\lambda }_i^{(N)}\}}_{i=1}^N$. Namely, their empirical distribution $L_N(\lambda )$ in (27) has a weak limit $L(\lambda )$.

If we look at each system at a fixed time $t=0$, we obtain a sample of the current observed stochastic intensities $\{X_i^{(N)}:i=1,\dots ,N\}$. Considered collectively that for all $N⩾1$, these random variables constitute a triangular array; without loss of generality, we may assume that they are all defined in a common probability space $(\mathrm{\Omega },\mathcal{F},\text{P})$.

For each N, we can define the random function ${\widehat{G}}_N$ by Equation (24). The main result below concerns the asymptotic behavior of these empirical stochastic intensity distributions.

Theorem 5.

Consider a family of local memory systems indexed by N with request processes satisfying Assumption 2 and with intensities ${\{{\lambda }_i^{(N)}\}}_{i=1}^N$ satisfying Assumption 3. Then,

$${\widehat{G}}_N\underset{N\to \infty }{\Rightarrow }{G}_{\infty }\hspace{1em}\text{P}\hspace{0.17em}\text{a}.\text{s}.,$$

where the function $G_{\infty }$ is given by

$$G_{\infty }(x)≔{\displaystyle {\int }_0^{\infty }G}(x/\lambda )L(d\lambda ).$$(29)

Moreover, assume that the memory size of the Nth system satisfies $\frac{C_N}{N}{\to }_{N}c$ with $0<c⩽1$.

Then, if $1-c$ is a continuity point of the quantile function $Q_{\infty }=G_{\infty }^{-1}$, the random threshold ${\widehat{\theta }}_N$ defined by Equation (26) converges P almost surely to ${\theta }^{*}=Q_{\infty }(1-c)$.

Proof.

The proof begins by computing the expected value of the random function ${\widehat{G}}_N$:

$${\overline{G}}_N(x)≔\text{E}\left[{\widehat{G}}_N(x)\right]=\text{E}\left[\frac{1}{N}{\displaystyle \sum _{i=1}^N{\mathbf{1}}_{\left\{X_i^{(N)}⩽x\right\}}}\right]=\frac{1}{N}{\displaystyle \sum _{i=1}^N{G}^{(i)}}(x)=\frac{1}{N}{\displaystyle \sum _{i=1}^{N}G}\left(\frac{x}{{\lambda }_i^{(N)}}\right),$$(30)

where we have applied the scaling in (23a). ${\overline{G}}_N$ is a (deterministic) distribution function in $x⩾0$. Using the definition of $L_N$, we can rewrite the above as

$${\overline{G}}_N(x)={\displaystyle {\int }_0^{\infty }G}(x/\lambda )L_N(d\lambda ).$$

We first show that as distribution functions, ${\overline{G}}_N\Rightarrow G_{\infty }$ as $N\to \infty$. To do so, it is convenient to interpret (30) as follows; consider a pair $(X,{\mathrm{\Lambda }}_N)$ of independent random variables in ${\mathbb{R}}_{+}$ with respective distribution functions $G(x)=P(X⩽x)$ and $L_N(\lambda )=P({\mathrm{\Lambda }}_N⩽\lambda )$. Then, ${\overline{G}}_N(x)$ is the distribution of the product $Z_N=X{\mathrm{\Lambda }}_N$. Indeed,

$$P(Z_N⩽x)={\displaystyle \sum _{n=1}^{N}P}(X{\mathrm{\Lambda }}_N⩽x|{\mathrm{\Lambda }}_N={\lambda }_i^{(N)})P({\mathrm{\Lambda }}_N={\lambda }_i^{(N)})=\frac{1}{N}{\displaystyle \sum _{n=1}^{N}P}(X⩽x/{\lambda }_i^{(N)})={\overline{G}}_N(x).$$

Now, consider the limit in the distribution of the pair $(X,{\mathrm{\Lambda }}_N)$. Because of their independence and because $L_N\Rightarrow L$, the limit corresponds to the distribution of $(X,\mathrm{\Lambda })$, a vector of independent random variables with marginal distributions $G(x)$ and $L(\lambda )$. By continuity of the map $(x,\lambda )\mapsto x\lambda$, we conclude that $Z_N=X{\mathrm{\Lambda }}_N\stackrel{d}{\to }Z=X\mathrm{\Lambda }$. It remains to compute the distribution function of the latter product:

$$P(Z⩽x)={\displaystyle {\int }_{{\mathbb{R}}_{+}^2}{\mathbf{1}}_{\{\xi \lambda ⩽x\}}}L(d\lambda )G(d\xi )={\displaystyle {\int }_0^{\infty }L}(d\lambda ){\displaystyle {\int }_0^{\infty }{\mathbf{1}}_{\{\xi ⩽x/\lambda \}}}G(d\xi )={\displaystyle {\int }_0^{\infty }G}(x/\lambda )L(d\lambda ).$$

We conclude that ${\overline{G}}_N\Rightarrow G_{\infty }$ as $N\to \infty$. Equivalently, we have point-wise convergence ${\overline{G}}_N(x)\to G_{\infty }(x)$ at any continuity point $x⩾0$ of $G_{\infty }$.

To relate the mean function ${\overline{G}}_N(x)$ to the stochastic one ${\widehat{G}}_N(x)$, we now resort to Shorack (1979, theorem 2.1), a generalization of the classical Glivenko–Cantelli theorem for empirical distributions for random variables that are not identically distributed. The theorem states that in the probability space $(\mathrm{\Omega },\mathcal{F},\text{P})$ where the triangular array $\{X_i^{(N)}:i=1,\dots ,N,N⩾1\}$ is defined, we have

$${\Vert {\widehat{G}}_N-{\overline{G}}_N\Vert }_{\infty }\underset{N\to \infty }{\to }0\hspace{1em}\text{P} \text{a}.\text{s}.$$(31)

In particular, with $\text{P}$ probability 1, $|{\widehat{G}}_N(x)-{\overline{G}}_N(x)|\to 0$ as $N\to \infty$ for all $x⩾0$. Combining this with the previously obtained point-wise convergence of ${\overline{G}}_N(x)$, we conclude that $\text{P}$ almost surely ${\widehat{G}}_N(x)\to G_{\infty }(x)$ at any continuity point $x⩾0$ of $G_{\infty }$, and thus, ${\widehat{G}}_N\Rightarrow G_{\infty }$.

Finally, convergence of ${\widehat{\theta }}_N$ now follows from the fact that convergence in distribution implies convergence of quantiles; specifically (van der Vaart 1998, lemma 21.2), ${\widehat{G}}_N\Rightarrow G_{\infty }$ is equivalent to ${\widehat{Q}}_N(p)\to Q_{\infty }(p)$ for all continuity points $p\in [0,1]$ of $Q_{\infty }=G_{\infty }^{-1}$. See also Proposition A.2 in Appendix A.1. □

We have thus established that the optimal causal local memory policy converges in the large-scale limit to a deterministic threshold policy in the observed stochastic intensities. Specifically, when memory scales as a fraction c of the catalog, a large-scale system should store at any given time the items whose current OSI exceeds a threshold ${\theta }^{*}$ chosen as the $1-c$ quantile of the limit distribution $G_{\infty }$ in (29).

5. Asymptotic Optimal Performance

In this section, we analyze the performance achieved by the optimal policy in the large-scale limit. As discussed in Section 3, performance in local memory systems is measured by the hit probability $H_{\mathcal{C}}$ or equivalently, the hit rate $h_{\mathcal{C}}={\lambda }^N{H}_{\mathcal{C}}$.

We will find it more convenient to derive expressions for the complementary miss probability $M_{\mathcal{C}}=1-H_{\mathcal{C}}$ and the miss rate $m_{\mathcal{C}}={\lambda }^N{M}_{\mathcal{C}}={\lambda }^N-h_{\mathcal{C}}$. Referring back to Equation (21), we can write the following expressions for these quantities in a system of size N.³

The key challenge in the evaluation of the above formulas is to compute ${\text{P}}_{{\mathrm{\Phi }}_i}^0(i\notin \mathcal{C}(0))$ (i.e., the probability that an incoming arrival does not find its file in local memory). In the optimal policy ${\mathcal{C}}^{*}$ for fixed N, the determining condition is whether the observed stochastic intensity $X_i^{(N)}$ of the requested item finds itself among the C largest. To correctly evaluate this probability, however, we must recognize an asymmetry. The competing $X_j^{(N)},\hspace{0.17em}j\ne i$ are being evaluated at a time not synchronized with their arrivals and thus, follow independent distributions $G(·/{\lambda }_j^{(N)})$; for the item in question, we must use the distribution $G_0(·/{\lambda }_i^{(N)})$ that applies to synchronized sampling of the stochastic intensity.

For this reason, to analyze the comparison, it is convenient to define the empirical distribution

of the stochastic intensities of nonrequested items and express the miss condition as follows:

The above equivalence assumes that there are no ties in the comparison of the OSIs; to simplify the analysis to follow, we will make this a standing assumption in this section.

Assumption 4.

For each $N⩾1$ and $1⩽i\ne j⩽N$, ${\text{P}}_{\mathrm{\Phi }}^0(X_i^{(N)}=X_j^{(N)})=0$.

Returning to (32b), we may now express the performance criterion of the optimal policy as

where ${\widehat{Q}}_N^{(-i)}$ is the inverse (quantile) function of ${\widehat{G}}_N^{(-i)}$.

We now outline informally the essence of the analysis that follows. Because the empirical distribution ${\widehat{G}}_N^{(-i)}$ corresponds to $N-1$ intensities, which are sampled at a nonsynchronized point, its asymptotic behavior under the assumed scaling should follow the conclusions of Theorem 5 (i.e., converge to the distribution $G_{\infty }$). Under $C/N\to c$, we have $p_N\to 1-c$, so we should have ${\widehat{Q}}_N^{(-i)}(p_N)\to Q_{\infty }(1-c)={\theta }^{*}$ as $N\to \infty$.

This leads us to consider the approximate formula

in the last equality, we have invoked the distribution of $X_i^{(N)}$ synchronized with the arrival under the Palm probability ${\text{P}}_{{\mathrm{\Phi }}_i}^0$. Of course, the approximation is not a rigorous step. We have taken the limit in the quantile but not in the rest of Equation (34); nevertheless, it will help us arrive at the right conjecture.

Invoking the distribution of intensities in (27), we may express the approximation as

Under Assumption 3, $L_N\Rightarrow L$. The integrand function $\lambda G_0({\theta }^{*}/\lambda )$ is bounded by ${\theta }^{*}$, invoking (7); if it is continuous, the right-hand side will converge to the corresponding integral with the limit distribution $L(\lambda )$. This formula for the asymptotic optimal miss rate is the main conjecture that we will prove in Theorem 6 below, making rigorous the preceding approximate reasoning.

We will require some additional technical conditions.

• For continuity of $\lambda G_0({\theta }^{*}/\lambda )$, it will suffice to guarantee it at the atoms of the measure $L(d\lambda )$ (i.e., the discontinuities of $L(\lambda )$); denote this set by $D_L$, and recall by Assumption 3 that $0\notin D_L$. Analogously, denote by $D_{G_0}$ the set of discontinuities of $G_0$, and denote by $D_L·D_{G_0}≔\{\lambda x:\lambda \in D_L,x\in D_{G_0}\}$; we will require for our limit theorem that ${\theta }^{*}\notin D_L·D_{G_0}$.

• To carry out the limit result for $m_{{\mathcal{C}}^{*}}$ in (34), we will treat separately two cases in regard to the uniform integrability of the family of popularity distributions ${\{L_N\}}_{N⩾1}$. The family is uniformly integrable if

  $$\forall ϵ>0,\hspace{0.17em}\exists \hspace{0.17em}K⩾0 \text{such} \text{that} \underset{N⩾1}{\sup }\frac{1}{N}{\displaystyle \sum _{{\lambda }_i^{(N)}⩾K}{\lambda }_i^{(N)}}⩽ϵ.$$

Uniform integrability is a standard assumption (see, e.g., Billingsley 1999, section 1.3) that connects convergence in distribution with convergence of the first moment. In particular, if $L_N\Rightarrow L$ and the $\{L_N\}$’s are uniformly integrable, then

A partial converse also holds; if $L_N\Rightarrow L$, with first moments satisfying (36), the family must be uniformly integrable.

Example 7.

The Zipf family considered in Example 6 has continuous limit L and thus, satisfies all necessary continuity assumptions. Furthermore, the family $L_N$ is uniformly integrable for $\beta <1$; for $\beta ⩾1$, the limit distribution has infinite mean.

We are now ready to state our main performance result.

Theorem 6

(Asymptotic Miss Rate—Uniformly Integrable Case). Suppose ${\{L_N\}}_{N⩾1}$ is uniformly integrable. Let $c\in (0,1]$ be such that $1-c$ is a continuity point of $Q_{\infty }$ and that ${\theta }^{*}≔Q_{\infty }(1-c)\notin D_L·D_{G_0}$. If $C/N\to c$ as $N\to \infty$, then

$$\underset{N\to \infty }{\lim }\frac{m_{{\mathcal{C}}^{*}}^{(N)}}{N}={\displaystyle {\int }_0^{\infty }\lambda }{G}_0\left(\frac{{\theta }^{*}}{\lambda }\right)L(d\lambda ).$$(37)

The proof is given in Appendix A.

The result states that for a uniformly integrable scaling of popularity distributions, under some regularity assumptions, the miss rate of the optimal policy scales linearly with N with a proportionality constant given by the integral in (37), where the distribution function $G_0$ of the OSI under synchronous sampling appears explicitly. On the other hand, the nonsynchronous distribution G of the OSI also influences the formula because it determines the distribution $G_{\infty }$ in (29), whose quantile is the asymptotic threshold ${\theta }^{*}$.

Corollary 1

(Asymptotic Miss Probability—Uniformly Integrable Case). Under the same hypothesis as Theorem 6, the optimal miss probability satisfies

$$\underset{N\to \infty }{\lim }{M}_{{\mathcal{C}}^{*}}^{(N)}=\frac{{\int }_0^{\infty }\lambda G_0\left(\frac{{\theta }^{*}}{\lambda }\right)L(d\lambda )}{{\int }_0^{\infty }\lambda L(d\lambda )}.$$(38)

Proof.

Note that

$$M_{{\mathcal{C}}^{*}}^{(N)}=\frac{m_{{\mathcal{C}}^{*}}^{(N)}}{{\lambda }^N}=\frac{m_{{\mathcal{C}}^{*}}^{(N)}/N}{{\lambda }^N/N};$$

the limit of the numerator is given in Theorem 6. For the denominator, we use (36) because $\frac{{\lambda }^N}{N}={\int }_0^{\infty }\lambda L_N(d\lambda )$, and we have uniform integrability. □

Note regarding Equation (38) that the numerator is bounded by ${\theta }^{*}$; indeed, we have $\lambda G_0({\theta }^{*}/\lambda )⩽{\theta }^{*}$ from Lemma 1, and L has unit mass. As the first moment of this distribution (in the denominator) becomes larger, the miss probability is smaller. This suggests that for L with infinite first moment, the miss probability will be zero. This is indeed true, but we must provide a separate argument because uniform integrability will not hold in this case. Our strategy will be to show that a suboptimal policy (the static one with ${\mathcal{C}}^s=\{1,\dots ,C\}$) already achieves vanishing asymptotic miss probability.

Theorem 7

(Asymptotic Miss Probability—Nonintegrable Case). Suppose that ${\int }_0^{\infty }\lambda L(d\lambda )=\infty$. Assume that $C/N\to c\in (0,1]$ as $N\to \infty$. Then,

$$M_{{\mathcal{C}}^{*}}^{(N)}⩽M_{{\mathcal{C}}^s}^{(N)}\underset{N\to \infty }{\to }0.$$(39)

Proof.

The first inequality is immediate by optimality of ${\mathcal{C}}^{*}$. So, we focus on the static policy, where misses are certain for $i>C$; therefore,

$$M_{{\mathcal{C}}^s}^{(N)}={\displaystyle \sum _{i=C+1}^N\frac{{\lambda }_i^{(N)}}{{\lambda }^N}}=\frac{\frac{1}{N}{\displaystyle \sum _{i=C+1}^N{\lambda }_i^{(N)}}}{{\lambda }^N/N}=\frac{{\int }_0^{{\alpha }_N}\lambda L_N(d\lambda )}{{\int }_0^{\infty }\lambda L_N(d\lambda )},$$(40)

where ${\alpha }_N=L_N^{-1}(p_N)$ is the $p_N$th quantile of $L_N$ and $p_N=1-\frac{C}{N}$.

Because $L_N\Rightarrow L$ and $p_N\to 1-c<1$, we have that $A≔{\sup }_N{\alpha }_N<\infty$. Then,

$$\underset{N\to \infty }{\lim \hspace{0.17em}\sup }{\displaystyle {\int }_0^{{\alpha }_N}\lambda }{L}_N(d\lambda )⩽\underset{N\to \infty }{\lim }{\displaystyle {\int }_0^A\lambda }{L}_N(d\lambda )={\displaystyle {\int }_0^A\lambda }L(d\lambda )<\infty .$$(41)

For the denominator, we have (Billingsley 1999, theorem 3.4)

$$\underset{N\to \infty }{\lim \hspace{0.17em}\inf }{\displaystyle {\int }_0^{\infty }\lambda }{L}_N(d\lambda )⩾{\displaystyle {\int }_0^{\infty }\lambda }L(d\lambda )=\infty .$$(42)

Together, (41) and (42) imply (39). □

As a comment on the above results, we note the following. When the distribution of item intensities is not uniformly integrable as, for example, in the Zipf case with $\beta ⩾1$, items with the largest intensities dominate the rest; thus, it is natural that the static policy would achieve asymptotic optimality and perfect performance regardless of the interarrival distribution. Note, however, that such convergence may be slow; we refer to Section 8 for examples.

In the more interesting case of uniform integrability with less disparate popularities, any causal memory management policy will incur some performance penalty; the minimum miss probability achieved by the optimal policy can be computed explicitly from the interarrival distribution characteristics and the storage fraction c.

6. Threshold Policies and Their Timer-Based Counterparts

In Section 4, we found that the optimal causal policy could be expressed in terms of a threshold on the observed stochastic intensity. This threshold is stochastically varying but converges in our large-scale regime to a deterministic constant.

This motivates us to look at policies that are defined by a deterministic threshold (i.e., where one keeps in memory items with stochastic intensity larger than $\theta$). An immediate observation is that in such policies, the memory constraint C would not be satisfied in a strong way at all times. Rather, we must replace it with the soft constraint where the average memory occupation is C. We now make this formal.

6.1. Threshold Policies and Memory Occupation

Consider a local memory system with independent request processes $\{{\mathrm{\Phi }}_i:i=1\dots N\}$, aggregated natural history ${\mathcal{F}}_t$, and stochastic intensities ${\phi }_i(t)$. Consider the following threshold policy:

(i.e., the store in memory of all of the items that have current stochastic intensity above the threshold $\theta$).

Because the ${\mathrm{\Phi }}_i$’s are stationary, the intensities ${\phi }_i(t)$ are also stationary, and thus, we have a stationary and causal policy. The memory occupation of this policy is now the stationary random process:

Its average can be computed as (using $t=0$ as a sampling point)

Note that $\text{E}[U_{\theta }(0)]$ is decreasing from N to zero as $\theta$ goes from zero to $\infty$. In order to have a fair comparison against a fixed memory constraint, define the threshold ${\theta }_C$ as

Thus, ${\theta }_C$ is the $1-C/N$ quantile of the average of the distributions of the stochastic intensities observed at time 0. From the right continuity of the distribution functions, it is easy to check that $\text{E}[U_{{\theta }_C}(0)]⩽C$ with equality if $1-C/N$ is a continuity point of the quantile function. We shall assume this henceforth to simplify exposition.

Because the arrival processes are independent, the random variables ${\phi }_i(0)$ are independent, and thus, we have the following proposition.

Proposition 1.

Assume that the above quantile is exact in the sense that $E[U_{{\theta }_C}(0)]=C$. Take $C=cN$ with $0<c⩽1$. Then, for any $\epsilon >0$,

$$\text{P}\left(\left|\frac{U_{{\theta }_C}(0)}{N}-c\right|>\epsilon \right)⩽2e^{-2N{\epsilon }^2},$$

and therefore, $U_{{\theta }_C}(0)/N\stackrel{\text{P}}{\to }c$ as $N\to \infty$.

Proof.

The proof follows from the Hoeffding inequality applied to the independent Bernoulli random variables $\{{\mathbf{1}}_{\{{\phi }_i(0)>\theta \}}\}$. In fact, for any N and $\epsilon >0$,

$$\text{P}\left(\left|\frac{U_{{\theta }_C}(0)}{N}-c\right|>\epsilon \right)=\text{P}\left(\left|{\displaystyle \sum _{i=1}^N{\mathbf{1}}_{\{{\phi }_i(0)>{\theta }_C\}}}-\text{E}\left[{\displaystyle \sum _{i=1}^N{\mathbf{1}}_{\{{\phi }_i(0)>{\theta }_C\}}}\right]\right|>N\epsilon \right)⩽2e^{-2N{\epsilon }^2}\text{.\hspace{1em}□}$$

From Proposition 1, we conclude that under independent request processes, the memory occupation of the threshold policy will not deviate much from a fixed memory policy for large N. We will use this to our advantage in Section 8.

6.2. Asymptotic Optimality of Threshold Policies

We focus now on the situation studied in Sections 4 and 5, where by Assumption 2, the request processes come from a common scale family. Furthermore, the traffic intensities satisfy Assumption 3.

In that case, ${\phi }_i(0)=X_i$, which is the observed stochastic intensity with distribution $G^{(i)}(x)$. Therefore, ${\theta }_C$ is the solution to the equation

Invoking Equation (23a) for the scale family and rearranging terms, we have

with the notation introduced in (30); invoking the distribution $L_N$ of traffic intensities ${\lambda }_i$, we may also write the above equation as

We are now in position to prove the following.

Proposition 2.

Consider a family of local memory systems indexed by N with request processes satisfying Assumptions 2 and 3. Choose the memory size of the Nth system as $C_N=cN$ with $0<c⩽1$. If there exists a unique solution to ${\theta }^{*}$ satisfying

$$G_{\infty }({\theta }^{*})=1-c,$$

then the sequence of thresholds ${\theta }_N≔{\theta }_{C_N}$ defined by (47) satisfies ${\theta }_N\to {\theta }^{*}$.

The essential step of the proof is to show that ${\overline{G}}_N\Rightarrow G_{\infty }$; this part is identical to the proof of Theorem 5. The result then follows from the convergence of quantiles.

Let us now analyze the asymptotic performance; considering an object i, its miss probability is given by

Therefore, the total miss probability for system N is given by

We can then state a result analogous to Theorem 6 and Corollary 1 for the asymptotic performance.

Proposition 3.

Under the conditions of Theorem 6, the asymptotic miss probability satisfies

$$\underset{N\to \infty }{\lim }{M}_{{\theta }_N}=\frac{{\int }_0^{\infty }\lambda G_0\left(\frac{{\theta }^{*}}{\lambda }\right)L(d\lambda )}{{\int }_0^{\infty }\lambda L(d\lambda )}.$$

The proof is substantially easier than in the case of Theorem 6 because the threshold ${\theta }_N$ is deterministic instead of depending on the state of the remaining processes.

Indeed, by Lemma 1 and the fact that ${\theta }_N\to {\theta }^{*}$, we see that the function $\lambda G_0({\theta }_N/\lambda )$ is uniformly bounded for all N. Taking proper account of continuity as in Theorem 6, the numerator converges as stated. For the denominator, we invoke uniform integrability.

The main conclusion of this analysis is that under the above assumptions, a deterministic threshold policy with a soft memory constraint is asymptotically equivalent to the optimal causal policy derived in Section 3 both in terms of memory usage and in terms of performance.

We shall show now that there is a strong connection between threshold policies and timer-based ones.

6.3. Connection with Timer-Based Policies: Monotone Hazard Rates

To end this section, we would like to highlight a strong connection between threshold policies and timer-based ones in the case where the requests follow renewal processes. Timer-based or time-to-live caching has been a long-standing idea in local memory systems; here, each time a request for item i occurs, a timer is started, and the item is kept in memory up to the timer expiration. When a new request arrives, the timer is reset. TTL policies were first analyzed in terms of point process requests in Fofack et al. (2014), and the optimal timers under stationary requests were obtained in Ferragut et al. (2016).

Consider the policy defined in (43) with deterministic threshold ${\theta }_N={\theta }_{C_N}$ from Equation (46). Assume that the incoming processes are renewal and that the interarrival hazard rates are strictly monotonically decreasing over the distribution domain (as in the Pareto parametric example). Assume for simplicity that the threshold ${\theta }_N$ lies in the range of the function ${\eta }_i(·)$, and define

Then, because ${\eta }_i$ is decreasing, we have

in panel (b) of Figure 4, we illustrate this condition. Consequently, in the case of monotonically decreasing hazard rates, the threshold policy is exactly equivalent to TTL caching.⁴ This is consistent with the characterization of optimal timers in Ferragut et al. (2016). In addition, from the asymptotic optimality of threshold policies established above, we further conclude here that TTL caching is asymptotically optimal.

An analogous discussion is valid for monotonically increasing hazard rates; here, the likelihood of a subsequent request is smallest immediately after receiving one, and thus, caching is not useful. Instead, it was proposed in Ferragut et al. (2024) to remove the item and prefetch it at an appropriate later time. In fact, this strategy can also be cast as a threshold policy by observing (see Figure 4) that

so the threshold policy removes the object from memory and recalls it after a time $T_i^{(N)}$; these timers coincide with the optimal timer prefetching policy from Ferragut et al. (2024). Once again, the asymptotical optimality of threshold policies allows us to further conclude that timer-based prefetching is asymptotically optimal for request processes with increasing hazard rates.

7. Extension to Heterogeneous Object Sizes

The preceding model assumes that objects have equal sizes; they all have the same impact on memory, and the natural performance criterion is the hit probability determined by whether the object can be (fully) recovered from local memory upon request. In practice, items can have different sizes and therefore, unequal memory cost. Also, one can consider in the performance the value of a partial recovery of the object. We now formalize this approach, which was first proposed in Panigrahy et al. (2022), and we show how the previous results can be extended to incorporate this case.

Consider a local memory system fed by a family of request processes $\{{\mathrm{\Phi }}_i:i=1,\dots ,N\}$ with intensities ${\lambda }_i$, natural histories ${\mathcal{F}}_t^{(i)}$, and stochastic intensities ${\phi }_i(t)$. Again, let $\mathrm{\Phi }$ be their superposition, and let ${\mathcal{F}}_t$ be the aggregated history. Assume that each object i has a size $z_i>0$ and that the system has total memory C.

A causal policy $\tilde{\mathcal{C}}(t)$ will now be an ${\mathcal{F}}_t$-predictable stochastic process $\tilde{\mathcal{C}}:\mathrm{\Omega }\times \mathbb{R}\to {[0,1]}^N$, where $\tilde{\mathcal{C}}(t)$ represents the fractions of each file stored in the local memory. For feasibility, the policy should satisfy the memory constraint

Thus, we are allowing fractional caching (i.e., only part of the item to be stored in memory).

Assume that whenever a request for item i arrives at time t, it can recover from the local memory $z_i{x}_i(t)$ and derives a utility from this amount of content $U_i(z_i{x}_i)$, where $U_i$ is a concave function. In this scenario, the analogue of the hit process is the following utility process:

The process ${\Upsilon }_{\tilde{\mathcal{C}}}$ is a measure-valued process that stores the utility derived from the local memory retrievals. For the special case where $U_i(z)=z$, we recover the byte-counting process in Panigrahy et al. (2022) because it keeps track of the amount of data recovered from the local memory in any time interval.

Now, let this local memory system be fed by a superposition of request processes $\{{\mathrm{\Phi }}_i:i=1,\dots ,N\}$ satisfying Assumption 1. We have the analogue of Lemma 2.

Lemma 4.

Let $\tilde{\mathcal{C}}(t)$ be a causal policy. The stochastic intensity of the utility process (49) with respect to the aggregated history ${\mathcal{F}}_t$ is

$$u_{\tilde{\mathcal{C}}}(t)={\displaystyle \sum _{i=1}^N{\tilde{\phi }}_i}(t)U_i(z_i{x}_i(t)).$$(50)

The proof is similar to the proof of Lemma 2, changing the predictable process ${\mathbf{1}}_{\{i\in \mathcal{C}(t)\}}$ for the fractional caching version $U_i(z_i{x}_i(t))$, where $x_i(t)$ is predictable by assumption.

Consider now the policy ${\tilde{\mathcal{C}}}^{*}(t)$ defined by solving the following optimization problem:

We then have the analogue of Theorem 3.

Theorem 8.

Given a local memory system with total memory C fed by a family of stationary point processes, $\{{\mathrm{\Phi }}_i:i=1,\dots ,N\}$ with aggregated natural history ${\mathcal{F}}_t$, satisfying Assumption 1. Assume that the item sizes are $\{z_i:i=1,\dots ,N\}$ and that the system may store fractional items. Then, for any causal policy $\tilde{\mathcal{C}}(t)$, the stationary utility rate $u_{\tilde{\mathcal{C}}}$ satisfies

$$u_{\tilde{\mathcal{C}}}=\text{E}\left[u_{\tilde{\mathcal{C}}}(0)\right]⩽\text{E}\left[u_{{\tilde{\mathcal{C}}}^{*}}(0)\right]=u_{{\tilde{\mathcal{C}}}^{*}}$$

with $u_{\mathcal{C}}(t)$ as in (50) and ${\tilde{\mathcal{C}}}^{*}$ as defined in (51).

The proof follows along the same lines of Theorem 3 by observing that the policy ${\tilde{\mathcal{C}}}^{*}$ satisfies Equations (51) at all times.

Example 8

(Maximizing the Byte Count). If we take $U_i(z)=z$ for all i, then we recover the byte-counting process of Panigrahy et al. (2022). In that case, the optimization problem defining ${\tilde{\mathcal{C}}}^{*}$ becomes a linear program, and its solution can be given explicitly in terms of the stochastic intensities ${\tilde{\phi }}_i(t)$ as follows.

• Rank the contents in decreasing order of ${\tilde{\phi }}_i(t)$.

• Choose the first K objects satisfying

  $${\displaystyle \sum _{k=1}^{K-1}{z}_{i_k}}<C \text{and} {\displaystyle \sum _{k=1}^K{z}_{i_k}}>C,$$
  where $i_k$ denotes the ordering permutation of the first step.

• Take $x_{i_k}(t)=1$ for $k=1,\dots ,K-1$ and $x_{i_K}(t)=\frac{C-{\sum }_{i=1}^{K-1}{z}_{i_k}}{z_{i_K}}$.

In other words, at all times, store the most likely upcoming requests as dictated by the stochastic intensity up to filling up your memory.

Note that the policy in Example 8 ranks the objects again in terms of the stochastic intensity independently of the object size. In particular, the optimal policy can be cast as a dynamic threshold policy, where the threshold is the stochastic intensity of the Kth object (i.e., the one that completes the memory allocation). Because of this fact, we think that the asymptotic results of Sections 5 and 6 can also be extended to this case under the appropriate scaling assumptions. This topic will be pursued in future work.

8. Parametric Examples and Simulations

In this section, we provide some interesting parametric examples to highlight the power of the results, in particular enabling us to compute sharp estimates for the performance of a local memory system. We must specify the interarrival distribution of our scale family of request processes and the distribution of popularities. We begin with the Pareto–Zipf combination, which was already introduced in examples above. We then analyze a further example with increasing hazard rates.

8.1. Pareto Interarrival Times and Zipf Popularities

Consider first the Pareto interrequest times introduced in Section 2.3 with tail parameter $\alpha$. As we already mentioned, this family represents bursty traffic with decreasing hazard rates. For the base (unit intensity) process, we have the following distribution for (nonsynchronized) observed stochastic intensity:

Combine it with the Zipf popularities with tail parameter $\beta$ introduced in Example 6 with limit distribution

By appropriately integrating Equation (29), we can obtain the asymptotic distribution:

which is a relevant parameter in the following discussion. Note that $G_{\infty }(x)$ is continuous and takes the value $1-c_{\alpha ,\beta }$ at $x=\frac{\alpha }{\alpha -1}$. A depiction of $G_{\infty }(x)$ is given in Figure 5.

Because $G_{\infty }$ is strictly increasing, we can now solve for the unique asymptotic threshold ${\theta }^{*}$ as a function of the memory size c. Imposing $G_{\infty }({\theta }^{*})=1-c$, we get the following result:

In the case $\beta <1$, it is easy to see that the measures $\{L_N\}$ are uniformly integrable, and thus, we can compute the miss rate estimate from (37):

Substituting the appropriate threshold and noting that ${\int }_0^{\infty }\lambda L(d\lambda )=\frac{1}{1-\beta }$, we reach the following result for the asymptotic miss probability:

In Figure 6, we plot the asymptotic miss probability of Equation (53) for fixed $\alpha$ and c as a function of the popularity tail parameter $\beta$. We also compare it with the asymptotic miss probability of the static policy, which is derived in Ferragut et al. (2016) and is given by $1-c^{1-\beta }$ for $0⩽\beta ⩽1$. The optimal policy has the most advantage when popularities are more homogeneous; in particular, as $\beta \to 0$, we have $M\to {(1-c)}^{\frac{\alpha }{\alpha -1}}<1-c$ for any $\alpha >1$. The gain is larger as $\alpha$ decreases; the optimal policy capitalizes on the burstiness of the incoming traffic captured by the hazard rates.

A second observation is that convergence of the empirical distribution of the OSIs is very fast. In Figure 7, we plot a simulated sample in the steady state of ${\widehat{G}}_N(x)$ for $N=100$ items for $\alpha =2$ and $\beta =0.5$ as an example. We see the convergence to $G_{\infty }(x)$ as established in Theorem 5.

Moreover, because convergence to $G_{\infty }$ is fast, convergence of the random threshold ${\widehat{\theta }}_N≔{\widehat{Q}}_N(1-c)\to {\theta }^{*}$ is also fast. We plot panels (a) and (b) of Figure 8 two examples with the same parameters as above for N = 1,000 and 10,000, respectively. The threshold process ${\theta }_N(t)$ is approximately constant for large N around the value ${\theta }^{*}$.

This last observation is crucial for developing finite N approximations for the performance. Because of the fact that when $\beta \to 1$, the family of distributions $\{L_N\}$ approaches nonuniform integrability, convergence of the miss rate estimate $m_{{\mathcal{C}}^{*}}^{(N)}$, the total rate ${\lambda }^{(N)}$, and the miss probability $M_{{\mathcal{C}}^{*}}^{(N)}$ is slow around this value as depicted in the simulations shown in Figure 9.

In order to compute finite N approximations, we use the intuition developed in Equation (35); that is, we compute the asymptotic threshold ${\theta }^{*}$ by solving $G_{\infty }({\theta }^{*})=1-c$ and plug in this estimate in place of the random threshold ${\widehat{\theta }}_N$. Then, we estimate $M_{{\mathcal{C}}^{*}}^{(N)}$ as

This turns out to be equivalent to approximating the optimal performance for that of the fixed threshold policy discussed in Section 6, and it is numerically easy to compute, even for distributions that do not have closed-form expressions as in this case. Therefore, this procedure provides sharp estimates of the maximum achievable performance for any policy and finite N. An example of this approximation is depicted in the dashed lines in Figure 9.

8.2. Erlang Interrequest Times and Zipf Popularities

We now turn our attention to a different example, where the hazard rate of the interrequest distribution is increasing. This leads to a totally different behavior; for instance, caching is not a good idea in this setting because upon receiving a request, a subsequent request becomes less likely. It is actually preferable to remove the content from memory and prefetch it again closer to request time (Ferragut et al. 2024).

Of course, the optimal memory management policy designed in Section 5 does this automatically by keeping track of the hazard rates, and all of the asymptotic results derived for it are still valid in this case.

To illustrate this behavior, we choose the interrequest times to be distributed as an Erlang distribution with k stages and appropriate means. For $k=1$, this corresponds to the Poisson process because interrequest times become exponential. As k grows, the process approaches deterministic interrequest times, and thus, the traffic pattern becomes more regular.

To be precise, let the base interrequest distribution be Erlang with k stages and mean of one (so $\lambda =k$). This corresponds to the following:

This yields the following nice formula for the hazard rate function:

where $B(A,C)$ is the classical Erlang-B formula for the blocking probability of telephone systems. For $k>1$, this becomes strictly increasing in t, $\eta (0)=0$, and $\eta (t)\uparrow k$ when $t\to \infty$.

We do not have analytical expressions for the age distribution or for the observed hazard rates, so $G_{\infty }$ must be estimated numerically. We do so for the Zipf popularity distribution limit $L(\lambda )$ introduced above. We plot the resulting distribution in Figure 10 together with a simulation of the empirical version ${\widehat{G}}_N(x)$ for N = 1,000, showing good convergence. Also, in Figure 10, we show the threshold ${\widehat{\theta }}_N$ evolution over time for the optimal policy, showing convergence to the numerically computed limit ${\theta }^{*}$.

Finally, in Figure 11, we plot the asymptotic miss probability of the optimal policy numerically computed from Equation (38) as well as a simulation of the optimal policy for N = 1,000 as a function of parameter $\beta$. As discussed above, convergence to the performance limit is slow when $\beta$ approaches one, so we compute the performance estimate from (54), which also corresponds to the optimal prefetching policy from Ferragut et al. (2024), showing good fit. As a comparison, the classical LRU policy is also simulated for the traffic pattern. As we discussed above, classical caching performs badly because of the regularity of the request process.

8.3. Practical Implementation

Although our paper is focused on theoretical results for the optimal management of local memory systems, it is important to discuss possible practical implementations of the optimal policy. From Theorem 3, we know that the key point to implement the optimal policy is correctly estimating the stochastic intensities of the underlying request processes, a well-known hard problem in statistics (Daley and Vere-Jones 2003, chapter 7.5) with few results.

In the case where the incoming processes are independent and renewal processes, the problem boils down to estimating the hazard rate function of each stream based on previously recorded requests. Hazard rate estimation from life tables and for discrete random variables is a well-studied issue, with estimators such as the Kaplan–Meier estimator for the hazard rate and the Nelson–Aalen estimator for the cumulative hazard rate, respectively (Colosimo et al. 2002). In the continuous setting, some sort of kernel smoothing must be done (Tanner and Wong 1983) because by definition, the hazard rate depends on the underlying density of the distribution, so the problem is completely related to kernel density estimation.

Nevertheless, in our case, we can propose a practical algorithm along the lines of the Nelson–Aalen estimator. We first discuss this for a given item i, so we drop the dependence on i to ease the notation. Begin by observing that the hazard rate is given by

where $F_0$ is the interarrival distribution. In particular, $-\log (1-F_0(t))$ is the cumulative hazard rate function. The algorithm will proceed as follows.

• Keep track of the observed interrequest times $\{{\tilde{\tau }}_k:k=1,\dots ,M\}$ up to time t.

• Construct the ordered sample $\{{\tilde{\tau }}_k^{*}:k=1,\dots ,M\}$.

• Measure the current elapsed time because the last arrival $t_0≔t-{\tau }^{-}(t)$.

• Find k such that

  $${\tilde{\tau }}_{k-1}^{*}⩽t_0<{\tilde{\tau }}_k^{*}$$

  (i.e., the interval in the sample that contains the current elapsed time).

• Estimate the hazard rate at elapsed time $t_0$ as the slope of the empirical cumulative hazard rate between times ${\tilde{\tau }}_{k-1}^{*}$ and ${\tilde{\tau }}_k^{*}$, which can be directly computed as

  $$\widehat{\eta }(t_0)=\frac{\log \left(1+\frac{1}{N-k}\right)}{{\tilde{\tau }}_k^{*}-{\tilde{\tau }}_{k-1}^{*}}.$$

Note that the computational complexity of this algorithm is high because we must keep track of a large-enough sample of interarrival times (something that is difficult to achieve for less popular items), and we must do so for each item in the catalog. We must also keep these interarrival times sorted and find the correct interval to evaluate the slope dynamically as time elapses.

This is why more computationally efficient algorithms are needed. In particular, the classical and simple LRU algorithm seems well suited but only in the case of decreasing hazard rates or bursty traffic. For more regular traffic, like in the increasing hazard rate case, the problem is still open.

9. Conclusions

This paper analyzes the optimal management of local memory systems with tools of stationary point processes. As a first contribution, we provided a rigorous setting for this problem, and under suitable assumptions, we characterized the optimal policy (in the sense of maximizing hit rates) to store in memory at every moment the items corresponding to the highest stochastic intensities.

From this starting point, for the case of independent request streams, we analyzed the limiting behavior of the optimal policy as the catalog size $N\to \infty$ when a fixed fraction c of items can be stored. Assuming that item request processes come from a common scale family with intensities that have a limit in distribution, we proved that the optimal policy amounts to comparing the stochastic intensity (observed hazard rate) of the process with a fixed threshold defined by the $1-c$ quantile of a certain limiting distribution function. We further characterized the asymptotic performance (miss probability) of this optimal policy.

We also analyzed optimal threshold policies for the finite N case that satisfy the memory constraint in the mean. We showed that they have the same limiting behavior as the optimal policy. Moreover, we found that for renewal traffic and monotonic hazard rates in the interrequest distribution, these are equivalent to timer-based policies, where caching or prefetching times are determined by a hazard rate threshold. We also showed that some of the optimality results presented extend quite nicely to the case of heterogeneous object sizes and fractional caching.

Finally, we presented two detailed examples of our results for the standard Zipf model of item popularities and two cases for the interrequest process. For the bursty, decreasing hazard rate case of Pareto interarrival times, we obtain closed-form expressions for the optimal asymptotic threshold and the corresponding performance. We also provide sharp estimates of the optimal performance for finite N validated by detailed stochastic simulations. For the regular, increasing hazard rate case of Erlang interarrival times, closed-form expressions are not available, but we still carry out a numerical validation of the asymptotic threshold and performance. We also use this example to exhibit the significant superiority of the optimal policy in comparison with the popular LRU policy in contrast with the bursty case where LRU has good behavior.

For future research, we may explore the application of our machinery to characterize optimality for other kinds of request traffic: Markov-modulated Poisson processes to account for time variations, more general mixtures of traffic from different sources, and possibly, heterogeneity in item sizes as well as different popularity distributions.

Also, note that as presented, the optimal policy serves as a fundamental limit on the achievable performance but not necessarily a practical algorithm because it requires knowledge of the relevant item intensities and hazard rate distributions. This poses the question of possibly learning this information from the actual request data and alternatively, designing an eviction policy that does not make explicit use of these quantities but approximates optimal performance in practice; to some extent, LRU achieves this in the bursty case, but a counterpart for the increasing hazard rate is currently open.