Hui Zhao
email: hui.zhao@eurecom.fr

Antonio Bazco-Nogueras
email: antonio.bazco@imdea.org

Petros Elia
email: petros.elia@eurecom.fr

Coded Caching in Land Mobile Satellite Systems

We investigate the performance of coded caching in land mobile-satellite (LMS) systems, where a satellite station with full access to a content library serves K cache-aided land users. The promising gains that coded caching provides for the error-free shared-link Broadcast Channel are known to suffer in some low signal-to-noise ratio (SNR) scenarios. For this reason, we analyze to what extent the coded caching gains are preserved in LMS systems, which are governed by low-to-moderate SNR due to the long propagation distances. We model the satelliteterrestrial channels through the widely adopted Shadowed-Rician fading, and we show that the coded caching gains are partially preserved even in the low-SNR limit due to the existence of line-ofsight (LOS) components, which allows us to double the goodput of LMS communication at low SNR. These results illustrate the potential of coded caching in LMS systems and motivate further research to design adapted and practical coded caching schemes for LMS systems.

I. INTRODUCTION

One of the main challenges in current and future mobile networks is dealing with the ever-increasing demand of video content. Coded caching has arisen as a promising solution to handle this problem, since it has shown that caching modest amounts of information at the receivers can provide remarkable improvements in content delivery time. Coded caching capitalizes on the fact that this traffic considerably fluctuates throughout the day, and do so by storing (or caching) content at the end users beforehand during off-peak hours.

Coded caching was first proposed by Maddah-Ali and Niesen in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF], where they presented a scenario in which a transmitter, which has access to a library of N files, serves K users in an error-free shared-link Broadcast Channel (BC) where each user is endowed with a local memory (or cache) with capacity to store a fraction γ ∈ [0, 1] of the library content. In a first phase, these caches are filled during off-peak hours and, in a second phase, each user requests a file from the library. In order to deliver the content, the transmitter generates a common message by applying XOR operations to several messages, each one intended by a different user. Then, it sends this common message over the physical-layer channel to serve Kγ + 1 users, thereby enhancing the content delivery rate by a factor of Kγ +1 compared to uncoded caching with simple time-division multiplexing (TDM). It is worth noting that in such uncoded caching scheme every user caches a fraction γ of each file in the library. During the delivery phase, the transmitter sends the remaining content of the requested files one-by-one [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF]. We refer to the coded caching scheme presented in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] as the MN scheme and to the boost factor Kγ + 1 as the theoretical coded caching gain. Motivated by these promising gains, the implementation of coded caching in realistic wireless networks has attracted great interest, including works that analyze e.g. dense urban cells [START_REF] Zhao | Wireless coded caching with shared caches can overcome the near-far bottleneck[END_REF], cell-free networks [START_REF] Bayat | Achieving spatial scalability for coded caching via coded multipoint multicasting[END_REF], MIMO systems [START_REF] Ngo | Scalable content delivery with coded caching in multi-antenna fading channels[END_REF], [START_REF] Zhao | Multi-antenna coded caching analysis in finite SNR and finite subpacketization[END_REF], among others [START_REF] Vu | Edge-caching wireless networks: Performance analysis and optimization[END_REF], [START_REF] Jin | A new order-optimal decentralized coded caching scheme with good performance in the finite file size regime[END_REF].

Another interesting use case is land mobile-satellite (LMS) systems [START_REF] Lin | 5G from space: An overview of 3GPP non-terrestrial networks[END_REF], whose integration in wireless networks is very relevant due to their large service coverage, wide bandwidth range, and high throughput. Indeed, the use of this type of communications is rapidly growing in recent years [START_REF] Wang | Convergence of satellite and terrestrial networks: A comprehensive survey[END_REF]. LMS systems can provide persistent and low-cost services in the case where the terrestrial network connection is very weak or even unavailable, such as in the case of network disruptions, rural areas, civil aviation, or cruise ships. Furthermore, these systems might serve an enormous amount of users once they handle a bigger portion of the traffic, mainly due to their large coverage area. These characteristics motivate us to analyze the potential of coded caching in LMS systems. Some works that jointly consider satellite and cache-aided terrestrial networks can be found in [START_REF] Wu | A two-layer caching model for content delivery services in satellite-terrestrial networks[END_REF]- [START_REF] Wang | Overlay coded multicast for edge caching in 5G-satellite integrated networks[END_REF], which have mostly focused on uncoded caching. However, in practical scenarios we usually have that the user cache size is much smaller than the total size of the library (γ 1), which makes the gain of uncoded caching over the approach without caching insignificant [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF]. In contrast, coded caching provides a multiplicative multicasting gain of Kγ + 1 even though the caches cannot cooperate [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF].

Worst-User Bottleneck in Coded Caching:

There exists an important aspect that impacts the performance of coded caching in wireless scenarios, which is referred to as the worst-user bottleneck, and that results from the fact that the achievable rate in multicast transmissions is constrained by the user with the worst channel state among the Kγ + 1 simultaneously served users [START_REF] Jindal | Capacity limits of multiple antenna multicast[END_REF]. This bottleneck is unfortunately exacerbated as the signal-to-noise ratio (SNR) decreases. Indeed, the gain of XOR-based coded multicasting schemes (e.g., MN) has been shown to entirely vanish in the low-SNR limit over symmetric Rayleigh fading channels [START_REF] Ngo | Scalable content delivery with coded caching in multi-antenna fading channels[END_REF], [START_REF] Zhao | Resolving the worst-user bottleneck of coded caching: Exploiting finite file sizes[END_REF], [START_REF] Zhao | Wireless coded caching can overcome the worst-user bottleneck by exploiting finite file sizes[END_REF], where the content delivery rate of coded caching deteriorates down to the rate of uncoded caching with TDM.

The worst-user bottleneck may be particularly important in LMS systems because such systems tend to operate in the low-SNR scenario due to the long distances between the satellite and the terrestrial users. For example, the received SNR at a terrestrial user is typically below 10 dB in home TV broadcasts from geosynchronous (GEO) satellites with 36 MHz of bandwidth and several hundred of watts of power [START_REF]Space communication calculations[END_REF]. Yet, while this problem may be tragic for the implementation of coded caching in a variety of settings such as Rayleigh fading, we need to explore if the same conclusion holds in LMS systems, where the channel statistics are totally different from Rayleigh fading [START_REF] Abdi | A new simple model for land mobile satellite channels: first-and second-order statistics[END_REF] due to the existence of LOS components. In this paper, we consider Rician-Shadowed fading [START_REF] Abdi | A new simple model for land mobile satellite channels: first-and second-order statistics[END_REF] to model the satellite-terrestrial channel. Our main contributions can be summarized as follows:

• We analyze the goodput (which will be defined in ( 6)) of the seminal MN scheme for first time in LMS systems. We derive the analytical expression of the maximum achievable goodput and validate these results with numerical evaluations for several practical fading configurations. • Our analysis shows that the goodput gain of coded caching in practical low-SNR scenarios is maintained in LMS settings when the LOS components are not heavily obstructed, even in the low-SNR limit. This result allows us to double the achievable goodput at very low SNR just considering the seminal coded caching scheme, which is tailored to the high-SNR regime. This deviates from the results of previous works [START_REF] Ngo | Scalable content delivery with coded caching in multi-antenna fading channels[END_REF], [START_REF] Zhao | Wireless coded caching can overcome the worst-user bottleneck by exploiting finite file sizes[END_REF], which proved that this gain disappears at low SNR for Rayleigh fading, and shows that coded caching has the ability to operate in low-SNR-governed (i.e., below 10 dB) LMS systems.

II. SYSTEM MODEL

