Guilherme I Ricardo
email: guilherme.ricardo@eurecom.fr

Alina Tuholukova
email: tugolukovaalina@gmail.com

Giovanni Neglia
email: giovanni.neglia@inria.fr

Thrasyvoulos Spyropoulos
email: thrasyvoulos.spyropoulos@eurecom.fr

Caching Policies for Delay Minimization in Small Cell Networks with Coordinated Multi-Point Joint Transmissions

Keywords: Edge caching, CoMP, joint transmission, heterogeneous cellular networks, optimization, distributed algorithms

In 5G and beyond network architectures, operators and content providers base their content distribution strategies on Heterogeneous Networks, where macro and small cells are combined to offer better Quality of Service to wireless users. On top of such networks, edge caching and Coordinated Multi-Point (CoMP) joint transmissions are used to further improve performance. In this paper, we address the average delay minimization problem by first formulating it as a static optimization problem. Even though the problem is NP-hard we are able to solve it via an efficient algorithm that guarantees a 1 2 -approximation ratio. We then proceed to propose two fully distributed and dynamic caching policies for the same problem. The first one asymptotically converges to the static optimal solution under the Independent Reference Model (IRM). The second one provides better results in practice under real (nonstationary) request processes. Our online policies outperform existing dynamic solutions that are PHY-unaware.

I. INTRODUCTION

With the ever-growing popularization of social media and on-demand video streaming, cellular data consumption has experienced an unprecedented increase. According to latest CISCO's forecast [START_REF]Cisco annual internet report[END_REF], by 2023 there will be 13 billion mobile connections, showing an increase of nearly 50% over 2018. Network densification is considered a key strategy to cope with the traffic deluge in future networks [START_REF] Bhushan | Network densification: the dominant theme for wireless evolution into 5g[END_REF]. The standard 3G/4G macro-cell topology will be enriched by a large number of overlapping and often heterogeneous small cells (e.g., femto, pico), in order to improve both coverage and capacity.

On top of such a densified network, two additional techniques have been considered to provide higher Quality of Service (QoS). Assuming that every small base station (BS) has a limited data storage capacity, the first technique is caching relevant content, e.g., the most popular content (with a higher probability of being requested). It allows users to directly access their desired content from the nearby BSs. As a consequence, the access latency can be drastically reduced as well as the backhaul congestion and main servers overload.

This work has been supported by the French government, through the EUR DS4H Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-17-EURE-0004 as well as the "5C-for-5G" JCJC project with the reference number ANR-17-CE25-0001.

The second technique is Coordinated Multi-Point (CoMP) joint transmissions [3]. The idea is that two or more BSs jointly transmit the requested file to the user. By doing so, users experience higher rates and, consequently, smaller delays to obtain the content.

Considering these techniques, in order to provide better experience for mobile users, our goal is to design strategies to minimize their experienced delay to get a request served. This problem can be solved statically, through offline solutions, or dynamically, through online caching policies.

In offline solutions, there is a centralized entity aware of the files popularities (assumed to be constant over time) and the whole network topology. With this information, it is able to decide which files should be cached at each BS, based on a given performance metric, e.g., probability of finding the requested file in the cache, bandwidth usage, original servers traffic load, etc. Normally, in this kind of approach, the content placement is split into two phases: (i) the measurement phase when requests are observed and files popularities are estimated and (ii) the file placement itself, usually performed during a low traffic load period.

However, having all this information available is a very strong assumption and is hardly satisfied in real systems. Moreover, static content placement may fail to capture shortterm popularity changes. Despite its drawbacks, we use the offline approach as a comparison baseline for the online policies.

Online caching policies are distributed algorithms deployed at every BS, which specify the cache update rules, e.g., when and how to update the cache. In our proposed caching policies, the BSs, using implicit information from their local neighborhood, estimate the marginal gain (in terms of local delay savings) for keeping a copy of a cached content. The marginal gain is used to drive the (probabilistic) caching decisions for the local cache, with the end goal of maximizing global performance gain. Since the BSs take decisions on-thefly, based on the request process they are exposed to, online policies turn out to be more reactive to files' popularity shortterm variability. In comparison with offline solutions, each BS needs to know and exchange much less information. For these reasons, online caching policies are more appropriate to be deployed in real systems.

A. Related Work

The term FemtoCaching was coined in [START_REF] Golrezaei | Femtocaching: Wireless video content delivery through distributed caching helpers[END_REF], [START_REF] Shanmugam | Femtocaching: Wireless content delivery through distributed caching helpers[END_REF] to describe the framework in which overlapping small cells have some storage capacity. Assuming that files have known and static popularities and are requested according to the Independent Reference Model (IRM), the problem is to find the content placement maximizing the hit rate. The authors proved that this problem is NP-hard, so it can be efficiently approximated by a greedy heuristic, with worst-case performance guarantees.

In this framework, [6] maximizes the hit ratio by jointly optimizing content placement and user-association. The authors of [START_REF] Wang | Dynamic femtocaching for mobile users[END_REF] go even further and consider a more dynamic scenario in which network topology evolves with time, to capture users' mobility. Looking at the application layer, [START_REF] Sermpezis | Soft cache hits: Improving performance through recommendation and delivery of related content[END_REF] and [START_REF] Costantini | Approximation guarantees for the joint optimization of caching and recommendation[END_REF] jointly optimize content allocation and recommendation. The idea is that the hit rate might increase if users accept the recommendation of an already cached alternative content. All these variants of the FemtoCaching problem were proven to be NP-Hard and efficient heuristics were proposed.

To the best of our knowledge, [START_REF] Ao | Distributed caching and small cell cooperation for fast content delivery[END_REF] was one of the first papers to explore, using the idea of collaborative joint transmissions, the trade-off between hit rate and delay savings. In this context, it might be more advantageous to eliminate copies of less popular files in order to make room for multiple copies of more popular files, creating joint transmissions opportunities and, consequently, reducing the experienced delay. The authors proposed a first approach based on a randomized heuristic with Maximum Ratio Transmission and a second approach based on Zero-Forcing BeamForming. However, both approaches lack of theoretical optimality guarantees. First introduced by [START_REF] Tuholukova | Optimal cache allocation for Femto helpers with joint transmission capabilities[END_REF], and revisited in the present work in Section III, the average delay minimization in FemtoCaching framework under CoMP assumption can be formulated as a combinatorial optimization problem. Although this problem is NP-Hard, submodularity properties are guaranteed under specific assumptions. Then, the greedy algorithm can again be used to find a content allocation that is 1 2 far from the optimal. A common drawback of the aforementioned works is the difficulty to find the adequate timescale for popularity estimation that is long enough to provide accurate measurements and still able to capture short-term variations. Instead, online policies, such as LRU and its variants, are widely deployed because they do not require popularity estimation. Additionally, they enjoy robust analytical performance evaluation tools, like the celebrated Che's approximation [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF]. Another downside of static centralized policies is that, in a dense cache network, having a centralized entity aware of the entire topology may not be feasible due to the network structure complexity. Online policies do not face the same issues because each cache takes individual decisions based on the experienced requests and possibly some limited information exchange with neighboring caches.

In [START_REF] Garetto | A unified approach to the performance analysis of caching systems[END_REF], the authors study a hierarchy of interacting caches by considering what they called replication strategies. [START_REF] Giovanidis | Spatial multi-lru caching for wireless networks with coverage overlaps[END_REF] introduces two caching policies: LRU-ONE and LRU-ALL. In the former, each user is assigned to a reference BS. When a user poses a request, its associated BS will update its cache, independently of which BS provided the file. In the latter, all neighboring BSs update their caches. The updates are based on the Least-Recently-Used (LRU) single-server policy.

In [START_REF] Leonardi | Implicit coordination of caches in small cell networks under unknown popularity profiles[END_REF], the authors propose a model based on Che's and exponential approximations able to evaluate the performances of interacting caching policies in a dense cellular network. Moreover, they present the first distributed online policy with provable convergence properties for the FemtoCaching setup. In the context of online linear optimization, [START_REF] Paschos | Learning to cache with no regrets[END_REF] uses a projected gradient method to decide how to split files and store chunks in the cache network. The technique cannot be applied with CoMP, because in their setting BSs store different chunks of the same file. The authors in [START_REF] Neglia | A Swiss Army Knife for Dynamic Caching in Small Cell Networks[END_REF] provide a generalpurpose online caching policy and demonstrate its application in different study cases. They also prove its convergence to optimal allocations under IRM.

