With the wide availability of content delivery networks, many applications utilize edge cache at end-users to deliver dynamic contents, reducing the network latency and system congestion during the peak-traffic time. By caching a large number of dynamic contents in the edge caches, the average response time can be reduced, benefiting from higher cache hit rates. However higher hit rates come at the expense of a less fresh content, resulting in higher overall system cost.
Numerous works study the content delivery in caching systems and effective strategies have been proposed. In [1], [2] and [3], authors study the benefits of caching with the focus being mainly on exploiting the history or statistics of the user demand. These works are based on the promise that the content stored in the cache will ultimately be used. An important factor that may greatly affect the caching decision is the content generation dynamics. However, these studies fail to take into consideration the possibility of content refreshment which renders the current version of the cached content less relevant or possibly obsolete. These types of dynamic contents include news and social network updates where the users prefer to have the most fresh version of the content while also making sure that the total cost of the network remains low.
As the data gets updated in data sources, currently cached version becomes out of date or stale since users are interested in the latest version of data [4]. Most caching policies, however, do not consider the content generation dynamics and focus alternatively on the content popularity. It turns out that the content generation rate plays a crucial role in deciding which data to be cached and with what rate should the cached data be updated to account for the dynamically varying content at the data source. In [5], Candan, et al. propose a framework which enables dynamic content caching for database-driven e-commerce sites by intelligently invalidating dynamically generated web pages in the caches. In [6], authors mention that great benefits can be reached by incorporating the freshness in caching but do not investigate the case due to complexity of it. In [7], authors propose a dynamic cache management policy based on the history of requests and age of the content to update the existing content of the cache. They show that the optimal policy for minimizing the number of missed requests is to keep the packets that have the highest instantaneous request value in the cache. In [8], authors study a least recently used (LRU) policy for cache management in a web browser but they suggest that finding a good caching policy that is conscious of document size and delay may be difficult. In [9], Chen et al. propose LA2U and LAUD policies to implement the update rate in caching. LA2U computes the access-to-update ratio for the cached data items, and evicts the one with the smallest ratio. Notably, LA2U is equivalent to least frequently used (LFU), in the absence of content updates. LAUD works in the same way as LA2U except that LAUD uses popularity-to-update differences rather than access-toupdate ratios to decide which items to cache. In [10], Akon et al., present OUR as a cache replacement scheme which uses both update rates and content popularities to achieve superior-guaranteed performance. They define a performance factor (PF) for each data item. If the newly requested item has a higher PF than that of any cached item, the item with the lowest PF is evicted, and the new item is stored in the cache. Otherwise, the requested item is not cached. However, having a closed form metric that also consider the freshness and can be used to sort the items and achieve a close to optimal solution is not fully investigated.
In this paper, we focus on the design of new caching strategies in the presence of dynamically changing data content and provide a design framework and performance analysis of relevant efficient caching strategies. With dynamically changing data content, the older content versions lose their value at different rates. A freshness-driven caching paradigm must account for these dynamics so as to optimally balance the costs of caching a content and the costs of serving the content non-fresh.
In particular, we propose a freshness-driven caching algorithm for dynamic content, which accounts for the update rate of data content both for the single-user and multi-user cases and provide an analysis of the average operational cost for both cases. We aim to reveal the gains of freshnessdriven caching compared to other basic caching strategies. 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 over wireless broadcast channels. • In Section III, for a database of N data items with an arbitrary popularity distribution that serves a single user with a limited cache space, we propose a suboptimal caching algorithm, Algorithm 1, that gives the cache checking and update rate together with the set of items to be cached in order to minimize the average system cost. We prove that our proposed algorithm optimally minimizes the average cost for any given cache check and update rate, and always outperforms the traditional cache the most popular items strategy, even with optimized cach check and update rates. • In Section IV, by distributing the cache capacity among multiple local users, we develop an optimal caching algorithm, Algorithm 2, that reveals the potential benefits of the multicasting property in wireless networks for optimal caching. We show that our proposed algorithm always minimizes the aggregate average cost of the system. Finally, we conclude the work in Section V.
Consider the network setup shown in Fig. 1, with a database hosting a set N of N data items and serving M users. Each data item n ∈ N is dynamically refreshed with a content refresh being sufficient for the user to consume without the need for older content from the same data item. Content refreshes arrive to data item n according to a Poisson process with rate λ n ≥ 0. We consider the vector λ = (λ n ) N n=1 as the collection of the data items refresh rates. Each user m generates requests according to a Poisson process with rate β ≥ 0. A generated request from any user targets data item n with probability p n . That is, the vector p = (p n ) N n=1 captures the popularity profile of the data items. Users are equipped with a limited-storage cache that can hold K different items.
When a user generates a request to a data item that is found in the cache of that user, the request is fulfilled immediately from that user's cache under a "freshness cost". The freshness cost is incurred due to the fact that the cached content may not be the most fresh version. We associate a freshness cost with such events which increases linearly with the age of the cached content. In particular, we define the age of a cached content from item n as the number of refreshes that item n has received in the database and not reflected on the content in the cache. If the user, thus, consumes a content from the cache with age k, the user will incur a freshness cost of k • C 0 , where C 0 ≥ 0 is a constant showing the freshness cost per stale version. If the requested data is not in the cache, the user has to fetch the data from the database and incur a constant fetching cost of C f ≥ 0.
In this paper, we will study the caching strategies to minimize the overall system cost in presence of dynamically refreshing content which adversely impacts the caching utility. We will investigate which items to cache and how many items to cache for the single-user and multi-user scenarios.
Single-user scenario concerns a user with a limited cache space that keeps local copies of the dynamic content for local-access. If the requested item is in the local cache, it is directly served with the possible age-cost described above. In order to prevent the age-cost from dominating the overall cost, the local cache needs to check for updates of stored content at appropriate rates. Therefore, in this scenario the questions of interest are which data items are worth storing and at what rate their updates must be checked to minimize the overall cost. We will address this question in Section III.
Multi-user scenario, in contrast, concerns the distributed caching setting whereby each user receives its independent requests for the dynamic content for local consumption. The key new component in this case is the broadcast nature of the wireless medium whereby transmissions of content made to one user can be received and used to opportunistically update content in other users' cache at no additional transmission cost. This multicasting property non-trivially couples the decisions across the distributed cache space for optimal caching solution. In Section IV, we undertake this interesting setting to provide optimal distributed allocation strategy for minimum overall cost.
In both the single and multi-user cases, we prove the optimality characteristics of our proposed caching and update strategies, and compare their gains over natural benchmarks that do not account for the dynamic nature of the content. In Section IV, we also compare the optimal solutions for the single and multi-user scenarios for equal request rates and equal total cache spaces in order to reveal the benefits of distributed caching over common caching that emerge due to the dynamic nature of the content.
In this scenario, the user requests are served individually and no other user can benefit from such a service. Therefore, we drop the dependence on the user index m, i.e., the user generates requests with a rate of β. The cache size at the user is K data items. To avoid excessive freshness cost, the user employs a cache check and update mechanism through which the user generates random cache check and update requests to check the items in the cache and update them from the database if they have been already refreshed in the database. We assume that the cache check and update requests are generated according to a Poisson process with rate µ ≥ 0. Each checking request costs an amount C ch ≥ 0 which accounts for the communication overhead with the database. If the content in the cache is found to be not the most updated version, then the user will fetch the most fresh version from the database at an additional caching cost of C ca ≥ 0 which accounts for the resource consumption to deliver the fresh content to the user's cache. As discussed earlier, if an older content with age k is served from cache, the user will incur a freshness cost of k•C 0 , where C 0 ≥ 0 is a constant. If the requested data is not in the cache, the user has to urgently fetch the data from the back-end database at a higher fetching cost of C f ≥ 0. The checking, caching and urgent fetching costs are constants and satisfy the relation
Let I K ⊆ N be the set of items that are stored in the user cache and let µ be the checking rate of cache content for the freshness. Note that K is the caching capacity of the user and due to the high refresh rate, the user may not necessarily fill the cache. As such |I K | ≤ K.
Lemma 1: Let C S I K (µ) be the average system cost in the Single-user scenario as the user caches the set of items I K and checks the cache freshness with the Poisson process of rate of µ. Then:
Proof. Let {Π i µ (t), t ≥ 0}, ∀i ∈ I K be the Markov process describing the freshness age of cached item i at time t under a given checking rate µ. The evolution of this process is shown in Fig. 2. As it can be seen in Fig. 2, every arriving content update to the item i in the database that occurs with rate λ i increases the age of that item in the cache by one. Checking and updating the cache content will occur with rate µ and upon occurrence, it will move the system back to state zero, the most fresh version. We are interested in the limit of
. .} be the probability of item i ∈ I K having the age of k under the checking rate µ, then:
Hence, the average age of any item i ∈ I K in the cache is given by:
The average system cost in the Single-user scenario as the user caches the set of items I K and checks the cache freshness with rate µ comprises four main terms as follows:
The first term in Equation ( 4) shows the average checking cost for a cache capacity of K that caches the set of items I K and updates the cache content with the rate of µ and each checking process has a cost of C ch . The second term in Equation (4) shows the average fetching cost for a cache set of I K and the request arrival rate of β as a function of miss rate β(1 -i∈I K ). For any arrival request, 1 -i∈I K p i is the probability that the requested content is not in the cache, so the content should be fetched from the database which incurs the cost of C f . The third term in Equation (4) shows the average caching cost for a cache set of I K and checking rate of µ. For a given µ, π i 0 (µ), ∀i ∈ I K is the probability that item i in the cache is the most updated version, i.e., has age 0. So 1 -π i 0 (µ) is the probability that item i existing in the cache is not fresh. For every checking process that happens with rate µ, if the content in the cache is not fresh, we cache the most updated version from the database and put it in the user cache which incurs the cost of C ca .
The fourth term in Equation ( 4) shows the average freshness cost for a cache set of I K and checking rate of µ. For each item i ∈ I K existing in the cache, the arrival request will be served from the cache. The arrival request of item i is βp i and since the item with age k incurs the cost of k.C 0 , so the average cost of freshness will be
is the average age of cached item i given in (3).
Replacing the results of Equations ( 2) and (3) in the cost function given in Equation ( 4) completes the proof.
The cost minimization problem for the single-user scenario would thus be: min
A traditional (suboptimal) approach to tackle the caching problem ( 5) is to cache the first K most popular items.
Definition 1 (Cache the Most Popular): Define the I p K ⊆ N to be the set of K most popular items. That is,
Then the cache the most popular strategy will assign the cached set of items as I K = I p K and optimizes the cache check and update rate as µ = µ p , where
Since the cost in ( 1) is convex over µ, such µ p exists.
The cache most popular strategy does not consider the content refresh rate, and the associated freshness costs. Hence it is a suboptimal strategy. We then note that, the optimization ( 5) is computationally formidable to solve as it necessitates a discrete search process which involves finding the jointly optimal subset of items to be cached from a large database of N items and the best cache check and update rate. We, therefore, investigate the design of suboptimal, yet simpler strategies that account for the dynamic content refreshing and lead to more performance merits than the traditional cache most popular strategy.
We propose an algorithm, Algorithm 1, with a selected set of cached items ÎK and a cached check and update rate μ, based on the refreshing rate of λ and other system parameters to minimize the expected system cost.
In particular, and as used in Algorithm 1, for item i, we define the metric δ S (λ i , p i , µ) = δ S i (µ) as follows:
to capture the marginal cost of adding the item i to the cache for a given µ.
Our proposed algorithm sorts the items based on δ S i (µ) and starts filling the cache with items that have the least δ S i (µ) and keeps adding until either all the items with negative δ S i (µ) are placed in the cache or the cache becomes Algorithm 1 Single-user caching strategy Update δ S i (μ) from step 2.
8:
Update ÎK from step 3. 9: end while 10: return μ, ÎK . full, i.e., K items have been already cached. Then for the new set of cached items, the algorithm computes the corresponding optimal cache check and update rate μ and modifies the values of δ S i (μ) based on new μ. Notice that all data items with positive δ S i (µ) can only increase the average cost if cached. The metric δ S i (µ) reveals the effect of refresh rate alongside the popularity on gains that can be achieved by caching an item. For example, if an item has a high probability of being requested and a high refresh rate, the high refresh rate will increase the values of δ S i (µ) and therefore renders that item less likely to be cached even if there is available cache storage.
In the following, we provide a proof of optimality for the proposed algorithm under a given cache check and update rate µ and show that it always outperforms the cache most popular content strategy.
Proposition 1: For a given cache check and update rate µ, Algorithm 1 minimizes the average cost in (1). Proof. For a given µ and the set of items I K in the cache, if we add any item i to the cache such that i / ∈ I K , then we can write the resulting cost as:
By induction, if we set I K = {∅} and add the item i to the cache, the cost will decrease by δ S i (µ). If we keep adding items i with δ S i (µ) < 0, the average cost will continue to decrease. Therefore:
Since the proposed algorithm at each step chooses the items with minimum negative δ S i (µ) for a given µ, it results in the optimal solution. Proof. We prove this by showing that in each iteration of the proposed algorithm, the resulting average cost decreases. Proposition 1, suggests that for a given µ, our algorithm gives the optimal solution. At any given iteration t, we have:
Since at each step we choose μ(t + 1) to minimize the average cost for a given ÎK (t+1), in other words, µ(t+1) = argmin µ C I K (t+1) (µ), we have:
Combining the two equations gives:
which shows at each iteration, the proposed algorithm reduces the cost. Since we start the algorithm with μ(1) = µ p and ÎK (1) = I p K , so the proposed algorithm always outperforms cache the most popular strategy.
We next investigate the efficiency of our algorithm compared to cache the most popular strategy.
We let the total number of data items be N = 10 6 , data items' popularity be p n = c/n α with α = 1.2 and content refresh rates be λ n = λ/n z , for some z ≥ 0. We consider the normalized costs of fetching, checking, caching and freshness to be C f = 1, C ca = 0.1, C ch = 0.05, C 0 = 0.025.
Setting the cache size K to be 500, we compare the average cost achieved by the proposed algorithm, Algorithm 1, and the average cost of the most popular items strategy under the same system variables declared above. We adopt the percentage cost reduction of our proposed algorithm to the cache the most popular strategy's cost as our performance metric. Such a metric is defined as:
The percentage cost reduction is depicted in Fig. 3. The figure shows substantial gains (between 50 -90% reduction in the cost) compared to the predominant popularity-based design, are achievable with our proposed preliminary design. It also reveals that the gains become more substantial as the refresh rate of different items becomes more non-uniform (as the parameter z increases).
Note that adding cache capacity to users is not always an effective way to reduce the average system cost, specially in presence of highly dynamic content.
Consider the scenario shown in Fig. 1, with M users. To gain a clear insight of the potential wireless multicasting gain and how distributed caching can relate to the singleuser scenario with a cache of size K, we assume that each user in the multi-user scenario has the capacity to cache only one of the date items. However, the number of users is set equal to the number of items that the user can cache in the single-user scenario. That is, M = K. In other words, we distribute the K caching capacity over the users with each user can cache one item.
In this section, we investigate what items to be cached and how should the cached items be replicated over the set of users. In the multi-user scenario, due to the broadcast capability of wireless service, it is not necessary to employ a cache check and update mechanism as is the case in the single-user scenario. Instead, users that have a certain item in their cache can update it for free if another user that does not have it, requests its most fresh version from the database.
Let r = (r 1 , ..., r N ) be the vector of the number of times each item has been cached among the K users. In other words, r i is the number of replicas of item i that exist in the users' caches. Also recall that C 0 is the freshness cost per an age unit. As the age of a cached content increases, the freshness cost grows linearly. The average cost of urgently fetching a data item from the database is C f and the the freshness cost of consuming an item from the cache is k.C 0 where k is the age of the cached content.
For K users, each equipped with one cache, let r = (r 1 , ..., r N ) be the vector of replication. Define the feasible set of solutions as:
Lemma 2: Let C M (β, r) be the average expected system cost in the Multi-user scenario with K users and request arrival rate of β under vector of replication r ∈ F K . Then:
Proof. Let {Π i ri (t), t ≥ 0}, ∀i ∈ N be the Markov process describing the freshness age of cached item i at time t under the number of replicas r i . The evolution of this process is shown in Fig. 4. As discussed earlier, in the multi-user scenario, the broadcast capability of wireless service acts as a natural update mechanism. In other words, users update their cached content for free by overhearing that content while being served to other users who do not have it in their cache. For any item i in the cache, since there are K users and r i of them have item i in their cache, the service rate of item i is equal to βp i (K -r i ). As it can be seen in Fig. 4, every service of item i acts as an update mechanism for the users that hold item i in their cache and upon occurrence, the service of item i from the database will move the system back to state zero, the most fresh version. Every arriving content update to the item i in the database that occurs with rate λ i increases the age of that item in the cache by one.
t→∞ Πi ri and using the steady state distribution of Π i ri (t) define π i k (r i ) = P ( Πi ri k), k ∈ {0, 1, 2, . . .} be the probability of item i having the age of k under the number of replicas r i , then the average age of item i is given by:
The average system cost in the Multi-user scenario as K users cache according to the vector of replication r = (r 1 , ..., r N ) ∈ F K , comprises two main terms and is given by:
The first term in Equation ( 8), shows the average fetching cost for any r ∈ F K and request arrival rate β as a function of miss rate β K -N i=1 r i p i . For any of the K users, if a requested item is in the user's cache, it will be immediately served from the cache with the freshness cost, otherwise it will be fetched from the database and the urgent fetching cost C f is incurred. Since there are r i users that have item i in their cache, the miss rate for item i is βr i (1 -p i ). Summing over all the N items and remembering that r ∈ F K , gives the total miss rate as β K -N i=1 r i p i . The second term in Equation ( 8), shows the average freshness cost for any r ∈ F K and request arrival rate of β. For each item i in the cache, the arrival request rate is βp i and since the item with age k incurs the cost of Algorithm 2 Multi-user caching strategy
r * j = r * j + 1 k • C 0 , so the average cost of freshness for item i will be
. Since r i is the number of users having item i in their cache, the total freshness cost incurred by item i is given by βp
Summing over all the items gives the total freshness cost of the system. Substituting Equation (7) in Equation ( 8) gives the average cost of system.
Our objective is thus to choose the content to be cached at the users in order to minimize the average cost of system, that is:
The traditional cache the most popular strategy in this context reduces to caching the K most popular itemsfoot_0 to the users' caches, one item per user cache.
Definition 2 (Cache the Most Popular): Define the I p K ⊆ N to be the set of K most popular items. Then cache the most popular strategy for the K users, each with a unit caching capacity, is given by:
K , with r p := (r p 1 , ..., r p N ). Such strategy does not consider the freshness of items, yet we address the question of whether the system can achieve better performance through lower cost.
We propose Algorithm 2 based on the data items refresh rate λ to solve (9).
In particular, as it can be seen in Algorithm 2, for item i, we define the metric δ M (λ i , p i , l) = δ M i (l) as follows:
The metric δ M i (l) captures the marginal cost of adding item i to the cache given that l of the users have already cached item i. Our proposed algorithm, at each step, sorts the items based on δ M i (l), caches the item with the minimum δ M i (l) and iterates until either all the items with negative δ i (l) are cached or there no more users are available to cache more items (i.e., no available cache storage). Complexity of proposed algorithm is similar to the sort algorithm.
Notice that items with positive δ M i (l) can only increase the average cost if cached. Similar to single user-scenario, δ M i (l) reveals the effect of refresh rate alongside the popularity on gains that can be achieved by caching an item.
In the following, we provide a proof of optimality for the proposed caching algorithm by showing that r * satisfies all the necessary conditions for optimality.
Theorem 1: Algorithm 2 solves the problem (9) optimally. Proof. We start the proof by first discussing the necessary conditions for the optimal solution.
Lemma 3 (Necessary conditions for optimality): Any optimal solution r = (r 1 , . . . , rN ) to the problem defined in Equation ( 9) must satisfy all the following conditions.
Proof. We use contradictions to prove that all the three conditions are necessary for the optimal solution.
To prove that Equation ( 11) is necessary for optimality, we use contradiction. Assume that Equation (11) does not hold, so there exists j ∈ N with rj > 0 such that δ M j (r j -1) > 0. Then construct r = r -e j , where r ∈ F K and we have that C M (r) = C M (r) -δ M j (r j -1). Since δ M j (r j -1) > 0, so C M (r) < C M (r) which contradicts the fact that r was the optimal solution.
To prove that Equation ( 12) is necessary for optimality, assume that there exist i, j ∈ N such that δ M i (r i -1) > δ M j (r j ). Then construct r = r -e i + e j , where r ∈ F K and we have that C M (r) = C M (r)-δ i (r i -1)+δ j (r j ). So there exists r ∈ F K with C M (r) C M (r) which contradicts the fact that r was the optimal solution.
To prove that Equation ( 12) is necessary for optimality, assume that N i=1 ri < K j ∈ N such that δ M j (r j ) < 0. Construct r = r -e j , where r ∈ F K and we have that C M (r) = C M (r) + δ M j (r j ). Since δ M j (r j ) < 0, so there exists r ∈ F K with C M (r) < C M (r) which contradicts the fact that r was the optimal solution. Now we prove that any solution r ∈ F K to the optimization problem defined in Equation ( 9) that satisfies all the necessary conditions for optimality given in Lemma 3, results in the same average cost.
Lemma 4: Any solution r ∈ F K satisfying the Equations (11), ( 12) and (13) will result in the same average cost. Proof. To prove the lemma, we show that for any r, r ∈ F K and arbitrary a = (a 1 , . . . , a N ) such that r = r + a if both r and r satisfy the conditions of Lemma 3, then either a = 0 or C M (r) = C M (r). Assume a = 0, we consider two cases separately.
Case 1: if δ M i (r i ) > 0 ∀i ∈ N , then if there exists j such that a j > 0, we have that: δ M j (r j -1) = δ M j (r j + a j -1) > δ M j (r j ) So Equation (11) does not hold for r, which is a contradiction. Hence a i ≤ 0 ∀i ∈ N . If a i = 0 ∀i then the problem is solved, but if there exists j such that a j < 0, then we have:
According to Equation (13),
i (r i ) > 0 does not hold for all i ∈ N , then according to Equation (13),
0 for all i, then in order to have a = 0, there exists j ∈ N with a j < 0 such that Equation (14) holds. Now, from Equation (13), N i=1 r i = K should hold for r, but since N i=1 a i < 0, it is not possible. So if there exists j ∈ N with a j < 0, there must exist v ∈ N with a v > 0 such that N i=1 a i = 0 since we should have N i=1 r i = K as shown before. Since r satisfies all the necessary conditions of Lemma 3, Equation (12) holds for r over v and j. δ
, the condition of Equation (12) does not hold for r which is a contradiction and if δ M v (r v ) = δ j (r j -1), construct the r = r + e v -e j . Then C M (r) = C M (r)+δ M v (r v )-δ M j (r j -1) = C M (r). which completes the proof.
The solution reached by Algorithm 2 satisfies all the necessary conditions in Lemma 3 and according to Lemma 4, such a solution is optimal.
It is worth noting that the cache allocation strategy for the multi-user scenario supported with wireless multicasting can lead to some users caching less popular items than those cached at other users. Such a diversity in cached iterms' popularities empowers the need for requests from the database which in turn brings the most recent version of content to users for free, thanks to wireless multicasting.
Knowing that the proposed algorithm, Algorithm 2, gives the optimal solution, we investigate its performance merits compared to other basic caching strategies like cache the most popular strategy.
Using the same parameter values defined in Section III.D with z = 1.2 and changing the number of users K, we set the performance metric to be the percentage cost reduction of our proposed algorithm, Algorithm 2, to cache the most popular strategy's cost. Define:
Fig. 5: Average cost reduction by the proposed algorithm over the cache the most popular for the multi-user scenario.
The percentage cost reduction is depicted in Fig. 5. The figure shows considerable gains compared to the predominant popularity-based design are achievable with our proposed preliminary design. It also reveals that the gains become more substantial as the number of users increases, reveling that proposed algorithm, Algorithm 2, can more effectively incorporate the broadcasting gain to reduce the cost. It also reveals that the gain increases as the refresh rate of different items decreases. Also as the refresh rate of different items decreases, with less users we can achieve higher gains, benefiting more from the multicasting gain. We also compare the average cost of the single-user with the multi-user scenario. Running the Algorithm 1 for the single-user scenario and Algorithm 2 for the multi-user scenario, with C S ÎK (μ) and C M (r * )/K representing the average cost per user for these two scenarios respectively. Setting the performance metric to be the percentage cost reduction per user for multi-user scenario compared to the single-user scenario's cost, we define: Fig. 6 shows the percentage cost reduction for different caching costs of C ca . According to the figure, for small cache size, single cache outperforms distributed caching in the sense of average cost per user, but as the number of users grows, the multi-user scenario, benefiting more through the multicasting property, will outperform the single-user scenario. In other words, through distributed caching aided with multicast cache update, the per-user cost in the multiuser system decreases as the number of users K grows, while the single-user's cost does not benefit from more cache storage, K, because of the associated cache check and update requests. Recall that the multi-user scenario, despite the single-user scenario, does not employ any optimized cache checking and updating mechanism.
In this work, we have proposed caching algorithms for wireless content distribution networks serving dynamically changing data content such as news updates, social network stories, and any other system with time-varying states. We have developed a design framework together with the performance analysis for efficient freshness-driven caching strategies. We have characterized the average operational cost both for the single-user and multi-user scenarios. Our results have revealed that, in the presence of dynamic content, adding more cache space to edge-users may solve the system congestion problem at the expense of a high freshness cost. In the multi-user scenario, as the number of users increases, our proposed algorithm benefits more from the multicasting property as a mechanism to update the cache content and outperforms single-user caching. Our results have also demonstrated that freshness-driven design considerably reduces the average cost and optimizes the cache space more effectively than the predominant existing strategies such as cache the most popular content.
Note that caching the same item at all users (i.e., setting r i = K for some i ∈ N , r j = 0 , ∀j = i) can only result in an infinite cost due to the fact that the item cached will never be requested from the database yielding a freshness cost that grows indefinitely.