Chapter Summary

Chapter Summary

Key Points

• 1.

  Non-uniform (Zipf) demand is the realistic case. Real CDN workloads have popularity distributions with exponent $\alpha \in [0.6, 1.2]$ typical for video/web. Higher $\alpha$ means more concentration on popular files.

• 2.

  Popularity caching vs MAN. Popularity caching achieves expected rate $K(1 - H_{M,\alpha}/H_{N,\alpha})$; MAN achieves worst-case $K(1-M/N)/(1+KM/N)$. At high $\alpha$ popularity wins in expectation; at low $\alpha$ MAN wins. Hybrid schemes bridge both.

• 3.

  Decentralized coded caching (MN 2015). Each user independently caches random bits with probability $\mu$. No coordination required. Rate asymptotically matches centralized MAN as $K \to \infty$. This is the deployable coded-caching scheme.

• 4.

  Heterogeneous caches. When users have different cache sizes $\{M_k\}$, the aggregate $\sum_k M_k$ drives the caching gain, not the minimum. Rich-cache users subsidize poor-cache users via coded multicast. Factor-of-2 gap to homogeneous at average.

• 5.

  Ji-Tulino-Llorca-Caire (2017) order-optimality. Under Zipf-$\alpha$, the optimal expected rate is $\Theta(K(1-\mu_\text{eff})/(1+K\mu_\text{eff}))$ with $\mu_\text{eff} = \mu^{1-\alpha}$. The effective caching gain far exceeds naive $\mu$ analysis.

• 6.

  Popularity-weighted decentralized placement. Popular files cached with higher probability per user; unpopular files with lower. Order-optimal for Zipf; simple to implement; no central coordinator.

• 7.

  Practical CDN implications. For typical video workloads ($\alpha \approx 0.8$, $\mu = 0.1$), effective caching gain can be 5-10× the naive value. Coded caching is highly effective for real content libraries — not just a theoretical curiosity.