Completion of this doctoral dissertation was possible with the support of several people. I would like to express my sincere gratitude to all of them. I am extremely grateful to my advisors, Prof. Daniela Tuninetti and Prof. Pablo Piantanida for their solid support. I would like to thank them for trusting me and giving this position to me. I would like to thank them for the detailed instruction on this topic which was totally new for me when I started. I know I was not good at speaking and writing in English. I would like to thank them for their patience while discussing with me and correcting my papers. I hope that after these three years, they find that they did not make a bad choice. I am so happy and proud to work with them.

I would like to thank our cooperator Prof. Mingyue Ji, who gave us many interesting research directions, useful ideas and detailed corrections on our work. I am also grateful to my administrative advisors, Prof. Pierre Duhamel and Prof. Armelle Wautier, who gave me a lot of help on the administrative affairs.

Besides my advisors and cooperator, I would like to thank the rest of my thesis committee: Prof. , Prof.

, and Dr. , for their insightful comments.

We also would like to thank Zhangchi Chen from Mathematical Department of University Paris-sud who proved Appendix A.9 and Tang Liu from ECE Department of University of Illinois at Chicago (UIC) who inspired us to derive Appendix A.7.

I gratefully acknowledge the funding sources that made my Ph.D. work possible. I was funded by Labex Digicosme for my first three years and three mouths and was funded by UIC for the last four mouths.

For my fellow labmates in Laboratoire des Signaux et Système (L2S), Weichao, Chen, Li, Maggie, Faton, Wafa, two Chao's', Xiaoxia, Xiaojun, Jian, Xuewen and many others, I would like to thank them for the stimulating discussions, for all the fun we have had in the last years, for everyday we were working together. I would like to thank all my 'brothers' (Siqi, Yunsong, Yao, Nan, Zhichao, etc.) in France with whom I did not feel alone even if I was away from my hometown. I also would like to thank my officemates (Tang, Kenneth, Meysam, Ahmad, Sara, Narueporn) at UIC where I visited three times. My time at Chicago was made enjoyable because of them. I would like to thank all the colleagues and secretaries of both L2S and UIC, for their friendly assistant. I owe a lot to my parents, who encouraged and helped me at every stage of my personal and academic life, and longed to see this achievement come true. I would like to thank them for their strong love and encouragement.

Last but not the least, I am very much indebted to my wife, who is willing to accompany me in France during these years. I can not find any words to express my gratitude to her. I also would like to thank our lovely dog and cat, who make our life really happy and colorful. optimal worst-case max link-load in centralized system

List of Acronyms

R ⋆ c,u
optimal worst-case max link-load with uncoded cache placement in centralized system R ⋆ d optimal worst-case max link-load in decentralized system

R ⋆ d,u
optimal worst-case max link-load with uncoded cache placement in decentralized system R s→r max link-load from the server to relays R r→u max link-load from relays to users R J set of relays connected to all the users in J RLC(m, S) m random linear combinations of the equal-length packets indexed by S; for two integers x and y, we let x y = 0 if x < y or x < 0 or y < 0.

T (n) ε (
x List of Figures

List of Tables

Motivation for Caching

In the last decade, there has been a massive increase of Internet devices connected through the wireless access, and a steep increase in mobile traffic because of multimedia streaming, web-browsing applications and socially-interconnected networks [1], [START_REF]Cisco visual networking index: Global mobile data traffic forecast update[END_REF]. At the same time, the evolution of mobile devices (in computation power, size and speed of RAM and ROM , etc.) has open possibility for more advanced and sophisticated transmission techniques to reduce the network traffic. For example, Fig. 1.1 illustrates the exponential evolution of micro-processors in mobile devices in terms of computation power. In addition, the users' demands may concentrate on a relatively limited number of files (e.g., latest films and musics). Moreover, in real communication systems, the high temporal variability of network traffic results in congestions during peak-traffic times and underutilization of the network during off-peak times (e.g., see the daily video consumption variation in Chicago provided by 'AT& T' in Fig. 1.2). All of the above together motivates the use of caching [START_REF] Bastug | Living on the edge: The role of proactive caching in 5g wireless networks[END_REF].

Cache is a network component that leverages the device memory to transparently store data so that future requests for that data can be served faster. Caching reduces peak traffic by taking advantage of memories distributed across the network to duplicate content during off-peak times. By doing so, caching effectively allows to shift traffic from peak to peak-off hours, thereby smoothing out traffic variability and reducing congestion. Two phases are included in a caching system: i) placement phase: each user stores some bits in its cache without knowledge of later demands; ii) delivery phase: after each user has made its request and according to cache contents, the server transmits packets in order to satisfy the user demands. The goal is to minimize the number of transmitted bits (load) such that user demands can be satisfied.

Cache-aided Shared-link Broadcast Networks

In this thesis, we first consider the fundamental performance of cache-aided broadcast systems (also known as shared-link model illustrated in Fig. 1.3) originally proposed by Maddah-Ali and Niesen (MAN) in their seminar works [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF], [START_REF]Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF]. In the MAN model, a server is connected to K users, or clients, via a shared broadcast error-free link. The server has N files (F 1 ,. . . , F N ) each of size B bits. Each user has a local cache of size MB bits to store parts of the files available at a server. In the placement phase, pieces of the files available at a server are stored within the users' cache. The placement phase is done during off-peak times and thus without knowledge of the users' demands. In this phase, the cache size M is the main limitation. When each user directly copies some bits of the files within its cache, the placement phase is said to be uncoded, otherwise that it is coded. In the delivery phase, each user k ∈ [K] demands a specific file F d k from the server. The server, based on the demands and the cache contents, broadcasts RB bits to all users so that each user can recover the demanded file. The delivery phase occurs during peak traffic times, thus the broadcast transmission rate from the server to the users is the main limitation. Therefore, the objective is to design a two-phase scheme so that the load is minimized regardless of the demands, i.e., to minimize the worst-case load, or just load for short in the rest of thesis.

Cache-aided systems are divided into two classes, centralized in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] and decentralized in [START_REF]Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF], depending on whether users can coordinate the content stored locally in their caches during the placement phase.

In centralized cache-aided systems, the users in the two phases are assumed to be the same; therefore, coordination among users is possible in the placement phase. In practice coordination may not be possible, for example due to users' mobility; thus a user may be connected to a server during its placement phase but to a different one during its delivery phase. In this decentralized scenario, coordination among users during the placement phase is thus not possible.

As pointed out in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF], when content is stored locally uncoded, the delivery phase of the caching problem in shared-link systems can be related to an index coding problem.

The Index Coding (IC) problem, originally proposed in [START_REF] Birk | Informed source coding on demand (iscod) over broadcast channels[END_REF], has connections to caching as already pointed out in [4, p. 2865, Section VIII.A. Connection to Index and Network Coding]: " [...] Now, for fixed uncoded content placement and for fixed demands, the delivery phase of the caching problem induces a so-called IC problem. However, it is important to realize that the caching problem actually consists of exponentially many parallel such IC problems, one for each of the N K possible user demands. Furthermore, the IC problem itself is computationally hard to solve even only approximately. [...]"

In an IC problem, a sender has N ′ independent messages and is connected to K ′ users through an errorfree broadcast link. Each user has already some messages stored locally as side information, and demands a subset of the remaining messages. The server broadcasts packets such that each user can recover the desired messages reliably. The objective is to determine the largest message rate region such that messages can be delivered reliably. If each user demands a different message, the IC problem is called a multiple unicast IC, and just IC otherwise. The difference between caching and IC is that the side information sets are fixed in IC, while they represent the cache contents that has to be properly designed in caching; moreover, in IC the demands are also fixed, while in caching one must consider all possible demands. In caching, if the cache placement phase is uncoded, the delivery phase is an IC problem for appropriately defined message and demand sets. Hence, IC results can be leveraged for the caching problem. This is exactly our approach in this thesis.

Our main contribution for cache-aided shared-link broadcast systems is to leverage known, and derived novel, results for the index coding problem to determine the fundamental limits of cache-aided systems with uncoded cache placement.

Cache-aided Combination Networks

In practice most communication systems include a network structure other than a single broadcast link.

Caching problem were considered in relay networks ( [START_REF] Golrezaei | Femtocaching: Wireless video content delivery through distributed caching helpers[END_REF]- [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF]), device-to-device systems ( [START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF]), small cell Server with N files (size B bits) (F ,..., F ) networks ( [START_REF] Bastug | Cache-enabled small cell networks: Modeling and tradeoffs[END_REF]), interference channel ( [START_REF] Maddah-Ali | Cache-aided interference channels[END_REF]), etc. In this thesis, we consider caching in two-hop relay networks, where the users communicate with the server through some intermediate relays. Since the analysis of relay networks with arbitrary topologies is challenging, a 'symmetric' version of this general problem is known as the combination networks with end-user-caches proposed in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF], [START_REF] Ngai | Network coding gain of combination networks[END_REF] as shown in Fig. 1.4: a server with N files is connected to H relays (without caches), which in turns are connected to K = H r users equipped with caches of size M files and where each user is connected to a different subset of the r relays. All links are assumed to be error-free and interference-free. The objective is to determine the optimal max-link load R ⋆ , defined as the smallest max-rate (the maximum rate among all the links, proportional to the download time) for the worst case demands. Lying at the intersection of multi-hop networks and single-hop broadcast channels, combination networks are an interesting class of networks to build up intuition and understanding, and develop new caching converse and achievable bounds applicable to general relay networks.

Our main contribution for combination networks with end-user-caches is to characterize the optimality in terms of the download time under the constraint of some system parameter regimes, by deriving improved converse bounds and achievable bounds based on the network topology compared to the state-of-the-art schemes. We denote the optimal load as R ⋆ t (i.e., BR ⋆ t is the maximum number of bits transmitted for the-worst case demands) for t ∈ {c, d}, where 'c' stands for centralized and 'd' for decentralized.

Centralized Cache-aided Systems In [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] Maddah-Ali and Niesen proposed a coded caching scheme that utilizes an uncoded combinatorial cache construction in the placement phase and a binary linear network code in the delivery phase, where content in the caches is stored in a coordinated manner. For the centralized MAN scheme, denoted as cMAN in the following for short, for M = t N K with t ∈ [0 : K], the worst-case load was shown to satisfy

R ⋆ c ≤ 1 - M N min K 1 + K M N , N (1.1a)
≤ K -t 1 + t =: R c,u,MAN [t], (1.1b)
where the subscript "c,u,MAN" in (1.1b) stands for "centralized uncoded-placement Maddah-Ali and Niesen'

and where for M K N = t ∈ [0 : K] one takes the lower convex envelope of the set of points (M, R) = t N K , R c,u,MAN [t] . In (1.1a) the factor 1 -M N ∈ [0, 1] is interpreted as a 'local caching gain'. Each user can store locally the same fraction M N of each file in the placement phase; the server delivers uncoded the missing fraction 1 -M N of the requested file to each user in the delivery phase. This type of gain was well know before the work of Maddah-Ali and Niesen and scales with the size of the cache M. What Maddah-Ali and Niesen surprisingly shown was that a 'global caching gain' is also possible with careful cache placement, by which a single transmission is useful to satisfy the requests of more than one user. This gain is represented by the first term within the minimum in (1.1a). The second term within the minimum in (1.1a) represents the 'natural multicasting gain' that arises when one file is demanded by several users in the regime N < K.

In [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF], the authors derived a cut-set type converse bound as well. The optimal load R ⋆ c must satisfy

R ⋆ c ≥ max s∈[1:min(N,K)] s - s ⌊N/s⌋ M . (1.2)
Comparing this cut-set bound and the load of cMAN in (1.1b), Maddah-Ali and Niesen proved that cMAN caching scheme is optimal within factor 12, but it was noted in [START_REF] Wang | A new converse bound for coded caching[END_REF] that it numerically appeared to be optimal to within a factor 4.7.

The pioneering work in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] was extended in several ways. In [START_REF] Amiri | Coded caching for a large number of users[END_REF], the authors proposed a novel delivery phase with the same placement phase as in cMAN for the case N < K. This novel group-based delivery is however only valid for the special case of M = N/K (that is, t = 1) where it achieves the load N -N(N+1) 2K . Recently, in [START_REF] Yu | The exact rate-memory tradeoff for caching with uncoded prefetching[END_REF] the optimal load for centralized cache-aided systems with uncoded cache placement was shown to be achieved essentially following the cMAN original idea, but with the fundamental observation that certain transmitted linear combinations sent by cMAN are redundant (i.e., they can be obtained as linear combinations of other transmitted messages) leading to the bound

R ⋆ c ≤ R c,u,YMA [t] := K t+1 -K-min(K,N) t+1 K t , (1.3) for M = t N K with t ∈ [0 : K],
where the subscript "c,u,YMA" in (1.3) stands for "centralized uncodedplacement Yu Maddah-Ali Avestimehr" and where for M K N = t ∈ [0 : K] one takes the lower convex envelope of set of points (M, R) = t N K , R c,u,YMA [t] . Notice that the load in (1.3) is strictly smaller than the one in (1.1b) for N < K. The converse bound under the constraint of uncoded cache placement used in [START_REF] Yu | The exact rate-memory tradeoff for caching with uncoded prefetching[END_REF] to characterize the optimality of R c,u,YMA was first derived in our previous conference works [START_REF] Wan | On the optimality of uncoded cache placement[END_REF], [START_REF]On caching with more users than files[END_REF], which are the short versions of this present thesis.

In [START_REF] Ghasemi | Further results on lower bounds for coded caching[END_REF]- [START_REF] Tian | Symmetry, demand types and outer bounds in caching systems[END_REF], converse bounds on R ⋆ c tighter than cut-set bound provided in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] were proposed. An improved lower bound compared to the cut-set bound was given in [23, Theorem 1], which was used to show that the effectiveness of caching become small when the number of files becomes comparable to the square of the number of users. An algorithm that generalizes [START_REF] Ajaykrishnan | Critical database size for effective caching[END_REF] was proposed in [START_REF] Ghasemi | Further results on lower bounds for coded caching[END_REF] to generate bounds of the form αR + βM ≤ R ⋆ c , for positive integers α and β, and used to show that the upper bound in (1.1b) is optimal to within a factor 4. Another lower bound was obtained in [START_REF] Sengupta | Improved approximation of storage-rate tradeoff for caching via new outer bounds[END_REF] by leveraging [START_REF] Cover | Elements of information theory[END_REF]Theorem 17.6.1] as a 'symmetrization argument' over demands and used to show that the bound in (1.1b) is optimal to within a factor 8; the lower bound applies to the case where users can request multiple files from the server as well. An approach based on solving a linear program derived from the sub-modularity of entropy and simplified by leveraging certain inherent symmetries in the caching problem was put forth in [START_REF] Tian | Symmetry, demand types and outer bounds in caching systems[END_REF] as a means to computationally generate lower bounds; the approach allowed to solve the case of K = 2 users and any number of files, and gives at present the tightest bounds for problems with small K and N (beyond which the computational approach becomes practically unfeasible).

An enhanced converse bound was proposed in [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF] by adding an additional non-negative term in the cut-set converse bound,

R ⋆ c ≥ s -1 + α - s(s -1) -l(l -1) + 2αs 2(N -l + 1) M, (1.4)
for any α ∈ 1, . . . , min{N, K} , α ∈ [0, 1], where l ∈ [1 : s] is the minimum value such that s(s-1)-l(l-1)

2

+ αs ≤ (N-l+1)l 2 . The multiplicative gap between the achieved load in (1.3) and the converse bound in (1.4) was proved to be within factor 2. In other words, coded cache placement can at most half the network load compared to the caching schemes with uncoded cache placement.

The cMAN scheme uses uncoded cache placement and linear network coding on the binary field for the delivery phase. Improvements on cMAN have been obtained by considering coded cache placement and linear network codes on fields of large size. The example of coded cache placement, originally proposed in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] for the case N = K = 2, was generalized in [START_REF] Chen | Fundamental limits of caching: Improved bounds for small buffer users[END_REF] to the case N ≤ K and MK ≤ 1 and shown to achieve the optimal point (M, R) = (M, N(1 -M)), i.e., to coincide with the cut-set bound. In [START_REF] Tian | Caching and delivery via interference elimination[END_REF]Theorem 1] the authors proposed a coded cache placement scheme, where the packets for the delivery phase are constructed based on the idea of interference elimination and linear combinations on a finite field of sufficiently large size; the proposed method combines rank metric codes and maximum distance separable codes and recovers the result of [START_REF] Chen | Fundamental limits of caching: Improved bounds for small buffer users[END_REF] for M = 1/K. The authors in [START_REF] Sahraei | K users caching two files: An improved achievable rate[END_REF] proposed a coded caching scheme for K ≥ N = 2 and M = m/K where m ∈ [1 : K -1]; in the placement phase, coded and symmetric cache placement is used while the delivery phase comprises the transmission of four kinds of linear combinations. Another caching scheme with coded cache placement was proposed in [START_REF] Amiri | Fundamental limits of coded caching: Improved delivery rate-cache capacity tradeoff[END_REF] when N and K satisfy N < K ≤ 3N/2 and (N, K) have a common divisor greater than 1, and M = (N -1)/K; the memory-load tradeoff point

(M, R) = ( N-1 K , K 2 + N K -1
) was shown to be achievable thus improving on cMAN in (1.1b). In [START_REF] Gomez-Vilardebo | Fundamental limits of caching: Improved bounds with coded prefetching[END_REF], a scheme was proposed for the case of coded cache placement with N ≤ K and MK N ≤ 1 that provably has the best load to-date for N ≤ K ≤ (N 2 + 1)/2.

Decentralized Cache-aided Systems The previously mentioned works leverage coordination among users in the placement phase which is not possible in decentralized systems. In [START_REF]Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF], Maddah-Ali and Niesen proposed a scheme, denoted as dMAN in the following, where each user fills its cache randomly and independently of the others. During the delivery phase of dMAN, the bits of the N files are organized into sub-files depending on which subsets of users cached them. With the assumption that the file size B goes to infinity (while N, K, and M are kept fixed), the normalized length (by the file size B) of each sub-file converges in probability to a value that only depends on the number of users who stored this sub-file in the local cache.

By repeating K times the delivery phase of cMAN (one for each group of sub-files known by k users, with k ∈ [0 : K -1]) the following load was shown to be achievable

R ⋆ d ≤ R d,u,MAN := 1 - M N min N M 1 -1 - M N K , N (1.5a)
≤ 1 -M N M N 1 -1 - M N K , (1.5b)
where the factor N M 1 -1 -M N K in (1.5a) represents an additional 'global caching gain' compared to the conventional 'local caching gain' of 1 -M N ; the subscript "d,u,MAN" in (1.5a) stands for "decentralized uncoded-placememnt MAN."

In general, existing centralized caching schemes with uncoded cache placements can be extended to decentralized systems in the same manner as cMAN was used to get dMAN. For example, in [START_REF] Yu | The exact rate-memory tradeoff for caching with uncoded prefetching[END_REF] the optimal load for decentralized cache-aided systems with uncoded cache placement was shown to be achieved essentially following the dMAN original idea, but with the fundamental observation that certain transmitted linear combinations sent by dMAN are redundant, leading to the upper bound

R ⋆ d ≤ R d,u,YMA := 1 -M N M N 1 -1 - M N min(K,N) , (1.6)
where the subscript "d,u,YMA" stands for "decentralized uncoded-placememnt Yu Maddah-Ali and Avestimehr." The load in (1.6) is strictly smaller than the one in (1.5b) for N < K and coincides with the converse bound for decentralized cache-aided systems under the constraint of random, independent and uniform caching, a result that was originally derived in the first author's preliminary Ph.D. defense document [START_REF] Wan | On caching with uncoded cache placement[END_REF]. For the multiple unicast IC problem several achievable bounds are known: based on the minimization of the rank of certain matrices [START_REF] Bar-Yossef | Index coding with side information[END_REF]; based on interference alignment [START_REF] Maleki | Index coding an interference alignment perspective[END_REF], [START_REF] Jafar | Topological interference management through index coding[END_REF]; based on graph proprieties such as clique-cover, partial clique-cover, local clique cover, and partial local clique covering in [START_REF] Bar-Yossef | Index coding with side information[END_REF], [START_REF] Witsenhausen | The zero-error side information problem and chromatic numbers[END_REF]- [START_REF] Agarwal | Local partial clique covers for index coding[END_REF],

Past Work on Index Coding

respectively; and based on linear coding for a class of interlinked-cycle structure graphs [START_REF] Thapa | Interlinked cycles for index coding: Generalizing cycles and cliques[END_REF].

Information-theoretic random coding arguments inspired by source coding have also been used to derive achievable schemes for the IC problem. The authors of [START_REF] Unal | A rate-distortion approach to index coding[END_REF]- [START_REF] Lim | Information theoretic caching: The multi-user case[END_REF] proposed achievable bounds based on the Heegard-Berger coding scheme 'where side information may be absent' [START_REF] Heegard | Rate distortion when side information may be absent[END_REF]. An achievable bound, referred to as composite coding, was proposed in [START_REF] Arbabjolfaei | On the capacity region for index coding[END_REF]Theorem 2] by combining Slepian-Wolf coding [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF] and binning (this last step referred to as flat coding). Composite coding matches the converse bound in [35, Theorem 1] for the multiple unicast IC problem with no more than five messages / users. In this work, since the composite (index) coding is not optimal in general for the caching problem with uncoded placement, we shall derive a novel IC achievable bound which strictly improves on the composite (index) coding rate region.

Main Contributions for Cache-aided Shared-link Networks

The exact memory-load tradeoff under the constraint of uncoded cache placement was recently characterized in [START_REF] Yu | The exact rate-memory tradeoff for caching with uncoded prefetching[END_REF] where the converse bound for centralized cache-aided systems and the its optimality for K ≤ N were originally proposed in our conference papers [START_REF] Wan | On the optimality of uncoded cache placement[END_REF], [START_REF]On caching with more users than files[END_REF], and the converse bound for decentralized cacheaided systems was originally derived in [START_REF] Wan | On caching with uncoded cache placement[END_REF]. In this thesis, we focus on cache-aided systems with uncoded placement (both centralized and decentralized) and study their performance based on the IC problem.

Our main contributions for cache-aided shared-link Networks (detailed in Chapter 2) are:

1. Novel index coding achievable bound. In Section 3.2, we propose an IC achievable bound based on Han's coding scheme [START_REF] Han | The capacity region of general multiple-access channel with certain correlated sources[END_REF], Slepian-Wolf coding [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF] and non-unique decoding. This achievable scheme is shown to strictly outperform composite (index) coding and is, to the best our knowledge, the best random coding achievable bound for the general IC problem to date.

2.

Centralized cache-aided systems with uncoded cache placement. By exploiting [START_REF] Arbabjolfaei | On the capacity region for index coding[END_REF]Corollary 1], in Section 4.2 we derive a lower bound for the load in centralized cache-aided systems with uncoded cache placement. We originally presented this bound in [START_REF] Wan | On the optimality of uncoded cache placement[END_REF], where we also showed that it matches the load of cMAN in (1.1b) when K ≤ N . We then show that our novel IC scheme matches our converse bound for cache-aided systems when K > N .

3. Decentralized cache-aided systems with uncoded cache placement. By again exploiting [START_REF] Arbabjolfaei | On the capacity region for index coding[END_REF]Corollary 1], in Section 4.3 we derive a lower bound for the load in decentralized cache-aided systems under the constraint that each user randomly, uniformly and independently chooses M B bits of the N files to store. We then prove that our centralized caching scheme can be extended to achieve the proposed converse bound for decentralized systems. For combination networks with end-user-caches, a straightforward way is that in the placement each user caches the same MB/N bits of each file and in the delivery the server uses routing to deliver the non-cached bits of the demanded file to each user. The achieved max link-load by routing is

R routing = K(1 -M/N)/H.
A coded caching strategy, referred to as two-step separation approach, was formalized in [START_REF] Naderializadeh | On the optimality of separation between caching and delivery in general cache networks[END_REF] for cacheaided relay networks: (a) cMAN-type uncoded cache placement and multicast message generation (i.e., the generation of the multicast messages is independent of the network topology), and (b) message delivery that aims to match the network multicast capacity region. With MAN placement and cMAN multicast messages generation, the authors in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] proposed to use an combination network linear coding to deliver cMAN multicast messages, which can achieve the max link-load

R MJ = min K(1 -M/N) H , K -t r(1 + t) (1.7) for M = Nt/K where t ∈ [0 : K].
The another approach is to design the placement and/or the multicast generation based on the network topology, referred to as non-separation approach. The existing schemes belonging to this approach were proposed in [START_REF] Tang | Coded caching for networks with the resolvability property[END_REF], [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF], where the combination network was split into H uncoordinated shared-link networks and then cMAN delivery was used in each one. With a coded cache placement based on MDS (maximum separable distance) codes, the scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] achieves the following max link-load which is the same as [START_REF] Tang | Coded caching for networks with the resolvability property[END_REF] but without the constraint in [START_REF] Tang | Coded caching for networks with the resolvability property[END_REF] that r divides H,

R ZY = K -t ′ H(1 + t ′ ) (1.8)
for M = NHt ′ /Kr where t ′ ∈ [0 : Kr/H]. The limitation of this coded placement is that the coded caching gain is now that of a network with H-1 r-1 < K equivalent users, which appears to be suboptimal in light of known results for shared-link networks (i.e., the coded caching gain fundamentally scales linearly with the number of users K).

Placement Delivery Array (PDA) originally proposed in [START_REF] Yan | On the placement delivery array design in centralized coded caching scheme[END_REF] to reduce the sub-packetization of MAN scheme in the shared-link models was also extended in [START_REF] Yan | Placement delivery array design for combination networks with edge caching[END_REF] to combination networks where r divides H to achieve the same load as [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] and [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] but with lower sub-packetization.

Information Theoretic Converse Bounds

The cut-set converse bound in (1.2) for shared-link broadcast Networks was extended to combination networks in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF]. The optimal load R ⋆ c must satisfy

R ⋆ c ≥ max α∈[1, H r ] 1 ⌈αr⌉ max l∈ 1,••• ,min N,( ⌈αr⌉ r ) l - l ⌊ N l ⌋ M , (1.9)
By analysing the above converse bound and the achieved max-link load in (1.7), the caching schemes in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] is order optimal within factor max{6 √ 3, 6 log(N/M)}. So when M ≥ N/6, the caching schemes in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] is order optimal within factor 6 √ 3. However, the gap might be extremely large when the memory size M is small.

Combination Networks with Cache-aided Relays and Users

Combination networks with caches at both the relays and the end-users has recently been considered in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF],

where each relay and user can store M relay B and M user B bits of all the N file in the placement phase, respectively. The objective of this problem is to find the capacity region of (R s→r , R r→u ) for each (M relay , M user ), where R s→r is the max link-load from the server to each relay (first layer load) and R r→u is the max link-load from each relay to each user (second layer load). In [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF], the authors proposed a caching scheme where each file is divided into two parts. Each relay only caches the content of first part and each user caches the content of the both parts. The first part is totally cached in the relays such that in the delivery phase, the server does not need to transmit the first part of each file. The proposed caching scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] for combination networks with end-user-caches is used to let each user recover the second part of his demanded file. For

M user = (t 1 -t 2 )M relay r K 1 + t 2 N K 1 ∈ 0, N r (1.10)
where

K 1 = Kr/H, t 1 , t 2 ∈ [0 : K 1 ]
, the achieved first and second layer loads are

R s→r ZY := K 1 -t 2 r(t 2 + 1) 1 - M relay r N , (1.11)
R r→u ZY := 1 r 1 - M user N .
(1.12)

It was proved [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] that the achieved second layer load of the proposed scheme is information theoretically optimal.

Main Contributions for Cache-aided Combination Networks

Our main contributions for cache-aided combination networks are:

1. For combination networks with end-user-caches, in Section 6.2 we study converse bounds on the max link-load under the constraint of uncoded cache placement when N ≥ K (the case N < K can be treated by similar ideas and is not treated here for simplicity). Based on the cut-set strategy in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF], we first extend the enhanced cut-set converse bound in (1.4) and the converse bound under the constraint of uncoded placement for shared-link models to combination networks with end-user-caches. We then extend the acyclic index coding converse bound to combination networks and propose a converse bound based on this extended acyclic index coding converse bound. Furthermore, by deriving bounds on the joint entropy of the various random variables that define the problem, we provide two novel ways to tighten the "acyclic index coding converse bound". The combination of these two ideas produces the best known converse bound to date, to the best of our knowledge.

As a result of independent interest, an inequality that generalizes the well-known sub-modularity of entropy is derived, which may find applications in other network information theory problems.

2. Based on the two-step separation approach, in Section 7.2 we propose four delivery schemes for combination networks with end-user-caches to deliver cMAN multicast messages to the corresponding users:

• We first propose a novel delivery scheme, Direct Independent delivery Scheme (DIS), by exploiting the fact that not all the linear combinations of the MAN delivery scheme are useful to every user.

• For M = N/K, Interference Elimination delivery Scheme (IES), use interference elimination (a form of interference alignment) to rid the users of the MAN coded messages that are not of interest.

• Concatenated Inner Code delivery Scheme (CICS) proposes a delivery coding scheme including two phases: in the first phase we directly transmit each MAN multicast message to some relays, which forward them to their connected users; such messages are simultaneously useful for t = KM/N users and will be used as 'side information' in the next phase; Since not all users are able to decode their desired file at the end of the first phase, in the second phase, we thus deliver the MAN multicast messages through a carefully design network code, to let the remaining 'unsatisfied' users recover their demanded file. In this phase, the multiplicative coding gain

• By leveraging the multicasting opportunities which are ignored in CICS, we propose, Improved Concatenated Inner Code delivery Scheme (ICICS).

3. By comparing the proposed achievable schemes with cMAN placement and the proposed converse bounds under the constraint of uncoded cache placement, we get the (order) optimality results illustrated in Table 1.1. Since the achieved max link-load in (1.7) was proved in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] to be order optimal within factor 6 √ 3, it can be seen that one of our main contributions is the order optimality within a constant value when M is small. The aforementioned optimality results can extended to the general case (coded or uncoded cache placement) by multiplying the order optimality factors by 2.

4.

Based on the separation approach, with cMAN placement, in Section 7.3 we propose a novel delivery scheme which generates multicast messages by leveraging the network topology. This delivery scheme could be used with any uncoded cache placement, with the proposed coded cache placements in this thesis and with decentralized cache placements.

5.

The main limitation of cMAN placement based schemes is that, due to the combination network topology, the multicasting opportunities (directly related to the overall coded caching gain compared

Delivery Schemes

Constraint of system parameters Optimality under the constraint of uncoded cache placement DIS, [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] N ≥ K order optimal within factor min{H/r, t

+ 1} for M = Nt/K DIS,CICS, ICICS N ≥ K, r > Ht/(t + 1), M = Nt/K optimal DIS,CICS, ICICS N ≥ K, r = H -1 optimal CICS N ≥ K, M = Nt/K order optimal within factor 1 + t/r CICS N ≥ K, M ≤ rt/K order optimal within factor 2 CICS N ≥ K, M = Nt/K, t/r → 0 optimal IES H ≤ 2r, N ≥ K, M ≤ N/K optimal IES H > 2r, N ≥ K, M ≤ N/K
order optimal within factor 2r/(2r -1) ≤ 4/3 to the uncoded routing scheme) to transmit the various subfiles are not "symmetric" across subfiles (because relays are connected to different sets of users). For example, consider the combination network in Fig. 1.4 and t = 2, since users 1 and 2 are connected to one relay (relay 1) while no relays is connected to users 1 and 6 simultaneously, it costs less load to transmit one multicast messages to users in {1, 2} from the server than to users {1, 6}. Hence, in Section 7.4 we fix one coded caching gain g ∈ 1 : H-1 r-1 compared to uncoded routing scheme and propose an asymmetric coded placement scheme to achieve this coded caching gain, where 'asymmetric' means that it is not necessary to generate one subfile known by each (g -1)-subset of users and 'coded' means that we use an MDS-precoded placement such that each user needs only to decode the subfiles with highest multicast opportunities. It is interesting to see that with this asymmetric placement, the delivery phase is symmetric. This scheme is proved to be information theoretically optimal when M ≥ (K-H+r-1)N K .

6. Comparing to all the existing schemes on combination networks with end-user-caches, DIS is strictly better than the caching schemes in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF], and the asymmetric coded placement scheme is strictly better than the caching scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF].

7. In Chapter 9, we extend the proposed results to more general models, including combination networks with cache-aided relays and users, and more general relay networks. Different to the existing scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] where the packets transmitted from the server are independent of the cached contents of relays, we propose a caching scheme where the cached contents in relays can also help users to decode the coded messages transmitted from the server and thus can further reduce the transmitted load from the server to relays. We prove that for some memory size regime, the achieved first layer load of the proposed scheme is information theoretically optimal. In the end, we extend the proposed schemes to more general relay networks with a further step to 'balance' the link-loads transmitted to relays.

Numerical results show that in both extended models, the proposed scheme improve the existing schemes.

Publications

The following lists are the papers produced during my Ph.D. candidature. System Model and Some Known Results

The Index Coding Problem: Definition

In this section, we provide the information-theoretic formulation of the IC problem shown in Fig. 2.1. A sender wishes to communicate N ′ independent messages to K ′ users. Each user j ∈ [K ′ ] demands a set of messages indexed by D j ⊆ [N ′ ] and knows a set of messages indexed by

A j ⊆ [N ′ ].
In order to avoid trivial problems, it is assumed that D j = ∅, A j = [N ′ ], and D j ∩ A j = ∅. The server is connected to the users through a noiseless channel with finite input alphabet X .

A (2 nR 1 , . . . , 2 nR N ′ , n, ǫ n )-code for this IC problem is defined as follows. Each message

M i , i ∈ [N ′ ], is uniformly distributed on [2 nR i ],
where n is the block-length and R i ≥ 0 is the transmission rate in bits per channel use. In order to satisfy the users' demands, the server broadcasts

X n = enc(M 1 , . . . , M N ′ ) ∈ X n
where enc is the encoding function. Each user j ∈ [K ′ ] estimates the messages indexed by D j by the decoding function dec j X n , (M i : i ∈ A j ) . The probability of error is

ǫ n := max j∈[K ′ ]
Pr dec j X n , (M i : i ∈ A j ) = (M i : i ∈ D j ) .

(2.1)

A rate vector (R 1 , . . . , R N ′ ) is said to be achievable if there exists a family of (2 nR 1 , . . . , 2 nR N ′ , n, ǫ n )-codes for which lim n→∞ ǫ n = 0.

M i : i ∈ A 1 Encoder User 1
User 2

User K'