B. Paper Contribution and Organization

This work extends two previous conference papers: It consolidates the discussion on the static optimization problem introduced in [START_REF] Tuholukova | Optimal cache allocation for Femto helpers with joint transmission capabilities[END_REF] and it refines the caching model, case study, and experimental results from [START_REF] Ricardo | Caching policies for delay minimization in small cell networks with joint transmissions[END_REF].

The main contributions of this paper are summarized below:

• We formalize the static delay minimization problem of allocating contents in a caching network with CoMP transmissions. We prove that the problem is NP-Hard. • For this problem, we prove that, under homogeneous transmission conditions, the objective function is submodular, so the greedy algorithm provides a solution with 1 2 -approximation ratio.

• We provide more insight on the static problem's solution by studying a simple scenario that we called fullcoverage. In this case study, we prove conditions for the optimal caching strategy to consist of replicating or diversifying contents throughout the network. • In a distributed setup for the same problem, we propose two online policies, qLRU-∆d and 2LRU-∆d. In these policies, BSs use only local information to update their cache states, taking a probabilistic drift towards improving the problem's objective. qLRU-∆d is able to achieve optimal allocations under IRM when parameter q tends to 0. 2LRU-∆d addresses the problem of non-stationary requests, offering better performance in real scenarios. • Using an extensive set of simulations, we demonstrate qLRU-∆d's convergence properties, and we observe both policies' ability to outperform other state-of-the-art policies in all considered scenarios. The remainder of the paper is organized as follows. In Section II, we introduce the caching model and the transmission protocol. Then, in Section III, we formalize the static optimization problem, and we further discuss the full-coverage scenario in Section IV. We introduce online caching policies in Section V and evaluate their performance in Section VI. We conclude our paper with an overview of our results and possible future work in Section VII.

II. SYSTEM MODEL AND OPERATION

A heterogeneous network consists of "multiple tiers (or layers) of networks of different cell sizes/footprints and/or of multiple radio access technologies" [START_REF] Sun | Heterogeneous cellular networks[END_REF], leading to overlapping cells. This overlap opens the possibility to use CoMP techniques, as a user is in general in the transmission range of multiple base stations (BS). While we do assume that all base stations have the same transmission power (e.g., a dense network of small cells) or equal capacity size, this is just for the sake of simplifying the presentation and providing experiments easier to interpret. Our caching policies do not require such homogeneity and their theoretical guarantees also hold when cells differ in terms of transmission power and/or cache size.

We consider in particular a set

u = 0.
Each BS is equipped with a cache that can store up to C files from a catalog [F ] of files. In order to ease our exposition, we assume that all files have the same size equal to M bits. This assumption is widely considered in the literature (e.g., [START_REF] Golrezaei | Femtocaching: Wireless video content delivery through distributed caching helpers[END_REF], [START_REF] Shanmugam | Femtocaching: Wireless content delivery through distributed caching helpers[END_REF], [START_REF] Tuholukova | Optimal cache allocation for Femto helpers with joint transmission capabilities[END_REF], [START_REF] Neglia | A Swiss Army Knife for Dynamic Caching in Small Cell Networks[END_REF], [START_REF] Neglia | Cache Policies for Linear Utility Maximization[END_REF]) as large files are often split into smaller chunks of roughly equal sizes.

Let V = [B]×[F ],
where element (b, f ) ∈ V represents the placement of file f in BS b's cache. Let V (b) = {b} × [F ] be a subset of V representing the possible file placements in BS b. The set X ⊆ V is a feasible static allocation if it satisfies the caches capacity constraints, i.e.,

|X ∩ V (b) |≤ C, ∀b ∈ [B]. (1)
Because of the high density of BSs, each UE u will, in general, be within communication range of multiple BSs. We denote by

I u = b ∈ [B] : G (b)
u > 0 the set of UE u's neighboring BSs, i.e., all BSs that have UE u within their coverage area and are able to receive requests and transmit content back to u. Among these BSs, under allocation X, a subset J u,f (X) = {b ∈ I u : (b, f ) ∈ X} is actually caching f . Assume now that a set of BSs, B ⊆ I u , uses CoMP to jointly transmit the same file f to UE u. Then, the end-to-end delay is given by:

t u (B) = M W log 2 1 + b∈B G (b) u , ( 2
)
where W is the channel bandwidth, so the denominator is the aggregate channel capacity1 as in [START_REF] Tse | Fundamentals of wireless communication[END_REF], [START_REF] Ao | Distributed caching and small cell cooperation for fast content delivery[END_REF]. We consider that t u (∅) = +∞. We assume that the aggregate request process follows the IRM model: each request is for file f with probability p f independently from the past, where p 1 ≥ p 2 ≥ . . . ≥ p F . Moreover, each UE is equally likely to have generated the request. We will consider non-stationary traffic demand later in Section VI.

Upon every request, the network operates as follows: UE u broadcasts an inquiry message for file f that is received by its neighboring BSs in I u . Then, according to the current cache state, there are two possibilities: downloads f from the back-end server and then transmits it to u. In this case, u experiences a delay consisting of (i) the time to fetch the file through the backhaul network, hereafter denoted by d B , plus (ii) the end-to-end delay to download from b * , i.e., t u ({b * }).

• If J u,f (X) = ∅ (Cache
• If J u,f (X) = ∅ (Cache Hit), the BSs in J u,f (X) can
jointly transmit to u, or the BS with the highest SNR in I u \J u,f (X), say it b , can retrieve an additional copy of f and then the BSs in J u,f (X)∪{b } can jointly transmit to u. The delay in the two cases is respectively t(J u,f (X)) and d B + t(J u,f (X ∪ {b })). The system will opt for the solution with the smallest delay. 2In both cases, the delay experienced by UE u to download file f under allocation X can be expressed as follows:

d u,f (X) = min{t u (J u,f (X)), d B + t u (J u,f (X) ∪ {b })}, (3) where b = arg max b∈Iu\J u,f (X) G (b) u .

III. OPTIMIZING STATIC CACHE ALLOCATIONS

In this section, we assume contents are prefetched at caches during low-traffic periods (e.g., at night), as in related works [START_REF] Shanmugam | Femtocaching: Wireless content delivery through distributed caching helpers[END_REF], [6]. Files are allocated with the goal of minimizing the average experienced delay, assuming file popularities are known. This corresponds to solving the following problem:

Problem 1 (Average Delay Minimization Problem). minimize X⊆V d(X) = u∈[U ] 1 U f ∈[F ] p f d u,f (X) (4) subject to |X ∩ V (b) |≤ C, ∀b ∈ [B].
The objective ( 4) is the average experienced delay for a request over all UEs and files and d u,f (X) is given by (3).

We start studying Problem 1 in the homogeneous SNR regime, where we assume that all non-zero SNRs are equal to g (i.e., G (b) u = g). We observe that it is hard to find Problem 1's exact solution:

Proposition III.1. Problem 1 is NP-Hard, even in the homo- geneous SNR regime.
The proof is presented in Appendix I-B, and it relies on reducing the NP-Hard FemtoCaching problem in [START_REF] Shanmugam | Femtocaching: Wireless content delivery through distributed caching helpers[END_REF] to Problem 1.

A simple heuristic to approximate Problem 1 is through the greedy algorithm described as follows: Start from an empty solution X = ∅ and then iteratively add to X the element (b, f ) ∈ V that does not violate the constraints (1) and maximizes the marginal delay gain d(X) -d(X ∪ {(b, f )}). We present a formal description in Algorithm 1. In the worstcase the algorithm goes through BC iterations, in which all O(BF ) possible placements must be checked, resulting in a time complexity of O(B 2 F C).

Algorithm 1: GREEDYAD input : files popularities p f , ∀f ∈ [F ] and network topology G (b) u , ∀b ∈ [B], ∀u ∈ [U ] output: allocation set X 1 X ← ∅ 2 while |X| < B • C do 3 δ * ← 0 4 for b ∈ [B] do 5 if |X ∩ V (b) |< C then 6 for f ∈ [F ] do 7 δ ← d(X) -d(X ∪ {(b, f )}) 8 if δ > δ * then 9 i ← b, j ← f, δ * ← δ 10 X ← X ∪ {(i, j)}
In order to provide approximation guarantees for GREEDYAD, we need to express Problem 1 as a maximization problem. The following problem is equivalent 3 to Problem 1. 3 Two optimization problems are "equivalent" if they have the same set of (global) optimizers [START_REF] Boyd | Convex optimization[END_REF]Section 4.1.3].