We consider a scenario in which a GEO satellite transmitter serves K terrestrial users. Each user requests a file from a content library composed of N files, each of size F bits. We denote the n-th file of the library by W n , such that the library is given by {W n } N n=1 . The broadcasting GEO satellite has full access to the library, 1 and each user has a local memory (or cache) of size M F bits which is filled with content from the library during off-peak hours. The ratio between the local memory size and the total size of the library is denoted by γ M N ∈ [0, 1] and is referred to as the normalized cache size of the local memory. This scenario is depicted in Fig. 1. We consider the MN coded caching scheme from [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF], which we will 1 This access can be either because all the content is stored at the satellite or because this satellite is connected to a terrestrial satellite gateway via a feeder link which can often sustain extremely high rates. This satellite gateway has a wired connection to the core network and thus access to the library. describe in Section II-B, such that as many as Kγ + 1 users (marked with the same color in Fig. 1) are simultaneously served via a satellite BC. In the following, we use | • | to denote the cardinality of a set or the magnitude of a complex number. We define [n] {1, 2, . . . , n} for any positive integer n, whereas [a, b] denotes the closed interval of real numbers. We also use exp(•) e (•) , where e is Euler's number.

A. Channel Model

In order to accurately describe the fluctuation of the signal envelope, we consider the widely adopted Rician-Shadowed fading [START_REF] Abdi | A new simple model for land mobile satellite channels: first-and second-order statistics[END_REF] to model the satellite-terrestrial channel, which can be nicely calibrated to capture both fixed and mobile land terminals, and which can be applied for all types of orbits and for a variety of frequency bands including S-band, L-band, Ku-band, and Ka-band [START_REF] An | On the performance of cache-enabled hybrid satellite-terrestrial relay networks[END_REF], [START_REF] Sharma | Performance analysis of overlay spectrum sharing in hybrid satellite-terrestrial systems with secondary network selection[END_REF], [START_REF] Pan | On HARQ schemes in satelliteterrestrial transmissions[END_REF]. We recall that the Rician-Shadowed fading model is calibrated by the following set of parameters: the average power of the scatter component, denoted by 2b, the average power of the LOS component, denoted by Ω, the amplitude of the random shadowing LOS component, denoted by Z, and m (E{Z 2 }) 2

Var{Z 2 } , which reflects the (average) obstruction of the LOS component (i.e., the blockage of the LOS by buildings, trees, hills, etc.) and where m = 0 stands for complete obstruction whereas m → ∞ corresponds to no obstruction [START_REF] Abdi | A new simple model for land mobile satellite channels: first-and second-order statistics[END_REF]. To facilitate the analysis, we assume the same channel statistics (i.e., same m, b and Ω) among the K users, which is reasonable when the users are uniformly distributed within a disk [START_REF] Pan | On HARQ schemes in satelliteterrestrial transmissions[END_REF]. We consider that the users are located within a disk of radius equal to several kilometers [START_REF] Zhao | Wireless coded caching with shared caches can overcome the near-far bottleneck[END_REF]. As the radius is negligible to the height of the GEO satellite, we assume that all the users have the same path-loss. Therefore, we consider statistically symmetric users.

GEO satellites are static with respect to an observer from Earth, which makes the Doppler spread negligible for static terrestrial users [START_REF] Sharma | Performance analysis of overlay spectrum sharing in hybrid satellite-terrestrial systems with secondary network selection[END_REF]. Thus, we assume that the coherence time is large, and we do not consider an ergodic channel. Instead, we assume that the channel experiences quasi-static fading, which generally comes about in the presence of longer coherence periods and shorter latency constraints, and models low-mobility scenarios which nicely capture coded-caching use-cases where slow users are consuming video content.

While the results hold for any generic Rician-Shadowed fading, in the numerical results we consider four fading scenarios that have been used for performance analysis of LMS systems, and which are obtained from [20, Table III]. Since we will refer to these cases thorough the document, we present them in Table I.

The probability density function (PDF) of the instantaneous channel power gain |h k |2 at user k ∈ [K] over Rician-Shadowed fading channels is given by (cf. [START_REF] Abdi | A new simple model for land mobile satellite channels: first-and second-order statistics[END_REF])

f |h k | 2 (x) = αe -βx 1 F 1 (m; 1; δx), x ≥ 0, (1)
where

α = 2bm 2bm+Ω m , β = 1 2b , δ = Ω 2b(2bm+Ω)
, and where 1 F 1 (•; •; •) denotes the confluent hypergeometric function of the first kind [START_REF] Gradshteyn | Table of integrals, series, and products[END_REF]. As a small difference in m reflects a similar (average) obstruction of the LOS component, we consider that m is a positive integer for mathematical tractability, which is a simplifying assumption that is widely adopted in many existing works [START_REF] An | On the performance of cache-enabled hybrid satellite-terrestrial relay networks[END_REF], [START_REF] Sharma | Performance analysis of overlay spectrum sharing in hybrid satellite-terrestrial systems with secondary network selection[END_REF]. Let us denote the normalized transmit power of the satellite as P t , and the power of the Additive White Gaussian Noise as N 0 . Therefore, the instantaneous SNR at user

k is SNR k Pt|h k | 2 N0 = ρ|h k | 2 , where ρ Pt N0
. By considering [24, Eq. ( 24)], we simplify the confluent hypergeometric function in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] for any positive integer m as

1 F 1 (m; 1; δx) = e δx m-1 i=0 m -1 i (δx) i i! . (2)
Hence, upon defining

ζ(i) m-1 i δ i i! , the PDF of SNR k = ρ|h k | 2 can
be simplified for any integer m ≥ 1 as (cf. [START_REF] Sharma | Performance analysis of overlay spectrum sharing in hybrid satellite-terrestrial systems with secondary network selection[END_REF])

f SNR k (x) = α m-1 i=0 ζ(i) ρ i+1 x i e -β-δ ρ x , x ≥ 0. (3)
Let Γ(•,•) denote the upper incomplete Gamma function [START_REF] Gradshteyn | Table of integrals, series, and products[END_REF].

By integrating the PDF of SNR k in (3), we can easily obtain the corresponding cumulative distribution function (CDF) as

F SNR k (x) = 1 -α m-1 i=0 ζ(i) (β -δ) i+1 Γ i + 1, β -δ ρ x . (4)

B. MN Coded Caching Scheme

We recall that the coded caching framework in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] consists of two distinct phases: the placement phase, in which the local cache of the users is filled, and which is carried out during offpeak hours before the actual demand of each user is revealed, and the delivery phase, in which each user requests a file from the library, and the transmitter serves these users while aiming at minimizing the total delivery time required to serve all users.

1) MN Placement phase: During the placement phase, each file W n is partitioned into K Kγ non-overlapping and equal-sized segments (subfiles), such that

W n → W T n : T ⊆ [K], |T | = Kγ . User k stores all the segments W T n such that k ∈ T , for any n ∈ [N ]. The content cached at user k, denoted by Z k , is hence given by Z k = {W T n : T ⊆ [K], |T | = Kγ, T k, ∀n ∈ [N ]}.
It follows that the total content cached at each user amounts to M F bits, which satisfies the local cache size constraint.

X G = k∈G W G\{k} d k
, where stands for the bit-wise XOR operator, and the superscript G\{k} implies that the segment transmitted to user k is the one stored at all other users in G. In the physical layer, X G is mapped into a common multicast 2 message which is then sent to the users in G via a BC.

After successfully receiving X G , user k can "cache out" the undesired messages in X G by using its locally-cached content, and thus it obtains the desired subfile W transmission stages, all the users obtain their demanded files. Note that even when Kγ is not an integer, the MN scheme can still achieve the coded caching gain Kγ + 1 by considering the memory-sharing strategy. We refer to [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] for more details about the MN scheme.

III. GOODPUT ANALYSIS

Let us consider that, in each transmission stage of the delivery phase of the MN scheme, the satellite adopts a constant transmission rate (C th ) -which will be optimized in Lemma 1 -to serve the corresponding served users in G. In this way, users do not require to feedback their channel state information to the satellite, which can be energy demanding for the users due to the long distances to the satellite. In this case, the main metric of interest is the goodput [START_REF] Wu | Robust rate, power and precoder adaptation for slow fading MIMO channels with noisy limited feedback[END_REF], which is one of the standard metrics for the performance evaluation of LMS systems over fading channels [START_REF] Liolis | An analytical unifying approach for outage capacity achieved in SIMO and MISO broadband satellite channel configurations[END_REF]. We assume that the channel state remains constant during a transmission stage and may independently change to other values in the next stage.

