Coding Schemes and Converse Bounds for Secure, Multi-Access, and Multi-Antenna Coded Caching Problems

Abstract

With rapid advancements in technology, there is an increase in the adoption of data-hungry applications, especially entertainment services like on-demand music and video streaming and download. The high temporal variability of these on-demand services leads to internet traffic congestion during peak hours and often leaves the network resources under-utilized during off-peak hours. Coded caching, introduced in “Fundamental limits of caching” (IEEE Transactions on Information Theory, 2014) by M. A. Maddah-Ali and U. Niesen, is a technique to tackle this temporal variability by employing and exploiting the caches at the user end. In the seminal work, Maddah Ali and Niesen considered a single-server broadcast network, where the server with a library of files is connected to a set of cache-aided users through an error-free shared link. The coded caching scheme operates in two phases: a placement phase and a delivery phase. In the placement phase (during off-peak hours), the server fills the caches at the user end with a fraction of the file library. In the delivery phase, each user requests a single file from the server. Once all the requests are known, the server makes coded transmissions so that users can decode their requested files using the accessible cache contents and the coded transmissions. The coded caching problem aims to jointly design the placement and delivery phases so that the rate (the transmission size) in the delivery phase is minimized. In addition to the dedicated cache setting considered by Maddah-Ali and Niesen, we address the coded caching problem in multi-access coded caching (MACC) networks, where each user accesses more than one cache.

In the first part, we discuss the notions of demand-privacy and secure delivery in the coded caching problem. We present an optimal demand-private coded caching scheme, where each user in the network is completely uncertain about the demanded file indices of the remaining users. Then, we consider the cyclic wrap-around MACC network model introduced in “Coded caching with multi-level popularity and access” (IEEE Transactions on Information Theory, 2017) by Hachem \textit{et al.} In this network, a user can access a set of neighbouring caches with a possible cyclic wrap-around. We design coded caching schemes for the cyclic wrap-around MACC problem incorporating the demand-privacy constraint. Further, we design a coding scheme and derive a converse bound by imposing a security constraint on the MACC problem. Additionally, we present certain optimality guarantees for the proposed secure MACC scheme.

The second part of our work focuses on designing coded caching schemes with coded placement for the MACC problem. For the cyclic wrap-around MACC problem, we present a coded caching scheme with coded placement for a specific memory regime. Further, we derive an improved lower bound for the problem and show the optimality of the proposed scheme. We also show that the derived lower bound is tighter than a cut-set-based lower bound. Additionally, we derive a lower bound for the cyclic wrap-around MACC problem by incorporating a secrecy constraint. Then, we consider another MACC network model, the combinatorial MACC network model, introduced in “Maddah-Ali Niesen scheme for multi-access coded caching” (in Proc. of IEEE ITW, 2021) by Muralidhar \textit{et al.} Unlike the cyclic wrap-around MACC setting, the number of users is more than the number of caches in the combinatorial MACC network. Muralidhar \textit{et al.} presented a coding scheme, which was later shown to be optimal under uncoded cache placement. By employing coding among the cached content in the placement phase, we achieve a better rate-memory trade-off than the optimal scheme under uncoded placement. For the combinatorial MACC setting, we present two achievable schemes with maximum distance separable (MDS) code-based placement. Further, we characterize optimality guarantees for the proposed schemes by deriving converse bounds.

In the final part, we aim to design coded caching schemes from new generalizations of the Placement Delivery Array (PDA). PDAs, introduced in ``On the placement delivery array design for centralized coded caching scheme'' by Yan \textit{et al.}, are originally used to construct coded caching scheme for the dedicated cache setting with reduced subpacketization level (subpacketization level of a coded caching scheme is defined as the number of subfiles into which a file is divided during the placement and delivery phases). However, we propose PDA-like structures for obtaining coded caching schemes in three different settings. First, we consider a multiple-input single-output (MISO) broadcast channel, where the central server is equipped with multiple transmit antennas, and each user has a single receive antenna. We introduce a combinatorial structure named ‘Extended Placement Delivery Array (EPDA)’, which can describe both the placement and the delivery phases of a multi-antenna coded caching scheme. Also, we see a few constructions of the EPDAs for different parameter settings. Further, we present an application of EPDAs to obtain caching and delivery arrays, which, in turn, describe coded caching schemes for a two-dimensional MACC network. Finally, we consider a coded caching network model with two sets of caches- a set of helper caches and a set of private caches. In this setting, a helper cache can serve more than one user. However, one user can access only one helper cache. Additionally, each user is endowed with a private cache. We design a combinatorial structure named `Shared and Private Placement Delivery Array (SP-PDA)' for coded caching schemes for the considered network model. We also propose a construction of SP-PDAs using two PDAs. Interestingly, the permutations of the columns of the two chosen PDAs result in SP-PDAs with different performances. Finally, we characterize the conditions for selecting the best column permutations for the two chosen PDAs.