arXiv Vanity renders academic papers from arXiv as responsive web pages so you don’t have to squint at a PDF. Read this paper on arXiv.org.

# Rate-Memory Trade-Off for Caching and Delivery of Correlated Sources

Parisa Hassanzadeh, Antonia M. Tulino, Jaime Llorca, Elza Erkip This work has been supported in part by NSF under grant #1619129, and in part by NYU WIRELESS.P. Hassanzadeh and E. Erkip are with the ECE Department of New York University, Brooklyn, NY. Email: {ph990, J. Llorca and A. Tulino are with Nokia Bell Labs, Holmdel, NJ, USA. Email: {jaime.llorca, A. Tulino is with the DIETI, University of Naples Federico II, Italy. Email:
###### Abstract

This paper studies the fundamental limits of content delivery in a cache-aided broadcast network for correlated content generated by a discrete memoryless source with arbitrary joint distribution. Each receiver is equipped with a cache of equal capacity, and the requested files are delivered over a shared error-free broadcast link. A class of achievable correlation-aware schemes based on a two-step source coding approach is proposed. Library files are first compressed, and then cached and delivered using a combination of correlation-unaware multiple-request cache-aided coded multicast schemes. The first step uses Gray-Wyner source coding to represent the library via private descriptions and descriptions that are common to more than one file. The second step then becomes a multiple-request caching problem, where the demand structure is dictated by the configuration of the compressed library, and it is interesting in its own right. The performance of the proposed two-step scheme is evaluated by comparing its achievable rate with a lower bound on the optimal peak and average rate-memory trade-offs in a two-file multiple-receiver network, and in a three-file two-receiver network. Specifically, in a network with two files and two receivers, the achievable rate matches the lower bound for a significant memory regime and it is within half of the conditional entropy of files for all other memory values. In the three-file two-receiver network, the two-step strategy achieves the lower bound for large cache capacities, and it is within half of the joint entropy of two of the sources conditioned on the third one for all other cache sizes.

Keywords: Caching, Coded Multicast, Gray-Wyner Network, Distributed Lossless Source Coding, Correlated Content Distribution

## I Introduction

Prefetching portions of popular content into cache memories distributed throughout the network in order to enable coded multicast transmissions useful for multiple receivers is regarded as a highly effective technique for reducing traffic load in wireless networks. The fundamental rate-memory trade-off in cache-aided broadcast networks with independent content has been studied in numerous works, including [1, 2, 3, 4], and more recently, with correlated content in [5, 6, 7, 8, 9, 10, 11, 12]. Exploiting content correlations becomes particularly critical as we move from static content distribution towards real-time delivery of rapidly changing personalized data (as in news updates, social networks, immersive video, augmented reality, etc.) in which exact content reuse is almost non-existent [13]. Such correlations are especially relevant among files of the same category, such as episodes of a TV show or same-sport recordings, which, even if personalized, may share common backgrounds and scene objects, and between multiple versions of dynamic data (e.g., news or social media updates).

The works in [5] and [6] consider a single-receiver single-cache multiple-file network with lossy reconstructions, and characterize the trade-offs between rate, cache capacity, and reconstruction distortions. The analysis in [5] also considers two receivers and one cache, in which again only local caching gains can be explored. The work in [6] models the caching problem in a way that resembles the Gray-Wyner network [14]. Our prior works in [7, 8, 9] focus on lossless reconstruction in a setting with an arbitrary number of files and receivers that allows exploring untapped global caching gains under correlated sources. A correlation-aware scheme is proposed in [7] and [8], in which content is cached according to both the popularity of files and their correlation with the rest of the library. Cached information is then used as references for the compression of requested files during the delivery phase. Alternatively, our work in [9] addresses the content dependency by first compressing the correlated library. A subset of the files, most representative of the library, are selected as references, referred to as I-files, and the remaining files are inter-compressed with respect to the selected files and referred to as P-files. This results in a compressed library where each file is made up of an I-file and a P-file, leading to a multiple-request caching problem. Differently from previous multiple-request schemes [15, 16, 4, 17, 18], the demand in [9] has a specific structure dictated by the configuration of the resulting compressed library in terms of I-files and P-files.

The first information-theoretic characterization of the rate-memory trade-off in a cache-aided broadcast network with correlated content was studied in [10] for the setting of two files and two receivers, each equipped with a cache. This paper introduces an achievable two-step scheme that exploits content correlations by first jointly compressing the library files using the Gray-Wyner network [14], and then treating the compressed content as independent files. It is shown in [10] that this strategy is optimal for a large memory regime, while the gap to optimality is quantified for other memory values.