M i : i ∈ A 2 M i : i ∈ A K ′ (M 1 , . . . , M N ′ ) M (1) i : i ∈ D 1 M (K ′ ) i : i ∈ D K ′ M (2) i : i ∈ D 2 . . . X n FIGURE 2.
1: An IC problem with N ′ files and K ′ users.

The Index Coding Problem: Composite (Index) Coding Achievable Bound

The composite (index) coding achievable bound proposed in [START_REF] Arbabjolfaei | On the capacity region for index coding[END_REF] is a two-stage scheme based on binning and non-unique decoding. In the first encoding stage, for each J ⊆ [N ′ ], the messages (M i : i ∈ J ) are encoded into the 'composite index' W J ∈ [2 nS J ] based on random binning at some rate S J ≥ 0. By convention S ∅ = 0. In the second encoding stage, the collection of all composite indices (W J :

J ⊆ [N ′ ])
is mapped into a length-n sequence X n which is received error-free by all users.

In the first decoding stage, every user recovers all composite indices. In the second decoding stage, user j ∈ [K ′ ] chooses a set K j such that D j ⊆ K j ⊆ [N ′ ]\A j and simultaneously decodes all messages (M i : i ∈ K j ), but uniquely only those in D j , based on the recovered (W J : J ⊆ K j ∪ A j ).

The achievable rate region with composite (index) coding is stated next.

Theorem 1 (Composite (Index) Coding Achievable Bound, generalization of [START_REF] Arbabjolfaei | On the capacity region for index coding[END_REF] to allow for multicast messages). A non-negative rate tuple R := (R 1 , . . . , R N ′ ) is achievable for the IC problem (A j , D j ) :

j ∈ [K ′ ] with N ′ = ∪ j∈[K ′ ] A j ∪ D j if R ∈ j∈[K ′ ] K j :D j ⊆K j ⊆[N ′ ]\A j R(K j |A j , D j ), (2.2a) R(K|A, D) := J :J ⊆K i∈J R i < v J , (2.2b)
where in (2.2b) the value v J is defined as

v J := P:P⊆A∪K,P∩J =∅ S P , (2.2c)
and where in (2.2c) the non-negative quantities (S J : J ⊆ [N ′ ]) must satisfy

J :J ∈[N ′ ],J A j S J ≤ log 2 (|X |), ∀j ∈ [K ′ ]. ( 2
R j ≤ log 2 (|X |), (2.3
)

for all J ⊆ [N ′ ]
where the sub-graph of G over the vertices in J does not contain a directed cycle.

The Caching Problem: Definition

Centralized Cache-aided Systems The information-theoretic formulation of the centralized coded caching problem, as originally formulated by Maddah-Ali and Niesen in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF], is as follows:

• The system comprises a server with N independent files, denoted by (F 1 , F 2 , . . . , F N ), and K users connected to it through an error-free link. Each file has B equally likely bits. The system is illustrated in Fig. 1.3.

• In the placement phase, user k ∈ [K] stores content from the N files in its cache of size MB bits without knowledge of later demands, where M ∈ [0, N]. We denote the content in the cache of user

k ∈ [K] by Z k = φ k (F 1 , . . . , F N ), where (placement functions) φ k : [0 : 1] NB → [0 : 1] ⌊MB⌋ , ∀k ∈ [K]. (2.4)
We also denote by Z := (Z 1 , . . . , Z K ) the content of all K caches.

• In the delivery phase, each user demands one file and the demand vector d := (d 1 , d 2 , . . . , d K ), where

d k ∈ [N]
corresponds to the file demanded by user k ∈ [K], is revealed to the server and all users. Given (Z, d), the server broadcasts the message X d = ψ(F 1 , . . . , F N , Z, d), where

(encoding function) ψ : [0 : 1] NB × [0 : 1] K⌊MB⌋ × [N] K → [0 : 1] ⌈RB⌉ . (2.5)
• Each user k ∈ [K] estimates the demanded file as

F k = µ k (X d , Z k ), where (decoding functions) µ k : [0 : 1] ⌈RB⌉ × [0 : 1] ⌊MB⌋ → [0 : 1] B , ∀k ∈ [K]. (2.6)
• The (worst-case over all possible demands) probability of error is

P (B) err,c := max d∈[N] K Pr K k=1 F k = F d k .
(2.7)

• A pair (M, R) is said to be achievable if there exit placement functions, encoding function and decoding functions such that lim B→∞ P (B)

err,c = 0, where P (B) err,c was defined in (2.7).

• The objective is to determine, for a fixed M, the (worst-case) load

R ⋆ c := inf{R : (M, R) is achievable}. (2.8)
In the following, we say that the placement phase is uncoded if the bits of the various files are simply copied within the caches, as formally defined next. • Each user caches bits of the files independently of the other users, that is, for some placement probability mass function q := q (A 1 ,A 2 ,...,A N ) :

A j ⊆ F j , j ∈ [N] , we let Pr [Z k = (A 1,k , A 2,k , . . . , A N,k ), k ∈ [K]] = u∈[K]
q (A 1,u ,A 2,u ,...,A N,u ) , (2.10)

for any A j,k ⊆ F j , j ∈ [N], k ∈ [K].
• For a demand vector d = (d 1 , d 2 , . . . , d K ) and a realization of the caches Z = (Z 1 , . . . , Z K ), the server sends X d (defined as in (2.5)) and receiver k ∈ [K] decodes F d k (defined as in (2.6)).

• The (worst-case over all possible demands) probability of error is

P (B) err,d := max d∈[N] K Pr K k=1 F k = F d k ∪ K k=1 {|Z k | > MB} , (2.11)
where the error event in (2.11) includes both the 'decoding error' K k=1 F k = F d k and the 'caching error' K k=1 {|Z k | > MB}, which is the event that at least one user fetches more bits that allowed by its cache size. Note that this definition of probability of error is not limited to uncoded cache placement (i.e., only the definition of the caching function in (2.10) is actually only valid for uncoded cache placement).

• A pair (M,
Z k = F i,W : k ∈ W, W ⊆ [K], |W| = t, i ∈ [N] . (2.13)
In the delivery phase, given the demand vector d, for each set of users J ⊆ [K] where |J | = t + 1, the server transmits the cMAN multicast messages

W J = ⊕ k∈J F d k ,J \{k} . (2.14)
Hence, totally the server broadcasts

X d = W J : J ⊆ [K], |J | = t + 1 , (2.15)
which requires broadcasting B K t+1 / K t bits. Note that user k ∈ J , for J as in (2.15), wants F d k ,J \{k} and knows/cached F ds,J \{s} for all s = k, so he can recover F d k ,J \{k} from X d in (2.15) and the cache content in (2.13). Thus for the cMAN caching scheme the load is given by (1.1b).

The optimal load for centralized cache-aided systems with uncoded cache placement was shown to be achieved essentially following the cMAN original idea, but with the fundamental observation that, of the K t+1 transmitted linear combinations in (2.15), K-min(K,N) t+1 can be obtained as linear combinations of other transmissions. Therefore, by removing these redundant transmissions for the case N < K, the load becomes the one in (1.3).

Decentralized Cache-aided Systems We now give the description of dMAN. In decentralized systems, coordination during the placement phase is not possible. The dMAN scheme in [START_REF]Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF] lets each user cache a subset of MB/N bits of each file, chosen uniformly and independently at random (which guarantees that every users does not violate its cache size limit). Given the cache content of all the users, the bits of the files are naturally grouped into sub-files F i,W , where F i,W is the set of bits of file i ∈ [N] that are only known/cached only by the users in W ⊆ [K]. It can be shown that

|F i,W | B → M N |W| 1 - M N K-|W|
in probability when B → ∞.

(2.16)

In the delivery phase, for each t ∈ [0 : K -1], all the K t+1 sub-files (F i,W : |W| = t, i ∈ [N]) are gathered together; since they all have approximately the same normalized length as in (2.16), the sender uses the cMAN scheme for M = tN/K to deliver them. As a result of the dMAN caching scheme, the load converges in probability when B → ∞ to

t∈[0:K-1] K t + 1 M N t 1 - M N K-t = 1 -M N M N 1 -1 - M N K , (2.17)
which coincides with (1.5b). The optimal load for decentralized cache-aided systems with uncoded cache placement can be achieved following the dMAN original idea without the redundant transmissions in the underlying cMAN scheme, which leads to the load in (1.6) (i.e., as in (2.17) but with K replaced by min(N, K)).

Mapping the

D k = F d k ,W : W ⊆ [K], k / ∈ W , (2.18)
A k = F i,W : W ⊆ [K], i ∈ N (d), k ∈ W . ( 2
W ⊆ [K] such that k / ∈ W, F d k ,W
is a message in a multiple unicast IC problem and is demanded by a virtual user with the side information identical to the cache content of user k in the caching problem. The inverse of the largest symmetric achievable rate for the this IC problem provides a lower bound for R ⋆ c,u if the cache-aided system is centralized or R ⋆ d,u if the cache-aided system is decentralized. In general, the lower bound derived in this way is not necessarily achievable in the original caching problem. A converse bound derived as just described and based on Theorem 2 will be derived in Section 4.2 for centralized cache-aided systems, and in Section 4.3 for decentralized cache-aided systems.

Achievable bound For the delivery phase in a cache-aided system with uncoded cache placement, which can be seen as a general multicast IC problem, the composite (index) coding achievable bound in Theorem 1 could be used. However, in our conference work [START_REF] Wan | On the optimality of uncoded cache placement[END_REF], [START_REF]On caching with more users than files[END_REF] we reported that Theorem 1 is not tight in general. In order to overcome this limitation, in Section 3.2, we propose a novel IC achievable bound which will be proved to be strictly better than composite (index) coding.

Chapter 3

Novel Index Coding Achievable Bound

Chapter Overview and Related Publications

In this chapter, based on Han's coding scheme [START_REF] Han | The capacity region of general multiple-access channel with certain correlated sources[END_REF], Slepian-Wolf coding [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF] and non-unique decoding, we propose a novel index coding achievable bound. This achievable scheme is shown to strictly outperform composite (index) coding and is, to the best our knowledge, the best random coding achievable bound for the general IC problem to date.

Related Publications

1. Kai Wan, Daniela Tuninetti and Pablo Piantanida, "An Index Coding Approach to Caching with Uncoded Cache Placement", submitted to IEEE Trans. on Information Theory, 2017. [START_REF] Wan | An index coding approach to caching with uncoded cache placement[END_REF] 2. Kai Wan, Daniela Tuninetti and Pablo Piantanida, "A Novel Index Coding Scheme and its Application to Coded Caching", in Proceedings of IEEE Infor. Theory Application Workshop (ITA), Feb.

[64]

Novel Index Coding Achievable Bound

We first introduce a novel IC achievable scheme based on coding for the Multi-Access Channel (MAC) with correlated messages [START_REF] Han | The capacity region of general multiple-access channel with certain correlated sources[END_REF], Slepian-Wolf coding [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF], and non-unique decoding [START_REF] Bandemer | Simultaneous nonunique decoding is rate-optimal[END_REF]. We then prove that the rate region of the proposed scheme not only strictly includes the region achieved by composite (index) coding in Theorem 1 but it also strictly outperforms the improved version of Theorem 1 from [START_REF] Liu | On the capacity for distributed index coding[END_REF].

Intuitively, the improvements in our scheme come from:

• In (2.2b), for each subset J ⊆ [N ′ ] in the composite (index) coding scheme, the composite index W J is determined by the messages indexed by J . Thus, composite indices are correlated among themselves. We leverage this correlation to loosen the required rate in the first decoding stage, which is given by (2.2d).

• In the composite (index) coding scheme, decoder j ∈ [K ′ ] wants to recover uniquely the messages in K j , and for that only the composite indices (W J : J ⊆ K j ∪ A j ) are used, as the constraint in (2.2c) indicates. In our proposed scheme, every user uses all the composite messages to uniquely recover the desired messages in the desired set D j , non-uniquely those in K j \D j , and treats the remaining messages as noise.

Theorem 3 (Novel Achievable Scheme for the General Index Coding Problem). A non-negative rate tuple

R := (R 1 , . . . , R N ′ ) is achievable for the IC problem (A j , D j ) : j ∈ [K ′ ] with N ′ = ∪ j∈[K ′ ] A j ∪ D j users if R ∈ j∈[K ′ ] K j :D j ⊆K j ⊆[N ′ ]\A j R(K j |A j , D j ), (3.1a) R(K|A, D) := J :J ⊆K,D∩J =∅ i∈J R i < κ J , (3.1b)
where in (3.1b) κ J is defined as

κ J := I U i : i ∈ J ; X P : P ⊆ [N ′ ] U i : i ∈ A j ∪ K j \ J , (3.1c)
for some independent auxiliary random variables

(U i : i ∈ [N ′ ]
) and some functions f P : P ⊆ [N ′ ] , such that X P = f P U i : i ∈ P and

H X P : P ⊆ [N ′ ] U i : i ∈ A j ≤ log 2 (|X |), ∀j ∈ [K ′ ]. (3.1d)
The proof of Theorem 3 is given in Appendix A.1.

Corollary 1. The composite (index) coding region in Theorem 1 is included in Theorem 3.

Proof. In general, for a set B ⊆ [N ′ ] and for the auxiliary random variables as defined in Theorem 3, we have

H X P : P ⊆ [N ′ ] U i : i ∈ B ≤ H X P : P ⊆ [N ′ ], P ⊆ B (3.2a) ≤ P:P⊆[N ′ ],P ⊆B H X P (3.2b) ≤ P:P⊆[N ′ ],P ⊆B S P , where S P = log 2 (|X P |). (3.2c)
In the following, we choose the auxiliary random variables

(U i : i ∈ [N ′ ]) and (X P : P ⊆ [N ′ ]
) such that all the inequality leading to (3.2c) holds with equality for any B ⊆ [N ′ ], that is, we construct random variables

(X P : P ⊆ [N ′ ]
) that are independent and uniformly distributed, where the alphabet of X P has support of size |X P | = 2 S P . With this choice of auxiliary random variables we show that Theorem 3 reduces to Theorem 1.

Let U i , for i ∈ [N ′ ],
be an independent and equally likely binary vector of length L i . For all P ⊆ [N ′ ],

let X P be a binary vector of length ⌊S P log 2 (|X |)⌋ obtained as a linear code for the collection of bits in

(U i : i ∈ P). If L i ≥ P⊆[N ′ ]:i∈P ⌊S P log 2 (|X |)⌋ for all i ∈ [N ′ ]
, then all the linear combinations that determine X P can be chosen to be independent and therefore all the inequalities leading to This concludes the proof.

In the rest of this section, we give an example to show that the proposed scheme in Theorem 3 is strictly better than the composite (index) coding in Theorem 1 and its improvement from [START_REF] Liu | On the capacity for distributed index coding[END_REF] Example 1. Consider a multiple unicast IC problem with K = 6 equal rate messages and with

D 1 = {1}, A 1 = {3, 4}, D 2 = {2}, A 2 = {4, 5}, D 3 = {3}, A 3 = {5, 6}, D 4 = {4}, A 4 = {2, 3, 6}, D 5 = {5}, A 5 = {1, 4, 6}, D 6 = {6}, A 6 = {1, 2}.
Composite (Index) Coding Achievable Bound In [67, Example 1] the authors showed that the largest symmetric rate with the composite (index) coding achievable bound in Theorem 1 for this problem is

R sym,cc = 0.2963 • log 2 (|X |).
In the same paper, the authors proposed an extension of the composite (index) coding idea (see [67, Section III.B]) and showed that this extended scheme for this problem gives

R sym,enhanced cc = 0.2987 • log 2 (|X |).
Converse Give message M 5 as additional side information to receiver 1 so that the new side information set satisfied {3, 4, 5} ⊂ A 2 . With this receiver 1, in addition to message 1, can decode message 2 and then message 6 for a total of 3 messages. Thus

3R sym ≤ lim n→∞ 1 n H(X n ) ≤ log 2 (|X |), (3.3)
where R sym denotes the symmetric rate. Next we show that

R sym ≤ 1/3 • log 2 (|X |) is tight.
This shows the strict sub-optimality of composite (index) coding and its extension.

Achievability Take the messages to be binary digits. It is not difficult to see that all users can be satisfied by the transmission of the three coded bits

X = (M 1 ⊕ M 3 ⊕ M 4 , M 2 ⊕ M 4 ⊕ M 5 , M 1 ⊕ M 2 ⊕ M 6 ).
We now map this scheme into a choice of auxiliary random variables in our novel IC scheme. Let each file be an independent bit, K j = D j for j ∈ [START_REF] Birk | Informed source coding on demand (iscod) over broadcast channels[END_REF], and

U 1 = M 1 , U 2 = M 2 , • • • , U 6 = M 6 , (3.4)
for all P ⊆ [6] set X P = 0 except (3.5)

X {1,3,4} = U 1 ⊕ U 3 ⊕ U 4 , (3.6)
X {2,4,5} = U 2 ⊕ U 4 ⊕ U 5 , (3.7) X {1,2,6} = U 1 ⊕ U 2 ⊕ U 6 , (3.8)
the transmitted signal is

X = (X {1,3,4} , X {2,4,5} , X {1,2,6} ). (3.9)
Here X = GF( 23 ) so one channel use corresponds to three bits. From (3.1c), we have that for example the rate bound corresponding to receiver 5 is

R sym ≤ I(U 5 ; U 1 ⊕ U 3 ⊕ U 4 , U 2 ⊕ U 4 ⊕ U 5 , U 1 ⊕ U 2 ⊕ U 6 |U 1 , U 4 , U 6 ) (3.10a) = I(U 5 ; U 3 , U 2 ⊕ U 5 , U 2 ) (3.10b) = I(U 5 ; U 2 , U 3 , U 5 ) (3.10c) = I(U 5 ; U 5 ) (3.10d) = H(U 5 ) (3.10e) = 1/3 • log 2 (|X |), (3.10f)
and similarly for all the other users. As a result,

R sym = 1/3 • log 2 (|X |
) is achievable by the proposed scheme and coincides with the converse bound.

Chapter 4

Optimal Converse Bound under the Constraint of Uncoded Cache Placement for Cache-aided Shared-link Broadcast Networks

Chapter Overview and Related Publications

This chapter analyses the cache-aided shared-link broadcast networks. After an uncoded cache placement, the deliver phase is equivalent to an index coding problem. In Section 4.2 and 4.3, we leverage the acyclic index coding converse bound and the proposed index coding achievable bound, for both centralized and decentralized caching systems. We derive a converse bound on the load cache-aided systems under the constraint of uncoded cache placement. When N ≥ K, we prove that cMAN (resp. dMAN) coincides with the proposed converse bound; while when N < K, the converse bound is attained by using the proposed novel IC scheme in the delivery phase with the same cMAN (resp. dMAN) placement phase.

Related Publications

Centralized Cache-aided Systems with Uncoded Cache Placement

In this section, we leverage the connection between caching and IC problems outlined in Section 2.6 to investigate the fundamental limits of centralized cache-aided systems with uncoded cache placement. We first derive a converse bound (by using Theorem 2 in Section 2.3), and then an achievable bound (by using Theorem 3 in Section 2.2) that matches the converse bound.

Recall that we denote the optimal load for centralized systems and decentralized systems by R ⋆ c and R ⋆ d , respectively. In addition, the loads for centralized systems and decentralized systems under the constraint of uncoded cache placement (see Definition 1) are denoted by R ⋆ c,u and R ⋆ d,u , respectively.

Novel Converse Bound under the Constraint of Uncoded Cache Placement

In this section, we prove our converse bound on the load of centralized cache-aided systems under the constraint of uncoded cache placement, which we first presented in [START_REF] Wan | On the optimality of uncoded cache placement[END_REF], [START_REF]On caching with more users than files[END_REF]. The main result of this section is stated next.

Theorem 4. In centralized cache-aided systems the load R ⋆ c,u satisfies

R ⋆ c,u ≥ K q+1 -K-min(K,N) q+1 K q + s q KM N -q , (4.1a)
s q := K q+1 -K-min(K,N) q+1 K q - K q -K-min(K,N) q K q-1 , ∀q ∈ [K]. (4.1b)
Moreover, this converse bound is a piecewise linear curve with corner points

(M, R) = t N K , K t+1 -K-min(K,N) t+1 K t , ∀t ∈ [0 : K]. (4.1c)
Before we proceed to prove the general converse bound in Theorem 4, we give a specific example. This example introduces the main ideas in the proof.

Example 2. The reasoning in this example applies to the general case K ≤ N. Assume that the server has

N = K = 3 files, denoted as (F 1 , F 2 , F 3 ). The total file length in number of bits is i∈[3] |F i | = NB = 3B. The total cache size in number of bits is i∈[3] |Z i | ≤ KMB = 3MB, for some M ∈ [0, N] = [0, 3].
After the uncoded cache placement phase is done, each file F i can be thought as having been divided into

2 K = 2 3 = 8 disjoint sub-files, denoted as (F i,W : W ⊆ [K] = [3], i ∈ [N] = [3]
) where F i,W has been cached only by the users in W. For simplicity in the following we omit the braces when we indicate sets, i.e., F 1,12 represents F 1,{1,2} , which dos not create any confusion.

For each demand vector d ∈

[N ] K = [3] 3 , we generate an IC problem with |N (d)|2 K-1 = 12 inde- pendent messages; these messages are (F d i ,W : i ∈ W, i ∈ [K]
) and represents the sub-files demanded by the users in [K] but not available in their caches. For this IC problem, we generate a directed graph with 12 vertices as follows. Each vertex corresponds to a different sub-file. We denote the user in the cache-aided system who wants the sub-file represented by vertex j by h j . There is a directed edge from vertex i to vertex Chapter 4. Optimal Converse Bound under the Constraint of Uncoded Cache Placement for Cache-aided Shared-link Broadcast Networks and u ∈ Perm(K, K), where Perm(n, k) denotes the set of all k-permutations of n elements (there are

n! (n-k)! elements in the set Perm(n, k) for n ≥ k). If we sum all the |Perm(N, K)||Perm(K, K)| = N K (K!) 2 = (3!) 2 = 36 inequalities as in (4.5), we get R ⋆ c,u ≥ 1 (3!) 2 d∈Perm(3,3) u∈Perm(3,3) j∈[3] W j ⊆[3]\{u 1 ,...,u j } |F du j ,W j | B (4.6a) = t∈[0:3] x t 3 t+1 3 t (4.6b) = t∈[0:3] x t 3 -t 1 + t (4.6c) = 3 • x 0 + 1 • x 1 + 1 3 • x 2 + 0 • x 3 , (4.6d)
where x t in (4.6b) is defined as

0 ≤ x t := j∈[N] W⊆[K]:|W|=t |F j,W | NB , t ∈ [0 : K], (4.7)
is the fraction of the total number of bits across all files that are known/cached only by a subset of t ∈ [0 :

K] = [0 : 3] users.
The general proof of (4.6b) can be found in (4.16b). At this point we can offer the following intuitive interpretation for the case K ≤ N, as it is the case in this example. The total number of sub-files cached by a subset of t ∈ [0 : K] users is N K t , where the factor K t appears at the denominator of (4.6b) (here K = 3), and the factor N at the denominator of (4.7). The total number of sub-files cached by a subset of t ∈ [0 : K] users in the bound in (4.5) (by the symmetry of the problem, all the other bound have the same structure) is

i∈[K] W i ⊆[K]\{u 1 ,...,u i } 1 {|W i |=t} = K -1 t + K -2 t + . . . + t t (4.8a) = K t + 1 , (4.8b)
where 1 {A} in the indicator function that is equal to one if and only if the condition in A is true, and where we have used the Pascal's triangle identity; the factor K t+1 (here K = 3) appears at the numerator of (4.6b). In addition to the bounds in (4.6) and (4.7), we also have that the total number of bits in the files is

j∈[N] W⊆[K] |F j,W | = NB ⇐⇒ t∈[K] x t = 1, (4.9)
and that the total number of bits in the caches must satisfy

j∈[N] W⊆[K]:j∈W |F j,W | ≤ KMB ⇐⇒ t∈[K] t x t ≤ KM N . (4.10)
Note that the bound in (4.9) is the total number of bits across all files, which is a looser constraint than imposing that each file contains the same number of bits; similarly, the bound in (4.10) is the total number of bits across all caches, which is a looser constraint than imposing that each cache has the same size; none of these is a problem as we aim to derive a lower bound on the load at this point. This implies that that the lower bound we derive applies to the case where the total number of bits across all files and the total number of bits across all caches are constrained, but not the size each individual file or each individual cache.

The constraints in (4.6)-(4.10) provide a converse bound for the load R ⋆ c,u with uncoded cache placement. Since there are many inequalities in K + 1 = 4 unknowns, we proceed to eliminate (x 0 , x 1 , x 2 , x 3 ) in the system of inequalities in (4.6)-(4.10). By doing so, we obtain

R ⋆ c,u by eq.(4.6d) ≥ 3x 0 + x 1 + 1 3 x 2 (4.11a)
by eq.( 4.9)

= 3(1 -x 1 -x 2 -x 3 ) + x 1 + 1 3 x 2 (4.11b)
by eq.(4.10)

≥ 3 + 2(2x 2 + 3x 3 -M) - 8 3 x 2 -3x 3 (4.11c) by eq.(4.7) ≥ 3 -2M. (4.11d)
Similarly, we can obtain

R ⋆ c,u ≥ - 2 3 M + 5 3 , (4.12)
R ⋆ c,u ≥ -

1 3 M + 1. (4.13)
The maximum among the right-hand sides of (4.11d), (4.12) and (4.13) give a piecewise linear curve with corner points: (0, 3), (1, 1), (2, 1 3 ), [START_REF] Bastug | Living on the edge: The role of proactive caching in 5g wireless networks[END_REF]0). Since these corner points are achieved by R c,u,MAN [t] for t ∈ [0 : 3], in (1.1b), we conclude that the two-phase strategy in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] is optimal under the constraint of uncoded cache placement in this case. Note that this shows that demand vectors with distinct demands lead to the worst case load.

We are now ready to extend the reasoning in Example 2 to a general setting, where not necessarily

K ≤ N.
Proof of Theorem 4. Consider a system with uncoded cache placement and a demand vector with min(K, N) distinct demanded files. We treat the delivery phase of this caching scheme as an IC problem, as described in Section 2.6. We derive a converse bound on R ⋆ c,u using Theorem 2. A directed graph can be generated for such IC problem as described in Section 2.6; Lemma 2 in Appendix A.4 gives the sets of nodes not containing a directed cycle as follows. Let u = (u 1 , u 2 , . . . , u min(K,N) ) be a permutation of C, where C is the chosen user set with different demands. A set of nodes not containing a directed cycle in the directed graph of the corresponding IC problem can be composed of sub-files

F du i ,W i : W i ⊆ [K]\{u 1 , . . . , u i }, i ∈ [min(K, N)] . ( 4
R ⋆ c,u ≥ i∈[min(K,N)] W i ⊆[K]\{u 1 ,...,u i } |F du i ,W i | B . (4.15)
Note that, in the bound in (4.15), the number of

F k,W 's such that |W| = t is i∈[min(K,N)] K-i t , while the total number of F k,W 's such that |W| = t is N K t .
By considering all sets C of users with min(K, N) different demands, and all the permutations u of C, we can list all the inequalities in the form of (4.15) and sum them together to obtain

R ⋆ c,u ≥ t∈[0:K] K-1 t + K-2 t + • • • + K-min(K,N) t K t x t (4.16a) = t∈[0:K] K t+1 -K-min(K,N) t+1 K t x t , (4.16b)
where from (4.16a) to (4.16b) we used the Pascal's triangle equality, where the set of coefficients (x 0 , . . . , x K )

as defined in (4.7) can be interpreted as a probability mass function (see (4.9)) subject to the first-moment constraint given in (4.10).

Next, by Fourier-Motzkin elimination of x q and x q-1 in (4.16b) for each q

∈ [K] (see Appendix A.2),
we obtain the bound given in (4.1a). The bound in (4.1a) is a family of straight lines parameterized by

q ∈ [K].
The lines for q = t and q = t -1 intersect at the point in (4.1c) because the coefficients

c t := ( K t+1 )-( K-min(K,N) t+1 ) ( K t )
decreases monotonously in t ∈ [K -1]. This concludes the proof.

Remark 1. In [START_REF] Yu | The exact rate-memory tradeoff for caching with uncoded prefetching[END_REF], the authors propose a genie-aided converse bound to arrive to the very same inequalities as in (4.15), which were originally derived in [START_REF] Wan | On the optimality of uncoded cache placement[END_REF], [START_REF]On caching with more users than files[END_REF] by leveraging the IC acyclic converse bound.

These two approaches are equivalent. Firstly, the acyclic converse bound can be proved by providing genie information to the receivers in the acyclic set. Secondly, the following steps in [START_REF] Yu | The exact rate-memory tradeoff for caching with uncoded prefetching[END_REF] are also the same as in our original work [START_REF] Wan | On the optimality of uncoded cache placement[END_REF], [START_REF]On caching with more users than files[END_REF], namely, summing all the inequalities, bounding the load by

(x t : t ∈ [0 : K])
defined in (4.7), and eliminating the x t 's to get the final bound. The only difference is that we used Fourier-Motzkin elimination while the authors in [START_REF] Yu | The exact rate-memory tradeoff for caching with uncoded prefetching[END_REF] treated (x t : t ∈ [0 : K]) as a probability mass function and optimized the bound over all probability mass functions (see (4.9)) with a given constraint on the the first moment (see (4.10)).

Remark 2. Our proposed converse bound can be generalized to different memory sizes

(M 1 , . . . , M K ) or file lengths (B 1 , . . . , B N )
, where where the memory size of user

i ∈ [K] is M i and the file size of file j ∈ [N]
is L j , or average load. In the above cases, we define the optimal load under the constraint of uncoded cache placement as R c,low , where R c,low is lower bounded as

d∈[N] K Pr[d]R d ≤ R c,low (in case of average load), (4.17)
or as

R d ≤ R c,low (in case worst-case load), (4.18)
where we can optimize over the lengths of the subfiles subject to

W⊆[K] |F j,W | = B j , ∀j ∈ [N], (file length), (4.19) j∈[N] W⊆[K]:u∈W |F j,W | ≤ M u , ∀u ∈ [K], (cache size), (4.20) i∈[min(K,N)] W i ⊆[K]\{u 1 ,...,u i } |F du i ,W i | ≤ R d , ∀d ∈ [N] K ,
∀permutation u of each largest user set with distinct demands (acyclic outer bound). (4.21)

Optimality of the Proposed Converse Bound

In this section, we prove that our converse bound in Theorem 4 is indeed achievable.

Theorem 5. The caching converse bound in Theorem 4 is achievable by the cMAN cache placement and a delivery scheme based on the IC achievable bound in Theorem 3.

Proof. For centralized cache-aided systems under the constraint of uncoded cache placement, for N ≥ K the claim is true because the converse bound in (4.1c) coincides with the cMAN scheme in (1.1b), and for N < K because Theorem 3 achieves (4.1c) as showed next.

We use the same placement phase as cMAN for M = t N K , for t ∈ [0 : K], so that the delivery phase is equivalent to an IC problem with K users in which each sub-file F i,W , for i ∈ N(d), W ⊆ [K] and |W| = t, is an independent message, and where the desired message and side information sets are given by (2.18) and (2.19), respectively. Note that the message rates in this equivalent IC problem are identical by construction and the number of messages for the worst case-load is N ′ = min(N, K) K t . In Theorem 3, following Example 1, we let K j = D j for j ∈ [K], we represent F i,W as a binary vector of length B/ K t bits (assumed to be an integer without loss of generality) and we let the corresponding random variable U to be equal to the message. We also let X P to be non zero only for the linear combinations of messages sent by the scheme in [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF]. With this we have

R sym = H(U ) = B/ K t and log 2 (|X |) = H(X) = B K t K t + 1 - K -min(N, K) t + 1 , (4.22)
so the symmetric rate is

R sym = 1 K t+1 -K-min(N,K)| t+1 log 2 (|X |) bits ch.use . (4.23)
Each receiver in the original caching problem is interested in recovering K t messages, or one file of B bits, thus the 'sum-rate rate' delivered to each user is for the case N < K uses Theorem 3 and gives an interpretation of the achievable scheme proposed in [START_REF] Yu | The exact rate-memory tradeoff for caching with uncoded prefetching[END_REF] via the framework of 'source coding with side information.' Our approach has the advantage that it applies to any IC scheme, and when applied to the caching problem is not limited to binary linear codes for the specific cMAN placement as that of [START_REF] Yu | The exact rate-memory tradeoff for caching with uncoded prefetching[END_REF].

R sum-rate = K t K t+1 -K-min(N,K) t+1 log 2 (|X |) bits ch.use . ( 4

Decentralized Cache-aided Systems with Uncoded Placement

In this section we consider decentralized cache-aided systems with uncoded cache placement. The delivery phase in the achievable scheme for such systems can be divided into several independent delivery phases of a centralized caching scheme, each one dealing with the sub-files known/cached by the same number of users, as originally proposed in dMAN.

In the following, we give the modelization of a decentralized caching scheme. Given a cache realization as a result of an uncoded placement function as defined in (2.10), let

X j,b,u = 1 if user u ∈ [K] cached bit b ∈ [B] of file j ∈ [N]
, and zero otherwise. The number of bits cached by user u ∈ [K] is

|Z u | = j∈[N] b∈[B] X j,b,u . (4.25)
The number of bits of file j ∈ [N] cached only by the users in

W ⊆ [K] is |F j,W | = b∈[B] u∈W X j,b,u   k ∈W (1 -X j,b,k )   . (4.26) Define Y t := 1 NB max j∈[N], W⊆[K]:|W|=t {|F j,W |}, t ∈ [0 : K], (4.27)
which is the length (normalized by NB) of the longest sub-files needed for cMAN-type linear combinations as in (2.15) involving the sub-files only cached by t users. Similarly define

X t := 1 NB j∈[N] W⊆[K]:|W|=t |F j,W |, t ∈ [0 : K]. (4.28) Clearly X t ≤ N K t Y t , t ∈ [0 : K], with equality if and only if |F j,W | only depends on t = |W|, but neither j ∈ [N] nor W ⊆ [K].
Based on the same reasoning we used for the centralized scheme in Section 4.2, the right hand side of (4.16b) with x t replaced by X t provides a lower bound on the load, and with x t replaced by N K t Y t provides an upper bound on the load. For the probability of error in (2.11) we have that the 'caching error' event is

E caching error := K k=1    |Z u | NB = 1 NB j∈[N] b∈[B] X j,b,u > M N    ; (4.29)
and the 'decoding error' is

E decoding error := K k=1 F k = F d k ; (4.30)
with this, the probability of error can be bounded as

P (B) err,d ≤ Pr[E caching error ] + Pr[E decoding error |E c caching error ]. (4.31)
Assume there is an uncoded cache placement in (2.10) such that:

A1: Pr K k=1 1 NB j∈[N] b∈[B] X j,b,u > M N → 0 as B → ∞, and
A2: for some deterministic non-negative vector (ℓ 0 , . . . , ℓ K ) such that i∈[0:K] ℓ K = 1 we have that

|F j,W | B → ℓ |W| as B → ∞ in probability, for all j ∈ [N] and W ⊆ [K] (which implies lim B→∞ Pr[|X t - N K t Y t | > ǫ] = 0 for all t ∈ [0 : K] and all ǫ > 0).
Then, clearly, the optimal delivery for this uncoded cache placement gives the load

R(ℓ 0 , . . . , ℓ K ) := t∈[0:K] K t+1 -K-min(K,N) t+1 K t ℓ t . (4.32)
Therefore finding the optimal uncoded placement for a decentralized cache-aided system is equivalent to find placement probability mass functions in (2.10) such that the conditions in A1 and A2 are satisfied and result in a PMF (ℓ 0 , . . . , ℓ K ) that minimizes the rate in (4.32), An example of placement probability mass functions in (2.10) such that the conditions in A1 and A2 are satisfied -that is, the one on dMAN is not the only one; possibly there are others. Fix an arbitrary ǫ ∈ (0, 1)

and let each user cache each bit of each file in an iid Bernoulli(q) fashion with q := M Nǫ. The probability that the placement violates the cache memory size is

Pr[E caching error ] = Pr   N j=1 B b=1 X j,b,u > MB for some u ∈ [K]   (4.33a) = 1 -   1 -Pr   1 NB N j=1 B b=1 X j,b,1 > M N     K (4.33b) = 1 -1 -e -NB• D( M N M N -ǫ)+O 1 NB K (4.33c) ≤ 1 -   1 -e -NB• ǫ 2 2 M N ( 1-M N ) +O 1 NB    K (4.33d) = K k=1 K k (-1) k+1 e -k•NB• ǫ 2 2 M N ( 1-M N ) +O 1 NB → 0 as B → ∞. ( 4
|F j,W | B → (q) |W| (1 -q) K-|W| ; (4.34) X t → K t (q) t (1 -q) K-t , t ∈ [0 : K]; (4.35) N K t Y t → K t (q) t (1 -q) K-t , t ∈ [0 : K]. (4.36)
Therefore, we conclude that the load is

t∈[0:K] K t+1 -K-min(K,N) t+1 K t ℓ t (4.37a) = t∈[0:K] K t + 1 - K -min(K, N) t + 1 (q) t (1 -q) K-t | q= M N -ǫ (4.37b) = 1 -q q 1 -(1 -q) min(K,N) | q= M N -ǫ (4.37c) = 1 -M N M N 1 -1 - M N min(K,N) -O(ǫ). (4.37d)
Theorem 6. In decentralized cache-aided systems under the constraint that each user randomly, uniformly and independently chooses MB bits of the N files to store, the optimal load is in (1.6), which can be achieved by the novel IC achievable bound in Theorem 3.

Proof. The delivery phase in the achievable scheme for such systems can be divided into several independent delivery phases of a centralized caching scheme, each one dealing with the sub-files known/cached by the same number of users, as originally proposed in [START_REF]Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF] for the dMAN scheme.

As shown in our past work [START_REF] Wan | On caching with uncoded cache placement[END_REF], assuming that each bit of each file has the same probability of being cached at each user's cache as in [START_REF]Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF], then the load of dMAN in (1.5b) is optimal for N ≥ K. In [START_REF] Yu | The exact rate-memory tradeoff for caching with uncoded prefetching[END_REF] the optimal load for N < K was shown to be achieved essentially following the dMAN original idea, but with the fundamental observation that certain transmitted linear combinations sent by dMAN are redundant when K > N, leading to the load in (1.6).

For N < K, by following the same proof idea of [START_REF]Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF] and by using as a building block for the delivery phase the novel IC achievable bound in Theorem 3, we can provide an alternative poof for the optimality of (1.6) to that given in [START_REF] Yu | The exact rate-memory tradeoff for caching with uncoded prefetching[END_REF]. The detailed steps are not reported because they are the same as those in Section 4.2.2 but repeated for every t ∈ [0 : K -1] (as opposed to for a single value of t).

Remark 4. We conclude this section by noting that in [START_REF]Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF] the authors claimed that when each user randomly and uniformly stores MB/N bits of each file and B → ∞, the length of each sub-file only depends on the number of users who cached it by the Law of Large Numbers. Recall that the placement phase is as follows.