We analyze in the following the goodput (i.e., the rate reliably delivered to the users [START_REF] Wu | Robust rate, power and precoder adaptation for slow fading MIMO channels with noisy limited feedback[END_REF]) of the MN scheme. For a given transmission to a user-set G, the satellite delivers a common message to the users in G over the physical-layer channel. Then, the total instantaneous goodput is defined as C out |G|C th I ln (1 + SNR MN ) ≥ C th nats/s/Hz, (5) where I {•} denotes the indicator function, which, for claim A, takes the value I{A} = 1 if A is true and I{A} = 0 otherwise, and SNR MN min k∈G {SNR k }, since we need to guarantee the successful decoding at the user with the weakest link strength. In [START_REF] Zhao | Multi-antenna coded caching analysis in finite SNR and finite subpacketization[END_REF], the existence of the factor |G| = Kγ + 1 is due to the fact that |G| users are served at a time. Consequently, we consider the worst case of outage inasmuch as an outage event happens as long as a single user in G fails to decode this common message. To analyze the coded caching gain later, and in a similar way as in [START_REF] Ngo | Scalable content delivery with coded caching in multi-antenna fading channels[END_REF], we take the expectation of C out over channel states, which yields the (average) goodput as

C out = |G|C th E I ln (1 + SNR MN ) ≥ C th = |G|C th ∞ 0 I{ln(1 + x) ≥ C th }f SNRMN (x)dx = |G|C th P ln (1 + SNR MN ) ≥ C th , (6)
where f SNRMN (x) denotes the PDF of SNR MN . Note that C out is just a statistical mean of C out in [START_REF] Zhao | Multi-antenna coded caching analysis in finite SNR and finite subpacketization[END_REF], which should not be confused by the long-term goodput [START_REF] Ngo | Scalable content delivery with coded caching in multi-antenna fading channels[END_REF]. We present our first main result, which consists of closedform expressions for C out and the rate that maximizes C out .

Lemma 1. The average goodput of the MN scheme is given by

C out = |G|C th m-1 i=0 αζ(i) (β -δ) i+1 Γ i + 1, β -δ ρ e C th -1 |G| .
Further, the optimal C out is C out = max C th ∈C * th C out (C th ), where C * th is the set of solutions to the equation

C * th = m-1 i=0 ζ(i) (β-δ) i+1 Γ i + 1, β-δ ρ (e C * th -1) |G|e C * th m-1 i=0 ζ(i) ρ i+1 (e C * th -1) i exp -β-δ ρ (e C * th -1)
.

Proof. We can write [START_REF] Vu | Edge-caching wireless networks: Performance analysis and optimization[END_REF] as

C out = |G|C th P min k∈G {SNR k } ≥ e C th -1 = |G|C th 1 -F SNR k e C th -1 |G| . (7)
Then, we can apply ( 4) into ( 7) to obtain the expression of C out in Lemma 1.

To maximize the goodput over C th , we obtain the first derivative of C out with respect to C th . For the sake of readability, let us define

FSNR k (•) 1 -F SNR k (•)
, and θ e C th -1. Then, we have that

∂C out ∂C th = |G| FSNR k (θ) |G|-1 FSNR k (θ) -|G|C th f SNR k (θ)e C th . (8)
Since C out is a continuous function over C th ∈ (0, ∞), the maximum value will be in one of the extreme points. Thus, letting this first derivative be equal to 0 allows us to obtain C * th in Lemma 1 by using the PDF and CDF of SNR k .

A. Low SNR Analysis

Next, we analyze the low-SNR regime by allowing the SNR parameter to approach to zero. When ρ → 0, we can consider the fact that ln(1 + ρx) = ρx + o(x), where o(x) denotes that lim ρ→0 o(x)/x = 0, to write that the goodput in [START_REF] Vu | Edge-caching wireless networks: Performance analysis and optimization[END_REF] satisfies

C out = |G|C th P SNR MN ≥ C th + o(SNR MN ) (9) ρ→0 ≈ C out |G|C th 1 -F SNR k (C th ) |G| , ( 10
)
where C out is obtained by omitting the term o(SNR MN ) in ( 9), and where F SNR k (•) has been given in (4).

In the following, we present a simplified expression for the values of C th that maximize the goodput at low SNR.

Proposition 1. The extreme points C * th ∈ C * th that make the derivative of C out equal to zero can be expressed by

C * th = * |G|(β -δ) ρ, as ρ → 0, (11)
where * ∈ [1, m] is a root of the following function: Proof. The proof is relegated to the extended version of this work [START_REF] Zhao | Coded caching in land mobile satellite systems[END_REF] due to space constraints.

m-1 i=0 ζ(i) (β -δ) i+1 Γ i + 1, * |G| -exp - * |G| ( * ) i+1 |G| i = 0. (12)
Note that * is independent of ρ, and it can have at most m different values [START_REF] Zhao | Coded caching in land mobile satellite systems[END_REF]. Moreover, it follows that * = 1 for any scenario in which m = 1, e.g. FHS in Table I By using Proposition 1, we can obtain an expression for the optimal C out , shown in Lemma 2, and which reveals that the optimal C out is actually a linear function of ρ.

Lemma 2. The maximum goodput C * out in the low-SNR regime can be expressed by

C out = α |G| e β -δ |G|+1 L |G| m-1 -δ |G|(β -δ) ρ, (13)
where L • (•) denotes the Laguerre polynomial [START_REF] Gradshteyn | Table of integrals, series, and products[END_REF], and ∈ [1, m] maximizes C out among the (at most m) roots of [START_REF] Vu | Efficient 5G edge caching over satellite[END_REF].

Proof. For the roots of ( 12), we have the following identity:

m-1 i=0 ζ(i) (β -δ) i+1 Γ i + 1, |G| = β -δ exp - |G| m-1 i=0 ζ(i) (β -δ) i |G| i . (14)
Applying the identity [START_REF] Zhang | On the performance of hybrid satellite-terrestrial content delivery networks with non-orthogonal multiple access[END_REF] in F SNR k (x) (defined in ( 4)) and incorporating this to (10) yields [START_REF] An | On the performance of cache-enabled hybrid satellite-terrestrial relay networks[END_REF] after considering that m-1 i=0 m-1 i x). Note that, if m = 1, we have that = 1 and therefore

x i i! = L m-1 (-
C out = α |G| e(β -δ) |G|+1 ρ. (15)
Furthermore, when m = 1 and Ω = 0, we have α = β = 1 2b and δ = 0, which means that Rician-Shadowed fading is reduced to Rayleigh fading. The optimal goodput becomes

C out = α |G| eβ |G|+1 ρ = 2bρ e , (16)
where 2bρ is the average SNR received at each user. Comparing [START_REF] Jindal | Capacity limits of multiple antenna multicast[END_REF] to the average capacity at low SNR (which converges to the average SNR in the low-SNR limit) [START_REF] Zhao | Wireless coded caching can overcome the worst-user bottleneck by exploiting finite file sizes[END_REF], we can see that there is a penalty of 1/e in the optimal goodput over Rayleigh fading channels. Moreover, C out in ( 16) is independent of |G|, which leads to the same delivery performance as uncoded caching with TDM transmission at low SNR, and which is consistent with [START_REF] Zhao | Wireless coded caching can overcome the worst-user bottleneck by exploiting finite file sizes[END_REF]Prop. 2].

B. Coded Caching Gain Analysis

