Exercises

$T_n(M) = \Theta(M/N)$ under: (i) random uniform deployment in unit area, (ii) random uniform demand, (iii) protocol interference model with radius $r(n) = \sqrt{c \log n/n}$, (iv) fixed memory ratio $M/N$, $n \to \infty$.

With $r(n) = \sqrt{\log n/n}$, expected $|\mathcal{N}| \approx \log n \approx 4.6$. Each neighbor caches 25% of the library. Expected neighbors caching any fixed file: $4.6 \cdot 0.25 = 1.15$ — likely to find at least one.

D2D caching: per-user $\Theta(M/N)$, constant in $n$ — the only scheme whose per-user throughput doesn't decay. Gupta- Kumar ad-hoc (no caching): $\Theta(1/\sqrt{n \log n})$, vanishing. Infrastructure cellular (no caching): $O(1/n)$, vanishing faster. D2D caching is the scalable architecture at dense network size.

As $n$ grows: (i) aggregate cache grows as $nM$; (ii) demand grows as $n$; (iii) spatial reuse grows as $\Theta(n/r^2)$. All three scale linearly with $n$. The per-user throughput = (spatial reuse × hit probability × link capacity) / $n$ stays constant: $\Theta(M/N)$. Supply, demand, and parallelism scale together, giving flat per-user scaling.

Protocol model: two simultaneous transmissions interfere if receivers are within distance $r(n)$ of either transmitter. This gives a combinatorial non-interference structure (graph coloring). The scaling law depends on $r(n)$: choosing $r(n) = \sqrt{c \log n/n}$ balances connectivity (not too small) against interference (not too large). The result $\Theta(M/N)$ assumes this optimal scaling.

Given a neighbor caches a random $\mu$-fraction of the library, probability it caches the requested file is $\mu$. Probability it doesn't: $1 - \mu$.

With $k$ independent neighbors, probability none caches the file: $(1 - \mu)^k$. Probability at least one does (hit): $p_{\text{hit}}(k, \mu) = 1 - (1-\mu)^k$.

As $k \to \infty$, $p_{\text{hit}} \to 1$. For $k \mu \geq 3$, hit probability $> 0.95$. Since $k \approx \log n$, even modest $\mu$ gives near-certain hits at large $n$.

This analysis ignores neighbor correlation (same neighbors may cache same files). The Ji-Caire-Molisch analysis accounts for this correctly.

Throughput constant $c$ involves the hit probability, the number of simultaneous non-interfering transmissions per unit area, and the per-link rate. Explicit form (simplified): $c \approx C_{\text{link}} / r^2 \cdot (1 - (1-M/N)^{k})$ where $k = \log n$ is expected neighbors.

For typical parameters (5 GHz band, 10 m range, 100 Mbps/link), $c$ can be 0.1-1. The per-user rate is then $T \approx 0.5 \cdot M/N \cdot 100 \text{ Mbps} = 50 \cdot M/N$ Mbps.

Hit rate $\propto M/N$. Throughput: $\Theta(M/N)$.

Hit rate scales with $H_{M,\alpha}/H_{N,\alpha}$ (generalized harmonic). For $\alpha > 0$, this exceeds $M/N$ — concentration helps caching.

Throughput: $\Theta(H_{M,\alpha}/H_{N,\alpha})$. For $\alpha = 1$: $H_{M,1}/H_{N,1} \sim \log M / \log N$, which can exceed $M/N$ for small $M$. Zipf demand benefits D2D caching disproportionately.

D2D: $\mu \cdot C_{\text{link}}$. Infrastructure: $\log n / n \cdot C_{\text{BS}}$. Assume $C_{\text{link}} \sim C_{\text{BS}}$. Crossover: $n/\log n \approx 1/\mu$.

$\mu = 0.1 \Rightarrow n/\log n \approx 10 \Rightarrow n \approx 30-40$. For $\mu = 0.05 \Rightarrow n \approx 60-80$. D2D wins for densities of ~30-100 users sharing a resource.

At stadium/urban density (1000+ users/cell), D2D is the overwhelmingly preferred architecture. At small-office or rural density, infrastructure is better.

Daily refresh per user: $10\% \cdot 10 \text{ GB} = 1 \text{ GB}$. Total across $n = 1000$ users: $1000 \text{ GB/day}$.

Distributed over 8 hours (off-peak): $1000 / 8 = 125$ GB/hr = $\approx 270$ Mbps aggregate. Per user average: $<1$ Mbps — negligible compared to peak delivery rates.

Cache refresh is practically affordable even with high churn rates. The main constraint is energy (wakeup / radio on) for mobile devices, not bandwidth.

Consider any user $k$. Its caching contribution (own cache) provides $M/N$ fraction of demands locally (no network transmission). Remaining demands must come via D2D, subject to Gupta-Kumar scaling.

$T_n(M) \leq T_{\text{local}}(M) + T_{\text{network}}(n) \leq M/N + O(1/\sqrt{n\log n})$. Achievability (Ji-Caire-Molisch) matches up to constants.

The $\Theta(M/N)$ scaling dominates for fixed $M/N$ and large $n$. The $1/\sqrt{n}$ term vanishes; cache dominates.

Fraction $p$ of demand is popular (covered by D2D with hit rate $p_h$). Fraction $1-p$ is unpopular (fallback to infrastructure). Aggregate demand rates: $R_{\text{D2D}} = p \cdot p_h \cdot T_{\text{D2D}}$, $R_{\text{inf}} = (1 - p \cdot p_h) \cdot T_{\text{inf}}$.

Infrastructure bandwidth is fixed; D2D scales with $n$. Optimize $p$ (cache-placement policy) to minimize infrastructure load subject to capacity constraint. Typically: cache popular content, let unpopular go via infrastructure.

See Ji-Tulino-Llorca-Caire 2017 for exact analysis under Zipf popularity. Hybrid schemes beat pure D2D or pure infrastructure.

Under SINR with path-loss exponent $\alpha > 2$, the equivalent interference radius scales as $r_{\text{eff}}(n) \propto \sqrt{\log n/n}$ — same as protocol. Analysis generalizes: $\Theta(M/N)$ holds.

Dense scatterer environments (small $\alpha$) can change the scaling; typically $\alpha = 4$ (urban) gives similar results to protocol model.

Physical-model analysis is technically involved; Ji-Caire- Molisch's Theorem 1 is stated under protocol, with extensions to SINR in follow-up CommIT papers.

Let $p_s$ = fraction of selfish users (refuse to serve). Effective serving population: $n (1 - p_s)$. Cache coverage reduced by same factor.

Per-user throughput: $\Theta(M/N \cdot (1 - p_s))$. Still $\Theta(M/N)$ in order; constant multiplied by $1 - p_s$.

Up to ~50% selfishness, D2D caching still delivers substantial throughput. Beyond that, infrastructure takes over. Incentive design (token schemes, reduced billing for servers) aims to keep selfishness low.

Game-theoretic analysis of D2D with strategic users is active research. The coded-caching community has touched on this; full treatment beyond scope.

If user mobility is faster than cache refresh, new arrivals don't have relevant cached content. Hit rate degrades. Scaling can even fall to Gupta-Kumar if mobility is extreme.

Mobile users can adapt caches based on location-dependent demand. The mobility mixing spreads popular content network-wide. Scaling holds with similar constants.

• Slow mobility (humans walking): negligible effect.
• Moderate (cars): $\Theta(M/N)$ holds with constant degradation.
• Fast (high-speed rail): may fall out of scaling regime.

Mobility-aware D2D caching is an active 6G research area. Digital twins and location-prediction may enable proactive caching that survives mobility.