PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Mingyue Ji, Antonia M. Tulino, Jaime Llorca, Giuseppe Caire

arXiv:1502.03124v1cs.IT

TL;DR

The paper examines how to select caching distributions and coded-delivery schemes for random-demand caching. It combines optimized caching, conflict-graph structure, and coded delivery, reporting order-optimality for several schemes and a 5× expected-rate improvement at M = 20.

  • Problem

    Selecting caching distributions that depend on network parameters, not only the demand distribution q, is identified as important for order-optimal schemes.

  • Method

    The proposed family combines optimized RAP caching distributions with linear coded delivery schemes that exploit the conflict graph.

  • Results

    RLFU-GCC, RLFU-CIC, RAP-GCC, and RAP-CIC achieve order-optimal rate, while the proposed scheme improves expected rate by 5× at M = 20.

  • Takeaways & Limitations

    Both CIC and the simpler GCC are sufficient for order optimality, while further conflict-graph and caching-distribution structure can provide additional gains.

Abstract

from arXiv · show

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 ...

I. INTRODUCTION

Caching research studies how storage and coding can reduce wireless delivery costs, especially when user requests are asynchronous and conventional multicasting is ineffective. In shared-link networks, information-theoretic caching models formalize placement and delivery, while prior results mainly guarantee near-optimal worst-case rather than average-rate performance.

  • Motivation: Asynchronous user requests make naive multicasting ineffective, while conventional unicasting treats each request independently and misses demand redundancy.This motivates caching and coded delivery methods that can exploit shared demand structure despite time-shifted access.
  • Motivation: Caching popular content at wireless edge devices uses storage to improve over naive multicasting and conventional unicasting.The approach targets content distribution services including video on demand, catch-up TV, and internet video streaming.
  • Caching model: Information-theoretic caching models separate a setup-phase placement of coded library functions from a delivery phase satisfying users’ requests.The shared-link framework contains m files, users with cache capacity, and transmissions evaluated by normalized equivalent file transmissions.
  • Prior information-theoretic results: Prior work also shows that spatial reuse and coded multicasting gains are not cumulative in certain wireless caching networks.This result concerns random requests and average rate minimization in a different network setting.
  • Open problems: The optimal caching performance in arbitrary networks remains a hard and open problem, motivating analyses of specific practically relevant network models.Existing work includes D2D and shared-link networks with random demands, caching, and coded multicast delivery.
  • Prior information-theoretic results: In the shared-link network, prior coded caching schemes achieve approximately optimal min-max rate within a multiplicative constant independent of n, m, and M.These results concern worst-case demand performance and include deterministic and random caching with coded multicast delivery.

B. Contributions

The paper develops caching and coded-delivery schemes for random demands, with order-optimality results for Zipf distributions and broader converse insights. It also identifies when conventional schemes remain order-optimal and when popularity-aware caching and coding can improve performance.

  • The work targets scaling laws for the optimal average rate under Zipf demand distributions.
  • The proposed RAP-CIC scheme optimizes random caching using all system parameters and applies chromatic-number index coding across requested packets.
  • The paper provides an upper bound for RAP-CIC and an information-theoretic lower bound on the average rate of any caching scheme.
  • The proposed schemes are order-optimal for Zipf demands across all regimes of n, m, M, and α.
  • The analysis shows that optimized cache thresholds can make RLFU-GCC order-optimal, while conventional schemes retain order-optimality in some parameter regions.
  • For 0 ≤ α < 1, average and arbitrary-demand min-max rates are order-equivalent, whereas α > 1 can yield average-rate order gains.

III. RANDOM FRACTIONAL CACHING AND LINEAR INDEX CODING DELIVERY

This section introduces random fractional caching with linear index-coded delivery. It defines CIC through conflict-graph coloring and presents GCC as a polynomial-time alternative.

  • Random caching functions are independent across users, while delivery uses linear index coding on the induced conflict graph.
  • A. Random Fractional Caching Placement: Each file is partitioned into equal-size packets, and user u caches pfMB packets of file f according to distribution p.
  • A. Random Fractional Caching Placement: The caching distribution p determines the fraction of each file cached by every user and is designed from system parameters.
  • B. Linear Index Coding Delivery: CIC colors the conflict graph and XORs packets assigned the same color, transmitting one coded packet per color.
  • B. Linear Index Coding Delivery: CIC codes over all requested packets, unlike the earlier grouped approach, and enables every user to decode its requested packets.
  • B. Linear Index Coding Delivery: GCC exploits the conflict-graph structure with polynomial-time complexity and achieves asymptotically no larger rate than the exponentially complex greedy coloring.

