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

I. INTRODUCTION

• Content distribution services drive exponential wireless traffic growth, while asynchronous requests make naive multicasting ineffective and conventional unicast misses demand redundancy.The introduction presents edge caching of popular content as a way to improve over both approaches.Source: §I · p. 3

A. Related work

• The optimal caching performance in arbitrary networks remains a hard, open problem, motivating analysis of specific models relevant to wireless networks.Prior work also generalized data placement to coded content distribution, relating it to network coding and showing polynomial solvability under uniform demands but hardness under arbitrary demands,.Source: A. Related work · pp. 4–5
• For D2D networks with Zipf demands and α < 1, [2] reports order-optimal average per-user throughput when nM ≥ m and n and m grow large.The scheme uses decentralized random caching and uncoded unicast delivery.Source: A. Related work · p. 5
• Multicast-delivery schemes provide approximately optimal min-max rates, within a multiplicative constant independent of n, m, and M from an information-theoretic lower bound, for worst-case user demands.Source: A. Related work · p. 5
• In a D2D network, prior work [21] found spatial-reuse and coded-multicasting gains are not cumulative, reflecting their contrasting local and global communication goals.Source: A. Related work · p. 6
• This work combines random requests, as in [2],,,, with the single-source shared-link network studied in,.Source: A. Related work · p. 6
• Prior work [20] partitioned files into subsets with approximately uniform request probabilities and applied the min-max strategy of to each subset.Source: A. Related work · p. 6
• The approach [20] uses the constant-factor relation between uniform-demand average rate and arbitrary-demand min-max rate, but restricts partitions to files whose popularities differ by at most a factor.The restriction reflects the difficulty of finding the optimal file partition and corresponding cache-memory allocation.Source: A. Related work · p. 6

B. Contributions

• RAP-CIC optimizes random caching using all system parameters and applies chromatic-number index coding across all requested packets.This addresses limitations of [20], whose placement used local popularity and whose delivery treated file groups separately.Source: B. Contributions · p. 7
• The paper bounds RAP-CIC’s achievable rate through the average chromatic number of its random conflict graph and numerically optimizes the bound to demonstrate gains over [20].A direct analysis of RAP-CIC is described as elusive.Source: B. Contributions · p. 7
• For analytical tractability, RLFU-GCC uses a step-function caching distribution and greedy constrained coloring, a polynomial-time approximation of CIC.Under the Zipf case, uniformly caching the most popular files is order-optimal when the cache threshold is carefully optimized for system parameters.Source: B. Contributions · pp. 7–8
• The paper provides an information-theoretic lower bound on average rate and shows order-optimality for Zipf demands, while identifying converse techniques applicable beyond Zipf.These are presented as the first order-optimal results under this network model for nontrivial popularity distributions.Source: B. Contributions · p. 7
• For 0 ≤ α < 1, average rate under Zipf random demands and min-max rate under arbitrary demands are order-equivalent; for α > 1, average rate can gain in order.The analysis also identifies regions where LFU with naive multicasting remains order-optimal and opportunities for RAP or RLFU with CIC or GCC.Source: B. Contributions · p. 8
• For Zipf demands, the proposed achievability schemes are order-optimal across system regimes, among the first such results for nontrivial popularity distributions.The converse technique is not restricted to Zipf demands and can establish order-optimality in other cases.Source: B. Contributions · pp. 7–8

II. NETWORK MODEL AND PROBLEM FORMULATION

• The model has a library of m files and n users with cache capacity M files; users request independently according to a known demand distribution q.Caching occurs once during setup, and the delivery rate is averaged over the random request vector.Source: §II · pp. 9–10
• Users request files according to q, and the network sends a variable-length transmission until all users decode before beginning the next request round.Because the library changes slowly, the analysis focuses on delivery rate and disregards the cost of filling caches.Source: §II · p. 10
• The rate is normalized coding length in file units, with performance taken worst-case over library realizations rather than averaged over them.The paper notes that averaging over file realizations has little operational meaning because the content library changes very slowly.Source: §II · p. 10
• A rate is achievable when a sequence of admissible caching schemes has rate R(F) no greater than that rate.The system’s optimal rate R*(n, m, M, q) is the infimum of achievable rates.Source: §II · pp. 10–11
• Order-optimality requires a rate within a constant factor independent of m, n, and M as library size m grows and n tends to infinity.The definition takes F to infinity first, then m to infinity, with n and M allowed to vary as functions of m.Source: §II · p. 11

