Ferkans — Interactive Telecom Tutor

Can We Have Both?

Chapter 2 showed that coded multicasting provides a factor $(1 + KM/N)$ improvement in single-server content delivery. Chapter 10 showed that D2D caching alone delivers $\Theta(M/N)$ per-user throughput via spatial reuse. A natural question:

If we combine both mechanisms — use MAN-style coded delivery within D2D clusters — do the gains multiply? Intuitively, one might hope for a throughput of $\Theta((1+KM/N) \cdot M/N) = \Theta(M/N + KM^2/N^2)$ — superlinear in $M/N$ .

The Ji-Caire-Molisch 2015 answer is more subtle. At the scaling- law order, the two gains do not cumulate. Both the uncoded and coded schemes achieve $\Theta(M/N)$ per-user throughput; the coded scheme improves only the constant factor, not the order. This is a surprising result that deserves careful explanation.

Definition:
Coded D2D Caching Network

A coded D2D caching network is a D2D network (Chapter 10) with two modifications:

MAN-style placement. Users cache according to the MAN combinatorial scheme (within local clusters of size $K_g$ ). Each file split into $\binom{K_g}{t}$ subfiles; each user caches $\binom{K_g-1}{t-1}$ of them.
Coded XOR delivery. On demand, neighbors exchange XORs of subfiles (following the MAN delivery pattern) instead of unicasting raw content.

The interference model, random demands, and scaling assumptions are the same as in Chapter 10.

"Local cluster" means a set of $K_g$ users within D2D range of each other, so that MAN delivery can be executed with all $K_g$ users participating. Typically $K_g \sim \log n$ for random deployments.

Coded D2D Delivery Protocol

Complexity: Per cluster:

\binom{K_g}{t+1}

XOR transmissions. Across clusters:

\Theta(n/K_g)

clusters, each running in parallel with spatial reuse. Total time: dominated by per-cluster cost.

Input: MAN placement within each local cluster; demand vector

\mathbf{d}

.

Output: Delivery schedule of coded XOR messages.

1. Partition

n

users into clusters of size

K_g

(disjoint or

overlapping, by geographic proximity).

2. for each cluster

\mathcal{C}

do

3.

\quad

Run MAN delivery within

\mathcal{C}

: for every

(t+1)

-subset of

\mathcal{C}

, form XOR message

X_{\mathcal{S}'}

.

4.

\quad

Schedule XOR transmissions within

\mathcal{C}

via

TDMA (one transmitter at a time in the cluster).

5. end for

6. Between clusters: spatial reuse. Multiple clusters transmit

concurrently, subject to the protocol-model interference

constraint.

The key design parameter is the cluster size $K_g$ . Larger $K_g$ gives larger MAN gain $(1 + K_g M/N)$ per cluster but requires more transmissions per cluster (worse scaling in cluster).

Coded D2D clustered topology — $n$ users partitioned into local clusters of size $K_g$ . Within each cluster: MAN placement + XOR delivery. Across clusters: spatial reuse — non-overlapping clusters transmit in parallel.

The Two Mechanisms in Tension

Let us name the two gain mechanisms clearly:

Spatial reuse (Gupta-Kumar / Ji-Caire-Molisch 2016): $n$ concurrent short-range D2D links can coexist. Each link has capacity $\Theta(1)$ . Aggregate throughput: $\Theta(n)$ . Per-user: $\Theta(1)$ — if every user has content in a neighbor's cache.

Coded multicasting (Maddah-Ali-Niesen): within a group of $K_g$ users sharing cached content, one coded XOR message simultaneously serves $t+1 = K_g M/N + 1$ users. Gain factor $1 + K_g M/N$ per cluster.

If we naively multiply: $\Theta(n \cdot (1 + K_g M/N))$ . But this is not right. The issue is that the mechanisms compete for the same resource: concurrent transmissions. A cluster running MAN uses its airtime internally; it cannot also be silently coexisting with concurrent external transmissions.

The correct analysis: per-cluster throughput scales as $\Theta((1 + K_g M/N))$ but per-cluster airtime scales as $\Theta(\binom{K_g}{t+1})$ messages. Normalized: effectively $\Theta(M/N)$ per user. The MAN gain is "absorbed" into the coding overhead at the scaling order.

Example: Cluster-Size Design

In a D2D network of $n = 1000$ users, $\mu = 0.1$ , choose cluster size $K_g = 10, 50, 100$ . Compare throughput scaling for each.

Solution

$K_g = 10$

Per-cluster MAN gain: $1 + 10 \cdot 0.1 = 2$ . Per-cluster airtime: $\binom{10}{2} = 45$ XOR messages per delivery round. Number of clusters: $100$ . With spatial reuse across clusters: aggregate throughput $\sim 2 \cdot 100 \cdot c_{\text{link}} = 200 c_{\text{link}}$ . Per-user: $0.2 c_{\text{link}} = \Theta(M/N \cdot 2)$ — constant factor 2 above uncoded.

$K_g = 50$

MAN gain: $1 + 5 = 6$ . Airtime: $\binom{50}{6} \approx 16 \times 10^6$ — astronomical. In practice subpacketization bounds the feasible cluster size.

$K_g = 100$

MAN gain: $1 + 10 = 11$ . Subpacketization astronomically large; infeasible.

Practical choice

The sweet spot is moderate $K_g$ — enough to capture the coded gain, not so large that subpacketization kills it. Typically $K_g \sim 5$ - $20$ in practice.

Key Takeaway

Coded multicasting and D2D spatial reuse are in tension at the scaling-law level. Cluster-based MAN within a D2D network improves the constant factor but not the scaling order. The order is $\Theta(M/N)$ for both uncoded and coded schemes. The coded scheme wins on the constant — a practically meaningful but not asymptotically dominant gain.

Combining Coded Multicasting with D2D