Each user k ∈ [K] randomly and uniformly choose a set of MB bits of the N files. For each user, there are NB MB choices with identical probability. After the placement phase, let F j,W be the set of bits of F j only known by users in W, where j ∈ [N] and W ⊆ [K]; we have

W⊆[K] |F j,W | = B for each j ∈ [N],
and

j∈[N] W⊆[K]:k∈W |F j,W | = MB.
In [START_REF]Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF] it was claimed that the one can use the Law of Lange Numbers to determine the limit |F j,W |/B for large B. However, since the number of stored bits in each cache is fixed, the events that a particular bit is stored are neither independent nor uncorrelated. Thus, the Law of Large Numbers can not be used directly. In Appendix A.5 we provide a proof for the claim in [START_REF]Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF] without using of the Law of Large Numbers.

Part 2

Coded Caching in Combination Networks

Chapter 5

System Model and Some Known Results

System Model of Combination Networks with End-user-caches

Consider the combination network with end-user-caches illustrated in Fig. 1.4. The server has access to N files denoted by {F 1 , • • • , F N }, each composed of B bits, and is connected to H relays through H errorfree and interference-free links. The relays are connected to K = H r users through r K error-free and interference-free links.

We let

K i := H -i r -i , i ∈ [0 : r], (5.1)
where K 0 = K is the number of users in the system, K 1 is the number of users connected to each relay, and K i represents the number of users that are simultaneously connected to i relays.

The subset of users connected to relay h ∈ [H] is denoted by U h , and the subset of relays connected to user k ∈ [K] by H k . For a subset of users J ⊆ [K], the set of relays connected to all the users in J is denoted by

R J := ∩ k∈J H k . (5.2)
For a subset of users J ⊆ [K], the set of relays connected to at least one user in J is denoted by

H J := ∪ k∈J H k . (5.3)
For a subset of relays Y ⊆ [H], the set of users who are simultaneously connected to all the relays in Y is denoted by

U Y := ∩ h∈Y U h . ( 5
G Y := k ∈ [K] : |H k ∩ Y| ≥ 2 . (5.5)
For a subset of relays Y ⊆ [H], the set of users whose connected relays are all in Y is denoted by

K Y := {k ∈ [K] : U k ⊆ Y}. (5.6)
We define the collection of the common users of each two relays as

S := {U J : J ⊆ [H], |J | = 2}. (5.7)
For a given integer t, the t-subsets of users for which there exists at least one relay connected to all the users in this subset is denoted as

Z t := W ⊆ [K] : |W| = t, R W = ∅ . (5.8)
By the inclusion-exclusion principle [68, Theorem 10.1]

|Z t | = r n=1 H n K n t (-1) n-1 , (5.9)
and moreover, from the definition of K i in (5.1), we have

t|Z t | K 0 = r n=1 H n K n K 0 K n -1 t -1 (-1) n-1 (5.10a) = r n=1 r n K n -1 t -1 (-1) n-1 . (5.10b)
For the network in Fig. 1.4, we have

U 1 = {1, 2, 3}, U 2 = {1, 4, 5}, U 3 = {2, 4, 6}, U 4 = {3, 5, 6}.
and thus, for instance,

H 1 = {1, 2}, R {1,2} = {1}, H {1,2} = {1, 2, 3}, U {2,3} = U 2 ∩ U 3 = {4}, G {1,2,3} = {1, 2, 4}, K {1,2,3} = {1, 2, 4}, S = [6],
and Z 1 contains all the 1-subsets of [START_REF] Birk | Informed source coding on demand (iscod) over broadcast channels[END_REF], while Z 2 contains all the 2-subsets of [START_REF] Birk | Informed source coding on demand (iscod) over broadcast channels[END_REF] with the exception of {1, 6}, {2, 5}, {3, 4}. is revealed to all nodes. Given (d, Z), the server sends a message

X h of B R h (d, Z, M) bits to relay h ∈ [H]. Then, relay h ∈ [H] transmits a message X h→k of B R h→k (d, Z, M) bits to user k ∈ U h . User k ∈ [K] must recover its desired file F d k from Z k and (X h→k : h ∈ H k )
with high probability for some file size B. The objective is to determine optimal the max-link load in centralized systems defined as

R ⋆ c := min Z max d∈[N] K max{R s→r , R r→u }, (5.11)
R s→r = max h∈[H] R h (d, Z, M), (5.12
)

R r→u = max h∈[H],k∈U h R h→k (d, Z, M), (5.13)
where R s→r denotes the max link-load from the server to relays, and R r→u denotes the max link-load from the relays to users. Since the max-link load of the uncoded routing scheme in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] is R routing = K(1 -M/N)/H, we define the coded caching gain g of a scheme with max-link load R as

g := R routing R = K(1 -M/N)/H R . (5.14)
By the cut-set bound in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF], g ≤ K 1 . It is obvious that when M = 0, and M = N, the coded caching gain is 1.

Systems with Uncoded Cache Placement

The max-link load under the constraint of uncoded cache placement is denoted by

R ⋆ c,u . In general, R ⋆ c,u ≥ R ⋆ .
After the uncoded placement phase is concluded, each file can be effectively divided into non overlapping sub-files depending on which user stores which bit. Let

T Z := F i,W : i ∈ [N], W ⊆ [K] ,
where

F i,W
is the set of bits of the file F i stored solely by the users in W. The set of requested sub-files according to the demand vector d ∈ [N] K is denoted by

T d,Z := F d k ,W : k ∈ [K], W ⊆ [K], k / ∈ W ⊂ T Z . (5.15)
After the uncoded cache placement and the demand vector are revealed, the delivery phase for the sub- over J does not contain a directed cycle, then the "acyclic index coding converse bound" in Theorem 2 for the shared-link broadcast networks can be used to lower bound for the max-link load as a function of the total number of bits of the sub-files in J (see Proposition 1).

files in T d,

Caching Scheme in [50, Theorem 1]

We state here the state-of-the-art scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] for the case of no cache at the relays; the scheme uses MDS-based coded placement so as the delivery from each relay is equivalent to that of a shared-link network serving K 1 virtual users and where the operations of the H virtual shared-link networks are not coordinated.

In particular, each file is divided into r non-overlapping and equal-length pieces that are encoded by an (H, r)

MDS code. The h-th MDS-coded symbol is denoted by s h i and must be delivered by relay h ∈ [H] to the users in U h following the MAN scheme [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF]. This is done as follows.

Placement Fix g ∈ [1 : K 1 ]. The MDS-coded symbol s h i is partitioned into K 1 g-1 non-overlapping and equal-length subfiles as s h i = {s h i,W : W ⊆ U h , |W| = g -1} (recall |U h | = K 1 for all h ∈ [H]).
There are in total

n = H K 1 g -1 [subfiles per file]. (5.16) User k ∈ [K] caches s h i,W if k ∈ W from all h ∈ H k (recall |H k | =
r for all users), for a total of

k 1 = r K 1 -1 g -2 [subfiles per file].
(5.17)

Delivery The MAN-like multicast coded message

w h J = ⊕ k∈J s h d k ,J \{k} , ∀J ⊆ U h : |J | = g, h ∈ [H], (5.18)
is delivered from the server to relay h, who then forwards it to the users in J . User k ∈ [K], thanks to its cache content and the received multicast coded messages from the relays in H k , recovers

k 2 = r K 1 -1 g -1 [subfiles per file]. (5.19)
Performance Each user eventually knows k 1 + k 2 = r K 1 g-1 subfiles of its desired file (either cached or delivered), which suffices to recover all the n = H K 1 g-1 subfiles of its desired file because of the (H, r) MDS encoding before placement, where k 1 , k 2 and n are defined in (5.17), (5.19) and (5.16), respectively.

Since each multicast coded message in (5.18) transmitted from the server is simultaneously useful for g users, the max link-load from the server to relays is K(1 -M ZY /N)/(Hg). In addition, since

|s h d k 1 ,J \{k 1 } | = |s h d k 2 ,J \{k 2 }
| for each relay h, each set J ∈ U h and any k 1 , k 2 ∈ J , and each user recovers B(1-M ZY /N)/r bits from r relays, the load on each link from relays to users is (1 -M ZY /N sf )/r. With K/(Hg) ≥ r, the max link-load is K(1 -M ZY /N)/(Hg). To achieve coded caching gain g, the required memory size per file is

M ZY N = k 1 k 1 + k 2 = g -1 K 1 (5.20)
where in (5.20) the factor H r is the inverse of the rate of the MDS code used before placement.

Limitation In [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF], the operations at the H relays are uncoordinated. Indeed, consider the network in Fig. 1.4 for g = 2. The scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] uses an (H, r) = (4, 2) MDS code, and the MDS-coded symbols s h 1 i,W and s h 2 i,W are treated as two "independent" subfiles if h 1 = h 2 . For example, among the MDS subfiles

s 1 i,{1} , s 1 i,{2} , s 1 i,{3} , s 2 i,{1} , s 2 i,{4} and s 2 i,{5}
, each of length is B/6, user 1 caches s 1 i,{1} and s 2 i,{1} , which requires M/N = 2/6. However, s 1 i,{1} and s 2 i,{1} can be treated as a single subfile known / cached by user 1. This observation is key for the design of the novel proposed schemes.

Bit-Borrowing

To conclude this section, we introduce the bit-borrowing idea proposed in [START_REF] Wan | Novel delivery schemes for decentralized coded caching in the finite file size regime[END_REF], [START_REF] Ramakrishnan | An efficient delivery scheme for coded caching[END_REF], which we will also use in our novel delivery scheme. For decentralized shared-link caching problems with non-uniform demands or finite file size B, the subfiles in (2.14) may have different lengths. If this is the case, instead of zero-padding the sub-files to meet the length of the longest one, which leads to inefficient transmissions, we can borrow bits from some subfiles to 'lengthen' short sub-files in such a way that the borrowed bits need not to be transmitted at a later stage. More precisely, if |F d ℓ ,J \{ℓ} | < max k∈J |F d k ,J \{k} |, we take bits from some F d ℓ ,W , where ℓ / ∈ W and J \{ℓ} ⊂ W (because F d ℓ ,W is also demanded by user ℓ and known by the users in J \{ℓ}) and add those bits to F d ℓ ,J \{ℓ} .

Chapter 6

Novel Converse Bounds for Combination Networks with End-user-caches

Chapter Overview and Related Publications

This chapter provides novel converse for combination networks with end-user-caches. The main idea is to adapt the converse bounds in shared-link models and the acyclic index coding converse bound with the network topology. We first use a cut-set strategy to directly extend the converse bounds for shared-link networks to combination networks. We then propose two ways to tighten the acyclic index coding converse bound in combination networks.

Related Publications

Main Results on Novel Converse Bounds for Combination Networks with End-user-caches

To derive bounds on the max link-load for combination networks with end-user-caches, we can use the cutset strategy proposed in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] to extend converse bounds for cache-aided shared-link models. More precisely, each time we consider the cut of x ∈ [r : H] relays. The total link load transmitted from the server should be outer bounded by the load in shared-link model including N files, x r users with memory of MB bits. So we can use this strategy to extend any converse bounds for shared-link models to combination networks. Based on this strategy, in the following we extend the enhance cut-set converse bound in (1.4) and the converse bound under the constraint of uncoded cache placement in Theorem 4.

Theorem 7. For an (H, r, M, N) combination network, the max link-load should satisfy

R ⋆ c ≥ R ⋆ e := s -1 + α -s(s-1)-l(l-1)+2αs 2(N-l+1) M x , x ∈ [r : H]. (6.1)
for any α ∈ 1, . . . , min{N, x r } , α ∈ [0, 1], where l ∈ [1 : s] is the minimum value such that s(s-1)-l(l-1) 2

+ αs ≤ (Nl + 1)l 2 .

Theorem 8. Consider a combination network with end-user-caches, under the constraint of uncoded cache placement, the max link-load should satisfy Recall that p(J ) := p 1 (J ), . . . , p |p(J )| (J ) representing a permutation of elements of the set J . We then propose the following lower bound which is tighter than the cut-set converse bound in (6.2). Since it follows quite straightforwardly from the work we did for shared-link broadcast networks [START_REF] Wan | On the optimality of uncoded cache placement[END_REF], in this thesis we consider it as the 'baseline' bound. The proof is in Section 6.4.

