Heterogeneous Caches and General Popularity

Beyond Uniform Setups

The MAN analysis assumes homogeneous caches (M1=…=MKM_{1} = \ldots = M_{K}) and uniform demand (every file equally likely). Real networks violate both:

  • Users have different cache sizes. Mobile phones: 32-512 GB. Tablets: more. Home routers: much more.
  • Demand is skewed. Zipf-α\alpha with α≈0.8−1.2\alpha \approx 0.8-1.2 is typical. A few files attract most demand.

The optimal coded-caching rate under heterogeneous {Mk}\{M_{k}\} and general popularity p\mathbf{p} is unknown in closed form. Bounds exist but are not tight. This is the second open frontier.

Definition:

Heterogeneous Coded Caching Problem

The heterogeneous coded caching problem allows:

  • Cache sizes M1≤…≤MKM_{1} \leq \ldots \leq M_{K} (non-uniform).
  • Demand distribution p∈Δ([N])\mathbf{p} \in \Delta([N]) (non-uniform).

Objective: minimize expected delivery rate Ed∼p⊗K[R(d)].\mathbb{E}_\mathbf{d \sim \mathbf{p}^{\otimes K}}[R(\mathbf{d})]. For uniform p\mathbf{p} and equal MkM_{k}, this reduces to the worst-case MAN rate.

The combined degree of generalization is what makes the problem hard. Either heterogeneous caches alone or Zipf demand alone is partially understood; together, they are open.

Theorem: Upper and Lower Bounds for Heterogeneous Caches

For heterogeneous coded caching with cache sizes {Mk}\{M_{k}\}, the worst-case expected rate satisfies K(1−μˉ)1+Kμˉ−Δlb  ≤  R∗  ≤  K(1−μˉ)1+Kμˉ+Δub,\frac{K(1 - \bar\mu)}{1 + K\bar\mu} - \Delta_\text{lb} \;\leq\; R^* \;\leq\; \frac{K(1 - \bar\mu)}{1 + K\bar\mu} + \Delta_\text{ub}, where μˉ=(1/K)∑kMk/N\bar\mu = (1/K) \sum_k M_{k} / N is the mean memory ratio, and Δub,Δlb\Delta_\text{ub}, \Delta_\text{lb} are bounded by constants depending on the spread σ2(μk)\sigma^2(\mu_k).

Tight characterization is open.

At the mean memory ratio, MAN-like results hold. Heterogeneity creates slack that the optimal scheme may or may not exploit — whether it does is precisely the open question.

Proof
Upper bound (achievable)

Apply MAN to the homogeneous system with μˉ\bar\mu cache each (upper-bound everyone's cache at μˉ\bar\mu; underperform for large-cache users). Δub=O(σ)\Delta_\text{ub} = O(\sigma).

Lower bound (converse)

Apply cut-set with user subsets weighted by μk\mu_k. Achieves Δlb\Delta_\text{lb} of the same order.

Gap

Δub+Δlb\Delta_\text{ub} + \Delta_\text{lb} bounded by O(σ)O(\sigma); closes in the limit σ→0\sigma \to 0. Tight characterization of the midrange remains open.

Heterogeneous Caching Bounds

Upper and lower bounds for heterogeneous caches as M2M_2 varies (M1,M3M_1, M_3 fixed). Shaded region between bounds shows the current knowledge gap.

Parameters
10

Zipf Popularity: What's Known

For Zipf-α\alpha demand with homogeneous caches:

  • Expected rate approach (Niesen-Maddah-Ali, Ji-Tulino-Llorca- Caire): Popularity-weighted placement gives order-optimal expected rate. Gap to lower bound: within constant factor.
  • Worst-case approach: The MAN rate applies unchanged; popularity-aware schemes improve the expected rate but not the worst-case.

Neither approach is tight for general Zipf-α\alpha. The optimal expected rate is known only up to constant factors.

Example: Heterogeneous Caches in a Mixed Device Network

A home network: 1 smart TV (cache M1=50M_1 = 50 GB), 3 phones (M2=M3=M4=16M_2 = M_3 = M_4 = 16 GB). Total library 1 TB. What's the expected rate under uniform demand?

Solution
Parameters

Mˉ=(50+3⋅16)/4=24.5\bar M = (50 + 3 \cdot 16)/4 = 24.5 GB. μˉ=24.5/1000=0.0245\bar\mu = 24.5/1000 = 0.0245. K=4K = 4; Kμˉ=0.098K\bar\mu = 0.098.

Upper bound

MAN rate at μˉ\bar\mu: R≈4⋅0.9755/1.098≈3.55R \approx 4 \cdot 0.9755/1.098 \approx 3.55 files/use.

Lower bound

Cut-set: R≥1−μmax⁡/N=1−0.05=0.95R \geq 1 - \mu_{\max}/N = 1 - 0.05 = 0.95. Loose.

Gap

Unknown tight rate in the range [0.95,3.55][0.95, 3.55]. Likely closer to MAN for small σ2\sigma^2.

Practical

TV and phones jointly cache; coded MAN-style delivery across all four works but under-uses the TV's cache. Open: scheme that fully uses TV's excess capacity.

Memory Sharing: A Partial Solution

A clever partial solution exists: memory sharing. Treat each user's cache as a weighted sum of "virtual" caches of standard sizes. Apply MAN to each virtual system; deliver on the union.

For users with MkM_{k} varying widely: memory sharing achieves something like the average μˉ\bar\mu rate, within a small constant factor. Not tight but useful.

This is why production systems treat heterogeneous caches practically: by aggregating into tiers (phone-tier, tablet-tier, TV-tier) each homogeneous within.

🎓CommIT Contribution(2024)

Heterogeneous Coded Caching with Shared Caches

A. M. Ibrahim, G. Caire — IEEE Transactions on Communications

The CommIT contribution to heterogeneous coded caching:

  1. Framework for heterogeneous cache sizes. Formalizes the per-user cache size variation and shared-cache structures.
  2. Achievable scheme. Memory-sharing-based scheme with provable rate close to the (loose) cut-set lower bound.
  3. Practical relevance. Addresses real-world heterogeneous deployments (mobile + tablet + TV) where MAN's uniform assumption fails.
  4. Gap analysis. Quantifies the distance from tight characterization; identifies the research frontier.

This paper is part of the CommIT group's ongoing work to close the heterogeneous-cache gap. Its results complement the Zhang-Moharrami-Caire multi-rate framework (Ch 21) — both address practical generalizations of MAN.

heterogeneouscommitopen-problemView Paper →

Common Mistake: Don't Assume Mean Memory Is Enough

Mistake:

Applying MAN with μˉ\bar\mu and ignoring the variance in {Mk}\{M_{k}\}.

Correction:

For highly heterogeneous caches (e.g., 1 TB vs 1 GB), the mean μˉ\bar\mu tells only part of the story. The large-cache user may be severely underserved by a mean-μˉ\bar\mu placement; conversely, small-cache users may be served suboptimally.

Memory sharing + per-tier MAN approximates the optimum but does not close the gap. Use with awareness: Δub,lb\Delta_\text{ub,lb} may be substantial for high variance.

Key Takeaway

Heterogeneous caches and general popularity remain open. Known bounds give constant-factor characterization; tight optimal schemes are unknown. CommIT Ibrahim-Caire 2024 is the latest contribution; practical deployments use memory sharing as approximation. The heterogeneous case is the most significant open problem after coded placement.

The Coded-Placement GapFinite-Blocklength Coded Caching