To measure the benefit of coded caching over uncoded caching with TDM at finite SNR, we make use of the effective coded caching gain [START_REF] Zhao | Wireless coded caching with shared caches can overcome the near-far bottleneck[END_REF], [START_REF] Zhao | Wireless coded caching can overcome the worst-user bottleneck by exploiting finite file sizes[END_REF], which is defined as the ratio of the maximum goodput achieved by the MN scheme over the maximum goodput achieved by uncoded caching with TDM. 3 Note that the latter corresponds to setting |G| = 1 in the MN scheme [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF]. Thus, the effective coded caching gain (∆) is

∆ max C th ≥0 C out (|G|, C th ) max C th ≥0 C out (|G| = 1, C th ) , (17)
where C out (|G|, C th ) is given in Lemma 1. The optimization of C out over C th can be solved by using Lemma 1. In the following, focus on the behavior of this effective gain at low SNR, which is presented in Corollary 1.

Corollary 1. In the low SNR limit, the effective coded caching gain of the MN scheme is given by

∆ ρ→0 = α β -δ |G|-1 ( ) |G|+1 e -L |G| m-1 - δ |G|(β-δ) ( 1 ) 2 e -1 L m-1 -1 δ β-δ , (18)
where 1 ∈ [1, m] maximizes C out for |G| = 1 among the (at most m) roots of [START_REF] Vu | Efficient 5G edge caching over satellite[END_REF].

Proof. The proof follows directly from considering Lemma 2 and the effective coded caching gain definition in [START_REF] Zhao | Resolving the worst-user bottleneck of coded caching: Exploiting finite file sizes[END_REF].

Note that for |G| ≤ 10 (which is a realistic setting [START_REF] Zhao | Wireless coded caching can overcome the worst-user bottleneck by exploiting finite file sizes[END_REF]), and for the four typical fading scenarios listed in Table I, we can directly take the numerical results of and 1 in Table II to evaluate the effective coded caching gain in the low-SNR limit, which will be also shown in Fig. 5.

For m = 1, such as in FHS, we have = 1 = 1, and ∆ in Corollary 1 can be simplified as ∆ = α β-δ |G|-1 = 1, which means that the MN scheme loses gains in the low-SNR limit when m = 1 (i.e., with heavy LOS obstruction).

IV. NUMERICAL RESULTS

In this section, we perform some numerical analysis to validate the correctness of the derived expressions and present some interesting comparisons. Every simulated result is averaged over 10 5 channel realizations. We consider the four channel fading scenarios listed in Table I.

First, we evaluate the goodput as a function of C th in Fig. 2. We can observe that the goodput has a single maximum, which 3 Unlike some existing uncoded caching schemes where the cache hit/miss probability is typically investigated by considering the statistics of the users' requests, in the MN coded caching framework every user caches some content of each file in the library. During the delivery phase, the transmitter sends the remaining content of the requested files that is not cached in the users [ can be found by applying Lemma 1. It is also worth noting that Lemma 2 (based on the simplified expression of Proposition 1) provides a very accurate result at low SNR. Fig. 3 plots the maximum goodput (optimized over C th ) versus ρ in the ILS, AS, OR and FHS scenarios. As mentioned in Lemma 2, the optimal goodput linearly grows with ρ at low SNR. For the same system settings as in Fig. 3, Fig. 4 shows the effective coded caching gain, and we can observe that the effective gain converges to a lower-bound as ρ decreases. However, the lower-bound depends on the fading scenario. Specifically, ILS has the largest effective coded caching gain in the low-SNR limit, followed by the figures for AS and OR, while the effective gain in FHS is the lowest (and equals 1). The reason is that ILS enjoys the lightest obstruction of the LOS component.

For the ILS scenario, the MN scheme almost doubles the goodput with respect to uncoded caching with TDM transmission even in the low-SNR limit. Note that this differs from the results on Rayleigh fading, where it has been shown that MN achieves no gain in the low-SNR limit [START_REF] Zhao | Resolving the worst-user bottleneck of coded caching: Exploiting finite file sizes[END_REF], [START_REF] Zhao | Wireless coded caching can overcome the worst-user bottleneck by exploiting finite file sizes[END_REF]. Moreover, except for the worst case (i.e., FHS), the MN scheme shows a significant boost effect over uncoded caching also for ρ ≤ 10 dB, which, by considering that E{|h k | 2 } = 2b + Ω, corresponds to an average SNR = ρE{|h k | 2 } of less than 10 dB in the AS case and than 1.3 dB in the FHS case Fig. 5 shows the effective coded caching gain in the low-SNR limit versus the theoretical coded caching gain |G| (which is only achieved in the high-SNR limit). We can see how the effective gain increases for every scenario except for FHS. Thus, in those cases, simultaneously serving more users from the single-antenna transmitter enhances the overall delivery performance. The steeper gain boost for the ILS and AS cases shows that the MN scheme (and coded caching) is advantageous mainly when the LOS component is not heavily obstructed.

V. CONCLUSION AND FUTURE WORK This work analyzes the goodput and the effective gain of coded caching in a LMS system where Rician-Shadowed fading is adopted to model the satellite-terrestrial channel. Our analysis shows that even the simplest coded caching scheme can double the goodput of LMS systems operating at very low SNR, despite the fact that such scheme is tailored for the high-SNR regime and suffers from the worst-user bottleneck. This implies that coded caching has the ability to operate in such (low-SNR governed) LMS systems. Satellite integration in beyond-5G networks, as well as satellite networks, are expected to be a relevant feature in the incoming communications developments. These results motivate further research on cache-aided LMS systems, e.g., by investigating the gain of more complex and adapted coded caching schemes to compensate the worst-user bottleneck for cases where the LOS component is heavily obstructed, but also by developing new schemes that adapt to the particular properties of LMS and other satellite systems.

Fig. 1 :

 1 Fig. 1: Schematic representation of the considered setting.

2 )

 2 MN Delivery phase: At the beginning of this phase, each user requests a different file W d k from the library, where d k ∈ [N ] denotes the index of the file demanded by user k ∈ [K]. The transmission is divided in different transmission stages. At each transmission stage, the transmitter simultaneously serves a unique set of Kγ + 1 users. Since there are K Kγ+1 different subsets of Kγ + 1 users in [K], the delivery phase consists of K Kγ+1 transmission stages, and at each stage the transmitter serves a different subset of users G ⊆ [K] of |G| = Kγ + 1 users. Specifically, for the transmission stage intended for a particular set of users G, the transmitted signal is designed as

  k ∈ G and k = k, have been stored in the cache of user k ∈ G. After K Kγ+1

Fig. 2 :

 2 Fig. 2: Goodput versus C th for |G| = 4 and ρ = -10 dB.

Fig. 3 :

 3 Fig. 3: Optimal goodput versus ρ for |G| = 5.

Fig. 4 :

 4 Fig. 4: Effective coded caching gain versus ρ for |G| = 5.

Fig. 5 :

 5 Fig. 5: Effective coded caching gain versus |G| as ρ → 0.

  This work is supported by the European Research Council under the EU Horizon 2020 research and innovation program/ERC grant agreement no. 725929 (ERC project DUALITY).

TABLE I :

 I Parameters in four typical fading scenarios

	Overall Results (OR)	5	0.251	0.278
	Average Shadowing (AS)	10	0.126	0.835
	Infrequent Light Shadowing (ILS)	20	0.158	1.29

Scenarios m b Ω Frequent Heavy Shadowing (FHS) 1 0.063 8.97 × 10 -4

TABLE II :

 II Numerical results of * in four fading scenarios

	*	Scenarios
			FHS	OR	AS	ILS
	|G|
	1		1	1.3783	2.7121	3.4088
	2		1	1.4342	3.4655	4.5529
	3		1	1.4586	4.0111	5.4215
	4		1	1.4723	4.4478	6.1422
	5		1	1.4812	4.8149	6.7665
	6		1	1.4874	5.1329	7.3215
	7		1	1.4919	5.4139	7.8236
	8		1	1.4954	5.6658	8.2836
	9		1	1.4982	5.8943	8.7090
	10	1	1.5005	6.1032	9.1054

  . Table II lists some numerical values of * for the four typical fading scenarios in Table I and for realistic values of the theoretical coded caching gain |G|. For all the cases in Table II, (12) has only a single (multiple) positive root. Therefore, if we use the values of * in Table II, the derived C * th in (11) is exactly the global maximum point for C out .

  1].

		0.14
					ILS, Simulation
		0.12			AS, Simulation
	Goodput [nats/s/Hz]	0.04 0.06 0.08 0.1			OR, Simulation FHS, Simulation Optimal Point in Lemma 1 Optimal Point in Lemma 2 2 4 6 ×10 -3
		0.02			0
					0	0.01	0.02	0.03
		0
		0	0.05	0.1	0.15	0.2	0.25	0.3
					C th [nats/s/Hz]

