Ferkans — Interactive Telecom Tutor

The Multicast Paradox

Broadcast is naturally efficient when everyone gets the same content: one transmission, many receivers. Coded caching pushes this efficiency further by XOR-combining distinct messages so that each XOR stream benefits $t+1$ users. But there is a catch: on a noisy channel, the XOR stream must be sent at a rate that every targeted user can decode — i.e., the rate of the worst user in the group.

This "worst-user bottleneck" has been a classical problem in broadcasting. Multicasting pay-TV to a suburb, for example, is often rate-limited by a single subscriber at the edge of coverage. Cache- aided delivery inherits this issue and — in vanilla MAN — does not automatically solve it. We spend this section understanding the bottleneck and the opportunities to mitigate it.

Theorem: Naive MAN on Degraded BC: Worst-User Limit

For the cache-aided degraded Gaussian BC with $K$ users, memory ratio $\mu = M/N$ , and user SNRs $\rho_1 \geq \ldots \geq \rho_K$ , the naive MAN delivery (single-rate multicast of coded XORs) achieves per-user symmetric rate $R_{\text{sym}} \;=\; \frac{\log_2(1 + \rho_K)}{R_{\text{MAN}}/K} \;=\; \log_2(1 + \rho_K) \cdot \frac{1 + t}{1 - \mu},$ where $t = K \mu$ is the caching gain.

Each coded XOR message is multicast at the weakest-user rate; the bottleneck is $\log_2(1+\rho_K)$ . The caching gain $(1 + t)$ reduces the total number of channel uses needed, so the per-user rate is the multicast capacity scaled by the caching gain ratio.

Proof

MAN delivery length

MAN sends $\binom{K}{t+1}$ coded messages, each of size $F/\binom{K}{t}$ bits. On a multicast channel of rate $C_{\min} = \log_2(1+\rho_K)$ , delivering each message takes $(F/\binom{K}{t})/C_{\min}$ channel uses. Total: $T = \binom{K}{t+1} \cdot F/(\binom{K}{t} C_{\min}) = F (K-t)/((t+1) C_{\min})$ .

Per-user rate

Each user recovers 1 file ( $F$ bits) in $T$ channel uses. Per-user rate: $F/T = (t+1) C_{\min}/(K-t)$ bits per channel use.

Rearrange

$R_{\text{sym}} = C_{\min} \cdot (t+1)/(K-t) = C_{\min} \cdot (1 + t)/((1-\mu) K)$ . In file units: $C_{\min}/R_{\text{MAN}}$ , matching the statement. $\blacksquare$

Per-User Capacity and Worst-User Bottleneck

For a degraded BC with $K$ users and ordered SNRs, visualize each user's individual capacity $C_k = \log_2(1 + \rho_k)$ and the worst-user multicast rate $C_{\min}$ . Adjust the spread to see how channel heterogeneity penalizes multicast. For narrow spread (all users similar), $C_{\min} \approx C_{\text{avg}}$ . For wide spread, multicast wastes the strong users' capacity.

Parameters

Number of users K8

Median SNR (dB)10

SNR spread (dB)20

Example: MAN-Multicast vs Time-Sharing Unicast

For $K = 10$ , $\mu = 0.2$ (so $t = 2$ ), user SNRs linearly spread from 20 dB (user 1) to 0 dB (user 10), compare (a) naive MAN-multicast at worst-user rate, (b) time-sharing unicast at each user's capacity, (c) full superposition BC coding with caching.

Solution

Per-user capacities

$\rho_k$ ordered 100, 63.1, 39.8, 25.1, 15.8, 10.0, 6.3, 4.0, 2.5, 1.0. $C_k = \log_2(1 + \rho_k)$ : 6.66, 6.00, 5.35, 4.70, 4.07, 3.46, 2.87, 2.32, 1.81, 1.00. $C_{\min} = 1.00$ bits.

(a) Naive MAN

$R_{\text{MAN-file}} = 10(1-0.2)/(1+2) = 8/3 \approx 2.67$ files. Per-user throughput: $C_{\min}/R_{\text{MAN-file}} = 1.00/2.67 \approx 0.374$ bits per channel use.

