Popularity-Based (Uncoded) Caching

The Natural First Answer

Suppose we are asked to cache MM files per user and then serve the users' requests over a shared link. If we ignore coding entirely β€” each user can only hold entire files, and the delivery phase sends uncoded file fragments β€” what is the best we can do?

The answer, long before coded caching was discovered, is to populate every cache with the MM most popular files. Users who happen to request any of those files find them locally, and the server only needs to deliver the remaining (rarer) requests. This is what Akamai, Netflix's Open Connect, and every commercial CDN still do.

We now compute exactly how well popularity caching performs, so that we have a concrete baseline to beat.

Definition:

Popularity Caching (LFU)

Let the demand distribution of each user be Pn=Pr⁑(dk=n)P_n = \Pr(d_k = n), with files ordered so that P1β‰₯P2β‰₯β‹―β‰₯PNP_1 \geq P_2 \geq \cdots \geq P_N. Popularity caching places the ⌊MβŒ‹\lfloor M \rfloor most popular files W1,…,W⌊MβŒ‹W_1, \ldots, W_{\lfloor M \rfloor} in every user's cache. In the delivery phase, the server sends WdkW_{d_k} to each user kk whose requested file is not in the cache (a miss), using unicast transmissions.

Popularity caching is sometimes called least-frequently-used (LFU) placement; the dynamic version, which tracks request frequencies online, reduces to this static rule in the limit of infinite observation time.

Definition:

Cache-Hit Ratio

The cache-hit ratio is the probability that a random user's request is served from its local cache: h(M)β€…β€Šβ‰œβ€…β€Šβˆ‘n=1⌊MβŒ‹Pn.h(M) \;\triangleq\; \sum_{n=1}^{\lfloor M \rfloor} P_n. Under popularity caching, the expected load on the shared link (in file units per delivery round) is E ⁣[R]β€…β€Š=β€…β€ŠKβ‹…(1βˆ’h(M)).\mathbb{E}\!\left[R\right] \;=\; K \cdot (1 - h(M)).

Example: Hit Ratio Under Zipf Demands

Empirical studies of web and streaming traffic show demand follows a Zipf distribution with exponent α∈[0.6,1.2]\alpha \in [0.6, 1.2]: Pnβ€…β€Š=β€…β€Šnβˆ’Ξ±βˆ‘m=1Nmβˆ’Ξ±.P_n \;=\; \frac{n^{-\alpha}}{\sum_{m=1}^{N} m^{-\alpha}}. Compute the cache-hit ratio under popularity caching for N=1000N = 1000, M=100M = 100 (so M/N=0.1M/N = 0.1), and α∈{0,0.5,0.8,1.2}\alpha \in \{0, 0.5, 0.8, 1.2\}.

Solution
Set up the sum

The hit ratio is h=βˆ‘n=1100Pn=H100,Ξ±/H1000,Ξ±h = \sum_{n=1}^{100} P_n = H_{100,\alpha} / H_{1000,\alpha} where HK,Ξ±=βˆ‘n=1Knβˆ’Ξ±H_{K,\alpha} = \sum_{n=1}^{K} n^{-\alpha} is the generalized harmonic number.

Compute for each $\alpha$
  • Ξ±=0\alpha = 0 (uniform): h=100/1000=0.10h = 100/1000 = 0.10.
  • Ξ±=0.5\alpha = 0.5: hβ‰ˆH100,0.5/H1000,0.5β‰ˆ18.6/61.8β‰ˆ0.30h \approx H_{100,0.5} / H_{1000,0.5} \approx 18.6/61.8 \approx 0.30.
  • Ξ±=0.8\alpha = 0.8: hβ‰ˆ0.50h \approx 0.50.
  • Ξ±=1.2\alpha = 1.2: hβ‰ˆ0.78h \approx 0.78.
Interpret

The more concentrated the popularity, the better popularity caching performs. For Ξ±=1.2\alpha = 1.2 β€” aggressive power-law decay seen in video streaming β€” caching 10% of the library catches 78% of requests. For uniform demand, caching 10% catches only 10% of requests. The key dependence is not on the cache size alone, but on the shape of the demand distribution.

Cache-Hit Ratio Under Zipf Demands