There exists a variety of schemes that handle the worst-user bottleneck of multicast transmission or the case with bounded number of subfiles in coded caching. We restrict ourselves to the standard MN scheme to provide simple but meaningful insights on the benefit of coded caching.


Adeel Malik
email: malik@eurecom.fr

Berksan Serbetci
email: serbetci@eurecom.fr

Petros Elia
email: elia@eurecom.fr

Stochastic Coded Caching with Optimized Shared-Cache Sizes and Reduced Subpacketization

Keywords: Coded caching, shared caches, heterogeneous networks, femtocaching

This work studies the K-user broadcast channel with Λ caches, when the association between users and caches is random, i.e., for the scenario where each user can appear within the coverage area of -and subsequently is assisted by -a specific cache based on a given probability distribution. Caches are subject to a cumulative memory constraint that is equal to t times the size of the library. We provide a scheme that consists of three phases: the storage allocation phase, the content placement phase, and the delivery phase, and show that an optimized storage allocation across the caches together with a modified uncoded cache placement and delivery strategy alleviates the adverse effect of cache-load imbalance by significantly reducing the multiplicative performance deterioration due to randomness. In a nutshell, our work provides a scheme that manages to substantially mitigate the impact of cache-load imbalance in stochastic networks, as well as -compared to the best known state-of-the-art -the well-known subpacketization bottleneck by showing its applicability in deterministic settings for which it achieves the same delivery time -which was proven to be close to optimal for bounded values of t -with an exponential reduction in the subpacketization.

I. INTRODUCTION

The ever-growing amounts of mobile data traffic have highlighted the need for innovative solutions that can provide service to an ever-increasing number of users while using restricted network bandwidth resources. Within this framework, cache-enabled wireless networks have emerged as a viable option that can transfigure the storage capabilities of the network nodes into a fresh and powerful resource.

The seminal work in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] introduced the concept of coded caching, and revealed that an unbounded number of cacheaided users having different content requests can be served simultaneously by the aid of multicasting transmissions even with a bounded amount of network resources. Key to this approach is a novel and carefully designed cache placement algorithm. This delivery speedup is referred to as the coding gain -or equivalently as the Degrees-of-Freedom (DoF)and it scales with the total storage capacity of the network. This same approach was shown to be information-theoretically optimal in [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF], [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF] for the shared-link broadcast channel. Fig. 1: An instance of a shared-cache network. Many follow-up works have been studied since then, including the study of coded caching in D2D networks [START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF], in subpacketization-constrained settings [START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF]- [START_REF] Shanmugam | Finite-length analysis of caching-aided coded multicasting[END_REF], in settings with arbitrary popularity distributions [START_REF] Niesen | Coded caching with nonuniform demands[END_REF]- [START_REF] Serbetci | Augmenting multiple-transmitter coded caching using popularity knowledge at the transmitters[END_REF], and in other settings as well [START_REF] Malik | Stochastic analysis of coded multicasting for shared caches networks[END_REF]- [START_REF] Wan | On the fundamental limits of fog-ran cache-aided networks with downlink and sidelink communications[END_REF].

A. Coded caching networks with shared caches

Even though coded caching offers massive gains for the shared-link broadcast channel, its applicability to more realistic settings requires further exploration. In the so-called shared-cache setting, different users are within the coverage area of different cache-aided base stations (or caches), and are forced to benefit from the same cache content stored in the cache that they are associated with. This shared-cache setting is of great importance, and it arguably represents a much more realistic scenario as having all users with their own caches dedicated to a certain content library is a fanciful assumption in practical wireless communication settings [START_REF] Parrinello | Fundamental limits of coded caching with multiple antennas, shared caches and uncoded prefetching[END_REF], [START_REF] Malik | Fundamental limits of stochastic shared-cache networks[END_REF]. Such realistic settings may include cache-enabled heterogeneous networks (HetNets), where a central transmitter (a base station, or a macrocell) needs to deliver content to a set of interfering users with the assistance of cache-enabled helper nodes (small base stations, or femtocells), where the cache content is available to all users (cost-free) within the coverage area of that node. An instance of a shared-cache network is shown in Figure 1.

An early work on this scenario can be found in [START_REF] Hachem | Coded caching for multi-level popularity and access[END_REF], where each helper node is serving an equal number of users. The work in [START_REF] Parrinello | Fundamental limits of coded caching with multiple antennas, shared caches and uncoded prefetching[END_REF] removed this assumption, and characterized the optimal (under the uncoded cache placement) worst-case delivery time for the case when an arbitrary number of users is assisted by each cache, and when the cache placement is agnostic to the user-to-cache association. Subsequently, the work in [START_REF] Malik | Fundamental limits of stochastic shared-cache networks[END_REF] extended the deterministic user-to-cache association setting in [START_REF] Parrinello | Fundamental limits of coded caching with multiple antennas, shared caches and uncoded prefetching[END_REF] to the stochastic network setting, and for the setting where the cache populations follow a given probability distribution. This work revealed the surprising fact that the cache-load imbalance could lead to the significant deterioration in coding gains. This same work also showed that a more balanced user-to-cache association performs better than the unbalanced one, leading to the fact that the multiplicative performance deterioration caused by the stochastic nature of the problem can be drastically reduced by carefully tuning the cache-load balance.

The work in [START_REF] Wan | On the fundamental limits of fog-ran cache-aided networks with downlink and sidelink communications[END_REF] proposed a novel coded placement strategy by assuming that user-to-cache association during the placement phase is known, and showed that exploiting this extra knowledge yields additional coding gains. In a similar context, the work in [START_REF] Parrinello | Coded caching with optimized shared-cache sizes[END_REF] optimized the cache sizes as a function of the number of users served by each cache, and then proposed a novel coded caching scheme that outperforms the optimal scheme in [START_REF] Parrinello | Fundamental limits of coded caching with multiple antennas, shared caches and uncoded prefetching[END_REF].

At this point, we need to highlight that there is a direct relation between the aforementioned shared-cache setting and the so-called subpacketization bottleneck. In order to achieve the originally promised theoretical coding gains [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF], each file in the content library must be partitioned into S unitsize subpackets, where S scales exponentially with number of cache states 1 . Subsequently, a subset of these subpackets is cached at different nodes depending on the cache-enabled device's cache state. The number of distinct cache states, denoted as Λ, is then subject to some physical limitations, i.e., a file cannot be partitioned into more subpackets than a certain threshold, hence forcing S to be less than some certain number, and inevitably forcing Λ to be less than a certain value. In a nutshell, Λ must be generally less than the total number of users since it is known that traditional coded caching techniques require file sizes that scale exponentially with Λ (cf. [START_REF] Lampiris | Adding transmitters dramatically boosts codedcaching gains for finite file sizes[END_REF], [START_REF] Shanmugam | Finite-length analysis of caching-aided coded multicasting[END_REF].). In broad terms, reducing the number of cache states leads to a reduction in the coding gain, hinting out that the subpacketization bottleneck is in fact a major factor on the performance.

