Combinatorial Multi-Access Coded Caching: Improved Rate-Memory Trade-off with
Coded Placement

With smartphones, mobile applications and expanded connectivity, people are consuming more video content than ever. This increase in mobile video consumption is taking a toll on the internet, which has seen data traffic increase many-fold in a few years. However, the high temporal variability of on-demand video services leaves the network underutilized during off-peak hours. Utilizing the channel resources by employing low-cost cache memory to store contents at the user end during off-peak times is an effective way to ease the network traffic congestion in peak hours. In the conventional caching scheme, the users’ demands are met by filling the caches during the placement phase (in off-peak hours without knowing the user demands) and by transmitting the remaining requested file contents in the uncoded form during the delivery phase (in the peak hours after knowing the user demands). In coded caching, introduced in [1], it was shown that by employing coding in the delivery phase among the requested contents, it is possible to bring down the network load further compared to the conventional caching scheme. In [1], Maddah-Ali and Niesen considered a single server broadcast network, where the server is connected to $K$ users through an error-free shared link. The server has a library of $N$ files, and the user caches have a capacity of $M$ files, where $M\leq N$ (since each user is equipped with a dedicated cache memory, we refer to this network as the dedicated cache network). During the placement phase, the server stores file contents (equivalent to $M$ files) in the caches without knowing the user demands. In the delivery phase, each user requests a single file from the server. In the delivery phase, the server makes coded transmissions so that the users can decode their demanded files by making use of the cache contents and the coded transmissions. The goal of the coded caching problem is to jointly design the placement and the delivery phases such that the rate (the size of transmission) in the delivery phase is minimized. The scheme in [1] achieved a rate $K(1-M/N)/(1+KM/N)$, which is later shown to be the optimal rate under uncoded placement if $N\geq K$ [2, 3]. In [4], it was shown that by employing coding among the contents stored in the placement phase in addition to the coding in the delivery phase, a better rate-memory trade-off could be achieved. By using coded placement, further improvement in the rate was obtained by the schemes in [5, 6, 7, 8, 9]. The works in [10, 11, 12, 13, 14], came up with different converse bounds for the optimal rate-memory trade-off of the coded caching scheme for the dedicated cache network.

Motivated by different practical scenarios, coded caching was extended to various network models, including multi-access networks [15], shared cache networks [16] etc. In the multi-access coded caching (MACC) scheme proposed in [15], the number of users, $K$ was kept to be the same as the number of caches. Further, each user was allowed to access $r<K$ neighbouring caches in a cyclic wrap-around fashion. The coded caching scheme under the cyclic-wrap model was studied in [17, 18, 19, 20, 21, 22]. Those works proposed different achievable schemes, all restricted to uncoded cache placement. In [23], the authors proposed a coded caching scheme with an MDS code-based coded placement technique and achieved a better rate-memory trade-off in the low memory regime compared to the schemes with uncoded placement. Further, by deriving an information-theoretic converse, the scheme in [23] was shown to be optimal in [24]. The MACC problem (in the cyclic wrap-around network) was studied by incorporating security and privacy constraints in [25, 26]. The first work that considered a multi-access network with more users than the caches is [27]. The authors established a connection between the MACC problem and design theory, and obtained classes of MACC schemes from resolvable designs. The works in [28, 29] also relied on design theory to obtain MACC schemes.

In this paper, we consider the combinatorial multi-access network model introduced in [30], which consists of $C$ caches and $K=\binom{C}{r}$ users, where $r$ is the number of caches accessed by a user. The combinatorial MACC scheme presented in [30] achieves the rate $R=\binom{C}{t+r}/\binom{C}{t}$ at cache memory $M=Nt/C$, where $t\in\{1,2,\dots,C-r+1\}$. Here onwards, we refer to the scheme in [30] as the MKR scheme. The optimality of the MKR scheme under uncoded placement was shown in [31]. In addition to that, in [31], the system model in [30] was generalized to a setting where more than one user can access the same set of $r$ caches. In [32], the authors addressed the combinatorial MACC problem with privacy and security constraints.