Building on the idea introduced in [9] and [10], concurrent work in [11] proposes a caching scheme for a network with arbitrary number of files and receivers, where the library has a specific correlation structure, i.e., each file is composed of multiple independent subfiles that are common among a fix set of files in the library. This, as in [9], leads to a multiple-request caching problem where the demand has a particular configuration dictated by the specific library structure.

All previously cited works provide achievable caching schemes without analytically quantifying the gap to optimality, except for the special case of two files and two receivers in [10]. In this paper, by focusing on lossless reconstructions, we extend the information-theoretic analysis of the broadcast caching network done in [10] to arbitrary number of receivers, each equipped with its own cache. Differently from [7, 8, 9] and [11], we characterize the peak and average rate-memory region for files generated by a discrete memoryless source with arbitrary joint distribution, and we propose a class of optimal or near-optimal two-step schemes, for which preliminary results were presented in [12]. Our main contributions are summarized as follows:

• We formulate the problem of efficient delivery of multiple correlated files over a broadcast caching network with arbitrary number of receivers via information-theoretic tools.

• We propose a class of correlation-aware two-step schemes, in which the files are first encoded based on the Gray-Wyner network [14], and in the second step, they are cached and delivered through a correlation-unaware multiple-request cache-aided coded multicast scheme. While most of the literature focuses on equal-length files, our multiple-request scheme in the second step is general enough to account for files compressed at different rates.

• We discuss the optimality of the proposed two-step scheme in a two-file and -receiver network by characterizing an upper bound on the peak and average rate-memory trade-offs for this class of schemes, and comparing it with a lower bound on the optimal rate-memory trade-offs derived in [19] using a cut-set argument on the corresponding cache-demand augmented graph [20]. We identify a set of operating points in the achievable Gray-Wyner region [14] for which the proposed two-step scheme is optimal over a range of cache capacities, and approximates the optimal rate in the two-file network within half of the conditional entropy for all cache sizes.

• We then extend the analysis to the three-file scenario since it captures the essence of the multiple-file case without involving the exponential complexity of the multiple-file Gray-Wyner network. We show that for two receivers the proposed scheme is optimal for high memory sizes and its gap to optimality is less than half of the joint entropy of two of the sources conditioned on the third source for other memory.

• As a means to designing an achievable scheme for the second step of the proposed Gray-Wyner-based methodology, we also present a novel near-optimal multiple-request caching scheme for a network with two receivers and three independent files, where each receiver requests two of the files. The proposed scheme uses coded cache placement to achieve optimality for cache capacities up to half of the library size.

The paper is organized as follows. Sec. II presents the information-theoretic problem formulation. In Sec. III, we introduce a class of two-step schemes based on the Gray-Wyner network. The multiple-request caching problem, arising from the Gray-Wyner network, is discussed in Sec. IV, and a multiple-request scheme for the two-file network is proposed and analyzed in detail in Sec. V. Sec. VI combines the multiple-request scheme proposed in Sec. V with the Gray-Wyner encoding step, and analyzes the optimality of the overall two-step scheme with respect to a lower bound on the rate-memory trade-off in a two-file network. Extensions to a three-file network are analyzed in Sec. VII. After numerically analyzing the rate-memory trade-off using an illustrative example, the paper is concluded in Sec. IX.

## Ii Network Model and Problem Formulation

We consider a broadcast caching network composed of one sender (e.g., base station) with access to a library of uniformly popular files generated by an -component discrete memoryless source (N-DMS). The N-DMS model consists of finite alphabets and a joint pmf over . For a block length , library file is represented by a sequence , where , and , is generated i.i.d. according distribution . The sender communicates with receivers, , over a shared error-free broadcast link. Each receiver is equipped with a cache of size bits, where denotes the (normalized) cache capacity.

We assume that the system operates in two phases: a caching phase and a delivery phase. During the caching phase, which takes place at off-peak hours when network resources are abundant, receiver caches are filled with functions of the library files, such that during the delivery phase, when receiver demands are revealed and resources are limited, the sender broadcasts the shortest possible codeword that allows each receiver to losslessy recover its requested file. We refer to the overall scheme, in which functions of the content are prefetched into receiver local caches, and are later used to reduce the delivery rate by transmitting coded versions of the requested files, as a cache-aided coded multicast scheme (CACM). A CACM scheme consists of the following components:

• Cache Encoder: During the caching phase, the cache encoder designs the cache content of receiver using a mapping

 fCrk:XF1×⋯×XFN→[1:2MF).

The cache configuration of receiver is denoted by .

• Multicast Encoder: During the delivery phase, each receiver requests a file from the library. The demand realization, denoted by , is revealed to the sender, where denotes the index of the file requested by receiver . The sender uses a fixed-to-variable mapping

 fM:D×[1:2MF)K×XF1×⋯×XFN→Y⋆\lx@notefootnoteWeuse$⋆$toindicatevariablelength.

