I. INTRODUCTION

The recent advances in the development of capable smart wireless devices and mobile internet services have resulted in rapidly escalating levels of data traffic over cellular networks. This surging data demand is depleting the limited spectrum resources for wireless transmission, especially over the wireless connection between the base stations and the end-users. Consequently, wireless resources are becoming scarce due to the tremendous development of throughputhungry applications including video streaming and online gaming [1]. Thus, more sophisticated resource management strategies are needed to meet the growing demand [2].

One possible solution for tackling this problem is to cache popular contents at the users' site to reduce the total response time to data requests. Content Distribution Networks (CDNs) utilize a large mesh of caches to deliver content from locations closer to the end users [3], [4]. Existing caching strategies rely on the assumption of static (or quasi-static) nature of the stored content [5], [6]. In many real-world scenarios, such as news updates in social networks and system state updates in cyber-physical networks, the data content is subject to updates at various rates, which render the older versions of the content less useful [7]. Hence, there is a growing need to develop new caching strategies that account for the refresh characteristics and ageing costs of content for efficient dynamic-content distribution.

Broadly speaking, there are two classes of caching policies for studying the system performance: timer-based, i.e., Time-To-Live (TTL) [8], [9] and non-timer-based caching policies. In the latter case, the strongly coupled nature of the eviction policies render exact analysis difficult. In contrast, a TTL cache policy associates each content with a timer upon placement in the cache. The content is then evicted once the timer expires, independent of other cached contents. Due in part to analytical tractability [8], [10], TTL caches have been widely employed since the early days of the internet with the Domain Name System (DNS) being an important application [11]. Recently, TTL caching strategies have received renewed attention, mainly because they enable a general analytical approach which is used to model replacementbased caching policies such as Least Recently Used (LRU) [12].

Using the TTL cache refresh framework for dynamic content, [13] proposes two metrics to measure the cached content freshness: age of synchronization (AoS) and age of information (AoI). Most existing research regarding the freshness of the local cache focus on the AoI metric which was first examined in the 1990s in studies on real-time databases [14], [15].

The problem of refreshing cache contents from an AoI perspective was first formulated in [16], where a remote server generates multiple files and transmits them to a local cache. The authors assume that each file has its own request popularity, a factor that affects how often the server should update the file contained in cache. The objective is to minimize the average AoI [17]. In [18], the authors formulate the AoI problem for a system with random transmission and service processes. They show that the age decreases with increasing service rate. Nevertheless, this comes at the cost of increased waste in the resources spent on obsolete packets [19]. Najm et al. [20] analyze the average age and average peak of AoI under the gamma distributed service time. Sun et al. [21] study how to optimally manage the freshness of information using AoI metric and under a general age penalty function to show that a zero-wait policy does not always minimize the age. Kam et al. [22] propose a dynamic model in which the rate of requests depends on the popularity and the freshness of information to minimize the number of missed packet requests.

While AoI is a meaningful metric for measuring the freshness of content in some systems, there are many realworld scenarios where a content does not lose its value simply because time has passed since it was put into the cache. These types of dynamic contents include news and social network updates where the users prefer to have the most fresh version but so long as there is no new update, that content is considered to be the most fresh version. In this work, we use a new freshness metric called Age-of-Version (AoV) which counts the integer difference between the versions at the database and the local cache. We also introduce a new cost function for dynamic content caching which captures both the cost due to the miss event and the cost due to content freshness [23] which grows with the AoV metric. Moreover, our model extends the traditional caching paradigm to allow for varying generation dynamics of content, and calls for new designs that incorporate these dynamics into its decisions.

In particular, we propose a freshness-driven caching model for dynamic content, which accounts for the update rate of data content and provides an analysis of the average operational cost for both the constrained and unconstrained cache sizes. We aim to reveal the effect of popularity and refresh rate on the optimal caching policies. Our contributions, along with the organization of the paper, are as follows.

