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], [2]. Thus, more sophisticated resource management strategies are needed to meet the growing demand [2].

One possible approach to tackle 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], [7] and [8]. 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 [9], [10]. 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) [11], [12] 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 [11], [13], TTL caches have been widely employed since the early days of the internet with the Domain Name System (DNS) being an important application [14]. Recently, TTL caching strategies have received renewed attention, mainly because they enable a general analytical approach which is used to model replacement-based caching policies such as Least Recently Used (LRU) [15].

Using the TTL cache refresh framework for dynamic content, [16] 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 focuses on the AoI metric which was first examined in the 1990s in studies on real-time databases [17], [18].

The problem of refreshing cache contents from an AoI perspective was first formulated in [19], 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 [20]. In [21], 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 [22]. Najm et al. [23] analyze the average age and average peak of AoI under the gamma distributed service time. Sun et al. [24] 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. [25] 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 real-world scenarios where a content does not lose its value simply because time has passed since it was cached. 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 [26], [27]. Furthermore, our proposed model can be applied to a wide range of scenarios where items can be considered as categories. For example, consider the category of the most popular video on youtube. New videos are constantly being generated and they may replace the current most popular video. Thus, the content of the most popular video can be thought of as dynamic content. In these scenarios, so long as there is no new update, the current version is considered fresh independent of the time passed since its generation.

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 [28] 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. This work was partially presented in 2021 IEEE International Conference on Computer Communications (INFOCOM). In the current version, we extend the model to include channel failure and investigate the effect of channel reliability on caching decisions. Our contributions, along with the organization of the paper, are as follows.

• In Section II, we present a novel caching model for serving dynamic content to end users from a back-end source and formulate the general problem of determining the cache holding times. • 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 with high-probability guarantee of the cache size constraint 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 counterparts in the unconstrained problem to demonstrate the potential of the proposed caching strategy and reveal the trade-off between the rate of convergence and cache size saving. 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. In Section VI, the trade-off is investigated through numerical simulations. Finally, we conclude the work in Section VII.

II. SYSTEM MODEL

We consider the generic hierarchical setting depicted in Fig. 1 whereby the (limited) local cache serves a user population that generate content requests 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 process 1 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 captures 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 interval 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 interval (t ′ n,i , t 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 interval (t n,i , t ′ n,i ] 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. Channel Failure: Due to the unreliability of the wireless transmission, fetching attempts from database are not always successful. Therefore upon each fetching failure, re-fetching will be attempted after a deterministic time duration of q time units. We assume a transmission attempt over the wireless medium is successful with probability r > 0 and is independent of other transmission attempts. Upon each cache miss, a fetching attempt is carried out to supply the requested item from the database. If such fetching attempt fails, the database will wait for a deterministic time q before performing another fetching attempt. For every time unit q that a request will be waiting to be served, a waiting cost c m is incurred. Note that, while a request of item n is waiting to be served, more requests for the same item n may arrive. Such requests will add to the waiting cost, since more requests are waiting to be served. One single successful fetch of the most fresh version of item n will be enough to serve all the waiting requests of item n. Problem Statement: Our broad objective in this work is to develop efficient caching and eviction strategies for the above setting that optimally balance the trade-off 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 n 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 [29]. 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. 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 (miss cost incurred) and served to the user; (ii) at the time of successful fetching of 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 τ .

Finally, since the following quantities appear consistently in the paper, for the sake of simplicity of notation, we define new parameters here.

A

Cmiss

(3)

We refer the curious readers to the proof of Lemma 1 on how these parameters were formed. The intuition behind these parameters is that A n (r) is a measure of the effective arrival request rate for item n to the database which is an increasing function of the channel reliability r. Average cost of cache miss per each miss event of item n is reflected in Cmiss n (r) that decreases as channel becomes more reliable. Their product, M (p n , r), is a measure of the average miss cost rate of item n which for a given p n is a decreasing function of the channel reliability r and for a given r is an increasing function of the item popularity p n . For a fully reliable channel with r = 1,

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. Please refer to Appendix A. 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 (7). Theorem 1: Policy τ * ∈ T that solves ( 7) 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 ( 5) 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 E[τ 2 n ] should be minimum. Since the variance var 2 which is a constant random variable. In calculating (5) we assumed that steady state distribution exists for the given random variable τ n . Now we verify it for the constant random variable τ n . Recall that X n (t) ∈ {0, 1} is the indicator that item n is in the local cache at time t.

Lemma 2: For a constant random variable τ n , the Bernoulli process (X n (t), t ≥ 0) has a limiting hit probability given by:

Proof. Bernoulli process (X n (t), t ≥ 0) is a semi-Markov process and is also irreducible. According to Fig.

exists and is independent of the initial state. Furthermore, the limiting hit probability h n (τ ) is given by: (2). This completes the proof of Lemma 2.

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 (8). Substituting τ * in (5) gives the optimal cost of (9).

To prove the optimal average cache occupancy (10), substituting the optimal solution (8) in the definition of average cache occupancy given in Lemma 1 and noting that τ * n = ∞, ∀n ∈ S, we obtain n∈S

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, (8) explicitly characterizes the optimal holding time of each dynamic item n in terms of its popularity p n and its refresh rate λ n and channel reliability r 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) It also shows that holding times decrease as the wireless channel becomes more reliable or item becomes less popular (since M (p n , r) is a decreasing function of r for a given p n and an increasing function of p n for a given r); (iv) 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 (v) 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 to 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 (7):

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 ( 12) is still complicated by the need to design with guarantees in the tail distribution of its cache use. To tackle this challenge, 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 (6). 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 (13) 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 (12). Accordingly, we first provide the solution of (13) in the next theorem. Theorem 2: Policy τ * = (τ * n ) n ∈ T that solves ( 13) 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 (21).

