Exercises

$R_{\text{unc}} = 5 \cdot (1 - 2/10) = 5 \cdot 0.8 = 4$ files.

$R_{\text{MAN}} = 5 \cdot 0.8 / (1 + 5 \cdot 2/10) = 4/2 = 2$ files. The gain factor is $1 + KM/N = 2$.

The server can always unicast one file per user, requiring at most $K$ file units on the shared link.

If each user caches the entire library, every requested file is a hit; no delivery is needed.

$h = \sum_{n=1}^{M} 1/N = M/N = 0.1$.

$h = H_{M,1} / H_{N,1} \approx \ln(100)/\ln(1000) = \log_{10} 100 / \log_{10} 1000 \approx 0.67$.

The placement phase populates caches during off-peak periods, when user requests have not yet been issued. The server does not know $\mathbf{d}$ at placement time. A scheme whose placement depended on $\mathbf{d}$ would require the server to anticipate every possible demand pattern, which defeats the purpose of caching — the whole point is to pre-position content robustly.

(a) $t = 100 \cdot 10 / 200 = 5$. Each XOR message serves $6$ users. (b) $t = 1000 \cdot 100 / 10000 = 10$. Each XOR message serves $11$ users.

$R_{\text{unc}} = 9$. $R_{\text{MAN}} = 9/(1+1) = 4.5$. Ratio: 2.

$R_{\text{unc}} = 9000$. $R_{\text{MAN}} = 9000/(1001) \approx 8.99$. Ratio: $\approx 1001$.

$R_{\text{unc}}/R_{\text{MAN}} = 1 + K\mu \to \infty$. The gap scales linearly in $K$ — the exact statement of why coded caching matters at CDN scale.

One library refresh per day: $K \cdot M = 100 \cdot 100 = 10{,}000$ files broadcast during off-peak. This costs the link $KM = 10^4$ file units per day, but off-peak capacity is not the bottleneck.

Peak period: $T_p = 8640$ s. 144 rounds. Per round: $R_{\text{unc}} = K(1-M/N) = 90$ files. Total peak-period traffic: $144 \cdot 90 = 12{,}960$ file-units on the bottleneck link.

MAN: per round, $R = 90/11 \approx 8.2$ files. Total peak traffic: $144 \cdot 8.2 = 1180$ file-units. MAN reduces peak-bottleneck traffic by a factor of $\sim 11$, but placement traffic is the same. This is why the engineering metric is peak load, not total traffic.

Because popularity caching places the same $M$ files in every user's cache (namely, $\{W_1, \ldots, W_M\}$), the worst case is when every user requests a distinct uncached file, say $d_k = M + k$ for $k = 1, \ldots, K$. This is feasible whenever $K \leq N - M$.

Under uncoded delivery, each miss costs one full unicast. All $K$ requests miss, so $R = K(1 - M/N)$ when $M$ of the $N$ files are cached but the $K$ requested files are among the $N - M$ uncached ones. For this demand, the "$-M/N$" local caching gain in the formula reduces to a gain of $0$ — caching did not help at all.

Popularity caching optimizes the expected rate under a prior distribution, but provides no worst-case robustness. Coded caching (Ch 2) has provably better worst-case performance.

Each user independently misses with probability $1 - H_{M,\alpha}/ H_{N,\alpha}$, and each miss costs one unicast. Summing over users: $R_{\text{exp}} = K(1 - H_{M,\alpha}/H_{N,\alpha})$.

As $\alpha \to 0$, $H_{K,\alpha} \to K$. Then $H_{M,\alpha}/H_{N,\alpha} \to M/N$, and $R_{\text{exp}} \to K(1 - M/N) = R_{\text{unc,worst}}$. So uniform demand is the worst case for popularity caching — there is nothing to exploit.

Worst-case: all users request distinct files. User $k$'s rate is at least $(1 - M_k/N)$ (the local miss rate). Total: $R \geq \sum_k (1 - M_k/N) = K - \sum_k M_k/N = K - KM/N = K(1-M/N)$.

Under uncoded delivery, only local gains count, and the total local gain is determined by the average cache size $M$, not by its distribution. Coded caching (Chapter 13) breaks this — heterogeneous caches do help coded delivery, because coded messages can serve users with different caches differently.

User 1 caches $(a_1, b_1)$ (the 'user-1-indexed' halves of each file). User 2 caches $(a_2, b_2)$. Each cache holds $F = 2$ bits — exactly the allowed budget $M \cdot F/F = 1$ file.