• In Section II, we present a tractable caching model for serving dynamic content to end users from a back-end source and formulate the general problem. • In Section III, we attack the generally intractable problem for the special and insightful case when there is no cache constraint, i.e., all items can be stored in the cache. We characterize the optimal caching decision and explicitly identify the optimal holding time of each item in terms of its popularity and its refresh rate, which reveals the balance between the fetching cost of a fresh update and the ageing cost of serving an old version. • In Section IV, we return to the general cost minimization problem under high-probability, and an associated average cache size constraints to propose an asymptotically optimal caching solution. The solution reveals the interesting fact that, for fresh caching of dynamic content, one should select the items to cache based on their popularities, while determining the holding times of the cached items based on their refresh rates. • In Section V, we contrast the operational cost and average cache occupancy of the constrained cache with their The results show that the asymptotically optimal solution presented in Section IV can yield significant cache savings by discarding static items that are not sufficiently popular, and using the limited cache space efficiently for sufficiently popular dynamic and static items. Finally, we conclude the work in Section VI.

II. SYSTEM MODEL

We consider the generic hierarchical setting depicted in Fig. 1, whereby: the (limited) local cache serves a user population that makes requests of content according to a popularity distribution; while the back-end database receives updates to update the content with different rates. Next, we will provide the details of this generic model, followed by the goal of our work. Demand Dynamics: We assume that a set N of N unitsize data items (with dynamically changing content) is being served to a user population by the hierarchical caching system in Fig. 1. In particular, requests arrive to the local cache according to a Poisson processfoot_0 with rate β ≥ 0, which captures the request intensity of the user population. An incoming request targets data item n ∈ N with probability p n . Accordingly, the probability distribution p = (p n ) N n=1 captures the popularity profile of the data items. Generation Dynamics: At the database, each data item may receive updates to replace its previous content. We assume that data item n receives updates according to a Poisson process with rate λ n ≥ 0. Note that λ n = 0 encapsulates the traditional case of static content that never receives an update. We denote the vector λ = (λ n ) N n=1 as the collection of update rates for the database. Age Dynamics: Since the data items are subject to updates at the database, the same items in the local cache may be older versions of the content. To measure the freshness of local content, we define the age ∆ n (t) ∈ {0, 1, . . .} at time t of a cached content for item n as the number of updates that the locally available item n has received in the database since it has been most recently cached. We name this freshness metric as the Age-of-Version (AoV), since it counts the integer difference between the versions at the database and the local cache. Fig. 2 illustrates an example evolution of ∆ n (t) for data item n under an arbitrary holding and eviction policy. At the instant t n,i , the local cache refreshes its content of data item n for the i th time. This item remains in the local cache for a duration of τ n,i ∈ R + units of time. In this sample path, the item is evicted from the local cache at time instance t n,i = t n,i + τ n,i . During the phase t ∈ [t n,i , t n,i ), the AoV ∆ n (t) of item n grows according to a Poisson process with rate λ n , as governed by the aforementioned generation dynamics. At the eviction instant t n,i , the ∆ n (t) drops to zero by default since the next request for the item that arrives after a random duration (denoted as R n,i+1 in the figure) will be serving a fresh update from the database.

Within the subsequent evictions t n,i and t n,i+1 of the item n, we refer to: the phase (t n,i , t n,i + R n,i+1 ] as the miss phase, since the incoming request is not in the local cache and must be fetched from the database at a higher cost; and the phase (t n,i + R n,i+1 , t n,i+1 ] as the hit phase, since the incoming request is served from the local cache, but possibly with a positive AoV value ∆ n (t). Fetching and Ageing Costs: Now that we have the dynamics defined, we can introduce the key operational and performance costs associated with our caching system. On the operational side, we denote the cost of fetching an item from the database to the local cache by c f > 0. On the performance side, we assume that serving an item n from the local cache with age ∆ n (t) incurs a freshness/age cost of c a × ∆ n (t) for some c a ≥ 0, which grows linearlyfoot_1 with the AoV metric. This ageing cost measures the growing discontent of the user for receiving an older version of the content she/he demands. Problem Statement: Our broad objective in this work is to develop efficient caching and eviction strategies for the above setting that optimally balance the tradeoff between the cost of frequently updating local content and the cost of providing aged content to the users. In particular, we are interested in provably cost-minimizing caching-and-eviction strategies that account for both the demand and the generation dynamics in order to optimally utilize a possibly limited cache space B ∈ [0, ∞] at the local cache. We can express this goal generically as