R ⋆ c,u M = t N x r ≥ 1 x ( x r ) t+1 - max ( x r )-N,0 t+1 ( x r ) t , x ∈ [r : H]. ( 6
|Q|R ⋆ c,u ≥ i∈[|K Q |] W⊆[K]\{p 1 (K Q ),...,p i (K Q )}
x W , (6.3a)

x W := 1 NB i∈[N] |F i,W |, ∀W ⊆ [K] : W⊆[K] x W = 1, (6.3b
)

W⊆[K]:i∈W x W ≤ M N , ∀i ∈ [K]. ( 6
partition Q = Q 1 ∪ . . . ∪ Q a where |Q i | ≥ r and i ∈ [a]
, and each combination of permutations

p(K Q 1 ), . . . , p(K Qa ), p K Q \ (K Q 1 ∪ • • • ∪ K Qa ) , the following must hold for B ≫ 1 |Q|R ⋆ c,u ≥ i∈[a] j∈[|K Q i |] W⊆[K]\∪ k∈[j] {p k (K Q i )} x W + j∈ K Q \V W⊆([K]\V)\∪ k∈[j] {p k (K Q \V)} x W , (6.4
)

where V := ∪ i∈[a] K Q i .
Remark

Q:|Q|=b y Q ≥ i∈[K] W⊆[K]\∪ j∈[i] {p j ([K])} c {p i ([K])} ∪ W, b x W , (6.5a) c(W 1 , l) :=max H -1 l -1 -|{Q⊆[H]:|Q|=l, K Q [K] \ W 1 }|, 0 . (6.5b)

Remark 7. The lower bound in Theorem 11 can be computed by means of a linear program with variables

(R ⋆ c,u , x W : W ⊆ [K], y Q : Q ⊆ [H]
) and constraints in (6.39), (6.5a), (6.3b) and (6.3c). By combining the converse bound ideas in Theorem 10 and 11, our final converse bound is as follows (the proof can be found in Section 6.7).

Theorem 12. Consider a combination network with uncoded cache placement and (d, Z) such that the

demands are distinct. For each integer b ∈ [r : H], each set of relays Q ⊆ [H] with |Q| = b, each integer a ∈ [⌊b/r⌋], each disjoint partition Q = Q 1 ∪ . . . ∪ Q a where |Q i | ≥ r and i ∈ [a], each combination of permutations p(K Q 1 ), . . . , p(K Qa ), p K Q \ (K Q 1 ∪ • • • ∪ K Qa ) , with B ≫ 1, the following must hold |Q|R ⋆ c,u ≥ i∈[a] j∈[|K Q i |] W⊆[K]\∪ k∈[j] {p k (K Q i )} x W + j∈ K Q \V W⊆([K]\V)\∪ k∈[j] {p k (K Q \V)}
x W + y Q , (6.6) satisfying (6.3b), (6.3c) and (6.5a), where

V := ∪ i∈[a] K Q i .

Remark 8. The lower bound in Theorem 12 can be numerically computed by means of a linear program with variables

(R ⋆ c,u , x W : W ⊆ [K], y Q : Q ⊆ [H]
) and constraints in (6.6), (6.5a), (6.3b) and (6.3c). Notice that the computation complexity orders of all theorems reported in this thesis are the same with O(2 K ) variables and O(HK!) constraints.

Preliminaries

We first extend the shared-link broadcast networks "acyclic index coding converse bound" from [START_REF] Wan | On the optimality of uncoded cache placement[END_REF] to combinations networks. (d,Z) such that the demands in d are distinct. For a set of relays J ⊆ [H], and for an acyclic set of sub-files S ⊆ T d,Z in the directed graph G T d,Z that are demanded by the users in K J , the following must hold

Proposition 1. Consider a combination network with uncoded cache placement and

H(S) ≤ H(X J |S c ) + Bε B (6.7a) ≤ |J |B R ⋆ c,u + Bε B . (6.7b)
Proof. The entropy of the sub-files in S is bounded as

H(S) = H(S|S c ) = H(X J , S|S c ) (6.8a) = H(X J |S c ) + H(S|X J , S c ) (6.8b) ≤ H(X J |S c ) + Bε B (6.8c) ≤ H(X J ) + Bε B (6.8d) ≤ |J |R ⋆ c,u B + Bε B , (6.8e)
where in (6.8a) we used the independence of the sub-files and the fact that X J is function of T d,Z , in (6.8c)

we use the fact that S is acyclic and Fano's inequality (where lim B→∞ ε B = 0), and in (6.8e) we used the definition of R ⋆ c,u .

Proposition 1 may not be tight when |J |R ⋆ c,u in (6.8e) is strictly larger than H(X J |S c ) in (6.8c). In the following, we tighten the bound in Proposition 1. , where S 1 includes some sub-files demanded by the users in K J and S 2 includes some sub-files demanded by the users in [K] \ K J but not cached by the users in K J , we have

H(S 1 ) + H(X J |S c 2 ) ≤ |J |B R ⋆ c,u + 2Bε B . (6.9)
Proof. The entropy of the sub-files can be bounded as

H(S 1 , S 2 ) ≤ H X [H] |(S 1 ∪S 2 ) c + Bε B (6.10a) = H X J |(S 1 ∪S 2 ) c + H X [H]\J |X J , S c 2 + I S 1 ; X [H]\J |X J , (S 1 ∪S 2 ) c + Bε B (6.10b) ≤ |J |B R ⋆ c,u + H X [H]\J |X J , S c 2 + H S 1 |X J , (S 1 ∪S 2 ) c + Bε B (6.10c) ≤ |J |B R ⋆ c,u + H X [H]\J |X J , S c 2 + 2Bε B (6.10d) ≤ |J |B R ⋆ c,u -H X J |S c 2 + H(S 2 ) + 2Bε B , (6.10e)
where (6.10a) is from (6.7a), where (6.10d) is from Fano's inequality (where lim B→∞ ε B = 0) and the fact S 1 is acyclic and S 2 does not include the side information of the user requesting S 1 , and where (6.10e) is because

H(S 2 ) = H(S 2 |S c 2 ) (6.11a) = H S 2 , X [H] |S c 2 (6.11b) ≥ H X [H] |S c 2 (6.11c) = H X J |S c 2 + H X [H]\J |X J , S c 2 . (6.11d)
This concludes the proof.

Finally, we generalize the well-known sub-modularity of entropy.

Proposition 3. Let Y be a set of random variables, and M be a set of mutually independent random Proof. Without loss of generality, assume M 1 = {M 0 , M 1 } and M 2 = {M 0 , M 2 }, where M 0 , M 1 , M 2 are independent random variables. We have

variables (but not necessary independent of Y). If Y 1 , Y 2 ⊆ Y and M 1 , M 2 ⊆ M, then the following must hold H(Y 1 |M 1 ) + H(Y 2 |M 2 ) ≥ H(Y 1 ∪ Y 2 |M 1 ∪ M 2 ) + H(Y 1 ∩ Y 2 |M 1 ∩ M 2 ). ( 6
H(Y 1 |M 0 , M 1 ) + H(Y 2 |M 0 , M 2 ) (6.13a) = H(Y 1 |M 0 , M 1 , M 2 ) + I(Y 1 ; M 2 |M 0 , M 1 ) + H(Y 2 |M 0 , M 1 , M 2 ) + I(Y 2 ; M 1 |M 0 , M 2 ) (6.13b) = H(Y 1 ∪ Y 2 |M 0 , M 1 , M 2 ) + I(Y 1 ; Y 2 |M 0 , M 1 , M 2 ) + I(Y 1 ; M 2 |M 0 , M 1 ) + I(Y 2 ; M 1 |M 0 , M 2 ) (6.13c) ≥ H(Y 1 ∪ Y 2 |M 0 , M 1 , M 2 ) + H(Y 1 ∩ Y 2 |M 0 ), (6.13d)
where the last inequality follows from with S = f d, [K], p(K Q ) provides a lower bound on R ⋆ c,u . In the limit for B ≫ 1, by summing all the so obtained bounds for a fixed Q ⊆ [H] we arrive at (6.3a).

I(Y 1 ; Y 2 |M 0 , M 1 , M 2 ) + I(Y 1 ; M 2 |M 0 , M 1 ) + I(Y 2 ; M 1 |M 0 , M 2 ) (6.14a) = I(Y 1 ; Y 2 |M 0 , M 1 , M 2 ) + I(Y 1 , M 1 ; M 2 |M 0 ) + I(Y 2 ; M 1 |M 0 , M 2 ) (6.14b) = I(Y 1 ; Y 2 |M 0 , M 1 , M 2 ) + I(Y 1 , M 1 ; Y 2 , M 2 |M 0 ) -I(Y 1 , M 1 ; Y 2 |M 0 , M 2 ) + I(Y 2 ; M 1 |M 0 , M 2 ) (6.14c) = I(Y 1 ; Y 2 |M 0 , M 1 , M 2 ) + I(Y 1 , M 1 ; Y 2 , M 2 |M 0 ) -I(Y 1 ; Y 2 |M 0 , M 1 , M 2 ) (6.14d) = I(Y 1 , M 1 ; Y 2 , M 2 |M 0 ) ≥ I(Y 1 ; Y 2 |M 0 ) (6.14e) ≥ H(Y 1 ∩ Y 2 |M 0 ). ( 6

Proof of Theorem 10

Our first improvement to Theorem 9 is explained by way of an example.

Q = [H] = [4] and divide Q into Q 1 = {1, 2} and Q 2 = {3, 4}; so K Q 1 = {1} and K Q 2 = {6}.
We then consider the three permutations p(K Q 1 ) = (1), [START_REF] Bastug | Living on the edge: The role of proactive caching in 5g wireless networks[END_REF][START_REF] Maddah-Ali | Fundamental limits of caching[END_REF][START_REF]Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF]. Recall the definition of f given in (6.15) and let

p(K Q 2 ) = (6) and p K Q \ (K Q 1 ∪ K Q 2 ) = (2,
B 1 = f d, [K], p(K Q 1 ) = {F 1,W : W ⊆ [2 : 6]}, (6.16
)

B 2 = f d, [K], p(K Q 2 ) = {F 6,W : W ⊆ [1 : 5]}, (6.17)
B 3 = f d, [K] \ (K Q 1 ∪ K Q 2 ), p K Q \ (K Q 1 ∪ K Q 2 ) = {F i,W : i ∈ [2 : 5], W ⊆ [i + 1 : 5]}. (6.18)
By using Proposition 2 with (J , S 1 , S 2 ) = (Q 1 , B 1 , B 3 ) we get

H(B 1 ) ≤ |Q 1 |R ⋆ c,u B -H X Q 1 |B c 3 + 2Bε B . (6.19)
and with

(J , S 1 , S 2 ) = (Q 2 , B 2 , B 3 ) we get H(B 2 ) ≤ |Q 2 |R ⋆ c,u B -H X Q 2 |B c 3 + 2Bε B . (6.20)
We sum (6. [START_REF] Yu | The exact rate-memory tradeoff for caching with uncoded prefetching[END_REF]) and (6.20) to obtain

H(B 1 , B 2 ) ≤ |Q|R ⋆ c,u B -H X Q 1 |B c 3 + H X Q 2 |B c 3 + 4Bε B (6.21a) ≤ |Q|R ⋆ c,u B -H(X Q |B c 3 ) + 4Bε B (6.21b) ≤ |Q|R ⋆ c,u B -H(B 3 ) + 4Bε B , (6.21c)
where (6.21c) follows from (6.7a). With the above mentioned choice of permutations and B ≫ 1, the bound in (6.21c) becomes

4BR ⋆ c,u ≥ W⊆[6]\{1} |F 1,W | + W⊆[6]\{6} |F 6,W | + i∈[2:5] W⊆[i+1:5] |F i,W |. (6.22)
If we list all the inequalities in the form of (6.22) for all the possible demands where users demand distinct files, and we sum them all together, we obtain(the definition of x W is in (6.3b))

4R ⋆ c,u ≥ W⊆[2:6] x W + W⊆[1:5] x W + i∈[2:5] W⊆[i+1:5]
x W . (6.23)

We then consider all the possible disjoint partitions of Q, and for each partition we consider all the possible combinations of permutations to write bounds as in the form of (6.23). For Q with |Q| ≤ 3, since Q can not be divided into two sets each of which has length not less than r = 2, we directly use the bound in (6.3a). With the file length and memory size constrains in (6.3b)-(6.3c), we can compute the converse bound by a linear program with the above mentioned constraints and with variables

(R ⋆ c,u , x W : W ⊆ [K] = [6]).
By solving the linear program numerically, the lower bound on R ⋆ c,u given by the above method is 7/17 ≈ 0.411, while Theorem 9 gives 9/23 ≈ 0.391.

Remark 10. Notice that in (6.21c), |Q|R ⋆ c,u B ≥ H(B 1 , B 2 , B 3 )
where B 1 ∪ B 2 forms a directed circle. The techniques in this example provides a tighter converse bound compared to Theorem 9 because it allows to deal with cycles in the directed graph that represents the equivalent index coding problem.

We are now ready to prove Theorem 10.

At first, choose a demand vector d where users demand different files. For a set of relays Q, con-

sider one division Q = Q 1 ∪ . . . ∪ Q a where a ∈ [⌊|Q|/r⌋],
and one combination of permutations

p(K Q 1 ), . . . , p(K Qa ), p K Q \ (K Q 1 ∪ • • • ∪ K Qa ) . We let B i = f d, [K], p(K Q i ) , where i ∈ [a], (6.24)
B a+1 = f d, [K] \ (K Q 1 ∪ • • • ∪ K Qa ), p K Q \ (K Q 1 ∪ • • • ∪ K Qa ) . (6.25)
For each i ∈ [a], we use Proposition 2 with J = Q i , S 1 = B i and S 2 = B a+1 to obtain

H(B i )≤ |Q i |R ⋆ c,u B-H X Q i |B c a+1 + 2Bε B . (6.26)
We sum all the inequalities in the form of (6.26) for i ∈ [a] and sum them to obtain

i∈[a] H(B i ) ≤ |Q|R ⋆ c,u B - i∈[a] H X Q i |B c a+1 + 2aBε B (6.27a) ≤ |Q|R ⋆ c,u B -H X Q |B c a+1 + 2aBε B (6.27b) ≤ |Q|R ⋆ c,u B -H(B a+1 ) + 2aBε B , (6.27c)
where from (6.27a) to (6.27b) we use the submodularity of entropy, and from (6.27b) to (6.27c) we use (6.7a).

We list all the inequalities in the form of (6.27c) for all the possible demands where users demand different files, and sum them to obtain (6.4).

Proof of Theorem 11

For a set S and a vector p, where each element of S is also an element in p, we define g(S, p) as the vector obtained by removing the elements not in S from p, e.g., g({1, 2, 3}, (2, 4, 1, 3)) = (2, 1, 3). Our second improvement to Theorem 9 is explained by way of an example first.

|Q|BR ⋆ c,u ≥ H X Q ≥ H S 1 + H X Q |S c 2 + 2Bε B , (6.28
)

S 1 = f d, [K], p(K Q ) , (6.29)
S 2 = f d, [K] \ K Q , g [K] \ K Q , p([K]) . (6.30) If Q = {1, 2, 3} and thus K Q = {1, 2, 4}, we have g [K]\K Q , p([K]) = g {3, 5, 6}, (1, . . . , 6) = (3, 5, 6), (6.31)
H X Q |S c 2 = H X {1,2,3} f d, {3, 5, 6}, (3, 5, 6) . (6.32)
We sum all the inequalities in the form of (6.28) for all the possible demands where the users request distinct files. With B ≫ 1, we have

|Q|R ⋆ c,u ≥ j∈[|K Q |] W⊆[K]\∪ k∈[j] {p k (K Q )} x W + y Q,p([K]) , (6.33)
y Q,p([K]) := 1 BK! d:d i =d j ,i =j H X Q S c
2 with S 2 in (6.30). (6.34)

For Q = {1, 2, 3} and Q = {1, 2, 4}, we have

H X {1,2,3} A c + H X {1,2,4} B c ≥ H X {1,2,3,4} |{F 6,∅ } c + H X {1,2} A c ∩ B c (6.35a) ≥ H(F 6,∅ ) + H X {1,2} A c ∩ B c , (6.35b)
where

A := f d, {3, 5, 6}, (3, 5, 6) = F 3,W : W ⊆ {5, 6} ∪ {F 5,∅ , F 5,{6} , F 6,∅ }, (6.36)
B := f d, {2, 4, 6}, (2, 4, 6) = F 2,W : W ⊆ {4, 6} ∪ {F 4,∅ , F 4,{6} , F 6,∅ }, (6.37)
where to get (6.35a) we used Proposition 3 and the fact that A c ∪ B c = {F 6,∅ } c . Notice that without using Proposition 3 we cannot bound the sum of the two terms in the LHS (left hand side) of (6.35a). By using Proposition 3, we have the term H X {1,2,3,4} |{F 6,∅ } c and all the relays connected to user 6 demanding F 6,∅ are in {1, 2, 3, 4} such that we can use Proposition 1 to bound this term by H(F 6,∅ ). Similarly,

Q⊆[H]:|Q|=b y Q,p([K]) ≥ 1 K!B d:d i =d j ,i =j H(F 1,∅ , . . . , F 6,∅ ) = 6x ∅ . (6.38)
We then consider each permutation p(K Q ) for Q ⊆ [K] with |Q| = b = 3 to write inequalities in the form of (6.33). With the constraints in (6.3b), (6.3c) and (6.38) we can compute a lower bound on R ⋆ c,u by solving a linear program which gives 13/12, while Theorem 9 gives 17/16. Notice that in general we should consider each permutation p([K]) to write constraints in the form of (6.38), but in this example it is enough to consider one permutation. In order to reduce the number of variables, the constraint in (6.33) is equivalent to the following

|Q|R ⋆ c,u ≥ j∈[|K Q |] W⊆[K]\∪ k∈[j] {p k (K Q )} x W + y Q , (6.39)
y Q := max p([K]) y Q,p([K]) , (6.40)
satisfying for each permutation p([K]),

Q⊆[H]:|Q|=b y Q ≥ Q⊆[H]:|Q|=b y Q,p([K]) , (6.41)
where y Q,p([K]) is defined in (6.34).

Remark 11. In Theorem 9, for each set Q we have the constraint in (6.39) but without y Q . The above example shows that the sum of all the y Q 's, where |Q| = b, is positive, thus the lower bound in (6.39) is tighter than the one in Theorem 9.

We are now ready to prove Theorem 10.

Choose an integer b ∈ [r : H], a permutation p([K]). As we claimed in Section 6.6, for each set of relays Q where |Q| = b, we consider a permutation p(K Q ) to obtain the following constraint (shown in (6.39))

|Q|R ⋆ c,u ≥ j∈[|K Q |] W⊆[K]\∪ k∈[j] {p k (K Q )} x W + y Q , (6.42)
satisfying for each permutation p([K]),

Q⊆[H]:|Q|=b y Q ≥ Q⊆[H]:|Q|=b y Q,p([K]) = 1 K!B d:d i =d j for i =j Q⊆[H]:|Q|=b H(X Q |S c Q ), (6.43)
S Q := f d, [K]\K Q , g [K]\K Q , p([K]) . (6.44)
Now for one permutation p([K]) we want to compute the converse bound of

Q⊆[H]:|Q|=b H(X Q |S c Q ).
Consider two sets of relays with cardinality b, J 1 and J 2 . We can use Proposition 3 to bound

H X J 1 |S c J 1 + H X J 2 |S c J 2 ≥ H X J 1 ∪J 2 |(S J 1 ∩ S J 2 ) c + H X J 1 ∩J 2 |(S J 1 ∪ S J 2 ) c . (6.45)
Each time we use Proposition 3, we call the first term in the RHS result as 'cup' term and the second term as 'cap' term. We then add H X J 3 |S c J 3 to the RHS of (6.45), where J 3 is the third term in the sum

Q⊆[H]:|Q|=b H(X Q |S c Q ).
Firstly, we use Proposition 3 to bound the sum of the cup term of (6.45) and H(X J 3 |S c J 3 ). We put the cup term in the new RHS result at the first position, and use Proposition 3 again to bound the sum of the cap term in the RHS result of (6.45) and the cap term in the new RHS result.

The cup term of the latest one is put at the second position while the cap term is at the third position. So after considering three sets, we now have three terms. Similarly, each time we consider the j th set with cardinality b, we use Proposition 3 to bound the sum of the term in the first position of the last iteration and H X J j |S c J j . The cup term of the result is put at the first position in this iteration. The cap term of the result should be added to the term at the second position in the last iteration. We do this procedure until the term in the last position in the last iteration. We describe this iterative procedure in Algorithm 1.

Notice that when we use Proposition 3 to bound a sum of two terms, the cap term of the result may be 0.

When we use Proposition 3 to bound the sum of 0 and one term, the result is also the sum of this term (seen as the cup term) and 0 (seen as the cap term). We should also notice that after each iteration, by assuming the term at the i th

1 is H X G i 1 |I c i 1 and the term at the i th 2 is H(X G i 2 |I c i 2 ) where i 1 < i 2 , we can see that G i 2 ⊆ G i 1 and I c i 2 ⊆ I c i 1 .
Algorithm 1 Iterative Procedure by using Proposition 3

1. input: H X J i |S c J i where i ∈ [ H b ];
(each J i is a distinct set of relays with cardinality b;) initialization: t = 2;

use Proposition 3 to bound H X J 1 |S c

J 1 + H X J 2 |S c J 2 ; let L t,1 be the cup term and L t,2 be the cap term;

3. use Proposition 3 to bound L t,1 + H X J t+1 |S c J t+1 ; let L t+1,1 be the cup term and T cap be the cap term.

4. for i = 2, . . . , t, use Proposition 3 to bound L t,i + T cap and let L t+1,i be the cup term and T cap be the cap term.

5. let L t+1,t+1 = T cap .

if t < H

b -1, then t = t + 1 and go to 3).

output: i∈[( H

b )] L ( H b ),i .
After considering all the sets of relays with cardinality b, we have a summation including H b terms. In the end, for an acyclic set of sub-files S, by using Proposition 1 we have

H X [H] |S c ≥ H(S). (6.46)
Hence, we can bound this summation by a sum of the lengths of sub-files, then we obtain

Q⊆[H]:|Q|=b H(X Q |S c Q ) ≥ i∈[K] W⊆[K]\∪ j∈[i] {p j ([K])} c {p i ([K])} ∪ W, b |F d p i ([K]) ,W |, (6.47)
where c(W 1 , l)

:= H-1 l-1 -|{Q ⊆ [H] : |Q| = l, K Q [K] \ W 1
}|, which will be proved in the following. We focus on ) ,W , we can see that the number of terms in the RHS of Proposition 3 including X h not knowing F d p i ([K]) ,W decreases by 1 compared to the LHS (the number of terms in the RHS not including X h but knowing F d p i ([K]) ,W also decreases by 1 compared to the LHS); otherwise, the number of terms in the RHS including X h not knowing

|F d p i ([K]) ,W |, where W ⊆ [K] \ {p 1 ([K]), . . . , p i ([K])}. For a set of relays Q with cardinality b, in the term H(X Q |S c Q ), we can see that F d p i ([K]) ,W ∈ S Q if and only if K Q ∩ ({p i ([K])} ∪ W) = ∅, in other words K Q ⊆ [K] \ ({p i ([K])} ∪ W).
F d p i ([K]
) ,W does not change compared to the LHS. In addition, it can be checked that in any case when we use Proposition 3, the number of terms in the RHS not including X h but knowing F d p i ([K]) ,W does not increase compared to the LHS. Hence, among all of the terms in the summation after the final iteration, the number of terms including X h not knowing

F d p i ([K]) ,W is not less than max |{Q⊆[H]:|Q| = b, h ∈ Q, K Q ⊆[K]\({p i ([K])} ∪ W)}| -|{Q⊆[H]:|Q| = b, h / ∈ Q, K Q [K]\({p i ([K])} ∪ W)}|, 0 =max H -1 l -1 -|{Q⊆[H]:|Q|=l, K Q [K] \ W 1 }|, 0 . (6.48)
In addition, after the final iteration, the term at the i th 1 position is H(X G i 1 |I c i 1 ) and the term at the i th 2 position is H(X G i 2 |I c i 2 ) where i 1 < i 2 , we can see that G i 2 ⊆ G i 1 and I c i 2 ⊆ I c i 1 . So by (6.46) we have,

c(W 1 , l) = H-1 l-1 -|{Q ⊆ [H] : |Q| = l, K Q [K] \ W 1 }|
as defined in (6.5b). Finally, from (6.43), (6.47) and the value of c(W 1 , l), we can obtain (6.5a) to finish the proof.

Proof of Theorem 12

Consider one demand vector where users demand different files and one division of

Q = Q 1 ∪ • • • ∪ Q a .
We let

B i = f d, [K], p(K Q i ) , where i ∈ [a], (6.49)
B a+1 = f d, [K] \ (K Q 1 ∪ • • • ∪ K Qa ), p K Q \ (K Q 1 ∪ • • • ∪ K Qa ) (6.50) B a+2 = f d, [K] \ K Q , g [K] \ K Q , p([K]) . (6.51)
For each i ∈ [a], we write an inequality in the form of (6.9) by

J = Q i , S 1 = B i , S 2 = B a+1 ∪ B a+2 .
We then sum all of the a inequalities to obtain

i∈[a] H(B i ) ≤ |Q|R ⋆ c,u B - i∈[a] H X Q i |(B a+1 ∪ B a+2 ) c + 2aBε B (6.52a) ≤ |Q|R ⋆ c,u B -H X Q |(B a+1 ∪ B a+2 ) c + 2aBε B (6.52b) = |Q|R ⋆ c,u B -H X Q |B c a+2 -I X Q ; B a+1 |(B a+1 ∪ B a+2 ) c + 2aBε B (6.52c) = |Q|R ⋆ c,u B -H X Q |B c a+2 -H(B a+1 ) + H B a+1 |(B a+1 ∪ B a+2 ) c , X Q + 2aBε B (6.52d) ≤ |Q|R ⋆ c,u B-H X Q |B c a+2 -H(B a+1 ) + (2a + 1)Bε B , (6.52e)
where from (6.52a) to (6.52b) the submodularity of entropy is used, and from (6.52d) to ( 6

Novel Separation Based Achievable Schemes

Based on separation approach where cMAN placement in (2.13) and cMAN multicast message generation in (2.14) are used independent of the network topology, we proposed four delivery schemes to deliver cMAN multicast messages

W J = ⊕ k∈J F d k ,J \{k} to users in J where J ⊆ [K], |J | = t+1 and t = KM N ∈ [0 : K].
Recall that R J is set of relays connected to all the users in J and we define that

V 1 := {J ⊆ [K] : |J | = t + 1, R J = ∅}, (7.1)
V 2 := {J ⊆ [K] : |J | = t + 1, R J = ∅}. (7.2)
Based on Separation approach, in Section 7.2.1 we first propose an improved scheme, namely Direct Independent delivery Scheme (DIS), compared to the second scheme in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] by observing that the cMAN multicast message W J is only useful to the users in J and thus we need not to let all users recover it. The achieved max link-load in the following theorem.

Theorem 13. For a (H, r, M, N) combination network with t = KM/N ∈ [0 : K], the max link-load satisfies

R ⋆ c,u ≤ R DIS := J / ∈V 1 + J ∈V |{h ∈ [H] : U h ∩ J = 0}| H K t . (7.
3)

The tradeoff between memory size and max link-load is the lower convex envelope of the above points.

We then propose Interference Elimination delivery Scheme (IES) in Section 7.2.2 to improve DIS when M = N/K, to achieve the max link-load in the following Theorem.

Theorem 14. For a (H, r, M = N/ H r , N) combination network, the max link-load satisfies

R ⋆ c,u ≤ R IES := 1 2H K -1 - H -r r + 2r-1 r-1 (2r -1)K H 2r , (7.4)
where R IES achieved by IES if 2r -1 = p v or pq, where p, q are different primes and v is a positive integer. 1We then propose Concatenated Inner Code delivery Scheme (CICS) in Section 7.2.3, which includes two phases to deliver each W J to the users in J , to achieve the max link-load in the following theorem.

Theorem 15. For a (H, r, M, N) combination network with t = KM/N ∈ [0 : K], the max link-load is

R ⋆ c,u ≤ R CICS := J ⊆[K]:|J |=t 1 + min h∈[H] |J \ U h |/r H K t , (7.5)
where R CICS is achieved by CICS. The tradeoff between memory size and max link-load is the lower convex envelope of the above points.

By leveraging the ignored multicasting opportunities of CICS, in Section 7.2.4 we propose Improved Concatenated Inner Code delivery Scheme (ICICS).

Direct Independent delivery Scheme (DIS)

We propose a delivery scheme, namely DIS, based on the observation that each cMAN multicast message W J is only useful to the users in J ; therefore, if R J = ∅, i.e., there exists at least one relay that is connected to all the users in J , it is enough to transmit W J only to the relays in R J ; this observation motivates the next steps.

Step 1: For each J ∈ V 1 , the source divides W J into |R J | non-overlapping pieces with equal length and directly transmits each different piece to the relays in R J .

Step 2: For each J ∈ V 2 , the source node divide W J into r non-overlapping equal-length pieces, which are then encoded by an (|{h ∈ [H] : U h ∩ J = ∅}|, r) MDS code. We then transmit one different MDS symbol to each relay h ′ ∈ {h ∈ [H] : U h ∩ J = ∅}. Each user in J is connected to r relays, and thus can receive r MDS symbols of W J to recover W J .

By Step 1 and

Step 2, each user k ∈ [K] can recover all the multicast messages W J where k ∈ J and then recover the sub-file F d k ,J \{k} . The resulting load is in (7.3).

Interference Elimination delivery Scheme (IES) for the Case t = 1

We propose a delivery scheme, namely IES, for M = N/K (t = 1). Notice that when H < 2r and M = N/K, V 2 contains the sets J where no relay is connected to all the users in J with |J | = t + 1 = 2. So we have

V 2 = ∅.

Delivery of multicast messages in

V 1 For each J ∈ V 1 with V 1 in (7.
1), we divide W J into |R J | nonoverlapping and equal-length pieces, i.e., W J = {W J ,h : h ∈ R J }; we transmit W J ,h to each relay h ∈ R J . Note that each relay h ∈ R J is connected to all of the users in J . Hence, if relay h forwards W J ,h to the users in J , each user in J can recover W J . The max-link load to deliver the coded multicast messages in

V 1 is 1 2H H r -1 -H-r r .
The key idea of IES is using an interference elimination scheme to transmit the messages W J where J ∈ V 2 . We examine three examples to highlight the key idea.

Example 5 (H = 2r, r = 2). Consider the network in Fig. 1.4 with N = 6 and M = 1. Assume that d = (1 : 6), so that

V 1 = {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 6}, {3, 5}, {3, 6} V 2 = {{1, 6}, {2, 5}, {3, 4}}.
For the messages in V 1 , the server transmits W {1,2} , W {1,3} , W {2,3} to relay 1, W {1,4} , W {1,5} , W {4,5} to relay 2, W {2,4} , W {2,6} , W {4,6} to relay 3, W {3,5} , W {3,6} , W {5,6} to relay 4.

We then use an interference elimination scheme to transmit the messages W J where J ∈ V 2 and V 2 = {{1, 6}, {2, 5}, {3, 4}}. Consider user 1. User 1 is connected to relays 1 and 2, and only needs to recover W {1,6} (i.e., W {2,5} and W {3,4} are interference). In order to perform IES we transmit (with operations in some finite field2 )

X 1 := +W {1,6} + W {2,5} + W {3,4} to relay 1, X 2 := +W {1,6} -W {2,5} -W {3,4} to relay 2, X 3 := -W {1,6} + W {2,5} -W {3,4} to relay 3, X 4 := -W {1,6} -W {2,5} + W {3,4} to relay 4,
and the relays then forward what they received to the users. Then, user 1 computes X 1 + X 2 = +2W {1,6} and recovers W {1,6} . Similarly, user 2 computes X 1 + X 3 = 2W {2,5} , and so on. With this, all users recover the missing sub-files for the demanded file. Since the length of W J , equal to B/6, goes to infinity as B → ∞, we can divide each W J where J ∈ V 2 into P sub-packets with length B/(6P ) such that we can do operations among multicast messages on a finite field of size 3. Notice that each file is composed of 6P sub-packets.

The load to transmit W J where J ∈ V 2 is P/(6P ) = 1/6, while the load to transmit W J where

J ∈ V is 1/2.
Hence, the max link-load of this scheme is 2/3 = 1/2 + 1/6, coinciding with the enhanced cut-set converse bound in (6.1), while that of CICS (ICICS) and the schemes in references [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF], and [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] are 0.6875, 5/4, and 1, respectively. In the next example, we generalize IES to transmit W J where J ∈ V 2 to the case H > 2r and r = 2.

Example 6 (H > 2r, r = 2). Consider the combination network with H = 5, r = 2, M = 1 and K = N = 10.

Assume that d = (1 : 10), so that

U 1 = [1 : 4], U 2 = {1, 5, 6, 7}, U 3 = {2, 5, 8, 9}, U 4 = {3, 6, 8, 10}, U 5 = {4, 7, 9, 10}, V 2 = {1, 8}, {1, 9}, {1, 10}, {2, 6}, {2, 7}, {2, 10}, {3, 5},
{3, 7}, {3, 9}, {4, 5}, {4, 6}, {4, 8}, {5, 10}, {6, 9}, {7, 8} .

The max link-load to transmit W J where J ∈ V 1 is 3/5. For W J where J ∈ V 2 , we expand on IES introduced in Example 5.

For each subset of relays B ⊆ [H] with cardinality |B| = 2r = 4, the set of users connected to r = 2 of the chosen relays is denoted as P B and we also let

T B := {J : J ∈ V 2 , J ⊆ P B }, (7.6)
to be the set of multicast messages in V 2 which are useful to some users in P B and not useful to the users not in P B . We then use the scheme in Example 5 to transmit the codewords for the multicast messages in

T B through the relays in B.
For example, for B = {1, 2, 3, 4} we have P {1,2,3,4} = {1, 2, 3, 5, 6, 8}

and T {1,2,3,4} = {1, 8}, {2, 6}, {3, 5} ; we transmit

+ W {1,8} + W {2,6} + W {3,5} to relay 1, + W {1,8} -W {2,6} -W {3,5} to relay 2, -W {1,8} + W {2,6} -W {3,5} to relay 3, -W {1,8} -W {2,6} + W {3,5} to relay 4.
Hence, each multicast messages W J where J ∈ T {1,2,3,4} can be recovered by the users in J . We proceed similarly to transmit the codewords for the multicast messages in T B through the relays B such that each user in J can recover W J where J ∈ T B .

The load to transmit the multicast messages in V 2 is 2/5 so that the max link-load of this scheme is 3/5 + 2/5 = 1, while that of CICS (ICICS) and the schemes in references [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] and [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] are 1.05, 2.25, and 1.5, respectively.

In the final example, we generalize IES to transmit W J where J ∈ V 2 to any r ≥ 2.

Example 7 (H ≥ 2r, r > 2). Consider the combination network with H = 6, r = 3, K = N = 20, M = 1.

Assume that d = (1 : 20) so that We focus on the transmission of the multicast messages in V 2 . If H = 2r (the case H > 2r can be dealt as in Example 6), there are 2r r /2 = 2r-1 r-1 = 10 elements in V 2 . We partition V 2 into 2r-1 r-1 /(2r -1) = 2 groups where each group contains 2r -1 = 5 elements. The existence of such a partition is discussed in Appendix A.7. In this example the groups could be chosen as

U 1 = {1, 2,
G 1 = {1, 20}, {2, 19}, {3, 18}, {5, 16}, {7, 14} , (7.7
)

G 2 = {4, 17}, {6, 15}, {8, 13}, {9, 12}, {10, 11} . (7.8)
We focus on group G 1 ; the same applies to G 2 . The vector of multicast messages in G 1 is indicated by

M 1 = [W {1,20} ; W {2,19} ; W {3,18} ; W {5,16} ; W {7,14}
]. We now design a linear code for M 1 on some finite field; we denote the coding matrix by A 1 , the element on i th row j th column of A 1 by a 1,i,j , and the i th row of A 1 by A 1,i ; A 1,i × M 1 represents the codeword for M 1 transmitted to relay i ∈ [START_REF] Birk | Informed source coding on demand (iscod) over broadcast channels[END_REF].

Recall that each multicast messages W J : J ∈ G 1 is useful to the users in J and is interference to the users in ∪ J 1 ∈G 1 :J 1 =J J 1 . Our objective is to eliminate the interference caused by W J to those users who do not need it. To achieve our objective, we construct the linear code as follows.

We focus on W {1,20} (assumed to be the first element in the vector M 1 ). Firstly, on some finite field, we let i∈ [START_REF] Birk | Informed source coding on demand (iscod) over broadcast channels[END_REF] a 1,i,1 = 0.

The reason for the choice in (7.9a) will become clear later. Then, for each J 1 ∈ G 1 \{{1, 20}} we eliminate the interference caused be W {1,20} to users in J 1 = {k 1 , k 2 } (where k 1 is the user connected to relay 6) by letting3

i∈H k 1 a 1,i,1 = 0, (7.9b)
It can be seen that each set J ∈ V contains two users k 1 and k 2 for which

H k 1 ∩ H k 2 = ∅ and H k 1 ∪ H k 2 =
[H], therefore, from (7.9a) and (7.9b), we have

i∈H k 2 a 1,i,1 = 0. (7.9c)
Hence, if user k 1 and k 2 sum their received codewords from their connected relays, they can eliminate the interference caused by W {1,20} . This construction is repeated for all J 1 ∈ G 1 \{{1, 20}}. Lastly, since user

20 requires W {1,20} , we let i∈H 20 a 1,i,1 = s : s = 0. (7.9d) Since H 1 ∩ H 20 = ∅ and H 1 ∪ H 20 = [H]
, from (7.9a) and ( 7.9d), it can be seen that

i∈H 1 a 1,i,1 = -s = 0. (7.9e)
Hence, if user 1 and 20 sum their received codewords from their connected relays, they can recover W {1,20} .

To summarize, by collecting all the constraint in (7.9) we obtain the following system of equations to Similarly, we can get all the elements in A 1 .

solve            1 1 1 1 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 1            ×            a 1,1,1 a 1,2,1 a 1,3,1 a 1,4,1 a 1,5,1 a 1,6,1            =            0 0 0 0 0 s            . ( 7
Hence, for all the multicast messages W J where J ∈ G 1 , we transmit (note that the following operations can be done on a finite field with size larger than 7)

           X 1,1 X 2,1 X 3,1 X 4,1 X 5,1 X 6,1            =            +1 +1 -2 +1 -2 -2 +1 +1 -2 +1 -2 -2 +1 +1 +1 +1 +1 +1 +1 +1 +1 -2 -2 +1 +1 +1 +1 +1 -2 -2            ×         W {1,20} W {2,19} W {3,18} W {5,16} W {7,14}         . (7.11)
Similarly, for all the multicast messages W J where J ∈ G 2 , we transmit

           X 1,2 X 2,2 X 3,2 X 4,2 X 5,2 X 6,2            =            -2 -2 +1 +1 +1 -2 +1 +1 -2 +1 +1 -2 -2 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 -2 -2 +1 +1 -2 +1 -2            ×         W {4,17} W {6,15} W {8,13} W {9,12} W {10,11}         . (7.12)
Each user k ∈ J can recover W J where J ∈ G u , u ∈ {1, 1}, by summing the received codewords (corresponding to G u ) from the relays in H k .

We can now compute the max link-load. The load to transmit W J where J ∈ V 1 is 3/2. The load for the multicast messages in V 2 is 1/10. Thus, the max link-load of this scheme is 3/2 + 1/10 = 8/5, while that of CICS (ICICS) and in references [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF], and [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF]

H k ∩ H k ′ = ∅. Transmission of V 2 for H = 2r If H = 2r, we have |V 2 | = 2r r /2 = 2r-1 r-1 . We partition V 2 into 2r-1 r-1 /(2r -1) = 2r-2 r-1 -2r-2
r groups, each containing 2r -1 elements (the group division is explained in Appendix A.7). In Appendix A.6, we prove 2r-1 r-1 /(2r -1) is an integer. For each group G g , g ∈ 2r-1 r-1 /(2r -1) , the vector M g of dimension (2r -1) × 1 lists the multicast messages W J : J ∈ G g . Let m g,j denote the j th element of M g . We design a linear code, on some finite field of sufficiently large size, to transmit M g , whose coding matrix is denoted by A g . Let the element on i th row and j th column of A g be denoted by a g,i,j , the i th row by A g,i ; the message A g,i × M g is transmitted to

relay i ∈ [H].
We construct the j th column of A g , whose elements are the coefficients for the multicast messages m g,j , as follows. Firstly, we let i∈[H] a g,i,j = 0.

(7.13a)

Then, for each J 1 where J 1 ∈ G g \ {J }, we let

i∈H k 1 a g,i,j = 0, (7.13b)
where k 1 is the user in J 1 connected to relay H. Assume that k 2 is the other user in

J 1 . Since H k 1 ∩H k 2 = ∅ and H k 1 ∪ H k 2 = [H]
, from (7.13a) and (7.13b) it can be seen that

i∈H k 2 a g,i,j = 0. (7.13c)
Users k 1 and k 2 can eliminate the interference caused by W J by summing their received codewords for G g from their connected relays. Lastly, we let

i∈H k 3 a g,i,j = s : s = 0, (7.13d)
where k 3 is the user in J who is connected to relay H. Assume k 4 is the other user in J , since

H k 3 ∩H k 4 = ∅ and H k 3 ∪ H k 4 = [H]
, from (7.13a) and (7.9d), it can be seen that

i∈H k 4 a g,i,j = -s. (7.13e)
Hence, if the users in J sums their received codewords for G g from their connected relays, they can recover

W J .
By collecting all the equations in (7.13), we can write the following system of equations

C g ×       a g,1,j . . . a g,H-1,j a g,H,j       =       0 . . . 0 s       , j ∈ [2r -1]. (7.

14)

In Appendix A.7, we show how the proposed group division results in a matrix C g that is full-rank. With this, we design the j th column of A g , and then the whole matrix of A g .

Finally, each user k ∈ J can recover W J for J ∈ G g by summing the received codewords (corresponding to G g ) from the relays in H k . Having recovered the multicast messages W J where k ∈ J , user k then decodes F d k ,J \{k} .

It can be easily see tat the load to transmit the multicast messages in V is

( 2r-1 r-1 ) (2r-1)K .
Transmission of V 2 for H > 2r For each set of relays B where |B| = 2r, we find the users who are connected to r of the chosen relays, and denote them by P B . We can see that

|P B | = 2r
r . It can also be seen that

|T B | = 2r r /2 = 2r-1 r-1
where T B is defined in (7.6). So we can use the same scheme for the case H = 2r to transmit T B through the relays in B with load ( 2r-1 r-1 ) (2r-1)K such that each user k ∈ P B can recover W J where J ∈ T B and k ∈ J . Notice that since V 2 contains all the sets of two users k and k ′ where

H k ∩ H k ′ = ∅, we have ∪ B⊆[H]:|B|=2r T B = V 2 .
Hence, after considering all the sets of relay B where |B| = 2r, each user k can recover all the multicast messages W J where k ∈ J and J ∈ V 2 , and then decodes F d k ,J \{k} .

Performance The max link-load to transmit the multicast messages in V 2 is ( 2r-1 r-1 )

(2r-1)K H 2r . In Appendix A.7, we show that when 2r -1 = p v or pq, where p and q are as in the statement of Theorem 14, we can partition V 2 in such a way that IES is doable. By summing the loads for the two classes of messages, the achieved max link-load of IES is given in Theorem 14.

Concatenated Inner Code delivery Scheme (CICS)

At a high level, the proposed Concatenated Inner Code delivery Scheme (CICS) works are follows. We directly transmit each MAN message to some relays in the first phase such that each W J can be recovered by a subset of users in J ; these messages can be seen as side information for the second phase. In the second phase, we design linear combinations of the MAN messages such that the remaining users in J recover W J . We illustrate this idea by means of one example first. First phase For each J ⊆ [START_REF] Birk | Informed source coding on demand (iscod) over broadcast channels[END_REF] of size |J | = 3, we compute the set of relays each of which is connected to the largest number of users in J , that is, S J := arg max h∈[H] |U h ∩ J |. We then partition each W J into

|S J | equal-length parts, denoted as W J = {W |S J | J ,h : h ∈ S J } , and transmit W |S J | J ,h to relay h ∈ S J .
For example, for J = {1, 2, 3}, relay 1 is connected to three users in J (user 1, 2 and 3), relay 2 is connected to one user in J (user 1), relay 3 is connected to one user in J (user 2), and relay 4 is connected to one user in J (user 3). So we have S {1,2,3} = arg max h∈[H] |U h ∩ J | = 1. Therefore, we have

W {1,2,3} = {W 1
{1,2,3},1 }. As another example, for J = {1, 2, 4}, relay 1 is connected to two users in J (user 1 and 2), relay 2 is connected to two users in J (user 1 and 4), relay 3 is connected to two users in J (user 2 and 4), and relay 4 is not connected to all users in J . So we have

S J = arg max h∈[H] |U h ∩ J | = 3. Therefore, we have W {1,2,4} = {W 3 {1,2,4},1 , W 3 {1,2,4},2 , W 3
{1,2,4},3 }. After considering all the sets J , the server has sent to relay 1 (and similarly for all other relays)

W 1 {1,2,3},1 , W 3 {1,2,4},1 , W 2 {1,2,5},1 , W 2 {1,2,6},1 , W 2 {1,3,4},1 , W 3 {1,3,5},1 , W 2 {1,3,6},1 , W 2 {2,3,4},1 , W 2 {2,3,5},1 , W 3 {2,3,6},1 ,
for a total of B/15 + 6B/30 + 3B/45 = B/3 bits; these messages are then transmitted by relay 1 to the users in U 1 .

Second phase Let us first focus on W {1,2,3} = {W 1 {1,2,3},1 }. From the first phase, W 1 {1,2,3},1 can be recovered by users 1, 2, 3 from the coded message transmitted by relay 1. Hence, W 1 {1,2,3},1 need not to be transmitted again.

For W {1,2,4} = {W 3 {1,2,4},1 , W 3 {1,2,4},2 , W 3 {1,2,4},3 }, from the first phase, W 3 {1,2,4},1 can be recovered by users 1, 2 from the coded message transmitted by relay 1. Note that user 4 has not received W 3 {1,2,4},1 yet. In the second phase, we aim to transmit W 3 {1,2,4},1 to user 4. We divide W 3 {1,2,4},1 into r = 2 non-overlapping and equal-length pieces, W 3 {1,2,4},1 = {W 3 {1,2,4},1,h : h ∈ H 4 }. We then let user 4 recover W 3 {1,2,4},1,2 from relay 2, and W 3 {1,2,4},1,3 from relay 3. In order to do so, since user 1, who is also connected to relay 2, knows W 3 {1,2,4},1,2 , we put W 3 {1,2,4},1,2 into P 2 4,{1} representing the set of bits needed to be recovered by user 4 (the first entry in the subscript) from relay 2 (the superscript) and already known by user 1 (the second entry in the subscript) who is also connected to relay 2. Similarly, we put W 3 {1,2,4},1,3 in P 3 4,{2} . After considering all the pieces of the multicast messages W J , for J ⊆ [START_REF] Birk | Informed source coding on demand (iscod) over broadcast channels[END_REF] and |J | = 3, in the second phase for relay 1 we have (similarly for all other relays) . Similarly, the server transmits P 1 1,{3} ⊕ P 1 3,{1} and P 1 2,{3} ⊕ P 1 3,{2} to relay 1. The total number of transmitted bits from server to relay 1 in this phase is 2B/15. In the end, for each set J ⊆ U 1 , relay 1 then forwards

P 1 1,{2} = {W 3 {1,2,4},3,1 , W 2 {1,2,6},3,1 , W
⊕ k∈J P 1 k,J \{k} to users k ∈ U 1 if k ∈ J .
In conclusion, the achieved max link-load is 1/3 + 2/45 = 7/15, while the max link-loads of the schemes [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF], and [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] are 2/3 and 1/2, respectively.

First phase For each W J in (2.14) where J ⊆ [K] and |J | = t + 1, we find S J := arg max h∈[H] |U h ∩ J | (i.e., the set of relays each relay in which is connected to the largest number of users in J ). We then partition

W J into |S J | non-overlapping equal-length pieces and denote W J = {W |S J | J ,h : h ∈ S J }. The server transmits W |S J |
J ,h to relay h ∈ S J , and relay h ∈ S transmits W

|S J | J ,h to the users in U h .
Second phase For each W J as in the first phase the users in J ∩ U h , h ∈ S J , can recover W |S J | J ,h ; thus the second phase aims to transmit W

|S J | J ,h to the users in J \ U h . For each user k ∈ J \ U h , W |S J |
J ,h is divided into r non-overlapping and equal-length pieces and denoted as W

|S J | J ,h = {W |S J | J ,h,h ′ : h ′ ∈ H k }. We aim to let user k ∈ J \ U h recover W |S J | J ,h,h ′ from relay h ′ ∈ H k .
For relays h, h ′ and user k, where user k is connected to relay h ′ but not to relay h, we define

Q k h,h ′ := j ∈ U h ∩ U h ′ : H j ⊆ H k ∪ {h} (7.21)
and put W

|S J | J ,h,h ′ in P h ′ k,Q k h,h ′
representing the set of bits known by the users in Q k h,h ′ and to be recovered by user k from relay h ′ . Note |Q k h,h ′ | = r -1, as explained in Remark 13. Finally, for each relay h ∈ [H] and each set V ⊆ U h where |V| = r, the server transmits ⊕ k∈V P h k,J \{k} to relay h, which forwards it to the users in V.

Remark 13. The two partition steps for each W J (e.g., W

|S J | J ,h and W |S J | J ,h,h ′ )
ensure that the number of bits transmitted from the server to each relay is the same. So the achieved max link-load is proportional to 1/H. (7.21); among the relays h, h ′ user k is only connected to relay h ′ . Since the users in Q k h,h ′ are connected to relays h and h ′ simultaneously and the connected relays of these users are in the set . Hence, the total link-load to transmit W J is 1

We put

W |S J | J ,h,h ′ in P h ′ k,Q k h,h ′ where Q k h,h ′ is defined in
H k ∪ {h} including r + 1 relays, one has |Q k h,h ′ | = r+1-2 r-2 = r -1.
(assumed to be k ′ ) connected to relays in (H k ∪ {h}) \ {a} is also in J ′ . Since user k ′ is connected to relays h and h ′ , one has k ′ ∈ Q k h,h ′ . In addition, user k ′ needs to recover W |S J ′ | J ′ ,a,h ′ from relay h ′ , whose length is equal to the length of W |S J | J ,h,h ′ . Notice that W |S J ′ | J ′ ,a is directly transmitted to relay a, so W |S J ′ | J ′ ,a,h ′ is known by the r -2 users in Q k h,h ′ \ {k ′ }
( K t ) + |S J ||J \U h | r( K t )|SJ | = 1+|J \U h |/r ( K t )
. By the symmetry of combination networks, the number of transmitted bits to each relay is the same as in Theorem 15.

Improved Concatenated Inner Code delivery Scheme (ICICS)

The main idea of Improved Concatenated Inner Code delivery Scheme (ICICS) is to leverage the multicasting opportunities which are ignored in CICS. We also examine one example to highlight the improvement

W 1 {1,2,3,4},1 , W 1 {1,2,3,5},1 , W 1 {1,2,3,6},1 , W 4 {1,2,5,6},1 , W 4 {1,3,4,6},1 , W 4 {2,3,4,5},1 ,
for a total of 3B/16 bits; these messages are then transmitted by relay 1 to the users in U 1 .

Second phase of CICS Let us focus on W 4 {1,2,5,6},1 , which is directly transmitted to relay 1 in the first phase and can be recovered by users 1, 2. In the second phase, we aim to transmit W 4 {1,2,5,6},1 to users 5, 6, while considering it as side information for users 1, 2. For user 5, we partition W all such P's contains 3B/80 bits. Finally the server transmits to relay 1

P 1 1,{2} ⊕ P 1 2,{1} , P 1 1,{3} ⊕ P 1 3,{1} , P 1 2,{3} ⊕ P 1 3,{2} ,
with totally 9B/80 bits.

In the end, for each set J ⊆ U h , each relay h ∈ [H] transmits ⊕ j∈J P d j ,J \{j} to each user j ∈ J . In conclusion, the max link-load of CICS is 15 4( 63 ) + 9

4( 63 ) = 0.3 while the max link-loads of the schemes in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] and [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] are 0.375 and 1/3, respectively.

Improved First phase of ICICS This step is the same as CICS with the exception that each coded messages W J is divided into B/P packets for some large enough length P (possible since B can be taken arbitrary large). , where X 1 {1,2},{3} is the set of packets needed to be recovered by users in {1, 2} (first part of the subscript) from relay 1 (superscript) and already known by the users in {3} (second part of the subscript) who are also connected to relay 1 (superscript). The number of packets in X 1 {1,2},{3} is |X 1 {1,2},{3} |/P . We then encode the messages at relay 1 as

Improved Second phase of ICICS

X 1 {1},{2} ⊕ X 1 {2},{1} , X 1 {1},{3} ⊕ X 1 {3},{1} , X 1 {2},{3} ⊕ X 1 {3},{2} ,
where we used the same convention as before when it comes to 'summing' sets. We also send

RLC(2|X 1 {2,3},{1} |/P, X 1 {1,2},{3} ∪ X 1 {1,3},{2} ∪ X 1 {2,3},{1} ) to relay 1. Note that the users in {1, 2, 3} know |X 1 {2,3},{1} |/P packets of X 1 {1,2},{3} ∪ X 1 {1,3},{2} ∪ X 1 {2,3},{1}
. So if the server transmits 2|X 1 {2,3},{1} |/P random linear combinations of those packets to relay 1, which will then forward them to its connected users, each user can recover all of the packets of

X 1 {1,2},{3} ∪ X 1 {1,3},{2} ∪ X 1 {2,3},{1} with high probability provided that B → ∞.
The max link-load of ICICS is 15

4(

K t ) + 17 8( K t ) K=6,t=3
= 0.29375, which is less than the max link-load of CICS (equal to 0.3); for the same set of parameters, the max link-loads of the schemes in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] and [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] are 0.375 and 1/3, respectively.

The main idea of ICICS is to leverage the multicasting opportunities that were ignored in CICS, as illustrated in the above example. The pseudo-code for this improved delivery can be found in Algorithm 3 in Appendix A.17.

First phase This step is the same as in Section 7.2.3 with the exception that each coded messages W J is divided into B/P packets for some large enough length P Second phase For each W J where J ⊆ [K] and |J | = t + 1, and each h ∈ S J , the second phase is used to transmit W |S J | J ,h to the users in J \ U h . In this paragraph, to simplify the notation, we let

A := U h ′ ∩ (J \ U h ) = ∅ and B := j ∈ U h ∩ U h ′ : H j ⊆ H A ∪ {h} . For each h ′ ∈ [H] \ {h} where A = ∅, we add |W |S J | J ,h |/(rP ) random linear combinations of packets of W |S J | J ,h in X h ′
A,B representing the packets to be recovered by users in A from relay h ′ and already known by the users in B who are also connected to relay

h ′ .
We aim to let each user k ∈ J \ U h recover all the sets of packets

X h ′ W 1 ,W 2 = ∅ where h ′ ∈ U k and k ∈ W 1 , such that he can recover |W |S J | J ,h |/P random linear combinations of packets in W |S J | J ,h and then recover W |S J |
J ,h with high probability provided that B → ∞. We use a two-stage coding. Stage 1: For each relay h ∈ [H] and each set V ⊆ U h , we encode all the sets of packets

X h W 1 ,W 2 = ∅ where W 1 ∪ W 2 = V, by L h V = RLC(c/P, C) where C = ∪ W 1 ,W 2 :W 1 ∪W 2 =V X h W 1 ,W 2 , (7.28)
c = max k∈V W 1 ,W 2 :W 1 ∪W 2 =V,k / ∈W 2 |X h W 1 ,W 2 |, (7.29)
where c/P is the maximal number of packets in C not known by the users in V. So from L h V , each user k ∈ V can recover all the sets

X h W 1 ,W 2 = ∅ where k ∈ W 1 . Stage 2: If for each set X h W 1 ,W 2 , where W 1 ∪ W 2 = V and |X h W 1 ,W 2 | > 0, we have k ∈ W 2 ,
it can be seen that user k already knows L h V from the first stage. Hence, in one relay h ∈ [H], we can encode L h V for all V ⊆ U h where L h V = ∅ by RLC(c ′ /P, C ′ ) where

C ′ = ∪ V⊆U h :L h V =∅ L h V , (7.30)
c ′ = max k∈U h V⊆U h :L h V is unknown to k |L h V |. (7.31)
We transmit RLC(c ′ /P, C ′ ) to relay h and relay h then forwards RLC(c ′ /P, C ′ ) to users in U h .

Remark 14. We now analyse the actual file split level for our proposed schemes. In IES, we need not divide W J . In DIS, we divide each W J into r non-overlapping equal-length pieces. In CICS, we first divide W J into |S J | non-overlapping equal-length pieces and then divide each obtained piece into r non-overlapping equal-length pieces. Hence, W J is divided into |S J |r pieces. in ICICS, we first divide W J into |S J | nonoverlapping equal-length pieces and then divide each obtained piece into at most H -1 non-overlapping equal-length pieces. Hence, W J is divided into at most |S J |(H -1) pieces.

Novel Non-separation Based Delivery Scheme

With any uncoded cache placement, we introduce a novel delivery scheme by leveraging the symmetry in the topology of combination networks, referred to as Separate Relay Decoding delivery Scheme (SRDS). Each multicast message sent to relay h ∈ [H] is aimed to be useful for the largest possible subset of H h (i.e, users connected to relay h). This delivery phase will also be used with our proposed asymmetric coded placement in the next section. In addition, this delivery scheme can also used with the decentralized placements in [START_REF]Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF] and in [START_REF] Mohajer | Erasure coding for decentralized caching[END_REF], while the caching scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] cannot be extended to decentralized systems (because its placement is designed with the knowledge of the position (the connected relays) of each user in the delivery phase).

Example for

H = 4, r = 2, N = K = 6 and M = 2
Consider the network in Fig. 1.4 with N = K = 6 and M = 2. We use MAN placement where each file F i is partitioned into K t = 15 non-overlapping sub-files of length B/15 bits, where t = KM/N. Each subfile denoted by F i,W where W ⊆ [K] and |W| = t, is cached by users in W. In the delivery phase, assume that d = (1 : 6). There are mainly three steps.

Step

1 [Subfile partition] For each F d k ,W , k ∈ [K]
where k / ∈ W, we seek to find the set of relays in H k each of which is connected to the largest number of users in W. Consider the following examples.

For sub-file F 1,{2,3} , which is demanded by user k = 1 and cached by the users in W = {2, 3}, we have that U 1 = {1, 2, 3} (relay 1 is connected to two users in W) and U 2 = {1, 4, 5} (relay 2 is not connected to any user in W). So we solve S k,W = arg max h∈H k |U h ∩ W| = {1} (i.e., relay h = 1). Since |S 1,{2,3} | = 1

we divide F 1,{2,3} into |S 1,{2,3} | = 1 equal-length pieces and denote F 1,{2,3} = (F |S| 1,{2,3},h : h ∈ S 1,{2,3} ). We add F 1 1,{2,3},1 into T h k,W∩U h = T 1 1,{2,3}
representing the set of bits needed to be recovered by user k = 1 from relay h ∈ S 1,{2,3} and already known by the users in W ∩ U h = {2, 3} who are also connected to relay

h = 1. Consider now F 1,{2,5}
where k = 1 and W = {2, 5}. Sub-file F 1,{2,5} is also demanded by user 1, who is connected to relays

H 1 = {1, 2}. Relay 1 is connected to users W ∩ U 1 = {2, 5} ∩ {1, 2, 3} =
{2}, while relay 2 is connected to users W ∩ U 2 = {2, 5} ∩ {1, 4, 5} = {5}, and thus we have

S k,W = arg max h∈H k |U h ∩ W| = {1, 2}. Since now |S 1,{2,5} | = 2, we divide F 1,{2,5} into |S| = 2 equal-length pieces and denote F 1,{2,5} = (F |S| 1,{2,5},h : h ∈ S 1,{2,5} ). We add F 2 1,{2,5},1 (i.e., (k, W, h) = (1, {2, 3}, 1)) to the set T h k,W∩U h = T 1 1,{2} , and F 2 1,{2,5},2 (i.e., (k, W, h) = (1, {2, 3}, 2)) in the set T h k,W∩U h = T 2 1,{5}
. After considering all the sub-files demanded by all the users, for relay h = 1 (and similarly for all other relays) we have

T 1 1,{2,3} = {F 1 1,{2,3},1 }, |T 1 1,{2,3} | = B/15, (7.32)
T 1 1,{2} = {F 2 1,{2,4},1 , F 2 1,{2,5},1 , F 1 1,{2,6},1 }, |T 1 1,{2} | = 2B/15, (7.33)
T 1 1,{3} = {F 2 1,{3,4},1 , F 2 1,{3,5},1 , F 1 1,{3,6},1 }, |T 1 1,{3} | = 2B/15, (7.34)
T 1 2,{1,3} = {F 1 2,{1,3},1 }, |T 1 1,{1,3} | = B/15, (7.35)
T 1 2,{1} = {F 2 2,{1,4},1 , F 1 2,{1,5},1 , F 2 2,{1,6},1 }, |T 1 2,{1} | = 2B/15, (7.36)
T 1 2,{3} = {F 2 2,{3,4},1 , F 1 2,{3,5},1 , F 2 2,{3,6},1 }, |T 1 2,{3} | = 2B/15, (7.37)
T 1 3,{1,2} = {F 1 3,{1,2},1 }, |T 1 1,{1,2} | = B/15, (7.38)
T 1 3,{1} = {F 1 3,{1,4},1 , F 2 3,{1,5},1 , F 2 3,{1,6},1 }, |T 1 3,{1} | = 2B/15, (7.39)
T 1 3,{2} = {F 1 3,{2,4},1 , F 2 3,{2,5},1 , F 2 3,{2,6},1 }, |T 1 3,{2} | = 2B/15. (7.40)
Step 2 [Multicast Message Generation] In this example, for each relay h ∈ [H] and each J ⊆ U h , we have

min k∈J |T h k,J \{k} | = max k∈J |T h k,J \{k} |, i.e.
, only a function of |J |. We thus create the multicast messages W h J := ⊕ k∈J T h k,J \{k} . For example, the server transmits to relay 1 the following messages

W 1 {1,2,3} = T 1 1,{2,3} ⊕ T 1 2,{1,3} ⊕ T 1 3,{1,2} of length B/15 bits, (7.41)
W 1 {1,2} = T 1 1,{2} ⊕ T 1 2,{1} of length 2B/15 bits, (7.42)
W 1 {1,3} = T 1 1,{3} ⊕ T 1 3,{1} of length 2B/15 bits, and (7.43)
W 1 {2,3} = T 1 2,{3} ⊕ T 1 3,{2} of length 2B/15 bits. (7.44)
Step 3 [Multicast Message Delivery] Finally, for each relay h ∈ [H] and each set J ⊆ U h where W h J = ∅, relay h forwards W h J to the users in k ∈ J . The normalized (by the file length) number of bits sent from the server to each relay is the same, thus the achieved max link-load is 7/15 = 14/30. The max link-loads of the schemes in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF], [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] are 20/30, and 15/30, respectively.