Similar network topologies were considered in various cache aided settings, including two-hop networks [33, 34] and multi-server networks [35]. The two-hop network considered in [33] and [34] consists of a server and $K$ users connected via a set of $h$ cache-aided relay nodes. Each user is connected to a distinct set of $\rho$ relay nodes, where $\rho<h$, and thus the number of user is $K=\binom{h}{\rho}$. Those users also have dedicated caches. The scheme in [33] followed an uncoded random placement strategy, whereas the scheme in [34] relied on MDS-coded placement. The main difference between the combinatorial MACC scheme and the coded caching scheme for the two-hop network is in the delivery phase. In the combinatorial MACC setting, the server communicates directly to the users over an error-free broadcast link. However, in two-hop networks, the server responds to the users’ requests by transmitting signals to each of the relay nodes. Then, each relay node utilizes its received signal and its cached contents to transmit unicast signals to each of its connected end users. In [35], a network model with $P$ servers and $K$ cache-aided users is considered. Each user can get connected to a random set of $\rho$ servers, where $\rho\leq P$. In order to ensure that any $\rho$ servers collectively store the entire file library, the file contents are stored in the servers after an MDS encoding.

The system model as shown in Fig. 1 consists of a central server with a library of $N$ independent files, $W_{[1:N]}\triangleq\{W_{1},W_{2},\dots,W_{N}\}$, each of size 1 unit (we assume that 1 unit of a file is constituted by $f$ symbols from the finite field of size $q$)¹¹1We assume that $q$ is such that all MDS codes considered in this work exist over $\mathbb{F}_{q}$.. There are $C$ caches, each with capacity $M$ units ($0\leq M\leq N$). i.e., each cache can store contents equivalent to $M$ files. There are $K$ users in the system, and each of them can access $r$ out of the $C$ caches, where $r<C$. We assume that there exists a user corresponding to any choice of $r$ caches from the total $C$ caches. Thus the number of users in the system is $K=\binom{C}{r}$. Further, each user is denoted with a set $\mathcal{U}$, where $\mathcal{U}\subset[C]$ such that $|\mathcal{U}|=r$. That is, a user is indexed with the set of caches that it accesses. In other words, user $\mathcal{U}$ has access to all the caches in the set $\mathcal{U}$. A system under the aforementioned setting is called the $(C,r,M,N)$ combinatorial multi-access network. The coded caching scheme under this model was introduced in [30].

The $(C,r,M,N)$ combinatorial MACC scheme works in two phases, the placement phase and the delivery phase. In the placement phase, the server populates the caches with the file contents. The cache placement is done without knowing the demands of the users. The placement can be either coded or uncoded. By uncoded placement, we mean that files are split into subfiles and kept in the caches as such, while coded placement means that coded combinations of the subfiles are allowed to be kept in the caches. The number of subfiles into which a file is split is termed the subpacketization number. The contents stored in cache $c$, $c\in[C]$, is denoted as $Z_{c}$. In the delivery phase, user $\mathcal{U}$ requests file $W_{d_{\mathcal{U}}}$ from the server, where $d_{\mathcal{U}}\in[N]$, and the demand vector $\mathbf{d}=(d_{\mathcal{U}}:\mathcal{U}\subset[C],|\mathcal{U}|=r)$. In the demand vector, we arrange the users (subsets of size $r$) in the lexicographic order. Corresponding to the demand vector, the server makes a transmission $X$ of size $R$ units. We assume that the broadcast channel from the server to the users is error-free. The non-negative real number $R$ is said to be the rate of transmission. Finally, user $\mathcal{U}$ should be able to decode $W_{d_{\mathcal{U}}}$ using transmission $X$ and the accessible cache contents $Z_{c},c\in\mathcal{U}$. That is, for $\mathcal{U}\subset[C]$ such that $|\mathcal{U}|=r$, we have

where $Z_{\mathcal{U}}=\{Z_{c}:c\in\mathcal{U}\}$.

The coded caching problem aims to design the placement and the delivery phases jointly so that the rate is minimized. In this work, we present two achievability results and a lower bound on $R^{*}(M)$.

In this section, we discuss the preliminaries required for describing the coding scheme as well as the converse bound.

In this section, we present two achievability results for the $(C,r,M,N)$ combinatorial MACC scheme. Further, we derive an information-theoretic lower bound on the optimal rate-memory trade-off, $R^{*}(M)$.

Proof of Theorem 1 is given in Section V-A. $\blacksquare$