User 1 wants $W_1 = (a_1, a_2)$; user 1 already has $a_1$, needs $a_2$. User 2 wants $W_2 = (b_1, b_2)$; user 2 already has $b_2$, needs $b_1$. Server sends one XOR bit: $a_2 \oplus b_1$. User 1 recovers $a_2 = (a_2 \oplus b_1) \oplus b_1$ using the $b_1$ in its cache; user 2 recovers $b_1$ similarly. Total: 1 bit = $1/2$ file. Match.

The same placement works for the other demand patterns; worst-case rate is $1/2$ file. This is the $K = 2$ MAN scheme in miniature.

Fix $s$ users, say $\{1, \ldots, s\}$. Consider $\lfloor N/s \rfloor$ demand vectors, each requesting $s$ distinct files from the library, such that the union of requested files covers a subset $\mathcal{F}$ with $|\mathcal{F}| \geq \lfloor N/s \rfloor \cdot s$.

The caches $\mathcal{Z}_{1}, \ldots, \mathcal{Z}_{s}$ plus the delivery messages across these $\lfloor N/s \rfloor$ rounds must determine all files in $\mathcal{F}$, of total size $\lfloor N/s \rfloor \cdot s \cdot F$ bits.

$\mathrm{H}(\mathcal{Z}_{1}, \ldots, \mathcal{Z}_{s}) \leq s M F$. The total delivery bit budget is $\lfloor N/s \rfloor \cdot R F$. Together they must support $\lfloor N/s \rfloor s F$ bits of file: $$s M F + \lfloor N/s \rfloor \cdot R F \geq \lfloor N/s \rfloor s F.$$ Rearranging: $R \geq s - sM/\lfloor N/s\rfloor$. $\blacksquare$

$R_{\text{MAN}} = 100 \cdot 0.9 / (1 + 10) = 90/11 \approx 8.18$.

$\zeta(1.5) \approx 2.612$; $H_{100,1.5} \approx 2.44$; $H_{1000,1.5} \approx 2.56$. So $h \approx 0.953$. $R_{\text{pop,exp}} = 100 \cdot (1 - 0.953) = 4.7$.

Under heavy Zipf, popularity's expected rate (4.7) beats MAN's worst-case rate (8.18). This is not a contradiction: MAN is worst-case optimal, but most demand vectors are not worst case. The right comparison is average-case MAN vs. popularity, which is subtle and chapter-13 material. The broader lesson: the "right" scheme depends on whether you want worst-case robustness (MAN) or average-case efficiency (popularity, or a decentralized hybrid).

Let $\pi_n$ be the steady-state popularity of file $n$ in a library that turns over at rate $\lambda$. If placement refreshes at rate $\mu$ and demand is i.i.d. $\pi$, the cache always contains the most popular $M$ files up to a lag of $1/\mu$.

$R_{\text{eff}} = K(1 - h_{\text{eff}})$ where $h_{\text{eff}} = \sum_{n=1}^M \pi_n - O(\lambda / \mu)$. The last term accounts for popular files that have changed but not yet been refreshed into caches.

Placement traffic: $\mu K M F$ per round. Delivery traffic: $K(1 - h_{\text{eff}}) F$ per round. Minimize the sum: $$\mu^* = \sqrt{\lambda K / (KM)} = \sqrt{\lambda / M}.$$ Real CDNs run refresh windows of minutes to hours, matching this optimum for typical libraries.

For a coded-caching system, the refresh overhead is even higher — the $\binom{K}{t}$ subfiles must all be kept consistent. This is why production CDNs still use popularity caching: the operational complexity of coded refresh exceeds the delivery savings for high-churn libraries. The research question is: can we design a coded scheme whose subfiles are stable under library turnover? Chapter 20 (online coded caching) treats this.

This question is open in full generality. For two-class demand (popular + unpopular), characterization was obtained by Hachem et al. 2017. For general Zipf demand, only order-optimal schemes are known (Zhang–Pedarsani–Ji 2015, Ji–Tulino–Llorca–Caire 2017). See Chapter 13 for the state of the art.

Coded caching's gain comes from multicasting across users with different demands. Concentrated popularity reduces the diversity of demands, narrowing the opportunity for coded gain. But concentrated popularity also makes uncoded caching better. The crossover is non-trivial and depends on $K, M, N, P$ jointly.

Open problem: characterize $R^*(M, P)$ exactly. Progress has been made in the two-extreme case ($P$ uniform, $P$ delta) and scaling regimes. This is an excellent PhD project for a student who enjoys both combinatorics and optimization.