to generate and transmit a multicast codeword over the shared link.

• Multicast Decoders: Each receiver uses a mapping

 gMrk:D×Y⋆×[1:2MF)→XFdrk

to recover its requested file, , using the received multicast codeword and its cache content as .

The worst-case probability of error of a CACM scheme is given by

 P(F)e=maxd∈DP⎛⎝⋃rk∈{1,…,K}{ˆXFdrk≠XFdrk}⎞⎠. (1)

In this paper, we consider two performance criteria:

• The peak multicast rate, , which corresponds to the worst-case demand,

 R(F)=maxd∈DE[L(Yd)]F, (2)

where denotes the length (in bits) of the multicast codeword , and the expectation is over the source distribution.

• The average multicast rate, , over all possible demands

 ¯R(F)=E[L(Yd)]F, (3)

where the expectation is over demands and source distribution.

###### Definition 1

A peak rate-memory pair is achievable if there exists a sequence of CACM schemes for cache capacity and increasing file size , such that , and .

###### Definition 2

The peak rate-memory region is the closure of the set of achievable peak rate-memory pairs and the optimal peak rate-memory function, , is

 R∗(M)=inf{R:(R,M)∈R∗}.
###### Definition 3

An average rate-memory pair is achievable if there exists a sequence of CACM schemes for cache capacity and increasing file size , such that , and .

###### Definition 4

The average rate-memory region is the closure of the set of achievable average rate-memory pairs and the optimal average rate-memory function, , is

 ¯R∗(M)=inf{R:(R,M)∈¯R∗}.

## Iii Gray-Wyner-Network-Based Two-Step Achievable Schemes

In this section, we propose a class of CACM schemes, based on a two-step lossless source coding setup, as depicted in Fig. 1. The first step involves lossless Gray-Wyner source coding [14], and the second step is a Multiple-Request CACM scheme.

The proposed two-step scheme exploits the correlation among the library content by first compressing the library using the Gray-Wyner network, described in detail in Sec. III-A, and depicted for two and three files in Fig. 2. The Gray-Wyner network represents the library using private descriptions and descriptions that are common to files for , thereby transforming the caching problem with correlated content and receivers requesting only one file, into a caching problem with a larger number of files where receivers require multiple descriptions. Note that this multiple-request caching problem has a specific class of demands. We assume that the multiple-request CACM scheme in the second step is agnostic to the correlation among the content generated by the Gray-Wyner network, i.e., the second step is correlation-unaware. The two steps are jointly designed to optimize the performance of the overall scheme, which is referred to as the Gray-Wyner Multiple-Request CACM (GW-MR) scheme. Before formally describing the GW-MR scheme, we briefly review the Gray-Wyner Network.

### Iii-a Gray-Wyner Network

The Gray-Wyner network was first introduced for two files in [14], in which a 2-DMS is represented by three descriptions , where is referred to as the common description, and and are the corresponding private descriptions as depicted in Fig. 2(a). The descriptions are such that file can be losslessly recovered from descriptions , and file can be losslessly recovered from descriptions , both asymptotically, as block length . In [14], Gray and Wyner fully characterized the rate region for lossless reconstruction of both files, which is restated in the following Theorem.

###### Theorem 1 (Gray-Wyner Rate Region)

The optimal rate region for the two-file Gray-Wyner network, , is

 SGW=cl{⋃{(ρ0,ρ1,ρ2):ρ0≥I(X1,X2;U),ρ1≥H(X1|U),ρ2≥H(X2|U)}}, (4)

where denotes the closure of set , and the union is over all choices of for some with .

The Gray-Wyner network can be extended to files such that the Gray-Wyner encoder observes a -DMS and communicates to decoder . The encoder is connected to the decoders through error-free links, such that there is a link connecting the encoder to any subset of the decoders. In particular, there is one common link connecting the encoder to all decoders, there are links common to any of the decoders, and finally, there are private links connecting the encoder to each decoder. For any nonempty set , description is communicated to all decoders . The Gray-Wyner rate region, , is represented by the set of all rate-tuples for the descriptions, for which file , can be losslessly reconstructed from the descriptions

 {Ws:s⊆{1,…,N},i∈s},

asymptotically, as . In general, files are encoded into descriptions, such that: i) of the descriptions contain information exclusive to only one file, and ii) the remaining descriptions comprise information common to more than one file. In this paper we will study in detail the three-file Gray-Wyner network depicted in Fig. 2. The encoded descriptions are such that222With an abuse of notation, the subscripts of and denote sets.

• ,

