We propose a novel caching strategy for the problem of centralized coded caching with non-uniform demands. Our placement strategy can be applied to an arbitrary number of users and files, and can be easily adapted to the scenario where file popularities are user-specific. The distinguishing feature of the proposed placement strategy is that it allows for equal sub-packetization for all files while requiring the users to allocate more cache to the more popular files. This creates natural broadcasting opportunities in the delivery phase which are simultaneously helpful for users who have requested files of different popularities. For the case of two files, we propose a delivery strategy which meets a natural extension of the existing converse bounds under uncoded placement to non-uniform demands, thereby establishing the optimal expected memory-rate trade-off for the case of two files with arbitrary popularities under the restriction of uncoded placement.
The graph-based delivery strategies that are predominantly used in this line of research @cite_21 @cite_12 are inherently limited, in that they do not capture the algebraic properties of summation over finite fields. For instance, one can easily construct examples where the chromatic-number index coding scheme in @cite_21 is sub-optimal, even for uniform file popularities. Suppose we have only one file @math and 3 users each with a cache of size @math file. Assume user @math caches @math . In this case, the optimal delivery rate is @math but the clique-cover (or chromatic-number) approach in @cite_21 only provides a delivery rate of 1. This is due to the fact that from @math and @math one can recover @math , a property that the graph-based model in @cite_21 fails to reflect. This issue was addressed in a systematic manner by Yu et. al. in @cite_20 which introduced the concept of leaders. Our delivery scheme in this paper provides an alternative mechanism for overcoming this limitation, which transcends the uniform file popularities and can be applied to nonuniform demands. This is accomplished via interference alignment as outlined in the proof of achievability of Lemma in Section .
@cite_21 @cite_20 @cite_12
2517585112 2963602389 2598021007 2796240652
We study a noiseless broadcast link serving @math users whose requests arise from a library of @math files. Every user is equipped with a cache of size @math files each. It has been shown that by splitting all the files into packets and placing individual packets in a random independent manner across all the caches prior to any transmission, at most @math file transmissions are required for any set of demands from the library. The achievable delivery scheme involves linearly combining packets of different files following a greedy clique cover solution to the underlying index coding problem. This remarkable multiplicative gain of random placement and coded delivery has been established in the asymptotic regime when the number of packets per file @math scales to infinity. The asymptotic coding gain obtained is roughly @math . In this paper, we initiate the finite-length analysis of random caching schemes when the number of packets @math is a function of the system parameters @math , and @math . Specifically, we show that the existing random placement and clique cover delivery schemes that achieve optimality in the asymptotic regime can have at most a multiplicative gain of 2 even if the number of packets is exponential in the asymptotic gain @math . Furthermore, for any clique cover-based coded delivery and a large class of random placement schemes that include the existing ones, we show that the number of packets required to get a multiplicative gain of @math is at least @math . We design a new random placement and an efficient clique cover-based delivery scheme that achieves this lower bound approximately. We also provide tight concentration results that show that the average (over the random placement involved) number of transmissions concentrates very well requiring only a polynomial number of packets in the rest of the system parameters. We consider the canonical shared link caching network formed by a source node, hosting a library of @math information messages (files), connected via a noiseless multicast link to @math user nodes, each equipped with a cache of size @math 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 rate (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. We consider the content delivery problem in a fading multi-input single-output channel with cache-aided users. We are interested in the scalability of the equivalent content delivery rate when the number of users, @math , is large. Analytical results show that, using coded caching and wireless multicasting, without channel state information at the transmitter, linear scaling of the content delivery rate with respect to @math can be achieved in some different ways. First, if the multicast transmission spans over @math independent sub-channels, e.g., in quasi-static fading if @math , and in block fading or multi-carrier systems if @math , linear scaling can be obtained, when the product of the number of transmit antennas and the number of sub-channels scales logarithmically with @math . Second, even with a fixed number of antennas, we can achieve the linear scaling with a threshold-based user selection requiring only one-bit feedbacks from the users. When CSIT is available, we propose a mixed strategy that combines spatial multiplexing and multicasting. Numerical results show that, by optimizing the power split between spatial multiplexing and multicasting, we can achieve a significant gain of the content delivery rate with moderate cache size. We investigate the problem of coded caching for nonuniform demands when the structured clique cover algorithm proposed by Maddah-Ali and Niesen for decentralized caching is used for delivery. We apply this algorithm to all user demands regardless of their request probabilities. This allows for coding among the files that have different request probabilities but makes the allocation of memory to different files challenging during the content placement phase. As our main contribution, we analytically characterize the optimal placement strategy that minimizes the expected delivery rate under a storage capacity constraint. It is shown that the optimal placement follows either a two or a three group strategy, where a set of less popular files are not cached at all and the files within each of the other sets are allocated identical amounts of storage as if they had the same request probabilities. We show that for a finite set of storage capacities, that we call the base-cases of the problem, the two group strategy is always optimal. For other storage capacities, optimal placement is achieved by memory sharing between certain base-cases and the resulting placement either follows a two or a three group strategy depending on the corresponding base-cases used. We derive a polynomial time algorithm that determines the base-cases of the problem given the number of caches and popularity distribution of files. Given the base-cases of the problem, the optimal memory allocation parameters for any storage capacity are derived analytically.