General Scheme of SRDS

The key in above example is that for each relay h ∈ [H] and each set J ⊆ U h , the length of the message T h k,J \{k} only depends on |J |. However, in other cases (e.g., r > 2 and MAN placement is used), we may have

min k∈J |T h k,J \{k} | < max k∈J |T h k,J \{k} |.
In order to 'equalize' the lengths of the various parts involved in the linear combinations for the multicast messages, we propose to use the bit-borrowing idea described in Section 5.4. The pseudo code of the proposed SRDS delivery scheme is in Algorithm 4 in Appendix A.17.

For any uncoded cache placement, each file F i where i ∈ [N] can be divided into non-overlapping subfiles and F i,W represents the bits known by users in W.

Step 1 [Subfile partition] For each user k ∈ [K] and each set W ⊆ [K] \ {k} where |F d k ,W | > 0, we search for the set of relays S k,W ⊆ H k , each relay in which is connected to the largest number of users in

W, i.e., max h∈H k |U h ∩ W| users. We partition F d k ,W into |S k,W | equal-length pieces F d k ,W = (F |S k,W | d k ,W,h : h ∈ S k,W ). For each relay h ∈ S k,W , we add F |S k,W | d k ,W,h to T h k,W∩U h
, where T h k,W∩U h represents the set of bits needed to be recovered by user k from relay h and already known by the users in W ∩ U h who are also connected to relay h.

Step 2 [Multicast Message Generation] Focus on each relay h ∈ [H] and each set J ⊆ U h where

W h J = ∅. For each user k ∈ J , if |T h k,J \{k} | < max k 1 ∈J |T h k 1 ,J \{k 1 } |,
we use the bit-borrowing idea described in Section 5.4: we take bits from T h k,W where J \ {k} ⊂ W and k / ∈ W and add them to T h k,J \{k} so that these borrowed bits need not to be transmitted to k later. Since J \ {k} ⊂ W, the users in J \ {k} also knows T h k,W . After considering all the users in J , the server forms the multicast messages

W h J := ⊕ k∈J T h k,J \{k} . (7.45)
Step 3 [Multicast Message Delivery] For each relay h ∈ [H] and each set J ⊆ U h where W h J = ∅, the server sends W h J to relay h, who then forwards it to each user k ∈ J .

Performance In the following we show that, when r = 2 and MAN placement is used, the bit-borrowing step is not needed (as example in Section 7.3.1). In this case the achieved max link-load is given in the following theorem.

Theorem 16. For a (H, r = 2, M, N) combination network with t = KM/N ∈ [0 : K], the max link-load is

R ⋆ c,u ≤ R SRDS := KX K,H H K t , (7.46a)
X K,H := min{t,H-2} b 1 =0 1 b 1 + 1 H -2 b 1 2 H-2 2 t -2b 1 + min{t,H-2} b 1 =0 b 1 -1 b 2 =0 2 b 1 + 1 H -2 b 1 H -2 b 2 H-2 2 t -b 1 -b 2 , (7.46b)
where R SRDS achieved by SRDS with MAN placement. The tradeoff between memory size and max link-load is the lower convex envelope of the above points.

Proof. When r = 2, each user k is connected to 2 relays, which are assumed to be h and h ′ . It can be seen that U h ∩ U h ′ = {k}. For one relay h ∈ [H] and each set J ⊆ U h , we can compute the length of T h k,J \{k} for each user k ∈ J . Assume that the other relay connected to k is h ′ . The number of W where

|W| = t and k / ∈ W such that |U h ′ ∩ W| = |U h ∩ W| = |J | -1, is Kr/H-1 |J |-1 ( H-r r ) t-2(|J |-1)
, where Kr/H -1 is the number of users connected to relay h ′ besides k and H-r r is the number of users which are not connected to relay h nor h ′ . For each of this kind W, we divide F d k ,W into 2 non-overlapping equal-length parts and put one part in T h k,J \{k} . Similarly, The number of W where |W| = t and k / ∈ W such that

|U h ′ ∩ W| < |U h ∩ W| = |J | -1, is |J |-2 m=0
Kr/H-1 m ( H-r r ) t-(|J |-1)-m . For this kind of W, we put F d k ,W in T h k,J \{k} .
Hence, we can find that for each user k ∈ J , |T h k,J \{k} | is identical and we need not to use the borrowing bits procedure. So we encode each

F d k ,W by a sum including max h∈[H] |U h ∩ W| sub-files. It is equivalent to say the total link-load to transmit F d k ,W is |F d k ,W |/ max h∈[H] B|U h ∩ W|. By considering each integer b 1 ∈ [0 : min{t, Kr/H -1}]
representing the number of sub-files in one sum, we can compute the max link-load achieved by SRDS shown in (7.46a).

Novel Non-separation Based Asymmetric Coded Placement

In Section 7.3, we propose a delivery phase by generating multicasting messages on network topology. However, with symmetric MAN placement where each t-subfile exists, the SRDS delivery phase is not symmetric; the subfiles in one multicasting messages may have different length. In this Chapter, we introduce an asymmetric coded cache placement by leveraging the relay connectivity. The proposed asymmetric coded placement can lead the symmetry of SRDS in the delivery phase.

We fix one coded caching gain g ∈ 1 : H-1 r-1 compared to uncoded routing scheme and want to minimize the needed memory size to achieve this coded caching gain. The achieved max link-load of the proposed scheme is stated as follows.

Theorem 17. For an (H, r, M, N) combination network, the lower convex envelop of the following points

(M b , R b ) = k 1,b N k 1,b + k 2,b , K(1 -M b /N) Hg (7.47a) for (coded caching gain) g ∈ [1 : K 1 ] and the point (M b , R b ) = (N, 0) is achievable, where k 1,b :=    r a=1 r a Ka-1 g-2 (-1) a-1 , if g ≤ K 2 + 1, H-r+1 m=1 N m K-( H-m r )-mK1+m(g-1) K , if g > K 2 + 1, (7.47b)
k 2,b := g|Z g |/K = r a=1 r a K a -1 g -1 (-1) a-1 , , (7.47c
)

N m = H m H-m r-1 y g-1,m - H-m a=1 H -m a H-m r-1 -a b=1 a b H-m-b r-b-1 (-1) b-1 y g-1,m -a b=1 a b H-m-b r-b-1 (-1) b-1 (-1) a-1 for m ∈ [2 : H -r + 1], (7.47d)
N 1 := |Z g-1 | - H-r+1 m=2 mN m , (7.47e)
y t,m := t -K 1 + H -m r -1 . (7.47f) 7.4.1 Proposed Asymmetric Coded Placement for g ∈ [2 : K 2 + 1]
We aim to achieve coded caching gain g ∈ [2 :

K 2 + 1].
In other words, every multicast coded message send through the network is simultaneously useful for g users and each subfile is cached by at least g -1 other users.

Placement We consider the elements of Z g-1 defined in (5.8), that is, those subsets of users with cardinality g -1 (from a ground set of cardinality K 1 ) for which there exists at least one relay connected to all of them. We aim to partition each coded file (the parameters of the MDS code will be specified later) into

n b := |Z g-1 | (7.48)
equal-length subfiles, i.e.,

f i = (f i,W : W ∈ Z g-1 ), i ∈ [N], (7.49)
where subfile f i,W is cached by the users in W. Therefore, each user caches

k 1,b = g -1 K |Z g-1 | [subfiles per file], (7.50)
since each subfile is cached by g -1 users and all users cache the same amount of subfiles. This placement is asymmetric because not all subfiles f i,W for W ⊆ [K] : |W| = g -1 are present.

Delivery We should create a multicast coded message similarly to (5.18) for each subset of users J of the form

J = W ∪ {k} : W ∈ Z g-1 , k ∈ [K], k ∈ W; (7.51)
however, only those J ∈ Z g are such that all users in J have at least one common connected relay; in order to have a symmetric delivery scheme from the relays to the users, we aim to deliver only those multicast coded messages for J ∈ Z g and consider those for J ∈ Z g as "erased". Therefore, each user eventually receives

k 2,b = g|Z g | K [subfiles per file], (7.52)
More precisely, for each set J ∈ Z g , we generate the MAN-like multicast message Performance By construction each multicast coded message transmitted from the server is simultaneously useful for g users, the max link-load from the server to relays is K(1 -M b /N)/(Hg). In addition, since

W J ,b := ⊕ k∈J f d k ,J \{k} (7.53)
|f d k 1 ,J \{k 1 } | = |f d k 2 ,J \{k 2 } |
for each set J ∈ Z g and any k 1 , k 2 ∈ J , and each user recovers B(1 -M b /N)/r bits from r relays, the load on each link from relays to users is (1-M b /N sf )/r. With K/(Hg) ≥ r, the max link-load is K(1 -M b /N)/(Hg). Hence, a coded caching gain of g is achieved with cache size per file

M b N = k 1 k 1 + k 2 = r a=1 r a Ka-1 g-2 (-1) a-1 r a=1 r a Ka g-1 (-1) a-1 , (7.54)
coinciding with the needed memory size in Theorem 17.

Proposed Asymmetric Coded

Placement for g ∈ [K 2 + 2 : K 1 ]
Since the number of users simultaneously connected to two relays is K 2 , when g -1 > K 2 , we have

|R W | = 1 for each set W ∈ Z g-1 .
hence, the proposed scheme in Section 7.4.1 does not leverage the relay connectivity-which in this case is equivalent to the scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF]. In this part, for g ∈ [K 2 + 2 :

K 1 ]
we further create multicasting opportunities across the relays which are not available in the scheme in Section 7.4.1. We start by two examples to highlight the key idea. In the first example, we present one way to create multicasting opportunities between two relays.

Example 10 (H = 6, r = 3, N = 20, g = 6). In this example, we have N = K = 20, K 1 = 10 and High level description of the proposed scheme In this example, we can see g = 6 > K 2 + 1 = 5 and so there is only one relay simultaneously connected to the users in W ∈ Z g-1 (i.e., |R W | = 1). For each

U 1 = {1, 2 , 3, 4, 5, 6, 7, 8, 9, 10},
U 2 = {1, 2,
W ∈ Z g-1 and each file i ∈ [N],
we aim to create one MDS subfile f i,W ′ such that W ′ ⊇ W. We define the collection of the common users of each two relays as

S := {U J : J ⊆ [H], |J | = 2}. ( 7
C ′ ∈ C {1,2},1 := C ⊆ U 1 \ U {1,2} : |C| = (g -1) -|U {1,2} | = 1 (7.56)
and one set The collection of remaining sets which should be considered is defined as Notice that for each generated MDS subfile in Hierarchy 2 (assumed to be f i,W ′ from relay h 1 and h 2 ), since

C ′′ ∈ C {1,2},2 := C ⊆ U 2 \ U {1,2} : |C| = (g -1) -|U {1,2} | = 1 (7.
H 1 = Z g-1 \ H 2 , i.e.,
W ′ ⊇ U {h 1 ,h 2 } , we have (U h 1 \ W ′ ) ∩ (U h 2 \ W ′ ) = ∅.
Hence, if we focus on one user k, for any sets J 1 , J 2 ∈ Z g where k ∈ J 1 and k ∈ J 2 , the created MDS subfiles f d k ,W ′ where W ′ ⊇ (J 1 \ {k}) and Delivery For each set J ∈ Z g , we generate the MAN-like multicast message

f d k ,W ′′ where W ′′ ⊇ (J 2 \
W ′ J ,b := ⊕ k∈J g d k ,J \{k} , (7.58)
and g i,W represents the created MDS subfile f i,W ′ where W ′ ⊇ W. Since g > K 2 + 1, we have for each

J ∈ Z g , |R J | = 1.
Hence, the server transmits W ′ J ,b to relay h where h ∈ R J , and relay h forwards it to users in J .

In this example, the needed memory to achieve

g = 6 is M b = Nk 1,b /(k 1,b + k 2,b ) = 9
.75 while the one of [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] is M ([50] = 10.

In the following example, we extend the scheme in Example 10 to create multicasting opportunities among more than two relays.

Example 11 (H = 6, r = 3, N = 20, g = 8). We consider the same network as Example 10.

High level description of the proposed scheme We aim to achieve coded caching gain g = 8. The main idea is also to create one MDS subfile f i,W ′ such that W ′ ⊇ W for each W ∈ Z g-1 and each file i ∈ [N].

We focus on the set of relays {1, 2, 3}. Recall that G Y defined in (5.5)

C ′ ∈ C {1,2},1 = C ⊆ U 1 \ U {1,2} : |C| = (g -1) -|U {1,2} | = 3, (U {1,2} ∪ C) U 1,h , h ∈ [H] \ {1, 2} , (7.63)
and one set Delivery For each set J ∈ Z g , we generate the MAN-like multicast message

C ′′ ∈ C {1,2},2 = C ⊆ U 2 \ U {1,2} : |C| = (g -1) -|U {1,2} | = 3, (U {1,2} ∪ C) U {2,h} , h ∈ [H] \ {1, 2} , (7.64
W ′ J ,b := ⊕ k∈J g d k ,J \{k} , (7.65)
and g i,W represents the created MDS subfile f i,W ′ where W ′ ⊇ W. Since g > K 2 + 1, we have for each

J ∈ Z g , |R J | = 1.
Hence, the server transmits W ′ J ,b to relay h where h ∈ R J , and relay h forwards it to users in J .

In this example, the needed memory to achieve

g = 8 is M b = Nk 1,b /(k 1,b + k 2,b ) = 12
.82 while the one of [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] is M ([50] = 14. Now we are ready to present our proposed scheme for g ∈ [K 2 + 2 :

K 1 ].
High level description of the proposed scheme The main idea is to create one MDS subfile f i,W ′ such that W ′ ⊇ W for each W ∈ Z g-1 and each file i ∈ [N]. We divide Z g-1 into Hr + 1 collections and define that

H m := W ∈ Z g-1 : {V ∈ S : V ⊆ W} = m -1 for m ∈ [H -r + 1]. ( 7
|G Y ∩ U h | = | ∪ h 1 ∈Y\{h} U {h,h 1 } | = K 2 + H -3 r -2 + . . . + H -m -1 r -2 = K 1 - H -m r -1 . (7.67) If K 1 -H-m r-1 > g -1,
C h,Y := {C ⊆ U h \ G Y : |C| = (g -1) -|G Y ∩ U h |, (G Y ∪ C) U {h,h 1 } , h 1 ∈ [H] \ Y}. ( 7
-H-m r -m H-m r-1 + m(g -1 -K 1 + H-m r-1 ) = K -H-m r
-mK 1 + m(g -1) users. We then repeat the construction for all subsets of m relays. The number of created MDS subfiles per file in Hierarchy m is denoted by

N m := |H m |/m. ( 7
k 1,b = H-r+1 m=1 N m K-( H-m r )-mK1+m(g-1)
K MDS subfiles per file.

Notice that for each generated MDS subfile in Hierarchy m (assumed to be f i,W ′ from relay h ∈ Y

where

|Y| = m), since W ′ ⊇ G Y , we have (U h 1 \ W ′ ) ∩ (U h 2 \ W ′ ) = ∅ for any two relays h 1 , h 2 ∈ Y.
Hence, for each user k ∈ [K] and for any sets J 1 , J 2 ∈ Z g where k ∈ J 1 and k ∈ J 2 , we can see that the Delivery For each set J ∈ Z g , we generate the MAN-like multicast message

W ′ J ,b := ⊕ k∈J g d k ,J \{k} , (7.71)
and g i,W represents the created MDS subfile f i,W ′ where W ′ ⊇ W. Since g > K 2 + 1, we have for each

J ∈ Z g , |R J | = 1.
Hence, the server transmits W ′ J ,b to relay h where h ∈ R J , and relay h forwards it to users in J .

Performance Hence, each demanded MDS subfile is multicasted from the server with other g -1 demanded MDS subfiles and thus the max link-load from the server to relays is K(1 -M b /N)/(Hg). In With K/(Hg) ≥ r, the max link-load is K(1 -M b /N)/(Hg). To achieve coded caching gain g, the needed memory size is given in (7.47a).

Remark 15. It can be checked that the delivery phases in Section 7.4.1 and Section 7.4.2 are equivalent to SRDS; in other word, for each set J ∈ Z g and each user k ∈ J , assuming f i,W ′ = g i,J \{k} , we have R J = arg max h∈H k |U h ∩ W ′ |. Hence, with the proposed asymmetric coded placement, the SRDS delivery phase becomes symmetric. Proof. It is obvious to prove that DIS is better than the second scheme in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] which transmit |W J |/r bits to each relay h ∈ [H]. The first scheme in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] is equivalent to use |J ||W J | bits to transmit W J . However, in DIS, we use at most |J ||W J | bits to transmit W J ; only when each two users k 1 , k 2 ∈ Jc, we have

H k 1 ∩ H k 2 = ∅, we use |J ||W J | bits.
Hence, the max link-load of DIS is lower than the one in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF].

In the following we show that our proposed asymmetric coded placement with SRDS is strictly better than the scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF]. For example, it can be checked from Theorem 17 that for the combination network with H = 4, r = 2, N = K = 6 in Fig. 1.4, to achieve g = 2, the needed memory size of the proposed scheme is 6/5 while the one of [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] is 2. In addition, when M = 6/5, the achieved max-link load in Theorem 17 is 3/5, which coincides with the converse bound in Theorem 7, while the max-link load with the scheme from [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] is 9/10. Notice that the converse bound under the constraint of uncoded placement in Theorem 12 is 157/255 ≈ 0.616, that is, in this example using uncoded cache placement is strictly suboptimal. In general we have the following corollary whose proof is in Appendix A.13.

Theorem 22. For an (H, r, M, N) combination network achieving each coded caching gain g ∈ [2 : K 1 ], it holds that the minimum needed memory size of the proposed scheme is strictly less than the one of [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF], i.e., M b < M ZY .

Numerical Evaluations for Combination Networks with End-user-caches

In this part, we will show the numerical results of our proposed converse bounds and novel delivery schemes for combination networks with end-user-caches.

Example for

H = 4, r = 2, N = K = 6
Firstly, we give an example where H = 4, r = 2 and N = K = H r = 6, to illustrate the proposed achievable bounds and converse bounds compared to the state-of-the-art. In Fig. 8.1, we plot the cut-set converse bound in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] (described in (1.9) of this thesis), the proposed enhanced cut-set converse bound in Theorem 7, the cache content of all the users, each file can be divided into sub-files. F i,W represents the bits of file F i which are only known by the users in W ⊆ [1 : K]. By the law of the large number, the length of each sub-file only depends on the number of user knowing it. In the delivery phase, an iteration is run from K -

1 to 0. In each loop t ∈ [0 : K -1], all the K t+1 sub-files (F i,W : |W| = t, i ∈ [N]
) are gathered together to be transmitted by the chosen proposed scheme with the lowest load among all the proposed delivery phases for the centralized case where M = Nt/K.

Notice that the proposed asymmetric coded placement and the placements of the scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] and in [START_REF] Tang | Coded caching for networks with the resolvability property[END_REF] are designed based on the knowledge of the position (the connected relays) of each user in the delivery phase. Hence, it is hard to extend these two schemes to the decentralized systems due to the mobility of the users. Fig. 8.4 shows that our proposed scheme outperforms the state-of-the-art schemes.

Chapter 9

Cache-aided Extended Models

Chapter Overview and Related Publications

In this chapter, we extend our results for combination networks with end-user-caches to more general models, including combination networks with cache-aided relays and users, and combination networks with more general relay networks. Different to the existing scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] where the packets transmitted from the server are independent of the cached contents of relays, in Section 9.2 we propose a caching scheme where the cached contents in relays can also help users to decode the coded messages transmitted from the server and thus can further reduce the transmitted load from the server to relays. We prove that for some memory size regime, the achieved first layer load of the proposed scheme is information theoretically optimal. We also show that the proposed scheme reduces the first layer load of the state-of-the-art scheme. For general relay networks, due to the asymmetry, the loads transmitted to relays may be different. Based on the proposed SRDS, in Section 9.3, we propose a further step to 'balance' the loads transmitted to relays.

Related Publications

Combination Networks with Cache-Aided Relays and Cache-Aided Users

Combination networks with both cache-aided relays and users were considered in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF], where each relay can store M relay B bits and each user can store M user B bits, for M relay ∈ [0, N/r] and M user ∈ [0, N]. Notice that if M relay = N/r, each user can get all the N files from its connected relays. For each (H, r, M relay , M user , N) combination network, the objective is to determine the lower convex envelop of the load (number of transmitted bits in the delivery phase) pairs

(R s→r , R r→u ) = max h∈[H] R h (d, Z), max h∈[H],k∈U h R h→k (d, Z)
for the worst case demands d for a given placement Z.

The authors in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] extended the cut-set converse bound in (1.9) to the combination networks with cache-aided relays and users.

Theorem 23. In a (H, r, M relay , M user , N) combination network, the optimal loads are lower bounded by

R s→r⋆ ≥    max l∈[r:H] max s∈ min N,( l r ) 1 l s -sM user +lM relay ⌊N/s⌋ , if rM relay + M user ≤ N, 0, if rM relay + M user ≥ N, (9.1a)
R r→u⋆ ≥ 1 r 1 - M user N . (9.1b)
In practice, the throughput of transmission from the server to relays may be much lower than the throughput from the relays to their local connected users. For example, in wireless networks where the throughput from small cell base stations to users are much higher than that from the macro base stations to small base stations if all use sub-6GHz wireless communications. In this thesis, for combination networks with cache-aided relays and users, we mainly want to minimize the max-link load from the server to relays, i.e.,

R s→r = max h∈[H] R h (d, Z).
For a caching scheme with max-link load among all the links from the server to relays R s→r , we say it attains a coded caching gain of g if

R s→r = R s→r routing g , for R s→r routing := K max 1 -(rM relay + M user )/N, 0 H (9.2)
where R s→r routing is achieved by routing. It can be seen that when M relay = 0, since the max link-load from relays to users can not be larger than the max link-load from the server to relays, the coded caching gain on the the max link-load from the server to relays is equivalent to the one on the max link-load among all links.

Thus the definition of coded caching gain in (9.2) is equivalent to the one given in (5.14) for combination networks with end-user-caches.

We start by give our main results on combination networks with both cache relays and users.

Theorem 24. In a (H, r, M relay , M user , N) combination network, the lower convex envelop of the following four groups of corner points is achievable,

1. Group 1: (M relay , M user ) = 0, Nk 1,b k 1,b +k 2,b for each g ∈ [1 : K 1 ]. The achieved loads are (R s→r , R r→u ) = K(1 -M user /N)/(Hg), (1 -M user /N)/r . ( 9
i,W = {f i,W,h : h ∈ R W } ∪ {f ′ i,W }. For each h ∈ R W , f i,W,h is cached by relay h where |f i,W,h | = M relay B N( K 1 g-1 )
. In addition, f ′ i,W is cached by each user in W where

|f ′ i,W | = B/36 -|R W |M relay B N( K 1 g-1 )
. Hence, each relay h ∈ [H] caches f i,W,h for each W ⊆ U h and each i ∈ [N]

where |W| = g -1. Thus the number of cached bits of relay h is

N K 1 g -1 M relay B N K 1 g-1 = M relay B. ( 9
∈ Z g-1 , k / ∈ W, R {k}∪W = ∅ and h ∈ (R W ∩ H k ).

In the second step, we also focus on each relay h ∈ [H] and each user k

∈ U h . For each set W ′ ⊆ U h and each k ′ ⊆ [K] \ U h where |W ′ | = g -1, k ∈ W ′ and R {k ′ }∪W ′ = ∅, relay h delivers f d k ′ ,W ′ ,h
to user k. These additional side information of user k will help him decode the multicast messages transmitted from the server in the second step.

In the last step, as Example 12, we let each user

k recover f d k ,W \ {f d k ,W,h : h ∈ (R W ∩ H k )} where W ∈ Z 3 , k / ∈ W and R {k}∪W = ∅. More precisely, we let T k,W := f d k ,W \ {f d k ,W,h : h ∈ (R W ∩ H k )} (
V h J := ⊕ k∈J T k,J \{k},h (9.8)
to be sent to relay h and then forwarded to the users in J .

For example, consider relay 1 and set Hence, we achieve g = 3 and (R s→r , R r→u ) = ( 29 , 41 72 ) ≈ (0.22, 0.57) while the scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] described in Chapter 5.3 gives (R s→r , R r→u ) = ( 1124 , 23 72 ) ≈ (0.46, 0.32). It can be seen the max link-load from the server to relays achieved by the proposed method is less than the half of the one achieved by the scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF].

J 1 = {1, 2, 3}. It can be seen that T 1,{2,3} = f d 1 ,{2,3} \ (f d 1 ,{2,3},1 ∪ f d 1 ,{2,3},2 ) = ∅. Similarly T 2,{1,3} = G 3,{1,2} = ∅. So V 1 {1,2,3} = ∅. Consider now relay 1 and set J 2 = {1, 2, 4}. It can be seen that T 1,{2,4} = f d 1 ,{2,4} \ f d 1 ,{2,4},1 = f d 1 ,{2,4},4 . Since R {1,2,4} = {1},
Comparing the proposed scheme and the scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF], there are main two advantages. On one hand, we can see that the cached contents of relays help users to decode the packets transmitted from the server which can lead an additional coded caching gain. For example, f d 7 ,{1,2},1 is cached by relay 1 and f d 2 ,{1,7},3 is cached by relay 3. In the second step of delivery, f d 7 ,{1,2},1 is transmitted from relay 1 to user 1 and f d 2 ,{1,7},3 is transmitted from relay 3 to user 1 such that user 1 knows them. In the third step of delivery, the server transmit f d 1 ,{2,7},4 ⊕ f d 2 ,{1,7},3 ⊕ f d 7 ,{1,2},1 to relay 2 and user 1 can use f d 7 ,{1,2},1 and f d 2 ,{1,7},3 to decode f d 1 ,{2,7},4 . On the other hand, our proposed scheme is based on the asymmetric coded placement scheme in Chapter 7.4 which is proved to be better than the scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF].

