Prerequisites & Notation

Before You Begin

This chapter generalizes Chapter 2's MAN scheme to non-uniform demand distributions and heterogeneous cache sizes — the realistic world of CDN design. Prerequisites: MAN, D2D scaling, and basic probability over Zipf distributions.

MAN coded caching and memory-load tradeoff (Ch 2)(Review ch02)
Self-check: Can you state the MAN rate and the coded caching gain parameter $t$ ?
Fundamental limits and YMA '18 (Ch 3)(Review ch03)
Self-check: Under what assumptions is the MAN scheme tight?
D2D caching + Ji-Caire-Molisch scaling (Ch 10)(Review ch10)
Self-check: Why is the scaling $\Theta(M/N)$ independent of $n$ ?
Zipf distribution(Review ch01)
Self-check: Can you state $P_n \propto n^{-\alpha}$ and the generalized harmonic number?
Expected rate computation
Self-check: Can you compute $\mathbb{E}[R]$ under a demand distribution?
Basic convex optimization
Self-check: Can you solve a simple resource allocation with Lagrangian?

Notation for This Chapter

Symbols for non-uniform demand and heterogeneous caches.

Symbol	Meaning	Introduced
$P_n, n \in [N]$	Popularity distribution: $\Pr(d_k = n) = P_n$	s01
$\alpha$	Zipf exponent; $\alpha = 0$ uniform, $\alpha > 0$ concentrated	s01
$h(M, P)$	Hit probability under popularity caching with cache $M$	s01
$M_{k}$	Cache size of user $k$ (heterogeneous setting)	s03
$\bar{M}$	Average cache size: $\bar M = (1/K) \sum_k M_k$	s03
$R^*_{\text{avg}}$	Expected worst-case rate under non-uniform demand	s01
$H_{M,\alpha}$	Generalized harmonic number $H_{M,\alpha} = \sum_{n=1}^M n^{-\alpha}$	s01

← Ch 12 Non-Uniform Demand and Zipf Popularity