In Section V-A, for the $(C,r,M,N)$ combinatorial MACC problem, we explicitly present a coding scheme making use of coded placement. As we have seen in the example in Section III-D, coding in the placement phase helps to avoid redundancy in the cached contents (accessed by a user) in the MKR scheme. The example shows that by storing fewer coded subfiles in the placement phase, a user can decode the same subfiles as the corresponding user in the MKR scheme (by corresponding user, we mean that the user accessing the same set of caches) gets in the uncoded form. In other words, it is possible to achieve the same rate as the MKR scheme by using a lesser value of cache memory by employing coding in the placement. For a cache memory value $M$ as defined in (6) corresponds to a $t\in[C-r]$, we can modify the rate expression as (proof is given in Appendix B)

Also, the parameter $t=C-r+1$ corresponds to $M=N/r$ (proof is provided in Appendix C) and rate, $R(M=N/r)=0$. Therefore, the rate expression (7) is valid for every $t\in[C-r+1]$. For a general $0\leq M\leq N/r$, a lower convex envelope of these points is achievable via memory sharing technique. In the rate expression, the term $(1-rM/N)$ shows that a user can access or decode $rM/N$ fraction of every file from the caches that it accesses and requires only the remaining portion of the required file from the delivery phase. Further, the denominator $\binom{t+r}{r}$ is the number of users simultaneously served by a coded transmission in the delivery phase.

The parameter $t$ in the MKR scheme represents the number of times the entire server library is duplicated among the caches. In the MKR scheme, user $\mathcal{U}$ gets $|\mathcal{T}\cap\mathcal{U}|$ copies of a subfile $W_{n,\mathcal{T}}$. Therefore, a user gets a different number of copies of different subfiles depending upon the cardinality of the intersection between the user index set and the subfile index set. Our objective is to design a coded placement phase such that from the accessible cache contents, a user should be able to decode the subfiles that the corresponding user in the MKR scheme gets in the uncoded form. The main challenge of designing such a placement phase is that a user should be able to decode all the subfiles with a non-zero intersection between the user index set and the subfile index set. To tackle this challenge, we employ a two-level MDS encoding. First, we encode the subfiles with an MDS code generator matrix. Then, in each round of the placement phase, a few selected coded subfiles are encoded again with another MDS code generator matrix. This two-level encoding technique is different from the MDS code-based coded placement strategies followed in the schemes in [34, 35] for two-hop networks and multi-server networks, respectively. In both cases, the entire file library was encoded with an MDS code. In our case, user $\mathcal{U}$, $\mathcal{U}\subseteq[C],|\mathcal{U}|=r$ should be able to decode all the subfiles $W_{n,\mathcal{T}}$ such that $\mathcal{T}\cap\mathcal{U}\neq\phi$, from the accessible cache contents. To ensure that, in general, a single-level encoding is not sufficient. Our first-level MDS encoding duplicates the file library, whereas our second-level MDS encoding ensures that the users can decode the required subfiles from the cache contents.

Further, note that the parameter $\tilde{r}=\min(r,t)$ is the maximum value of $|\mathcal{T}\cap\mathcal{U}|$ for any $\mathcal{T}$ and $\mathcal{U}$. In other words, $\tilde{r}$ is the maximum number of copies of a single subfile that is accessed by a user in the MKR scheme. Therefore, our placement phase depends upon $\tilde{r}$. In fact, the placement phase consists of $\tilde{r}$ rounds. i.e, Round 0, Round 1, $\dots$, Round $\tilde{r}-1$. The transmissions in our delivery phase is the same as that of the MKR scheme. Thus the coded placement phase should enable user $\mathcal{U}$ to decode all the subfiles $W_{n,\mathcal{T}}$ with $\mathcal{T}\cap\mathcal{U}\neq\phi$ from the content stored in the accessible caches. Let us denote the content stored in cache $c$ in Round $b$ as $Z_{c}^{b}$, where $c\in[C]$ and $b\in\{0\}\cup[\tilde{r}-1]$. Then, we design our placement phase such that user $\mathcal{U}$ be able to decode a subfile $W_{n,\mathcal{T}}$ with $|\mathcal{T}\cap\mathcal{U}|=\tilde{r}-\beta$ using $Z_{c}^{0},Z_{c}^{1},\dots,Z_{c}^{\beta}$ for every $c\in\mathcal{U}$. For instance, using $Z_{c}^{0}$ alone (for every $c\in\mathcal{U}$), the user can decode $W_{n,\mathcal{T}}$ if $|\mathcal{T}\cap\mathcal{U}|=\tilde{r}$. In further decoding, the user also uses the already decoded subfiles. Thus the cache content decoding happens sequentially. First, the user decodes the subfiles $W_{n,\mathcal{T}}$ with $|\mathcal{T}\cap\mathcal{U}|=\tilde{r}$, then the subfiles $W_{n,\mathcal{T}}$ with $|\mathcal{T}\cap\mathcal{U}|=\tilde{r}-1$ and so on. Finally, the user can decode the subfiles $W_{n,\mathcal{T}}$ with $|\mathcal{T}\cap\mathcal{U}|=1$.