We now generalize the proposed scheme in Example 12. Notice that in this example, f i,{1,2} with B/36 bits is divided into |R {1,2} |+1 = 3 non-overlapping pieces where |f

i,{1,2},1 | = |f i,{1,2},2 | = M relay B N( K 1 g-1 )
= B/72 bits and |f ′ i,{1,2} | = 0. It can be seen that if we increase M relay by a small value and we still desire to achieve g = 3, we have |f i,{1,2},1 | + |f i,{1,2},2 | > f i,{1,2} and thus these two pieces are overlapped which leads to redundancy. In other words, not all the bits of F d 1 cached in relays 1 and 2 are useful to user 1, from the proposed scheme in Example 12, we cannot achieve the coded caching gain g compared to the routing scheme in which all the bits of F d k cached from h ∈ H k is useful to user k. So in this thesis, we only consider the case

M relay ≤ N K 1 g-1 max W∈Zg |R W | = N K 1 g-1 (k 1,b + k 2,b ) max{y ∈ [r] : K y ≥ g -1} , (9.9)
where B/(k 1,b + k 2,b ) is the length of each MDS symbol generated by the asymmetric coded placement scheme in Chapter 7.4. The memories-loads tradeoff of the proposed scheme is the lower convex envelope of the four groups of corner points.

1. Group 1: (M relay , M user ) = 0,

Nk 1,b k 1,b +k 2,b for each g ∈ [1 : K 1 ].
For each point in this group, we can see that relays do not have memory and the scheme is equivalent to the one for combination networks with end-user-caches. We directly use the asymmetric coded placement scheme in Chapter 7.4 which leads (R s→r , R r→u ) = K(1 -M user /N)/(Hg), (1 -M user /N)/r .

Group

2: (M relay , M user ) = N( K 1 g-1 ) (k 1,b +k 2,b ) max{y∈[r]:Ky≥g-1} , N k 1,b (k 1,b +k 2,b ) - N( K 1 -1 g-2 )r (k 1,b +k 2,b ) max{y∈[r]:Ky≥g-1}
where the coded caching gain g ∈ [2 : K 2 + 1] and the proposed scheme is based on the asymmetric coded placement scheme in Chapter 7.4.1.

Placement phase

f i,W into |R W | + 1 non-overlapping parts, f i,W = {f i,W,h : h ∈ R W } ∪ {f ′ i,W }. For each h ∈ R W , f i,W,h is cached by relay h where |f i,W,h | = M relay B N K 1 g-1 (9.10a) = B max{y ∈ [r] : K y ≥ g -1}(k 1,b + k 2,b ) . (9.10b)
In addition, f ′ i,W is cached by each user in W where

|f ′ i,W | = B/(k 1,b + k 2,b ) - |R W |M relay B N K 1 g-1 (9.11a) = B/(k 1,b + k 2,b ) - |R W |B (k 1,b + k 2,b ) max{y ∈ [r] : K y ≥ g -1} . (9.11b) Hence, each user k ∈ [K] totally caches i∈[N] W∈Z g-1 :k∈W |f ′ i,W | = M user B bits. Notice that for each W ∈ Z g-1 , if W ∈ arg max W ′ ∈Zg |R W ′ |, we have |f ′ i,W | = 0; otherwise, |f ′ i,W | > 0.
Delivery phase We let each user k recover f d k ,J \{k} where J ∈ Z g and k ∈ J . There are three steps in delivery phase:

f d k ′ ,W,h to user k where k ′ ⊆ ([K] \ U h ) and R {k ′ }∪W = ∅.
(c) In the last step, we let each user k recover

f d k ,W \{f d k ,W,h : h ∈ (R W ∩H k )} where W ∈ Z g-1 ,
k / ∈ W and R {k}∪W = ∅. More precisely, we let

T k,W := f d k ,W \ {f d k ,W,h : h ∈ (R W ∩ H k )} (9.12)
representing the unknown bits in f d k ,W of user k. We divide T k,W into |R {k}∪W | non-overlapping and equal-length pieces, T k,W = {T k,W,h : h ∈ R {k}∪W }. After considering all the MDS coded symbols demanded by all the users, for each relay h ∈ [H] and each set J ⊆ U h where |J | = g, we create the multicast message in (9.8), which is to be sent to relay h and then forwarded to the users in J . It is also easily to check that each subfile in the multicast message in (9.8) has the same length.

In Appendix A.15, we compute the achieved loads are given in (9.3c).

3. Group 3:

(M relay , M user ) = N( K 1 g-1 ) (k 1,b +k 2,b )m g max , N k 1,b (k 1,b +k 2,b ) - N( K 1 -1 g-2 )r (k 1,b +k 2,b )m g max where the coded caching gain g ∈ [K 2 + 2 : K 1 ] and m g max := max m ∈ [H -r + 1] : K 1 -H-m r-1 ≤ g -1 representing the max value of m ∈ [H -r + 1]
such that there exist some created MDS subfiles in Hierarchy m (i.e., N m > 0). We use the similar way as the above case to extend the asymmetric coded placement scheme in Chapter 7.4.2.

Placement phase

f i,W ′ = {f i,W ′ ,h : h ∈ Y} ∪ {f ′ i,W ′ }. For each h ∈ Y, f i,W ′ ,h is cached by relay h where |f i,W ′ ,h | = M relay B N K 1 g-1 (9.13a) = B m g max (k 1,b + k 2,b ) . (9.13b) In addition, f ′ i,W ′ is cached by each user in W ′ where |f ′ i,W ′ | = B/(k 1,b + k 2,b ) - mM relay B N K 1 g-1 (9.14a) = B/(k 1,b + k 2,b ) - mB (k 1,b + k 2,b )m g max . (9.14b) Hence, each user k ∈ [K] totally caches Nk 1,b (k 1,b +k 2,b ) - N( K 1 -1 g-2 )r (k 1,b +k 2,b )m g max = M user B bits. Notice that if m = m g max , we have |f ′ i,W ′ | = 0; otherwise, |f ′ i,W ′ | > 0.
W ′ ⊇ W, relay h delivers f d k ′ ,W ′ ,h to user k where k ′ ∈ ∪ h 1 ∈(Y\{h}) U h 1 \ W ′ .
(c) In the last step, we let user k ∈ [K] recover

P k,J \{k} := f d k ,W ′ \ {f d k ,W ′ ,h : h ∈ (Y ∩ H k )} (9.15)
for each set J ∈ Z g where k ∈ J and we assume the created MDS subfile for J \ {k} is In Appendix A.15, we compute the achieved loads are given in (9.3f).

f d k ,W ′ by
4. Group 4: (M relay , M user ) = (N/r, Nt 1 /K 1 ) where t 1 ∈ {0, K 1 } and (M relay , M user ) = (0, N). This group is equivalent to the second group of the caching scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] described at beginning of this subsection. So if

t 1 = 0, (R s→r , R r→u ) = (0, 1/r). If t 1 = K 1 , (R s→r , R r→u ) = (0, 0). If (M relay , M user ) = (0, N), (R s→r , R r→u ) = (0, 0).
In the corner points of Groups 2 and 3, each user can leverage the cached contents of the connected relays to decode the coded messages transmitted from the server to reduce the load R s→r . However, the tradeoff is that in the second step of delivery phase, each relay h ∈ [H] transmits some bits of the files which are not demanded by user k ∈ U h to user k and thus we increase the load R r→u . So if we do not want to increase R r→u , we can directly take the corner points in Group 1 and 4.

Numerical Evaluations

We compare the performance of the proposed scheme in Theorem 24 and the caching scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] for the combination network with cache-aided relays and users, where H = 6, r = 2

and N = K = H r . We fix M relay = 1 and plot the tradeoffs between M user and (R s→r , R r→u ). We have two strategies:

1. Strategy 1: we take the memory-sharing of the corner points in Groups 1, 2, 3 and 4 in Theorem 24 in order to minimize R s→r . The achieved load pair is (R s→r Strategy 1 , R r→u Strategy 1 ).

2. Strategy 2: we take memory-sharing of the corner points in Groups 1 and 4 in Theorem 24 to minimize R s→r , which can simultaneously lead to the optimal max link-load from relays to users R r→u⋆ . The achieved load pair is (R s→r Strategy 2 , R r→u Strategy 2 ).

The achieved load pair of [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] is (R s→r ZY , R r→u ZY ). As a converse bound, we use the cut-set converse bound (R s→r⋆ , R r→u⋆ ) in Theorem 23. We also plot the ratios of the max link-loads from relays to user as otherwise their difference would not be clearly visible on a small figure. It can be seen in Fig. 9.1 that both Strategies 1 and 2 can reduce R s→r ZY . In addition, Strategy 1 leads to the optimal R s→r⋆ when M user ≥ 4.5, while the minimum user memory sizes to achieve the optimal R s→r⋆ of Strategy 2 and [50] are 5 and 6, respectively.

In addition, when M user ≥ 5, the proposed scheme can achieve the optimal load pair (R s→r⋆ , R r→u⋆ ).

Cache-aided More General Relay Networks

In this part, we consider more general relay networks. For the existing schemes with coded cache placement (the asymmetric coded placement scheme in Section 7.4 and the scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF]), the schemes are achievable if each user k, the number of cached subfiles per file is the same and the number of the subfiles to be recovered is also the same. In Example 13, we can directly use the proposed coded placement scheme and the scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF]. When M = 20/7, the achieved max link-load of the asymmetric coded placement scheme in Section 7.4.1 is 1/7 ≈ 0.142, which coincides with the cut-set converse bound in (1.9) extended to this network.

The achieved max link-load of the schemes in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] and in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF], and the scheme SRDS with MAN placement are 11/63 ≈ 0.174, 4/21 ≈ 0.190 and 23/140 ≈ 0.164, respectively.

Since SRDS does not rely on the symmetric topology of combination networks, it can be used in general relay networks with end-user-caches. In addition, SRDS is designed to minimize the total link-loads to all the relays. For combination networks, minimizing the total link-loads to all the relays is equivalent to minimize the max link-load. However, for asymmetric networks, we may need to further 'balance' the link-load to each relay, which will be shown in the following example. to relay 5.

It can be seen that the link-loads to relay 1 to 5 are 1/3, 7/30, 17/60, 7/30 and 1/3, respectively. So the achieved max link-load is 1/3; while the achieved max link-load by the schemes in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] is 1/2.

One can further improve on SRDS by observing that the link-load to relay 1 (or relay 5) is the largest.

Thus, instead of transmitting W 1 {1,3},B/30 to relay 1, we can transmit it to relay 2 which is also connected to users in {1, 3}. Similarly, instead of transmitting W 5 {3,5},B/30 to relay 5, we can transmit it to relay 4 which is also connected to users in {3, 5}. With this modification, the achieved max link-load is reduced to 3/10, which is equal to the cut-set converse bound in (1.9) (by considering the cut of relays {1, 5}).

The observation at the end of Example 14 can be translated in an improvement of the Algorithm 4 as described in Algorithm 5. Summary of Thesis and Prospectives on Future Work

In this chapter, we first revisit some results, summarize our contributions in this thesis and then present some prospectives on the future work.

Conclusions

In this thesis, we investigated the coded caching problem by building the connection between coded caching with uncoded placement and index coding, and leveraging the index coding results to characterize the fundamental limits of coded caching problem. We mainly analysed the caching problem in shared-link broadcast model and in combination networks.

Cache-aided Shared-link Broadcast Networks

In the first part of this thesis, for cache-aided shared-link broadcast networks, we considered the constraint that content is placed uncoded within the caches. When the cache contents are uncoded and the user demands revealed, the caching problem can be connected to an index coding problem. We derived fundamental limits for the caching problem by using tools that are either known or newly developed for the index coding problem.

A novel index coding achievable scheme was first derived based on distributed source coding. This achievable bound was proved to be strictly better than the widely used "composite (index) coding" achievable bound by leveraging the ignored correlation among composites and the non-unique decoding. For the centralized caching problem, a converse bound under the constraint of uncoded cache placement is proposed based on the "acyclic index coding converse bound". This converse bound is proved to be achieved by the cMAN scheme when the number of files is not less than the number of users, and by the proposed novel index coding achievable scheme otherwise. For the decentralized caching problem, this thesis proposes a converse bound under the constraint that each user stores bits uniformly and independently at random. This converse bound is achieved by dMAN when the number of files is not less than the number of users, and by our proposed novel index coding achievable bound otherwise.

Comment 1: Further advancement on the coded caching problem in shared-link problem beyond the results presented in this thesis are thus only possible by considering strategies where the cache placement phase is coded.

Comment 2: Index coding problem is generally an open problem. For a very limited number of graphs, we can characterize the rate region. However, in this thesis, we showed the caching problem with uncoded placement is solved. The main reason is that we can design the placement to lead the maximum multicasting opportunities.

During my Ph.D. study, we also analysed a more practical setting, the cache-aided shared-link model with finite file size (see results in [START_REF] Wan | Novel delivery schemes for decentralized coded caching in the finite file size regime[END_REF]). But in this thesis, we focused on the information theoretical model where the file size is infinite and thus we did not go into detail on the results on finite file size regime.

Cache-aided Combination Networks

In this second part of this thesis, we considered the centralized caching problem in two-hop relay networks, where the server communicates with cache-aided users through some intermediate relays. Because of the hardness of analysis on the general networks, we mainly considered a well-known symmetric relay networks, combination networks, including H relays and H r users where each user is connected to a different r-subset of relays. We aimed to minimize the max link-load for the worst cases. We derived converse and achievable bounds in this thesis.

For the converse bound, the straightforward way is that each time we consider a cut of x relays and the total load transmitted to these x relays could be converse bounded by the converse bound for the shared-link model including x r users. We used this strategy to extend the converse bounds for the shared-link model and the acyclic index coding converse bound to combination networks. In this thesis, we also tightened the extended acyclic index coding converse bound in combination networks by further leveraging the network topology and joint entropy of the various random variables. As a result of independent interest, an inequality that generalizes the well-known sub-modularity of entropy is derived, which may find applications in other network information theory problems.

For the achievable schemes, there are two approaches, separation and non-separation. In the separation approach, we use cMAN cache placement and multicast message generation independent of the network topology. We then deliver cMAN multicast messages based on the network topology. In the non-separation approach, we design the placement and/or the multicast messages on the network topology. In this thesis, we proposed four delivery schemes on separation approach. On non-separation approach, firstly for any uncoded cache placement, we proposed a delivery scheme by generating multicast messages on network topology. With this novel delivery scheme, we then proposed an asymmetric coded cache placement, where 'asymmetric' means that it is not necessary to generate one subfile known by each (g -1)-subset of users and 'coded' means that we use an MDS-precoded placement such that each user needs only to decode the subfiles with highest multicast opportunities. Optimality results were also given for certain system parameters.

Comment 3: The main advantage of separation approach is the low design complexity and its extensibility to more general networks such as decentralized systems, more general relay networks. However, if we focus on some specific networks, non-separation approach provides better performance. For example, as we showed in Section 8.2.1, for combination network with H = 4, r = 2 and M = 6/5, our proposed asymmetric coded placement scheme on non-separation approach is strictly better than all the scheme with uncoded cache placement and thus strictly better than all the separation approach based schemes. Moreover, we also extended our results to more general models, such as combination networks with cache-aided relays and users, and caching systems in more general relay networks. For combination networks with cache-aided relays and users, different to the existing scheme in which the cached contents of relays are independent of the transmitted packets from the server, we proposed a novel strategy which leads to an additional coded caching gain on the load transmitted from the server because of the cached contents of relays. Optimality results were given under some constraints and numerical evaluations showed that our proposed schemes outperform the state-of-the-art.

Comment 4: The proposed converse bounds does not lie on the symmetry of the combination networks and thus can be directly extended to more general relay networks. Our proposed achievable schemes were designed to minimize the total load transmitted from the server. Because of the symmetry of combination networks, it is equivalent to minimize the max link-load. However, if we consider the more general relay networks which are not symmetric, some further steps are needed to 'balance' the link-loads (e.g., the additional steps in Algorithm 5 described in Section 9.3).

Prospectives on Future Work

Owing to the limitation upon the duration of a Ph.D. program, it remains some possible problems to be investigated. Besides searching tighter converse bounds and achievable bounds for combination networks with end-user-caches, we allude in the sequel some other potential directions for future work.

Cache-aided Combination Networks with More Users than Files

It can be seen that the existing caching schemes and the proposed caching schemes in this thesis treat each sub-file demanded by each user as an independent sub-file. However, when N < K, one file may be demanded by several users such that there exist some multicasting opportunities from which we can profit.

Similar to the scheme in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] where each cMAN multicast messages is transmitted to all users by an (H, r) MDS code, one straightforward way is to extend the caching scheme for shared-link models in [START_REF] Yu | The exact rate-memory tradeoff for caching with uncoded prefetching[END_REF] with the load in (1.3) to combination networks. In other words, for each demanded file, we choose arbitrarily a demanding user as a leader and thus we can form a leader set U . We let all users recover cMAN multicast messages in (2.14) W J where J ⊆ [K], |J | = t + 1 and J ∩ U = ∅. The max link-load is achieved in the following theorem. The tradeoff between memory size and max link-load is the lower convex envelope of the above points.

Comparing the load in (10.1) and the cut-set converse bound under the constraint of uncoded placement in (6.2) with x = H, we can prove that the above scheme is order optimal within factor H/r under the constraint of uncoded placement.

In the following example, we propose an improved scheme based on SRDS which can lead to a lower max link-load than the previous scheme. Problem 2: Let k be a positive integer. We focus on all the 2k+1 k subsets of [2k + 1] with cardinality k. We want to divide these subsets into 2k+1 k /(2k + 1) groups such that each group has 2k + 1 subsets. In each group, the number of subsets containing each number in [2k + 1] is the same (equal to k). We create a (2k + 1) × (2k + 1) matrix, called incident matrix. There is one row of 0 and 1 in the incident matrix corresponding to each subset in this group, where the j th element in the row is 1 if and only if j is in this subset. The condition is that each incident matrix is full-rank.

Compared to Problem 1, Problem 2 has an additional constraint, which is that in each group, the number of subsets containing each number in [2k +1] is the same. In Example 7, we have a group division satisfying Problem 1. In addition, if we take out the number 2k + 2 = 6 in each subset, it is a solution for Problem 2.

To analyse the existence, we firstly recall the following theorem given in [START_REF] Petecki | On cyclic hamiltonian decompositions of complete k-uniform hypergraphs[END_REF]Theorem 1.1].

Theorem 28 ([73]). Let k ′ and n ′ be positive integers, and let λ be the smallest non-trivial divisor of n ′ . Then all the n ′ k ′ subsets of [n ′ ] with cardinality k ′ could be divided into n ′ k ′ /n ′ non-overlapping groups, where each group includes n ′ subsets and its incident matrix is circulant, if and only if n ′ is relatively prime to k ′ , λk ′ > n ′ and n ′ divides n ′ k ′ .

A circulant n ′ × n ′ matrix is uniquely determined by its first row [c 0 , c 1 , . . . , c n ′ -1 ] and its i th row is obtained by shifting the first row rightwards by i -1 where i ∈ [2 : n ′ ]. In Problem 2, n ′ = 2k + 1 and k ′ = k. It is easy to see that 2k + 1 and k are relatively prime and that λ ≥ 3 leading λk > 2k + 1. In addition, in Appendix A.6 we prove that 2k + 1 divides 2k+1 k . Hence, if we choose n ′ = 2k + 1 and k ′ = k, the conditions in Theorem 28 are satisfied. Since the incident matrix of each group is circulant, we can see that in each group, the number of sets containing each number in [2k + 1] is the same. Hence, it remains to analyse the rank of each incident matrix. In Appendix A.9, we prove the following theorem (We are grateful to Mr. Zhangchi Chen from Math department of University Paris-sud who proves the following theorem for us).

Theorem 29. Let k be a positive integer. A (2k + 1) × (2k + 1) circulant matrix, where the number of 1 in the first row is k and the number of 0 in the first row is k + 1, is always invertible if 2k + 1 = p v or pq, where p, q are different primes and v is a positive integer.

We have proved Conjecture 1 when 2k + 1 = p e . Now we prove Conjecture 1 when 2k + 1 = pq.

Proof of Conjecture 1 when 2k + 1 = pq. Without loss of generality we suppose that p < q. In this case we have dim Q (Q[ζ]) = φ(pq) = (p -1)(q -1) = pqpq + 1. As a Q-vector space, Q[ζ] is generated by {1, ζ, . . . , ζ 2k } with relations {τ p,βp : β p ∈ [0 : q -1]} and {τ q,βq : β q ∈ [0 : p -1]}. However, unlike the case where 2k + 1 = p e , these relations are not independent. There is a second relation since λ q,βq τ q,βq ∈ ker(d 1 ), where λ p,0 , . . . , λ p,q-1 , λ q,0 , . . . , λ q,p-1 ∈ Q, we have

d 1 (Λ 1 ) = q-1 βp=0 p-1 βq=0
(λ p,βp + λ q,βq )e f (βp,βq) = 0, (A. [START_REF] Han | The capacity region of general multiple-access channel with certain correlated sources[END_REF] where f (β p , β q ) is the unique solution in {0, . . . , pq -1}, guaranteed by Chinese Reminder Theorem [START_REF] Gauss | Disquisitiones arithmeticae (English edition)[END_REF],

of the equations f (β p , β q ) ≡ β p (mod q) f (β p , β q ) ≡ β q (mod p) (A. [START_REF] Tang | Coded caching for networks with the resolvability property[END_REF] where ≡ is the congruence modulo. Thus we get λ p,βp + λ q,βq = 0, ∀β p , β q . So λ p,βp = λ p,0 = -λ q,βq , ∀β p , β q , i.e. Λ 1 = d 2 (λ p,0 ) ∈ im(d 2 ).

To prove im(d 1 ) = ker(d 0 ) we calculate dimensions. We have

dim Q ker(d 0 ) = dim Q Q pq -dim Q Q[ζ] = p + q -1, while dim Q im(d 1 ) = dim Q Q p+q -dim Q ker(d 1 ) = p + q -dim Q im(d 2 ) = p + q -1 as well.
Thus im(d 1 ) = ker(d 0 ). We conclude that the sequence above is exact. Define µ 2k+1 as the Abelian group composed by all the (2k + 1)-th roots of unity. Let E ⊂ µ 2k+1 be a set of (2k + 1)-th roots with sum 0.

  •) set of weak typical n-length sequences p(J ) p(J ) := p 1 (J ), . . . , p |p(J )| (J ) , a permutation of elements of the set J U h set of connected users of relay h U Y set of common connected users to all the relays in Y c Var() variance Z t collection of t-subsets of users to which at least one relay is connected to Z, Z + fields of integers and positive integers ⊕ bit-wise XOR operation between binary bits or vectors with same lengths | • | the cardinality of a set, or the length of a vector, or the length of a (sub)file in bits φ the Euler phi function x y binomial coefficient;

1. 1

 1 Evolution of micro-processors in mobile devices. . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Daily variation of video consumptions in Chicago provided by 'AT& T'. . . . . . . . . . . . . . . 1.3 A cache-aided shared-link broadcast system where a server with N files of size B bits is connected to K users equipped with a cache of size MB bits. . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 A combination network with end-user-caches, with H = 4 relays and K = 6 users, i.e., r = 2. . . . . 2.1 An IC problem with N ′ files and K ′ users. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Directed graph for the equivalent IC problem to the caching problem with N = K = 3 and with demand vector d = (1, 2, 3). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1 A combination network with end-user-caches in centralized caching systems, with H = 4 relays, K = 6 users and N = 6 files, i.e., r = 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 A combination network with end-user-caches, where H = 6, N = K = H r and r = 2. . . . . . . . . 8.3 A combination network with end-user-caches, where H = 6, N = K = H r and r = 3. . . . . . . . . 8.4 A combination network in decentralized caching systems with end-user-caches, with H = 6 relays, N = K = H r and r = 2 and 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1 A combination network with cache-aided relays and users, where H = 6, N = K = H r , r = 2 and M relay = 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1. 1

 1 Order optimality results under the constraint of uncoded cache placement . . . . . . . . . .

FIGURE 1 . 4 :

 14 FIGURE 1.4: A combination network with end-user-caches, with H = 4 relays and K = 6 users, i.e., r = 2.

( 3 .

 3 2c) holds with equality for such a choice of auxiliary random variables. As a result, we have that the bound in (3.1d) reduces to the one in (2.2d) by using (3.2c) with B = A j , and that the bound in (3.1c) reduces to the one in (2.2c) by using (3.2c) twice, once with B = A ∪ K \ J and once with B = A ∪ K, which is so because κ J = P:P⊆[N ′ ]:P ⊆(A∪K\J ) S P -P:P⊆[N ′ ]:P ⊆(A∪K) S P = P:P⊆A∪K:P∩J =∅ S P .

. 4 )

 4 Note that U {h} = U h . For a subset of relays Y ⊆ [H], the set of users who are connected to at least two relays in Y is denoted by

  In the placement phase, user k ∈ [K] stores information about the N files in its cache of size MB bits, where M ∈ [0, N]. We denote the content in the cache of user k ∈ [K] by Z k and let Z := (Z 1 , . . . , Z K ). Centralized systems allow for coordination among users in the placement phase, while decentralized systems do not. During the delivery phase, user k ∈ [K] demands file d k ∈ [N]; the demand vector d := (d 1 , . . . , d K )

1 .

 1 Kai Wan, Mingyue Ji, Pablo Piantanida and Daniela Tuninetti, "Novel Outer Bounds and Inner Bounds with Uncoded Cache Placement for Combination Networks with End-User-Caches", in preparation, to IEEE Trans. on Information Theory. [55] 2. Kai Wan, Mingyue Ji, Pablo Piantanida and Daniela Tuninetti, "Novel Outer Bounds for CombinationNetworks with End-User-Caches", in Proceedings of the IEEE Information Theory Workshop (ITW), Nov. 2017.[START_REF] Wan | Novel outer bounds for combination networks with end-user-caches[END_REF]

. 2 )

 2 In the rest of the thesis, for a set of sub-files S ⊆ T d,Z where T d,Z is given in (5.15), we denote by H(S) the joint entropy of the sub-files in S, and by H(Y |S c ) the entropy of a random variable Y conditioned on the sub-files in S c := T d,Z \ S. Other preliminary results for the converse bounds can be found in Section 6.3.

Theorem 9 .

 9 Consider a combination network with uncoded cache placement and (d, Z) such that the demands in d are distinct. For each subset Q ⊆ [H] such that |Q| ∈ [r : H], and each permutation p(K Q ), with B ≫ 1, we have

Proposition 2 .

 2 Consider a combination network with uncoded cache placement and (d, Z) where the demands in d are distinct. For a set of relays J ⊆ [H], and for two sets of sub-files S 1 , S 2 ⊆ T d,Z that are acyclic in the graph G T d,Z

. 12 ) 9 .

 129 Remark If either Y 1 = Y 2 or M 1 = M 2 ,Proposition 3 reduces to the well-known submodularity of entropy.

.14f) 6 . 4

 64 Proof of Theorem 9In (6.3b), NBx W represents the number of bits only cached by the users in W ⊆ [K]. For a demand vectord ∈ [N] whose elements are distinct, a set S ′ ⊆ [K] and a vector v = (v 1 , . . . , v |v| ) where v i ∈ S ′ , ∀i ∈ [|v|], we define f (d, S ′ , v):= i∈[|v|] F dv i ,W : W ⊆ S ′ \ {v 1 , . . . , v i } ; (6.15) by [20, Lemma 1] the set f (d, S ′ , v) forms an acyclic set in the directed graph G T d,Z . For each Q ⊆ [H] with |Q| ∈ [r : H], each permutation p(K Q ), and each demand vector d with distinct demands, Proposition 1

Example 3 .

 3 Consider the combination network in Fig. 1.4 with N = 6 and M = 2. Consider the demand vector d = (1, . . . , 6). Choose a set of relays Q and divide Q into several disjoint subsets, each of which has a length not less than r = 2. In this example, we let

Example 4 .

 4 Consider the combination network in Fig. 1.4 with N = 6 and M = 1/2. Consider the demand vector d = (1, . . . , 6). For an integer b ∈ [r : H] = [2 : 4], e.g., say b = 3, consider each set of relays Q with cardinality b. Consider a permutation p K Q and apply Proposition 2 with J = Q so as to obtain

  Focus on one relay h ∈ [H]. When we use Proposition 3 to bound the sum of two terms by the sum of two new terms, if among the two terms in the LHS of Proposition 3, one term includes X h not knowing F d p i ([K]) ,W and the other does not include X h knowing F d p i ([K]

Example 8 .

 8 Consider the network in Fig.1.4 with N = K = 6, M = t = 2 and let d = (1 : 6). For each J ⊆[START_REF] Birk | Informed source coding on demand (iscod) over broadcast channels[END_REF] where |J | = t + 1 = 3, the MAN multicast messages in (2.14) contain B/15 bits, because each file was split into K t = 15 equal length parts. Let us now look at the two-phase delivery of MAN multicast messages.

Example 9 .

 9 given by ICICS compared to CICS. Recall that RLC(m, S) represents m random linear combinations of the equal-length packets indexed by S; m random linear combinations of |S| packets are linearly independent with high probability if operations are done on a large enough finite field; the same can be obtained by using the parity-check matrix of an (|S|, |S|m) MDS (Maximum Distance Separable) code. Consider the network in Fig. 1.4 with N = K = 6, M = t = 3 and let d = (1 : 6). For each J ⊆ [6] where |J | = t + 1 = 4, we have that the MAN multicast messages in (2.14) contain B/20 bits. Let us know look at the two-phase delivery of CICS. First phase of CICS for each J ⊆ [6] of size |J | = 4, we compute the set of relays each of which is connected to the largest number of users in J , S J := arg max h∈[H] |U h ∩ J |. We then partition W J into |S J | non-overlapping equal-length pieces, W J = (W |S J | J ,h : h ∈ S J ). We transmit W |S J | J ,h to relay h ∈ S J . After considering all the sets J ⊆ [K] where |J | = 4, we see that the server has sent to relay 1 (and similarly for all other relays) the following messages

  and divide W J ,b into |R J | non-overlapping and equal-length pieces, W J ,b = {W h J ,b : h ∈ R J }. For each relay h ∈ R J , the server transmits W h J ,b to relay h which then forwards it to users in J . Each user must be able to recover its required file by recovering all the k 1,b + k 2,b subfiles that were either cached or received of its desired file; this is possible if we divide each file into k 1,b + k 2,b non-overlapping and equal-length pieces and use (n b , k 1,b + k 2,b ) MDS code to generate the subfiles before placement, where k 1,b , k 2,b and n b are given in (7.50), (7.52) and (7.48), respectively.

H 1

 1 is the collection of the sets W ∈ Z g-1 where |{V ∈ S : V ⊆ W}| = 1 -1 = 0. For each set W ∈ H 1 and each file i ∈ [N], we directly create one MDS subfile f i,W cached by users in W for each file i ∈ [N]. We say such created MDS subfiles are in Hierarchy 1. The number of created MDS subfiles per file in Hierarchy 1 is denoted by N 1 := |H 1 | = 1332. Hence, we totally create n b = N 1 + N 2 = 1422 MDS subfiles per file. Each MDS subfile in Hierarchy 1 and Hierarchy 2 is known by 5 and 6 users, respectively. Hence, each user caches k 1,b = 5N 1 /K+6N 2 /K = 360 MDS subfiles per file.

  {k}), are different. So in the delivery phase, for each user k ∈ [K], we let user k recover the created MDS subfile f d k ,W ′ where W ′ ⊇ (J \ {k}) for each J ∈ Z g where k ∈ J . Hence, the number of recovered MDS subfiles by each user in the delivery phase is k 2,b = g|Z g |/K = 378. Placement We divide each file F i into k 1,b + k 2,b non-overlapping and equal-length pieces, which are then encoded by an (n b , k 1,b + k 2,b ) MDS code. Each MDS symbol represents one MDS subfile in either Hierarchy 1 or 2 denoted by f i,W ′ and cached by users in W ′ .

  ) and create the MDS subfile f i,U {1,2} ∪C ′ ∪C ′′ cached by U {1,2} ∪ C ′ ∪ C ′′ for each file i ∈[N]. Notice that each element in C {1,2},1 and C {1,2},2 is only chosen one time. We then repeat the construction for all subsets of two relays. We recall that H 2 is the collection of the sets W ∈ Z g-1 where |{V ∈ S : V ⊆ W}| = 2 -1. Hence, considering all the set of two relays, we create the MDS subfiles for each set W ∈ H 2 . Since we create one MDS subfile corresponding to two sets in H 2 for each file i ∈ [N] (we say such MDS subfiles are in Hierarchy 2), the number of created MDS subfiles per file in Hierarchy 2 is denoted by N 2 := |H 2 |/2 = 240. In the last step, for each set W ∈ H 1 , we directly create one MDS subfile f i,W cached by users in W for each file i ∈ [N] (we say such MDS subfiles are in Hierarchy 1). The number of created MDS subfiles per file in Hierarchy 1 is denoted by N 1 := |H 1 | = 180. Hence, we totally create n b = N 1 + N 2 + N 3 = 440 MDS subfiles per file. Each MDS subfile in Hierarchy 1, 2 and 3 is known by 7, 10 and 10 users, respectively. Hence, each user caches k 1,b = (7N 1 + 10N 2 + 10N 3 )/K = 193 MDS subfiles per file. If we focus on one user k, for any sets J 1 , J 2 ∈ Z g where k ∈ J 1 and k ∈ J 2 , we can see that the created MDS subfiles f d k ,W ′ where W ′ ⊇ (J 1 \ {k}) and f d k ,W ′′ where W ′′ ⊇ (J 2 \ {k}), are different. So in the delivery phase, for each user k ∈ [K], we let user k recover the created MDS subfile f d k ,W ′ where W ′ ⊇ (J \ {k}) for each J ∈ Z g where k ∈ J . Hence, the number of recovered MDS subfiles by each user in the delivery phase is k 2,b = g|Z g |/K = 108. Placement We divide each file F i into k 1,b + k 2,b non-overlapping and equal-length pieces, which are then encoded by an (n b , k 1,b + k 2,b ) MDS code. Each MDS symbol represents one MDS subfile in either Hierarchy 1, 2 or 3 denoted by f i,W ′ and cached by users in W ′ for each file i ∈ [N].

