Source-linked AI summary
Coded Caching with Nonuniform Demands
Urs Niesen, Mohammad Ali Maddah-Ali
TL;DR
The paper asks how to minimize expected shared-link load when multiple users request files with widely differing popularities, a setting where storing only the most popular files can be suboptimal. It proposes grouping similarly popular files and applying coded caching within each group, with an approximation guarantee. The scheme can substantially reduce expected load and cache requirements relative to HPF.
Problem
With multiple caches and nonuniform file popularities, highest-popularity-first caching can be highly suboptimal for minimizing expected shared-link load.
Method
The scheme groups files with similar popularities, allocates memory by group, and uses coded caching for delivery within each group.
Results
At M = 600F bits, expected load falls from 152F bits for HPF to 56F bits for the grouped coded scheme, an improvement by more than a factor 2.7.
Takeaways & Limitations
Coding is required for optimal operation of caching systems with multiple caches under nonuniform popularities, rather than relying on uncoded HPF.
Abstract
from arXiv · showhide
We consider a network consisting of a file server connected through a shared link to a number of users, each equipped with a cache. Knowing the popularity distribution of the files, the goal is to optimally populate the caches such as to minimize the expected load of the shared link. For a single cache, it is well known that storing the most popular files is optimal in this setting. However, we show here that this is no longer the case for multiple caches. Indeed, caching only the most popular files can be highly suboptimal. Instead, a fundamentally different approach is needed, in which the cache contents are used as side information for coded communication over the shared link. We propose such a coded caching scheme and prove that it is close to optimal.
I. INTRODUCTION
The paper studies expected shared-link load when file popularities are nonuniform and shows that single-cache HPF intuition fails with multiple caches. It proposes coded caching that uses cache contents as side information to improve delivery.
- Problem setting: Caching stores content near users to reduce shared-network load in a server–cache network with N files and K users.Each user has an isolated cache of size MF bits.
- Motivation: For a single cache, highest-popularity-first caching is optimal, but this intuition fails for multiple caches, where HPF can be arbitrarily suboptimal.The paper therefore seeks a fundamentally different multi-cache strategy.
- Toy example: In the two-user example, coded caching sends 1/2F bits on average, compared with 5/9F for broadcast HPF and 2/3F for unicast HPF.Files are split into halves, placed across users, and combined through an XOR transmission.
- Motivation: Expected load is more relevant than peak load when file popularities differ substantially, especially over many users or long operating periods.The law of large numbers makes aggregate demand behavior important in these settings.
- Contributions: The proposed scheme groups files with similar popularities, applies coded caching within groups, and provides a bicriteria approximation guarantee.It is evaluated on Netflix popularities against uncoded HPF.
II. PROBLEM SETTING
The model separates cache placement from demand-dependent delivery in a noiseless broadcast network. Users independently request files according to a known popularity distribution, and performance is measured by expected and peak rates.
- Network model: The system has one server, N equal-size files, K users, and isolated caches of size MF bits connected by a noiseless broadcast link.The normalized cache size M may be real-valued even though MF is an integer number of bits.
- Placement phase: During placement, a caching function stores file content in each cache subject to the MF-bit memory constraint.Placement occurs before user demands are revealed.
- Delivery phase: During delivery, each user requests one file, and the server sends a request-vector-dependent transmission that users decode using the broadcast signal and their cache contents.The scheme includes one encoding function and K decoding functions for every possible request vector.
- Demand model: Users independently request file n with probability p_n under the independent reference model.The popularity probabilities form a distribution over the N files.
- Performance metrics: The expected rate averages request-dependent delivery rates, while the peak rate is the maximum rate over all request vectors.The optimal expected rate is defined asymptotically in the large-file limit.
III. BACKGROUND ON CODED CACHING
The reviewed coded-caching scheme randomly distributes file bits across caches and exploits that placement during delivery. XOR-based multicasting lets users recover missing pieces simultaneously, yielding an achievable rate for every demand vector.
- Algorithm: Each user randomly caches MF/N bits from every file, using independent uniform subsets that satisfy the cache-memory constraint.Delivery then codes several requested files together to exploit available side information.
- Algorithm: The placement partitions each file into subfiles indexed by the subset of users whose caches store each bit.This creates cache-exclusive pieces and uncached pieces for delivery.
- Delivery: For different demands, the server XORs requested pieces that users can partially resolve from their cached side information.In the two-user example, A2 ⊕ B1 lets each user recover the missing requested part.
- Guarantee: The placement is designed to create coded multicasting opportunities simultaneously across all possible demands.The resulting rate is therefore achievable as a peak rate for every user-demand vector.
- Scope: The theoretical setting assumes equal file sizes, synchronous requests, and sufficiently large files to simplify analysis.The paper notes that these assumptions can be relaxed in related work and a prototype.
IV. THEORETICAL RESULTS
The paper develops grouped coded caching for nonuniform file popularities and establishes bicriteria guarantees relative to optimal expected-rate caching. Grouping preserves within-group symmetry, enables popularity-aware memory allocation, and yields a modest approximation gap when popularity spans are not extreme.
- Scheme design: The proposed scheme groups files with approximately uniform popularities, allocates memory across groups, and applies coded delivery separately within each group.Files in different groups may receive different memory allocations, while coding opportunities across groups are ignored.
- Grouping rationale: The grouping limits approximation loss by bounding within-group popularity variation by a factor of two and keeping the number of exponentially scaled groups small.For the stated construction, L = ⌈log p1/pN⌉.
- Theoretical guarantees: Theorems 1 and 2 provide a bicriteria approximation guarantee: a boundary point (R, M) is matched by the grouped scheme at (cLR, LM).The constant c is independent of the problem parameters, while L is the number of popularity groups.
- Approximation gap: The scheme’s approximation factor is usually modest because exponential popularity grouping makes L small.The paper explicitly attributes this to the construction L = ⌈log p1/pN⌉.
- Special case: For uniform file popularity, L = 1, so the proposed coded caching scheme is within a constant factor of optimal expected rate.In this case, optimal peak and expected rates are approximately the same.
- Comparison with HPF: The proposed scheme’s expected rate can be up to a factor Θ(K) smaller than HPF, although HPF is optimal for a single cache.Thus, the single-cache intuition does not extend to multiple caches.
V. EMPIRICAL RESULTS
Under Netflix popularities, the grouped coded caching scheme substantially improves the memory-rate tradeoff over HPF, while retaining a stated approximation guarantee.
- The Netflix popularity distribution has a flat head of roughly 600 files followed by a power-law tail with exponent approximately −2.
- For K = 300 users and N = 10 000 files, Fig. 4 compares the memory-rate curves of HPF and grouped coded caching under Netflix popularities.
- At M = 600F bits, HPF sends 152F bits on average, whereas grouped coded caching sends 56F bits, improving the load by more than a factor of 2.7.
- At the same expected load of 152F bits, grouped coded caching requires only M = 63F bits instead of HPF’s M = 600F bits, a factor-9.5 memory improvement.
- The proposed scheme is within a factor cL in the rate direction and a factor L in the memory direction of the optimal memory-rate tradeoff; here L = 10.
VI. CONCLUSIONS AND FOLLOW-UP RESULTS
The paper concludes that coding is required for optimal operation with multiple caches under nonuniform popularities, and follow-up work refines the grouping approach and its guarantees.
- With a single cache, uncoded HPF is optimal for nonuniform popularities, whereas with multiple caches the paper shows that coding is required for optimal operation.
- Follow-up work proposed applying decentralized coded caching to the most popular N1 files and serving requests outside that set directly from the server.
- A later result chooses N1 as the largest n satisfying KMp_n ≥ 1 and proves a universal constant multiplicative-plus-additive gap when M ≥ 2.
- For systems with one user per cache, follow-up work finds that using only L = 2 groups can be approximately optimal, while many users per cache can require L > 2 groups.
APPENDIX A OPTIMALITY OF THE HIGHEST-POPULARITY FIRST CACHING RULE FOR K = 1
The appendix proves that HPF minimizes expected rate for the single-user caching problem even when coded caching is allowed, establishing that coding is unnecessary for K = 1.
- For a single cache, HPF stores the most popular files, with partial storage of the next file when the normalized memory is noninteger.
- For K = 1 and arbitrary file popularities, highest-popularity first minimizes the expected rate among all caching schemes.
- The proof lower-bounds every scheme’s expected link load using the cache contents and delivery messages associated with each requested file.
- A cut-set argument supplies the key inequality by observing that the user can decode files 1 through n from their messages and cache contents.
- The resulting lower bound equals the expected rate achieved by HPF, completing the optimality proof.
APPENDIX B PROOF OF THEOREM 1
The proof analyzes grouped coded caching by decomposing random demands into popularity groups, relating each group’s optimal expected rate to near-uniform and uniform cases, and optimizing memory allocation.
- Algorithm 1 has the same peak rate for every demand, so its expected rate equals its rate for any specific request.
- A random request partitions users into group-specific subsets, and the delivery algorithm serves those groups independently.
- The expected-rate upper bound averages over the random group sizes induced by user requests.
- Optimizing the memory allocation across groups minimizes this upper bound and yields Theorem 1.
- The proof of Theorem 2 uses three claims connecting uniform-popularity, almost-uniform-popularity, and group-restricted caching problems.
- Within each group, popularities differ by at most a factor of two, enabling the almost-uniform comparison used in the proof.
- The resulting constant in the approximation is c = 72 · 12, though the analysis notes that a more careful proof could reduce it.
A. Proof of Claim 1 (Symmetrization and Cut-Set Arguments)
Claim 1 is proved through three lemmas connecting uniform-demand expected rates, distinct-request counts, and a peak-rate bound. Symmetrization and a cut-set argument establish the key lower bound, yielding that Algorithm 1’s peak rate is within a factor of 12 of the optimal without-replacement expected rate.
- Three-lemma proof: Lemma 4 lower bounds the uniform-popularity expected rate using the expected rate for requests chosen uniformly without replacement.The comparison is stated for any s from 1 through K.
- Three-lemma proof: Lemma 5 shows that the number of distinct requests is not too small with large probability.Its proof models the process as a coupon collector problem and uses geometrically distributed waiting times.
- Three-lemma proof: Lemma 6 lower bounds the optimal expected rate for uniformly random requests without replacement in terms of Algorithm 1’s peak rate.The proof combines symmetrization over disjoint subsets with a cut-set argument around s users.
- Conclusion: 12 is the maximum factor separating Algorithm 1’s peak rate from the optimal expected rate for uniformly random requests without replacement.This is the stated consequence of the proof’s lemmas.
- Symmetrization and cut-set: The cut-set argument requires the caches and transmissions to recover sI distinct files, producing the corresponding information lower bound.Across I demand vectors, the s users have total cache size sMF bits and transmissions totaling the summed rates times F bits.
B. Proof of Claim 2 (Uniformization Argument)
The uniformization argument uses a genie to remove selected requests so that the remaining requests are uniformly distributed over files. Probability and partitioning arguments then relate the resulting system to the original nonuniform-demand system.
- Rate comparison: The resulting comparison identifies the original nonuniform-demand rate with, up to a constant, the optimal rate under uniform file popularities.The left-hand side concerns K users with popularities {pn}; the right-hand side concerns the same system with uniform popularities.
- Genie transformation: The genie helps a request for file n with probability 1 − pN/pn, while the complementary event occurs with probability pN/pn ≥ 1/2.If the genie helps, it supplies the requested file for free; otherwise the user remains for shared-link delivery.
- Genie transformation: The probability that a user requests file n and is not helped is identical for every file n.The genie applies the procedure independently to each user.
- Genie transformation: Ignoring genie-served users transforms K users with nonuniform popularities into a random number of users with uniform file popularities.The remaining number of users is denoted by K̃.
- Probability bound: With probability at least 1/3, at least ⌈K/4⌉ users are not helped by the genie.This follows from the bound on the expected number of users helped and Markov’s inequality.
- Rate comparison: The optimal expected rate for K users is related to the rate of a system with ⌈K/4⌉ users by partitioning the users into four parallel subsets.The rate of the parallel construction is the sum of the four subset rates, and the optimal scheme can be no worse.
C. Proof of Claim 3
For Claim 3, a genie supplies every user requesting a file outside Nℓ with that file for free, which can only reduce the shared-link rate. The resulting genie-aided rate therefore provides a lower bound on the original optimal expected rate.
- Genie-aided lower bound: The genie gives users requesting files outside Nℓ their requested files for free before shared-link delivery.Users whose requests are served by the genie can be omitted from the subsequent transmission problem.