C. Achievable Rate

The achievable-rate analysis bounds CIC and GCC using the caching distribution, demand distribution, and random conflict graph. In the large-file limit, the proposed random schemes concentrate below the stated bound.

  • The conflict graph and resulting CIC or GCC rate depend on the cache and demand realizations rather than the file contents.
  • Theorem 1 gives an achievable-rate bound for fixed caching distribution p in the shared-link network.
  • In the large-file limit, the conditional GCC rate concentrates to the left of min{ψ(q, p), m̄}, so cache configurations exceeding the bound have vanishing probability.
  • The bound is the minimum of ψ(q, p) and the average number of distinct requested files, denoted m̄.
  • For very small M, caching provides no order gains over conventional unicasting or naive multicasting, and m̄ becomes a tight upper bound for RGCC2.
  • The probabilities used to evaluate ψ(q, p) can be computed by sorting values of gℓ(j).

D. Random Caching Optimization

The paper optimizes random caching through a popularity-truncated placement and analyzes RLFU-GCC against rate lower bounds. For Zipf demands, the resulting scheme is order-optimal in the stated regimes, while optimized cutoffs can provide substantial finite-parameter gains.

  • Caching optimization: The caching distribution p* minimizes the achievable rate, but its general form may be analytically intractable, motivating the simpler RLFU placement.RLFU caches equal fractions of randomly selected packets from the most popular em files and none from the remainder; em = M recovers LFU.
  • Order-optimality: RLFU-GCC is sufficient for order-optimal rate under Zipf demands, despite being generally inferior to RAP-GCC.The comparison uses an achievable upper bound and a rate lower bound; order-optimality means their ratio is uniformly bounded for sufficiently large m.
  • Zipf regimes: For 0 ≤ α < 1, setting em = m makes RLFU-GCC order-optimal and equivalent in order to the deterministic-demand min-max rate.This choice corresponds to uniform random packet placement across the library and is also called UP.
  • Scope: The analysis omits the α = 1 Zipf case because it requires a different treatment.The paper cites analytical complexity and the prevalence of empirical demand parameters other than α = 1 as reasons for omission.
  • Zipf regimes: For α > 1, optimized em can yield substantial constant-rate gains, especially when α is close to 1.The cutoff is obtained by minimizing the achievable upper bound subject to M ≤ em ≤ m.
  • Numerical comparison: At target rate 20, optimized RLFU-GCC requires M ≈ 800, compared with M ≈ 2000 for UP-GCC when m = 50000, n = 50, and α = 0.9.The comparison is shown for the rate-versus-cache-size setting in Fig. 2.

B. Case α > 1

For α > 1, order-optimality depends on how the user count scales with library size and on cache capacity. UP-GCC suffices for sufficiently many users, whereas RLFU-GCC is needed across several smaller-user regimes.

  • Large-user regime: When n = ω(m^α), UP-GCC achieves order-optimal rate.This is the large-user regime for Zipf demands with α > 1.
  • Intermediate-user regime: When n = Θ(m^α), RLFU-GCC achieves order-optimal rate using cutoff values em specified for the system subcases.The corresponding achievable upper bounds are provided in Table I.
  • Small-to-moderate user regime: When n = o(m^α), RLFU-GCC achieves order-optimal rate with cutoff choices given in Tables II and III.For ρ > 1, the network behaves similarly to the n = ω(m^α) regime, where UP-GCC is order-optimal.
  • Cache-capacity regimes: For M < 1, the achievable rate scales as 2n^(1/α), and caching provides no significant gain over combining naive multicasting with unicasting.The same leading-order rate can be achieved without caching.
  • Cache-capacity regimes: For n = o(m^(α−1)) and sublinear M, popularity-aware caching achieves an order gain over UP and over the min-max order-optimal rate.The paper attributes this gain to caching according to demand popularity.

C. Remark