. 66 )

 66 The created MDS subfiles for the sets in H m are defined in Hierarchy m. For each MDS subfile f i,W ′ in Hierarchy m, we have |{W ∈ Z g-1 : W ⊆ W ′ }| = m. We now focus on H m . For any set of relays Y ⊆ [H] where |Y| = m and any relay h ∈ Y, we can compute that

  we have |H m | = 0 and there is no created MDS subfile in Hierarchy m; otherwise, for each file i ∈ [N] we use the following way to create MDS subfiles for H m as described in Example 11. We focus on one set of relays Y ⊆ [H] where |Y| = m. For each relay h ∈ Y, we define that

. 70 )

 70 In Appendix A.14, we prove that N m is given in (7.47d) for m ∈ [2 : Hr + 1] and (7.47e) for m = 1.Hence, we totally create n b = H-r+1 m=1 N m MDS subfiles per file. Each MDS subfile in Hierarchy m is known by K -H-m r -mK 1 + m(g -1) users. Hence, each user caches

  created MDS subfiles f d k ,W ′ where W ′ ⊇ (J 1 \ {k}) and f d k ,W ′′ where W ′′ ⊇ (J 2 \ {k}), are different. So in the delivery phase, for each user k ∈ [K], we let user k recover the created MDS subfile f d k ,W ′ where W ′ ⊇ (J \ {k}) for each J ∈ Z g where k ∈ J . Hence, the number of recovered MDS subfiles by each user in the delivery phase is k 2,b = g|Z g |/K. Placement We divide each file F i into k 1,b + k 2,b non-overlapping and equal-length pieces, which are then encoded by an (n b , k 1,b + k 2,b ) MDS code. Each MDS symbol represents one MDS subfile in Hierarchy m ∈ [Hr + 1] denoted by f i,W ′ and cached by users in W ′ for each file i ∈ [N]. The needed memory size per file to achieve the coded caching gain g is M b N = k 1,b /(k 1,b + k 2,b ).

  addition, since |g d k 1 ,J \{k 1 } | = |g d k 2 ,J \{k 2 } | for each set J ∈ Z g and any k 1 , k 2 ∈ J , and each user recovers B(1 -M b /N)/r bits from r relays, the load on each link from relays to users is (1 -M b /N sf )/r.

  FIGURE 8.1: A combination network with end-user-caches in centralized caching systems, with H = 4 relays, K = 6 users and N = 6 files, i.e., r = 2.

FIGURE 8 . 2 :

 82 FIGURE 8.2: A combination network with end-user-caches, where H = 6, N = K = H r

FIGURE 8 . 3 :and r = 3 . 12 , 12 ,

 8331212 FIGURE 8.3: A combination network with end-user-caches, where H = 6, N = K = H r

1 .

 1 Kai Wan, Mingyue Ji, Pablo Piantanida and Daniela Tuninetti, "Caching in Combination Networks: Novel Asymmetric Coded Cache Placement and Multicast Message Generation by Leveraging Network Topology", in preparation, to IEEE Trans. on Information Theory. [54] 2. Kai Wan, Mingyue Ji, Pablo Piantanida and Daniela Tuninetti, "Caching in Combination Networks: Novel Multicast Message Generation and Delivery by Leveraging the Network Topology", in IEEE Intern. Conf. Commun. (ICC), May 2018. [57]3. Kai Wan, Daniela Tuninetti, Pablo Piantanida and Mingyue Ji, "On Combination Networks with Cache-aided Relays and Users", in Proceedings of Workshop on Smart Antennas (WSA), Mar. 2018.[START_REF] Wan | On combination networks with cache-aided relays and users[END_REF]

. 6 )N( K 1 g- 1 )=

 611 For example, consider f i,{1,2} which is divided into |R {1,2} | + 1 = 3 non-overlapping pieces. Eachrelay h ∈ R {1,2} = {1, 2} caches f i,{1,2},h with M relay B N( K 1 g-1 )= B/72 bits. So for the last piece, we have|f ′ i,{1,2} | = B/36 -2B/72 = 0 and thus no user caches any bits of f i,{1,2} . Consider nowf i,{1,6} which is divided into |R {1,6} | + 1 = 2 non-overlapping pieces. Each relay h ∈ R {1,6} = {1} caches f i,{1,6},h with M relay B B/72 bits. So |f ′ i,{1,6} | = B/36 -B/72 = B/72. Thus each user in {1, 6} caches f ′ i,{1,6}with B/72 bits. We then focus on user 1. For each set W ∈ {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 7}, {1, 8} , we have|R W | = 2and |f ′ i,W | = 0. For each set W ∈ {1, 6}, {1, 9}, {1, 10} , we have |R W | = 1 and |f ′ i,W | = B/72. So user 1 caches 3NB/72 = M user B bits. Delivery phase We let each user k recover f d k ,W where W ∈ Z g-1 and R {k}∪W = ∅. There are three steps in delivery phase: 1. In the first step, for each relay h ∈ [H] and each user k ∈ U h , relay h delivers all the cached bits of F d k to user k. More precisely, for each set W ⊆ U h where |W| = g -1, relay h delivers f d k ,W,h to user k. So by this step and the placement phase, each user k ∈ [K] can recover f d k ,W where W ∈ Z g-1 and k ∈ W. User k can also recover f d k ,W,h where W

  We divide each file F i where i ∈ [N] into k 1,b + k 2,b non-overlapping and equallength pieces, which are then encoded by (|Z g-1 |, k 1,b + k 2,b ) MDS code. The length of each MDS symbol is B/(k 1,b + k 2,b ). For each W ∈ Z g-1 and each file i ∈ [N], there is one MDS symbol denoted by f i,W and we divide

( a )

 a For each relay h ∈ [H] and each user k ∈ U h , relay h delivers all the cached bits of F d k to user k. More precisely, for each set W ⊆ U h where |W| = g -1, relay h delivers f d k ,W,h to user k. (b) For each set W ⊆ U h and each user k ∈ W, where |W| = g -1 and |R W | > 1, relay h delivers

  We divide each file F i where i ∈ [N] into k 1,b + k 2,b non-overlapping and equallength pieces, which are then encoded by (n b , k 1,b +k 2,b ) MDS code. The length of each MDS symbol is B/(k 1,b + k 2,b ). Each MDS symbol represents one MDS subfile in Hierarchy m ∈ [Hr + 1]. For each MDS subfile f i,W ′ in Hierarchy m which is created from the multicasting opportunities among m relays (assumed to be Y), we divide it into m + 1 non-overlapping pieces,

  Delivery phase We let each user k ∈ [K] recover the created MDS subfile f d k ,W ′ where W ′ ⊇ (J \ {k}) for each J ∈ Z g where k ∈ J . There are three steps in delivery phase: (a) For each relay h ∈ [H] and each user k ∈ U h , relay h delivers all the cached bits of F d k to user k. More precisely, for each set W ⊆ U h where |W| = g -1, relay h delivers f d k ,W ′ ,h to user k where W ′ ⊇ W. (b) For each set W ⊆ U h and each user k ∈ W where |W| = g -1, assuming the created subfile for each i ∈ [N] is f i,W ′ by leveraging multicasting opportunities among relays in Y where

FIGURE 9 . 1 :

 91 FIGURE 9.1: A combination network with cache-aided relays and users, where H = 6, N = K = H r , r = 2 and M relay = 1.

Example 13 .U 1 =

 131 Consider a relay network with end-user-caches where N = K = 5, H = 5, g = 3 and {1, 2, 3}, U 2 = {1, 3, 4}, U 3 = {1, 4, 5}, U 4 = {2, 4, 5}, U 5 = {2, 3, 5}. Each user is connected to three relays and each relay is connected to three users. We want to use our asymmetric coded placement scheme in Section 7.4.1. In this example, we can see |Z g-1 | = 10. Each user should cache the subfile f i,W if R W = ∅ for each file i ∈ [N]. Hence, each user caches k 1,b = 4 subfiles per file. In the delivery phase, each user k should recover f d k ,J \{k} for each set J ∈ Z g and k ∈ J . Hence each user should recover k 2,b = 3 subfiles. So the needed memory size to achieve g = 3 is M b = Nk 1,b /(k 1,b + k 2,b ) = 20/7. For the scheme in [50], each user caches k 1 = 6 subfiles per file and recovers k 2 = 3 subfiles. Hence, the needed memory size to achieve g = 3 is M ZY = Nk 1 /(k 1 +k 2 ) = 10/3 > 20/7.

Example 14 .U 1 = 1 {1, 2 ,

 14112 Consider a relay network with end-user-caches where N = K = 5, H = 5, M = 2 and {1, 2, 3}, U 2 = {1, 3, 4}, U 3 = {1, 4, 5}, U 4 = {3, 4, 5}, U 5 = {2, 3, 5}, i.e., we changed U 4 from {2, 4, 5} in Example 13 to {3, 4, 5} so that the number of connected relays to each user is not the same. Let d = (1 : 5). We use SRDS with MAN placement and indicate the multicast messages as W h J ,L = ⊕ k∈J T h k,J \{k} , where in this example we added the subscript L to indicate that the message has length L bits. Then, we have the server transmit W 3},B/10 , W

Algorithm 5

 5 New Step 5) for Algorithm 4 1. initialization: i = 1; Define that L h = J ⊆U h |W h J | for each h ∈ [H];2. sort all the relays h ∈ [H] by L h , i.e., C(1) represents the relay whose L h is maximal and C(H) represents the relay whose L h is minimal;3. if there exists a set J ⊆ U C(i) such that |W C(i) J| > 0 and there exists a set of relays (denoted by Q) where Q ⊆ {C(i + 1), . . . , C(H)} and each relay h ∈ Q is connected to all the users in J , then, (a) choose one relay h ∈ Q where L(h) = max h∈Q L(h), and move min{|WC(i) J |, (L C(i) -L h )/2} bits from |W C(i) J | to W h J ; (b) update L(h)for relay h and update L(C(i)) for relay C(i); else then, i = i + 1; 4. if i < H, go to Step 2) of Algorithm 4; 5. for each relay h and each J ⊆ U h where W h J = ∅, transmit W h J to relay h and relay h transmits W h J to each user in J ;

Theorem 27 .

 27 For a (H, r, M, N) combination network with t = KM/N ∈ [0 : K], the max link-load satisfiesR ⋆ c,u ≤ R 1 := K t+1 -K-min(K,N)

3 .

 3 if P i = ∅ for all i ∈ [ 2k+1 k /(2k + 1)], then Output P i for all i ∈ [ 2k+1 k /(2k + 1)];else, then go to Step 1);We can use Algorithm 2 to construct the groups. However, it is hard to prove the existence of the group division satisfying the full-rank condition for the general case. Instead of proving the existence of solution for Problem 1, we introduce Problem 2, the existence of whose solution is easier to analyse. Since the number 2k + 2 appears in each subsets of Problem 1, we do not consider the number 2k + 2 in Problem 2.In Appendix A.8 we prove that the we can add 2k + 2 into each subset in the solution of Problem 2 to get one solution of Problem 1.

46 ) 2 > Q p+q d 1 >e 1

 46211 In other words, defining linear maps d 0 , d 1 and d 2 where d 2 is injective and d 0 is surjective, we have the following sequence of Q-linear mapsQ d Q pq d 0 > Q[ζ] (A.47) Define {e α : α ∈ [0 : pq -1]} is a base of Q pq and {τ p,βp : β p ∈ [0 : q -1]} ∪ {τ q,βq : β q ∈ [0 : p -1]} is a base of Q p+q . We have d 0 (e α ) = ζ α , d 1 (τ p,βp ) = spq+βp , d 1 (τ q,βq ) = βq .In addition, we have d 0 d 1 (τ p,βp ) = 0, d 0 d 1 (τ q,βq ) = 0 andd 1 d 2 (1) = 0. Thus im(d 2 ) ⊂ ker(d 1 ), im(d 1 ) ⊂ ker(d 2 ). Now we prove im(d 2 ) = ker(d 1 ). For any Λ

Define λ α = 1

 1 if ζ α ∈ E and 0 if not. Thus we have pq-1 α=0 λ α ζ α = 0, (A.50)

  1.2 State-of-the-Art and Main Contributions for Cache-aided Shared-link Networks 1.2.1 Past Work on Cache-aided Shared-link Networks

  A converse bound for the IC problem based on the polymatroid properties of the entropy function was proposed in[START_REF] Blasiak | Lexicographic products and the power of non-linear network coding[END_REF] Theorem 3.1]. For a multiple unicast IC problem, a looser version of[35, Theorem 1] but easier to evaluate was given in[35, Corollary 1]. In[35, Corollary 1] one needs knowledge of the subgraphs not containing a directed cycle in the directed graph generated based on the side information sets (more detailed can be found in Section 2.3). In this work, we shall use this looser converse bound, referred to as acyclic index coding converse bound, to lower bound the performance of caching schemes with uncoded cache placement.

TABLE 1 . 1 :

 11 Order optimality results under the constraint of uncoded cache placement

  Theorem 2. (Acyclic Subgraph Converse Bound [35, Corollary 1]) If (R 1 , . . . , R N ′ ) is achievable for the multiple unicast IC problem (A j , D j = {j}) : j ∈ [N ′ ] represented by the directed graph G then it must satisfy j∈J

	of messages. A looser (compared to [35, Theorem 1]) converse bound was proposed in [35, Corollary 1]
	and is stated next.
	.2d)
	Note that the constrain in (2.2d) is from the first decoding stage at receiver j ∈ [K ′ ], and (2.2c) from the
	second decoding stage at receiver j ∈ [K ′ ].
	2.3 The Index Coding Problem: Acyclic Subgraph Converse Bound for Mul-
	tiple Unicast Index Coding
	If K ′ = N ′ and D j = {j} and j ∈ A j for each j ∈ [N ′ ], the multiple unicast IC problem can be represented
	as a directed graph G, where each node in the graph represents one user and its demanded message, and
	where a directed edge connects node i to node j if user j knows message M i . By the submodularity of
	entropy, a converse bound was proposed in [34, Theorem 3.1] for the symmetric rate case and extended
	in [35, Theorem 1] to the case where messages can have different rates. Due to the high computational
	complexity, the converse bound [35, Theorem 1] can only be evaluated for IC problems with limited number

  R) is said to be achievable if there exit placement probability mass function, encoding function and decoding functions such that lim B→∞ P

		• The (worst-case) load with uncoded cache placement is
		R ⋆ d,u := inf{R : (M, R) is achievable with uncoded cache placement}.	(2.12)
	2.5 The Caching Problem: Achievability of (1.1b) and (1.3), and of (1.5b)
		and (1.6)
	Centralized Cache-aided Systems We start with the description of cMAN. Let M = t N K for some positive
	integer t ∈ [0 : K]. In the placement phase, each file is split into K t non-overlapping equal size sub-files of
	B ( K t ) as	bits. The sub-files of F i are denoted by F i,W for W ⊆ [K] where |W| = t. User k ∈ [K] fills its cache
		(B) err,d = 0, where P	(B) err,d was defined in (2.11).

  Caching Problem with Uncoded Cache Placement into an Index Coding Problem Under the constraint of uncoded cache placement, when the cache contents and the demands are fixed, the delivery phase of the caching problem is equivalent to the following IC problem. Denote the set of distinct demanded files in the demand vector d by N (d). For each i ∈ N (d) and for each W ⊆ [K], the subfile F i,W (containing the bits of file F i only within the cache of the users indexed by W) is an independent message in the IC problem with user set [K]. Hence, by using the notation introduced in Sections 2.1 and 2.4, we have K ′ = K and N ′ ≤ |N (d)|(2 K -1). For each user k ∈ [K] in this general IC problem, the desired message set and the side information sets are given by

  Chapter 4. Optimal Converse Bound under the Constraint of Uncoded Cache Placement for Cache-aided Shared-link Broadcast Networks Remark 3. For the case N ≥ K, the claim of Theorem 5 is trivially obvious because the converse bound in (4.1c) coincides with the cMAN scheme in (1.1b), as already pointed out in the Introduction. Our proof

.

[START_REF] Sengupta | Improved approximation of storage-rate tradeoff for caching via new outer bounds[END_REF]

The load in the caching problem is the number of transmissions (channel uses) needed to deliver one file to each user, thus the inverse of R sum-rate for |X | = 2 indeed corresponds to the load in

(1.3)

.

  .33e) Chapter 4. Optimal Converse Bound under the Constraint of Uncoded Cache Placement for Cache-aided

	Shared-link Broadcast Networks
	With this we have

  As we shall see, this 'baseline' bound can be improved by means of Propositions 2 and 3. We use the idea highlighted in Example 3 to get the following lower bound, whose proof can be found in Theorem 6.5.

.3c) Remark 5. The lower bound in Theorem 9 can be numerically computed by means of a linear program with variables (R ⋆ c,u , x W : W ⊆ [K]) and constraints in (6.3a)-(6.3c). Theorem 10. Consider a combination network with uncoded cache placement and (d, Z) such that the demands in d are distinct. For each set of relays Q ⊆ [H], each integer a ∈ [⌊|Q|/r⌋], each disjoint

  6. The lower bound in Theorem 10 can be computed by means of a linear program with variables (R ⋆ c,u , x W : W ⊆ [K]) and constraints in (6.4), (6.3b) and (6.3c). We use the idea of Example 4 to get the following converse bound and the detailed proof is in Theorem 6.6. Theorem 11. Consider a combination network with uncoded cache placement and (d, Z) such that the demands in d are distinct. For each integer b ∈ [r : H], each set of relays Q ⊆ [H] with |Q| = b,

each permutation p(K Q ), with B ≫ 1, the bound in (6.39) holds, satisfying (6.3b)-(6.3c) and for each permutation p([K]), the following must hold

  .52e) we use Fano's inequality and the fact that B a+1 is acyclic and B a+2 does not include the side information of the user requiring B a+1 . We then use the similar method in Theorem 11 to bound H(X Q |B c a+2 ). Kai Wan, Mingyue Ji, Pablo Piantanida and Daniela Tuninetti, "Novel Inner Bounds for Combination Networks with End-User-Caches", in Proceedings of the 55th Allerton Conf. Commun., Control,

	Networks with End-user-caches 7.1 Chapter Overview and Related Publications Comp., Oct. 2017. [62] 8. Kai Wan, Mingyue Ji, Pablo Piantanida and Daniela Tuninetti, "Caching in Combination Networks: A Novel Delivery by Leveraging the Network Topology", in preparation, to IEEE Inf. Theory Workshop Remark Chapter 7 Novel Inner Bounds for Combination (ITW), available at arXiv:1802.10479, Apr. 2018. [65]
	Cache Placement in Combination Networks with End-User Caches", in IEEE Int. Symp. Inf. Theory
	(ISIT), Jun. 2018. [56]
	4. Kai Wan, Mingyue Ji, Pablo Piantanida and Daniela Tuninetti, "Caching in Combination Networks:
	Novel Multicast Message Generation and Delivery by Leveraging the Network Topology", in IEEE
	Intern. Conf. Commun. (ICC), May 2018. [57]
	5. Kai Wan, Daniela Tuninetti, Pablo Piantanida and Mingyue Ji, "A Novel Asymmetric Coded Place-
	ment in Combination Networks with end-user Caches", in Proceedings of IEEE Infor. Theory Appli-

12.

If N < K, we can not find a demand vector where each user has distinct demand. In this case, it is possible to find demand vectors such that every user demands a different file and, in turns, it is relatively straightforward to apply the "acyclic index coding converse bound" (see

Proposition 1)

. When N < K one should consider many subsystems with only min(N, K) = N users with distinct demands (as we did in Section 4.2.1 for shared-link model), which is not conceptually more difficult but requires a somewhat heavier notation.

This chapter provides novel inner bounds for combination networks with end-user-caches. The achievable schemes for combination networks could be divided into separation and non-separation approaches, dependent of whether we generate the multicast messages on the network topology. In Section 7.2, based on separation approach, we propose four schemes to deliver cMAN multicast messages. Based on non-separation approach, we first propose a delivery scheme in Section 7.3 by generating multicast messages on network topology. With this delivery scheme, In Section 7.4 we then propose an asymmetric coded placemen.

Related Publications

1. Kai Wan, Mingyue Ji, Pablo Piantanida and Daniela Tuninetti, "Caching in Combination Networks: Novel Asymmetric Coded Cache Placement and Multicast Message Generation by Leveraging Network Topology", in preparation, to IEEE Trans. on Information Theory. [54] 2. Kai Wan, Mingyue Ji, Pablo Piantanida and Daniela Tuninetti, "Novel Outer Bounds and Inner Bounds with Uncoded Cache Placement for Combination Networks with End-User-Caches", in preparation, to IEEE Trans. on Information Theory. [55] 3. Kai Wan, Mingyue Ji, Pablo Piantanida and Daniela Tuninetti, "On the Benefits of Asymmetric Coded cation Workshop (ITA), Feb. 2018. [59] 6. Kai Wan, Daniela Tuninetti, Mingyue Ji, and Pablo Piantanida, "State-of-the-art in Cache-aided Combination Networks", in Proceedings of the IEEE Asilomar Conf., Nov 2017. [61] 7.

  We now generalize the scheme to transmit the messages W J where J ∈ V 2 , described in the above examples to the general case of t = 1 and H ≥ 2r. We use cMAN cache placement and let W J = ⊕ j∈J F d j ,J \{j} for each J ⊆ [K] where |J | = 2. Notice that if t = 1, V 2 contains all the sets of two users k and k ′ where

are 1.6111, 19/6 ≈ 3.1667, and 29/12 ≈ 2.41667, respectively.

  By the symmetry of combination networks, for each relay a ∈ H k \ {h ′ }, there must exist one set J ′ with |J ′ | = t where a is in the set arg max b∈[H] |U b ∩ J ′ |, which also includes |S J | elements, and the user

  and by user k. So we can add W ′ such that user k and k ′ can recover their desired pieces. Similarly, there are |H k \ {h ′ }| = r -1 relays as relay a. So W |S| J ,h,h ′ can be added with the other r -1 pieces with the same length (each of which is demanded by one user in Q k h,h ′ ) and then be transmitted to relay h ′ .Performance For each W J the server directly transmits W |S J | J ,h to relay h ∈ S J in the first phase for a total of |W J | = B/ K t bits. In the second phase, for relay h ∈ S J , |J \ U h | users recover W|S J | J ,h,h ′ to each user k ∈ J \ U h for h ′ ∈ H k )in one linear combination with other r -1 pieces of the same length (equal to

	So the server transmits W	B t )|SJ | r( K	|S| J ,h,h ′ and W	|S J ′ | J ′ ,a,h |S J | J ,h .

  After considering all the pieces of the multicast messages W J , for relay 1 we have (but similarly for all

	P 1 1,{3} = {W 1 {1,3,5,6},1,1 , W 4 {1,2,5,6},4,1 , W 4 {1,3,4,6},4,1 },	(7.23)
	P 1 2,{1} = {W 1 {1,2,4,5},1,1 , W 4 {1,2,5,6},2,1 , W 4 {2,3,4,5},2,1 },	(7.24)
	P 1 2,{3} = {W 1 {2,3,5,6},1,1 , W 4 {1,2,5,6},4,1 , W 4 {2,3,4,5},4,1 },	(7.25)
	P 1 3,{1} = {W 1 {1,3,4,5},1,1 , W 4 {1,3,4,6},2,1 , W 4 {2,3,4,5},2,1 },	(7.26)
	P 1 3,{2} = {W 1 {2,3,4,6},1,1 , W 4 {1,3,4,6},3,1 , W 4 {2,3,4,5},3,1 };	(7.27)
	4 {1,2,5,6},1 into r = 2
	equal-length parts and denote W 4 {1,2,5,6},1 = {W 4 {1,2,5,6},1,k : k ∈ H 5 }. where H 5 = {2, 4}; we then let user
	5 recover the first part W 4 {1,2,5,6},1,2 from relay 2, and the second part W 4 {1,2,5,6},1,4 from relay 4. Since user
	1, who is connected to relay 2, knows W 4 {1,2,5,6},1 , we put W 4 {1,2,5,6},1,2 in T 2 5,{1} . Since user 3 connected to
	relay 4 knows W 4 {1,2,5,6},1 we put W 4 {1,2,5,6},1,4 in P 4 5,{3} .
	We do the same procedure for user 6. We partition W 4 {1,2,5,6},1 into r = 2 equal-length parts and denote
	W 4 {1,2,5,6},1 = {W 4 {1,2,5,6},1,k : k ∈ H 6 } and put W 4 {1,2,5,6},1,3 in P 3 6,{2} , W 4 {1,2,5,6},1,4 in P 4 6,{3} .
	other relays)
	P 1 1,{2} = {W 1 {1,2,4,6},1,1 , W 4 {1,2,5,6},3,1 , W 4 {1,3,4,6},3,1 },	(7.22)

  It can be seen that CICS treats W 4 {1,2,5,6},1 demanded by user 1 and 2 as two independent pieces. It lets user 1 recover |W 4 {1,2,5,6},4 |/2 bits from relay 1 and |W 4 {1,2,5,6},4 |/2 bits from relay 2 in two linear combinations, and lets user 2 recover |W 4

	{1,2,5,6},4 |/2 bits from relay 1 and
	|W 4 {1,2,5,6},4 |/2 bits from relay 3 in two other linear combinations.
	Instead, we can leverage the following multicasting opportunity. We put
	RLC(|W 4 {1,2,5,6},4 |/(2P ), W 4 {1,2,5,6},4 ) in X 1 {1,2},{3}

  3, 4, 11, 12, 13, 14, 15, 16}, U 3 = {1, 5, 6, 7, 11, 12, 13, 17, 18, 19}, U 4 = {2, 5, 8, 9, 11, 14, 15, 17, 18, 20}, U 5 = {3, 6, 8, 10, 12, 14, 16, 17, 19, 20}, U 6 = {4, 7, 9, 10, 13, 15, 16, 18, 19, 20}.

  .[START_REF]Novel outer bounds and inner bounds with uncoded cache placement for combination networks with end-user-caches[END_REF] Let us focus on the set of two relays, e.g., {1, 2}, whose set of common connected users is U {1,2} = {1, 2, 3, 4}. We choose (g -1) -|U {1,2} | = 1 element in U 1 \ U {1,2} , say 5, and in U 2 \ U {1,2} , say 11; we let W ′ = U {1,2} ∪ {5} ∪ {11}, which has cardinality 6, and generate one MDS subfile f i,W ′ to be cached by the users in W ′ for each file i ∈ [N]. By construction, we can see that W ′ ∩ U 1 = {1, 2, 3, 4, 5} ∈ Z g-1 andW ′ ∩U 2 = {1, 2, 3, 4, 11} ∈ Z g-1 .Hence, in the delivery phase, each user k ∈ U 1 \{1, 2, 3, 4, 5} = [6 : 10] will recover f d k ,W ′ from relay 1 and each user k ∈ U 2 \ {1, 2, 3, 4, 11} = [12 : 16] will recover f d k ,W ′ from relay 2. Similarly, each time we choose one set

  [START_REF]Caching in combination networks: Novel multicast message generation and delivery by leveraging the network topology[END_REF] and create the MDS subfile f i,U {1,2} ∪C ′ ∪C ′′ cached by U {1,2} ∪ C ′ ∪ C ′′ for each file i ∈ [N]. Notice that each element in C {1,2},1 and C {1,2},2 is only chosen one time. We then repeat the construction for all subsets of two relays. We define H 2 as the collection of the sets W ∈ Z g-1 where |{V ∈ S : V ⊆ W}| = 2 -1, i.e., there exists one pair of relays {h 1 , h 2 } such that W ⊇ U {h 1 ,h 2 } . Hence, considering all the set of two relays, we create the MDS subfiles for each set W ∈ H 2 . Since we create one MDS subfile corresponding to two sets in H 2 for each file i ∈ [N] (we say such MDS subfiles are in Hierarchy 2), the number of created MDS subfiles per file in Hierarchy 2 is denoted by N 2 := |H 2 |/2 = 90.

  represents the set of users connected to at least two relays in Y. In this example, we haveG {1,2,3} ∩ U 1 = U {1,2} ∪ U {1,3} = {1, 2, 3, 4, 5, 6, 7} ∈ Z g-1 , (7.60) G {1,2,3} ∩ U 2 = U {1,2} ∪ U {2,3} = {1,5, 6, 7, 11, 12, 13} ∈ Z g-1 , (7.61) G {1,2,3} ∩ U 3 = U {1,3} ∪ U {2,3} = {1, 5, 6, 7, 11, 12, 13} ∈ Z g-1 . (7.62) Hence, we can create one MDS subfile f i,G {1,2,3} cached by users in G {1,2,3} which can cover three sets inZ g-1 for each file i ∈ [N]. In the delivery phase, each user k in U 1 \ G {1,2,3} = [8 : 10], in U 2 \ G {1,2,3} = [14 : 16], in U 3 \ G {1,2,3} =[17 : 19] will recover f d k ,W ′ from relay 1, 2 and 3, respectively. We then repeat the construction for all subsets of three relays. We define H 3 as the collection of the sets W ∈ Z g-1 where{V ∈ S : V ⊆ W} = 3 -1, i.e.,there exist two pairs of relays {h 1 , h 2 } such that W ⊇ U {h 1 ,h 2 } . Hence, considering all the set of three relays, we create the MDS subfiles for each set W ∈ H 3 . Since we create one MDS subfile corresponding to three sets in H 3 for each file i ∈ [N] (we say such MDS subfiles are in Hierarchy 3), the number of created MDS subfiles per file in Hierarchy 3 is denoted by N 3 := |H 3 |/3 = 20. In the next step, we create MDS subfiles for each of two relays, e.g., {1, 2} whose set of common connected users is U {1,2} = {1, 2, 3, 4}. Since the set U {1,2} ∪ U {1,3} = {1, 2, 3, 4, 5, 6, 7} which is in the collection Z g-1 , has already been covered by Hierarchy 3, we need not to create MDS subfile for this set in this step. Similarly, we need not to create MDS subfile for U {1,2} ∪ U {1,h} where h ∈ [H] \ {1, 2} in this step. Hence, each time we choose one set

	G {1,2,3} = {1, 2, 3, 4, 5, 6, 7, 11, 12, 13},	(7.59)

  .68) Each time we choose one element (denoted by C h ) in C h,Y for each h ∈ Y. We create one MDS subfile ∪ G Y for each file i ∈ [N]. Notice that each element in C h,Y where h ∈ Y is only chosen one time. Since G Y is the set of users connected to at least two relays in Y, We

	can compute that
			|G Y | = K -	H -m r	-m	H -m r -1	(7.69)
	From (7.67) and (7.69), we can see that each MDS file in Hierarchy m is known by K
	f i, ∪ h∈Y	C h ∪G Y	cached by users in ∪

h∈Y

C h

  .3a) Placement phase As the asymmetric coded placement scheme in Chapter 7.4, we divide each F i into k 1,b + k 2,b = 36 non-overlapping and equal-length pieces, which are then encoded by (n b , k 1,b + k 2,b ) = (45, 36) MDS code. The length is each MDS symbol is B/36.For each W ∈ Z g , there is one MDS symbol denoted by f i,W . However, different to the asymmetric coded placement scheme, not the whole symbol f i,W is stored in the cache of each user in W. Instead, we divide f i,W into |R W | + 1 non-overlapping parts (but not necessary with identical length), f

  9.7) representing the unknown bits in f d k ,W of user k. We divide T k,W into |R {k}∪W | non-overlapping and equal-length pieces, T k,W = {T k,W,h : h ∈ R {k}∪W }. After considering all the MDS coded symbols demanded by all the users, for each relay h ∈ [H] and each set J ⊆ U h where |J | = g, we create the multicast message

  we don't further partition T 1,{2,4} which includes B/72 bits. Similarly, each of T 2,{1,4} and T 4,{1,2} has B/72 bits. Hence, V 1 {1,2,4} = T 1,{2,4} ⊕ T 2,{1,4} ⊕ T 4,{1,2} including B/72 is transmitted from the server to relay 1, which then forwards it to users in {1, 2, 4}.

  leveraging multicasting opportunities among relays in Y. More precisely, for each relay h ∈ [H] and each set J ⊆ U h where |J | = g, we create the MAN-like multicast message ⊕ k∈J P k,J \{k} which is to be sent to relay h and then forwarded to the users in J . It is also easily to check that each subfile in the multicast message in (9.8) has the same length.

The smallest value of r not satisfying the condition in Theorem

is 23. If r = 23 and H = 2r = 46, in the network there are more than 8.23 × 10 12 users, which is not practical. Note that the proof in Appendix A.7 fails when r ≥ 23 but this does not imply that the group division cannot be found for r ≥ 23. We conjecture that the claim of the theorem is true in general.