where C π represents the mean of the combined fetching and ageing cost of the system, and X π n (t) ∈ {0, 1} is the indicator that item i is in the local cache under the operation of a feasible policy π. In its full generality, the feasible policy space Π can contain any policy that decides on its fetching and eviction decisions at time t with the knowledge of the cache content until time t and the generation/demand dynamicsfoot_2 (λ, β, p), but not the ages {∆ n (t)} n (since that information depends on the updates occurring at the backend database). Outline of our Approach and Results: The generic problem in (1) falls under the scope of Partially Observable Markov Decision Processes (POMDP), and quickly becomes intractable [24]. Even formulating the problem explicitly, let alone solving it, becomes practically impossible. Therefore, a more productive approach is needed to attack this problem in order to develop algorithms and principles with performance guarantees. In this work, we propose such an approach whereby we: (i) first study the unconstrained version of the problem where B = ∞ in Section III, which reveals how the caching and eviction decisions must depend on the generation and demand dynamics; and then (ii) extend our approach to a constrained version in Section IV, where we can guarantee that the B < ∞ cache limit can be satisfied with arbitrarily high probability as the database size N increases. This approach is not only productive in designing of policies with asymptotically optimal and cachespace efficient, but also reveals new and explicit metrics (cf. Theorems 1 and 2) for easily measuring the importance of content in terms of its popularity and refresh rates. Throughout the paper, we use cache to refer to the cache size available in the local server.

III. OPTIMAL CACHING FOR DYNAMIC CONTENT

WITHOUT CACHE CONSTRAINTS In this section, we attack the generally intractable problem in (1) for the special and insightful case when there is no cache constraint, i.e., B = ∞. The characterization of the optimal caching decision in this section under this unconstrained setting will not only yield interesting insights about the impact of the generation dynamics, but will also form the basis of our approach to handling the cache-constrained case with high probability guarantees in Section IV.

We start by noting that the relaxation of the constraint decouples the problem into finding the optimal fetching and eviction decisions for each data item n independently. This is obvious once we note that the contribution of each item to the average cost is independent of the others. This motivates us in this setting to focus on a space of policies T with random holding times, defined next.

Definition 1 (Policy Space T ): T denotes the space of policies with random holding times, where a policy τ ∈ T is defined by N (non-negative-valued) random variables (τ n ) N n=1 , representing the holding times of the items after their last fetching. In particular, the policy τ = (τ n ) N n=1 operates as follows for each item n ∈ N : (i) if item n is not in the local cache when it is requested at time t, a fresh version of it is fetched from the database (at cost c f ) and served to the user; (ii) at the time of fetching item n into the local cache, a random holding time is generated (independently from previous realization of holding times) with respect to the distribution of τ n , and item n is held in the queue for the duration of the generated τ n value, at which time it is evicted from the local cache; (iii) if item n is in the local cache when it is requested at time t, it is served (with age-of-version cost of c a ∆ n (t)) to the user.

The space T takes advantage of the decoupling of the caching decisions between items as well as possesses the flexibility to adapt to different generation and demand dynamics of data items. The next lemma explicitly characterizes the average cost and average cache size of such a policy τ ∈ T in terms of the first and second moments of the holding time distributions of the policy τ .

Lemma 1: Let C(τ ) and B(τ ), respectively, denote the average cost and the average cache occupancy when the policy τ ∈ T is implemented for the caching system without cache constraints at the local cache. Then,

where (λ, β, p) are the system model parameters (cf. Section II) and (τ n ) n are the random variables describing the policy τ (c.f. Definition 1).

