Ferkans — Interactive Telecom Tutor

The Missing Ingredient

Popularity caching is optimal within the uncoded-caching regime, but we are about to show that the uncoded regime itself leaves money on the table. The key observation is that popularity caching does nothing to exploit the multiplicity of users. If $K$ users request $K$ different files, the server must unicast $K$ separate messages — one per user — regardless of how much each user has cached. Information-theoretically, this is wasteful.

This section quantifies what uncoded caching cannot do, setting up the gap that coded caching will close.

Theorem: Worst-Case Rate Under Uncoded Caching

Under any uncoded caching strategy with per-user cache size $M$ , the worst-case delivery rate over all demand vectors $\mathbf{d} \in [N]^K$ satisfies $R_{\text{unc}}(M) \;\geq\; K\left(1 - \frac{M}{N}\right).$ This bound is achieved with equality by popularity caching when $K \leq N$ and demands are distinct.

Consider the worst case where every user requests a different file. Any single user caches at most a fraction $M/N$ of its own requested file (by symmetry, any file it could request). Hence each user must receive at least $(1 - M/N)$ files' worth of data from the server. With $K$ users, the total load is at least $K(1 - M/N)$ . Caching saves each user a fraction $M/N$ of its file — nothing more.

Proof

Consider worst-case demands

Choose demands so that all $K$ users request distinct files, which is possible whenever $K \leq N$ . Denote these distinct files as $W_{d_1}, \ldots, W_{d_K}$ .

Lower-bound each user's reception

Under uncoded delivery, the message sent to user $k$ must contain enough information for user $k$ to recover all $F$ bits of $W_{d_k}$ . The cache $\mathcal{Z}_{k}$ covers at most $M$ files' worth of content, so the fraction of $W_{d_k}$ that user $k$ does not already have is at least $(1 - M/N)$ on average across all choices of $d_k$ consistent with a symmetric placement.

Sum over users

Because uncoded delivery cannot multicast useful bits to more than one user (different users want different files), the total rate is at least the sum of individual rates: $R_{\text{unc}} \;\geq\; \sum_{k=1}^K \left(1 - \frac{M}{N}\right) \;=\; K\left(1 - \frac{M}{N}\right).$ $\blacksquare$

Example: A Concrete Number

Netflix-sized thought experiment: $N = 10^5$ movies on offer, $K = 10^6$ simultaneous users during peak hours, each with a local cache of $M = 10^4$ movies (10% of the library). What is the peak-hour shared-link load under popularity caching and worst-case demands (say, a new blockbuster release spreads demand across 1000 different titles)?

Solution

Apply the worst-case bound

$R_{\text{unc}}(M) \geq K(1 - M/N) = 10^6 \cdot (1 - 0.1) = 9 \times 10^5$ movies/delivery round. Caching saves only 10% of peak load.

Preview the coded result

The MAN bound from Chapter 2 gives $R \leq K(1 - M/N)/(1 + KM/N) = 9 \times 10^5 / (1 + 10^5) \approx 9$ movies/delivery round. A factor of $10^5$ improvement — if the theory can be realized in a system. The rest of this book is about both the realization and the subtleties hidden in this "if."

Identify the key gain

The factor $(1 + KM/N)^{-1}$ is exactly the coded multicasting gain. For any caching system with enough users ( $K$ large), popularity caching leaves most of the potential savings untouched. This is the operational meaning of the coded caching gain.

Multiplicative vs. Additive Gains

Caching provides two conceptually distinct gains:

Local caching gain ( $1 - M/N$ ). This is the classical hit-rate benefit — each user individually avoids fetching what it already has. Available to any caching system; captured fully by popularity caching.
Coded multicasting gain ( $1 + KM/N$ ). This is the combinatorial gain from exploiting coincidences across users' caches. It requires both combinatorial placement and coded delivery. Invisible to popularity caching.

The two gains multiply: under the MAN scheme, $R \;=\; K\, \underbrace{(1 - \mu)}_{\text{local}} \cdot \underbrace{\frac{1}{1 + K \mu}}_{\text{coded}}.$ As we scale up the network ( $K \to \infty$ at fixed $M/N$ ), the local gain is bounded but the coded gain grows unboundedly. This is why coded caching matters at scale.

Caching Loses Traction as Libraries Grow

With fixed absolute cache size $M$ and Zipf-distributed demand, the hit ratio collapses as the library $N$ grows. This is the fundamental limitation of popularity caching in an era where content libraries grow faster than edge storage. Coded caching reframes the problem: the figure of merit is the ratio $M/ N$ , not the absolute cache size.

Parameters

Absolute cache size M (files)50

Zipf exponent α0.8

Common Mistake: Uncoded Caching Scales Linearly in K

Mistake:

Thinking that adding more users to a shared-link network with popularity caching improves per-user delivery cost (via "economies of scale").

Correction:

Exactly the opposite: under popularity caching, the shared-link load is $K(1 - h(M))$ — linear in $K$ . Adding users linearly degrades the per-round link usage. Coded caching turns this linear growth into a bounded one: for fixed memory ratio $M/N$ , the rate $R_{\text{MAN}}$ approaches $(1-M/N)/(M/N)$ as $K \to \infty$ . The gain is unbounded in $K$ , which is the killer feature of coded caching at CDN scale.

Historical Note: Web Caching and the Zipf Assumption

1998–2014

The field of web caching in the 1990s–2000s was built on the assumption that web requests follow a Zipf distribution. Breslau et al.'s 1999 study of web traffic was seminal: it found Zipf exponents between 0.6 and 0.8 for page requests. Video streaming a decade later confirmed similar exponents (0.6–1.2 depending on the platform). These numbers are good for popularity caching but not so good: even $\alpha = 1.0$ leaves substantial demand in the long tail, where popularity caching cannot reach.

The industry's response was to make caches bigger and distribute them more widely. The Caire group's response, starting in 2013–2014, was to rethink the problem at the information-theoretic level. Both responses have merit; this book develops the latter.

Quick Check

Under uncoded caching with $K = 100$ users, $N = 1000$ files, $M = 100$ files, and worst-case distinct demands, what is the minimum achievable shared-link delivery rate (in file units)?

1

10

90

100