Problem 2 (Average Delay Saving Maximization Problem

). maximize X⊆V s(X) = d (0) -d(X) (5) subject to |X ∩ V (b) |≤ C, ∀b ∈ [B],
where

d (0) = d B + M W log 2 (1+g)
is the delay experienced upon a cache miss. Function ( 5) can be seen as the average delay saving for a request under allocation X. Now, consider the following lemmas:

Lemma III.2. Function (5) is monotone and submodular.

The proof is presented in Appendix I-C.

Lemma III.3. Constraints (1) define a partition matroid. This lemma was originally proved in [5, Lemma 2]. Finally, the following theorem provides the approximation guarantees for GREEDYAD in the homogeneous SNR regime.

Theorem III.4. In the homogeneous SNR regime, GREEDYAD is a 1/2-approximation algorithm for Problem 2, i.e.,

s X GREEDYAD ≥ 1 2 s X OPT ,
where X GREEDYAD is a solution provided by GREEDYAD and X OPT is an optimal one.

Proof. Problem 2 involves the maximization of a monotone submodular set function (Lemma III.2), subject to a partition matroid constraint (Lemma III.3). Therefore, according to [25, Theorem 3.1], the greedy algorithm achieves a 1 2approximation ratio.

GREEDYAD can also be used to approximate Problem 1 in the general case, though it does not enjoy the same approximation guarantees as in the homogeneous SNR regime. The reason is that the objective function is no longer submodular in the heterogeneous SNR regime as we show in an example in Appendix I-D. However, we see in Section VI that GREEDYAD can still provide reasonable results.

The key characteristic of heterogeneous networks for our problem is the fact that UEs may be connected to multiple BSs simultaneously. Problem 1 imposes that allocation variables related to nearby caches are non-trivially coupled in two levels: (i) If the BS with the best SNR does not cache the requested file, it may fetch it from the back-end servers and (ii) neighboring BSs caching the requested file may jointly transmit it (with CoMP). We illustrate the trade-off created by these conflicting aspects in Section IV.

IV. CASE STUDY: FULL-COVERAGE SCENARIO

While the previous section provides a formal complexity analysis for the problem at hand, it does not provide much insight as to what the optimal allocation looks like in different scenarios. In order to fill this gap, we investigate some special instances of the problem that shed some light into the properties of the optimal cache allocation. We study the fullcoverage scenario, which considers two assumptions: (i) SNRs are homogeneous and (ii) each UE u can connect to all BSs (I u = [B], for all u), so every UE has access to (the same) aggregate cache capacity of B • C files.

In this scenario, the end-to-end delay ( 2) is only a function of the number of copies in the system, then:

t(k) = max M W log 2 (1+kg) , M W log 2 (1+B•g) , (6)
where we consider that we cannot have more than B copies. We consider t(0) = +∞.

In this case, we can rewrite (3) as follows:

d(|J u,f (X)|) = min {t(|J u,f (X)|), d B + t(|J u,f (X)|+1)} . (7)
We first observe that, in the full-coverage scenario, it is possible to efficiently compute the optimal allocation: Proposition IV.1. In the full-coverage scenario, an allocation provided by GREEDYAD is optimal.

The proof of Proposition IV.1 is presented in Appendix II-A. For the upcoming results, we define locally optimal allocations as follows:

Definition 1. A cache allocation X is locally optimal, if it does not exist another allocation X such that d(X ) < d(X), where X differs from X only by a single file at a single cache.

First, we note that: Lemma IV.2. In the full-coverage scenario, an allocation is optimal if and only if it is locally optimal (Definition 1).

The proof of Lemma IV.2 is in Appendix II-B. Then, we characterize for the full-coverage scenario, the necessary and sufficient conditions for the optimal allocation to be one of the two extreme ones: Full-diversity (one copy of each of the B • C most popular files is stored in the network), and full-replication (the C most popular files are cached in each one of the B BSs).

Proposition IV.3. In the full-coverage scenario, full-diversity is an optimal allocation if and only if

p 1 (d(1) -d(2)) ≤ p B•C (d(0) -d(1)), (8)
and full-replication is an optimal allocation if and only if

p C+1 (d(0) -d(1)) ≤ p C (d(B -1) -d(B)). (9)
The proof of Proposition IV.3 is presented in Appendix II-C. As an application of the results above, Fig. 1 shows, for a full-coverage scenario, for which regions of the parameter space (g, d B ) a full-diversity and full-replication allocations are optimal. Files popularities are generated according to Zipf law with exponent α.

The optimal solution depends on parameters g, d B in a complex way. Fig. 1 (left) shows a simple setup, where 5 separated regions are formed. For a given value of g, for high values of d B , we want to avoid paying the high retrieval cost for as many contents as possible, and then full-diversity is optimal. As we diminish d B , the miss cost decreases and some form of replication is beneficial (mixed region), until we reach a full replication region. However, if we keep reducing d B , the optimal allocation moves back to full-diversity (passing again through a mixed region). This happens because, when

d B ≈ 0, d(1) = d B + t(2) and d(2) = t(2) (because B = 2).
This makes the LHS of ( 8) approximately zero and smaller than the RHS. A more realistic setup is provided in Fig. 1 (right). The fact that we cannot see the full-replication region is caused by the low difference in popularity of files C and C + 1, for the specific values of C and α.

However, given an instance of a generic topology, it is not guaranteed that both directions of the conditions in Proposition IV.3 are going to be satisfied. For example, consider a specific topology where BSs do not overlap at all. The optimal allocation is full-replication, even if condition (8) holds. In this case (and for any topology different from full-coverage), condition (8) is necessary but not sufficient for full-diversity to be the optimal allocation. Although Proposition IV.3 does not hold for general topologies, we can still derive new conditions: Corollary 1. For general network topologies, assuming homogeneous SNRs, the following conditions hold: (i) Inequality (8) is a necessary condition for the full-diversity allocation to be locally optimal, and (ii) inequality (9) is a sufficient condition for the full-replication allocation to be locally optimal.

The proof of Corollary 1 is presented in Appendix II-D.

Corollary 1 can be used to forecast the best caching strategy for a given network. If files popularities, average SNR and backhaul access delay can be estimated, it is possible to analytically measure how close is the optimal allocation to an "extreme" one. For example, this may help develop an intuition on how beneficial CoMP joint transmissions can be for a given network setting.

Although static solutions have good performance and may eventually be optimal, they can rarely be deployed in practice because, as discussed in Section I, real systems hardly have a centralized intelligence aware of the entire network topology, transmission characteristics, and stationary files popularities [START_REF] Leconte | Placing dynamic content in caches with small population[END_REF]. However, given the tight approximation guarantees they offer, they work as a useful baseline for dynamic policies. Next section presents online solutions for the average delay minimization problem.

V. ONLINE CACHING POLICIES

In this section, we assume that caches are implemented as LRU-like queues with capacity for storing up to C files. The most-recently-used file is at the front and least-recently-used file is at the rear of the queue. The cache can perform three operations: (i) Insert a new file to the front, (ii) evict the file at the rear, and (iii) move-to-the-front a file already present.

At every request (u, f ) from UE u for file f , after u's neighboring BSs serve the file, the respective caches react to that request by performing a set of operations. These operations aim to minimize the average experienced delay. Then, in what follows, we will consider the marginal delay gain experienced by UE u for having a copy of file f at BS b as follows:

∆d (b) u,f (X) = d u,f (X \ {(b, f )}) -d u,f (X) . (10)
In the next subsections, we introduce two online caching policies, qLRU-∆d and 2LRU-∆d. We use the notion of marginal delay gain ∆d [START_REF] Ao | Distributed caching and small cell cooperation for fast content delivery[END_REF], to drive the operations of distributed caching algorithms.

(b) u,f (X), in

A. qLRU-∆d Caching Policy

The qLRU-∆d caching policy is inspired by qLRU-LAZY in [START_REF] Leonardi | Implicit coordination of caches in small cell networks under unknown popularity profiles[END_REF], that is shown to maximize the hit ratio when parameter q converges to 0, under IRM request process. As we discuss in detail in Appendix III, we use the results in [START_REF] Neglia | A Swiss Army Knife for Dynamic Caching in Small Cell Networks[END_REF] to provide similar guarantees for the minimization of the average experienced delay. In summary, the policy's core idea is to perform insertions and moves-to-the-front with probabilities proportional to the gain [START_REF] Ao | Distributed caching and small cell cooperation for fast content delivery[END_REF]. The evictions occur to the leastrecently-used cached files.

qLRU-∆d Policy: Upon a request (u, f ), given the current allocation X:

(i) All neighboring BSs caching f (∀b ∈ J u,f (X)) move f to the front with probability:

ρ (b) u,f (X) = β • ∆d (b) u,f (X), (11)
where constant β guarantees that ρ

(b) u,f (X) ∈ (0, 1]. (ii)
The remaining BSs (∀b ∈ I u \J u,f (X)) evict the file at the rear and insert f with probability:

q (b) u,f (X) = q • σ (b) u,f (X), (12)
where q ∈ (0, 1] is a dimensionless parameter and:

σ (b) u,f (X) = γ • ∆d (b) u,f (X ∪ {(b, f )}) , (13)
where γ guarantees that σ

(b)
u,f (X) ∈ (0, 1]. We formalize qLRU-∆d caching policy in Algorithm 2 from the perspective of each BS b. The algorithm is a simple if-then-else clause triggered by a request message from the UE. Then, it is O(1) both in terms of run time and exchanged messages.

Although each BS runs the algorithm individually, the following result suggests that they manage to reach implicit coordination that asymptotically leads to an optimal allocation: Algorithm 2: qLRU-∆d Caching Policy (for BS b) Insert f to cache Proposition V.1. Under IRM request traffic, Che's [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF], [START_REF] Fagin | Asymptotic miss ratios over independent references[END_REF], and exponentialization [START_REF] Leonardi | Implicit coordination of caches in small cell networks under unknown popularity profiles[END_REF] approximations, a network of qLRU-∆d caches asymptotically achieves an optimal caching configuration, when q → 0. Proposition V.1 follows from a more general result [17, Prop. IV.1] that we adapt in Appendix III. In fact, in this paper, we adapt the general caching policy qLRU-∆, in [START_REF] Neglia | A Swiss Army Knife for Dynamic Caching in Small Cell Networks[END_REF], to solve the average delay minimization problem (4). We provide an intuitive explanation of why qLRU-∆d is optimal. Intuition: We observe that, as q converges to 0, the cache exhibits two different dynamics with very different timescales: The insertion of new files tends to happen more and more rarely (q (b) u,f (X) converges to 0), while the frequency of moves-to-the-front for files already in the cache is unchanged (ρ (b) u,f (X) does not depend on q). A file f at cache b is moved to the front with a probability proportional to ∆d (b) u,f (X), i.e. proportional to how much the file contributes to reduce the delay of that specific request. This is a very noisy signal: Upon a given request, the file is moved to the front or not. At the same time, as q converges to 0, more and more moves-to-the-front occur between any two file evictions. The expected number of moves-to-the-front file f experiences is proportional to 1) how often it is requested (p f ) and 2) how likely it is to be moved to the front upon a request (ρ

Input: J u,f (X), G (b ) u , ∀b ∈ I u , and d B 1 if b ∈ J u,f (X) then
(b) u,f (X)).
Overall, the expected number of moves is proportional to p f ∆d (b) u,f (X), i.e. its average contribution to the decrease of the expected delay. By the law of large numbers, the random number of moves-to-the-front will be close to its expected value and the least valuable file in the cache likely occupies the last position. We can then think that, when a new file is inserted in the cache, it will replace the file that contributes the least to the decrease of the expected cost. qLRU-∆d then behaves as a random greedy algorithm that, driven by the request process, progressively replaces the least useful file from the cache, until it reaches a global minimum.

Experiments in Section VI show that, under IRM request process, the smaller q is, the closer qLRU-∆d's delay is to GREEDYAD's delay, as it is stated by Proposition V.1.

Remark 1. The probability q (b) u,f (X) is analogous to q in the usual qLRU policy. We note that setting q (b) u,f (X) = q, i.e., a constant value, suffices to prove the asymptotic convergence of the policy (Proposition V.1). However, we propose [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF] to make it more likely to add new copies to helpers bringing a larger marginal gain ∆d (b) u,f (X ∪ {(b, f )}). This can speed up the transient dynamics of the policy (see Section VI). Remark 2. From equations ( 3) and [START_REF] Ao | Distributed caching and small cell cooperation for fast content delivery[END_REF] we see that probabilities ρ u,f can be obtained with negligible overhead and be piggybacked in uplink communications from u to the BSs.

B. 2LRU-∆d Caching Policy

While qLRU-∆d converges to a local optimum for static popularities, in practice, the slow insertion process of qLRU-∆d, for small values of q, becomes problematic when some files are popular over a short time scale: A new file gets a chance to be inserted in the cache on average by every 1/q requests, and by that time, its popularity may have declined. In order to gain in reactivity, we propose 2LRU-∆d.

In 2LRU-∆d, each BS maintains two storage layers: A physical cache and a virtual cache. The physical cache stores the actual files, while the virtual cache stores files' identification data. The identification for file f is denoted by ID(f ). Here, we introduce the support variables X indicating the allocation of the files' IDs at virtual caches throughout the network. The two-layers structure along with the leastrecently-used eviction rule are the core of plain 2LRU. On top of these characteristics, 2LRU-∆d additionally performs insertions and moves-to-the-front with probability proportional to [START_REF] Ao | Distributed caching and small cell cooperation for fast content delivery[END_REF].

2LRU-∆d Policy: Upon a request (u, f ), given the current physical and virtual allocations, X and X, respectively:

(i) All neighboring BSs caching ID(f ) (∀b ∈ J u,f ( X)) move ID(f ) to the front of the virtual cache and, if f is physically cached as well, they move f to the front of the physical cache with probability ρ (b) u,f (X), given by ( 11), otherwise they cache f .

(ii) The remaining BSs (∀b ∈ I u \J u,f ( X)) evict the ID at the rear and insert ID(f ) at the front with probability σ

(b) u,f (X),
given by [START_REF] Garetto | A unified approach to the performance analysis of caching systems[END_REF].

We formalize 2LRU-∆d caching policy in Algorithm 3 from the individual perspective of each BS b. As qLRU-∆d, 2LRU-∆d has constant complexity in time and number of messages. Remark 3. 2LRU-∆d does not enjoy the same theoretical guarantees of qLRU-∆d. However, its two-layer structure works as a more responsive filter, which makes it easier for 2LRU-∆d to reflect short-term popularity variabilities. This fact makes 2LRU-∆d more reactive than qLRU, whose insertion rate may be drastically reduced by parameter q. This feature is particularly favorable for scenarios where the request process has strong temporal locality, which is a characteristic Algorithm 3: 2LRU-∆d Caching Policy (for BS b) Insert ID(f ) to virtual cache often observed in practice [START_REF] Traverso | Temporal Locality in Today's Content Caching: Why It Matters and How to Model It[END_REF]. Additionally, we consider an insertion probability depending on the average delay in order to tune the filter to be more selective towards files that may be supposed to reduce more the delay. Therefore, 2LRU-∆d is a strong candidate to cope with the delay minimization problem under non-stationary request processes, as we observe empirically in Section VI.

Input: J u,f (X), J u,f ( X), G (b ) u , ∀b ∈ I u , and d B 1 if b ∈ J u,f ( X) then 2 Move-to-the-front ID(f ) at virtual cache 3 if b ∈ J u,f (X) then

VI. PERFORMANCE EVALUATION

In this section, we first consider qLRU-∆d convergence to the optimal allocation. In particular, we show that it converges to an allocation similar to the one found by GREEDYAD. Then, we investigate the proposed solutions' performance in a homogeneous SNR regime under synthetic and real request processes. Finally, we study how heterogeneous SNRs affect our policies' performance in a more realistic scenario.

A. Simulation Setup 1) Cellular network: In our experimental setup, we consider files with equal size M = 1.0 Mbits. Each cache can store C = 100 files (i.e., less than 1% of the catalog, which is inline with studies about small cell caching [START_REF] Shanmugam | Femtocaching: Wireless content delivery through distributed caching helpers[END_REF], [START_REF] Paschos | Learning to cache with no regrets[END_REF]). We consider the Berlin topology, which consists of B = 10 BSs located across an area A according to the positions of T-mobile BSs in Berlin extracted from [START_REF]Openmobilenetwork[END_REF]. We call network density the average number of BSs covering a UE and we assume homogeneous spatial user density. The backhaul-access delay is d B = 100 ms and the channel bandwidth is W = 5 MHz, for all pairs BS-UE (which are values consistent with related literature [START_REF] Tuholukova | Optimal cache allocation for Femto helpers with joint transmission capabilities[END_REF], [START_REF] Neglia | A Swiss Army Knife for Dynamic Caching in Small Cell Networks[END_REF]).

2) Request Generation Mechanisms: We simulate a discrete time process, where, at every step, a UE is chosen uniformly at random to generate the next request. We consider the following mechanisms:

• Stationary Request Process: Simulations have a warm up phase and a measurement phase each consisting of 100 million requests. At every request, a file is chosen from a catalog of F = 10 6 files according to a Zipf law with exponent α = 1.2, unless otherwise stated. • Non-stationary Request Process: We additionally consider a request process based on a real trace from Akamai Content Delivery Network [START_REF] Nygren | The Akamai Network: A Platform for High-performance Internet Applications[END_REF], consisting of 17 million requests observed during 5 consecutive days. The trace is described in [START_REF] Neglia | Access-time-aware cache algorithms[END_REF]. Files popularities may vary over different time scales. 3) Algorithms and Policies: Besides our proposed greedy algorithm (Section III) and online policies (Section V), we consider the following solutions in our performance analysis:

• GREEDYHR: Static allocation determined by a greedy algorithm that aims to maximize the hit ratio. • LRU-ONE and LRU-ALL [START_REF] Giovanidis | Spatial multi-lru caching for wireless networks with coverage overlaps[END_REF]. Upon request (u, f ), in LRU-ONE, only a fixed BS b u ∈ I u updates its cache, whereas in LRU-ALL, all BSs b ∈ I u update their caches. • qLRU-LAZY and 2LRU-LAZY [START_REF] Leonardi | Implicit coordination of caches in small cell networks under unknown popularity profiles[END_REF]. Upon request (u, f ), if it is a hit, BS b ∈ I u updates its cache only if J u,f (X) = {b}, if it is a miss, a BS b * is randomly chosen to serve and possibly insert the file into its cache.

The updates and insertions are based on plain qLRU and 2LRU, respectively. • LFU-ALL. Each cache keeps track of how often every file has been requested. The least-frequently-requested cached file is evicted to make room for new insertions.

B. Numerical Results

1) Convergence Analysis for qLRU-∆d

To study the convergence of qLRU-∆d, we consider the homogeneous SNR regime with SNR g = 10dB, for all connected pairs BS-UE, and the stationary request process. We show that, as q tends to 0, qLRU-∆d converges to the optimal static solution similar to the one provided by GREEDYAD.

Fig. 2 (left) shows the average delay of qLRU-∆d and GREEDYAD for different values of q. As q decreases, qLRU-∆d's average delay converges to GREEDYAD's one. Fig. 2 (right) shows the distance between qLRU-∆d and GREEDYAD. The distance dist(P 1 , P 2 ) between policies P 1 and P 2 is defined as the cosine distance 4 between their occupancy vectors θ, which are F × 1 vectors containing the fraction of time every file spent on average in a cache during 4 The cosine distance between vectors u and v is given by dist

(u, v) = 1 - u,v u 2 v 2
, where •, • denotes the inner product. the measurement phase. For GREEDYAD, we can compute directly θ from the allocation matrix. As q decreases, the distance between qLRU-∆d and GREEDYAD decreases, indicating that qLRU-∆d tends to store the same files GREEDYAD stores.

Observation 1. qLRU-∆d converges to the optimal solution provided by GREEDYAD as q → 0. Fig. 3 shows the average delay achieved by GREEDYAD and qLRU-∆d for different values of Zipf exponent α (left) and backhaul-access delay d B (right), when q = 0.001. We observe that the two curves almost match for all different parameter choices, indicating that the convergence is achieved in multiple settings.

Observation 2. For sufficiently small q, qLRU-∆d achieves delays close to GREEDYAD across different network settings and popularity distributions. Now, for a fixed network density of 9.4 and for each online policy, we show the average delay Fig. 4 (left) and the hit ratio Fig. 4 (right) after every 100 requests. In this plot, we can observe the policies convergence process. Files popularities follow a Zipf law with exponent α = 1.2 and we also take g = 10dB and d B = 100ms. We fix q = 0.001 for qLRU-∆d and qLRU-LAZY.

First, we highlight that qLRU-like policies have worse performance in the beginning due to the lower insertion rate (caused by parameter q), until the point where they stabilize and present better results (after 10 7 requests in this scenario). Despite their noticeably faster convergence, 2LRU-like policies reach performance levels close to the qLRU-like ones. This fact reveals 2LRU-∆d higher reactivity and suggests its suitability for dealing with non-stationary request processes.

Observation 3. Despite their slightly worse performance under IRM, 2LRU-like policies present faster convergence.

2) Effect of Network Density

We consider the homogeneous SNR regime with g = 10dB, for all connected pairs BS-UE. We fix the BSs positions and vary the transmission range to achieve network densities from 1.1 (almost isolated BSs) to 9.4 (highly overlapped network, with approximately 73% of UEs covered by all 10 BSs). We fix q = 0.001 for qLRU-∆d and qLRU-LAZY.

In the first setting, we assume a stationary request process. In Fig. 5, we show the normalized average delay as function of the network density, for different policies and algorithms. The qLRU-∆d result is very close to GREEDYAD one, reasserting its convergence across different densities. qLRU-∆d reaches performance gains of up to 20% related to GREEDYHR and other hit-rate-maximization policies. If compared to simpler policies, such as LRU-ALL and LRU-ONE, qLRU-∆d achieves performance gains of up to 27%. Observation 4. Under stationary requests, qLRU-∆d outperforms other policies, presenting nearly optimal results. In Fig. 6, we show the hit ratio corresponding to the experiment previously described. Policies like qLRU-LAZY and 2LRU-LAZY [START_REF] Leonardi | Implicit coordination of caches in small cell networks under unknown popularity profiles[END_REF] outperform other policies as they are designed to maximize the hit ratio, even though they have inferior performance in terms of average delay (see Fig. 5).

Observation 5. As expected, policies targeting the hit ratio in general perform worse in terms of average delay.

In the second setting, we assume the non-stationary request process. The greedy allocation in this case was determined by estimating the files popularities over 5 days. However, real request processes exhibit strong temporal locality features. Static allocations based on time-average popularities smooth out the variability over short time scale. Consequently, we observe in Fig. 7 that GREEDYAD and GREEDYHR perform worse than most of the online policies. u ∈ [g 0 -∆g, g 0 +∆g]. For the static solutions, we simply calculate in advance the average experienced delay for each UE to download from k = 0, . . . , |I u | cached copies, and apply the greedy algorithm as if SNRs were homogeneous. We consider the same Berlin topology, with density of 5.9 BSs/UE, on average, and file requests follow again the (non-stationary) Akamai trace. Moreover, we consider two different scenarios for SNR variability:

• Slow SNR variability regime: SNRs can be considered constant from the moment the request is posed until it is served. • Fast SNR variability regime: SNRs change over the timescale corresponding to the backhaul retrieval time.

As a consequence, the BS that retrieves an additional copy (b in (3)) may not have the highest SNR by the time the copy is available.

First, in Fig. 8, we show the performance of the caching policies under slow SNR variability regime. We present the average delay as a function of the SNR variation ∆g. We observe that all curves decrease for smaller values of SNR variation (∆g ∈ [1.0, 7.0]). The average delay tends to increase again for larger SNR variation (∆g ≥ 9.0) for the hit-ratio maximization schemes. The fact that the BS with the highest SNR serves the requested file mitigates the miss cost for the delay-based schemes. Our proposed policies also outperform other schemes. The maximum observed performance gain (related to 2LRU-∆d and LRU-ALL) moderately increases with ∆g, going from 13% to around 15%. Observation 8. The proposed policies outperform other schemes and the SNR variation has low impact on the schemes' relative performance gains.

The SNR variability may be interpreted as the BSs using different transmission powers, which is a common characteristic of real heterogeneous cellular networks (e.g., in an overlay of femto, pico, and macro cells). The previous experimental result suggests that dynamic policies are resilient to different transmission conditions and may achieve satisfactory results even in these scenarios.

In a similar fashion, in Fig. 9, we show the performance of the caching policies under fast SNR variability regime. All policies presents a strictly increasing behavior. This fact is explained by Jensen's inequality, since the delay is now a convex random function: Given g = g 0 +∆g and g = g 0 -∆g, the delay reduction achieved with the larger g is smaller than the delay increase due to the smaller g . Observation 9. In a scenario with more unstable transmission conditions (fast SNR variability), the average delay strictly increases with the SNR variation.

VII. DISCUSSION AND CONCLUSIONS

In this paper we proposed static and online solutions for the experienced delay minimization problem in a FemtoCaching architecture with CoMP joint transmissions. We formulated the static optimization problem and provided a greedy algorithm with approximation guarantees under homogeneous SNR regime. In this regime, we studied the full-coverage scenario that gives us more insight on the possible solutions. Then, we introduced two novel online caching policies able to minimize delay under IRM and to provide good results under a real request process. In our experiments, we observed qLRU-∆d's convergence and evaluated all proposed cache schemes performances under different request processes and SNR regimes. We conclude that our caching policies achieve considerable performance gains with negligible additional deployment complexity.

Interesting future works include, for example, studying the problem under heterogeneous file size assumption. Besides the files popularities and network transmission conditions (SNRs and backhaul access time), the files' sizes would affect the problem solution by imposing different costs in terms of both storage and transmission time.

B. Proof of Lemma IV.2

The necessary part is trivial: If an allocation is optimal, it provides the minimum delay among all possible allocations.

To prove the sufficient part, we consider a locally optimal allocation X. We prove that X is optimal by contradiction.

Consider the problem introduced in the proof of Proposition IV.1. The optimal greedy algorithm iteratively builds a solution generating the following sequence of allocations:

A * 0 = ∅, A * 1 , A * 2 , . . . , A * B•C
. We observe that each A * i corresponds to a valid allocation.

Let A be the set corresponding to X. We order the elements in A in decreasing order of their weights, generating the following sequence: A 0 = ∅, A 1 , . . . , A B•C . We assume that A is not optimal, i.e., w(A * ) > w(A). Then, there is an index h, such that w

(A * h ) > w(A h ) and w(A * m ) = w(A m ), for m < h. Let A h = A h-1 ∪ { f (h) }. Then, there is an element f (k) ∈ A * h ∩ A c h , such that, w( f (k) ) = w(A * h ) -w(A * h-1 ) > w(A h ) -w(A h-1 ) = w( f (h) ). Moreover, f (k) ∈ A as w(A m ) -w(A m-1 ) is not increasing. Consider h = max{l| f (l) ∈ A} ≥ h. It holds that w( f (h ) ) ≤ w( f (h) ) < w( f (k) ). Also, k = min{l| f (l) / ∈ A} ≤ k. It holds w( f (k ) ) ≥ w( f (k) ). If à = A \ { f (h ) } ∪ { f (k ) }, then w( Ã) > w(A)
and à has been obtained from A replacing a single element, which contradicts the fact that X is locally optimal.

C. Proof of Proposition IV.3

As provided by Lemma IV.2, in the full-coverage scenario, an allocation is optimal iff it is not possible to replace any file in a cache and reduce the expected delay d. Let us consider first the full-diversity allocation. It is evident that it cannot be advantageous to replace one of the B • C most popular files with a less popular file j > B • C. The full-diversity allocation is then optimal iff it is not worthy to replace any file i ∈ [B•C] with an additional copy of a file j ∈ [B • C] \ {i}. This is the case iff:

p i d B ≥ p j (d(1) -d(2)), ∀i ∈ [B • C], j ∈ [B • C] \ {i},
i.e., the delay increase due to the cost to retrieve i through the backhaul is larger than the delay decrease due to the possibility to have two BSs jointly transmitting j. The minimum of the left-hand side of the inequality above is achieved when i = B •C (the least popular file in cache), and the maximum of the right-hand side is achieved when j = 1 (most popular file). Then, the set of inequalities above is satisfied iff

p B•C d B ≥ p 1 (d(1) -d(2)) ,
i.e., we can restrain to consider the possibility to replace the least popular of the B • C files with an additional copy of the most popular file 1.

The reasoning for the full-replication allocation is similar: in this case we need to ensure that replacing one of the B copies of file C with (a first copy of) file C + 1 does not reduce the expected delay, i.e.,

p C+1 d B ≤ p C (d(B -1) -d(B)).

D. Proof of Corollary 1

We prove each part of the corollary separately: First, we want to show that, for general topologies, if fulldiversity is locally optimal, then (8) holds. Let X be a fulldiversity allocation and X be an allocation that differs from X by a single file, i.e., and

X = (X \ {(b, f 1 )}) ∪ {(b, f 2 )}, for any b ∈ [B] and f 1 , f 2 ∈ [F ], such that (b, f 1 ) ∈ X, and (b, f 2 ) ∈ X. Let k u,f = |J u,f (X)| and k u,f = |J u,f (X )|. If full-diversity is locally optimal, then: d(X) ≤ d(X ) ⇔ ⇔ u∈[U ] 1 U f ∈[F ] p f d(k u,f ) ≤ u∈[U ] 1 U f ∈[F ] p f d(k u,f ).
We denote by U(b) the set of users covered by BS b. Notice that, ∀u ∈ U(b), d(k u,f ) = d(k u,f ) so their contributions to the LHS and RHS of the inequality above cancel out. Similarly, all files different from f 1 and f 2 will have equal contributions on both sides, also being canceled out. Then, we can write: (39)

Then, we have that: In particular, we can take f 1 = B • C, f 2 = 1, and b such that (b, 1) ∈ X and we obtain: Therefore, if full-diversity is locally optimal, then (8) holds. Second, we want to show that, for general topologies, if [START_REF] Costantini | Approximation guarantees for the joint optimization of caching and recommendation[END_REF] holds, then full-replication is locally optimal. Equivalently, we prove that if full-replication is not locally optimal, then (9) does not hold. If a full-replication allocation Y is not locally optimal, then there exists b, f 1 , f 2 , with (b, f 1 ) ∈ Y , (b, f 2 ) ∈ Y , such that (Y \ {(b, f 1 )}) ∪ {(b, f 2 )} has a smaller delay than Y . Note that every file C < f ≤ f 2 leads to an even larger reduction to the delay, so we consider f that contradicts [START_REF] Costantini | Approximation guarantees for the joint optimization of caching and recommendation[END_REF].

Therefore, if (9) holds, then full-replication is locally optimal.

APPENDIX III ADAPTATION OF FRAMEWORK [START_REF] Neglia | A Swiss Army Knife for Dynamic Caching in Small Cell Networks[END_REF] TO THE DELAY MINIMIZATION PROBLEM

The idea of this appendix is to derive qLRU-∆d from the general policy qLRU-∆ proposed in [START_REF] Neglia | A Swiss Army Knife for Dynamic Caching in Small Cell Networks[END_REF].

The first important adaptation, is regarding the gain function

u∈[U ]
f ∈[F ] λ u,f γ u,f (X), where λ u,f is the request rate of file f from user u. In our setting we can consider λ u,f = p f /U and γ u,f (X) = d u,f (∅) -d u,f (X),

which is analogous to the "delay saving" function introduced in Section III. We define the marginal gain related to the performance improvement experienced by UE u for retaining file f in the cache of BS b given an allocation X:

∆γ (b) u,f (X) = = γ u,f (X) -γ u,f (X \ {(b, f )}) = d u,f (∅) -d u,f (X) -(d u,f (∅) -d u,f (X \ {(b, f )})) = d u,f (X \ {(b, f )}) -d u,f (X) = ∆d (b) u,f (X), (44)
where ∆d

(b)
u,f (X) matches the definition of marginal delay gain [START_REF] Ao | Distributed caching and small cell cooperation for fast content delivery[END_REF] introduced in Section V. Since we are interested in maximizing the gain, the policy is going to behave as a random greedy algorithm that considers the marginal gain to take probabilistic caching decisions.

The policy qLRU-∆ performs move-to-the-front with probability: .

Similarly, upon a miss, qLRU-∆ inserts the file with probability:

q (b) f (u) = q (b) • δ • ∆γ (b)
u,f (X ∪ {(b, f )}) by [17, Eq. ( 7)] = q • δ • ∆d and q (b) = q, ∀b ∈ [B].

Since we are able to map all the quantities of our problem to the ones in [START_REF] Neglia | A Swiss Army Knife for Dynamic Caching in Small Cell Networks[END_REF], we conclude that qLRU-∆d is a special instance of qLRU-∆ which targets the delay minimization and, therefore, it enjoys the same optimality guarantees.

  (X) marginal delay saving for u by caching f at b under X

  Miss), the BS with the highest SNR, i.e., b * = arg max b∈Iu G (b) u

Fig. 1 .

 1 Fig. 1. Extreme allocations regions for different setups. Axes are in log scale.

  depend on the allocation of file f at nearby BSs or, more precisely, on (i) the aggregate SNR all BSs in J u,f can achieve when transmitting to u(i.e., b ∈J u,f G (b ) u ), (ii) the SNR G (b)u of the local channel from b to u, and (iii) the backhaul delay d B . In cellular networks, each UE takes SNR measurements of BSs within range[START_REF] Sesia | LTE -The UMTS Long Term Evolution: From Theory to Practice[END_REF]. Thus, the information needed to set q

4 with 7 Evict file at the rear of physical cache 8 Insert f to physical cache 9 else 10 with

 47810 prob. ρ (b) u,f (X) in (11) do 5 Move-to-the-front f at physical cache 6 else prob. σ (b) u,f (X) in (13) do 11 Evict file's ID at the rear of virtual cache 12

Fig. 2 .

 2 Fig. 2. Convergence analysis: Delay (left) and allocation (right) as q converges to 0, for α = 1.2, d B = 100ms, and g = 10dB.

Fig. 3 .

 3 Fig. 3. Convergence analysis: α variation with d B = 100ms (left) and d B variation with α = 1.2 (right), for q = 0.001.

Fig. 4 .

 4 Fig. 4. Average delay (left) and hit ratio (right) of different policies after every 100 requests under IRM in a Berlin topology.

Fig. 5 .

 5 Fig. 5. Average delay of different policies versus density in Berlin topology with IRM request process (α = 1.2).

Fig. 6 .

 6 Fig. 6. Hit ratio of different policies versus density in Berlin topology with IRM request process (α = 1.2).

Fig. 7 .

 7 Fig. 7. Performance analysis of various policies in a real topology with Akamai trace.

Fig. 8 .

 8 Fig. 8. Slow SNR variability regime: Berlin topology with density 5.9, g 0 = 10.0dB, and d B = 100.0ms following trace-based request process.

Fig. 9 .

 9 Fig. 9. Fast SNR variability regime: Berlin topology with density 5.9, g 0 = 10.0dB, and d B = 100.0ms following trace-based request process.

  d(k u,f1 ) + p f2 d(k u,f2 )) ≤ 1 |U(b)| u∈U (b) p f1 d(k u,f1 ) + p f2 d(k u,f2 ) ⇔ 1 |U(b)| u∈U (b) p f2 d(k u,f2 ) -d(k u,f2 ) ≤ 1 |U(b)| u∈U (b) p f1 d(k u,f1 ) -d(k u,f1 ) .

  that ∀u ∈ U(b), 2 ≥ k u,f2 > k u,f2 ≥ 0. Then, it holds that:p f2 (d(1) -d(2)) ≤ 1 |U(b)| u∈U (b) p f2 d(k u,f2 ) -d(k u,f2 ) .

  , ∀u ∈ U(b), k u,f1 = 1 and k u,f1 = 0. Then:1 |U(b)| u∈U (b) p f1 d(k u,f1 ) -d(k u,f1 ) = p f1 (d(0) -d(1)).

  together (37) and (38) with (36), we obtain:p f2 (d(1) -d(2)) ≤ 1 |U(b)| u∈U (b) p f2 d(k u,f2 ) -d(k u,f2 ) ≤ 1 |U(b)| u∈U (b) p f1 d(k u,f1 ) -d(k u,f1 ) = p f1 (d(0) -d(1)).

p

  f2 d(k u,f2 ) -d(k u,f2 ) ≤ 1 |U(b)| u∈U (b) p f1 d(k u,f1 ) -d(k u,f1 ) ⇒ ⇒ p f2 (d(1) -d(2)) ≤ p f1 (d(0) -d(1)).

p 1

 1 (d(1) -d(2)) ≤ p B•C (d(0) -d(1)).

  2 = C + 1 and Y = (Y \ {(b, f 1 )}) ∪ {(b, C + 1)}. Let k u,f = |J u,f (Y )| and k u,f = |J u,f (Y )|.Using a similar reasoning to the first part of the proof, we have that:1 |U(b)| u∈U (b) p C+1 d(k u,C+1 ) -d(k u,C+1 > 1 |U(b)| u∈U (b) p f1 d(k u,f1 ) -d(k u,f1 ) .

  that ∀u ∈ U(b), k u,C+1 = 0 and k u,C+1 = 1. Then, it holds that:p C+1 (d(0) -d(1)) = = 1 |U(b)| u∈U (b) p C+1 d(k u,C+1 ) -d(k u,C+1 . (41) Also, ∀u ∈ U(b), k u,f1 = B and k u,f1 = k u,f1 -1. Then: 1 |U(b)| u∈U (b) p f1 d(k u,f1 ) -d(k u,f1 ) = = p f1 (d(B -1) -d(B)).

  41) and (42) with (40), we obtain:p C+1 (d(0) -d(1)) > p f1 (d(B -1) -d(B)) ≥ p C (d(B -1) -d(B))

  move-to-the-front probability used in qLRU-∆d, if the normalization factor is β = max u,f,b,x f ∆d

  (x f ∪ {(b, f )}) by (44) = q (b) u,f (x f ), by def. (12)which is the insertion probability used in qLRU-∆d, if we setδ = max u,f,b,x f ∆d (b) u,f (X ∪ {(b, f )}) -1

  + be the Signal-to-Noise Ratio (SNR) of the wireless channel between BS b and UE u. If the channel SNR is below a minimum SNR value, g min , we assume u and b cannot communicate, and set G

	[B] of base stations (BSs)
	arbitrarily located in a given area A ⊆ R 2 , where [n] denotes
	the set {1, . . . , n}. There is a set [U ] of user equipments (UEs)
	spread across area A that can connect to at least one BS.
	Let G (b) u ∈ R (b)

For simplicity, we assume the limiting capacity provided by Shannon-Hartley theorem. However, our results are also valid for more realistic models, e.g., discrete rates dictated by predetermined Modulation and Coding Schemes (MCS)[START_REF] Arvanitakis | An analytical model for flow-level performance in heterogeneous wireless networks[END_REF], as long as tu is a non-increasing convex function (see Lemma I.1).

In scenarios with highly heterogeneous BSs within range of a UE, the ones currently having a cached copy might have weak SNRs, and the additional backhaul delay to fetch an additional copy to the BS with highest SNR might be amortized by the better overall channel performance.

APPENDIX I ADDITIONAL CONTENT FOR SECTION III A. Homogeneous SNR Additional Notation

In the homogeneous SNR regime, the delay experienced by UE u to download file f under allocation X is a function of the number of cached copies of f in its neighboring BSs, |J u,f (X)|:

In this case, we cannot allow two-steps transmissions when all neighboring BSs are already providing a cached copy of the requested file, i.e., J u,f (X) = I u . Then, to avoid this issue, we redefine t u as follows: [START_REF] Leonardi | Implicit coordination of caches in small cell networks under unknown popularity profiles[END_REF] where we truncate the delay at its minimum allowed value. We consider t u (0) = +∞.

B. Proof of Proposition III.1

We want to show that the FemtoCaching problem [START_REF] Shanmugam | Femtocaching: Wireless content delivery through distributed caching helpers[END_REF] can be reduced to Problem 1. We use the additional notation introduced in Appendix I-A for homogeneous SNR regime. The homogeneous version of the FemtoCaching problem is:

subject to constraints [START_REF]Cisco annual internet report[END_REF], where dF (X) is the average delay for the FemtoCaching problem and t(1) = M W log 2 (1+g) is given by [START_REF] Leonardi | Implicit coordination of caches in small cell networks under unknown popularity profiles[END_REF] dropping subscript u, since every UE is covered by at least one BS.

Assume further that popularities can be written as rational numbers, i.e.,

We observe that, given any two allocations X, X , such that, dF (X) = dF (X ), it holds that:

Equality [START_REF] Sun | Heterogeneous cellular networks[END_REF] is the direct application of the FemtoCaching problem's objective [START_REF] Paschos | Learning to cache with no regrets[END_REF]. We use the popularities' rational notation in [START_REF] Neglia | A Swiss Army Knife for Dynamic Caching in Small Cell Networks[END_REF] to derive [START_REF] Neglia | Cache Policies for Linear Utility Maximization[END_REF]. The absolute part of ( 21) always results in a positive integer, which leads to inequality [START_REF] Tse | Fundamentals of wireless communication[END_REF]. We take a large enough value for the SNR g, such that the following inequality holds:

Then, Problem 1's objective can be written as:

= dF (X) -

Equality ( 24) is an adaptation of Problem 1's objective to the homogeneous SNR regime, where we replace the general delay function (3) with [START_REF] Giovanidis | Spatial multi-lru caching for wireless networks with coverage overlaps[END_REF]. Equation [START_REF] Krause | Simultaneous placement and scheduling of sensors[END_REF] comes from the fact that, if J u,f (X) = ∅ (i.e., cache miss), the delay is

Note that this decomposition is at first redundant, given that definition ( 14) covers both miss and hit cases. We obtain [START_REF] Fagin | Asymptotic miss ratios over independent references[END_REF] by simply putting the indicator functions from [START_REF] Leconte | Placing dynamic content in caches with small population[END_REF] in evidence. Finally, we observe that the first term in ( 27) is exactly the definition of the FemtoCaching objective function, which yields [START_REF] Sesia | LTE -The UMTS Long Term Evolution: From Theory to Practice[END_REF].

Observe that d u (|J u,f (X)|)) < t(1), then the following relation holds:

Now, we prove that, given two allocations X, X ,

and then solving Problem 1 brings the solution to Problem 3.

First, we prove dF (X) < dF (X ) ⇒ d(X) < d(X ):

by ( 29)

Second, we prove d(X) < d(X ) ⇒ dF (X) < dF (X ):

≥ dF (X) by ( 29)

Then, because both implications hold, (30) also holds and, therefore, Problem 3 can be reduced to Problem 1. Because Problem 3 is NP-hard [START_REF] Shanmugam | Femtocaching: Wireless content delivery through distributed caching helpers[END_REF] and we can reduce it to Problem 1, then Problem 1 is NP-hard.

C. Proof of Lemma III.2

We start proving the following lemma: Lemma I.1. For any u and any k 1 , k 2 ∈ Z + , such that k 1 ≤ k 2 , the following inequality holds:

. Function h can be written as a function composition h(x) = (w • y)(x), where w(x)

ln(x) and y(x) = 1+g•x. Function y is affine. Function w first and second derivatives are, respectively,

x 2 ln 3 (x) . For x > 1, w (x) < 0, which makes w decreasing, and w (x) > 0, which makes w convex. Because h is the composition of a convex decreasing function and an affine increasing function, h is also a convex decreasing function for x > 1. Moreover, because t u is the point-wise maximum between h and constant M W log 2 (1+|Iu|•g) , t u is a non-increasing convex function. This means that the function l(k) = t u (k)-t u (k+1) is also non-increasing. Therefore, inequality (31) holds.

We separate the proof of Lemma III.2 in two parts, one for each desired property of s(X).

Monotonicity: Let X ⊂ X ⊂ V and consider the case where X = X ∪ {(b , f )}. We can apply this argument itemby-item to prove the case for general X and X . By definition, the set function ( 5) is monotone if:

We observe that ∀f = f , the LHS equals the RHS in [START_REF] Neglia | Access-time-aware cache algorithms[END_REF], so we focus on cases where f = f . Similarly, we consider only the set of users covered by BS b , that we call U(b ).

Then, (32) becomes:

Notice that t u (k) is non-increasing, which makes d u (k) non-increasing as well (see ( 14)). Then,

) ≥ 0 and, therefore, ( 5) is monotone. Submodularity: Let X ⊂ X ⊂ V and (b , f ) ∈ V \X . The set function ( 5) is submodular if:

We observe that ∀f = f , the LHS equals the RHS in the inequality above, so we focus on cases where f = f . Similarly, we consider only the set of users covered by BS b , i.e., U(b ). Then, the inequality above becomes:

We will prove [START_REF] Edmonds | Matroids and the greedy algorithm[END_REF] by showing that for each u,

and, since it refers to a single file f , we can simplify the notation defining k = |J u,f (X)| and k = |J u,f (X )|. If we prove the inequality above for k = k + 1, then it will hold ∀k ≥ k + 1. Thus, we need to show that ∀u ∈ U(b ),

However, the delay d u is the minimum of two functions (see [START_REF] Giovanidis | Spatial multi-lru caching for wireless networks with coverage overlaps[END_REF]). We observe that

Then, we need to consider only four cases:

, and d u (k + 2) = t u (k + 2). Then, (34) is written as:

which is always true by Lemma I.1. 34) is written as:

Case (II):

Case (III):

Then, (34) becomes:

). This case is analogous to Case (I).

D. Problem 2 is not submodular in the heterogeneous case.

. Additionally, consider that UE u is located in the region covered by all BSs simultaneously, and the power-base SNRs are G u = [30.0, 30.0, 10.0, 100.0]. We consider d B = 10.0ms, M = 1Mbit, and W = 5MHz.

We list below the experienced delay before and after adding a copy of f 1 to BS b 3 in allocations X and X .

Then, we calculate and compare the gain for making such placement in both allocations:

However, as shown in Appendix I-C, if s(X) is submodular, the following inequality must hold

Therefore, s(X) is not submodular in general.

APPENDIX II ADDITIONAL CONTENT FOR SECTION IV

In this appendix we provide the proofs for the results on the Full-Coverage scenario. We use the same notation introduced in Section IV.

A. Proof of Proposition IV.1

For every file f ∈ [F ], we generate B objects f (1) , . . . , f (B) with weight w(f (k) ) = p f (d(k -1)-d(k)) > 0. We gather all objects generated this way in F = {f (1) , . . . , f (B) , ∀f ∈ [F ]}. The total weight of any subset A ⊂ F is w(A) = e∈A w(e).

We observe that any cache allocation X can be mapped to a set A ⊂ F such that w(A) = s(X) and |A|= B • C. In fact, let k f be the number of copies of file f in allocation X, then

can be mapped to an allocation X, such that w(A) = s(X). The mapping is detailed in Alg. 4.

Algorithm 4: Mapping

This is a weight maximization problem, so a greedy algorithm finds the optimal solution A * (see [START_REF] Edmonds | Matroids and the greedy algorithm[END_REF]). A * can be written as

Suppose it is not the case, i.e., ∃f | f (k) ∈ A * but f (h) ∈ A * , for some h < k. Then, there is a set A = A * \{f (k) }∪{f (h) }, such that w(A ) > w(A * ), contradicting the optimality of A * .

As A * = {f (i) : 1 ≤ i ≤ k f , ∀f ∈ [F ], k f > 0}, A * can be mapped to an allocation X * with s(X * ) = w(A * ). We claim that X * is an optimal solution of Problem 2. In fact, any other allocation X can be mapped to a set A with s(X) = w(A) ≤ w(A * ) = s(X * ).

Finally, consider the ordered set of choices of GREEDYAD for Problem 2, and map them to corresponding elements of A (the h-th choice of a copy of f by GREEDYAD corresponds to add f (h) to A). These choices are possible choices for the greedy algorithm in the problem defined in (35). It follows that GREEDYAD provides an optimal solution for Problem 2.