Therefore the assumptions to calculate the average cost and average cache occupancy given in ( 5) and ( 6) hold and the optimization problem (13) 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 ( 13) can be expressed as:

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

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

Therefore, the non-trivial KKT solution to the problem (16) 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 ( 14) reveals the interesting insights that, for dynamic content n ∈ D: whether to cache an item depends on the channel reliability and whether the item is sufficiently popular (in particular, whether p n ≶ α * βc f for r = 1); and how long a cached item will remain in the cache before eviction depends on its refresh rate λ n as characterized in (14). It can also be seen that, for the same system parameters (λ, β, p), as the average cache limit B decreases, then the optimal α * that solves ( 14) and (15) will increase. Then, for both static and dynamic content, the popularity threshold α * /(βc f ) of perfect wireless channel 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 (13), we are ready to connect it to the probabilistic problem (12) with the following proposition.

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

such that the solution τ * (δ) of ( 13) for B = B(δ) satisfies

Proof. (Proposition 1) Notice 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:

In this equation, setting δ to the form δ

Proposition 1 provides an explicit means of using the tractable problem (13) to find efficient feasible solutions to the problem (12). 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 (12) 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 (14). 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 under the fully reliable channel to show its desirable characteristics.

V. COST AND CACHE SPACE PERFORMANCE ANALYSIS

To establish the performance merits or the proposed approximate solution (τ * , α * ) given in ( 14) and ( 15), we contrast the operational cost and average cache occupancy of the approximate problem (13) with its counterpart of the unconstrained problem (7) 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 (7), respectively, by C * (N ) and B * (N ), whereas the cost and average cache occupancy of the proposed approximate problem (13) are denoted by C α(N ) and B α(N ), where the superscript α indicates the dependence of these values to the α parameter that is optimized in ( 14) and ( 15) for a given cache bound. Here, α ≥ 0 is a flexible parameter that allows us to explore the trade-off between the cost and the cache occupancy. Note that C * (N ) = C * (λ, β, p) in ( 9) and B * (N ) = B(τ * ) in (10). In addition, we consider a full reliable channel, i.e., r = 1, to give insights on the nature of the trade-off. Under a fully reliable channel,

βp n c f . Therefore , according to Lemma 1, the average cost and cache occupancy for a fully reliable channel are given by:

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

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 (13), P α, as

to contain all the items that should be held in the cache after being fetched from the back-end database since ( 14) 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 (7). 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 (12) 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 such that P α is defined in (17).

