Order-Optimal Rate of Caching and Coded Multicasting with Random Demands

Abstract

We consider the canonical {\em shared link network} formed by a source node, hosting a library of $m$ information messages (files), connected via a noiseless common link to $n$ destination nodes (users), each with a cache of size M files. Users request files at random and independently, according to a given a-priori demand distribution $\qv$. A coding scheme for this network consists of a caching placement (i.e., a mapping of the library files into the user caches) and delivery scheme (i.e., a mapping for the library files and user demands into a common multicast codeword) such that, after the codeword transmission, all users can retrieve their requested file. The rate of the scheme is defined as the {\em average} codeword length normalized with respect to the length of one file, where expectation is taken over the random user demands. For the same shared link network, in the case of deterministic demands, the optimal min-max rate has been characterized within a uniform bound, independent of the network parameters. In particular, fractional caching (i.e., storing file segments) and using linear network coding has been shown to provide a min-max rate reduction proportional to 1/M with respect to standard schemes such as unicasting or "naive" uncoded multicasting. The case of random demands was previously considered by applying the same order-optimal min-max scheme separately within groups of files requested with similar probability. However, no order-optimal guarantee was provided for random demands under the average rate performance criterion. In this paper, we consider the random demand setting and provide general achievability and converse results. In particular, we consider a family of schemes that combine random fractional caching according to a probability distribution $\pv$ that depends on the demand distribution $\qv$, with a linear coded delivery scheme based on ...

Submitted to IEEE Transaction on Information Theory

References in corpus (11)

• Topological Interference Management through Index Coding
• Fundamental Limits of Caching with Secure Delivery
• On the Capacity Region for Index Coding
• Content Caching and Delivery over Heterogeneous Wireless Networks
• Index coding via linear programming
• FemtoCaching: Wireless Video Content Delivery through Distributed Caching Helpers
• Hierarchical Coded Caching
• The Throughput-Outage Tradeoff of Wireless One-Hop Caching Networks
• Caching and Coded Multicasting: Multiple Groupcast Index Coding
• Online Coded Caching
• Living on the Edge: The Role of Proactive Caching in 5G Wireless Networks

Cited by in corpus (11)

• Wireless Content Caching for Small Cell and D2D Networks
• Information-Theoretic Caching: Sequential Coding for Computing
• Speeding up Future Video Distribution via Channel-Aware Caching-Aided Coded Multicast
• Wireless Multihop Device-to-Device Caching Networks
• Coded Caching Schemes with Low Rate and Subpacketizations
• A New Converse Bound for Coded Caching
• Information Theoretic Caching: The Multi-User Case
• Cache-Enabled Broadcast Packet Erasure Channels with State Feedback
• New Order-Optimal Decentralized Coded Caching Schemes with Good Performance in the Finite File Size Regime
• Constructions of Coded Caching Schemes with Flexible Memory Size
• Content Delivery in Erasure Broadcast Channels with Cache and Feedback