III. RANDOM FRACTIONAL CACHING AND LINEAR INDEX CODING DELIVERY

• As file size F grows, the random rate falls below a given threshold with high probability, establishing achievability by the scheme itself rather than only by an existence argument.Source: §III · p. 11

A. Random Fractional Caching Placement

• Each file is split into B equal packets, and each user stores pfMB distinct packets per file, with 0 ≤ pf ≤ 1/M and pf denoting the fraction of memory allocated to file f.The packet subsets are chosen uniformly and independently across users and files.Source: A. Random Fractional Caching Placement · p. 12

B. Linear Index Coding Delivery

• CIC colors the conflict graph and XORs packets assigned the same color, transmitting each color's combined packets as one packet.It allows coding over the full set of requested packets, rather than restricting coding to packets within particular file groups [20].Source: B. Linear Index Coding Delivery · pp. 13–14
• CIC lets all users decode their requested packets with zero error for every file length, making it fixed-to-variable length exactly lossless.Source: B. Linear Index Coding Delivery · p. 14
• GCC exploits the caching-induced conflict-graph structure, runs in polynomial time in n and B, and asymptotically achieves rate no worse than the exponentially complex greedy coloring algorithm [19].Source: B. Linear Index Coding Delivery · p. 15
• Algorithm 1 forms independent sets from vertices whose packets have the same set of requesting or caching users.Each set is built from a root vertex and other independent vertices with the same user set.Source: B. Linear Index Coding Delivery · p. 15
• GCC2 is naive multicasting: it transmits each requested packet uncoded for simultaneous reception by all users requesting it.The scheme assigns a set and color to each requested packet.Source: B. Linear Index Coding Delivery · p. 15
• The cited analysis states that Algorithm 1 has complexity O(n^3B^2), polynomial in n and B, and that this complexity dominates Algorithm 2, yielding the overall complexity.Source: B. Linear Index Coding Delivery · p. 16

C. Achievable Rate

• In the large-file limit, GCC’s conditional rate concentrates below min{ψ(q,p), m̄}, the smaller of ψ(q,p) and the average number of distinct requested files.The theorem gives this achievable bound for fixed caching distribution p.Source: C. Achievable Rate · p. 17
• For every realization of caches and demands, CIC’s rate is no greater than GCC’s, so GCC’s rate stochastically dominates CIC’s.Source: C. Achievable Rate · p. 17
• When m̄ < ψ(q,p), a very-small-cache regime, caching provides no order gains over conventional unicasting or naive multicasting, and m̄ tightly bounds GCC2.Source: C. Achievable Rate · p. 18
• For numerical evaluation, the probabilities ρ_f,ℓ can be computed by sorting the values {g_ℓ(j): j ∈ F}.Source: C. Achievable Rate · p. 18

D. Random Caching Optimization

• The optimized caching distribution p* minimizes the rate, but its generally intractable expression motivates analyzing a truncated-uniform alternative.RLFU caches the same fraction of randomly selected packets from the e_m most popular files and none from the rest; when e_m = M, it coincides with LFU.Source: D. Random Caching Optimization · pp. 18–19

IV. RATE LOWER BOUND

• Theorem 2 provides a rate lower bound that every admissible scheme for the shared-link network must satisfy.The bound is stated for n users, library size m, cache capacity M, and demand distribution q.Source: §IV · p. 20

V. ORDER-OPTIMALITY

• Under Zipf demands, RLFU-GCC is order-optimal when its achievable-rate to lower-bound ratio stays uniformly bounded for sufficiently large m.Order-optimality of RLFU-GCC also implies order-optimality of schemes using optimized RAP placement and/or CIC delivery.Source: §V · p. 20

A. Case 0 ≤α < 1

