On the Average Performance of Caching and Coded Multicasting with Random Demands

Abstract

For a network with one sender, $n$ receivers (users) and $m$ possible messages (files), caching side information at the users allows to satisfy arbitrary simultaneous demands by sending a common (multicast) coded message. In the worst-case demand setting, explicit deterministic and random caching strategies and explicit linear coding schemes have been shown to be order optimal. In this work, we consider the same scenario where the user demands are random i.i.d., according to a Zipf popularity distribution. In this case, we pose the problem in terms of the minimum average number of equivalent message transmissions. We present a novel decentralized random caching placement and a coded delivery scheme which are shown to achieve order-optimal performance. As a matter of fact, this is the first order-optimal result for the caching and coded multicasting problem in the case of random demands.

5 pages, 3 figure, to appear in ISWCS 2014

References in corpus (3)

• Index coding via linear programming
• Fundamental Limits of Distributed Caching in D2D Wireless Networks
• The Throughput-Outage Tradeoff of Wireless One-Hop Caching Networks

Cited by in corpus (8)

• Fundamental Limits of Caching in Heterogeneous Networks with Uncoded Prefetching
• New Order-Optimal Decentralized Coded Caching Schemes with Good Performance in the Finite File Size Regime
• A Novel Centralized Strategy for Coded Caching with Non-uniform Demands
• Degrees of Freedom of Interference Networks with Transmitter-Side Caches
• A Delay-Aware Caching Algorithm for Wireless D2D Caching Networks
• Learning-Based Delay-Aware Caching in Wireless D2D Caching Networks
• Adaptive Delivery in Caching Networks
• An Efficient Multiple-Groupcast Coded Multicasting Scheme for Finite Fractional Caching