In this work, we aim to exploit cache-size differences and optimize the individual cache sizes to mitigate the cache-load imbalance bottleneck in stochastic shared-cache networks. To do so, we propose a coded caching scheme that optimizes the individual cache sizes based on each cache's load statistics, subject to a given cumulative cache capacity. We characterize the performance of our scheme and numerically verify its effectiveness in substantially ameliorating the impact of cacheload imbalance on the coding gain. We also show that for a deterministic user-to-cache association setting, our scheme achieves the same state-of-the-art (SoA) delivery time as of [START_REF] Parrinello | Coded caching with optimized shared-cache sizes[END_REF] with a significant (exponential) reduction in subpacketization, thus making our scheme more suitable than [START_REF] Parrinello | Coded caching with optimized shared-cache sizes[END_REF] to apply in HetNets in the finite file size regime.

B. Notations

Throughout this paper, we use the notation [z] [1, 2, . . . , z], and we use Q\P to denote the set difference of P and Q, which is the set of elements in Q but not in P. We use X

[n] k {δ : δ ⊆ [n], |δ| = k} and we use δ(i) to denote the ith element of δ.

II. NETWORK SETTING

We consider a heterogeneous cache-aided network setting which consists of a base station (BS) having access to a library of N unit-sized files F = F 1 , F 2 , . . . , F N , as well as consists of Λ cache-enabled helper nodes (i.e., caches), and K receiving users. The BS delivers content via an error-free broadcast link of bounded capacity per unit of time to K users, with the assistance of helper nodes. We assume that users within the coverage area of a cache λ ∈ [Λ] have direct access to the content stored at that cache. We consider the scenario of non-uniform cache population intensities where the number of users served by each cache may not be identical. For any cache λ ∈ [Λ], let p λ be the probability that a user appears in the coverage area of this λth cache-enable helper node, and let p = [p 1 , p 2 , . . . , p Λ ] denote the cache population intensities vector, where λ∈[Λ] p λ = 1. Without loss of generality, we assume that

p 1 ≥ p 2 ≥ • • • ≥ p Λ . At any given instance, we denote V = [v 1 , v 2 , . . . , v Λ ]
to be the cache population vector, where v λ is the number of users having access to the content of cache λ ∈ [Λ], and we let V = Kp = [v 1 , v2 , . . . , vΛ ] be the expected cache population vector.

The size of each cache λ ∈ [Λ] is the design parameter M λ ∈ (0, N ] (measured in units of file), adhering to a cumulative sum cache-size constraint

Λ λ=1 M λ = M Σ . For any cache λ ∈ [Λ], we denote by γ λ M λ
N the normalized cache capacity, and subsequently we have the normalized cache capacity vector γ = [γ 1 , γ 2 , . . . , γ Λ ]. Consequently, the normalized cumulative cache-size constraint takes the form

Λ λ=1 γ λ = t M Σ N . (1)
The communication process consists of three phases; the storage allocation phase, the content placement phase and the delivery phase. The storage allocation phase involves allocating the cumulative cache capacity M Σ (or the normalized cumulative cache capacity t) to the caches subject to (1), a process that results in the aforementioned normalized cache capacity vector γ. The content placement phase involves the placement of a portion of library-content, Z λ , in each cache λ ∈ [Λ]respecting its allocated cache capacity γ λ -according to a certain placement strategy

Z = [Z 1 , Z 2 , . . . , Z Λ ].
We assume that the first two phases are aware of the cache population intensities p. However, these two phases are oblivious to the actual requests generated during the delivery phase. The delivery phase begins after each user k ∈ [K] appears within the coverage area of one of the caches, and requests a content file using the knowledge of the content stored at each cache Z λ ∈ Z, and the user-to-cache association, the BS delivers the content to the user.

F d k ∈ F,

A. Problem Definition

For a given normalized cache-size budget t, and cache population intensities vector p, our goal is to design a content placement strategy Z, and a delivery scheme for the system where a BS is serving K users with the help of Λ caches. Then our goal is to evaluate its performance in terms of the delivery time (delay), which corresponds to the time needed to complete the delivery of any request vector d, where the time scale is normalized such that a unit of time corresponds to the optimal amount of time needed to send a single file from the transmitter to the receiver, had there been no caching and no interference. Given the random nature of our problem where at any given instance of the problem we may experience a different cache population vector V, our measure of interest is the average delay

T (t) = E V [T (V)] = V∈V P (V)T (V), (2)
where T (V) is the time needed to complete the delivery of any request vector d corresponding to a specific cache population vector V, where V is the set of all possible cache population vectors, and where P (V) is the probability of observing the cache population vector V.

III. MAIN RESULT

In this section, we first present our main results on the performance of the stochastic network setting described in Section II. After doing so, we will also discuss the applicability as well as the efficacy of our proposed scheme for a deterministic shared cache setting studied in [START_REF] Parrinello | Coded caching with optimized shared-cache sizes[END_REF] by showing that it provides an exponential reduction in the subpacketization. Our first result is the characterization of the achievable delivery time T (V) for any cache population vector V. Crucial to this characterization is the greatest common divisor (GCD) of vector V, which we denote by α, and the partition of

V into a set B V = [V 1 , V 2 , . . . , V β V ] of β V = max i∈[Λ]
αvi vi vectors according to the partition algorithm presented in Algorithm 1. Each resulting partition vector

V j = [v j 1 , v j 2 , . . . , v j Λ ] will then satisfy v j λ ≤ vλ α , where j∈[β V ] v j λ = v λ , ∀λ ∈ [Λ].
Under the assumption of a random user-to-cache association with cache population intensities vector p such that the expected cache population vλ ∈ V is a non-negative integer for each cache λ = [Λ], the achievable delay is given in the following theorem.

Theorem 1. In the K-user, Λ-cache setting with a normalized cache budget t, and a random user-to-cache association with cache population intensities vector p, the delivery time for any cache population vector V

T (V) = j∈[β V ] τ ∈X [Λ] t+1 t+1 i=1 vτ(i) α - τ ∈X A j t+1 t+1 i=1 vτ(i) α -v j τ (i) τ ∈X [Λ] t t i=1 vτ(i) α (3)
is achievable if the expected cache population vector V is a non-negative integer vector, where A j ⊆ [Λ] is a subset of the set of caches, such that for each cache λ ∈ A j , vλ α > v j λ . Proof. The proof is deferred to Section IV.

With Theorem 1 in hand, we present our next result, which is the average delay T (t) corresponding to our stochastic network setting.

Theorem 2. In the K-user, Λ-cache setting with a normalized cache budget t, and a random user-to-cache association with cache population intensities vector p, the average delay of

T (t) = V∈V T (V)K! λ∈[Λ] v λ λ∈[Λ] p v λ λ (4)
is achievable if the expected cache population vector V is a non-negative integer vector.

Proof. From the fact that the probability distribution P (V) follows the well-known multinomial distribution with parameter p, we have

P (V) = K! λ∈[Λ] v λ λ∈[Λ] p v λ λ . (5)
Combining ( 3) with ( 5) allows us to obtain (4), which concludes the proof.

Next, we see the applicability of our scheme in a similar setting, but with a fixed user-to-cache association, which was initially studied in [START_REF] Parrinello | Coded caching with optimized shared-cache sizes[END_REF].

Corollary 1. In the K-user, Λ-cache setting with a normalized cache budget t, and a fixed user-to-cache association with cache population vector V, the proposed scheme in Section IV achieves the delivery time of

T ( V) = α τ ∈X [Λ] t+1 t+1 i=1 vτ(i) α τ ∈X [Λ] t t i=1 vτ(i) α , (6)
which is same as of [18, equation (11)] and it requires the subpacketization rate of

S = τ ∈X [Λ] t t j=1 vτ(j) α , (7)
which is α t times less than the subpacketization rate of [18, equation ( 7)].

Proof. The analysis of our scheme is given in Section IV. In particular, the proof is straightforward from [START_REF] Serbetci | Augmenting multiple-transmitter coded caching using popularity knowledge at the transmitters[END_REF] and [START_REF]Unselfish coded caching can yield unbounded gains over symmetrically selfish caching[END_REF].