• For Zipf demands with 0 ≤ α < 1, RLFU-GCC with e_m = m achieves order-optimal rate.This placement caches packets uniformly across all library files and is also called uniform placement; its rate is order-equivalent to the deterministic-demand min-max rate.Source: A. Case 0 ≤α < 1 · p. 21
• With 0 ≤ α < 1, the Zipf demand mass is approximately uniform across the library, explaining why uniform placement attains the deterministic-demand min-max order.The paper omits the α = 1 case, which requires a different analysis.Source: A. Case 0 ≤α < 1 · p. 21
• Optimizing e_m by minimizing the stated rate upper bound can yield substantial constant rate gains, especially when α is close to 1.The optimization treats e_m as a continuous variable subject to M ≤ e_m ≤ m.Source: A. Case 0 ≤α < 1 · p. 22
• At target rate 20, optimized RLFU-GCC requires M ≈800, versus M ≈2000 for UP-GCC, for m = 50000, n = 50, and α = 0.9.The comparison uses the optimized cutoff e_m from (26).Source: A. Case 0 ≤α < 1 · p. 22, Figure 2 · p. 23

B. Case α > 1

• For the case discussed, the analysis distinguishes three sub-cases according to how the number of users scales with library size: n = ω(mα), n = Θ(mα), and n = o(mα).Source: B. Case α > 1 · p. 23

1) Regime of “very large” number of users:n = ω (mα):

• For n = ω(mα), UP-GCC with em = m achieves order-optimal rate as m → ∞.The result assumes a shared-link network with Zipf demands of parameter α > 1.Source: 1) Regime of “very large” number of… · p. 23

2) Regime of “large” number of users n = Θ (mα):

• For n = Θ(m^alpha), RLFU-GCC achieves an order-optimal rate, with the corresponding e_m choices and achievable rate upper bounds provided in Table I for different system-parameter sub-cases.Source: 2) Regime of “large” number of users n… · pp. 23–24

3) Regime of “small-to-moderate” number of users n = o (mα):

• RLFU-GCC achieves order-optimal rate for n = o(mα), with parameter choices and achievable rate upper bounds specified across sub-regimes in Tables II and III.The theorem covers a shared-link network with library size m, cache capacity M, Zipf parameter α > 1, and m → ∞.Source: 3) Regime of “small-to-moderate”… · p. 25, Table II · p. 25, Table III · p. 26
• For 0 ≤ M < 1, the achievable rate upper bound is 2n^(1/α); this order-optimal rate scaling is achieved without caching, which offers no significant gain over the described non-caching strategy.Source: 3) Regime of “small-to-moderate”… · pp. 25–26
• When n = o(m^(α−1)) and M = o(m), the order-optimal average rate yields an order gain over the min-max order-optimal rate,.Source: 3) Regime of “small-to-moderate”… · pp. 26–27
• For the larger-cache case, LFU with naive multicasting of uncached requests achieves an order gain over the min-max rate, and the multiplicative caching gain is super-linear when α > 2.The source attributes the vanishing rate to LFU covering most requests so that only unpopular requests need serving.Source: 3) Regime of “small-to-moderate”… · p. 27
• As M grows with the user-order fixed, the order-optimal em shifts from n^(1/α) toward m, so placement approaches UP rather than LFU; LFU with naive multicasting is not order-optimal outside M < 1.Across increasing orders of M, the rate scaling changes from sub-linear to linear multiplicative caching gain.Source: 3) Regime of “small-to-moderate”… · pp. 27–28

C. Remark

• For constant library size and Zipf demands with α ≥ 0, UP-GCC is order-optimal with a gap guarantee for arbitrarily small ε > 0 independent of m, n, and M.The remark considers the regime n → ∞ with m constant.Source: C. Remark · p. 28

VI. DISCUSSIONS AND SIMULATION RESULTS

