SCIENCE@home

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

Mingyue Ji,A. Tulino,Jaime Llorca,G. Caire

Published 2015 in IEEE Transactions on Information Theory

ABSTRACT

We consider the canonical <italic>shared link caching network</italic> formed by a source node, hosting a library of <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula> information messages (files), connected via a noiseless multicast link to <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> user nodes, each equipped with a cache of size <inline-formula> <tex-math notation="LaTeX">$M$ </tex-math></inline-formula> files. Users request files independently at random according to an a-priori known demand distribution q. A coding scheme for this network consists of two phases: cache placement and delivery. The cache placement is a mapping of the library files onto the user caches that can be optimized as a function of the demand statistics, but is agnostic of the actual demand realization. After the user demands are revealed, during the delivery phase the source sends a codeword (function of the library files, cache placement, and demands) to the users, such that each user retrieves its requested file with arbitrarily high probability. The goal is to minimize the average transmission length of the delivery phase, referred to as <italic>rate</italic> (expressed in channel symbols per file). In the case of deterministic demands, the optimal min-max rate has been characterized within a constant multiplicative factor, independent of the network parameters. The case of random demands was previously addressed by applying the order-optimal min-max scheme separately within groups of files requested with similar probability. However, no complete characterization of order-optimality was previously provided for random demands under the average rate performance criterion. In this paper, we consider the random demand setting and, for the special yet relevant case of a Zipf demand distribution, we provide a comprehensive characterization of the order-optimal rate for all regimes of the system parameters, as well as an explicit placement and delivery scheme achieving order-optimal rates. We present also numerical results that confirm the superiority of our scheme with respect to previously proposed schemes for the same setting.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-63 of 63 references · Page 1 of 1

CITED BY

Showing 1-100 of 242 citing papers · Page 1 of 3

123
Next