The proposed caching distributions adapt to network parameters and demand aggregation, while coded delivery across all requested packets supports order-optimal performance and substantial simulated rate improvements. Simulations compare these schemes with uncoded, grouped, and uniform-caching baselines.

  • Order optimality: The proposed schemes achieve order-optimal rates, including UP-GCC, RLFU-CIC, RAP-GCC, and RAP-CIC.For constant library size under Zipf demands, UP-GCC is stated to have a constant gap guarantee for arbitrarily small ϵ independent of m, n, and M.
  • Caching distribution: The caching distribution adapts to system parameters beyond the local demand distribution q, a key feature of the order-optimal schemes.This adaptation is identified as one reason previously proposed schemes lacked order-optimal guarantees.
  • Coded delivery: CIC delivery over the entire set of requested packets avoids missed coding opportunities that can arise when file subsets are treated independently.The paper contrasts this with grouped schemes, where separate coding across subsets can significantly degrade coded-multicast efficiency.
  • Simulation results: RLFU-GCC significantly outperforms LFU-NM and the reference grouping scheme in the simulated scenarios.For α = 1.6, m = 500, n = 5000, and M = 20, it improves expected rate by 5× over the reference scheme and 8× over LFU-NM.
  • Simulation results: Finite-length hierarchical greedy coloring can further improve rates beyond the asymptotic RLFU-GCC, UP-GCC, and LFU-NM comparisons.Figure 7 compares RAP-HgC with these schemes for B = 500 and small network examples.

VII. CONCLUSIONS

The paper develops caching and coded-delivery schemes for random demands, establishing achievability and converse results for average rate. Its order-optimality results characterize when caching gains are absent, linear or nonlinear in cache size, and when simple or coded delivery is required.

  • Problem and framework: The paper formally studies shared-link caching with coded delivery and random demands under an average per-user rate criterion.It provides achievability and converse analysis for this setting.
  • Proposed schemes: Random fractional caching with Chromatic-number Index Coding delivery constructs rates through a conflict graph containing all requested packets.The proposed Greedy Constrained Coloring delivery is polynomial in the system parameters.
  • Order-optimality: RLFU-GCC is order-optimal for Zipf demands by comparing its achievable rate with a general lower bound.Here, order-optimality means the achievable-to-optimal rate ratio remains bounded by a constant as m,n→∞, including the stated fixed-m, n→∞ case.
  • Design principles: The caching distribution must adapt to all system parameters, not only the demand distribution, because file-group separation can miss coding opportunities.The paper identifies this adaptation as a key feature distinguishing its schemes from earlier approaches.
  • Scaling results: The scaling analysis identifies regimes where caching is useless, where it provides multiplicative gains, and where those gains are linear or nonlinear in M.The dependence of these regimes on the Zipf parameter α is also characterized.
  • Operational implications: In some multiplicative-gain regimes, RAP-CIC converges to LFU with naive multicasting, whereas other regimes require fractional caching and index-coded delivery.Thus, additional coding complexity is not uniformly necessary for order-optimality.

APPENDIX A

The appendix analyzes the random conflict-graph structure underlying GCC. It bounds independent-set counts through user labels, cache-placement probabilities, concentration, and convergence arguments before applying the result to converse comparisons.

  • Independent-set counting: GCC independent sets are counted by enumerating unordered user labels and upper-bounding the sets generated for each label.A necessary condition is that each labeled user requests a packet cached by exactly the other labeled users.
  • Theorem application: Theorem 1 follows by combining the concentration argument with the demand distribution, whose maximizer probabilities are the quantities ρ_f,ℓ.The proof then applies the theorem to the optimized caching distribution.
  • Cache events: For a labeled user subset, the relevant cache event has probability (p_f M)^(ℓ−1)(1−p_f M)^(n−ℓ).The event corresponds to ℓ−1 users caching the packet and n−ℓ users not caching it, conditional on the requesting user missing it.
  • Concentration: The packet-level indicators are not independent across packets, so the proof uses conditional probabilities and concentration rather than an i.i.d. assumption.As B→∞, the normalized quantities concentrate around g_ℓ(f).
  • Maximizer comparison: When g_ℓ values are distinct, concentration makes the empirical maximizer agree with the maximizer of g_ℓ with vanishing error probability.Equivalent classes extend the argument when distinct file indices yield the same g_ℓ value.
  • Converse: The converse lower bound is obtained by restricting service to selected users and comparing with a genie-aided uniform-demand system.The resulting bound includes the maximization over z shown in the theorem statement.

APPENDIX D