• Under Zipf demands, RLFU-GCC, RLFU-CIC, RAP-GCC, and RAP-CIC achieve order-optimal rates; for this problem, GCC and CIC suffice despite general limits of graph coloring.The delivery phase is an index-coding problem once cache placement is fixed.Source: §VI · p. 28
• For m = 3, M = 1, and q = [0.7, 0.21, 0.09], the optimized caching distribution shifts from most-popular-file caching at n = 3 toward uniform caching at n = 15.The example evaluates n = 3, 5, 10, and 15; the optimized distribution need not equal q.Source: §VI · pp. 28–29, Figure 3 · p. 29
• As user count grows, the aggregate probability that a file is requested at least once flattens, so caching distributions flatten to balance local caching and multicast gains.The paper notes that optimized p tilde follows the same LFU-to-uniform trend, though constrained to a step function.Source: §VI · p. 29
• Numerical minimization of the caching-distribution bound yields RAP-GCC performance improvement over the compared RLFU-GCC configurations, while the optimization is non-convex.The paper suggests brute-force search or branch-and-bound to find good caching distributions.Source: §VI · pp. 28–29, Figure 4 · p. 30
• With M = 1.5 and n = 20, grouping files for separate delivery yields expected rate 1.5, while RLFU-GCC with uniform caching and GCC over all requested packets yields 0.5.The comparison illustrates the cost of missed coding opportunities when subsets are handled separately.Source: §VI · p. 30
• Across the simulated settings, RLFU-GCC significantly outperforms LFU-NM and the reference scheme, consistent with the paper’s scaling-law analysis.The simulations vary n ∈ {50, 500, 5000}, m ∈ {500, 5000}, and α ∈ {0.6, 1.6}.Source: §VI · p. 31, Figure 5 · p. 31, Figure 6 · p. 32
• At α = 1.6, m = 500, n = 5000, and M = 20, RLFU-GCC improves expected rate by 5× over the reference scheme and 8× over LFU-NM.Here M is 4% of the library; the comparison appears in Fig. 6(d).Source: §VI · p. 31, Figure 6 · p. 32

VII. CONCLUSIONS

• The paper formalizes per-user rate averaged over random demands and analyzes random fractional caching with CIC; polynomial-time GCC colors a conflict graph of requested packets.Source: §VII · p. 33
• RAP optimizes the caching distribution, while RLFU uses uniform caching probability through an optimized file-index cutoff and caches no packets beyond it.Source: §VII · pp. 33–34
• RLFU-GCC is order-optimal for Zipf demands: its achievable rate is within a constant factor of the best rate asymptotically, including the stated fixed-m, growing-n case.The result follows by comparing the achievable rate with a general rate lower bound.Source: §VII · p. 34
• The paper assesses RAP-CIC against unicast or naive multicasting, LFU with naive multicasting, and a scheme from [20] that separately codes groups of similarly demanded files.The groups’ file probabilities differ by at most a factor of two.Source: §VII · p. 34
• For Zipf demands, caching can be useless in some regimes and yield multiplicative gains in others, with gains linear or nonlinear in M depending on α.The paper characterizes the system-parameter regions for these behaviors.Source: §VII · p. 34
• In some multiplicative-gain regimes, order-optimal RAP-CIC converges to LFU with naive multicasting; elsewhere, order-optimality requires cooperative fractional caching and index coding.Source: §VII · p. 34

APPENDIX A

• Algorithm 1’s independent sets are counted by user labels, with each labeled user requiring a requested packet cached by the other users in that label.The proof enumerates possible user labels and bounds the number of generated independent sets for each label.Source: Appendix A · p. 35
• As B grows, per-file counts concentrate around g_l(f), and the resulting bound yields Theorem 1 through probabilities identified as ρ_f,l.The proof uses the limiting count and the probability that f maximizes g_l over the random demand subset.Source: Appendix A · pp. 38, 40

APPENDIX B

• For p = ep, Appendix B applies Theorem 1 and uses Jensen’s inequality and E[N_em] = n P_em in its bound.Source: Appendix B · p. 40

APPENDIX C

• The optimal rate is non-increasing in the number of users, since a scheme for n users is admissible for any n′ < n users.The proof can add virtual users with i.i.d. demands to the reduced system and use the n-user code.Source: Appendix C · p. 40
• The converse lower-bounds any scheme using a genie-aided system, then an ensemble of reduced systems with binomial user counts, smaller libraries, and uniform demands.The ensemble average is further lower-bounded using a bound for arbitrary demands.Source: Appendix C · p. 41
• A genie makes the original optimal rate at least the genie-aided rate, whose remaining requests are uniform over a reduced library of size ℓ.The genie removes some users from service; the remaining system can be compared with one having uniform demands over ℓ files.Source: Appendix C · pp. 41–42
• The converse lower-bounds service-count and distinct-file event probabilities using self-bounding concentration, including for the dependent indicators defining the distinct-file count.The number of users requiring service is binomial with mean nℓqℓ; the distinct-file count is a sum of binary indicators, so the self-bounding lemma applies despite their dependence.Source: Appendix C · pp. 43–44
• Maximizing the derived lower bound over ℓ, r, and ez yields equation (19) in Theorem 2.The bound is R*(n,m,M,q) ≥ P1(ℓ,r)P2(ℓ,r,ez) max over z∈{1,...,⌈min{ez,r}⌉} of (z − zM/⌊ℓ/z⌋).Source: Appendix C · pp. 44–45

