Ferkans — Interactive Telecom Tutor

Beyond Random Placement

Under Zipf demand, random uniform placement is suboptimal: popular files should be cached more often than unpopular ones. But pure popularity caching has its own issue: no coded-multicast opportunity because everyone caches the same files. The sweet spot is a hybrid placement that combines popularity bias with sufficient randomness for MAN-style delivery.

This section derives the optimal placement parameters for Zipf demand and characterizes the resulting rate. The Ji-Tulino- Llorca-Caire result shows that the optimized placement is order-optimal for the expected-rate setting.

Theorem: Order-Optimal Rate for Zipf Demand

Under Zipf- $\alpha$ demand with $\alpha \in (0, 1)$ , the optimal expected rate for the shared-link coded caching problem satisfies $R^*_\text{exp}(M, \alpha) \;=\; \Theta\!\left(K \cdot \frac{1 - (M/N)^{1-\alpha}}{1 + K (M/N)^{1-\alpha}}\right).$ That is, the Zipf concentration $\alpha$ shifts the effective memory ratio from $\mu$ to $\mu^{1-\alpha}$ — caching popular files buys more than its memory weight.

Under Zipf, the top fraction $\mu$ of files by popularity covers $\mu^{1-\alpha}$ of the probability mass. So an $M$ -file cache covers a $\mu^{1-\alpha}$ -fraction of demand — more than $\mu$ . The MAN-like formula $K(1 - \mu_{\text{eff}})/(1 + K\mu_{\text{eff}})$ with effective $\mu_{\text{eff}} = \mu^{1-\alpha}$ achieves the claimed rate.

Proof

Popularity shift

Under Zipf- $\alpha$ , $H_{M,\alpha}/H_{N,\alpha} \approx (M/N)^{1-\alpha}$ for large $N$ . Hit probability: $(M/N)^{1-\alpha}$ .

Effective memory ratio

Set $\mu_\text{eff} = (M/N)^{1-\alpha}$ . Reinterpret the problem: under uniform demand with effective memory $M_\text{eff} = N \mu_\text{eff}$ , apply MAN analysis.

Rate

$R = K(1 - \mu_\text{eff})/(1 + K\mu_\text{eff})$ . Plugging in: stated formula. Achievability via popularity-weighted MAN placement; matching converse via Yu-Maddah-Ali-Avestimehr '18 converse adapted to Zipf. $\blacksquare$

Order-optimality

The scaling is tight up to constants. Higher-order refinements (Jin-Cui-Liu-Caire 2017, Zhang-Pedarsani-Ji 2015) close specific regimes.

Popularity-Weighted Random Placement

Complexity: Placement:

O(KN)

coin flips. Total storage per user: approximately

M

files with high probability (Hoeffding concentration).

Input: Library

\{W_1, \ldots, W_N\}

ordered by popularity;

Zipf exponent

\alpha

; memory ratio

\mu

; users

1, \ldots, K

.

Output: Caches

\mathcal{Z}_1, \ldots, \mathcal{Z}_K

.

1. Compute file caching probability:

q_n = \min(1, \mu \cdot N^{1-\alpha} / H_{N,\alpha} \cdot n^{-\alpha})

.

2. for each user

k

do

3.

\quad

for each file

n \in [N]

do

4.

\quad\quad

User

k

caches file

n

independently with probability

q_n

.

5.

\quad

end for

6. end for

7. return

(\mathcal{Z}_1, \ldots, \mathcal{Z}_K)

.

This is the "soft popularity" placement: popular files cached by more users, but each user's cache is randomized. Combines the hit- rate benefit of popularity with the coded-multicast opportunity of MAN. Asymptotically order-optimal for Zipf- $\alpha$ demand.

Example: Zipf Placement Design

For $\alpha = 0.8$ , $N = 1000$ , $K = 100$ , $M = 100$ , derive the optimal placement and expected rate.

Solution

Effective memory

$\mu = M/N = 0.1$ . $\mu_\text{eff} = \mu^{1 - \alpha} = 0.1^{0.2} \approx 0.63$ . Much higher than $\mu$ itself.

Effective caching gain

$t_\text{eff} = K \mu_\text{eff} = 100 \cdot 0.63 = 63$ . Very high — under Zipf, the effective multicast opportunity is much larger than naive $\mu$ suggests.

Expected rate

$R \approx K(1 - \mu_\text{eff})/(1 + t_\text{eff}) = 100 \cdot 0.37/64 \approx 0.58$ files/round. Compare: uniform-demand MAN at $\mu = 0.1$ : $R = 100 \cdot 0.9/11 = 8.18$ . Zipf gives ~14× better rate for the same cache budget.

Conclusion

Zipf concentration is a massive practical win for coded caching. Popular-content-heavy workloads (YouTube, etc.) yield dramatically lower delivery rates than uniform analysis would suggest.

Key Takeaway

Under Zipf- $\alpha$ demand, the effective memory ratio is $\mu^{1-\alpha}$ , not $\mu$ . Popular files amplify the caching gain. The MAN-like rate formula applies with this effective memory; for typical $\alpha \approx 0.8$ , the effective caching gain $t_\text{eff}$ can be 5-10× the naive value. This is the practical answer to why coded caching is highly effective for video/media CDNs.

Open Problem: Exact Non-Uniform Rate

The Ji-Tulino-Llorca-Caire result is order-optimal: it gives the correct scaling in $K, N, M, \alpha$ . But the exact constant-factor rate is not known. Specifically, for Zipf demand, the question of whether a particular scheme is exactly optimal (like YMA '18 is for uniform demand) remains open.

Progress:

Zhang-Pedarsani-Ji (2015): refined constants.
Jin-Cui-Liu-Caire (2017): closed gap for specific regimes.
Niesen-Maddah-Ali (2017): worst-case Zipf analysis.

A tight characterization for arbitrary Zipf- $\alpha$ remains a research topic. The CommIT group has published several refinements but the problem is not fully solved.

Historical Note: The Non-Uniform Demand Research Arc

2014–2020

The coded-caching community's evolving understanding of non-uniform demand:

2014: Maddah-Ali-Niesen's MAN scheme assumes uniform demand. The " $\Theta(M/N)$ story" is worst-case optimal.
2015: Pedarsani-Maddah-Ali-Niesen — first analysis of MAN under Zipf demand. Shows popularity can hurt.
2015-2016: Multiple extensions: Zhang-Pedarsani-Ji, Ji-Caire- Molisch (D2D). Order-optimal bounds.
2017: Ji-Tulino-Llorca-Caire — comprehensive Zipf analysis. Order-optimal achievable scheme; exact rate open.
2018: Jin-Cui-Liu-Caire — structural refinements. Heterogeneous caches (Sengupta-Tandon-Clancy).
2020+: Privacy-aware non-uniform analysis (Wan-Caire).

The story has become progressively more realistic: from worst-case / uniform to average-case / Zipf to heterogeneous / privacy-constrained. Each step brings the theory closer to practical CDN design.

Placement Optimization for Zipf Demand