(b) Time-sharing unicast

Per user: $C_k/K$ . Average: $\bar C / K = 3.824/10 = 0.38$ bits per channel use. Similar to MAN-multicast in this regime — coded-caching multicast's rate advantage is offset by worst-user penalty.

(c) Superposition + caching (JLEC)

The JLEC scheme (§6.3) exploits both. Users get different effective rates based on their channel quality; cache + superposition achieves strictly more than either (a) or (b). Approximate per-user rate: 0.5–0.7 bits per channel use, a 50–100% gain over naive schemes.

Lesson

On heterogeneous BC, vanilla MAN is not much better than time-sharing. The JLEC result is that a properly designed scheme can extract both caching AND heterogeneity gains simultaneously.

Per-User Throughput vs Memory Ratio (Degraded BC)

Compare the naive MAN-over-BC throughput (blue) with the time-sharing unicast baseline (red dashed) as a function of memory ratio. At small $\mu$ , both are limited by the worst-user capacity. At larger $\mu$ , MAN's caching gain dominates. The crossover point depends on the channel spread.

Parameters

Number of users K10

Min SNR (dB)0

Max SNR (dB)20

Definition:
Superposition Coded Caching

Superposition coded caching is a delivery strategy for the degraded BC that combines coded multicasting with rate-split BC coding. The delivery signal is $x \;=\; \sqrt{\beta P} u_{\text{common}} + \sqrt{(1-\beta) P} u_{\text{strong}},$ where $u_{\text{common}}$ is a MAN-style XOR message decodable by all users, and $u_{\text{strong}}$ is additional content destined for stronger users (cache-aided in a sub-scheme). The split parameter $\beta \in [0, 1]$ is tuned based on channel heterogeneity.

The superposition-CC idea generalizes superposition BC coding (Cover '72) to the cache-aided setting. It is one of several approaches; the JLEC 2019 framework provides the asymptotically optimal version in GDoF terms.

User Grouping Alternative

A simpler (and often practical) alternative to superposition coding is user grouping: partition users into $G$ channel-quality groups and run MAN independently within each group, time-sharing between groups. If groups have approximately uniform SNRs within each, the worst-user penalty within a group is small.

Tradeoff: more groups $\Rightarrow$ smaller $K_g$ per group $\Rightarrow$ less coded-caching gain. Fewer groups $\Rightarrow$ more within-group heterogeneity $\Rightarrow$ larger worst-user penalty. The optimum balances these, typically at $G = \Theta(\log K)$ groups with geometrically spaced SNR boundaries.

Common Mistake: Don't Assume All Users Decode the Same Rate

Mistake:

Applying MAN's error-free-link rate formula $R = K(1-\mu)/(1+K\mu)$ directly to a wireless BC with heterogeneous channels.

Correction:

The MAN rate formula is in file units. To convert to bits per channel use on a degraded BC, multiply by the channel rate — but which rate? Naive: multicast at worst-user rate $C_{\min}$ . This gives a throughput far below each user's individual capacity. A better answer uses superposition or grouping; the correct rate is $R_{\text{eff}} = C_{\min} \cdot (t+1)$ only if the scheme genuinely leaves strong users idle — a design flaw, not a fundamental limit. JLEC 2019 closes this gap.

The Worst-User Bottleneck in Multicast

The Multicast Paradox

Theorem: Naive MAN on Degraded BC: Worst-User Limit

MAN delivery length

Per-user rate

Rearrange

Per-User Capacity and Worst-User Bottleneck

Parameters

Example: MAN-Multicast vs Time-Sharing Unicast

Per-user capacities

(a) Naive MAN

(b) Time-sharing unicast

(c) Superposition + caching (JLEC)

Lesson

Per-User Throughput vs Memory Ratio (Degraded BC)

Parameters

Definition: Superposition Coded Caching

User Grouping Alternative

Common Mistake: Don't Assume All Users Decode the Same Rate

Definition:
Superposition Coded Caching