APPENDIX D

• The Appendix D analysis compares Rlb(n, m, M, q) with Rub(n, m, M, q, em), choosing scheme parameters by regime while taking δ and σ as system-independent constants.The value of z is determined according to m, n, and M.Source: Appendix D · p. 45
• The Appendix D proof ignores non-integer effects when z or ⌈ez⌉ diverges as m → ∞.Source: Appendix D · p. 45

A. Region of n = ω(m)

• For n = ω(m), the proof divides memory into subregions and derives a converse lower bound by maximizing over z before comparing it with the achievable rate.The memory subcases are illustrated in Fig. 8; the displayed lower bound is proportional to the maximum of z − zM/⌊ℓ/z⌋ over the specified z range.Source: Appendix D · p. 47, Figure 8 · p. 47, A. Region of n = ω(m) · p. 48

B. Region of n = O(m)

• For n = O(m), the proof treats memory subregions separately and distinguishes whether n m^δ(1−α) is at least 1 when comparing converse and achievable rates.The passages indicate separate parameter choices and rate comparisons across these cases, but do not provide the complete resulting expressions.Source: B. Region of n = O(m) · pp. 49–50

APPENDIX E

• When Theorem 5 has n = ρm^α with ρ ≥ 1, the converse and order-optimality arguments follow the procedure for n = ω(m^α), with em set to m.Source: Appendix E · pp. 51–52
• For 0 < ρ < 1 in Appendix E, the proof treats the memory ranges 0 ≤ M < 1 and 1 ≤ M < m^α separately.The corresponding memory subcases are illustrated in Fig. 10.Source: Appendix E · p. 52, Figure 10 · p. 52
• Appendix E likewise ignores non-integer effects when z or ⌈min{ez, r}⌉ diverges as m → ∞.Source: Appendix E · p. 52

A. Region of 0 ≤M < 1

• The converse proofs apply Theorem 2 with selected parameters, then evaluate its terms to obtain lower bounds.The parameter choices include constants δ and σ in (0, 1), subject to ez ≤ r.Source: A. Region of 0 ≤M < 1 · pp. 53, 55, 56
• The derived bound establishes order-optimality of the achievable expected rate, with constant parameters chosen to keep its bound uniform in n, m, and M.The passages note that suitable σ and δ values make the right-hand side uniformly bounded.Source: A. Region of 0 ≤M < 1 · p. 55
• The converse analysis shows that RLFU-GCC achieves an order-optimal expected rate.The proof computes the converse using Theorem 2 and then concludes order-optimality for RLFU-GCC.Source: A. Region of 0 ≤M < 1 · pp. 55, 58

Regime scope

• The appendix considers 0 ≤ M < 1 and 1 ≤ M < m^α, with further subregions for the latter range.The setting assumes n,m → ∞ and n = o(m^α).Source: Appendix F · p. 61

Small-memory regime

• For 0 ≤ M < 1, caching cannot affect the expected-rate order: its gain is at most additive.The proof establishes this for the small-enough-M regime.Source: Appendix F · pp. 62–63

RLFU-GCC

• For the analyzed memory subregimes, converse bounds establish order-optimality of the achievable expected rate for RLFU-GCC.The proof treats distinct cases including M = o(m) and M = Θ(m).Source: Appendix F · pp. 66, 68

RLFU and RAP

• For M = o(m) and M = Θ(m), the converse establishes order-optimality of the achievable expected rate for RLFU and RAP.The Θ(m) analysis further distinguishes cases according to the relationship between m and M.Source: Appendix F · pp. 69, 71

RLFU-GCC with em = m