Corollary 1 reveals the substantial benefits of our scheme compared to the SoA [START_REF] Parrinello | Coded caching with optimized shared-cache sizes[END_REF] as it achieves the same delivery time with a significantly reduced -with a factor of α t -subpacketization. This exponential reduction in subpacketization is a crucial contribution as the subpacketization is a major bottleneck in the applicability of coded caching schemes [START_REF] Lampiris | Adding transmitters dramatically boosts codedcaching gains for finite file sizes[END_REF], [START_REF] Malik | Fundamental limits of stochastic shared-cache networks[END_REF] especially in the finite file size regimes. To illustrate this gain, in Figure 2, we compare the required subpacketization of our scheme with the scheme in [START_REF] Parrinello | Coded caching with optimized shared-cache sizes[END_REF] for V = [START_REF] Niesen | Coded caching with nonuniform demands[END_REF][START_REF] Lampiris | Adding transmitters dramatically boosts codedcaching gains for finite file sizes[END_REF][START_REF] Lampiris | Adding transmitters dramatically boosts codedcaching gains for finite file sizes[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF][START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF][START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF].

We can see that even for a modest network consisting of an extremely small number of users, our scheme requires significantly less subpacketization.

Remark 1. An interesting observation of our scheme is that α can be treated as a trade-off parameter between the subpacketization and the delivery time. For example, when V = [20, 15, 15, 5, 5, 4], we have α = 1. However, if we associate one virtual user to the Λ-th cache, α increases from 1 to 5, thus, reducing the subpacketization by a factor of 5 t with a modest increase in the delivery time. We leave the study of this trade-off for future work.

IV. PLACEMENT AND DELIVERY

In this section, we present the proof of Theorem 1. We describe the content placement and delivery strategies that can achieve the delay of (3).

A. Content Placement

The content placement scheme is based on the idea of assigning more storage capacity to the caches with high population intensities. We denote V = [v 1 , v2 , . . . , vΛ ] as the base cache population vector, which is given as V V α , where α is the GCD of the elements in V. For a base cache population vector V, we assume that there are Λ Λ λ=1 vλ virtual caches such that each cache λ ∈ [Λ] consists of vλ virtual caches. We then use C = [1, 2, . . . , Λ] to denote the set of virtual caches, and

C λ = [v λ-1 + 1, . . . , vλ-1 + vλ ] (assuming v0 0) to denote the set of virtual caches that belongs to cache λ ∈ [Λ]. Let Q C t ⊆ X C t be the set of all possible t-tuples of C such that for each tuple τ ∈ Q C t , no two virtual caches i, j ∈ τ belong to the same cache λ ∈ [Λ]. Next, each content file F i ∈ F is divided into Q C
t subpackets, and labeled as

F i = F i τ τ ∈Q C t .
Then, the set of contents to be cached at each cache λ ∈ [Λ] is given by

Z λ = Z λ : λ ∈ C λ , (8)
where

Z λ = F i τ : F i τ ∈ F i , τ ∈ Q C t , λ ∈ τ, F i ∈ F . ( 9
)
From the fact that for each cache λ we have vλ virtual caches, we can conclude that for any t-tuple of caches τ ∈ X

[Λ] t there must be t i=1 vτ(i) t-tuples of virtual caches that belong to the set Q C t . Consequently, the number of t-tuples of C in the set Q C t is given as

Q C t = τ ∈X [Λ] t t j=1 vτ(j) , (10)
and the normalized cache capacity required at any cache λ ∈ [Λ] is given as

γ λ = |Z λ | N Q C t = τ ∈X [Λ] t :τ λ t j=1 vτ(j) τ ∈X [Λ] t t j=1 vτ(j) . ( 11
)
Thus, (11) yields our proposed storage allocation strategy. We can see that λ∈[Λ] γ λ = t, as for each τ ∈ Q C t , the corresponding subpackets F i τ : F i ∈ F are placed in t caches. Thus, the content placement strategy satisfies the total caching budget constraint (1).

Algorithm 1 Cache Population Vector Partition

Input: V and V Output: B V Initialization: α ← GCD( V), β V ← max i∈[Λ] αvi vi , B V ← φ for j from 1 to β V do for i from 1 to Λ do if v i > vi α v j i ← vi α , v i ← v i -vi α else v j i ← v i , v i ← 0 end if end for B V ← [B V , [v j 1 , v j 2 , . . . , v j Λ ]] end for

B. Content Delivery

We will consider the worst-case delivery scenario where each user requests a different file. Once the BS is notified of the cache population vector V and the corresponding request vector d, it commences delivery. We propose a delivery scheme that is completed in

β V = max i∈[Λ]
vi vi rounds, where the content is delivered to at most vλ users from each cache λ ∈ [Λ] in each round. We divide the cache population vector

V into a set of β V vectors B V = [V 1 , V 2 , . . . , V β V ] based on the procedure described in Algorithm 1, such that for all j ∈ [β V ], V j = [v j 1 , v i 2 , . . . , v j Λ ] satisfies v j λ ≤ vλ and j∈[β V ] v j λ = v λ for all λ ∈ [Λ].
In the following, we describe our delivery strategy for the two only possible cases after applying Algorithm 1.

Case 1: V j = V: In this case, the BS will serve Λ users based on the base cache population vector V. Let U = [u 1 , u 2 , . . . , u Λ] denote the set of indices of users that corresponds to V, and U λ = {u i } vλ-1 +v λ i=v λ-1 +1 be the set of users associated to cache λ ∈ [Λ] (assuming v0 = 0). The corresponding request vector is

d V = d u1 , d u2 , . . . , d u Λ . Let Q C t+1 ⊆ X C
t+1 be the set of all possible (t + 1)-tuples of C such that for each tuple τ ∈ Q C t+1 , no two virtual caches i, j ∈ τ belong to the same physical cache. Then, for each (t + 1)-tuple τ ∈ Q C t+1 , the BS transmits the following XOR:

Y τ = ⊕ λ∈τ F du λ τ \ λ . (12)
The structure of Y τ allows to serve t + 1 users simultaneously as each user can easily decode its required subpacket using the content Z λ of its associated cache λ ∈

[Λ]. Let Y = Y τ : τ ∈ Q C
t+1 denote the set of all transmissions. In order to completely serve the request vector d V corresponding to cache population vector V, the BS transmits

|Y| = Q C t+1 = τ ∈X [Λ] t+1 t+1 j=1
vτ(j) XORs in the set Y. Thus the corresponding transmission delay is given as

T ( V) = τ ∈X [Λ] t+1 t+1 i=1 vτ(i) τ ∈X [Λ] t t i=1 vτ(i) . ( 13
)
Case 2: V j v j λ < vλ for some λ ∈ [Λ]: The delivery scheme for this case is exactly the same as for the case when V j = V. However, the number of users to be served in this case is less than Λ, i.e., |U| < Λ. Hence, there may exists some subpackets in Y that does not serve any user, and the BS only transmits the subpacket Y τ ∈ Y if it serves at least one user. Let A j ⊆ [Λ] be the subset of caches such that for each cache λ ∈ A j , v j λ < vλ holds. Then, for any cache population vector V j , the total number of subpackets Y τ ∈ Y that will not serve any user is given by

τ ∈X A j t+1 t+1 i=1 (v τ (i) -v j τ (i) ). Consequently,
for any cache population vector V j v j λ ≤ vλ ∀ λ ∈ [Λ], the transmission delay T (V j ) is given as

T (V j ) = τ ∈X [Λ] t+1 t+1 i=1 vτ(i) - τ ∈X A j t+1 t+1 i=1 (v τ (i) -v j τ (i) ) τ ∈X [Λ] t t i=1 vτ(i) . (14)
Hence, the transmission delay T (V) corresponding to the cache population vector V is equal to [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF].

Example: Let us take the example of K = N = 10, Λ = 4, t = 2, and p = (0.4, 0.2, 0.2, 0.2). Then the expected cache population vector is V = [4, 2, 2, 2], and consequently V = [2, 1, 1, 1] (α = 2 for V). The set of virtual caches is C = [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF][START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF][START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF], where the virtual caches