The appendix proves order-optimality across parameter regimes by comparing the RLFU-GCC upper bound with the converse lower bound. It separates cases according to user-library scaling and cache size.

  • Proof strategy: The proof evaluates the converse and achievable upper bound by selecting ℓ, r, e_z, and z according to the system regime.The constants δ and σ are chosen independently of m, n, and M.
  • User-library regimes: For n=ω(m) and n=O(m), the analysis treats separate cache-size subregions illustrated in Figs. 8 and 9.The appendix computes the gap between R_lb and R_ub in each subregion.
  • Converse evaluation: The lower-bound analysis uses the maximization max_z(z−zM/⌊ℓ/z⌋) over an admissible range of z.The admissible range depends on the selected parameters and the cache regime.
  • Superlinear user scaling: When n=ρm^α with ρ<1, the proof separates the regions 0≤M<1, 1≤M<m^α, and M≥m^α.The corresponding cache subregions are illustrated in Fig. 10.

A. Region of 0 ≤M < 1

For the region 0≤M<1, the appendix evaluates achievable and converse rates using regime-specific parameter choices. The resulting comparison establishes order-optimality of RLFU-GCC in this region.

  • Achievability analysis: The achievable-rate analysis substitutes the selected parameters into the upper-bound expression for R_ub(n,m,M,q,e_m).The proof evaluates the terms separately before combining them.
  • Converse construction: The proof computes the converse using Theorem 2 and selects parameters ℓ, r, e_z, and z for the small-cache region.The constants δ and σ remain in (0,1), with choices constrained by the converse construction.
  • Order-optimality: The appendix states that the resulting bound is uniformly bounded for suitable constant choices of σ and δ.This uniform bound is the basis for the order-optimality conclusion.
  • Conclusion: The section concludes that RLFU-GCC achieves order-optimal expected rate in the analyzed small-cache setting.The conclusion follows from the comparison with the converse bound.

APPENDIX F

Appendix F proves order-optimality of the achievable expected rate across the memory regimes in Table II, using case-specific converse analyses. The proof treats regions from 0 ≤ M < 1 through M ≥ mα and subdivides them by scaling relations among n, m, and M.

  • Table II covers the memory regions 0 ≤M < 1, 1 ≤M < mα, and M ≥mα under n = o(mα).
  • For 0 ≤M < 1, caching cannot provide a large gain, and M cannot affect the order of the expected rate.
  • The proof subdivides 1 ≤M < mα into cases such as M = o(m), M = Θ(m), and n mα−1 = Θ(1), with further subregions shown in Fig. 11.
  • The converse calculations establish order-optimality of the achievable expected rate in the analyzed regimes.
  • For M = Θ(m), the analysis distinguishes κ1 thresholds and imposes constraints on c to ensure ℓ < m.
  • When M = o(m) or M = Θ(m) in the relevant regimes, the results show order-optimality for RLFU and RAP.

APPENDIX G

Appendix G proves order-optimality of RLFU when n = o(mα), organizing the analysis by the scaling of memory relative to n and m. The proof uses separate subregions illustrated in Fig. 13.

  • Appendix G addresses the case n = o(mα) and proves order-optimality of RLFU.
  • The analysis first separates κ ≥1 and κ < 1, with all memory subregions illustrated in Fig. 13.

A. Region of κ < 1

For κ < 1, the appendix derives converse bounds using Theorem 2 and compares them with achievable rates across multiple memory and scaling subregions. These comparisons establish order-optimality in the treated cases.

  • The κ < 1 analysis separates memory scalings including M = o(m) and M = Θ(m), with additional κ1 thresholds and subcases.
  • The converse uses Theorem 2 with parameters ℓ, r, and ez selected separately for each scaling regime.
  • The proof reports that the achievable expected rate is order-optimal in the analyzed subregion.
  • For κ1 > µ, the constant c is restricted to 1 < c < µ to guarantee ℓ < m, while another subcase restricts c to 1 < c < 2.

2) When M = Θ(m)

When M = Θ(m), the appendix divides the analysis by κ1 and by whether m/M exceeds specified thresholds, then derives matching converse and achievable-rate orders. It also treats the regime M > m separately.

  • For M = Θ(m) with 0 < κ1 < 1, the proof distinguishes m/M > 2 from m/M ≤2.
  • When m/M > 2, the analysis uses em = M and constrains c to 1 < c < 2 to guarantee ℓ < m.
  • The converse lower bound includes a maximization over z, and the resulting comparison yields a matching order for the achievable rate.
  • The appendix also analyzes M > m as a separate case using the converse expression and corresponding achievable-rate bounds.
Loading 1502.03124v1…