Proof. The average system cost utilizing the local cache to serve the requests comprises two main terms. Average fetching cost associated with requests that are not in the cache after a miss event. And, average freshness cost associated with requests that are served from the cache after a hit event, in which case an ageing/freshness cost is incurred due to the fact that the cached content may not be the most fresh version. Then the average cost C(τ ) under the policy τ ∈ T can be expressed as:

where ∆ n (τ ) is the time average age of the data item n served from the local cache when the policy τ ∈ T is implemented. Based on Renewal Reward Theorem, we have:

where A n,i is the area shown in Fig. 2 and the last equality comes from the fact that:

and N n (t) is a Poisson process with parameter λ n which is independent of τ n,i . Then noting that

gives us the result. We omit the indices i for convenience.

Next, let us denote the steady-state hit probability under the caching policy τ as h n (τ n ) = P ( Xn (τ ) = 1), where Xn is the limiting distribution of X n (t) that is the indicator of whether item n is in the local cache at time t or not (cf.

(1)). Using the illustration of Fig. 2, it is easy to confirm that the hit probability for content n can be expressed as:

where R n is the interarrival time between requests of item n. Since requests for item n arrive at the cache according to a Poisson process with rate βp n , we have E[R n ] = 1 βpn . Then, substituting in (5), we get the cost expression of (2).

Using the hit probability given in ( 5) and noting that

The explicit characterization of the cost under Lemma 1 allows us to pose the problem of finding the cost minimizing policy in this setting as:

where the minimization is performed over all distributions for the holding times (τ n ) n with non-negative ranges, and the tuple (λ, β, p) indicates that the solution is a function of these system parameters. For brevity, we will occasionally omit these parameters and refer to the optimal cost as C * , and later on we will also use C * (N ) when we study the scaling of the performance as the database size N grows.

The following theorem fully solves (6). Theorem 1: Policy τ * ∈ T that solves ( 6) is given by:

where D = {n ∈ N | λ n > 0} , and S = {n ∈ N | λ n = 0} = N \D are, respectively, the set of dynamic and static data items. Then, the corresponding optimal average cost is given by:

Also, the average cache occupancy under τ * is given by:

Proof. First we show that the average system cost given in ( 2) is minimized when the variable τ n is a constant, ∀n. For a random variable τ n with expectation E[τ n ], in order to minimize the cost, the second moment 2 which is a constant random variable. In calculating (2) we assumed that steady state distribution exists for the given random variable τ n . Now we verify it for the constant random variable τ n .

Lemma 2: For a constant random variable τ n , Bernoulli process (X n (t), t ≥ 0) has a steady state distribution and its average is given by (5). Proof. According to Fig. 2, for data item n, define a new random variable

βpn . Based on the instances of random variable Z n , define S q n = q i=1 Z n,i = q i=1 (R n,i + τ n ) to be the time of the q th renewal when the data item n enters the cache for the q th time. Let W (t) be the number of times that data item n has evicted from the cache up to time t. Blackwell's renewal theorem states that for any fixed

which shows the existence of the steady state distribution. Therefore the random process (X n (t), t) has a steady state distribution with its average given by the above equation.

The cost minimization problem for the unconstrained cache can thus be expressed as:

The objective function has the form of quadratic over linear ratio, which is convex. Using KKT conditions gives the optimal solution for τ * in (7). Substituting τ * in (2) gives the optimal of (8).

To prove the optimal average cache occupancy substituting the optimal solution (7) in the definition of average cache occupancy given in Lemma 1 and noting that τ * n = ∞, ∀n ∈ S, we obtain n∈S βpnτ * n 1+βpnτ * n = |S| which completes the proof.

Theorem 1, under the unconstrained cache setting, provides some useful insights about the nature of the optimal caching strategy for dynamic content: (i) we see that the cost minimizing policy τ * selects a fixed holding time for each item n rather than any other random choice; (ii) more interestingly, (7) explicitly characterizes the optimal holding time of each dynamic item n in terms of its popularity p n and its refresh rate λ n in order to strike the optimal balance between the fetching cost of a fresh update and the ageing cost of serving an old version; (iii) less interestingly, we also see that any static item is cached forever under this unconstrained setting since it is never necessary to update it once it is fetched; and (iv) it explicitly characterizes the average cache occupancy of τ * in terms of system parameters.

