With the emergence of new services and application scenarios, such as Youtube, augmented reality, social networking, and online gaming, which produce dynamically changing data over time, serving the most recent version of data to end-users is becoming the main challenge due to the massive device connectivity. To alleviate the latency of data transmission between the servers and end-users, many applications utilize edge-caches close to the end-users to deliver dynamic contents, reducing the network latency and system congestion during the peak traffic time [1], [2]. Usually, several edge-caches are deployed over the edge networks and the data required by end-users can be cached at one or multiple edge-caches. By caching a large number of dynamic contents in the edge-caches, the average response This work funded, in part, by the NSF grants: CNS-NeTS-2007231, CNS-SpecEES-1824337, CNS-NeTS-1717045, CNS-NeTS-2106679; and the ONR Grant N00014-19-1-2621.
time can be reduced, benefiting from higher cache hit rates. However higher hit rates come at the expense of less fresh content, resulting in higher overall system cost.
One possible solution for tackling this problem is to cache popular contents at the edge-caches to reduce the total response time to data requests. Content Distribution Networks (CDNs) utilize a large mesh of edge-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 and aim to simply maximize the cache hit rate [5]. In many realworld 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 [6], [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.
Numerous works study the dynamic content delivery in caching systems and effective strategies have been proposed [8] and [9]. In [10], authors propose 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 and often the objective is to minimize the average AoI. Kam et al. [9] 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 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 [11] which grows with the AoV metric. Moreover, our model utilizes the multicasting property of the wireless medium to opportunistically update the cached contents over the edge-caches. Finally, 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 focus on wireless networks that utilize edge-caches to serve dynamic contents to a group of endusers and edge-caches can update their caches content with no additional cost by overhearing that content being served to other edge-caches. we propose a freshness-driven caching model for dynamic content, which accounts for the update rate of data content and provide an analysis of the average operational cost.
This work is related to our earlier work [6], which also considered optimal distributed caching over the wireless edge. However, the setting in [6] is complementary to this one, with each local cache having its separate demand to serve without a possibility of splitting the load. Here, by allowing such a split, the setting as well as the nature of the problem and its solution are completely different. Not only do they lead to new challenges, such as a Knapsack problem appearing within it, but it also results in new insights on how to serve a common edge user population with distributed edge-caches.
By intelligently choosing the number of edge-caches, we propose a policy that jointly optimizes the distributed edge caching and load-splitting between those edge-caches. The proposed optimal policy reveals counter-intuitive insights on the nature of the distributed edge caching for dynamic content. In particular, for the practical case of Zipf popularity, load and cache capacity are generally split unequally between the edge-caches, and edge-caches with higher load will store less items in their cache, however, they are the more popular ones. We aim to reveal the trade-off between our proposed optimal policy and the more practically implemented policy where the load is split equally between the edge-caches. Our contributions, along with the organization of the paper, are as follows.
• In Section II, we present a tractable caching model that utilizes distributed edge-caches for serving dynamic content over wireless broadcast channels in which edgecaches take advantage of the wireless multicasting to keep their cached content fresh. • In Section III, we provide a full characterization of the optimal caching policy which jointly optimizes the number of edge-caches, load-splitting, and cache placements over the network. The solution is achieved by intelligently manipulating a group of intractable 0-1 Knapsack problems to remove all the inequality constraints that renders such problems NP-hard. The outcome is a policy that achieves the global minimum average cost. Our findings reveals the nature of the unequal load-splitting between the edge-caches and dependence of the content caching on the load allocated to each edge-cache. • In Section IV, we provide the optimal content placement for the special case of the equal load-splitting. We also
Fig. 1: Setting of Fresh Caching for Dynamic Content characterize the cost-cache trade-off between the optimal policy and the equal load-splitting policy. Our findings reveal that as the number of edge-caches increases, the equal load-splitting cost decreases at the expense of increasing the cache occupancy. • In Section V, comparing the average cost and the cache occupancy of the proposed optimal policy to the equal load-splitting policy, we investigate trade-off using numerical simulations for the practical case of Zipf popularity and highlight scenarios in which each of these approaches are more cost or cache effective. Our findings reveal that for less predictable demand, i.e., more uncertainty about the demand, equal load-splitting can potentially have significant cache savings while achieving a close-tooptimal cost. On the other hand, as the certainty about the demand increases, the optimal policy can achieve significant gains on the cost without increasing the cache occupancy. 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 generates requests to content according to a popularity distribution; while the back-end database receives updates to refresh the content with different rates. In the following, 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 unitsized data items (with dynamically changing content) is being served to the user population through a hierarchical caching system as depicted in Fig. 1. In particular, there are K edge-caches that supply local content to the neighboring users. Requests arrive to the local edge-cache k according to a Poisson processfoot_0 with rate β k ≥ 0, which captures the request intensity of the user population served by the edge-cache k. 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. Furthermore, denoting the total request arrival rate by β, we define s k = β k β , ∀k ∈ 1, ..., K to be the fraction of the total request served by the edge-cache k. Accordingly, the vector s = (s k ) K k=1 captures the load-splitting between the edge-caches.
Generation Dynamics: At the database, each data item may receive updates at random times 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 caches may be older versions of the content. To measure the freshness of local content, we define the age Δ k n (t) ∈ {0, 1, . . .} at time t for item n stored at the edge-cache k 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. The incoming request to an item that is stored in the edge-cache k is served from the local cache, but potentially with a positive AoV value Δ k 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 edge-cache k with age Δ k n (t) incurs a freshness/age cost of c a × Δ k 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. Content Multicasting: We stress that broadcast nature of the wireless medium enables transmission of content made to one edge-cache to be received and used to update content in other edge-caches at no additional cost. This multicasting property non-trivially couples the decisions across the distributed cache space for optimal caching solution. Moreover, all replicas of the same content at local caches will have the same age of version thanks to the broadcast nature of wireless communication, i.e., Δ k n (t) = Δ n (t) among the edge-caches that hold item n.
Our broad objective in this work is to develop efficient distributed edge caching strategies for the above setting that optimally balance the tradeoff between the cost of serving the fresh item from database and the cost of providing potentially older content to the users from the local cache.
Let I n ⊆ K, ∀n ∈ N be the set of edge-caches that have stored item n and |K| = K is the total number of edgecaches deployed over the network. Note that due to high refresh rates, edge-caches may not necessarily fill their cache to avoid excessive freshness costs. As such, N n=1 |I n | will be always finite for the dynamic content even if there is unlimited cache storage capacity. The total arrival request rate β for items is split between the edge-caches, such that each edge-cache k receives a fraction s k of the total incoming request. Therefore, s = (s k ) K k=1 is the vector of load-splitting between the edge-caches where
s) be the average caching cost of a system composed of K edge-caches where each item n ∈ N is stored in the set I n ⊆ K of edge-caches and each edge-cache k ∈ K receives the fraction s k of the total request. Then:
Proof. Here we only give the outline of the proof. For the full proof refer to [12]. Let {Π n In (t), t ≥ 0}, ∀n ∈ N be the Markov process describing the freshness age of cached item n at time t under the cached set I n . The evolution of this process is shown in Fig. 2. In , the average age of item n is given by:
The average system cost in the distributed edge caching where each item n ∈ N is stored in the set I n ⊆ K of edge-caches and the load is split between the K edge-caches according to the vector s = (s 1 , ..., s K ), comprises two main terms and is given by:
The first term shows the average fetching cost due to the miss events. The second term shows the average freshness cost due to the hit events incurred by serving potentially aged content from the local cache. Substituting Equation (2) in Equation (3) gives the average cost of the system.
The cost minimization problem for such system would thus be: min
Minimizing the average caching cost requires finding the optimal value for the number of edge-caches, how to split the load between those edge-caches and which items should be stored at each edge-cache.
In the following sections, we use the caching cost defined in Equation (1) and propose an optimal caching strategy that jointly optimizes distributed edge caching and load-splitting.
LOAD-SPLITTING OF DYNAMIC CONTENT In this section we tackle the general problem formulated in (4). The characterization of the optimal caching strategy under this setting will not only yield interesting insights about the impact of generation dynamics, but we will also provide an upper bound on the cache occupancy of the proposed optimal caching strategy.
First, in order to gain an insight into the optimal caching policy, we tackle the problem in a simplified version by assuming that the number of edge-caches K and the vector of load-splitting s = (s 1 , ..., s K ) are given and s is not necessarily uniform, i.e., unequal load-splitting between the edge-caches. Our objective is thus for the given load-splitting vector s to choose the cached sets I n (s) ⊆ K, ∀n ∈ N to be stored at the K edge-caches in order to minimize the average cost of the system.
Proposition 1: The policy {I * n (s)} n ∈ K N that solves (5) is given by:
where I n (s) has the form of 0 -1 knapsack problem given by:
and k = arg min
Proof. To prove this, we define δ D n (I n , {k }) to be the marginal cost of adding item n already stored in the set I n ⊂ K of edge-caches to the new edge-cache k ⊂ I n that does not have item n in its cache. In other words:
Using the average caching cost in Equation (1), we have:
In the case of δ D n (I n , {k }) < 0 for a given cached set I n ⊂ K, adding item n to the edge-cache k will reduce the average caching cost. On the other hand, items with positive δ D n (I n , {k }) can only increase the cost if added to the edge-cache k . Therefore, the sufficient condition for the optimality of set I n (s) of the edge-caches to store item n is given by:
Using the definition of δ D n (I n , {k }), for this to not hold we should have:
for some k ⊂ K\I n . Since s k ≥ 0, ∀k ∈ K, we can rewrite this as:
which gives the condition as:
We define the set I n (s) as in Equation ( 6) such that it maximizes k∈In s k while also satisfying the above condition. For I n (s) to be optimal, the sufficient condition for optimality given in Equation ( 7) should hold. In other words: 8) holds for k , then it will hold for ∀k ⊂ K\I n and the set I * n (s) = I n (s) satisfies the sufficient condition for optimality and therefore is the optimal set of edge-caches to store item n.
On the other hand, if Equation (8) does not hold for k , it means that adding item n to the edge-cache k will reduce the average cost. In this case we prove that the set I n (s) ∪ {k } satisfies the sufficient condition for optimality. According to the definition of I n (s) given in Equation ( 6), and assuming that s k > 0, we will have that:
The sufficient condition for optimality would thus be:
for ∀k ⊂ K\{I n ∪{k }}. Because of Equation ( 9), the right hand side is always negative and the sufficient condition for optimality holds. Therefore, the set I * n (s) = I n (s) ∪ {k } is the optimal set of edge-caches to store item n.
The 0-1 knapsack problem in ( 6) is known to be NP-hard and is generally intractable [13] due to the nature of the inequality constraint. In the rest of this section we focus on solving the generally intractable optimization problem (6) by intelligently choosing the number of edge-caches K and vector s = (s k ) K k=1 such that the inequality constraints for all n ∈ N becomes equality constraints. Doing so will remove the complexity that arises by knapsack problems in their general form. Our analysis shows that by intelligently choosing the number of edge-caches and the fraction of the load directed to each edge-cache, we can achieve the global minimum average system cost by our proposed caching strategy.
The following theorem provides the optimal caching strategy for the general problem formulated in (4).
Theorem 1: In a system composed of a data set N of N items with popularity distribution p = (p n ) N n=1 and update rates λ = (λ n ) N n=1 , assume without loss of generality that items are ordered such that y * 1 ≥ y * 2 ≥ ... ≥ y * N where y * n is defined as y * n = max 0, 1 -
≤ N , then the following caching strategy where K * = Q + 1 optimally solves (4).
where s * k and I * n are the fraction of allocated load to the edge-cache k and the set of edge-caches that have stored item n respectively. Under such policy, the optimal caching cost C * and the upper bound on the cache occupancy B * are given by:
Proof. We start the proof by defining the variable y n = k∈In s k ∈ [0, 1], ∀n ∈ N and rewriting the average cost defined in (1) as:
Next, by relaxing the equality constraint y n = k∈In s k and letting y n taken on any arbitrary value in [0, 1], we can write the cost minimization problem as:
This is a convex optimization problem whose solution is given as:
Using this solution, we intelligently assign (s k ) k , {I n } n and K such that:
Doing so will render all the inequalities in the 0-1 knapsack problems given in Equation ( 6) to equality constraints. Therefore, Proposition 1 in this case reduces to:
To guarantee that Equation ( 16) holds ∀n ∈ N , we define Q = max (n : y * n > 0) ≤ N and choose the number of edge-caches as K * = Q + 1 which is the upper bound on the number of different values that y * n can take. Then, by hypothesis, since y and no item will be stored in this edgecache. Replacing the results in the average cost given in Equation ( 1) yields the optimal cost C * (λ, p) as in Equation (12). Finally, the upper bound on cache occupancy of the optimal policy is given by:
(17) and the inequality in the equation is due to the fact that s * k can be zero for some k ∈ K. In that case, the edge-cache with no load will store no item in its cache. This completes the proof.
Remark 1: The extra edge-cache k = K * that does not cache any items, contributes to enhancing content freshness since all the load directed to this edge-cache is served fresh from the database. Due to the multicasting, this acts as a freshness mechanism to keep the content in other edgecaches from getting obsolete.
In the following we investigate some special cases. Proposition 2: In the special case of λn pn = λ p , ∀n ∈ N , the optimal caching strategy is to have two edge-caches, i.e., K * = 2 where the load is split according to s * 1 = max 0, 1 -
In the case of s * 1 > 0, the first edge-cache will store All the N items in its cache, i.e., I * n = {1}, ∀n ∈ N , otherwise if s * 1 = 0, the first edge-cache will store no items, i.e., I * n = {∅}, ∀n ∈ N . The second edge-cache will never store any items. The purpose of the second edge-cache is to utilize multicasting as a freshness mechanism to keep the cached content of the first edge-cache from getting obsolete. Proof. Since λn pn = λ p , ∀n ∈ N , according to Equation (15) all y * n , ∀n ∈ N will be identical.
Now we show how Equation ( 16) holds ∀n ∈ N. In case of y * 1 = 0, no caching will be employed, i.e., I * n = {∅}, ∀n ∈ N . But if y * 1 > 0, then since all y * n have same value, we can guarantee that Equation ( 16) holds for ∀n ∈ N by choosing an edge-cache that receives the fraction s * 1 = y * 1 and then placing all the items in this edge-cache, i.e., I * n = {1}, ∀n ∈ N . The other edge-cache will receive the remaining load and will have no items stored in its cache.
The case of uniform popularity with constant refresh rates is a special case of this. According to Proposition 2, the optimal policy in this case will deploy two edge-caches over the network and split the load and cache space unequally between those edge-caches, even though the popularity and refresh rates are uniform. This reveals the counter-intuitive nature of the optimal policy that benefits by splitting the load and cache capacity unequally between the edge-caches to fully leverage the wireless broadcast as a free cache update mechanism.
Proposition 3: In the case of item popularity distributed according to Zipf with parameter z and constant update rates, i.e., p n = p0 n z and λ n = λ, ∀n ∈ N with p 0 =
< 1, the proposed optimal caching strategy of Theorem 1 reduces to:
where
For the case of Zipf popularity distribution with constant update rate, p 1 ≥ p 2 ≥ ... ≥ p N , then y * n given in (15) can be written as:
which results in Q as:
Replacing y * n in Equation (10) will give the s * k as in (18). This reveals very interesting insights on the nature of the proposed optimal policy. The optimal policy will split the load unequally between the edge-caches and will completely discard the less popular items, i.e., less popular items will not be stored in any of the edge-caches. More interestingly, edge-caches with higher load will generally store less items in their cache, however, they are the more popular ones. This is counter-intuitive, because one may guess that putting more items on the edge-caches with higher load will result in cost reduction over the network. However, the optimal policy which aims to minimize the cost by balancing the freshness and fetching cost, not only avoids to fill up the edge-caches with higher load, but it puts less items into edge-caches as their load increases. Yet, by intelligently deciding to put the most popular items into edge-caches with higher load while keeping the cache small, the optimal policy achieves the optimal cost over the network.
Remark 2: In the special case of Zipf popularity distribution with parameter z = 2, the optimal caching strategy is to have K * = βc f p0 caλ + 1 and then split the load equally between the edge-caches such that each edge-cache receives the fraction
The results of Remark 2 motivates us to investigate the performance of equal load-splitting more deeply. It may not always be possible to split the load unequally between the edge-caches due to complexity of the implementation. In the next section, we propose an optimal policy for the special case of the equal load-splitting and investigate under what conditions such a policy can be beneficial.
In this section, we attack the problem in (4) for the special case when the total number of edge-caches |K| = K is given and the load is split equally between the edge-caches. In this case, s k = 1 K , ∀k ∈ K. This equal load-splitting is simple to implement and yields interesting insights on the cost and cache occupancy trade-offs. We first characterize the optimal caching strategy and then provide insights on the cache occupancy of the proposed strategy.
For K edge-caches, each receiving a fraction s k = 1 K , k ∈ {1, 2, ..., K} of the total load, we define r n = |I n | to be the number of edge-caches that have stored item n and let r = (r 1 , ..., r N ) be the vector of replication.
Define the feasible set of solutions as:
where each item can be stored at most once in each edgecache. Lemma 2: Let C S (K, r) be the average expected system cost in the equal load-splitting scenario with K edge-caches and vector of replication r ∈ F K . Then:
Proof. Since the number of replica r n is defined to be r n = |I n |, and in the load is split equally between the K edgecaches, we have:
Replacing this in the general cost defined in Lemma 1 gives the average cost of the caching system with K edgecaches and under vector of replication r as C S (K, r).
Our objective is thus to choose the content to be stored at the K edge-caches in order to minimize the average cost of the system, that is:
Proposition 4: The policy r * = (r * n ) n ∈ F K that solves (21) is given by:
where x + = max(0, x ), and x is the greatest integer less than or equal to x. Proof. We define δ S n (l) to be the marginal cost of adding item n to the caches given that l of the edge-caches have already cached item n. In other words:
Therefore, we have:
In the case of δ S n (l) < 0 for a given integer l, adding item n to one more edge-cache will decrease the average cost. On the other hand, items with positive δ S n (l) can only increase the average cost if cached. Therefore, we can add item n to the edge-caches, as long as δ S n (l) is negative. Such δ S n (l) reveals the effect of refresh rate alongside the popularity on gains that can be achieved by caching an item. The optimal caching strategy will keep filling the cache for each item n until δ S n (l) turns positive. Therefore, the optimal number of replica for item n would be:
n (l) defined in (23) yields r * n as ( 22). Next we study the trade-off between the average system cost and cache occupancy of the optimal policy for the equal load-splitting compared to the optimal caching policy for the general case when the load is allowed to be split unequally between the edge-caches.
Proposition 5: In a system composed of a data set N of N items with popularity distribution p = (p n ) N n=1 and update rates λ
where y * n , ∀n ∈ N is defined in Equation (15). Let Q = max (n : y * n > 0) ≤ N which is independent of the number of edge-caches K, then we have:
where C S (K, r * ) is the optimal cost in the equal loadsplitting and C * is the minimum achievable cost in Theorem (1). Also we have:
where B S (K, r * ) is the cache occupancy under the optimal policy in the equal load-splitting and B * (λ, p) is the cache occupancy of the proposed optimal policy in Theorem (1). Proof. To prove Equation (24), we use the following Taylor approximation.
where y * n = max(0, 1 -caλn βc f pn ). In the case when y * n = 0, we have caλn βc f pn ≥ 0 and according to Equation ( 22), r * n = 0,
where the terms inside the parentheses are independent of K and this shows a cost reduction with the rate 1 K 2 . Also, since the cache occupancy of equal load-splitting is equal to B S (K, r * ) = N n=1 r * n , where r * n is given in Equation ( 22), and as we showed that in the case of y * n = 0, we have r * n = 0, therefore, using the definition of Q and the lower bound on the cache occupancy of our proposed optimal policy in (13), we can write the lower bound on the cache saving of our proposed policy compared to the equal load-splitting as in Equation ( 25).
This shows that as the number of edge-caches K increases, the cost of the equal load-splitting converges to the optimal cost with rate 1 K 2 but its cache occupancy increases with the rate of up to K 2 .
In this section we compare the performance of the equal load-splitting to the optimal case of general load-splitting between the edge-caches using numerical simulations. We consider the simulation parameters to be β = 5 for the average total request rate and the normalized fetching and aging costs to be c f = 1 and c a = 0.01 respectively. We assume that the database consists of N = 10 6 items.
We compare the average cost achieved by the optimal caching policy and the average cost of the equal loadsplitting policy under the number of edge-caches K = K * and the same system variables declared above. We adopt the percentage cost gain of the optimal caching to the equal loadsplitting strategy's cost as our performance metric. Such a metric is defined as:
The percentage cost gain is depicted in Fig. 3. The figure shows that gains are negligible for small Zipf parameters. In other words, if the item demand is less predictable, i.e., more uncertainty about the demand, the equal load-splitting policy performs almost as good as the optimal caching and the difference vanishes as the refresh rate decreases and items become less dynamic. But as the Zipf parameter increases and the certainty about the demand increases, the cost reduction gain increases. It also reveals that the gain becomes more substantial as the refresh rate of items decreases. The figure reveals a dip in the cost reduction gain at the Zipf parameter z = 2, which agrees with the results of the Remark 2.
Next we compare the cache occupancy of the optimal caching policy and the equal load-splitting policy under the number of edge-caches K = K * and the same system variables declared above. We adopt the percentage cache loss of the optimal caching to the equal load-splitting strategy's Fig. 3: Percentage cost gain of the optimal caching policy Fig. 4: Percentage cache loss of the optimal caching policy cache occupancy as our performance metric. Such a metric is defined as:
Cache Loss (%) = 100 × B * -B S (K * , r * ) B * .
The percentage cache loss is depicted in Fig. 4. The figure shows that for small Zipf parameters, more uncertainty about the demand, equal load-splitting policy occupies significantly less cache space compared to the optimal caching policy and the differences increases as the refresh rate decreases and items become less dynamic. If parameter z approaches zero, content popularity becomes almost uniform and both policies may decide not to cache any items at all. On the other hand, as the Zipf parameter increases and certainty about demand increases, the percentage cache loss of the optimal policy decreases and the optimal policy which achieves the global minimum cost, will occupy less cache space compared to the equal load-splitting policy. The figure reveals that both optimal and equal load-splitting policies achieve almost same cost and same cache sizes at the Zipf parameter z = 2, which agrees with Remark 1.
According to Fig. 3 and4, when item demand is less predictable, i.e., z < 2, equal load-splitting policy achieves almost the same average cost of the optimal caching policy while potentially saving in the cache occupancy. On the other hand, as item demand becomes more predictable, i.e., z > 2, optimal caching policy results in substantial gains in the caching cost while simultaneously reducing the cache occupancy.
Notice that in Figs. 3 and4, we have assumed K = K * both for the optimal and equal load-splitting policies. Ac-cording to Proposition 5, increasing K for the equal loadsplitting policy, such that K > K * , the resulting average cost approaches the optimal cost but this is achieved at the expense of increasing the cache occupancy.
VI. 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. By utilizing the broadcast nature of the wireless medium, our model reveals the benefits of the multicasting property as a mechanism to update the cached content. We have characterized the optimal caching policy both in the general case and also in the special case of the equal load-splitting. Moreover, we have explored the trade-off between the cost minimization and cache savings gain of these two policies. Our results demonstrate that for more predictable demand, splitting the cache and load unequally between the edge-caches results in significant cost gains without increasing the total cache occupancy. On the other hand, for less predictable demand, equal load-splitting achieves a close-to-optimal cost while saving in cache occupancy.
Accordingly, we assume that the system evolves in continuous time.
While this linearity assumption is meaningful as a first-order approximation to ageing cost and facilitates simpler expressions in the analysis, it can also be generalized to convex forms to extend this basic framework.