then: lim

(ii) (Cost-cache Size Trade off) For a given database size

), 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. Please refer to Appendix C. 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. We will investigate this trade-off thoroughly in the following section.

VI. NUMERICAL RESULTS

The analytical results obtained in this paper are validated through numerical simulations in this section. In the following, we investigate the effects of item popularity and refresh rates alongside the channel uncertainty on the cost and cache gains of the proposed constrained caching strategy with that of the unconstrained cache. We set the number of data items to N = 1000, unless otherwise stated. We let the data item's popularity be p n = c/n z with z = 1 which is Zipf distributed with parameter z = 1. The refresh rates are captured according to λ n = λ, ∀n ∈ N with λ = 1. Moreover, the normalized costs of fetching, waiting and aging are considered to be c f = 1, c m = 0.5 and c a = 0.1, respectively and β = 5 is the arrival request rate. We also assume that cache space for the constrained caching strategy and channel reliability are B = 50 and r = 0.9, unless otherwise stated.

To emphasize the cache-cost trade-off, we adopt the percentage cost increase and cache saving of our proposed caching strategy for the constrained cache to the optimal solution derived for the unconstrained cache as our performance metric. Such metrics are defined as:

Note that our proposed caching strategy for the constrained cache aims to achieve a close to optimal cost with Fig. 3: Cost increase and cache saving trade-off Fig. 4: Cost increase and cache saving trade-off a limited cache space. As such, the defined cost increase metric is always positive and the defined cache change metric is always negative. A negative cache change shows the percentage of cache space saved by the proposed algorithm.

Fig. 3 shows the percentage cost increase and cache saving as a function of the wireless channel uncertainty. According to the figure, as the wireless channel becomes more reliable, the cost of the proposed constrained caching strategy converges to the optimal cost while the cache space saving decreases. Also, the figure shows that for highly unreliable wireless channels, the proposed constrained caching strategy can greatly save in the cache spaces (more than 80% cache saving) without sacrificing that much on the cost side (around 20% cost increase). In other words, the proposed constrained caching strategy is very effective in saving cache spaces while also maintaining a close to optimal cost of the unconstrained case.

Fig. 4 shows the percentage cost increase and cache saving as functions of the Zipf parameter for the popularity distribution. According to the figure, as items become more predictable, i.e., z increases, the cost of the proposed constrained caching strategy converges to the optimal cost while potentially saving in the cache spaces. When items are highly predictable (z > 2 here), the optimal caching strategy without cache constraint will use less than B = 50 cache space that is set for the constrained caching strategy. Therefore both strategies are the same. On the other hand, as items become less predictable, the proposed caching strategy results in great cache saving without considerable loss on the Fig. 5: Cost increase and cache saving trade-off Fig. 6: Cost increase and cache saving trade-off cost side. In particular, if an item's popularity is according to a Zipf distribution with parameter close to z = 1.5, there is great cache saving without a noticeable cost increase.

Fig. 5 shows the percentage cost increase and cache saving as a function of the item's refresh rate. According to the figure, as items become highly dynamic, for example λ > 7 for our choice of parameters, both the unconstrained caching strategy and the optimal caching strategy are the same. In other words, the optimal caching strategy is using less than B = 50 cache space available for the constrained caching strategy. On the other hand, for less dynamic items, the proposed caching strategy results in great cache saving while achieving a substantially close-to-optimal cost. This shows that as long as items are not highly dynamic, the proposed caching strategy is very effective at saving cache spaces without sacrificing in the cost.

Fig. 6 shows the percentage cost increase and cache saving as functions of the refresh rate's distribution. In particular, we have assumed refresh rates are weighted according to λ n = λ 0 /n q , ∀n ∈ N with λ 0 = 1. We consider the Zipf distribution with parameter z = 1 for item's popularity. According to the figure, when q is largely negative (i.e., q < -0.5 in our case), the proposed constrained caching policy with a limited cache capacity B = 50 achieves almost the same cost of the unconstrained case with almost the same cache occupancy. This is due to the fact that when q < 0, items that are popular will have lower refresh rates. This simplifies the caching decision to cache the most popular item. Moreover, since items with lower popularities have Fig. 7: Rate of convergence and cache saving trade-off higher refresh rates, by not caching such unpopular items, cost is only slightly increased with huge gains on the cache occupancy. On the other hand, if q > 0, popular items will also have higher refresh rates. Therefore, in caching popular items we should also consider the trade-off between their popularity and refresh rates. According to the figure, as q increase, the optimal unconstraned caching policy will occupy more cache space, since it cannot afford to not cache the popular items or items with lower refresh rates. Therefore, as q increase, the constrained caching policy with limited cache capacity will lose more on the cost side and the unconstrained caching will occupy more caches.