In the next section, we will build upon this foundation to return to a soft-constrained version of the problem (1).

IV. ASYMPTOTICALLY-OPTIMAL CACHING FOR DYNAMIC CONTENT WITH CACHE CONSTRAINTS

Returning the general cost minimization problem given in (1), the instantaneous cache size constraint with B < ∞ entails a dependence between the optimizing items holding time. With such a dependence the optimization (1) suffers from the curse of dimensionality and has no tractable solution. In this section, we bypass this challenge by replacing the deterministic-constraint N n=1 X π n (t) ≤ B, at all times t, to a probabilistic-constraint where cache size limit has to be met with (arbitrarily) high probability over time. In particular let us introduce the following probabilistic version of (6):

for any arbitrarily small δ > 0, where Xn (τ ) is the steadystate fraction of time that item n is held in the cache under policy τ . Such probabilistic approaches to solving deterministic problems are used increasingly frequently and fruitfully in learning and optimization domains. Solving this high-probability variation of the hard problem, in turn, provides a means to operate the original system efficiently with arbitrarily high probability. Despite its softer statistical form, solving (10) is still complicated by the need to design with guarantees in the tail distribution of its cache use. To tackle this challenge, we, in turn, pose the following average-cache-constrained problem with a flexible choice of cache size bound B ∈ [0, ∞) :

where B(τ ) is the average cache occupancy under the policy τ that is explicitly characterized in (3). We note that this problem is non-convex since the constraint set {τ : B(τ ) ≤ B} is non-convex. Nevertheless, the approach in the rest of the section is to first solve the non-convex problem (11) for any given B, and then choose a particular B as a function of the given B < ∞ and δ > 0 in order to guarantee the probabilistic constraint in (10). Accordingly, we first provide the solution of (11) in the next theorem. Theorem 2: Policy τ * = (τ * n ) n ∈ T that solves ( 11) is given by deterministic τ * n ≥ 0, ∀n, and α * ≥ 0 satisfying:

where [z] + = max(0, z), and

where D and S are, respectively, the set of dynamic and static data items defined in Theorem 1.

Proof. In the proof of Theorem 1, we showed that in order to minimize the cost, the random variable τ n should be a constant. Also, Lemma 2 shows that for such a constant random variable τ n , the Bernoulli process (X n (t)) t has a steady-state distribution whose average is given by (5). Therefore the assumptions to calculate the average cost and average cache occupancy given in ( 2) and (3) hold and the optimization problem (11) can be rewritten as:

This is not a convex optimization problem. However, we take the following approach to solve it. Define the feasible set F B as:

which is a non-convex set. Then the cost optimization problem ( 11) can be expressed as:

For any optimization problem min τ ∈F C(τ ) as it is given in [25], if all the following hold: 1) Slater condition, 2) non degeneracy assumption for ∀τ ∈ F , 3

Lemma 3: Optimization problem ( 14) satisfies all the above four necessary conditions. Proof. (Lemma 3) Please refer to Appendix A.

Therefore, the non-trivial KKT solution to the problem ( 14) would be a global minimizer. Such a solution can be expressed as:

where α * ≥ 0 and μ * n ≥ 0 are the optimal Lagrange multipliers which satisfy all the following KKT conditions:

Accordingly, for dynamic data items, n ∈ D, with λ n > 0, we have:

while for static data items, n ∈ S, with λ = 0, we have: The form of the optimal solution in ( 12) reveals the interesting insights that, for dynamic content n ∈ D: whether to cache an item depends on whether it is sufficiently popular (in particular, whether p n ≶ α * βc f ); and how long a cached item will remain in the cache before eviction depends on its refresh rate λ n as characterized in (12). It can also be seen that, for the same system parameters (λ, β, p), as the average cache limit B decreases, then the optimal α * that solves ( 12)-( 13) will increase. Then, for both static and dynamic content, the popularity threshold α * /(βc f ) for caching or not caching the content increases to make sure only sufficiently popular items are cached. Now that we solved the average-cache-constrained problem (11), we are ready to connect it to the probabilistic problem (10) with the following proposition.

