In this paper, we consider the (N,K,L) multi-access caching network where K users and K caches are connected to a server with N files, each of size F bits, through a shared error-free broadcast channel. Each user has access to L nearby caches, each of size MF bits, in a cyclic wrap-around manner. Even after several previous attempts, the exact characterization of the optimal rate memory tradeoff is still an open problem except in the case where L = K − 1 and L = 1 with large cache $M \in \left[ {\frac{N}{L} \cdot \frac{{K - 1}}{K},\frac{N}{L}} \right]$. This paper determines the optimal rate memory tradeoff for the cache network with L = K − 2 and $M \in \left[ {\frac{N}{{K - 2}} \cdot \frac{{K - 1}}{K},\frac{N}{{K - 2}}} \right]$. This is done by proposing a new caching scheme that operates at the memory rate pair $\left( {\frac{N}{{K - 2}},\frac{{K - 1}}{K},\frac{1}{K}} \right)$ and deriving a set of lower bounds to demonstrate the optimality of the scheme.

The idea of coded caching for content distribution networks was introduced by Maddah-Ali and Niesen, who considered the canonical$(N, K)$cache network in which a server with$N$files satisfies the demands of$K$users (each equipped with an independent cache of size$M$). The optimal rate memory tradeoff for demands where all files are requested by at least one user has been characterized only for small caches where$M\leq \frac {1}{K}$and large caches where$M\geq N-\frac {N}{K}$. For the case$N \leq K \leq 2N-1$, we derive new lower bounds for small and large caches and propose a new coded caching scheme for large caches. Along with the scheme proposed by Gómez-Vilardebó, this leads to a characterization of the optimal rate memory tradeoff for$M\leq \frac {1}{K}+\frac {1}{K(N-1)}$and$M\geq N-\frac {N}{K}-\frac {N-1}{K(K-1)}$. For the case$2N-1\leq K$, we derive a new lower bound for large caches, which proves the optimality of the scheme proposed by Yu et al. and leads to a characterization of the optimal rate memory tradeoff for$M\geq N-\frac {2N}{K}$. We also derive a new lower bound for small caches, which improves upon previously known lower bounds.

The problem of coded caching was introduced by Maddah-Ali and Niesen and has been extensively studied in recent years. The problem is fundamentally a multi-objective optimization problem where the rates achieved for each demand type is of interest and Pareto optimality is a natural framework. Under the constraint that the placement phase is uncoded, Yu et al. introduced the YMA scheme which was shown to be universal for all demand types. Vijith et al. showed that there are no universal schemes when coded placement is permitted and introduced the problem of finding Pareto optimal schemes. In this paper we study the possibility of finding schemes that dominate the YMA scheme and demonstrate, rather surprisingly, that they continue to operate at the Pareto optimal frontier of coded caching for (N, K) cache networks when$K$≤ 3. We introduce new lower bounds which partially characterize the tradeoffs between different demand types.

Maddah-Ali and Niesen, in a seminal paper, introduced the notion of coded caching. The exact nature of the fundamental limits in this context has remained elusive even as several approximate characterizations have been found. A new optimal scheme for the (3, 3) cache network, operating at the memory rate pair (5/3, 1/2) for the demand where all the users request for distinct files, was introduced recently to partially address this issue. In this paper, an extension of this scheme to the general (K, K) cache network, operating at the memory rate pair ((K2-K -1)/K, 1/(K -1), is proposed. A new lower bound is also derived which demonstrates the optimality of the proposed scheme for the demand where all the users request for distinct files.

Maddah-Ali and Niesen, in a seminal work, initiated the study of rate memory tradeoff for a canonical cache network which operates via a placement phase and a delivery phase. While considering the case of placement phase being uncoded, Yu et al. proved the surprising result of the existence of a universal code, a code which is simultaneously optimal for all demand types. In this paper, we prove that universal codes do not exist when coding is permitted in the placement phase. As part of our proof, we introduce new kinds of lower bounds. In these lower bounds, instead of considering one demand type at a time, we consider several demand types simultaneously. These bounds give us better insight into how the performance for one demand type affects the performance for the other demand types. The non-existence of a universal scheme motivates us to introduce the notion of Pareto optimal schemes, and we prove that Chen's scheme is Pareto optimal.