When $t=1$, there is no duplication in cached contents, and thus the contents accessed by a user from different caches are distinct. Therefore, performance improvement by coding is available when $t>1$. Further, the placement phase of the MKR scheme is independent of $r$, whereas our scheme takes $r$ into consideration during the cache placement. Also, our scheme needs to divide each file into $\tilde{r}!\binom{C}{t}$, whereas the MKR scheme needs a lesser subpacketization of $\binom{C}{t}$.

The MKR scheme achieves the rate $\binom{C}{t+r}/\binom{C}{t}$ at $M=Nt/C$, which is optimal under uncoded placement. Since $\sum\limits_{i=1}^{\tilde{r}-1}\frac{\tilde{r}-i}{r}\binom{r}{\tilde{r}-i+1}\binom{C-r}{t-\tilde{r}+i-1}$ is always positive for $t>1$, we achieve the same rate $\binom{C}{t+r}/\binom{C}{t}$ at $M<Nt/C$. This advantage is enabled with the help of coding in the placement phase. If $t=1$, we have cache memory $M=N/C$. For $0\leq M\leq N/C$, the scheme in Theorem 1 has the same rate-memory trade-off as the MKR scheme. For every $M>N/C$, our proposed scheme performs strictly better than the MKR scheme in terms of the rate achieved.

Next, we present a combinatorial MACC scheme that performs better than the MKR scheme in the lower memory regime. In the following theorem, we present an achievability result for $M\leq(N-\binom{C-1}{r})/C$.

Proof of Theorem 2 is given in Section V-B. $\blacksquare$

When the number of files $N$ is such that $\binom{C-1}{r}<N\leq\binom{C}{r}$, the rate $R(M)=N-CM$ is strictly less than the rate of the MKR scheme for $0\leq M\leq(N-\binom{C-1}{r})/C$.

Now, we present a lower bound on the optimal rate-memory trade-off for the $(C,r,M,N)$ combinatorial MACC scheme.

Proof of Theorem 3 is given in Section V-C. $\blacksquare$

The lower bound in Theorem 3 has two parameters: $s$, which is related to the number of caches, and $\ell$, which is associated with the number of transmissions. To obtain this lower bound, we consider $s\in[r:C]$ caches and $\binom{s}{r}$ users who access caches only from those $s$ caches. From $\lceil{N}/{\binom{s}{r}}\rceil$ number of transmissions, all the $N$ files can be decoded at the $\binom{s}{r}$ users’ end by appropriately choosing the demand vectors. Further, we split the total $\lceil{N}/{\binom{s}{r}}\rceil$ transmissions into $\ell$ transmissions and the remaining $\lceil{N}/{\binom{s}{r}}\rceil-\ell$ transmissions. Then, we bound the uncertainty in those two cases separately. This bounding technique is similar to the approach used in [10] and [24], where lower bounds were derived for the dedicated cache scheme and the MACC scheme with cyclic wrap-around, respectively.

In Fig. 3, we plot the rate-memory trade-off in Theorem 1 along with that of the MKR scheme. For $0\leq M\leq 7$ ($t=1$ gives $M=7$), both the schemes have the same rate-memory trade-off. However, for $M>7$, our scheme has a strictly lower rate compared to the MKR scheme. It is worth noting that, in order to achieve $R(M)=0$, it is sufficient to have $M=N/r$, whereas, in the optimal scheme with uncoded placement, $M=N(C-r+1)/C$ is required to achieve $R(M)=0$. In Fig. 4, we compare the performance of the $(5,3,M,10)$ combinatorial MACC scheme under uncoded and coded placements. The rate-memory trade-off of the optimal scheme under uncoded placement (MKR scheme) is denoted as $R^{*}_{uncoded}(M)$, whereas $R_{coded}(M)$ is obtained from Theorem 1 and Theorem 2, where the placement is coded. For the $(4,2,M,6)$ combinatorial MACC scheme, the improvement in rate using coded placement can be observed from Fig. 5. Also, notice that the rate-memory trade-off in Theorem 1, Theorem 2 are optimal when $M\geq 2.5$, and $M\leq 0.75$, respectively.

Using the lower bound in Theorem 3, we show the following optimality results. First, we prove that the rate-memory trade-off in Theorem 1 is optimal at a higher memory regime.

Proof of Theorem 4 is given in Section V-D. $\blacksquare$

The optimality is shown towards the higher memory regime. When $\frac{\binom{C}{r}-1}{r\binom{C}{r}}\leq\frac{M}{N}\leq\frac{1}{r}$, the users would be requiring only a single subfile from the delivery phase and the server can meet that by a single coded transmission. Also, it is worth noting that in our proposed scheme (Scheme 1), the delivery phase is optimal under the placement that we followed. Because the users in our proposed scheme and the users in the MKR scheme obtain the same subfiles from the respective placement phases. Thus, if we could design a better delivery phase, the same would apply to the MKR scheme. However, that is impossible since the MKR scheme is optimal for the placement employed. As the dedicated coded caching scheme (introduced in [1]), the optimal rate-memory trade-off of the $(C,r,M,N)$ combinatorial MACC scheme is also open.

In the lower memory regime, when $M<N/C$, the rate-memory trade-off in Theorem 1 is clearly not optimal, since the scheme in Theorem 2 achieves a better rate. Now, we show that the rate-memory trade-off in Theorem 2 is optimal if the number of users is not more than the number of files.

Proof of Theorem 5 is given in Section V-E. $\blacksquare$

In the proposed scheme, $N-\binom{C-1}{r}$ coded subfiles are kept in each cache (for $M=(N-\binom{C-1}{r})/C$) in the placement phase. However, the delivery phase is uncoded. That is, the server transmits uncoded subfiles in the delivery phase. A user receives $C-r$ subfiles (of the demanded file) directly, and the remaining $r$ subfiles need to be decoded from the $r$ accessible caches. A user requires $\binom{C-1}{r}$ subfiles from the delivery phase to decode a subfile of the demanded file from an accessible cache. That is, using $N-\binom{C-1}{r}$ coded subfiles in a cache and $\binom{C-1}{r}$ uncoded subfiles from the delivery phase, a user can decode $N$ subfiles, out of which only one is required for the user. Therefore, the ratio between the number of coded subfiles stored in a cache and the number of subfiles required to decode a subfile from a cache increases with $N$. Thus the optimality of the scheme is limited to the case where $N\leq\binom{C}{r}$.

Next, we show that the rate-memory trade-off of Scheme 1 is within a constant multiplicative factor from the optimal rate-memory trade-off, when $r=2$ and the number of files with the server is not less than the number of users in the system.

Proof of Theorem 6 is given in Section V-F. $\blacksquare$

In order to prove the optimality gap result, we divide the entire memory regime into three regions. For a lower memory regime (for $0\leq M\leq 2N/C$), we approximate the rate to $R(M=0)=\binom{C}{2}$. In the second regime, where $2N/C\leq M\leq 0.1N$, we approximate the rate to $(N/M)^{2}$ (note that, $R(M)\leq(N/M)^{2}$). Finally, for $M\geq 0.1N$, we approximate the rate $R(M)\approx(N/M)^{2}(1-2M/N)$. To obtain the optimality gap result, we compute the ratio of these approximate rate-memory trade-off to the lower bound on $R^{*}(M)$ in Theorem 3. Due to these approximations and the analytical bounding techniques used, the optimality gap of 21 in Theorem 6 is loose. From numerical simulations, for the $(C,r=2,M,N)$ combinatorial MACC scheme, we have

Also, the numerical simulations suggested that the multiplicative gap between the rate-memory trade-off given by Scheme 1 and the lower bound on $R^{*}(M)$ given in Theorem 3 increases as $r$ increases. However, providing an analytical result on the optimality gap becomes increasingly hard with increasing $r$ because of the optimization problem in the lower bound expression (8).