Proposition 1: For any finite B > 0 and arbitrarily small δ > 0, there exits

≤ δ , such that the solution τ * (δ) of ( 11) for B = B(δ) satisfies

Proof. (Proposition 1) Notice that Xn (τ ), ∀n ∈ N are independent Bernoulli random variables. We define a new random variable Y N (τ ) = N n=1 Xn (τ ), which is the sum of N independent Bernoulli random variables and is known to have a Poisson Binomial distribution. Also using the linear property of expectation and given that E[ Xn (τ )] = h n (τ ), we have:

.

For the random variable Y N with Poisson Binomial distribution, using the Chernoff bound we have:

Then to guarantee P (Y N ≤ B) ≥ 1 -δ, we have:

Proposition 1 provides an explicit means of using the tractable problem (11) to find efficient feasible solutions to the problem (10). To glean an insight on the structure of B(δ), suppose that m = 1 and δ = e -B/e , which is very small for sufficiently large B. Then, we have B(δ) = Be -1 .

In the next section, we will study the cost and cache occupancy performance merits of the proposed approximate optimization of (10) for large databases, which is commonly the case in content distribution networks. In particular, we will introduce the variable 0 ≤ m(N ) ≤ N as the number of most popular items that will remain in the cache after being fetched for the optimized holding times from (12). The remaining N -m(N ) items will never be cached, i.e., will only be fetched and served upon a user request and not cached. Then we will examine the cost-cache trade-off for this proposed strategy to show its desirable characteristics.

V. COST AND CACHE SPACE PERFORMANCE ANALYSIS

To establish the performance merits or the proposed approximate solution (τ * , α * ) given in ( 12) and ( 13), we contrast the operational cost and average cache occupancy of the approximate problem (11) with its counterpart of the unconstrained problem (6) in the asymptotic regime as the number of data items, N , grows.

We expose the dependence of the relevant quantities on N to highlight its impact on the analysis as follows. We denote the optimal cost and average cache occupancy of (6), respectively, by C * (N ) and B * (N ), whereas the cost and average cache occupancy of the proposed approximate problem (11) are denoted by C α(N ) and B α(N ), where the superscript α indicates the dependence of these values to the α parameter that is optimized in ( 12) and ( 13) for a given cache bound. Here, α ≥ 0 is a flexible parameter that allows us to explore the tradeoff between the cost and the cache occupancy. Note that C * (N ) = C * (λ, β, p) in ( 8) and B * (N ) = B(τ * ) in ( 9). In addition,

where (τ α, α) satisfies ( 12) and ( 13) for a given α ≥ 0 with the appropriate choice of B α as the corresponding cache limit in (10).

As the number of data items N grows, both the set of static items, S, and/or the set of dynamic items, D, grow in size accordingly, yet at different rates with N . Nevertheless, by the definition of D in Theorem 1, we can guarantee a minimum content update rate λ min > 0 for all the items n ∈ D for any number of data items N . That is, λ min = inf n∈D λ n > 0, ∀n ∈ N .

Further, for any given α ≥ 0, we define the set of popular items in the approximate problem (11), P α, as

to contain all the items that should be held in the cache after being fetched from the back-end database since (12) implies:

It is worth noting that, if α = 0, then P α = N and all data items are considered popular which collapses to the case of the unconstrained cached size optimization (6). The last step before stating the asymptotic gains of the proposed policy is to divide the set of static items into two disjoint subsets. A subset S α of static items that are popular, i.e., S α = S ∩P α, and a subset S α = S -S α of static unpopular items.

The following theorem jointly establishes the asymptotic optimality of the proposed approximate policy together with characterizing the cost-cache size trade off.