To make the trade-off even more clear, we consider the full reliable wireless channel. As stated in the Theorem 3, we assume 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. 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 the cache saving increases with N , 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 reveals for the proposed asymptotic strategy.

VII. CONCLUSION

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 has 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. APPENDIX A. Proof of Lemma 1:

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 and Cmiss n (r) is the average cost of successful fetch per each cache miss of item n. Based on Renewal Reward Theorem, we have:

where S 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 E

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 time until the next request of item n after its last eviction and Q n is the waiting time after each cache miss of item n before it is successfully fetched from the database. Since requests for item n arrive at the cache according to a Poisson process with rate βp n , thus the interarrival times between the requests of item n are exponentially distributed. Due to the memorylessness property of the expenential distribution, R n which is the time until next request given that a certain amount of time has already passed from the last request, will still have exponential distribution with the same rate as the interarrival times. Therefore, we have E[R n ] = 1 βpn . Moreover, letting F to be the number of failures before a successful fetch, since each fetch attempt is successful with probability r, F will have Geometric Distribution with its first and second moments given by:

Since after each failure we wait for q unit time and attempt another fetch, the average waiting time of Q n is given by:

Then, substituting in (20), and defining A n (r) = βpn 1+βpn( 1 r -1)q as the effective arrival request of item n, the hit probability can be given as:

Next, we calculate Cmiss n (r) which is the average cost of successful fetch per each cache miss of item n.

Cmiss

Note that since requests for item n are generated according to a Poisson Process with rate βp n , therefore the number of requests for item n at any interval of length q have a Poisson with rate βp n q. This results in an average number of βp n q requests for item n at any waiting interval of length q. Substituting ( 22) and ( 21) in (19) gives the average cost as in (5).

Using the hit probability given in (21) and noting that E[ Xn (τ )] = h n (τ ), the average cache occupancy which is E

B. Proof of Lemma 3:

To check that Slater condition holds for any 0 < B < N , assume τ n = A N (r) ) ∈ F B which is a feasible point and all the inequalities are inactive.

To check the non-degeneracy assumption, we need to show that every where that a constraint is active, it's gradient is nonzero. Since constraints τ n ≥ 0, ∀n ∈ N have always nonzero gradient, so we only need to check this for g(τ ) =

N n=1

An(r)τn An(r)τn+1 -B. We have:

which is always nonzero for any feasible τ ∈ F B . To check the third condition, consider τ ′ = (0, ..., 0) ∈ F B and choose t n = c n such that cτ ∈ F B for a given τ . Then for this choice of τ ′ and t n we can show that condition 3 holds for all τ ∈ F B . To check the last condition, notice that L C (τ ) = τ ′ ∈ R N : C (τ ′ ) < C(τ ) is sub level set of the convex function C(τ ) and therefore is also itself a convex set.

C. Proof of Theorem 3:

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 (17), 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 ( 8) and ( 14) 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 ( 12) takes the form: 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 ( 8) and ( 14) respectively. Therefore, we have Cn (τ α n ) = C * n = 0, ∀n ∈ S ∩ P α. For unpopular static items n ∈ S α, τ * n = ∞ according to (8) and according to (18) we have τ α n = 0. This gives C * n = 0 and Cn (τ α n ) = βp n c f based on the average cost function given in (5). Therefore,

Thus, the total average system cost is upper-bounded as: In order to make sure that the upper bound vanishes as N increases, we need 4 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: Recall the average cache occupancy defined in (6) and note that according to (18) 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:

Now, using the fact that: