Anastasios Giovanidis
email: anastasios.giovanidis@lip6.fr

Apostolos Avranas
email: apostolos.avranas@huawei.com

Spatial multi-LRU: Distributed Caching for Wireless Networks with Coverage Overlaps

Keywords: Wireless, Cache, LRU, Information Centric Networking, Hit Probability, Popularity, IRM, Temporal locality

This article introduces a novel family of decentralised caching policies, applicable to wireless networks with finite storage at the edge-nodes (stations). These policies, that are based on the Least-Recently-Used replacement principle, are here referred to as spatial multi-LRU. They update cache inventories in a way that provides content diversity to users who are covered by, and thus have access to, more than one station. Two variations are proposed, the multi-LRU-One and -All, which differ in the number of replicas inserted in the involved caches. We analyse their performance under two types of traffic demand, the Independent Reference Model (IRM) and a model that exhibits temporal locality. For IRM, we propose a Che-like approximation to predict the hit probability, which gives very accurate results. Numerical evaluations show that the performance of multi-LRU increases the more the multicoverage areas increase, and it is close to the performance of centralised policies, when multi-coverage is sufficient. For IRM traffic, multi-LRU-One is preferable to multi-LRU-All, whereas when the traffic exhibits temporal locality the -All variation can perform better. Both variations outperform the simple LRU. When popularity knowledge is not accurate, the new policies can perform better than centralised ones.

I. INTRODUCTION

T HE design of today's and future networks is characterised by a paradigm shift, from a host-centric communication architecture, towards an Information Centric Networking (ICN) one [START_REF] Xylomenos | A survey of Information-Centric Networking[END_REF]. Following this novel concept, network nodes are equipped with storage capacity where data objects can be temporarily cached and retrieved [START_REF] Paschos | Wireless Caching: Technical Misconceptions and Business Barriers[END_REF]. In this way information can be made available closer to the user, it can be accessed reliably [START_REF] Timo | Joint cache-channel coding over erasure broadcast channels[END_REF] with minimum delay, and possibly with a quality adaptable to the users' preferences, as envisioned in the case of multimedia files. The principal benefits are the partial elimination of redundant traffic flows at the core network by serving demands from intermediate nodes, as well as reduced latency of service [START_REF] Sourlas | Storage planning and replica assignment in content-centric publish/subscribe networks[END_REF]. The edge-nodes constitute a very important part of the ICN architecture, since it is where the wireless users directly have access to. When these nodes are equipped with storage capability, download path length is minimised [START_REF] Elayoubi | Performance and cost effectiveness of caching in the mobile access network[END_REF].

In this work, we consider the wireless edge of a content centric network, which consists of a set of transmitting nodes taking fixed positions on a planar area, and a set of users dynamically arriving at this area and asking for service. The set of transmitters can refer to base stations (BSs) of a cellular network, small stations of heterogeneous networks, WIFI hotspots, or any other type of wireless nodes that can provide access to users. A user can be covered by multiple of these nodes, but she/he will be served by only one. Each node is equipped with memory of some given size.

An important question is how to best manage the available edge-memories, in order to maximise the hit probability of user-demands. We define the hit probability as the probability that a user finds her/his demand cached in the memory of one of the covering cells. By managing, we mean to choose a policy that decides which objects to install in each cache and how each cache inventory is updated over time.

Given the possibility for multi-coverage, cache management should target two, somewhat conflicting, goals: On the one hand make popular objects, which attract the large bulk of demands, generously available at many geographic locations. On the other hand, make good use of multi-coverage, by filling the memory caches in a way that provides large object variety to each user, so that also less popular objects can be found in the caches. Additionally, since wireless nodes (BSs) are scattered over a very large area and are of considerable number, related operations should be distributed as in [START_REF] Naveen | On the interaction between Content Caching and Request Assignment in Cellular Cache Networks[END_REF], [START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF], [START_REF] Leconte | Designing adaptive replication schemes in distributed content delivery networks[END_REF], and centralised solutions should be avoided.

A. Related research

Single Cache: There exists a variety of cache placement policies that apply to single caches, when no coverage overlap is considered. These include the Least Frequently Used (LFU), the Least Recently Used (LRU), and their variations. Specifically LRU has been extensively studied and approximations to the hit probability have been proposed, like the one from Dan and Towsley [START_REF] Dan | An approximate analysis of the LRU and FIFO buffer replacement schemes[END_REF]. Che et al proposed in 2002 [START_REF] Che | Hierarchical web caching systems: Modeling, design and experimental results[END_REF] a simple approximation for the (single-)LRU under the Independent Reference Model (IRM) [START_REF] Coffman | Operating Systems Theory[END_REF], which results in an analytic formula for the hit probability with excellent fit to simulations. This fitness is theoretically explained by Fricker et al in [START_REF] Fricker | A versatile and accurate approximation for LRU cache performance[END_REF]. Application of the Che approximation under more general traffic conditions, to variations of the LRU for single caches as well as networks of caches, is provided by Martina et al [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF]. In that work, and further in Elayoubi and Roberts [START_REF] Elayoubi | Performance and cost effectiveness of caching in the mobile access network[END_REF], it is shown that for mobile networks, application of pre-filtering improves the performance of LRU.

Multiple Caches: The problem of optimal content placement, when network areas are covered by more than one station has also been recently studied. A number of pro-active caching policies have been proposed, where the cache inventories are pre-filled by content, based on knowledge of the content popularity distribution and additional network-related information. Golrezaei et al [START_REF] Golrezaei | Femtocaching: Wireless video content delivery through distributed caching helpers[END_REF] find the optimal content placement that maximises hit probability, when full network information (popularity, node and user positions) is available. They formulate a binary optimisation problem and propose approximation and greedy algorithms for its solution. Using reduced information (content popularity, coverage probability), Błaszczyszyn and Giovanidis [START_REF] Błaszczyszyn | Optimal geographic caching in cellular networks[END_REF] provide a randomised strategy that maximises the hit probability. Poularakis et al. [START_REF] Poularakis | Approximation algorithms for mobile data caching in small cell networks[END_REF] formulate and solve the joint content placement and user association problem that maximises the fraction of content served by the caches of the edge-nodes. Araldo et al. [START_REF] Araldo | Design and evaluation of costaware information centric routers[END_REF] propose joint cache sizing/object placement/path selection policies that consider also the cost of content retrieval. Recently, Naveen et al. [START_REF] Naveen | On the interaction between Content Caching and Request Assignment in Cellular Cache Networks[END_REF] have formulated the problem in a way to include the bandwidth costs, and have proposed an online algorithm for its solution. Further distributed replication strategies that use different system information are proposed by Borst et al [START_REF] Borst | Distributed caching algorithms for content distribution networks[END_REF], and also by Leconte et al [START_REF] Leconte | Designing adaptive replication schemes in distributed content delivery networks[END_REF]. The problem of optimal request routing and content caching for minimum average content access delay in heterogeneous networks is studied by Dehghan et al in [START_REF] Dehghan | On the complexity of optimal routing and content caching in heterogeneous networks[END_REF].

Traffic: There can be strong dependencies between content demands, objects can have a finite lifespan, and new ones can appear anytime. These phenomena constitute the temporal locality (not captured from the standard IRM traffic model). Such type of traffic was studied for (single-)LRU initially by Jelenković and Radovanović [START_REF] Jelenković | Least-recently-used caching with dependent requests[END_REF], and recently using also statistics from user measurements, by Traverso et al [START_REF] Traverso | Unravelling the impact of temporal and geographic locality in content caching systems[END_REF] and Olmos et al [START_REF] Olmos | Catalog dynamics: Impact of content publishing and perishing on the performance of a LRU cache[END_REF].

Point Processes: The cache management problem for cellular networks has also been approached using point process modelling of the network node positions. Bastug et al. [START_REF] Bastug | Cache-enabled small cell networks: Modeling and Tradeoffs[END_REF] find the outage probability and content delivery rate for a given cache placement. Furthermore, Tamoor-il-Hassan et al [START_REF] Tamoor-Ul Hassan | Modeling and analysis of content caching in wireless small cell networks[END_REF] find the optimal station density to achieve a given hit probability, using uniform replication. The policy in [START_REF] Błaszczyszyn | Optimal geographic caching in cellular networks[END_REF] can also be applied for point process BS placement.

B. Contributions

This work has the following contributions to the subject of caching at the network edge.

-Main contribution: It introduces (Sec. II) a new family of decentralised caching policies, which exploit multi-coverage, called spatial multi-LRU. Specifically, two variations of this family are studied, namely multi-LRU-One and -All. These policies constitute an extension of the classic (single-)LRU, to cases where objects can be retrieved by more than one cache.

The work investigates how to best adapt the actions of update, insertion and eviction of content for multiple caches.

-The modelling takes geometry and time explicitly into consideration for the analysis of caching policies. Specifically, it investigates a three-dimensional model (two-dimensional space and time). In this, stations have a certain spatial distribution (modelled by Point Processes) and coverage areas may overlap, allowing for multi-coverage. Furthermore, it is a dynamic model, where users with demands arrive over time at different geographic locations (Sec. III).

-The hit probability performance of the new policies is evaluated for two types of traffic: (a) IRM (Sec. IV), and (b) traffic with temporal locality (Sec. V). Specifically for the case of IRM, we initiate from the Che approximation to derive new analytic solutions (Sec. IV-B). Two additional approximations are made here, namely the Cache Independence Approximation (CIA) for multi-LRU-One, and the Cache Similarity Approximation (CSA) for multi-LRU-All, that allow for simple but accurate analytic formulas.

-The performance of the policies is numerically evaluated. Verification for the Che-like approximations (IRM), as well as further comparison of the multi-LRU policies with other policies from the literature, under both traffic inputs, are provided in Sec. VI. For comparison we consider distributed as well as centralised policies that use various network information.

Important conclusions: For IRM, the multi-LRU-One always performs better than the -All variation. For traffic with temporal locality, the multi-LRU-All can perform better than -One in cases where sufficient memory is available. Both policies outperform the (single-)LRU and perform close to centralised policies for IRM traffic with significant multicoverage. In the case of temporal locality it is shown that multi-LRU can better adapt to popularity changes compared to policies which depend on popularity estimates and content prefetching.

II. CACHING AND ITS MANAGEMENT

Caching policies can profit from various system information related e.g. to user traffic, node positions and coverage areas, or caching decisions of neighbouring nodes. Specifically, based on the available knowledge on content popularity, cache management policies can be grouped into two categories:

(i) Policies with per-reQuest updates (POQ). For these, file popularity information is not available. Updates of the cache content are done locally and are triggered by the users on a per-request basis. The Least Frequently Used (LFU), as well as the Least Recently Used (LRU and q-LRU) policies for single cache fall in this category.

How LRU works: Given an isolated cache of size K, the policy keeps the K most recently demanded objects. The first position of the cache is called Most Recently Used (MRU) and the last one Least Recently Used (LRU). When a new demand arrives, there are two options. (a. Update) The object demanded is already in the cache and the policy updates the object order by moving it to the MRU position. (b. Insertion) the object is not in the cache and it is inserted as new in the MRU position, while the object in the LRU position is evicted.

In this work we call this policy, single-LRU.

(ii) Policies with Popularity updates (POP), where exact or estimated information over content popularities is available, and is used to infrequently update cache inventories by prefetching. This category covers the Most Popular Content (MPC) caching strategy, as well as policies that result from solutions of optimisation problems with a-priori knowledge of additional system information, e.g. the Greedy Full Information (GFI) [START_REF] Golrezaei | Femtocaching: Wireless video content delivery through distributed caching helpers[END_REF], and the Probabilistic Block Placement (PBP) [START_REF] Błaszczyszyn | Optimal geographic caching in cellular networks[END_REF]. Due to the extra information, POP are expected to have higher hit-probability than POQ (but this is not always true).

A. Spatial multi-LRU

This work introduces a novel family of distributed cache management POQ policies that profit from multi-coverage. These are the spatial multi-LRU policies and are based on the single-LRU. The main idea is that, since a user can check all the caches of covering BSs for the demanded object and download it from any one that has it in its inventory, cache updates and object insertions can be done more efficiently than by just applying single-LRU independently to all caches. The fact that the user triggers a cache's update/insertion action, allows each cache to be indirectly informed about the inventory content of its neighbours. Variations of the multi-LRU family differ in the number of inserted contents in the network, after a missed content demand. Differences can also appear in the update phase.

• multi-LRU-One: Action is taken in only one cache out of the covering m ≥ 1. (a. Update) If the content is found in a non-empty subset of the m caches, only one cache from the subset is used for download and, for this, the content can be moved to the MRU position. (b. Insertion) If the object is not found in any cache, it is inserted only in one, while its least-recently-used object is evicted. This one cache can be chosen as the closest to the user, a random one, or from some other criterion. (Here, we choose the closest node).

• multi-LRU-All: Insertion action is taken in all m caches. (a. Update) If the content is found in a non-empty subset of the m caches, all caches from this subset are updated. (b. Insertion) If the object is not found in any cache, it is inserted in all m. A variation based on q-LRU can be proposed, where the object is inserted in each cache with probability q > 0.

The motivation behind the different versions of the multi-LRU policies is the following. When a user has more than one opportunity to be served due to multi-coverage, she/he can benefit from a larger cache memory (the sum of memory sizes from covering nodes.). In this setting, the optimal insertion of new content and update actions are not yet clear. If multi-LRU-One is applied, a single replica of the missed content is left down in one of the m > 1 caches, thus favouring diversity among neighbouring caches. If multi-LRU-All is used, m replicas are left down, one in each cache, thus spreading faster the new content over a larger geographic area (the union of m covering cells), at the cost of diversity. q-multi-LRU-All is in-between the two, leaving down a smaller than m number of replicas. A-priori, it is unclear which one will perform better with respect to hit probability.

The performance largely depends on the type of incoming traffic. For fixed object catalogue and stationary traffic, diversity in the cache inventories can be beneficial, whereas for time-dependent traffic with varying catalogue, performance can be improved when many replicas of the same object are available, before its popularity perishes.

III. NETWORK MODEL

Wireless multi-coverage: For the analysis, the positions of transmitters coincide with the atoms from the realisation of a 2-dimensional stationary Point Process (PP), Φ b = {x i }, indexed by i ∈ N + = {1, 2, . . .}, with intensity λ b > 0 in [m -2 ]. In this setting, the type of PP can be general, however we consider here:

-A homogeneous Poisson PP (PPP) Φ b,P with intensity measure E [Φ b,P (A)] = λ b |A|, for some area A ⊂ R 2 , where |A| is the surface of A.

-A square lattice Φ b,L = ηZ 2 + u L , Z = {. . . , -1, 0, 1, . . .}, whose nodes constitute a square grid with edge length η > 0, randomly translated by a vector u L that is uniformly distributed in [0, η] 2 (to make Φ b,L stationary). Its

intensity is equal to λ b = η -2 .
There are two different planar areas (cells) associated with each atom (BS) x i . The first one is the Voronoi cell V(x i ) ⊂ R 2 . Given a PP, the Voronoi tessellation divides the plane into non-overlapping planar subsets, each one associated with a single atom. A planar point z belongs to V(x i ), if atom x i is the closest atom of the process to z. In other words,

V(x i ) = z ∈ R 2 : |z -x i | ≤ |z -x j | , ∀x j ∈ Φ .
The second one is the coverage cell C i . Each transmitter node x i ∈ Φ b has a possibly random area C i of wireless coverage associated with it. When users arrive inside the coverage cell of x i they can be served by it, by downlink transmission. In general C i is different from V(x i ). Coverage cells can overlap, so that a user at a random location may be covered by multiple BSs, or may not be covered at all. The total coverage area from all BSs with their coverage cells is [START_REF] Baccelli | Stochastic Geometry and Wireless Networks[END_REF]Ch.3]).

Ψ = i∈N+ {x i + C i } (see
Due to stationarity of the PP Φ b , any planar location y ∈ R 2 can be chosen as reference for the performance evaluation of the wireless model. This reference is called the typical location o, and for convenience we use the Cartesian origin (0, 0).

Because of the random realisation of the BS positions and the random choice of the reference location o, the number of BS cells covering o is also random. This coverage number random variable (r.v.) N (see [START_REF] Błaszczyszyn | Optimal geographic caching in cellular networks[END_REF], [START_REF] Keeler | SINR-based kcoverage probability in cellular networks with arbitrary shadowing[END_REF]) depends on the PP Φ b and the downlink transmission scheme, with mass function

p m := P [N = m] , m = 0, 1, . . . , M, (1)
where

M ∈ N + ∪ {∞}. It holds, M m=1 p m = 1.
The choice of the coverage model determines the shape of the coverage cells and consequently the values of the coverage probabilities p m . In this work the choice of C i is left to be general (for the evaluation, specific models are considered). Special cases include: (1) the SINR Model and (2) the SNR or Boolean Model. Both models consider the coverage cell C i of x i , as the set of planar points for which the received signal quality from x i exceeds some threshold value T . The motivation is that T is a predefined signal quality, above which the user gets satisfactory Quality-of-Service. The difference between these two is that the SINR model refers to networks with interference (e.g. when BSs serve on the same OFDMA frequency sub-slot), whereas the SNR model, to networks that are noise-limited (e.g. when neighbouring BSs operate on different bandwidth, by frequency reuse). For the Boolean model the C i is a ball B(x i , R b ) of fixed radius R b centred at x i . It coincides with the SNR model, when no randomness of signal fading over the wireless channel is considered. A more detailed presentation of the different coverage models can be found in [START_REF] Baccelli | Stochastic Geometry and Wireless Networks[END_REF], [START_REF] Błaszczyszyn | Equivalence and comparison of heterogeneous cellular networks[END_REF] and [START_REF] Baccelli | On a coverage process ranging from the Boolean model to the Poisson Voronoi tessellation, with applications to wireless communications[END_REF].

Storage: We consider the case where a cache memory of size K ≥ 1 is installed and available on each transmitter node x i of Φ b . (All content files are considered of equal size, see below). The memory inventory of node x i at time t is denoted by Ξ i (t) and is a (possibly varying over time) subset of the content catalogue F(t), with number of elements |Ξ i (t)| ≤ K.

Traffic Models: Each user arrives at some point in space and time, with a request for a specific data object. The arrivals are assumed spatially independent. We model the users by a marked space-time Point Process in R 2 × R × N, Φ u = {(ψ i , t i , z i )}, where ψ i takes values on the Euclidean plane, and the time t i of arrival occurs at some point on the infinite time axis. The mark z i takes as values the indices of the files/objects j : c j ∈ F(t). Service time is considered fixed and equal to unity but it will not play any role in the analysis. In this work, we evaluate the caching policies under the following two traffic models:

-A spatially homogeneous version of the Independent Reference Model (IRM) [START_REF] Fagin | Efficient calculation of expected miss ratios in the independent reference model[END_REF] (Sec. IV).

-Traffic that exhibits temporal locality, like the Shot Noise Model (SNM) [START_REF] Leonardi | Least recently used caches under the Shot Noise Model[END_REF] (Sec. V).

Typical user: The network performance is evaluated at the typical user u o , who -due to stationarity of the PPP -will be representative of any user of the process. We suppose that this user appears at the Cartesian origin (0, 0), at time t o = 0. In this way, the typical user coincides with the typical location o of the process Φ b at time t = 0.

The model described so far is illustrated in Fig. 1(a) for the case of Poisson placement of transmitters Φ b,P with Poisson arrivals Φ u , and in Fig. 1(b) for the case of a square lattice Φ b,L with Poisson arrivals Φ u . We also provide the reader with a list of symbols in Table I.

IV. MULTI-LRU UNDER SPATIAL IRM TRAFFIC

The new policies are first evaluated under spatial IRM traffic [START_REF] Fagin | Efficient calculation of expected miss ratios in the independent reference model[END_REF], which has the following properties:

(i) The Φ u is a homogeneous Poisson Point Process (PPP) in both space and time, with intensity

λ u > 0 in [m -2 sec -1 ].
Given a planar area A, the arrival rate of users in this area, with any request, is equal to λ u |A| in [sec -1 ]. All users within the area take their positions independently and uniformly.

(ii) The catalogue of available files/objects is fixed over time F(t) := F, and has finite size F . The elements of F are {c 1 , . . . , c F }. We additionally consider that all objects have the same size, normalised to 1. Cases of unequal size will not be treated in this work, but we can always assume that each file can be divided into chunks of equal size, so the same analysis can still be applied.

(ψ i , t i , z i )} λ b intensity of transmission nodes [m -2 ] λu intensity of users [m -2 sec -1 ] A planar area V(x i ) Voronoi cell of node x i C i coverage cell of node x i R b radius of
(iii) The probability a j that a user requests object c j ∈ F (i.e. the object popularity) is constant over time, (can be) known, and independent of all past requests. Objects in F are ordered by popularity: c 1 is the most popular, c 2 the second most popular and so on. The popularity of c j is a j > 0, and to be consistent with the ordering, we also have a 1 ≥ a 2 ≥ . . . ≥ a F . For every popularity distribution it obviously holds, F j=1 a j = 1. Then the marks z i are i.i.d. random variables distributed as Z with mass function {a j }. A consequence is that the users that request object c j ∈ F form a homogeneous space-time PPP with intensity a j λ u [m -2 sec -1 ] (independent thinning of Φ u ).

Without loss of generality, we will consider (especially in the simulations) that the distribution has a Zipf probability mass function, although the analysis holds for general {a j }. This is motivated by traffic measurements showing that dataobject popularity in the WWW follows a power law [START_REF] Huberman | The nature of markets in the World Wide Web[END_REF], [START_REF] Newman | Power laws, Pareto distributions and Zipf's law[END_REF]. In such case, the probability that a user asks for c j is equal to

a j = D -1 j -γ , j = 1, . . . , F . Here, γ is the Zipf exponent, often satisfying γ < 1, so that a 1 /a 2 = 2 γ < 2.
The normalisation factor is equal to D := F j=1 j -γ . Hit performance upper bound: As mentioned already, the performance measure of the caching policies is the hit probability. We can already provide an upper bound for any POP policy under IRM traffic. The bound requires knowledge over the content popularity and coverage number, like the PBP [START_REF] Błaszczyszyn | Optimal geographic caching in cellular networks[END_REF]. The main idea is that the hit probability of a user covered by m cells is maximised if these m inventories have distinct entries, so that the user has the maximum choice. Hence if the mK most popular objects from the set F are installed,

P hit ≤ M m=1 p m F j=1 a j 1 {1≤j≤mK} = M m=1 p m mK j=1 a j .
(

) -5 -4 -3 -2 -1 0 1 2 3 2

A. Che approximation for IRM traffic: Single Cache

The mathematical analysis of LRU policies is complicated, due to the different inter-arrival times for different content and the update/insertion policy. However, Che et al provided in 2002 [START_REF] Che | Hierarchical web caching systems: Modeling, design and experimental results[END_REF] an analysis and a simple approximation for the single-LRU cache, which results in an analytic formula for the hit probability P hit with excellent fit to simulations. In the following, we explain in short the idea and, after, apply it to the multi-LRU policies.

The approximation is based on the so-called characteristic time T C . Given a cache of size K under single-LRU replacement, if at time t = 0 an arrival of object c j occurs, then this will be positioned at the MRU place, either due to a. Update, or due to b. Insertion. This object is removed from the cache if at least K different objects arrive, before a new demand for object c j at time s j > 0. The reason is that, each arrival of a new object moves c j one position away from the MRU and closer to the LRU. Che et al approximate the eviction time of an object by a deterministic quantity, equal for all objects to the characteristic time T C . This is found by solving

F i=1 P (s i < T C ) = K (Che approximation), (3)
using a fixed point procedure, where s i is the first arrival time of object c i , i = j, after t = 0. The summation in (3) is taken over the entire F, which is also part of the approximation. It works well for a large number F of objects, each one of which having a small portion of the popularity. For IRM traffic, the inter-arrival times are exponentially distributed, hence for an area A covered by a single cache, P (s i < T C ) = 1e -λu|A|aiT C . The time-average probability that an object c j is in the cache is P (c j ∈ Ξ) = P (s j < T C ), hence

P (c j ∈ Ξ) IRM = 1 -e -λu|A|aj T C P AST A = P hit (j). (4)
The fact that, for IRM traffic P (c j ∈ Ξ) = P hit (j), is due to the PASTA property of Poisson arrivals. Finally, the approximation for the total hit probability is,

P hit = F j=1 a j P hit (j). (5)

B. Che-like approximation for multi-LRU

We will use the approach of Che for the single-LRU, to derive here similar approximations of the multi-LRU cache management policies, for the network model described in the previous section. (To provide more intuition on this general approach, a similar analysis for a network with only two caches is given in the Appendix).

Consider an arrival of user u o at the Cartesian origin ψ o = (0, 0) at time t o = 0, who requests for object c j . This is the typical user, who is covered by a number m o ≥ 0 of BSs, a realisation of the r.v. N o with mass function {p m }. A common characteristic time T C is assumed for all caches of the network, due to stationarity of all processes. We focus on the cache of a specific x i among the m o covering BSs, for which definitely o ∈ C i . The probability that user u o finds the requested content in the cache of x i , is calculated using the following arguments: There is a previous user u -1 requesting for the same object c j , who arrived in an area S -1 (that varies depending on the type of multi-LRU policy). The u -1 is covered by x i definitely (otherwise the user will not influence Ξ i ) and possibly some other stations, the total number of which is m (the realisation of another r.v. N -1 ). Since we know that u -1 is at least covered by one station (the x i ), the distribution of N -1 has mass function

p m = p m(1 -p 0 ) -1 , m = 1, . . . , M. (6)
Suppose this user arrived at t

- -1 ∈ [t o -T C , t o ],
i.e. within the characteristic time (t -is the time right before t). Then the object is found in

Ξ i (t - o ) at t - o , if (i) either the object was in Ξ i (t - -1
) and an update was triggered by u -1 , or (ii) the object was not cached in any of the m stations and an insertion in the inventory Ξ i was triggered. If m o > 0 (otherwise, the user is not covered), we write for i ∈ {1, . . . , m o }

P hit,i (u o ) = P (u -1 ∈ (S -1 , |t o -t -1 | < T C , j)) • • P(c j ∈ Ξ i (t - -1 )) + P( m =1 c j / ∈ Ξ (t - -1 ) ) .
For IRM traffic with PASTA, P(c j ∈ Ξ i (t - -1 )) = P hit,i (u -1 ), and is also independent of the time t and user position ψ, hence we can simply write P hit,i (j). Substitution in the above equation gives,

P hit,i (j) = P (u -1 ∈ (S -1 , |t o -t -1 | < T C , j)) • • P hit,i (j) + M m=1 p m 1 -p o P( m =1 {c j / ∈ Ξ }) . (7)
Solving the above over P hit,i (j) provides an expression for the hit probability of object c j at the cache of node x i . To find the characteristic time T C we solve the equation,

F j=1 P hit,i (j) = K, i ∈ {1, . . . , m o } . (8)
Finally, the total hit probability is equal to,

P hit = F j=1 a j M mo=0 p mo 1 -P( mo =1 {c j / ∈ Ξ }) . (9)
We note that P(

0 =1 {c j / ∈ Ξ }) = 1
, for m o = 0, in which case, the user surely misses the content.

The main difficulty when dealing with the general case, is that the hit probability of one cache depends on the hit probability of its neighbours and the neighbours of its neighbours. This is because the coverage area of each node has many sub-areas of multi-coverage by different BS subsets, which makes analysis neither easy, nor exact.

• multi-LRU-One (Che with CIA) Only the users falling in the Voronoi cell of a node can trigger an action of a. Update or b. Insertion at the cache of that node as long as they are covered. (Here we analyse this version for the Update phase, but other policy variations are possible without significant performance change). Then S o = S -1 = V(x i ) in [START_REF] Błaszczyszyn | Optimal geographic caching in cellular networks[END_REF]. The coverage cell can be smaller than the Voronoi cell, in which case only the users falling in the intersection of the two trigger cache actions. To avoid dealing with these special cases, we consider coverage cells which fully cover the related Voronoi cells, that is

|C i | > |V i |, ∀i.
There are the unknown probabilities P( m =1 {c j / ∈ Ξ }) and P( mo =1 {c j / ∈ Ξ }) that need to be calculated. Instead of directly trying to find a solution, we use a Cache Independence Approximation (CIA). Based on this, each cache performs single-LRU for the users that arrive within its Voronoi cell. The idea is that, since only the users in the Voronoi cell change the inventory of the related cache, the influence of the neighbouring stations' traffic on the inventory of x i should be small. Then in [START_REF] Błaszczyszyn | Optimal geographic caching in cellular networks[END_REF] we forget the rest m -1 nodes and we replace

P( m =1 {c j / ∈ Ξ }) ≈ P(c j / ∈ Ξ i ), (CIA 1 ). (10)
Furthermore, the independence due to the CIA, has the result that, when the user is covered by m o stations, her/his hit probability is simply the product of hit probabilities of all these stations. The fact that the Voronoi cells of different stations do not overlap is further in favour of the approximation. Then, in

P( mo =1 {c j / ∈ Ξ }) ≈ (P(c j / ∈ Ξ i )) mo , (CIA 2 ). (9)
From the above, the hit probability of each object in Ξ i is,

P hit,i (j) = P (u -1 ∈ (S -1 ∈ V(x i ), |t o -t -1 | < T C , j)) • • [P hit,i (j) + P(c j / ∈ Ξ i )] IRM = 1 -e -aj λu|V|T C , i ∈ {1, . . . , m o } . ( 12
)
We used the fact that for IRM P hit,i (j) = 1 -P(c j / ∈ Ξ i ). The characteristic time is found by solving the equation

F j=1 (1 -e -aj λu|V|T C ) = K. (13)
The total hit probability, based on CIA, is,

P hit = F j=1 a j M mo=0 p mo (1 -P(c j / ∈ Ξ i ) mo ) (12) = F j=1 a j M mo=0 p mo 1 -e -aj λumo|V|T C . ( 14
)
Special case: For the PPP model of node positions, the Voronoi cell size is a random variable. We can use for simplicity of the expression the average size of a Voronoi cell, equal to |V| = λ -1 b , [START_REF] Baccelli | Stochastic Geometry and Wireless Networks[END_REF]. In the Boolean coverage model, |C| = πR 2 b . • multi-LRU-All (Che with CSA) In this case, users falling on any point inside the coverage cell of x i can trigger an action of update and insertion at its cache inventory Ξ i . This means that S o = S -1 = C i , for the hit probability expression in [START_REF] Błaszczyszyn | Optimal geographic caching in cellular networks[END_REF].

Again, the unknown probabilities P( m =1 {c j / ∈ Ξ }) and P( mo =1 {c j / ∈ Ξ }) need to be calculated. In this case, we use a different approximation, the Cache Similarity Approximation (CSA), which states that inventories of neighbouring caches have the same content. This is motivated by the fact that new content is simultaneously installed in all caches of nodes covering a user, when the user triggers insertion. The approximation is better, the larger the cache size K, because for large memories it takes more time for an object to be evicted after its insertion and similar content stays in all inventories. Then in [START_REF] Błaszczyszyn | Optimal geographic caching in cellular networks[END_REF],

P( m =1 {c j / ∈ Ξ }) ≈ P({c j / ∈ Ξ i }), (CSA 1 ). (15)
Interestingly, CSA 1 and CIA 1 give the same expression. However, in multi-LRU-All, we do not assume independence, but rather similarity. Then, since neighbouring caches have the same content, the total miss probability when a set of m o stations cover user u o is equal to the probability that no user with the same demand arrives within the total area of coverage during the characteristic time T C (otherwise the content is definitely in all caches, either because of a. Update or b. Insertion. Then, for IRM traffic,

P( mo =1 {c j / ∈ Ξ }) ≈ e -aj λu|Am o |T C , (CSA 2 ). (16)
In the above, the total area of coverage from the m o stations is denoted by A mo and its surface is equal to, The hit probability of each object in Ξ i is found by using CSA in [START_REF] Błaszczyszyn | Optimal geographic caching in cellular networks[END_REF], and we get

|A mo | = mo =1 C i , m o = 0, . . . , M. (17)
P hit,i (j) = P (u -1 ∈ (S -1 ∈ C i , |t o -t -1 | < T C , j)) • • [P hit,i (j) + P({c j / ∈ Ξ i })] IRM = 1 -e -aj λu|C|T C . (18)
We used the fact that for IRM P hit,i (j) = 1 -P(c j / ∈ Ξ i ). For the characteristic time, we solve the equation

F j=1 (1 -e -aj λu|C|T C ) = K. ( 19
)
The total hit probability, based on CSA, is

P hit (16) = F j=1 a j M mo=0 p mo 1 -e -aj λu|Am o |T C . ( 20
)
The difficulty in calculating the approximate hit probability for multi-LRU-All with the above formulas, is to obtain exact values for the total surface |A mo |. For the PPP special case, this surface is also a random variable, that we can approximate by its mean value for simplicity of the expressions. A method to approximate these quantities is given in V.A. (We refer, again, the reader to the Appendix for the two-cache network example.)

V. MULTI-LRU UNDER TEMPORAL LOCALITY TRAFFIC

Although the IRM offers tractability, it is not enough to describe real traffic aspects. In real networks new objects (never requested before) appear, while older ones become obsolete after some time. Furthermore, the popularity of a content does not remain constant but varies over time, and there is dependence between requests of the same object within some time window. All these characteristics are described by the term temporal locality [START_REF] Jin | Sources and characteristics of web temporal locality[END_REF], [START_REF] Traverso | Unravelling the impact of temporal and geographic locality in content caching systems[END_REF], [START_REF] Olmos | Catalog dynamics: Impact of content publishing and perishing on the performance of a LRU cache[END_REF] (see also [START_REF] Brodersen | YouTube around the world: geographic popularity of videos[END_REF] for space-locality). Generators of such traffic have been proposed in the literature [START_REF] Almeida | Characterizing reference locality in the WWW[END_REF]. A so-called Shot Noise Model (SNM) is presented in [START_REF] Traverso | Unravelling the impact of temporal and geographic locality in content caching systems[END_REF], [START_REF] Leonardi | Least recently used caches under the Shot Noise Model[END_REF], which we make use here as a basis of our own traffic model. Under SNM the demand process is a superposition of independent point processes (not necessarily homogeneous), one for each content.

A detailed description of the SNM variation in this work follows. F(t) is the catalogue (set) of active objects at time t, with cardinality F (t) := |F(t)|. The evolution of the catalogue size is a random process. We assume that the arrival of a new object c n coincides with the time of its first request t n . The time instants of these first requests (arrivals) are modelled as a homogeneous PPP Φ c on R with intensity λ c > 0 [ objects unit-time ]. Unit-time can be e.g. 1 day.

A pair of r.v.'s is related to each content as an independent mark on the arrival process: (a) The first r.v. denoted by T n is the n'th content's lifespan, which gives the length of time period during which it is requested by users, and after the period's end it becomes obsolete. We could allow for the realisation τ n to take infinite values but in such option the size of the catalogue would grow indefinitely, unless the popularity of different objects tends to zero fast enough. We let here τ n < ∞ so that the catalogue size F (t) fluctuates over time and remains finite. The time interval of an object is ∆t n := [t n , t n + τ n ). (b) The second r.v. attached to the object c n is the volume V n (with realisation v n ) i.e. the total number of requests during its life. The pair of values (τ n , v n ) per object is chosen independently of other objects and in the general case should be drawn from a joint probability distribution with a given density f (T,V ) (τ, v), where T and V are the generic variables. In general the two variables are dependent.

To simplify the traffic model it is assumed here that T and V are independent of each other, i.e. f (T,V ) (τ, v) = f T (τ )f V (v). This simplification has no obvious impact on the performance of the caching policies. Both lifespan and volume follow a Power-law, i.e both T and V are Pareto distributed [START_REF] Newman | Power laws, Pareto distributions and Zipf's law[END_REF]. The Pareto distribution in both cases has parameter β > 1 (for the expected value to be finite), and its p.d.f. is given by (here for V ) f V (v) = βV β min v β+1 . Its expected value depends on the values of β and V min through the expression E[V ] = βVmin β-1 . To guarantee V ∈ N + for the samples, we choose V min = 0.5 and we round to get discrete values. Sampling from a Pareto distribution, generates Zipf-like distributed sizes of objects due to the Power-law behaviour.

Having sampled (τ n , v n ) for a specific object arriving at t n , it remains to determine how these v n requests are positioned within ∆t n . To include additional attributes of temporal locality in the traffic model, we let requests be distributed according to a finite point process (given V < ∞) and more specifically a (non-homogeneous) binomial point process (BPP) Ψ n on R vn-1 with density function g n (t, t n , τ n ) over t,

Ψ n ∼ Binomial(∆t n , v n -1, g n (t, t n , τ n )). (21)
We randomly position only v n -1 requests, because the first request always coincides with the time of content arrival t n . The choice of the Binomial distribution further implies that requests take position independently of each other. Since g n (t, t n , τ n ) describes how each of the v n -1 requests is distributed within ∆t n according to the function's shape, the higher the value of g n for some t, the more probable it is that a request will appear at that point. The popularity shape is an important aspect of the model. For some c n it holds

g n (t, t n , τ n ) = 0 for t / ∈ ∆t n , (22)
and

tn+τn tn g n (t, t n , τ n )dt = 1. (23)
When the requests follow a homogeneous BPP for some c n with a given ∆t n , the shape function is uniform and takes the expression g n (t, t n , τ n ) = τ -1 n 1 {t∈∆tn} . For further shape options we refer the reader to [START_REF] Richier | Modelling View-count Dynamics in YouTube[END_REF]. In this reference work, for finite volume per object three shapes are proposed, namely (i) the logistic, (ii) the Gompertz, and (iii) the negative exponential 1 . Applying this to our traffic generator, when a new object arrives it is assigned a shape of index k with probability a k , the exact value of which is a tuneable parameter.

The spatial (geographic) aspect of traffic plays an important role in influencing the performance of the policies studied here. In our work requests are uniformly positioned on a finite 2D plane. However, the traffic model can be easily extended to incorporate spatial locality.

Based on the above description, characteristic quantities of the generated traffic can be derived.

-

Mean Catalogue Size E[F(t)].
Because of the stationarity of the arrival PPP the expected number of active contents (hence catalogue size) does not depend on time t ∈ R + ,

E[F(t)] = λ c P(V > 1)E[T ]. (24)
-Mean Total Number of Requests within [0, t] [days],

N req ([0, t]) = tλ c E[V ]. (25)
-Memory-to-Mean-Catalogue-Size-Ratio (MMCSR) where we omit P(V > 1), which is just a scaling constant,

ρ := K λ c E[T ] . (26)
Hit Upper Bound: Similarly to the IRM traffic, we can derive a (numerical) upper bound for the POP policies under traffic with temporal locality. We consider a scenario where popularities are estimated periodically. Specifically, at time instants t n = n∆t up , n ∈ Z, the caches are updated by some POP policy, using the estimated popularities during the time interval [t n -∆t es , t n ), i.e. ∆t es is the window of observation. Let F mK (t n ) be the set of the mK most requested objects in [t n -∆t es , t n ). Then the upper bound within the time interval [t n , t n + ∆t up ) is equal to,

P (P OP ) hit [t n , t n + ∆t up ) ≤ ∞ m=1 p m P(c ∈ F mK (t n )). (27)
The more often the algorithm updates the caches the better performance it achieves. But, considering that a cache update 1 By assuming that the lifespan of every content ends when it reaches its 1 -ε of its total views v i , τ i can be mapped to the curve parameter λ in [START_REF] Richier | Modelling View-count Dynamics in YouTube[END_REF], which parametrises the speed of change of a content's popularity. In this paper we chose ε = 0.02.

will use backhaul and computational resources by the controller, ∆t up cannot be too small. We fix ∆t up = 1 day, i.e. the caching policy runs every night when the request load is low [START_REF] Golrezaei | Femtocaching: Wireless video content delivery through distributed caching helpers[END_REF]. As far as ∆t es is concerned there is a "crisp" optimal choice. If it is too big, F mK (t n ) will possibly include outdated objects. On the other hand, small ∆t es can result in excluding even the most popular objects from F mK (t n ) because they have not been sufficiently requested. The bound in [START_REF] Leonardi | Least recently used caches under the Shot Noise Model[END_REF] (see [START_REF] Baccelli | Stochastic Geometry and Wireless Networks[END_REF]). We evaluate a Boolean coverage model so that every station covers a disc of radius R b ∈ [0. (see [START_REF] Baccelli | Stochastic Geometry and Wireless Networks[END_REF]). For the Boolean Lattice case, these are found by Monte Carlo simulations. Given the intensity, λ b = 0.5, there is a mapping from the Boolean radius R b to the number N BS , some values of which are given in Table II.

A. IRM traffic

Following the spatial IRM traffic model for the request arrivals, we consider a homogeneous space-time PPP with intensity λ u = 0.023 [m -2 sec -1 ], which is approximately equal to 80 [m -2 /hour -1 ] requests -a reasonable value for a busy corner in a city.

The content mark for each request is independently chosen from a catalogue of size F = 10, 000 objects. The popularities of these objects follow a Zipf distribution with parameter γ = 0.78 (unless otherwise stated). A cache memory of capacity K objects is considered available on each BS. The size K is defined as a proportion of the catalogue size, i.e. K/F = ρ, where α is called the Memory-to-Catalogue-Size Ratio (MCSR). (We use different notation than the MMCSR ρ for temporal locality in ( 26)).

When a user is covered by a station with the requested content in memory, the demand is considered a hit. At the end of the simulation of a large number of realisations for the BS and request point processes (this number chosen over 10,000) the total hit probability is approximated by the frequency of hits (number of hits over number of requests). In the simulations we take considerations over issues related to edge effects that arise from the finite window size.

1) Verification of the approximations: To verify the validity of the proposed approximations, we compare the analytic formulas derived in Section IV-B with the hit probability from simulations, for the Boolean PPP coverage model. For the memory size K, we consider two cases, (a) α = 0.05, hence K = 500 objects, and (b) α = 0.2, hence K = 2000 objects.

• multi-LRU-One: The total hit probability is evaluated numerically using [START_REF] Dehghan | On the complexity of optimal routing and content caching in heterogeneous networks[END_REF]. The characteristic time per cache is found by solving (13) by a fixed point method, where the individual hit probability of each object is given in [START_REF] Coffman | Operating Systems Theory[END_REF]. To guarantee that |C| > |V|, we need that πR

2 b > λ -1 b ⇒ R b > (πλ b ) -1/2 = 0.4. Since R b > 0.
6 in the evaluation, the condition should be satisfied. The comparison between approximate hit probability and simulations are shown in Fig. 2(a). The curves exhibit a very good match. The evaluation shows that the independence approximation (CIA) works very well in this general model with PPs.

• multi-LRU-All: The total hit probability is evaluated numerically using [START_REF] Giovanidis | Spatial Multi-LRU Caching for Wireless Networks with Coverage Overlaps[END_REF]. The characteristic time per cache is found by solving (19) using a fixed point method, where the individual hit probability of each object is given in [START_REF] Fricker | A versatile and accurate approximation for LRU cache performance[END_REF].

We provide a method to estimate the surfaces |A mo |, m o = 1, . . . , M for the Boolean/PPP case: A user u o has a distance R d,i from each one of the m o nodes x i that cover her/him. These distances are realisations of a random variable, whose expected value can be found equal to E[R d ] = 2R b /3, i.e. the user lies in expectation at 2R b /3 away from the center of each covering disc. Then we have:

i) The coverage cell size (for the Boolean model) is the disc surface, equal to

|A 1 | = |C| = πR 2 b . ii) When M → ∞, a disc having center the user u o and radius R M = R b + E[R d ] = 5R b /3 is (due to randomness of node positions) fully covered. So |A M | = |C|(5/3) 2 .
iii) For intermediate cases 1 < m o < M , the surface should be somewhere between the two extremes, and obviously the surface |A mo | should be monotone increasing with m o . We also expect that for low m o , the total area |A M | will be filling fast, whereas for larger ones, the change in surface should be small. For this we can use a function with exponential decrease for large m o , such as

|A mo | = |A M |(1 -e -moδ ), δ = -ln(1 -|A1| |A M | ). (28)
The comparison between approximate hit probability and simulations are shown in Fig. 2(b). The approximation and simulation curves seem to closely follow one another. For large values of the radius, the approximation curves seem to diverge from the simulations. This should be less a failure of the CSA approximation (which is shown to be accurate for the twocache network in the Appendix), but more possibly a failure of the above method to approximate well the surfaces |A mo |. More accurate values of |A mo | should exhibit a better fit.

2) Comparison of policies: Hit versus Coverage Number. In Fig. 3(a), 3(b) and 3(c) we evaluate the hit probabilities of the proposed multi-LRU policies over the expected number of covering stations. In the simulations the radius of the Boolean model is increased from R b = 0.6 to 2.25. The radius is mapped to the expected coverage number, as in Table II. In Fig. 3(a) transmission nodes are positioned as a PPP, while in Fig. 3(b), 3(c) on a Lattice. We compare the multi-LRU-One/All performance with different existing policies mentioned in this paper, like LFU, single-LRU, PBP [START_REF] Błaszczyszyn | Optimal geographic caching in cellular networks[END_REF] and GFI [START_REF] Golrezaei | Femtocaching: Wireless video content delivery through distributed caching helpers[END_REF], as well as the upper bound given in [START_REF] Araldo | Design and evaluation of costaware information centric routers[END_REF]. The parameter α is chosen equal to 1% in Fig. 3(a), 3(b) and 5% in Fig. 3(c). In both F = 10000, γ = 0.78.

As a reminder, the single-LRU policy is not influenced by multi-coverage. Each user can contact a single station, the one closest to the user. If the user request is cached in this memory, then there is a hit, otherwise the object is fetched from the core network and inserted to the station's cache.

From the three figures very interesting conclusions about the policies can be derived: (i) Even for small values of coverage overlap (expected coverage number) a considerable increase in hit probability is achieved by using the multi-LRU policies, compared to the single-LRU. For α = 1%, when N BS = 2, the multi-LRU-One is 42% (relative gain) above the single-LRU for Lattice placement and 35% for PPP placement. A further increase of N BS makes the gain even more apparent. For N BS = 3 the relative gains are 70% and 60%, respectively.

(ii) For every value of N BS the multi-LRU-One policy performs better that the multi-LRU-All, in all three figures. This is because, for stationary traffic, when the same object is inserted in all stations covering a user (case -All), a request falling in areas of overlap profits less by the diversity of content from the multiple covering stations.

(iii) From both figures, the difference in performance between POP {LFU, PBP, GFI} and POQ {multi-LRU-One/All, simple LRU} policies is evident. For IRM traffic, POP policies have greater performance by exploiting the "expensive" information of known object popularity, which is assumed constant over time. In a realistic environment however, where traffic patterns change with time, such policies will demand regular updates and are approximative, because they depend on estimations over the popularity values. On the other hand, the multi-LRU policies introduced here do not depend on such information. A related interesting remark is that, as the MCSR α increases, the difference between the two groups' performance decreases. This can be observed by comparing Fig. 3(c (iv) For N BS close to 1, a user can connect to approximately one station, and the performance of multi-LRU-One/All, and single-LRU coincide. The same applies for the group LFU, PBP and GFI. For N BS ≈ 1 these last three policies tend to cache the K most popular objects in each station. Hence, when a user connects to a single station then she/he gets the maximum hit probability and the upper bound also coincides.

(v) It is obvious that the two standard policies single-LRU and LFU exhibit constant performance as the multi coverage event increases, because the memory of each station is updated independently of the others and a user is served by at most one station.

(vi) GFI performs best among all policies, and its performance is very close to the upper bound. The latter is an indication that the upper bound is fairly tight. The good performance of the GFI comes at the cost of very high computational complexity for the memory allocations, as well as centralised implementation that requests considerable amount of information availability.

3) q-LRU: Fig. 3(d) plots the hit probability of q-multi-LRU-All policies for various values of q ∈ (0, 1]. As in the previous figures, γ = 0.78, F = 10, 000, λ b = 0.5 and stations are modelled by PPP and have memory K = 100.

When q = 1 = 100%, q-multi-LRU-All reduces to the multi-LRU-All policy. As q decreases, the performance of qmulti-LRU-All improves, but new content is inserted more rarely. In this sense, the good performance of q-multi-LRU-All with small q exploits the IRM characteristic of stationary traffic, and will converge to good performance after a long transient period. This is often not realistic for traffic that exhibits faster variations in popularity and catalogue content. 4) Zipf parameter γ: We provide plots for the hit probability versus this parameter in Fig. 3(e). Letting γ increase results in a popularity distribution where a small number of objects is considerably more popular than the rest of the catalogue. Eventually, hit probability will increase for both multi-LRU policies, because due to the Update phase, popular objects tend to be kept cached in memory once inserted and get hit more often. Furthermore, the relative difference P hit (multi-LRU -One)-P hit (multi-LRU -All) P hit (multi-LRU -All)

decreases as γ increases. This happens because for increasing γ unpopular objects have less influence on the hit probability.

5) Memory-to-Catalogue-Size Ratio MCSR α: Fig. 3(f) illustrates the behaviour of the three policies {multi-LRU-One, multi-LRU-All, PBP} when varying α (here a larger size catalogue of F = 20, 000 is used, in order to evaluate for very small values of the α = K/F ratio). The hit probability increases when the ratio α increases, and tends to 100% as the ratio tends to 1. Furthermore, the need for smart memory allocations is less important for large values of the ratio α = K/F because the sum popularity of files left outside the caches is not considerable. Thus, we reasonably see in the figure, that different policies tend to have the same performance for larger values of the ratio α.

B. Traffic with temporal locality

The evaluation up to this point has been restricted to IRM user (request) traffic, and it was observed in the simulation figures that the multi-LRU-One performs better than the multi-LRU-All. This is because IRM is stationary, so, by letting the simulations run for a long time period the performance of the multi-LRU-One can converge to high hit probabilities. This however is generally not true for traffic that exhibits temporal locality, like the model we introduce in Section V of our work (see also [START_REF] Traverso | Unravelling the impact of temporal and geographic locality in content caching systems[END_REF], [START_REF] Olmos | Catalog dynamics: Impact of content publishing and perishing on the performance of a LRU cache[END_REF]).

For the performance evaluation we consider N st = 20 stations placed on a square lattice in a rectangular window, and the Boolean coverage model. [months]. The popularity shape g i of content c i is chosen with probability a 1 = 0.06 as Logistic, a 2 = 0.38 as Gompertz and with a 3 = 0.56 as Exponential. Later we include the Uniform shape.

In each simulation, we keep some variables fixed and let others vary, to evaluate the policy performance and understand their influence. The variables to be varied are categorised into (1) network variables (mean coverage number N bs , cache size K), and (2) traffic variables (average request volume per content E[V ], mean lifespan E[T ], probability vector for the shape (a 1 , a 2 , a 3 )).

1) Network influence: To increase the hit probability, dataobjects should both: stay long-enough in each cache, and be inserted in as many caches as possible. But since storage space per station is limited, a trade-off arises, which is captured by the two variations of the multi-LRU policy (-One and -All). This trade-off is depicted in Fig. 4(a) for different values of the memory size. The larger the storage space, the longer it takes for an object to be evicted. So, for large memory the geographical expansion of an object is beneficial. This is shown for K = 5000 in which case multi-LRU-All surpasses multi-LRU-One. But for each K, there is a critical value of N bs after which the performance of the -All is less than -One, because after this value further increase of content diversity is at the cost of content variety. The smaller the cache size, the more valuable storage space becomes because an object stays less time in the cache before eviction. Hence, for smaller K -One shows better performance and exceeds the -All variation even for small values of multi-coverage N bs .

In Fig. 4(b) the performance of multi-LRU policies versus the CCSR ratio ρ (26) is illustrated. This ratio is equal to the mean number of memory slots per active content and is a measure of the system's storage capability, because the smaller it is than one, the less storage resources are available. Keeping the denominator of ρ constant, Fig. 4(b) shows the impact of the memory size on the policy performance. Obviously, hit probability increases with K, but for smaller K, the -One variation is preferable to the -All, as explained also previously. There is again a critical point in K after which the -All variation is preferable (for large storage). If the ratio ρ is further increased, the performance gains are diminishing for both variations, and saturation occurs.

2) Traffic influence: The qualitative impact of the mean lifespan value on the hit probability can be understood by reading Fig. 4(b) in the opposite direction of the x-axis, from right to left. Keeping the numerator constant, as ρ decreases E[T ] increases. This means that the same storage capacity serves a larger active catalogue size E[F]. Consequently the overall performance drops. Moreover, Fig. 4(b) illustrates that the hit probability improves as the average number of requests per content E[V ] increases. The reason is that for higher E[V ] a content put in storage is requested and hit more times.

In Fig. 4(c) each curve corresponds to a scenario where contents are assumed to follow only one particular popularity shape. Specifically, either the logistic, or the negative exponential, or the uniform shape is used. In the negative exponential shape popularity takes big values in a short time period and then drops abruptly. A steep popularity shape implies that consecutive requests of the same content appear close to each other in time. This makes more probable the event that the content is not evicted before its next request happens. With this in mind, it can be understood that the negative exponential can lead to higher hit probabilities than the uniform shape. Interestingly, for isolated caches the authors in [START_REF] Traverso | Unravelling the impact of temporal and geographic locality in content caching systems[END_REF], [START_REF] Olmos | Catalog dynamics: Impact of content publishing and perishing on the performance of a LRU cache[END_REF] state that the shape does not affect significantly the hit probability of LRU. In our model, this can be observed when N bs takes small values so every user can connect to at most one station, and this observation is confirmed in Fig 4(c). But as N bs increases and multi-coverage effects appear, the multi-LRU performance depends considerably on the correlation between requests of the same content, and thus the shape of the popularity curves.

P hit multi-LRU-One, E[V]=3.8 multi-LRU-All, E[V]=3.8 single-LRU, E[V]=3.8 multi-LRU-One, E[V]=2.1 multi-LRU-All, E[V]=2.1 single-LRU, E[V]=2.1 (b) Hit Prob. VS CCSR ρ (various E[V ]).
3) Comparison with the single-LRU: Under single-LRU a user can access only one (the closest in this work) station's memory even when covered by more than one. As a result hit performance is independent of N bs (provided coverage is enough so that a user is always covered by at least one station). Depriving the user of the ability to retrieve its content from all covering stations, strongly reduces the overall hit probability. In Fig. 4(b), where N bs = 2.4, both multi-LRU policies show relative gains compared to the single-LRU, for all values of ρ. The maximum gains reach 30% when E[V ] = 2.1 and 20% when E[V ] = 3.8.

4) Comparison with centralised Policies with periodic Popularity updates and prefetching (POP): Fig. 4(a) shows that even the upper bound in [START_REF] Leonardi | Least recently used caches under the Shot Noise Model[END_REF] for POP policies with estimated popularity input does not surpass the appropriate multi-LRU policy in performance, except maybe for a small range of N bs . For static IRM traffic, we saw in Fig. 3(a)-3(c) that multi-LRU performed lower than the centralised policies POP. But, under a temporal traffic model (which is also more realistic), the ability of multi-LRU policies to update at each request the caches, without the need to estimate the content popularities, results in a considerable performance boost.

VII. CONCLUSIONS

In this work we have introduced a novel family of spatial multi-LRU policies, which exploit multi-coverage events of wireless networks to increase the hit probability. Two main variations are investigated, the multi-LRU-One and the -All. Che-like approximations give results close to simulation values. The multi-LRU-One provides higher object diversity in neighbouring caches and performs better under IRM traffic. The multi-LRU-All instead, lets objects quickly spread geographically and makes them immediately available to many users. This variation is profitable for traffic with temporal locality. Hence, depending on the incoming traffic either policy can be recommended. Future work should explain more clearly how the performance of these policies is affected by the spatial and temporal locality characteristics of traffic.

APPENDIX

To understand how the Che-like approximations work for the multi-LRU policies, we analyse the simple network of two nodes x i , i ∈ {1, 2}, each one equipped with a cache of size K. Each node covers an entire area A ⊂ R 2 , so that all planar We apply the analysis of Section IV-B to this network model. Specifically, the formula for the hit probability of an object c j at cache Ξ i in [START_REF] Błaszczyszyn | Optimal geographic caching in cellular networks[END_REF], takes the expression (for i = {1, 2}), P hit,i (j)

IRM = P (u -1 ∈ (S -1 , |t o -t -1 | < T C , j)) • • [P hit,i (j) + P (c j / ∈ Ξ 1 ∩ c j / ∈ Ξ 2 )] . (29)
Solving the above over P hit,i (j) gives an expression for the hit probability of object c j at cache Ξ i . The characteristic time T C is found by solving the equation ( 8),

Finally, the total hit probability (9) takes both caches into account, and is equal to

P hit = F j=1 a j (1 -P (c j / ∈ Ξ 1 ∩ c j / ∈ Ξ 2 )) . (31)
• multi-LRU-One: In this case, S o = S -1 = V(x i ), in [START_REF] Naveen | On the interaction between Content Caching and Request Assignment in Cellular Cache Networks[END_REF]. Table III gives all pairs of inventory states that a user u o arriving at t - o sees, when the previous user u -1 asking for the same content arrived in cell (say) ψ -1 ∈ V(x 1 ) at some time t - -1 , such that |t o -t -1 | ≤ T C . We denote by logical 1 the fact that the object is in the cache and by 0 otherwise. From the table it is clear that user u -1 does not take any action on cache Ξ 2 , this is why, when 1 c j ∈ Ξ 2 (t - -1 ) = 1, we cannot know whether the content will remain in the cache till t - o , so we write 1 [c j ∈ Ξ 2 (t - o )] ∈ {0, 1}. There is the unknown probability P (c j = Ξ 1 ∩ c j = Ξ 2 ) = 1 -P (c j ∈ Ξ 1 ∪ c j ∈ Ξ 2 ). For multi-LRU-One, we observe that an insertion of an object is triggered when its request arrives but does not find the object inside any of the two caches. However, the insertion is done only in the closest cache and stays there for time T C . During this time, the same object cannot be inserted in the other cache, hence, {c j ∈ Ξ 1 } and {c j ∈ Ξ 2 } are mutually exclusive events. Then,

P (c j / ∈ Ξ 1 , c j / ∈ Ξ 2 ) = 1 -P (c j ∈ Ξ 1 ∪ c j ∈ Ξ 2 ) = 1 -2P hit,1 (j), (32)
where the last equality is due to the symmetry of our model and the IRM traffic. However, in more general cases of node placement and coverage, content exclusivity is not true, because only a small area of the coverage cell will overlap with one neighbour. Users in other areas of the cell will be covered by other neighbours that can trigger the insertion of the same object, anyway. Hence, this result is not of much use for the PP coverage models. For this reason we want to evaluate how the CIA approximation applies here. For the two-cache model, this means for Ξ 1 (or Ξ 2 ), P (c j / ∈ Ξ 1 ∩ c j / ∈ Ξ 2 ) = 1 -P hit,1 (j), (CIA 1 ).( 33)

We can then replace in ( 29) and [START_REF] Newman | Power laws, Pareto distributions and Zipf's law[END_REF] to get (for i ∈ {1, 2})

P hit,i (j) = 1 -e -aj λu|V|T C , (34)
and the area 2|V| = |A| is equal to the total coverage cell.

• multi-LRU-All: In this case, S -1 = S o = A in (29) , for the hit probability of node i.