C 1 = [1, 2], C 2 = [3], C 3 = [4]
, and C 4 = [START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF] belong to the caches 1, 2, 3, and 4 respectively. Then we have nine 2-tuples in the set [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF], [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF], [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF], (2, 3), [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF], [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF], [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF], [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF], [START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF]] and each file is divided into nine subpackets. The content placement at each cache is given as [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF], [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF], [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF], [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF][START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF], [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF], [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF] [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF], [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF][START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF], [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF], [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF] [START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF], [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF], [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF], [START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF]], i ∈ [N ] , [START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF], [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF], [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF], [START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF]], i ∈ [N ] . This placement leads to the normalized cache capacity allocation of γ = [ 6 9 , 4 9 , 4 9 , 4 9 ]. Now, let us move to the content delivery phase. Let us assume the case of V = [6, 2, 1, 1], where users 1 to 6 have access to cache 1 and request the content F 1 , F 2 , F 3 , F 4 , F 5 , and F 6 respectively, users 7 and 8 have access to cache 2 and request F 7 and F 8 respectively, user 9 has access to cache 3 and requests F 9 , and user 10 has access to cache 4 and requests F 10 . The BS partitions the cache population vector into the set of β V = 3 vectors, and transmits the content in 3 rounds. The partition of V based on Algorithm 1 leads to B V = [(2, 1, 1, 1), (2, 1, 0, 0), (2, 0, 0, 0)], and the corresponding demand vectors are d [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF][START_REF] Niesen | Coded caching with nonuniform demands[END_REF], and d V 3 = [START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF][START_REF] Lampiris | Adding transmitters dramatically boosts codedcaching gains for finite file sizes[END_REF]. In the first round of delivery, the BS serves user 1 and 2 from cache 1, user 7 from cache 2, user 9 from cache 3, and user 10 from cache 4. For this round, we have V 1 = V, thus, for the demand vector d V 1 = [1, 2, 7, 9, 10], the BS transmits the following seven subpackets based on set Q C t+1 = [ [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF][START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF], [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF][START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF], [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF], [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF][START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF], [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF][START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF], [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF], [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF][START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF]

Q C t = [(1,
Z 1 = F i τ : τ ∈ [(1,
], i ∈ [N ] , Z 2 = F i τ : τ ∈ [(1,
], i ∈ [N ] , Z 3 = F i τ : τ ∈ [(1,
Z 4 = F i τ : τ ∈ [(1,
V 1 = [1, 2, 7, 9, 10], d V 2 =
], Y 1,3,4 = F 1 3,4 ⊕ F 7 1,4 ⊕ F 9 1,3 , Y 1,3,5 = F 1 3,5 ⊕ F 7 1,5 ⊕ F 10 1,3 Y 1,4,5 = F 1 4,5 ⊕ F 9 1,5 ⊕ F 10 1,4 , Y 2,3,4 = F 2 3,4 ⊕ F 7 2,4 ⊕ F 9 2,3 Y 2,3,5 = F 2 3,5 ⊕ F 7 2,5 ⊕ F 10 2,3 , Y 2,4,5 = F 2 4,5 ⊕ F 9 2,5 ⊕ F 10 2,4
Y 3,4,5 = F 7 4,5 ⊕ F 9 3,5 ⊕ F 10 3,4 . After this round user 1, 2, 7, 9, and 10 can successfully decode their required files. Then, in the second round of delivery, the BS serves users 3 and 4 from cache 1 and user 8 from cache 2. For this round, we have . After this round users 3, 4, and 8 can successfully decode their required files. Next, in the final round of delivery, the BS serves users 5 and 6 from cache 1. For this round, we have [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF][START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF], and the demand vector d V 3 = [START_REF] Yan | On the placement delivery array design for centralized coded caching scheme[END_REF][START_REF] Lampiris | Adding transmitters dramatically boosts codedcaching gains for finite file sizes[END_REF]. We can see that subpacket Y 3,4,5 will not serve any user, thus, the BS transmits the following six subpackets based on set

V 2 = V, A 2 = [3, 4],
V 3 = V, A 3 = [2,
Q C t+1 \(3, 4, 5), Y 1,3,4 = F 5 3,4 , Y 1,3,5 = F 5 3,5 , Y 1,4,5 = F 5 4,5 Y 2,3,4 = F 6 3,4 , Y 2,3,5 = F 6 3,5 , Y 2,4,5 = F 6 4,5
. After this round users 5 and 6 can successfully decode their required files. This completes the content delivery phase, which results in a delivery time of T (V) = 20 9 .

V. NUMERICAL EVALUATION

We know from Theorem 2 that it is computationally expensive to numerically evaluate the exact average delay even for small system parameters. This is due to the fact that such evaluation would require the generation of the set V of all possible cache population vectors V, which corresponds to the so-called weak composition problem, and where the Fig. 4: Cache capacity allocations cardinality of V is known to grow exponentially with system parameters K and Λ. Instead, we proceed to numerically evaluate our results by using the sampling-based numerical (SBN) approximation method, where we generate a large set V 1 of randomly generated cache population vectors V based on cache population intensities p, and approximate T (t) as

T (t) ≈ 1 |V 1 | V∈V1 T (V), (15)
where T (V) is given in [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF]. Then, the corresponding approximate performance is evaluated by comparing it with the achievable average delay for the uniform cache size from [START_REF] Malik | Fundamental limits of stochastic shared-cache networks[END_REF], which is given as

T uni ≈ 1 |V 1 | V∈V1 Λ-t λ=1 L(λ) Λ-λ t Λ t , (16)
where L = sort(V) is the sorted (in descending order) version of the cache load vector V.

Figure 3 compares the SBN approximation from (15) (i.e., our non-uniform cache size (N-UCS) scheme) with the SBN approximation from (16) (i.e., uniform cache size (UCS) scheme [START_REF] Malik | Fundamental limits of stochastic shared-cache networks[END_REF]) for |V 1 | = 10000, K = 400, Λ = 10, and p = [0.2, 0.2, 0.15, 0.1, 0.1, 0.05, 0.05, 0.05, 0.05, 0.05], where V 1 is generated based on cache population intensities vector p. This figure highlights the significant gain that can be achieved by allocating the cache capacity according to the cache population intensities as our scheme significantly outperforms the uniform cache size based coded caching scheme. For the same parameter setup, Figure 4 compares the cache capacity allocations of our scheme (N-UCS) with uniform cache capacity allocations (UCS) for various capacity budgets t. This new figure illustrates how our scheme allocates cache capacity in proportion with cache population intensities.

VI. CONCLUSION

The work explored the coded caching problem in stochastic shared-cache networks, where each user can appear within the coverage area of one of Λ caches with a given probability, and in this context proposed a scheme that optimizes the storage allocation of caches under a cumulative cache-size constraint. The novel scheme alleviates the adverse effect of cacheload-imbalance by significantly ameliorating the detrimental performance deterioration due to randomness. Furthermore, for each and every instance of the coded caching problem, our scheme substantially alleviates -compared to the best known state-of-art -the well-known subpacketization bottleneck.

  The work is supported by the European Research Council under the EU Horizon 2020 research and innovation program / ERC grant agreement no. 725929 (project DUALITY).

  User (K) Helper Node (Λ) Cache BS BC-link Library (N )

Fig. 2 :

 2 Fig. 2: Comparison of the required subpacketization.

5 Y 1 , 4 , 5 = F 3 4 , 5 ,

 514545 and the demand vector d V 2 = [3, 4, 8]. Thus, the BS transmits the following seven subpackets based on set Q C t+1 , Y 2,4,5 = F 4 4,5 , Y 3,4,5 = F 8 4,5

Fig. 3 :

 3 Fig.3: T (t) from (15) (i.e., N-UCS) vs T uni from (16) (i.e., UCS).

When adopting the cache placement strategy in[START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] for Λ cache-enabled users, we refer the content to be placed in a single cache as a cache state.