D2D Coded Caching

Caching Without a Server: Device-to-Device Delivery

What if there is no server at all during the delivery phase? In dense networks (stadiums, concerts, urban hotspots), nearby users can communicate directly via device-to-device (D2D) links. If each user has cached parts of the file library, they can exchange missing content directly — no base station needed.

Ji, Caire, and Molisch showed that D2D coded caching achieves a remarkable throughput scaling: the per-user throughput is Θ(M/N)\Theta(M/N) files per time slot, independent of the number of users KK. This means the system scales perfectly: adding more users does not reduce throughput, because each new user brings both a new demand and new cached content that helps others.

Definition:

D2D Coded Caching Model

Consider KK users placed in a network, each with a cache of size MFMF bits storing content from a library of NN files. Communication occurs in two phases:

Placement phase: Same as the centralized model (MAN-style placement without knowledge of demands).

D2D delivery phase: Users communicate over D2D links. The network is modeled as a one-hop interference network: each user can transmit to all nearby users within distance rr, and transmissions from different users interfere.

The key difference from the shared-link model is that:

  1. There is no server; all delivery is peer-to-peer.
  2. Spatial reuse allows multiple simultaneous transmissions if they are sufficiently separated geographically.
  3. The interplay between coded multicasting gain and spatial reuse gain determines the throughput scaling.

Theorem: Throughput Scaling of D2D Coded Caching

For KK users uniformly distributed in a unit square, NN files, and cache size MM, with D2D communication range r=Θ(1/K)r = \Theta(1/\sqrt{K}) (ensuring Θ(1)\Theta(1) neighbors per user), the per-user throughput with coded caching is:

TD2D=Θ ⁣(MN) files per time slotT_{\text{D2D}} = \Theta\!\left(\frac{M}{N}\right) \text{ files per time slot}

for M/N=Ω(1/K)M/N = \Omega(1/\sqrt{K}). This scaling is independent of KK and order-optimal (matching the cut-set upper bound to within a constant).

The total network throughput is KTD2D=Θ(KM/N)KT_{\text{D2D}} = \Theta(KM/N), which grows linearly with the number of users.

The result combines two gains:

  1. Coded multicasting gain: Each D2D transmission serves t+1=1+KM/Nt+1 = 1 + KM/N users simultaneously, as in the MAN scheme.
  2. Spatial reuse gain: The network supports Θ(K)\Theta(K) simultaneous transmissions (each with local range r=Θ(1/K)r = \Theta(1/\sqrt{K})).

The product gives: number of user-demands served per slot =Θ(K)×(1+KM/N)= \Theta(K) \times (1 + KM/N). Dividing by KK users, each requesting one file per slot: TD2D=Θ(1+KM/N)/1×Θ(1/K)×T_{\text{D2D}} = \Theta(1 + KM/N) / 1 \times \Theta(1/K) \times (delivery load per user).

After careful accounting, the throughput simplifies to Θ(M/N)\Theta(M/N). The remarkable feature is that KK cancels: the spatial reuse gain and the per-user demand grow at the same rate, leaving throughput independent of KK.

Proof
Spatial clustering

Divide the unit square into clusters of area Θ(1/K)\Theta(1/K), each containing Θ(1)\Theta(1) users. Within each cluster, users can communicate via D2D links. Between clusters, simultaneous transmissions can be scheduled without interference (spatial TDMA with frequency reuse factor Θ(1)\Theta(1)).

Intra-cluster coded delivery

Within each cluster of Kc=Θ(1)K_c = \Theta(1) users, apply the MAN coded caching scheme. The coded multicasting gain within the cluster is 1+KcM/N1 + K_c M/N. The delivery load per cluster is Kc(1−M/N)/(1+KcM/N)K_c(1-M/N)/(1+K_c M/N).

Global throughput

There are Θ(K)\Theta(K) clusters, each completing delivery in Θ(Kc(1−M/N)/(1+KcM/N))\Theta(K_c(1-M/N)/(1+K_c M/N)) time slots. With spatial reuse (all clusters operate simultaneously), the per-user throughput is Θ((1+KcM/N)/(Kc(1−M/N)))=Θ(M/N)\Theta((1+K_c M/N)/(K_c(1-M/N))) = \Theta(M/N) for Kc=Θ(1)K_c = \Theta(1).

🎓CommIT Contribution(2016)

D2D Coded Caching

M. Ji, G. Caire, A. F. Molisch — IEEE Trans. Inf. Theory, vol. 62, no. 2, pp. 849-869

Ji, Caire, and Molisch established the fundamental throughput scaling law for D2D networks with coded caching. The main result is that per-user throughput scales as Θ(M/N)\Theta(M/N), independent of the number of users KK, by combining coded multicasting within local clusters with spatial reuse across the network. This resolved the open question of whether coded caching gains survive in distributed (serverless) settings.

D2Dcoded-cachingthroughput-scalingwireless-networksView Paper →

D2D Coded Caching: Per-User Throughput Scaling

Compare per-user throughput as a function of the number of users for: D2D coded caching, D2D uncoded caching, and centralized (server-based) delivery. Observe that D2D coded caching throughput is independent of KK.

Parameters
0.1
100

Coded Caching Architectures: Comparison

ArchitectureServerDelivery channelDoF / GainThroughput scaling
Shared-link (MAN)YesError-free broadcast1+t1 + tΘ(1+KM/N)\Theta(1+KM/N) (total)
MISO BCYes (LL antennas)Wireless MISO BCL+tL + tΘ(L+KM/N)\Theta(L + KM/N) (total)
Fog-RANCloud + edge cachesFronthaul + wirelessL+tuserL + t_{\text{user}}Depends on fronthaul
D2DNo serverD2D interferenceSpatial reuse + ttΘ(M/N)\Theta(M/N) (per-user)
Uncoded baselineYesAny1 (no coding gain)Θ(1)\Theta(1) (per-user, server)

Example: D2D Coded Caching in a Stadium

A stadium has K=10,000K = 10{,}000 users, each with a 5 GB cache. The content library has N=100N = 100 popular videos of 1 GB each. Users want to watch replays of key moments. Compute:

(a) The cache ratio and coded caching parameter. (b) The per-user throughput with D2D coded caching. (c) How long to deliver one video to each requesting user.

Solution
Cache ratio

M=5M = 5 GB / 1 GB per file =5= 5 files. M/N=5/100=0.05M/N = 5/100 = 0.05. t=KM/N=10,000×0.05=500t = KM/N = 10{,}000 \times 0.05 = 500.

Per-user throughput

TD2D=Θ(M/N)=Θ(0.05)T_{\text{D2D}} = \Theta(M/N) = \Theta(0.05) files per time slot. This means approximately 20 time slots to deliver one file per user.

Delivery time estimate

If each D2D time slot is 1 ms (short-range, high-rate D2D link at ∼\sim1 Gbps over 10 m), delivering 1 GB takes approximately 1GB/(0.05×1Gbps)=1GB/50Mbps≈1601\text{GB} / (0.05 \times 1\text{Gbps}) = 1\text{GB} / 50\text{Mbps} \approx 160 seconds.

With uncoded caching (T=Θ(1/K)→0T = \Theta(1/K) \to 0 as KK grows), delivery would require Θ(K)\Theta(K) more time slots, making it impractical.

Practical caveat

The subpacketization (Kt)=(10000500)\binom{K}{t} = \binom{10000}{500} is astronomically large, making the full MAN scheme impractical. In practice, users are clustered into groups of Kc∼20K_c \sim 20-5050, and the coded caching gain is 1+KcM/N1 + K_c M/N rather than 1+KM/N1 + KM/N. Even with Kc=20K_c = 20: gain =1+1=2= 1 + 1 = 2, still a significant improvement.

Common Mistake: Ignoring Interference in D2D Coded Caching

Mistake:

Assuming that all D2D transmissions in the network can occur simultaneously without interference, treating the D2D network as a set of parallel links.

Correction:

D2D transmissions interfere: a user transmitting at distance rr from its intended receiver also interferes with users within distance rr of the transmitter. The throughput scaling Θ(M/N)\Theta(M/N) accounts for this by using spatial TDMA (or frequency reuse) to schedule non-interfering transmissions. The spatial reuse factor is Θ(K)\Theta(K) (proportional to the number of non-overlapping clusters), which exactly compensates for the per-cluster throughput reduction due to interference. Ignoring interference leads to throughput overestimates by a factor of Θ(K)\Theta(K).

Quick Check

In D2D coded caching, the per-user throughput Θ(M/N)\Theta(M/N) is independent of KK. Why doesn't adding more users reduce throughput (as it would in a conventional system)?

Because each new user brings cached content that helps other users decode

Because D2D links have unlimited capacity

Because the server increases its transmission power

Correction:
Because each new user brings cached content that helps other users decode

Each new user adds demand (needs one file) but also adds cache content (has MM files cached). The coded multicasting gain from additional caches exactly compensates for the additional demand. This is the self-scaling property of coded caching in D2D networks.

Key Takeaway

D2D coded caching achieves perfect throughput scaling. With KK users, each caching MM out of NN files, D2D coded delivery achieves per-user throughput Θ(M/N)\Theta(M/N) independent of KK. This is possible because each new user contributes cached content that creates multicast opportunities, and spatial reuse allows parallel D2D transmissions. The result is order-optimal: it matches the cut-set upper bound. The practical limitation is subpacketization, addressed by user clustering at the cost of reduced multicasting gain.

Coded Caching over Wireless ChannelsChapter Summary