Theorem 3: For a given α ≥ 0, consider the policy τ α that solves (10) for a corresponding average cache bound B α and average cost C α. Let m(N ) = |P α| denote the number of sufficiently popular items that will be cached under τ α policy.

then: lim

), the rate of convergence is at least:

the average cache saving is lower bounded by:

and the average cache occupancy Bα (N ) is bounded by:

Proof. Without loss of generality, assume that p 1 ≥ p 2 ≥ • • • ≥ p N > 0. Since m(N ) = |P α| and according to the definition of the set of popular items P α given in ( 15), we will have α ≤ βc f p m(N ) for any given α where p m(N ) is the probability of the m(N ) th most popular item. Using the expressions for τ * n and τ α n given in ( 7) and ( 12) respectively, for dynamic data items we can show that:

Since τ *

n ≥ τ α n , ∀n ∈ N , applying Taylor series to average cost of the data item n will give us the following inequality:

The Lagrangian function L(τ α n , α, μ) of (10) takes the form:

where α ≥ 0 and μn ≥ 0, ∀n ∈ {1, 2, ..., N } are Lagrange multipliers. Note that since τ α n > 0, ∀n ≤ m(N ), we have that μn = 0, ∀n ≤ m(N ). Using the fact that τ α n is a nontrivial KKT point for a given α ≤ βc f p m(N ) and setting the derivative of Lagrangian function to zero, we have:

Apply (17) to each popular dynamic data item n ∈ D ∩ P α:

and apply it to each unpopular dynamic item n ∈ D -P α:

where the second inequality comes from the fact that p n (p m(N ) -p n ) ≤ 1 4 p 2 m(N ) . For popular static items n ∈ S α, we have τ * n = τ α n = ∞ according to (7) and ( 12) respectively. Therefore, we have Cn (τ α n ) = C * n = 0, ∀n ∈ S ∩ P α. For unpopular static items n ∈ S α, τ * n = ∞ according to (7) and according to (16) we have τ α n = 0. This gives C * n = 0 and Cn (τ α n ) = βp n c f based on the average cost function given in (2). Therefore,

Thus, the total average system cost is upper-bounded as:

λmin . Also, for unpopular static items we have p n ≤ p m(N ) , ∀n ∈ S α. Therefore we have that n∈S α p n ≤ p m(N ) |S α|. Finally, since we assumed that items are ordered based on their popularity and p m(N ) is the probability of m(N ) th most popular item, so p m(N ) ≤ 1 m(N ) . This gives us:

In order to make sure that the upper bound vanishes as N increases, we need 4 to have m(N ) = min(ω( √ N ), ω(|S α|)). This proves (i). To prove (ii), note that m(N ) = min(ω( √ N ), ω(|S α|)) is equivalent to b > min( 1 , a 2 ). Then the convergence rate of the upper bound becomes:

which demonstrates the smallest rate of convergence on the average cost. On the other hand, since m(N ) is the number of most popular items that we choose to cache while discarding all the other unpopular ones, we can show that:

where B α(N ) is the average cache occupancy under the proposed strategy. On the other hand, for the unconstrained cache system, we have:

Since P α -S ⊆ D and τ * n ≥ τ α n ≥ 0, ∀n ∈ N , we have that: Recall the average cache occupancy defined in (3) and note that according to (16) for unpopular items we have τ α n = 0, ∀n / ∈ P α. Also, according to Theorem 2, for static popular items we have τ α n = ∞, ∀n ∈ S α. This gives:

where |P α -S| = m(N ) -|S α| ≥ 0. Using the solution given in ( 12), we have:

Now, using the fact that:

we can show that the second term in the right side of ( 18) is lower-bounded by:

, where the second inequality comes from the fact that

λmin . Substituting the results gives the upper bound on the average cache occupancy completing part (ii) of the proof.

Theorem 3 reveals the potential of our proposed caching strategy which chooses items for caching based on their popularity and then incorporates the update rate of contents to decide how long each item should remain in the cache before eviction. Our proposed caching strategy completely discards the unpopular items, static or dynamic. More specifically, not caching the unpopular static items yields a very large gain on the cache saving side at a marginal loss on the average system cost side.