To calculate the unknown probability P (c j / ∈ Ξ 1 ∩ c j / ∈ Ξ 2 ) we argue as follows. In the case of multi-LRU-All, an object cannot be inserted in cache 1 if not inserted also in cache 2 and the other way round. Based on the Che approximation, once the object is inserted it stays T C amount of time, before removed from each cache. Hence, the existence of an object in one cache implies the of the same object in the other. So, due to the model's symmetry

P (c j / ∈ Ξ 1 ∩ c j / ∈ Ξ 2 ) = 1 -P (c j ∈ Ξ 1 ∪ c j ∈ Ξ 2 ) = 1 -P hit,1 (j). (37)
This is simply the Cache Similarity Approximation (CSA), which for the two-cache network is exact! Then (29) gives, P hit,i (j) = 1 -e -aj λu|A|T C .

To find the characteristic time, we need to solve [START_REF] Newman | Power laws, Pareto distributions and Zipf's law[END_REF],

F j=1 P hit,i (j) = F j=1 1 -e -aj λu|A|T C = K. ( 39
)
The total hit probability is equal to,

P hit = F j=1 a j (1 -P (c j / ∈ Ξ 1 , c j / ∈ Ξ 2 )) (38)
= F j=1 a j (1 -e -aj λu|A|T C ).

(40)

An alternative way to calculate P (c j / ∈ Ξ 1 (t o ), c j / ∈ Ξ 2 (t o )) is the following. A user u o finds the two caches without object c j , if the previous user u -1 (at say S -1 = V(x 1 )) with the same demand, arrived either (i) at t - -1 : |t o -t -1 | > T C , so that whatever the state of the two caches Ξ 1 (t - -1 ), Ξ 2 (t - -1 ), the object c j is eventually removed, since more than T C elapsed till t o , or (ii) at |t o -t -1 | ≤ T C . In the second case all possible change of states for the two caches is shown in Table IV. From this, we note that, the object will always be found in at least one of the two caches at t o , so that the time difference can not be smaller than T C . Hence,

P (c j / ∈ Ξ 1 (t o ), c j / ∈ Ξ 2 (t o )) IRM = e -aj λu|A|T C . ( 41
)
The expressions in (41) and ( 38) are the same. The accuracy of the approximations in the two-cache network is shown in Fig. 5. The Che-CIA approximation for multi-LRU-One -although not accurate -performs reasonably well in the two-cache network. The Che-CSA approximation for the multi-LRU-All, is exact.

Fig. 1 .

 1 Fig. 1. A realisation of the introduced model for t = 0 and a window of size 10 × 10 [m 2 ]. In both subfigures, user arrivals are modelled by a PPP with λu = 0.6 [m -2 sec -1 ]. The users choose between two objects that have popularities a 1 = 0.65 (users with "o"), a 2 = 0.35 (users with "x"). The typical user is shown at the Cartesian origin (0, 0) (thicker "o"). (a) The transmitters (squares) are modelled by a PPP with λ b = 0.1 [m -2 ]. (b) The transmitters (squares) are modelled by a Square Lattice PP with η = λ -1/2 b = 1/ √ 0.1 [m]. In both figures, we assume the Boolean model for coverage, with R b = 2η/3 [m]. In this realisation, the typical user is covered by two cells in the PPP case and by a single one in the Lattice case.

  It holds |A 0 | = 0, for m o = 0. For the Boolean model |A 1 | = |C 1 | = πR 2 b , while the surface of A mo is a superposition of m o overlapping discs with equal radius R b .

  can be evaluated by Monte Carlo simulations. The optimum ∆t es [days] can be numerically determined. VI. SIMULATION AND COMPARISON For the simulations, BSs are placed within a rectangular window of size A × B = 12 × 12 [km 2 ]. After choosing the BS intensity λ b = 0.5 [km -2 ], their positions are chosen based on the type of network we want to analyse (PPP or Lattice). For PPP, a Poisson number of stations is simulated in each realisation and their positions are set uniformly inside the window. In the case of a Lattice network, the stations are put on a square grid with distance η = 1/ √ λ b = 1.4142 [km] from each other. In both types of networks, the average Voronoi size |V| = λ -1 b

  5, 3] [km] with surface |C| = πR 2 b . The larger the radius the stronger the multicoverage effects. The magnitude of coverage overlap can be described by the expected number of BSs covering a planar point, N BS = E[Number of covering stations] = ∞ m=1 mp m , where the p m are the coverage number probabilities for m stations, whose values depend on the node placement and coverage model. For the Boolean PPP case, the probabilities {p m } correspond to a Poisson r.v. with parameter ν := λ b πR 2 b

Fig. 2 .

 2 Fig.2. Verification of the approximations for the two multi-LRU policies.

  Hit Probability PPP/Boolean, α = 1%.

  Hit Probability Lattice/Boolean, α = 1%.

  Hit Probability Lattice/Boolean, α = 5%.

  multi-LRU-ALL multiLRU-ONE PBP (d) q-multi-LRU-All, Boolean/PPP, α = 1%. -ALL N BS =8 Multi-LRU-ONE N BS =2 Multi-LRU-ONE N BS =4 Multi-LRU-ONE N BS =8(e) Hit Probability over γ, PPP, α = 1%.

  -ALL, N BS =8 Multi-LRU-ONE, N BS =2 Multi-LRU-ONE, N BS =8 PBP, N BS =2 PBP, N BS =8(f) Hit Probability over ρ, PPP, γ = 0.78.

Fig. 3 .

 3 Fig. 3. IRM traffic. Hit Probability evaluation of the two multi-LRU policies and comparison with existing POP and POQ policies.

  ) to Fig. 3(b) (Lattice).

  If not mentioned otherwise, λ c = 2400 [objects/day], with expected request volume per content E[V ] = 2.1. The distribution lifespan p.d.f. is truncated Pareto, with T ∈ [τ min , τ max ] = [0.1, 96] [days], and E[T ] = 35. The overall duration of the simulations is 15

  -One, K=500 multi-LRU-All, K=500 multi-LRU-One, K=5000 multi-LRU-All, K=5000 Upper Bound Static, K=500 Upper Bound Static, K=5000 (a) Hit Prob. VS N bs (various cache-size K).

  -One, Uniform multi-LRU-All, Uniform multi-LRU-One, Logistic multi-LRU-All, Logistic multi-LRU-One, Exponential multi-LRU-All, Exponential (c) Hit Prob. VS N bs (different popularity shapes).

Fig. 4 .

 4 Fig. 4. Evaluation of the hit probability of multi-LRU policies for different system variables. Parameter values in (b) N bs = 2.4. In (c) K = 1500.

1 (Fig. 5 .

 15 Fig. 5. Che approximations for (a) multi-LRU-One with CIA and (b) multi-LRU-All with CSA, in the two-cache network. Hit probability versus MCSR a = K/F , F = 10, 000 objects, for different Zipf parameter γ.

F j=1 P

 j=1 hit,i (j) = K, i = {1, 2}.

1 -a j 1 -

 11 e -aj λu|V|T C = K.[START_REF] Sourlas | Storage planning and replica assignment in content-centric publish/subscribe networks[END_REF] For the total P hit probability, we should appropriately adapt the form in[START_REF] Olmos | Catalog dynamics: Impact of content publishing and perishing on the performance of a LRU cache[END_REF] to the CIA 2 approximation,P hit = F j=1 (P (c j / ∈ Ξ 1 )) 2 = F j=1 a j (1 -e -aj λu2|V|T C ),

TABLE I SYMBOLS

 I Φ bPoint Process of transmission nodes {x i } Φ b,P , Φ b,LPoisson and Lattice position of {x i } ΦuPoint Process of users marked by object {

TABLE II R

 II b TO N BS MAPPING: BOOLEAN PPP AND LATTICE (λ b = 0.5 km -2 ).

	Radius (R b ) [km] PPP (N BS ) Lattice (N BS )
	0.8	1	1.06
	1.13	2	2.12
	1.38	3	3.22
	1.60	4	4.21
	1.78	5	5.32
	1.95	6	6.42
	2.11	7	7.43
	2.26	8	8.44

TABLE IV MULTI

 IV -LRU-ALL: STATES AT t - -1 AND t -

						o
	Ξ 1 (t --1 ) Ξ 2 (t --1 )		Ξ 1 (t -o ) Ξ 2 (t -o )
	0	0	→	1	1	insert both
	0	1	→	0	1	update 2
	1	0	→	1	0	update 1
	1	1	→	1	1	update both

ACKNOWLEDGMENT

The authors kindly thank Jim Roberts (IRT-SystemX, IN-RIA) for helpful discussions that improved the current work.