• , , ,

• , , ,

and the Gray-Wyner rate region is represented by the set of all rate-tuples

 ϱ=(ρ123,ρ12,ρ13,ρ23,ρ1,ρ2,ρ3), (5)

for which file , , can be losslessly reconstructed from the descriptions with asymptotically, as .

While the rate region of the -file Gray-Wyner network has been studied in a number of papers [21, 22, 23], the optimal characterization for general sources is not known.

### Iii-B Gray-Wyner Multiple-Request CACM Scheme

The proposed class of two-step schemes consists of:

• Gray-Wyner Encoder: Given the library , the Gray-Wyner encoder at the sender computes descriptions , where is the set of all nonempty subsets of , using a mapping

 fGW:XF1×⋯×XFN→∏s∈S[1:2FρS),

for .

• Multiple-Request Cache Encoder: Given the compressed descriptions, the correlation-unaware cache encoder at the sender computes the cache content at receiver , as .

• Multiple-Request Multicast Encoder: For any demand realization revealed to the sender, the correlation-unaware multicast encoder generates and transmits the multicast codeword .

• Multiple-Request Multicast Decoder: Receiver decodes the descriptions corresponding to its requested file as

 {ˆWs:s∈Sdrk}=gMMRrk(d,Yd,ZrK),

where .

• Gray-Wyner Decoder: Receiver decodes its requested file using the descriptions recovered by the multicast decoder, as , via the Gray-Wyner decoder

 gGWrk:∏s∈Sdrk[1:2Fρs)→XFdrk.

The Gray-Wyner encoder and decoder correspond to the first step, namely the encoder and decoder of the Gray-Wyner network, and the multiple-request cache encoder, multiple-request multicast encoder, and multiple-request multicast decoder comprise the second multiple-request CACM (MR) step of the proposed two-step scheme.

Note that the performance of the class of schemes described above depends on the operating point of the Gray-Wyner network . For a given , the performance of the overall two-step scheme is dictated by the peak and average multicast rates of the MR scheme, which similar to (2) and (3), are defined as

 R(F)MR(ϱ)=maxd∈DE[L(Yd)]F, (6) ¯R(F)MR(ϱ)=E[L(Yd)]F, (7)

respectively.

Furthermore, the worst-case probability of error of the class of two-step schemes depends on the probability of error of the Gray-Wyner source coding step and the probability of error of the multiple-request CACM step. Since , and is a Gray-Wyner description of with , it is guaranteed that Gray-Wyner decoding is asymptotically lossless with . Hence, the probability of error of a two-step scheme is approximately upper bounded by the probability of error of the MR scheme, given by

 P(F)e,MR=maxd∈DP⎛⎝⋃rk∈{1,…,K}{ˆWs≠Ws,∀s∈Sdrk}⎞⎠.
###### Definition 5

For a given rate-tuple , an MR peak rate-memory pair is achievable if there exists a sequence of MR schemes with rate , for cache capacity and increasing file size , such that , and .

###### Definition 6

For a given rate-tuple , the MR peak rate-memory region is the closure of the set of achievable MR peak rate-memory pairs , and the MR peak rate-memory function is defined as

 R∗MR(M,ϱ)=inf{R:(R,M)∈R∗MR(ϱ)}.

In the class of two-step schemes, we refer to the scheme operating at the rate-tuple that minimizes the MR peak rate-memory function as the GW-MR scheme. The peak rate-memory pair achieved by this scheme is the GW-MR peak rate-memory function defined below.

###### Definition 7

The GW-MR peak rate-memory function is given by

 R∗GW-MR(M)=inf{R∗MR(M,ϱ):ϱ∈SGW}.

In line with Definitions 5-7, for the average rate criterion we have the following.

###### Definition 8

For a given rate-tuple , an MR average rate-memory pair is achievable if there exists a sequence of MR schemes, with rate , for cache capacity and increasing file size , such that , and .

###### Definition 9

For a given rate-tuple , the MR average rate-memory region is the closure of the set of achievable MR average rate-memory pairs , and the MR average rate-memory function is defined as

 ¯R∗MR(M,ϱ)=inf{R:(R,M)∈¯R∗MR(ϱ)}.
###### Definition 10

The GW-MR average rate-memory function is given by

 ¯R∗GW-MR(M)=inf{¯R∗MR(M,ϱ):ϱ∈SGW}.

In the remainder of this paper, we first present the MR scheme in the second step for a general setting (Sec. IV), and then describe and analyze the performance of the overall GW-MR scheme for the case of two files and receivers (Secs. V and VI), and for the case of three files and two receivers (Sec. VII).

## Iv Multiple-Request CACM Scheme