Theorem 3 shows that while the proposed strategy is asymptotically optimal for large data base sizes, it can also result in massive cache savings. This reveals that a cache size that grows with the rate of popular static items can achieve the same performance of having unconstrained cache size with the data base size being very large. As such, increasing the cache size beyond the threshold which is given as an upper bound in Theorem 3 will not reduce the average system cost for large data base sizes.

In the special scenario where the static items are unpopular for the given popularity measure α, i.e., S ∩ P α = φ, Theorem 3 reveals that a bounded cache size of βc f caλmin can be asymptotically optimal and achieve the same average cost of a system with unconstrained cache size, even if the database size grows to infinity. Specifically, our proposed strategy is asymptotically optimal while massively reducing the cache occupancy to a constant cache size which does not grow with N .

Notice that the average cache occupancy for the unconstrained cache is not necessarily bounded by the order of popular static items. Not only does our proposed caching scheme achieve the same average cost of the system with unconstrained cache asymptotically but it also maintains a cache size which does not grow linearly with N . In other words, intelligently choosing the items to cache is a critical factor to optimize the average system cost in dynamic caching. If the popularity of static items is low, then caching only dynamic items considerably reduces the system's cost and attains remarkable cache space savings.

According to Theorem 3, m(N ) determines the trade off between how much cache storage is saved and how fast the cost converges to the optimal. Larger m(N ) will result in a faster convergence but a smaller cache saving gain. To make this trade-off more clear through an example, consider a set of items with Zipf(1) popularity distribution and assume λ = 1 100 is equal for all the dynamic items. Consider m(N ) = N b , 0 < b ≤ 1 to be the number of most popular items that will be considered for caching and also assume |S α| = N 0.5 is the number of static items which are not in the popular set. According to Theorem 3, the sufficient condition for asymptotic optimality is b > 1 2 . For such a choice of m(N ) we, investigate the trade-off. We adopt the percentage cost reduction of our proposed caching strategy for the constrained cache to the optimal solution derived for the unconstrained cache as our performance metric. Such metric is defined as: Cost Reduction(%) = 100 × C α(N ) -C * (N )

This percentage is depicted in Fig. 3 as a function of cache saving for different values of N . According to the figure, and as expected from Theorem 3, for any choice of m(N ) = N b with b > 1 2 as N increases from 1000 to 10000, the proposed cost for the constrained cache converges to the optimal cost for an unconstrained cache size. The x-axis shows the amount of cache saving for the proposed strategy compared to the optimal average cache size for the unconstrained case. The figure illustrates that, as N increases, the cache saving also increases, while the cost of the proposed policy converges to the optimal cost. This behavior demonstrates the potential of our proposed asymptotic strategy in massive cache savings. In addition, as m(N ) increases, the rate of convergence increases at the expense of having smaller savings in the cache size, as predicted by our theoretical result. In other words, smaller m(N ) result in bigger cache saving but with a slower convergence rate in cost. This is exactly the trade-off that theorem 3 revealed for the proposed asymptotic strategy. In this work, we have proposed and investigated an increasingly important caching scenario for serving dynamically changing content. We introduced the age-of-version metric to capture the served content's freshness and track the number of stale versions per content. We have addressed the problem of developing optimal caching strategies for minimizing the system's cost which is shaped by a combination of the service cost of fetching fresh content directly from a back-end database and the aging cost of cached, potentially older, content from a front-end cache. In the scenario of constrained cache size, our analysis have revealed the interesting fact that the optimal caching strategy allocates cache space to items based solely on their popularity, while the content update rate is what determines the content holding time in the cache. Moreover, we have explored the trade-off between the cost minimization and cache savings gain of our design. In particular, not only the cost of our proposed strategy converge asymptotically to the optimal strategy as the number of data items grows, but can also reduce the cache occupancy substantially, as fully characterized by our analysis and illustrated with numerical results.