• For RLFU-GCC with em = m, the proof separates cases n m^(α−1) = ω(1) and n m^(α−1) = Θ(1).This part begins the converse analysis for these cases but does not include its concluding order-optimality statement.Source: Appendix F · p. 73

• For n m^(alpha-1)=Theta(1), the appendix computes the converse using Theorem 2 and divides the analysis into further regions.Source: Appendix F · pp. 75–76
• The further regional analysis treats both n m^(alpha-1) ≤ 1 and m^(alpha-1) > 1 when bounding terms in the converse.Source: Appendix F · pp. 76–77
• The achievable expected rate of RLFU and RAP is order-optimal, with the converse argument using a lower bound on z.Source: Appendix F · p. 78

APPENDIX G

• Appendix G is the proof of Table III in Theorem 6.Source: Appendix G · p. 78
• RLFU is order-optimal when n = o(m^α) and memory scales as M = κn for a positive constant κ.The proof focuses on the asymptotic regime n → ∞.Source: Appendix G · p. 78
• The proof handles κ ≥ 1 and κ < 1 as separate cases, with the memory subregions illustrated in Fig. 13.The subregions are treated separately in the following proofs.Source: Appendix G · p. 78

A. Region of κ < 1

• The κ < 1 region is analyzed separately for M = o(m) and M = Θ(m).The text indicates that the conditions distinguishing these cases are determined later.Source: A. Region of κ < 1 · p. 78

1) When M = o(m):

• For M = o(m), the converse analysis applies Theorem 2 and derives a lower bound on Rlb(n, m, M, q).The displayed lower-bound expression depends on P1, P2, and a maximization over z, but its full formula is not preserved in the passage.Source: 1) When M = o(m) · pp. 79, 81
• The analysis also derives an upper bound Rub(n, m, M, q, em) and states that the achievable expected rate is order-optimal for a specified em choice.The extracted passages do not preserve the full choice of em.Source: 1) When M = o(m) · p. 81
• A further converse uses the second term of Theorem 2 to bound Rub(n, m, M, q, em) in another M = o(m) subcase.The passage gives the method and bound label but not the complete bound formula.Source: 1) When M = o(m) · p. 82
• For one scaling regime, the proof divides the analysis into further cases using a threshold on m/M and then a threshold involving κ.The extracted threshold expressions are incomplete, so their exact values cannot be stated reliably.Source: 1) When M = o(m) · p. 83
• For the regime with an arbitrary constant µ > 2, the analysis distinguishes 1/κ1 > µ from 1/κ1 ≤ µ and constrains c to keep ℓ < m.The passage specifies 1 < c < µ in the first branch and 1 < c < 2 in the second.Source: 1) When M = o(m) · p. 83
• The section states that it derives a converse and the order-optimality of UP-GCC in the regime under consideration.In a separate branch, it sets em = m and gives another converse result, with the extracted bound expression incomplete.Source: 1) When M = o(m) · pp. 83–84

B. Region of κ ≥1

• For κ ≥ 1, the analysis distinguishes M = o(m) from M = Θ(m) and computes the converse using the second term of Theorem 2.The M = Θ(m) case is further split according to whether m/M = 1/κ₁ is above or at most 2.Source: B. Region of κ ≥1 · p. 85, 2) When M = Θ(m) · p. 86

2) When M = Θ(m)

• RLFU-GCC with e_m = M is order optimal when M = Θ(m), for both m/M = 1/κ₁ > 2 and m/M = 1/κ₁ ≤ 2.In the first case, the proof constrains c to 1 < c < 2 to ensure ℓ < m.Source: 2) When M = Θ(m) · pp. 86–87

APPENDIX H

• The Corollary 1 proof follows the procedure for Theorem 3, while its converse is evaluated term by term using Lemma 1.The resulting lower bound maximizes over z in a specified range; the proof then specializes z to max{(1 − ϵ)m, 1}.Source: Appendix H · pp. 89–90
• The Appendix H argument combines the bounds from (279) and (288) to relate R_ub and R_lb.The supplied passage also states a bound involving m, but its extracted formula is incomplete.Source: Appendix H · p. 90

B. When 1

• For m < 3, the passage sets z = 1 and uses (287); other displayed derivations combine (279) with (290) and (292), while the excerpt does not show their resulting formulas.Source: B. When 1 · p. 90