In this section, we focus on the second step of the GW-MR scheme depicted in Fig. 1, namely the MR scheme when the Gray-Wyner network operates at .

Recall that the Gray-Wyner network converts the -file library into descriptions, each required for the lossless reconstruction of a set of the files in the original library. The MR scheme arranges the descriptions generated by the Gray-Wyner encoder into groups, , referred to as sublibraries. Sublibrary contains the descriptions that are common to exactly files. We refer to sublibrary as the common-to-all sublibrary, and to , which contains all the private descriptions, as the private sublibrary. The MR scheme accounts for populating the receiver caches with content from sublibraries and serving the demand realizations placed in the original library, which translate into a new class of demands from the compressed sublibraries. More specifically, each receiver demand corresponds to a demand for a set of descriptions from each of the sublibraries (hence the term multiple-request), such that the original library file requested by receiver maps to descriptions from sublibrary , . Even though receivers request single files from the original library independently and according to a uniform demand distribution, the Gray-Wyner encoding process leads to a non-uniform multiple-request demand for descriptions (files) from the compressed sublibraries.

Our proposed MR scheme treats each sublibrary independently during both caching and delivery phases. Specifically, the descriptions from each sublibrary are cached and delivered as follows: i) the description in the common-to-all sublibrary , which is required for the reconstruction of all files, and hence requested by all receivers, is cached according to the Least Frequently Used (LFU)333LFU is a local caching policy that, in the setting of this paper, leads to all receivers caching the same part of the file. strategy and delivered through naive (uncoded) multicasting, ii) sublibrary is cached and delivered according to any single-request correlation-unaware CACM scheme (such as [24, 25, 26] for unequal-length descriptions, and [1, 27, 28, 29, 30, 31, 32] for equal-length descriptions), and iii) sublibrary , is cached and delivered according to any correlation-unaware CACM scheme in which each receiver requests descriptions. Schemes where each receiver requests more than one file have been analyzed in previous works, e.g., [15, 16, 4, 17, 18]. However, in addition to being limited to settings with equal-length files, they have been designed for arbitrary demand combinations and could therefore be suboptimal for the specific class of demands considered in our MR scheme. One of the challenges addressed in the next sections is the design of near-optimal schemes for delivering the descriptions requested by each receiver from sublibrary , . Since the ultimate goal is to characterize the performance of the overall two-step GW-MR scheme, and the optimal Gray-Wyner rate region is only known for two files [14], in the following sections, we first describe the proposed MR scheme and analyze the performance of the associated GW-MR scheme for the case of two files and receivers in Secs. V and VI, respectively. In addition, to illustrate how extensions to more files could be done, we focus on the setting with three files and two receivers in Sec. VII.

It is worth noticing that the setting of our MR scheme, where the descriptions generated by the Gray-Wyner network are modeled as independent subfiles common to a fix set of files in the original library, is a generalization of the problem considered in [11], where, differently from our setting, subfiles are assumed to have equal length. Our results, for two files and receivers, and for three files and two receivers, if specialized to equal-length descriptions (subfiles) are shown to yield optimal or near-optimal schemes for the problem formulation studied in [11].

## V Multiple-Request CACM Scheme for Two Files and K Receivers

This section describes in more detail the MR scheme introduced in the previous section for a network with two files and receivers. Let denote the operating point of the Gray-Wyner network, where denotes the rate of the common description , and and denote the rate of the private descriptions and , respectively. As described in Sec. IV, the MR scheme for two files arranges the three descriptions generated by the Gray-Wyner network into a common-to-all (or simply common) sublibrary , and a private sublibrary . Each receiver demand corresponds to requesting two descriptions: one from the common sublibrary , and one from the private sublibrary . The specific caching and delivery strategies adopted for each sublibrary are provided in Sec. V-B.

In order to analyze the performance of the proposed MR scheme we also provide lower bounds on the MR peak and average rate-memory functions in Sec. V-A, and compare the achievable rates of the proposed MR scheme with these lower bounds in Sec. V-C.

### V-a Lower Bounds on R∗MR(M,ϱ) and ¯R∗MR(M,ϱ)

###### Theorem 2