Adjust the Zipf exponent Ξ±\alpha and the library size NN. The curve shows the cache-hit ratio h(M/N)h(M/N) for popularity caching. The dashed diagonal is the uniform-demand baseline: caching a fraction M/NM/N of a uniform library yields exactly that fraction in hit ratio. Heavy-tailed demand distributions benefit disproportionately from popularity caching β€” but only at small M/NM/N.

Parameters
0.8

0 = uniform, ~0.8 = video streaming, ~1.2 = news articles

1000

Theorem: Optimality of Popularity Caching Under Uncoded Placement

For the shared-link network with i.i.d. demands following distribution PP, and with the restriction that each cache store whole files only (uncoded placement) and that the delivery phase transmit whole file fragments (uncoded delivery with unicast messages), popularity caching of the ⌊MβŒ‹\lfloor M \rfloor most popular files minimizes the expected delivery rate: E ⁣[Rpop]β€…β€Š=β€…β€ŠK(1βˆ’h(M)).\mathbb{E}\!\left[R_{\text{pop}}\right] \;=\; K (1 - h(M)). No uncoded strategy (even a randomized one) can do strictly better.

Under uncoded placement + uncoded delivery, each user's cache is a "free copy" of MM specific files and every miss costs one unicast transmission. To minimize misses, we must cache the files that are requested most often. This is classical: it's the LFU rule, optimal for static demand distributions under the uncoded-caching restriction.

Proof
Reduce to a set-cover argument

Fix any placement strategy. Without coding, user kk's cache Zk\mathcal{Z}_{k} is a subset SkβŠ†[N]\mathcal{S}_k \subseteq [N] with ∣Sk∣=M|\mathcal{S}_k| = M. The probability of a hit for user kk is Pr⁑(dk∈Sk)=βˆ‘n∈SkPn\Pr(d_k \in \mathcal{S}_k) = \sum_{n \in \mathcal{S}_k} P_n.

Maximize each user's hit probability

Because user kk's demand dkd_k is independent of the demands of other users, and because the only way to serve a miss is an individual unicast, the expected delivery rate decouples across users: E[R]=βˆ‘k=1KPr⁑(dkβˆ‰Sk).\mathbb{E}[R] = \sum_{k=1}^K \Pr(d_k \notin \mathcal{S}_k). Each user's contribution is minimized by choosing Sk\mathcal{S}_k to be the MM most-probable files. Because the PnP_n's are the same for every user, the optimal choice is identical across users.

Conclude

Hence Skβˆ—={1,2,…,M}\mathcal{S}_k^* = \{1, 2, \ldots, M\} for every kk, and the optimal expected rate is K(1βˆ’h(M))K(1 - h(M)). β– \blacksquare

Key Takeaway

Under the uncoded-caching restriction, popularity caching is optimal. But this optimality is conditional on a specific restriction β€” that we neither code the cache contents nor the delivery messages. Once we lift either restriction, a strictly better strategy exists. This is the central message of coded caching, and the reason we are writing this book.

Shared-Link Load Under Popularity vs. Coded Caching

Compare the expected shared-link load under popularity caching (red, for Zipf demands) with the coded-caching upper bound R=K(1βˆ’ΞΌ)/(1+KΞΌ)R = K(1-\mu)/(1+K\mu) (blue dashed, a preview of the Maddah-Ali–Niesen scheme from Chapter 2). The coded bound is demand-agnostic: it applies for any demands, including worst-case ones. Popularity caching beats the coded bound only for very concentrated demand (high Ξ±\alpha) and small ΞΌ\mu.

Parameters
30
0.8
1000

Common Mistake: The Hit Ratio Is Per-Request, Not Per-File

Mistake:

Reading "90% cache-hit ratio" as "the cache contains 90% of the library".

Correction:

The hit ratio measures the fraction of requests served locally, not the fraction of the library stored. With Zipf demands of exponent Ξ±=1.2\alpha = 1.2, a cache of 10% of the library already achieves a hit ratio near 78%. This is why commercial CDNs operate at very small cache fractions but still deliver most traffic from the edge. Conversely, in scientific or archival workloads where demand is close to uniform, a 10% cache yields exactly 10% hit ratio β€” and popularity caching buys you nothing.

Content Delivery Networks and the Shared-Link BottleneckThe Limits of Uncoded Caching