Ferkans — Interactive Telecom Tutor

Not All Caches Are Equal

Real users have different cache budgets: a smartphone with 64 GB of free storage is different from a tablet with 500 GB. A smart-TV set-top box is different from a handheld. Even within a homogeneous fleet, users may pre-allocate storage differently. How does coded caching perform when cache sizes vary across users?

This section extends MAN to the heterogeneous-cache setting and quantifies the rate degradation from heterogeneity. The main result: at fixed aggregate cache $\sum_k M_k = K \bar M$ , the best achievable rate is typically within a constant factor of the homogeneous rate at the average. Heterogeneity costs a factor of $\leq 2$ .

Definition:
Heterogeneous-Cache Network

In a heterogeneous-cache coded caching network, user $k$ has cache size $M_{k}$ files, with $k \in [K]$ . The average cache is $\bar{M} = (1/K) \sum_k M_{k}$ . The aggregate caching gain is $t_\text{agg} \;=\; \sum_k M_{k} / N \;=\; K \bar{M}/N.$ Demand vectors $\mathbf{d} \in [N]^K$ as in MAN.

At $M_{k} = \bar{M}$ for all $k$ : reduces to homogeneous MAN. At extreme heterogeneity (some caches empty, others full): significantly different.

Theorem: Achievable Rate with Heterogeneous Caches

For a heterogeneous-cache network with per-user caches $(M_{1}, \ldots, M_{K})$ , the following rate is achievable: $R_\text{het}(M_{1}, \ldots, M_{K}) \;\leq\; K\!\left(1 - \bar{\mu}\right)/\left(1 + K\bar{\mu}\right),$ where $\bar{\mu} = \bar{M}/N$ is the average memory ratio. Moreover, the gap to the homogeneous rate at $\bar M$ is at most a factor of 2.

A randomized placement that mimics MAN but allows cache sizes to vary achieves the stated rate. At aggregate level, the caching gain depends only on $\sum M_k = K \bar M$ . Individual heterogeneity affects the distribution of cached content but not (to first order) the total coded-multicast opportunity.

Proof

Placement

User $k$ caches each subfile $W_{n, \mathcal{S}}$ (in the MAN combinatorial structure, with $|\mathcal{S}| = t = K \bar \mu$ ) with probability $M_{k} / M_\text{MAN,k}$ where $M_\text{MAN,k}$ is what user $k$ would cache under uniform MAN. Stated differently: each user caches a random subset of the MAN subfiles, with size proportional to its cache budget.

Delivery

Standard MAN XOR delivery, adapted to handle the randomness. Some XOR messages may need to be resent because not all expected subfiles are cached — this overhead is small on average.

Rate

Expected rate: matches MAN at $\bar M$ up to a factor from the random admission. Worst case: at most 2× the homogeneous rate (Sengupta-Tandon-Clancy 2017, Theorem 1). $\blacksquare$

Heterogeneous Cache Effect

Rate as a function of cache heterogeneity (spread across users). At 0 (homogeneous): baseline MAN rate. As heterogeneity grows, some users cache more, others less — aggregate cache is fixed, rate slightly degrades. Even at full heterogeneity, gap to homogeneous is small. Reveals that average cache is the dominant quantity.

Parameters

Users K10

Average memory ratio0.3

Example: Two-Tier User Network

Design a network: 50% of users have $M_1 = 100$ (rich cache), 50% have $M_2 = 10$ (poor cache). Library $N = 200$ , total users $K = 100$ . Compute the achievable heterogeneous rate and compare with homogeneous MAN at $\bar M = 55$ .

Solution

Average

$\bar M = (50 \cdot 100 + 50 \cdot 10)/100 = 55$ . $\bar\mu = 55/200 = 0.275$ .

Homogeneous rate

$t = K \bar\mu = 100 \cdot 0.275 = 27.5$ . $R_{\text{homo}} = 100 \cdot 0.725/28.5 = 2.54$ files/round.

Heterogeneous rate

Rich users contribute more to coded multicast gain per cache bit. Achievable rate: approximately $R_{\text{homo}}$ with small constant-factor gap. Rigorously: $R_\text{het} \leq 2 R_\text{homo} = 5.08$ . Practically: $\approx 2.7$ - $3.0$ .

Engineering interpretation

A user with 10× the cache doesn't give 10× the benefit — the rate depends on aggregate cache, not max. For fair resource allocation: weighted proportional-to-budget works best. Rich users subsidize poor users through coded multicasting.

Rich Caches Subsidize Poor Caches

A subtle but important insight from the heterogeneous-cache analysis: users with larger caches not only benefit themselves (higher hit ratio, cache direct) but also contribute to other users' content via coded multicasting. A user with a very large cache holds many subfiles that appear in XOR messages targeting other users.

Economic implication: rich-cache users create positive externalities. In privacy-preserving / incentive-compatible designs, rewarding users who contribute large caches (beyond what they personally need) could improve total network performance. The theoretical basis for this is the MAN structure's sensitivity to aggregate cache rather than individual cache.

Common Mistake: Average, Not Minimum

Mistake:

Saying "heterogeneous MAN rate is bottlenecked by the smallest cache."

Correction:

The bottleneck is the aggregate cache, not the minimum. Rich caches compensate for poor caches in the coded-multicast gain formula. A single user with zero cache still receives coded messages that are XOR'd from other users' cached subfiles. Her own lack of cache reduces her hit rate but not the delivery rate to others.

Mathematically: $R_{\text{MAN}}$ depends on $\sum M_k/N$ , not $\min M_k/N$ . This is a pleasant feature — fleet heterogeneity is surprisingly friendly to coded caching.

Heterogeneous Cache Sizes