In the two-file -receiver network, for a given cache capacity and rate-tuple , a lower bound on , the MR peak rate-memory function, is given by

 RLBMR(M,ϱ)=inf{R: R≥ρ0+ρ1+ρ2−2M, R≥ρ0+12(ρ1+ρ2+max{ρ1,ρ2})−M,

A lower bound on , the MR average rate-memory function, is given by

 ¯RLBMR(M,ϱ)=inf{R: R≥ρ0+(1−12K)(ρ1+ρ2)−2(1−12K)M, R≥34ρ0+12(ρ1+ρ2)+14max{ρ1,ρ2}−34M, R≥ρ0+34(ρ1+ρ2)−M,
###### Proof 1

The proof follows from the more general results presented in Theorem 8 in Sec. VI-A. By setting and , the above results are readily obtained.

### V-B Proposed MR Scheme

As described in Sec. IV, the proposed MR scheme for two files treats the descriptions in and as independent content and operates as follows: the cache capacity is optimally divided among the two sublibraries, caching is done independently from each sublibrary, and the content requested from each sublibrary is delivered independently, i.e., with no further coding across them. While the common description in is cached according to the LFU strategy and delivered through uncoded multicasting, the private descriptions in can be cached and delivered according to any correlation-unaware CACM scheme available in literature (e.g. [1, 27, 28, 29, 30, 31, 32]), properly generalized to a setting with unequal-length files. In the following, for a given generalized correlation-unaware CACM scheme adopted for sublibrary , we describe how to optimally allocate the memory to each sublibrary, and we then characterize the peak and average rate achieved by the corresponding MR scheme.

Let and denote the lower convex envelope of the peak and average rates achieved by the scheme adopted for sublibrary , respectively.

Under the peak rate criterion, the cache allocation that minimizes the overall delivery rate (i.e., the sum rate of each sublibrary) is as follows. Let

 M∗≜min{M:∣∣∂−∂MRach(M,ρ1,ρ2)∣∣<1}. (8)

denote the cache encoder threshold, where denotes the left partial derivative with respect to . For a given , the cache encoder allocates the memory to each sublibrary as follows:

• If , the common description is not cached at either receiver, and descriptions from are cached according to the caching strategy of the adopted correlation-unaware CACM scheme.

• If , the first bits of description are cached at both receivers (as per LFU caching), and descriptions are cached according to the scheme adopted for sublibrary over the remaining memory .

• If , the common description is fully cached at both receivers, and descriptions are cached according to the adopted correlation-unaware CACM scheme over the remaining cache capacity .

The optimality of the cache allocation described above is proved in Appendix A, and its graphical representation is depicted in Fig. 3. This representation can be understood as “water-filling of two leaky buckets”, which is related to the well-known water-filling optimization problem [33]. For small cache capacities up to , all the memory is allocated to the private sublibrary. As the cache size increases, it is optimal to first store the common description until it is fully cached, and for cache capacities larger than , the residual memory is allocated to storing the private descriptions.

###### Remark 1

Differently from the single-cache setting analyzed in [5], where it is always optimal to cache the common description, in our case, when the cache capacity is smaller than , it is optimal to first cache the private descriptions. This is due to the fact that for small cache sizes delivering the privare descriptions with coded multicast transmissions is more effective in reducing the overall reate compared to mutlicasting the commom description, and therefore it is preferable to prioratize caching from the private sublibrary. As the cache size increases, this difference in rate reduction diminishes to the extent that assigning memory to the common sublibrary is more effective in reducing the rate compared to the private sublibrary. Therefore, it is preferable to fully store the common description prior to allocating additional memory for storing the private descriptions.

Under the average rate criterion, the optimal cache allocation among sublibraries and is similar to the peak rate scenario described previously, with respect to a cache encoder threshold

 ¯M∗≜min{M:∣∣∂−∂M¯Rach(M,ρ1,ρ2)∣∣<1}, (9)

where is the average delivery rate achieved by the correlation-unaware CACM scheme adopted for sublibrary .

The following theorem provides the peak and average rates achieved by the proposed MR scheme for the optimal cache allocation described above.

###### Theorem 3

In the two-file -receiver network, for a given cache capacity , rate-tuple , and a given adopted correlation-unaware CACM scheme with peak rate the peak rate achieved by the MR scheme, , is given by

 RMR(M,ϱ)=⎧⎪ ⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪ ⎪⎩ρ0+Rach(M,ρ1,ρ2),M∈[0,M∗)ρ0+Rach(M∗,ρ1,ρ2)+M∗−M,M∈[M∗,ρ0+M∗)Rach(M−ρ0,ρ1,ρ2),M∈[ρ0+M∗,ρ0+ρ1+ρ2] (10)

where is defined in (8). Denoting by the average rate achieved by an adopted correlation-unaware CACM scheme, the average delivery rate achieved by the corresponding MR scheme, , is similar to that in (10) but with respect to and .

###### Proof 2

The proof is given in Appendix A.

From Theorem 3 it is observed that the performance of the proposed MR scheme depends on the correlation-unaware CACM scheme adopted for the private sublibrary. In order to analyze the optimality of the proposed MR scheme in Sec. V-C, for sublibrary , we resort to a scheme that properly combines near optimal schemes available in literature, generalized to unequal file lengths, as described next.

#### V-B1 Peak Rate

The scheme adopted for the private sublibrary is based on memory sharing among generalizations of the correlation-unaware CACM schemes proposed in [28] and [29] to files with unequal lengths. Specifically, for small cache sizes, the adopted scheme uses the scheme in [28] (first introduced in [30] for a specific cache capacity), which prefetches coded content during the caching phase, while for large cache sizes, it uses the scheme in [29] with uncoded cache placement. For ease of exposition, the specific details of the scheme adopted for the private sublibrary is given in Appendix C, where we also derive an upper bound on its achievable rate, , given in (39). By combining with Theorem 3, an upper bound on the peak rate achieved by the proposed MR scheme is given in the following theorem.

###### Theorem 4

In the two-file -receiver network, for a given cache capacity and rate-tuple , an upper bound on , the peak rate achieved with the proposed MR scheme, is given by

 RMR(M,ϱ)≤⎧⎪ ⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪ ⎪⎩ρ0+ρ1+ρ2−2M,M∈[0,γK)ρ0+ρ1+ρ2−γK−M,M∈[γK,λK)12(ρ0+ρ1+ρ2−M),M∈[λK,ρ0+ρ1+ρ2] (11)

where

 γK≜1Kmin{ρ1,ρ2},λK≜ρ0+ρ1+ρ2−2γK. (12)
###### Proof 3

The proof follows from Theorem 3 and from adopting the scheme described in Appendix C for the private sublibrary. An upper bound on the peak rate achieved with this scheme, , is given in (39) and when replaced in (8), the cache encoder threshold becomes . Combining (10) with (39), and using the fact that , (12) is obtained after algebraic manipulation.

Specializing the upper bound on given in (11) to receivers results in a tight upper bound444By a tight upper bound we mean that for equation (11) holds with equality. for this setting as per the following corollary.

###### Corollary 1

In the two-file two-receiver network, for a given cache capacity and rate-tuple , the proposed MR scheme achieves the following peak rate

 RMR(M, ϱ)=⎧⎪ ⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪ ⎪⎩ρ0+ρ1+ρ2−2M,M∈[0,12min{ρ1,ρ2})ρ0+12(ρ1+ρ2+max{ρ1,ρ2})−M,M∈[12min{ρ1,ρ2},ρ0+max{ρ1,ρ2})12(ρ0+ρ1+ρ2−M),M∈[ρ0+max{ρ1,ρ2},ρ0+ρ1+ρ2].

#### V-B2 Average Rate

In this case, for the private sublibrary, we adopt a generalization of the close-to-optimal correlation-unaware CACM scheme in [29] to unequal-length files. The specific details of the adopted scheme are provided in Appendix E, where we also derive an upper bound on its achievable rate, , given in (52). By combining with the average counterpart of (10) given in Theorem 3, an upper bound on the average rate achieved with the proposed MR scheme is given in the following theorem.

###### Theorem 5

In the two-file -receiver network, for a given cache capacity and rate-tuple , an upper bound on , the average rate achieved with the proposed MR scheme, is given by

 (13)

for and defined in Theorem 4, and with

 ¯γK≜ρ0+2Kmin{ρ1,ρ2}=ρ0+2γK. (14)
###### Proof 4

The proof follows from Theorem 3 and from adopting the scheme described in Appendix E for the private sublibrary. An upper bound on the average rate achieved with this scheme, , is given in (52) and when replaced in (9), the cache encoder threshold becomes . Eq (12) is obtained by combining the average counterpart of (10) given in Theorem 3 with (52).

Specializing the upper bound on given in (13) to the setting with receivers leads to the following corollary.

###### Corollary 2

In the two-file two-receiver network, for a given cache capacity and rate-tuple , the proposed MR scheme achieves the following average rate

 ¯RMR(M,ϱ)= ⎧⎪ ⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪ ⎪⎩ρ0+34(ρ1+ρ2)−M,M∈[0,ρ0+min{ρ1,ρ2})34ρ0+12(ρ1+ρ2)+14max{ρ1,ρ2}−34M,M∈[ρ0+min{ρ1,ρ2},ρ0+max{ρ1,ρ2})12(ρ0+ρ1+ρ2−M),M∈[ρ0+max{ρ1,ρ2},ρ0+ρ1+ρ2] (15)

### V-C Optimality of the Proposed MR Scheme

In this section, we compare the performance of the proposed MR scheme charaterized in Sec. V-B with the lower bounds given in Sec. V-A. The following theorems provide the memory regions for which the proposed MR scheme is optimal or near-optimal.

#### V-C1 Peak Rate

###### Theorem 6

In the two-file -receiver network and for a given rate-tuple , when

 M∈[0,1Kmin{ρ1,ρ2}]⋃[ρ0+ρ1+ρ2−2Kmin{ρ1,ρ2},ρ0+ρ1+ρ2],

the proposed MR scheme is optimal under the peak rate criterion among all multiple-request schemes, i.e., . For all other cache capacities,

 RMR(M,ϱ)−R∗MR(M,ϱ)≤(12−1K)min{ρ1,ρ2}.
###### Proof 5

The proof is given in Appendix B.

###### Corollary 3

In the two-file two-receiver network, for any cache capacity and rate-tuple , the proposed MR scheme is optimal under the peak rate criterion among all multiple-request schemes, i.e.,

###### Proof 6

The optimality of the scheme with respect to the MR peak rate-memory function follows from setting in Theorem 6, for which the achievable rate meets the lower bound for the entire region of the memory.

#### V-C2 Average Rate

###### Theorem 7

In the two-file -receiver network and for a given rate-tuple , when

 M∈[ρ0+ρ1+ρ2−2Kmin{ρ1,ρ2},ρ0+ρ1+ρ2],

the proposed MR scheme is optimal under the average rate criterion among all multiple-request schemes, i.e, For all other cache capacities,

 ¯RMR(M,ϱ)−¯R∗MR(M,ϱ)≤(14−12K)(ρ1+ρ2).
###### Proof 7

The proof is given in Appendix D.

###### Corollary 4

In the two-file two-receiver network, for any cache capacity and rate-tuple , the proposed MR scheme is optimal under the average rate criterion among all multiple-request schemes, i.e.,

###### Proof 8

The optimality of the scheme with respect to the MR average rate-memory function follows from setting in Theorem 7, for which the achievable rate meets the lower bound for the entire region of the memory.

###### Remark 2

Corollaries 3 and 4 imply that in the two-file two-receiver network, caching and delivering content independently across the sublibraries, as described in Sec. V-B, is sufficient to achieve optimality among all MR schemes, rendering coding across the multicast codewords pertaining to each sublibrary unnecessary.

## Vi Optimality of the GW-MR Scheme for Two Files

In this section, we first provide lower bounds on the optimal peak and average rate-memory functions, and , given in Definitions 2 and 4, respectively, for the two-file -receiver network described in Sec. II. Then, by using the results of the MR scheme for two files (Sec. V), we evaluate the performance of the proposed GW-MR scheme (Sec. III), by comparing the presented lower bounds with the peak and average rates achieved by the proposed GW-MR,

 RGW-MR(M)=inf{RMR(M,ϱ):ϱ∈SGW}, (16) ¯RGW-MR(M)=inf{¯RMR(M,ϱ):ϱ∈SGW}, (17)

respectively, where and are the peak and average rates achieved by the MR scheme (Sec. V-B).

### Vi-a Lower bounds on R∗(m) and ¯R∗(M)

###### Theorem 8

In the two-file -receiver network with library distribution , for a given cache capacity , a lower bound on , the optimal peak rate-memory function, is given by

 RLB(M)=inf{R: R≥H(X1,X2)−2M, R≥12(H(X1,X2)+max{H(X1),H(X2)})−M, R≥12(H(X1,X2)−M)}.

A lower bound on , the optimal average rate-memory function, is given by

 ¯RLB(M)=inf{R: R≥(1−22K)H(X1,X2)+12K(H(X1)+H(X2))−2(1−12K)M, R≥12H(X1,X2)+14(H(X1)+H(X2))−M, R≥12H(X1,X2)+14max{H(X1),H(X2)}−34M, R≥12(H(X1,X2)−M)}.
###### Proof 9

The proof is given in Appendix F.

###### Remark 3

When particularized to i.i.d. sources, the lower bounds in Theorem 8 match the corresponding best known bounds derived in [34].

### Vi-B Optimality of the Proposed GW-MR Scheme

The following theorems characterizes the performance of the proposed GW-MR scheme described in Sec. III for different regions of , and delineates the rate-memory region for which the scheme is optimal or near-optimal.

###### Theorem 9

In the two-file -receiver network, let

 MK≜maxX1−U−X21Kmin{H(X1|U),H(X2|U)}, (18)

for with . When , the proposed GW-MR scheme is optimal under the peak rate criterion, i.e, . For all other cache capacities, we have

 RGW-MR(M)−R∗(M)≤12min{H(X1|X2),H(X2|X1)}−MK. (19)
###### Proof 10

The proof is given in Appendix G.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9341434836387634, "perplexity": 1357.0992102063112}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2020-40/segments/1600400193391.9/warc/CC-MAIN-20200920031425-20200920061425-00429.warc.gz"}