We would like to perform the operations "+" and "-" on some finite field of sufficiently large size. In other words, with an abuse of notation, we use WJ to denote both the binary multicast messages as well as its representation on some higher field size. In this example we need a field size larger than

3; on GF(3) the "-1" becomes "+2" so that X1 = W {1,6} + W {2,5} + W {3,4} , X2 = W {1,6} + 2W {2,5} + 2W {3,4} , and thus X1 + X2 = (2W {1,6} + 3W {2,5} + 3W {3,4} ) mod 3 = 2W {1,6} , etc.

For each pair of users J1 = {k1, k2}, we can choose any one of them (denoted by k ′ ) and write the equation i∈H k ′ a1,i,1 = 0 which can also lead to i / ∈H k ′ a1,i,1 = 0 from (7.9a). Thus, the interference of W {1,20} for these two users is eliminated. Here we choose the user connected to relay 6, i.e., k ′ = k1.

Acknowledgements

Optimality Results

We first give the following information theoretical optimality results of the proposed asymmetric coded placement scheme, whose proof is in Appendix A.12.

Theorem 18. For an (H, r, M, N) combination network, when M ∈ (K-H+r-1)N K , N , we have

Remark 16. As claimed in Appendix A. [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF], when M = (K-H+r-1)N K corresponding to g = K 1 , the proposed non-separation cache placement is uncoded. The description of the placement can be simplified as follows.

We divide each file i ∈ [N] into H r-1 non-overlapping and equal-length subfiles. For each subset of relays Y ⊆ [H] where |Y| = Hr + 1, there is a subfile of each file i ∈ [N] known by users in G Y .

In the following, we introduce the optimality results under the constraint of uncoded cache placement.

We first compare the cut-set converse bound in (6.2), the converse bound in Theorem 11 and the aforementioned proposed schemes, in order to derive the following optimality results under the constraint of uncoded cache placement, whose detailed proof can be found in Appendix A.10.

Theorem 19. For combination networks with end-user-caches, under the constraint of uncoded cache placement and N

when t ∈ [K -2 : K]; (8.2c) which is achieved by DIS, CICS and ICICS.

3. M ≤ N K . The optimal max link-load

, when H = 2r, (8.2e)

which is achieved by IES.

By using the techniques in [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF], in the above regimes the mentioned schemes are optimal to within a factor 2.

We then compare the cut-set converse bound and the achieved max link-loads of CICS and IES to derive the following order optimality results, whose detailed proof is in Appendix A.11.

Theorem 20. For combination networks with end-user-caches, under the constraint of uncoded cache placement and N ≥ K = H r , we have 1. DIS and the scheme in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] is order optimal within a factor of min{H/r, t + 1}.

2. M ≤ tN K , CICS is order optimal within a factor of 1 + t/r.

3. M ≤ rN K , CICS is order optimal within a factor of 2.

4. M ≤ tN K , and t/r → 0, CICS is order optimal within a factor closed to 1.

5. H > 2r and M ≤ N K , IES is order optimal within a factor of 2r 2r-1 ≤ 4 3 .

By using the techniques in [START_REF] Yu | Characterizing the rate-memory tradeoff in cache networks within a factor of 2[END_REF], in each of the above regimes the mentioned scheme is optimal to within the previous factor multiplied by 2.

Notice that in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF], where it was proved that the caching schemes in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF] is order optimal within factor max{6 √ 3, 6 log(N/M)} and thus when M is small the factor becomes large. In this thesis, we give the order optimality results for small memory size M.

Comparison to Existing Schemes

Comparing the achieved loads in [START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF] and (1.7), we have the following theorem.

Theorem 21. For a (H, r, M, N) combination network, it holds that

where R MJ defined in (1.7) is achieved by the caching schemes in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF]. 5. (M, R) = (6, 0) where each user caches the full information of all the N files.

It can be seen that when M = 1, IES coincides with the enhanced cut-set converse bound in Theorem 7

and with the converse bound under the constraint of uncoded placement in Theorem 12. So it corresponds to the optimality results in (8.2e). When M = 6/5, the asymmetric coded placement coincides with the enhanced cut-set converse bound in Theorem 7, which is strictly lower than the converse bound under the constraint of uncoded placement in Theorem 12. So in this case, uncoded cache placement is sub-optimal.

When M = 3, the asymmetric coded placement coincides with the enhanced cut-set converse bound in Theorem 7, which corresponds to the optimality results in Theorem 18.

Examples for

We then compare the performance of the proposed caching schemes to the existing caching schemes in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF], [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF]. In these examples, the caching scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] outperforms the one in [START_REF] Ji | On the fundamental limits of caching in combination networks[END_REF]. So we only plot the caching scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF]. As a converse bound, we use the enhanced cut-set converse bound in Theorem 7.

We also plot the ratios R IES /R ZY of IES, min(R ICICS , R SRDS )/R ZY of ICICS and SRDS with cMAN placement, R b /R ZY of the asymmetric coded cache placement scheme, and R ⋆ e /R ZY of the converse bound in Theorem 7. We plot the ratio of max-link loads as otherwise their difference would not be clearly visible on a small figure.

In Fig. 8.2 and 8.3, we consider the combination network with H = 6, r = 2 and H = 6, r = 3, respectively. It can be noted from the right-hand side figures of Fig. 8.2 and 8.3, that the blue curves, which represent the asymmetric coded placement scheme, are never above 1, that is, it is never inferior in performance to the caching scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF]. Moreover, the asymmetric coded placement scheme coincides with the enhanced cut-set converse bound when M ≥ 10 if r = 2 and when M ≥ 16 if r = 3. In addition, the proposed delivery schemes with cMAN placement outperform the asymmetric coded placement scheme when M ≤ 1.6 if r = 2 and when M ≤ 10 if r = 3.

Numerical Evaluations for Decentralized Combination Networks with End-user-caches

Following similar steps to [START_REF]Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF], we can extend our proposed delivery schemes (DIS, IES, CICS, ICICS and SRDS), to decentralized systems in combination networks. The cache placement phase is the same as dMAN in [START_REF]Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF], i.e., each user k ∈ [K] stores MB/N bits of each file independently at random. Given the

for any relay h and any user k ∈ U h . (9.3d)

The achieved loads are

for any relay h and any user k ∈ U h . (9.3g)

Compared to the caching scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF], we have the following corollary.

Corollary 2. The achievable memory-load tradeoff region for (H, r, N) combination network from the proposed scheme in Theorem 24 is strictly larger than the one of [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF].

Compared to the cut-set converse bound in Theorem 23, we can derive the following optimality result on the max link-load from the server to relays whose proof is in Appendix A.16.

Theorem 25. In a (H, r, M relay , M user , N) combination network, if the memory pair (M relay , M user ) can be obtained by memory-sharing among the following four memory pairs, 0, (K-H+r-1)N

, (N/r, 0) and (0, N), the optimal max link-load from the server to relays is

achieved by the proposed scheme in Theorem 24.

From a similar proof of Theorem 25, we can derive the following optimality result on the load pair (R s→r , R r→u ).

Chapter 9. Cache-aided Extended Models Theorem 26. In a (H, r, M relay , M user , N) combination network, if the memory pair (M relay , M user ) can be obtained by memory-sharing among the following three memory pairs, 0, (K-H+r-1)N K , (N/r, 0) and (0, N), the optimal max link-load pair is

achieved by the proposed scheme in Theorem 24.

For combination networks with cache-aided relays and users, we first revise the caching scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] which divides each file into two parts and the packets transmitted from the server are independent of the cached contents of relays. The memories-loads tradeoff of the scheme in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] is the lower convex envelope of the two groups of points.

1. (M relay , M user ) = (0, N(g -1)/K 1 ) where g ∈ [1 :

For each point in this group, we can see that relays do not have memory and the scheme is equivalent to the one for combination networks with end-user-caches described in Chapter 5.

where t 1 ∈ {0, K 1 } and (M relay , M user ) = (0, N). In this case, each relay directly caches s h i such that the server needs not to transmit any packets to relays. If t 1 = 0, each user does not cache any bits. In the delivery phase, each relay

So it caches all the N files and (R s→r , R r→u ) = (0, 0).

If (M relay , M user ) = (0, N), we also have (R s→r , R r→u ) = (0, 0).

Compared to the converse bound in Theorem 24, it is obvious that the max link-load from relays to users achieved by the above scheme is optimal. To reduce the max link-load from the server to relays, we can directly replace the used caching scheme for combination networks with cache-end-users in [START_REF] Zewail | Coded caching for combination networks with cache-aided relays[END_REF] by our proposed asymmetric coded placement scheme in Chapter 7.4, which corresponds to Group 1 in Theorem 24.

So we can reduce R s→r without increasing R r→u . Hence we can prove Corollary 2.

Moreover, we propose a novel caching scheme, in which the users can leverage the cached contents of the connected relays to decode the coded messages transmitted from the server, to further reduce R s→r . In the rest of this subsection, we present our proposed scheme to achieve Theorem 24. We start by an example to illustrate the main idea of the proposed scheme.

Example 12 (H = 5, r = 3, N = 10, M relay = 25/12 and M user = 5/12, g = 3). In this example, we have To achieve g = 3, we impose that each demanded subfile of each user which is neither stored in its memory nor in the memories of its connected relays, is transmitted from the server in one linear combination including other g -1 = 2 subfiles.

Example 15. Consider the network in Fig. 1.4 with N = 2, M = 1 and d = (1, 1, 1, 2, 2, 2). We use cMAN placement phase and each sub-file F i,W where i ∈ [START_REF] Birk | Informed source coding on demand (iscod) over broadcast channels[END_REF], W ⊆ [START_REF] Birk | Informed source coding on demand (iscod) over broadcast channels[END_REF] and |W| = 1, has length equal to B/6. In the delivery phase, we firstly use a similar idea of SRDS to transmit F d k ,W where k / ∈ W and there exist at least one relay connected to the users in {k} ∪ W, i.e., {k} ∪ W = {1, 6}, {2, 5}, {3, 4}. Different to SRDS, we observe that F 1,{2} , which will be transmitted to relay 1, is demanded by both of user 1 and 3.

So we put F 1,{2} in T 1 {1,3},{2} the set of bits which need to be recovered by user 1 and 3 from relay 1 and are known by user 2. Hence, in this step we have

So we transmit The above example inspires us to profit from the multicasting opportunities arised from one file demanded by several users, and the future work aims to search a general scheme leveraging these opportunities.

Linear Programming of Converse Bound in Theorem 12

By improving the extended acyclic index coding converse bound to combination networks, we proposed a converse bound under the constraint of uncoded cache placement which was numerically showed to outperform the other converse bounds under the constraint of uncoded cache placement. However, we need to solve a linear programming including O(HK!) constraints, where for each permutation of [K] there is one constraint. It can be seen that for the proposed converse bound under the constraint of uncoded cache placement for shared-link models, we also have one constraint for each permutation of [K]. Moreover, in shared-link mode, subfiles known by the same number of users are equivalent and thus we can sum all the constraints without loosing the converse bound. In contrast to the shared-link models, due to the topology of combination networks, subfiles known by the same number of users are all equivalent and thus if we sum all the constraints, the converse bound is loosen. However, there is still a symmetry in the networks. We think that we can divide the constraints into groups and sum the constraints in each group without loosing the converse bound. The future work includes solving or simplifying the linear programming. Recently a coded distributed computing scheme was proposed in [START_REF] Li | A fundamental tradeoff between computation and communication in distributed computing[END_REF] which showed that increasing the computation load in the Map stage by a factor of r can create coded multicasting opportunities to reduce the communication load in the Reduce stage by the same factor. This scheme was designed inspired by the caching scheme for Device-to-Device systems proposed in [START_REF] Ji | Fundamental limits of caching in wireless d2d networks[END_REF]. Indeed, the Map-Reduce distributed computing problem is quite similar to the Placement-Delivery caching problem. As stated in the end of [START_REF] Li | A fundamental tradeoff between computation and communication in distributed computing[END_REF],

Extension to Distributed Computing

the results in [START_REF] Li | A fundamental tradeoff between computation and communication in distributed computing[END_REF] only consider a singe-layer structure, where each node multicast the computed data to all the other nodes. However, in practical data center networks, nodes should be connected through multiple switches at different layers. Hence, one of our future direction is to extend our results in cache-aided relay networks (especially combination networks) to topological distributed computing problem.

In addition, we can also think about how to leverage the acyclic index coding bound in the Device-to-Device systems instead of broadcasting systems. We believe it can help us derive the tighter converse bound in the cache-aided Device-to-Device problem and the distributed computing problem.

Appendix A

Appendices

A.1 Proof of Theorem 3

To clarify the notations, we use different symbols for transmitted messages or known messages (nothing above), uniquely decoded ones (hat above) and non-uniquely decoded ones (check above).

Codebook Generation Fix a probability mass function

where each random variable U i is defined on the finite alphabet U i for i ∈ [N ′ ], and functions

for some finite alphabets

For each i ∈ [N ′ ], randomly and independently generate

). For each P ⊆ [N ′ ], let x n P := (x P,1 , . . . , x P,n ) and x P,t (u i :

Randomly and independently assign an index g ∈ [|X | n ] to each collection of sequences (x n P : P ⊆ [N ′ ]) according to a uniform probability mass function over [|X | n ]. The sequences with the same index g are said to form bin B(g). We also indicate g = bin(x n P : P ⊆ [N ′ ]), the index of the bin of x n P . The codebook so generated is revealed to all the decoders.

) and eventually transmits g = bin(x n P : P ⊆ [N ′ ]) to all the decoders.

Decoding Fix K j where D j ⊆ K j and K j ∩ A j = ∅ for each receiver j ∈ [K ′ ]. Decoding proceeds in two steps.

Step 1: Since receiver j ∈ [K ′ ] has messages (m i : i ∈ A j ) as side information, it also knows (u n i : i ∈ A j ) and (x n P : P ⊆ A j ). Upon receiving g = bin(x n P : P ⊆ [N ′ ]), receiver j ∈ [K ′ ] estimates the sequences ( x n P : P ⊆ [N ′ ], P A j ) as the unique

if none or more than one are found, it picks one uniformly at random within B(g).

Step 2: Receiver j ∈ [K ′ ] then uses the found ( x n P : P ⊆ [N ′ ], P A j ), and the side information to decode all messages in K j , but only those in D j uniquely, that is, it finds a unique tuple ( m i : i ∈ D j ) and some tuple ( mi : i ∈ K j \D j ) such that

if none or more than one ( m i : i ∈ D j ) are found, it picks one uniformly at random.

Error Analysis For each decoder j ∈ [K ′ ] and J ⊆ K j where J ∩ D j = ∅, we define the following error events

, where G is the random index of g, (A.6)

For decoder j, the probability of error at decoder j denoted by Pr(E(j)) can be upper bounded by

We now bound each term of the above expression. By LLN, Pr(E 1 ) → 0 as n → ∞. Next consider the second term in (A.8)

where

We then focus on q (u n i :i∈[N ′ ]) to obtain

Pr ( x n P : P ⊆ [N ′ ] and P A j ), f P (u n i : i ∈ P) : P ⊆ A j ) ∈ B(1)

From (A.9) and (A.12b) we can see that

Finally for the third term on the RHS of (A.8), by packing lemma [72, Lemma 3

To avoid heavy notations, in the rest we let

such that s q = c qc q-1 , where s q is defined in (4.1b). From (4.9) (i.e., the fact that (x 0 , . . . , x K ) as defined in (4.7) can be interpreted as a probability mass function), we have

where s q is given in (4.1b). By the Lemma proved in Appendix A.3, for any q ∈ [K -1], s q+1 ≥ s q . Since s K ≤ 0, we have s q ≤ 0 for all q ∈ [K]. From (4.10), we have

By summing (A.15) and (A.16) we get

Next, we substitute (A.17) into (4.16b) and get

Note that when i ∈ {q, q -1} we have w q,i = 0. It remains to prove for each i ∈ [0 : K] we have w q,i ≥ 0.

For any q ∈ [K] and i ∈ [0 : K -1] we have

From Lemma 1 and (A.20), it can be seen that for any q ∈ [K] and i ∈ [0 :

and if i ≥ q -1, w q,i+1 ≥ w q,i . Furthermore, w q,i = 0 for i ∈ {q, q -1}. Hence, for each i ∈ [0 : K],

w q,i ≥ 0. As a result we have

which proves bound given in (4.1a).

A.3 Lemma 1

Lemma 1. Let K, N be positive integers where K > N. For any q ∈ [K -1], s q+1 ≥ s q , where s q is defined in (4.1b).

Proof. Recall that

. Focus on the first term of s q K q+1 -K-min(K,N)

For the second term of s q K q -K-min(K,N)

Taking (A.22b) and (A.23b) into s q , we finally obtain

Hence, it is easy to check that for any q ∈ [K -1], s q+1 ≥ s q .

A. [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF]

Proof. For a u = (u 1 , u 2 , . . . , u min(K,N) ), we say that sub-files/nodes F du i ,W i , for all W i ⊆ [K]\{u 1 , . . . , u i }, are in level i. It is easy to see each node in level i only knows the sub-files F j,W where u i ∈ W. So each node in level i knows neither the sub-files in the same level, nor the sub-files in the higher levels. As a result, in the proposed set there is no sub-set containing a directed cycle.

A.5 Lemma 3 Lemma 3. For decentralized caching system with N files and K users, if each user randomly and uniformly stores MB/N bits of each file, we have

, and zero otherwise. Note that

For user u, there are NB MB choices with identical probability to store MB/N bits and there are NB-1 MB-1 choices that the b th bit of F j is known by u.

. For user u, the probability that he knows simultaneously the b th 1 bit and the b th

Similarly, for user u, the probability that he knows neither the b th

Hence, from (A.27b) and (A. [START_REF] Chen | Fundamental limits of caching: Improved bounds for small buffer users[END_REF])

So by the proprieties of the expected value and the variance of a sum of dependent variables, it follows that

Finally, by Chebyshev's inequality, we have

which coincides with (A.25).

A.6 Proof: 2k+1 k /(2k + 1) is an integer.

If k is a positive integer, we have that

A.7 Discussion of the Group Division of the Interference Elimination Scheme

To get the coefficients [a g,1,j ; . . . ; a g,H,j ] in equation (7.14), C g should be full-rank for each group G g . We should solve the following problem to ensure the feasibility where we introduce an integer k = r -1 such that 2k + 2 = 2r.

Problem 1: Let k be a positive integer. We focus on all the 2k+1 k subsets of [2k + 2] with cardinality k + 1 and 2k + 2 is in each subset (because in (7.13b) and (7.13d) we only focus on the users connected to relay H). We want to divide these subsets into 2k+1 k /(2k + 1) groups such that each group has 2k + 1 subsets. For each group P i , we create a (2k + 2) × (2k + 2) matrix. The first row is all 1. For each subset in this group, we have one row of 0 and 1, where the j th element is 1 if and only if j is in this subset. The condition that the solution exsits for this problem is that each such matrix is full-rank.

In Appendix A.6, we prove that 2k+1 k /(2k + 1) is an integer if k is a positive integer. We provide the following algorithm to construct such groups for Problem 1, which is shown by numerical evaluation to find such groups when k ≤ 12. When k > 12, this numerical simulation might be infeasible due to the complexity.

Algorithm 2 Group division method for Problem 1

(a) T est = 0; randomly choose 2k + 1 subsets in P; create a (2k + 2) × (2k + 2) matrix denoted by C; (the first row of C is all 1 and for each chosen subset, there is one row of 0 and 1, where We prove it by contradiction, i.e., assume that C g is not full-rank. There must exist a sequence of real numbers (a 1 , . . . , a 2k+1 ) such that i∈[2k+1] a i B i = E T , where B i represents the i th row of B. In other words, we have

Since B is full-rank, B T is also full-rank. Hence, there is only one sequence (a 1 , . . . , a 2k+1 ) where

For a solution of Problem 2, in each group, the number of sets containing each number in [2k + 1] is the same. Hence, (a 1 , . . . , a 2k+1 ) = (1/k, . . . , 1/k). However, in this case, i∈[2k+1] a i = 1, not satisfying the last column of C g . Hence, we prove that C g is full-rank.

A.9 Proof of Theorem 29

In this section, we let i be the imaginary unit. Recall that the following equation

has n ′ distinct roots in C (complex field), called (n ′ ) th roots of unity. Write ζ := e 2πi n ′ , then the group of n ′ roots can be expressed as

(A.37)

A circulant n ′ × n ′ matrix is uniquely determined by its first row [c 0 , c 1 , . . . , c n ′ -1 ] and its i th row is obtained by shifting the first row rightwards by i -1 where i ∈ [2 : n ′ ]. The eigenvalues of this matrix are given by

where ω j := e In this thesis we will study the following matrix. Definition 2. A (2k + 1) × (2k + 1) matrix is called a k-matrix if it is circulant, binomial and the first row contains exactly k elements of 1 and k + 1 elements of 0.

Note that when gcd(j, n) = 1, the eigenvalues of a k-matrix is always a sum of k distinct (2k + 1)-th roots of unity. But when gcd(j, n) ≥ 1, the sum may be taken over repeated roots. In this thesis, we want to discuss whether a k-matrix is invertible. We have the following relation:

There exists k distinct (2k + 1)-th roots of unity with sum 0. ⇓ There exists some non-invertible k-matrices.

⇓

There exists k (2k + 1)-th roots of unity with sum 0.

And equivalently

Any sum of k distinct (2k + 1)-th roots of unity is not 0. ⇑ Any k-matrix is invertible.

⇑

Any sum of k (2k + 1)-th roots of unity is not 0.

In the following we prove the following lemmas.

where β ∈ [0 : p e-1 -1]. Recall Q a represents the a-dimension vector space of Q. We define an injective linear map d 1 and a surjective linear map d 0 with the following following sequence of Q-linear maps

. So im(d 1 ) = ker(d 0 ). We conclude that the sequence above is exact.

Suppose that there exists some α 1 , . . . , α k ∈ Z + such that 0 and gcd(k, 2k + 1) = 1.

Proof of Lemma 6. In fact, even if we allow repetitions, any sum of k (2k + 1)-th roots of unity is nonzero. Suppose not, i.e., we have some α 1 , . . . , α t ∈ Z and r 1 , . . . , r t ∈ Z + such that 0 Thus λ 0 , . . . , λ p e-1 -1 ∈ Z and we raise the same contradiction as above.

In the rest of the thesis we consider the case 2k + 1 = pq, where p, q are two distinct primes, and prove Lemma 5 and Lemma 7. The idea is similar to the proves of Lemma 4 and Lemma 6, where we write down generators of Q-linear relations among {1, ζ, . . . , ζ 2k }. In this case there could be two kinds of linear relations: where β p ∈ 0 : 2k+1 p -1 . It contains exactly p distinct (2k + 1)-th roots of unity and has sum 0. Note that when 2k + 1 = pq, there are in total q p-orbits (summands in τ p,βp ) and p q-orbits (summands in τ q,βq ). Conjecture 1. Any subset of µ 2k+1 with sum 0 is a disjoint union of ∪ j O p j ,βp j , where O p j ,βp j is a p j -orbit with p j a prime factor of 2k + 1. (A.51)

So there exists λ p,0 , . . . , λ p,q-1 , λ q,0 , . . . , λ q,p-1 ∈ Q such that

λ q,βq τ q,βq ), (A.52)

i.e., λ p,βp + λ q,βq = λ f (βp,βq)

The choice of an element in d -1 1 (Λ 0 ) is not unique. By subtracting d 2 (λ p,0 ) we may assume that λ p,0 = 0. Since λ f (β p , β q ) ∈ {0, 1} we conclude that λ q,βq ∈ {0, 1}, ∀β q and λ p,βp ∈ {-1, 0, 1}, ∀β p 1.

Easy case: if none of λ p,βp takes value of -1, then A = ( βp,λ p,βp =1 O p,βp ) ∪ ( βq,λ q,βq =1 O q,βq ) is a union of orbits. It is indeed a disjoint union since λ f (βp,βq) 1.

Special case: if there exists some β ′ p ∈ {1, . . . , q -1} such that λ p,βp = -1, then λ q,βq = 1, ∀β q since λ f (β p , β q ) 0. Moreover λ p,βp = -1 since λ f (β p , β q ) 1. By adding d 2 (1) we get an element in

1 (Λ 0 ) with coefficient in {0, 1}. We are back in the easy case then.

Proof of Lemma 5. Note that any p-orbit O p,βp intersects with any q-orbit O q,βq at exactly one element ζ f (βp,βq) , by using Chinese Remainder Theorem [START_REF] Gauss | Disquisitiones arithmeticae (English edition)[END_REF]. Define #(A) as the number of orbits in the union A. Hence a disjoint union of orbits must be a union of orbits with the same length. So either p|#(A) or

Proof of Lemma 7. Now we study the eigenvalues of k-matrices. Given a k-matrix

where the only nonzero terms are c α j = 1, with 0

The eigenvalues are given by

Recall that 2k + 1 = pq. If gcd(j, pq) = 1, then λ j is a sum of k distinct pq-th roots of unity, which is nonzero by the argument above. If gcd(j, pq) = p, then λ j is a sum of k q-th roots of unity, which is nonzero by the previous section and the fact that gcd(k, q) = 1. For the same reason if gcd(j, pq) = q, λ j = 0. Thus all eigenvalues of this arbitrarily chosen k-matrix are nonzero.

A.10 Proof of Theorem 19

A.10.1 Proof of Theorem 19-1)

Achievability. We focus on one set of users J where |J | > t. If each relay is connected to at most t users of J , J at most contains Ht/r users. So if Ht/r < t + 1, there must be one relay connected to t + 1 users of J . So if Ht/r < t + 1, we have V 2 = ∅, i.e., for any set J of t + 1 users, there exists at least one relay connected to all of these users. So the max link-load of DIS is K(1-M/N) H(1+KM/N) . Then we focus on CICS under this case. For each set J of t+1 users, we have

So the total link-load to transmit is |W J | HB ; thus the link-load to transmit all the demanded sub-files of users is also K(1-M/N) H(1+KM/N) . Converse. The converse bound in (6.2) coincides with the above load by taking with x = r.

A.10.2 Proof of Theorem 19-2)

Achievability. By setting r = H -1 in (7.2), we have V 2 = ∅ when t ≤ K -2, i.e., for any set J of t + 1 users, there exists at least one relay connected to all of these users. So similar to the previous case, for each t ∈ [0 : K -2], the max link-load achieved by DIS or CICS is K-t (t+1)H . For t = K, the link-load is 0. For t ∈ [K -2 : K], we use memory-sharing between the points t = K -2 and t = 0.

Converse. The converse bound in (6.2) coincides with the lower convex-hull of the above loads by taking

x = H when M ≤ N(K -2)/K, and x = r when M ≥ N(K -2)/K.

A.10.3 Proof of Theorem 19-3)

Achievability for H < 2r. When t = KM/N = 1, we have V 2 = ∅ so the load from the source to all the relays is (Kt)/(t + 1) = (K -1)/2; due to the symmetry, the load from the source to each relay is the same, and thus the link-load is K-1 2H . When M = 0, the load is K/H. By the memory-sharing between M = 0 and M = KM/N, we can achieve the load in (8.2d).

Converse for H < 2r. The converse bound in (6.2) coincides with the achievable bound by taking x = H when 0 ≤ M ≤ N/K.

Achievability for H = 2r. When 0 ≤ M ≤ N/K, from Theorem 14 and by memory-sharing between M = 0 and M = N/K, the load achieved by IES is

.

Converse for H = 2r. We use the converse bound in Theorem 11. In Appendix A.10.4 we prove that

where z W ≥ 0 is the coefficient of x W in (6.3b). Hence, the bound in (A.55) coincides with the achievable bound when 0 ≤ M ≤ N/K.

A.10.4 Proof of (A.55)

When H = 2r, we compute the converse bound in Theorem 11. We sum all the inequalities as (6.39) for all the sets of relays Q where |Q| = H -1 and for all the permutations p(K Q ). In (6.39), there are

Because of the symmetry, from the sum we obtain

where x 1 = W⊆[K]:|W|=1 x W and v W ≥ 0 represents the coefficient of x W . Then, we focus on (6.5a). It

So in (6.5a), the total coefficient of x ∅ is K(r -1). Then we focus on a set of user W 1 ⊆ [K] where |W 1 | = 2 under the assumption that the two users in W 1 are k 1 and k 2 . In (6.5a), there is only one term with coefficient c W 1 ,H-1 for each W 1 ⊆ [K] where

Hence, we can sum all the inequalities as (6.5a) for all the permutations p([K]) to obtain,

From (A.56) and (A.58), we have

Then, we want to eliminate x ∅ and x 1 with the help of (6.3b) and (6.3c). From (6.3b), we have

From (6.3c), we have

We take (A.60) and (A.61) into (A.59c) to obtain,

where

A.11 Proof of Theorem 20

By taking x = H and comparing the cut-set bound under the constraint of uncoded placement and the achievable bounds in (1.7), we can straightforward obtain Theorem 20-1).

A.11.1 Proof of Theorem 20-2),

It can be seen that for each

Hence, from (7.5),

(A.63)

By the cut-set converse bound in (6.2), R ⋆ c,u is lower bounded by the convex hull of Nt K ,

Hence, the scheme in Section 7.2.3 is order optimal within a factor of 1 + t/r under the constraint of uncoded cache placement. So we can sequentially prove Theorem 20-2) and 3).

A.11.2 Proof of Theorem 20-5)

To encode each message W J where J ∈ V 1 , the total link-load of IES is |W J |/B. To encode each message W J where J ∈ V 2 , we transmit one linear combination including W J and other 2r -2 messages to 2r relays. So the total link-load to transmit W J is 2r/(2r -1). Compared to The converse bound in (6.2) with

x = H when 0 ≤ M ≤ N/K, IES is order optimal within factor 2r 2r-1 ≤ 4 3 under the constraint of uncoded cache placement.

A.12 Proof of Theorem 18

Converse From the cut-set converse bound in (1.9) with α = 1 and l = 1, we have R ⋆ c ≥ (1 -M/N)/r. Between M ∈ (K-H+r-1)N K , N , the converse bound is a straight line. When M = (K-H+r-1)N K , we have

When M = N, we have R ⋆ c ≥ 0. Achievability It is obvious that when M = N, we can achieve R = 0. So it remains to prove that we can achieve R = H-r+1 rK when M = (K-H+r-1)N K . The memory-sharing of these two points can coincide with the converse bound.

We focus on the coded caching gain g = K 1 . We consider two cases, H = r + 1 and H > r + 1.

Hence, we have in this case K 2 + 1 = K 1 , which means that we can use the scheme in Section 7.4.1 to achieve the maximum coded caching gain. In this case, K = H r = r+1 r = r + 1 and K 1 = H-1 r-1 = r. In addition, we have

Hence, the needed memory size is

The achieved max link-load is

In addition, we have

Hence, in this case we have

So we should use the asymmetric coded placement scheme in Section 7.4.2. Since y g-1,m = g -1 -K 1 + H-m r-1 , we have when m = Hr + 1, y g-1,m = 0. In addition, when m = Hr + 1, for any a ∈ [1 : Hm], we have

In addition, with

From (A.70c) and (A.69b), we can see that

. Furthermore, we have

Hence, the needed memory size is

The achieved max link-load is

In addition, in this case,

Hence, in this case we have

In conclusion, for both cases we prove Theorem 18.

In addition, for both cases, we have n b = k 1,b +k 2,b and thus we need not to use MDS precoding. Hence, when g = K 1 , the proposed cache placement is uncoded.

A.13 Proof of Theorem 22

We consider two cases, where g ∈ [2 : (g-1)|Z g-1 |+g|Zg| . It can be seen that M b < M ZY = (g-1)N

, which is always true because

we should use the asymmetric coded placement scheme in Section 7.4.2. In this case, from a similar derivation as (A.75d), we can see that From the construction of the asymmetric coded placement scheme in Section 7.4.2, it can be seen that when g > K 2 + 1, there exists at least one m ∈ [2 : Hr + 1] such that N m > 0. In addition, m=1 mN m = |Z g-1 |. In the following we prove the statement that for m ∈ [Hr + 1], we have

g-1

≤

m and the equality holds only when m = 1. With this statement, we can obtain (A.76) and thus we prove Theorem 22. To prove this statement, it is equivalent to prove K -H-m r -mK 1 ≤ 0. In addition,

where the equality holds only when m = 1.

A.

Hence, we can see that

and it remains to compute |C h,Y |. In (7.67), we compute that

m where y t,m is defined in (7.47f). In addition, it can be computed that

where

and there exist some relay(s)

In addition, we define that where |V| = a, we have

Hence, from (A.84), we have

(A.85)

In the end, from (A.85), (A.83), (A.80) and (A.79), we can prove (7.47d).

A.15 Proof of (9.3c) and (9.3f)

We focus on the corner points in Groups 2 and 3. For each coded caching gain g ∈ [2 : K 1 ], it is straightforward to obtain the max link-load from the server to relays is K max 1-(rM relay +M user )/N,0 Hg

. So it remains to compute the max link-load from relays to users. We consider two cases, when g ∈ [2 : K 2 + 1] and

Hence, the number of bits transmitted from relay h to each user k ∈ U h is given by the second term of the RHS of (9.3c) and thus we can prove that the max link-load from relays to users is given in (9.3c).

Similarly, when g ∈ [K 2 + 2, K 1 ], in Steps 1 and 3 of delivery phase, the number of bits transmitted from relay relay in

. Hence, the number of bits transmitted from relay h to each user k ∈ U h is given by the second term of the RHS of (9.3f) and thus we can prove that the max link-load from relays to users is given in (9.3f).

A.16 Proof of Theorem 25

If H = r + 1, we focus on Group 2 with g = K 2 + 1 = K 1 . So we have max{y ∈

It is computed in Appendix A.12 that in this case k

.

If H > r + 1, we focus on Group 3 with g = K 1 . So we have m

.

So we focus on the corner point

, and the achieved max link-load from the server to relays is

In addition, for each memory pair of 0, (K-H+r-1)N K , (N/r, 0) and (0, N), we can also achieve the con-

. Hence, if a memory pair can be obtained by the memory-sharing of the four memory pairs, 0, (K-H+r-1)N

, (N/r, 0) and (0, N), we can achieve the converse bound R s→r⋆ ≥

(b) we transmit RLC(c ′ , C ′ ) to relay h and relay h then forwards RLC(c ′ , C ′ ) to users in U h , where

Algorithm 4 Separate Relay Decoding delivery Scheme (SRDS)

(R e represents the number of bits to be borrowed.)