PaperlayerView exact revision on arXiv

Source-linked AI summary

Fundamental Limits of Caching in Wireless D2D Networks

Mingyue Ji, Giuseppe Caire, Andreas F. Molisch

arXiv:1405.5336v1cs.IT

TL;DR

The paper develops deterministic and random caching with coded delivery for wireless D2D networks. It establishes constructive achievability strategies and shows that combining spatial spectrum reuse with coded multicasting does not improve throughput scaling.

  • Problem

    The paper studies caching and delivery in wireless D2D networks, including whether spatial reuse and coded multicasting provide a cumulative gain.

  • Method

    The paper considers deterministic centralized caching and random decentralized caching, together with inter-session network-coded delivery.

  • Results

    The throughput does not improve in terms of the scaling law when spatial spectrum reuse and coded multicasting are used together.

  • Takeaways & Limitations

    The results establish constructive achievability coding strategies and show no fundamental cumulative gain from using both mechanisms.

  • Takeaways & Limitations

    The conclusions rely on an assumption of asynchronous content reuse, under which naive multicasting is forbidden or useless by the model.

Abstract

from arXiv · show

We consider a wireless Device-to-Device (D2D) network where communication is restricted to be single-hop. Users make arbitrary requests from a finite library of files and have pre-cached information on their devices, subject to a per-node storage capacity constraint. A similar problem has already been considered in an ``infrastructure'' setting, where all users receive a common multicast (coded) message from a single omniscient server (e.g., a base station having all the files in the library) through a shared bottleneck link. In this work, we consider a D2D ``infrastructure-less'' version of the problem. We propose a caching strategy based on deterministic assignment of subpackets of the library files, and a coded delivery strategy where the users send linearly coded messages to each other in order to collectively satisfy their demands. We also consider a random caching strategy, which is more suitable to a fully decentralized implementation. Under certain conditions, both approaches can achieve the information theoretic outer bound within a constant multiplicative factor. In our previous work, we showed that a caching D2D wireless network with one-hop communication, random caching, and uncoded delivery, achieves the same throughput scaling law of the infrastructure-based coded multicasting scheme, in the regime of large number of users and files in the library. This shows that the spatial reuse gain of the D2D network is order-equivalent to the coded multicasting gain of single base station transmission. It is therefore natural to ask whether these two gains are cumulative, i.e.,if a D2D network with both local communication (spatial reuse) and coded multicasting can provide an improved scaling law. Somewhat counterintuitively, we show that these gains do not cumulate (in terms of throughput scaling law).

I. INTRODUCTION

The paper contrasts infrastructure-based coded multicasting with infrastructure-less D2D caching, asking whether spatial reuse and coded multicasting provide cumulative throughput gains. Prior results show both approaches exploit redundant demands and achieve favorable scaling, motivating the paper’s central question.

  • Prior caching approaches: Prior D2D caching uses random caching and interference-avoiding spatial reuse, with throughput scaling order-optimally under the considered model.The result applies as n, m →∞ with nM ≫m and allows a fixed small outage probability.
  • Prior caching approaches: Infrastructure-based coded multicasting stores packets from all files and broadcasts linear combinations that satisfy arbitrary user demands.The scheme uses a common multicast coded message from an omniscient transmitter.
  • Prior caching approaches: The infrastructure-based scheme achieves approximate optimality within a constant factor, while its throughput scaling matches the D2D caching result when nM ≫m.The cited result gives a cut-set lower bound and a constant-factor comparison.
  • Motivation: Conventional central-server delivery cannot exploit content reuse when many users request a limited library, whereas caching performs better for highly redundant demands.Both caching approaches scale linearly with per-user cache memory M in the cited regime.
  • Motivation: The paper asks whether combining D2D spatial reuse with coded multicasting yields an additional throughput-scaling gain.The two prior approaches respectively exploit local communication and global coded multicast messages.

A. Overview of the Main Results

The paper studies deterministic and decentralized random caching with coded delivery in D2D networks. It shows that coded multicasting can work without a base station, but combining it with optimized spatial reuse does not improve the throughput scaling law.

  • Approach: The paper develops caching and delivery schemes based on subpacketization and inter-session coding, considering both deterministic and decentralized random caching.The two schemes differ in whether cache placement is centralized or random.
  • Main results: When every node can reach every other node in one hop, the proposed scheme nearly matches infrastructure-based coded multicasting without a central base station.In this setting, scheduling concurrent transmissions is irrelevant.
  • Main results: With limited transmission range, throughput has the same scaling law as either reuse-only or coded-only schemes, up to potentially different leading-term constants.This remains true even after optimizing transmission range and spatial reuse.
  • Main results: The spatial reuse gain and coded multicasting gain therefore do not cumulate in throughput scaling, despite being different types of gains.The paper distinguishes scaling-law conclusions from coefficient-level optimization.
  • Main results: For most system-parameter regimes, excluding very small caches, both proposed caching schemes achieve throughput optimal within a constant factor.The paper identifies very small caches as not especially relevant for applications.

B. Remarks

The remarks clarify the paper’s coding terminology, channel and caching assumptions, and interpretation of asynchronous content reuse. They also distinguish the model from online caching and account for unequal file lengths and asynchronous demands.

  • Terminology: Here, coding means inter-session network coding: codewords combine subpackets from different library files, unlike intra-session erasure coding.The distinction concerns whether subpackets from different source messages are mixed.
  • Modeling assumptions: The protocol model treats in-range transmissions as noiseless and does not include packet-erasure coding for channel impairments.The model assumes successful decoding within the appropriate range.
  • Modeling assumptions: Caching occurs a priori on a slower timescale than delivery, such as daily cache updates during off-peak cellular-network use.This differs from online policies that update cache contents during delivery.
  • Scope: The paper handles asynchronous demands and unequal-length files without changing the fundamental performance of its schemes.The exposition assumes equal-length files for simplicity.
  • Spatial reuse illustration: Figure 1 depicts a 49-node grid and a clustered spatial-reuse layout in which separated clusters transmit concurrently under an interference-avoidance protocol.Gray squares mark concurrent transmitting clusters, while the red disk marks the exclusion region.

II. NETWORK MODEL AND PROBLEM DEFINITION

The model places users on a grid, gives each a finite cache, and allows arbitrary file-segment requests over single-hop D2D links. Performance jointly depends on caching, coded delivery, decoding, and interference-constrained transmission scheduling.

  • Network and demands: The network contains n users on a unit-square grid, each requesting an arbitrary file from a library of m files.Grid nodes have minimum separation 1/√n.
  • Transmission model: A transmission succeeds only when the receiver lies within range r and every simultaneously transmitting interferer is at least (1+∆)r away.The protocol model constrains feasible concurrent links.
  • Network and demands: Each file is divided into L packets, and each user requests an arbitrary contiguous segment of L′ packets from its selected file.The analysis considers large L and finite L′, including worst-case demand vectors.
  • Caching and delivery: Caching maps the library into per-user caches of size M files, while delivery uses node encoding and decoding functions based on caches and the demand vector.Each node transmits a coded message determined by its cache and the requests.
  • Performance measure: The system rate is defined through worst-case coded transmissions and is converted to throughput by the channel uses required to deliver all requested information.The model measures useful information bits per channel use.
  • Performance measure: Because no omniscient node exists and demands are deterministic worst-case demands, the aggregate caches must contain the library, requiring t ≥1.If t < 1, missing files or file parts cannot be delivered.

III. DETERMINISTIC CACHING, ACHIEVABILITY AND CONVERSE BOUND √

The proposed caching and coded-multicasting scheme is achievable and, except in very small-cache redundant-request regimes, matches information-theoretic lower bounds within a constant factor. Localized communication with clustering and reuse extends the scheme to spatially reused D2D networks, while the benefit of reuse depends on the physical-layer channel model.

  • Achievability: Theorem 1 provides an achievable rate for the proposed caching and coded-multicasting scheme, with convex interpolation when the parameter t is nonintegral.The caching and delivery construction is given in Appendix A, and the convex lower envelope remains achievable.
  • Converse bound: A converse lower bound follows from cut-set arguments and the fact that activating a single link per channel use is feasible.The bound upper-bounds any achievable throughput after conversion between rate and throughput.
  • Order optimality: Except when n > m and M < 1/2 file, the achievable result is within a constant multiplicative factor of the lower bound.The unbounded gap in the excluded regime is tied to asynchronous requests and the prohibition of naive multicasting.
  • Order optimality: When every user requests a whole file (L = L′), the achievable rate is within a constant multiplicative factor of the lower bound in all parameter regimes.For large asynchronous content reuse with moderate-to-large caches, a constant multiplicative gap remains achievable without naive multicasting.
  • Spatial reuse: For short-range communication, clustering stores the library within each cluster and partitions clusters into reuse sets for concurrent transmissions.The construction assumes gcM ≥ m and uses a reuse factor K; one transmitter serves all nodes in an active cluster per time slot.
  • Spatial reuse: Whether spatial reuse improves throughput depends on how link spectral efficiency varies with communication range, which the protocol model does not capture.The relevant comparison is between network-wide efficiency and the reused-cluster efficiency Cr/K.

C. An Example

The example introduces a three-user D2D network with per-node cache size M = 2 and library size m = 3. It frames the proposed placement and delivery scheme through this small network.

  • C. An Example: The proposed placement and delivery scheme, together with the converse techniques, is illustrated through this three-user network.The example serves as a concrete setting for the general achievability and lower-bound arguments.
  • C. An Example: The example considers three users, each storing M = 2 files from a library of m = 3 files.The files are denoted A, B, and C, and the transmission range satisfies the example's stated condition.

2. Without

The example divides files into subpackets, assigns cached subsets to users, and uses pairwise coded transmissions to satisfy distinct demands. It achieves rate R(2) = 1/2, while cut-based inequalities establish the matching lower bound.

  • Placement: For demand vector (A, B, C), the example treats the requested files as distinct, so the segment index can be omitted.The construction assumes one requested packet per file in this illustration.
  • Placement: Each file packet is divided into six subpackets of size F/6, enabling distributed cache placement across the three users.The example labels subpackets separately for files A, B, and C and specifies each user's cached collection.
  • Coded delivery: Users multicast pairwise XORs such as B3 + C1, A5 + C2, and A6 + B4, each useful to two intended receivers.These three transmissions collectively implement coded delivery for the example demands.
  • Achievability: R(2) = 1/2 is achievable for the three-user, M = 2 example.The figure caption independently identifies the same achieved rate.
  • Converse: Cut-set inequalities over all three request permutations lower-bound the total transmitted coded information and yield a bound on R(M).The argument sums analogous inequalities, normalizes by file size, and applies the worst-case rate definition.

2. Therefore, in this case the achievability

The example is information-theoretically optimal for the D2D setting, but lacks the omniscient base station available in infrastructure-based coded multicasting. In this instance, that absence incurs a relative loss of 3/2.

  • 2. Therefore, in this case the achievability: The example's caching and delivery scheme is information theoretically optimal for the considered D2D network.The optimality statement refers to the scheme established in the preceding example.
  • 2. Therefore, in this case the achievability: For n = 3, M = 2, and m = 3, infrastructure-based coded multicasting uses a single codeword sent through a common bottleneck.This contrasts the D2D setting with a base station that has access to all files.
  • 2. Therefore, in this case the achievability: The relative loss from not having a base station with access to all files is 3/2 in this case.The comparison uses the same three-user, cache-size-two, library-size-three setting.

D. Discussions

The rate decomposes into local caching, global caching, and transmission terms. Comparing D2D and base-station schemes shows that spatial reuse and coded multicasting do not provide a fundamental cumulative gain under the paper’s assumptions.

  • R(M) combines a transmission term, a local caching gain, and a global caching gain from coded multicast messages.The local gain reflects cached file fractions, while the global gain makes transmissions useful to multiple users.
  • The comparison interprets spatial reuse as reducing the codeword length of the corresponding coded multicasting scheme.
  • For nM ≫m, the D2D and base-station rate factors are essentially identical in the compared terms.
  • Theorem 4 shows no fundamental cumulative gain from using both spatial reuse and coded multicasting.Under the stated assumptions, spatial reuse may or may not be convenient.

2. A closer look reveals a more subtle tradeoff. Without

The discussion contrasts cluster sizes and coding choices, showing a tradeoff between spatial reuse, coded multicast delivery, and implementation complexity. The proposed approach also extends to multicast-capable peer-to-peer wired networks.

  • The subpacketization-related parameter t may become very large when n and M are large.
  • The coded scheme can achieve throughput close to the uncoded whole-file strategy when clusters are large enough to cache the entire library.In the minimum cluster-size case, each node stores M whole files and delivery serves whole files without coding.
  • Spatial reuse is maximized when codewords have length 1, whereas the proposed coded scheme uses longer codewords.
  • The construction can be applied to multicast-capable peer-to-peer wired networks with limited per-peer storage.Peers can exchange multicast messages useful to many other peers when r ≥ 2.

IV. DECENTRALIZED RANDOM CACHING

The decentralized random-caching scheme combines random MDS-coded placement with coded D2D delivery. It supports decentralized implementation and, under stated conditions, achieves reliable decoding and constant-factor performance.

  • The main drawback of deterministic placement is the need for tight control of user caches to maintain the required stored subpackets.
  • The decentralized random-caching approach is designed to provide greater robustness than deterministic caching.The paper specifically motivates it as more suitable for decentralized implementation and more robust to mobility and nodes turning on or off.
  • Each file packet is divided into K subpackets and encoded into K/ρ MDS-coded symbols before random cache placement.Each user independently samples symbols for every packet according to the decentralized placement algorithm.
  • The delivery scheme sends XORs of requested symbols across user subsets, with users transmitting distinct segments of each coded sequence.For smaller subsets, users directly transmit symbols when no multicasting opportunity remains.
  • With appropriately chosen ρ, users recover requested files from received and cached MDS-coded symbols with high probability.Theorem 7 sets ρ=(1−ε)ρ*, where ρ* is defined through a fixed-point equation; all files decode with arbitrarily high probability for sufficiently large K.
  • For n=3, m=3, and M=2, choosing ε=0.001 gives ρ=0.95 and achievable rate R(2)=0.77.

C. Discussions

The decentralized random scheme approaches deterministic caching in relevant regimes and achieves constant-factor scaling optimality for large networks. The analysis depends on a specified order of limits and on the network parameters.

  • The decentralized random-caching scheme performs approximately as well as centralized deterministic caching in the most relevant parameter regimes.
  • For r ≥ and t > 1, the decentralized approach achieves order-optimal throughput scaling with a constant multiplicative gap as n →∞.
  • The analysis first takes L →∞ and F →∞ before examining rate behavior for large network and library sizes.This order is motivated by typical video-on-demand applications.
  • For large n and m, the multiplicative gap between decentralized random and centralized deterministic caching becomes a constant.
  • Simulation results show that the gap between decentralized random and deterministic caching vanishes as cache size M increases.

V. CONCLUSIONS

The paper develops deterministic and decentralized random caching with coded delivery for infrastructureless, one-hop D2D networks. Across most regimes, both schemes achieve constant-factor optimality, while spatial reuse and coded multicasting do not improve throughput scaling cumulatively.

  • Optimality: Both caching schemes achieve information-theoretic optimality within a constant multiplicative factor in most system-parameter regimes.The result is stated for large network regimes and excludes a specific large-content-reuse, very-small-cache regime.
  • Contributions: The work proposes deterministic centralized caching and decentralized random caching with coded delivery for strictly peer-to-peer D2D networks.The schemes avoid a central omniscient server and use subpacketization and coding during delivery.
  • Optimality: The exception is large content reuse, n > m, with cache capacity M < 1/2; naive multicasting closes this remaining gap.The paper characterizes this regime as less relevant for applications because caching trades device memory for bandwidth.
  • Spatial reuse: When transmission range is restricted to enable concurrent transmissions, spatial reuse does not improve throughput scaling with respect to n, m, and M.It can still improve actual rates through shorter link distances.
  • Spatial reuse: Assessing the practical benefit of spatial reuse requires physical-layer, propagation, rate, and interference modeling beyond the coarse protocol model used here.The paper points to realistic propagation-channel analysis as an example of the needed modeling.
  • Decentralized caching: The decentralized random scheme lets users independently cache coded symbols without knowing which symbols other users have stored.MDS or random linear coding ensures that the distributed cached symbols can recover the files with high probability.

APPENDIX C

The appendix derives converse bounds for worst-case D2D caching demands using cut-set arguments and compares them with achievable rates. It also analyzes spatial reuse and the random-caching recovery condition.

  • Cut-set bounds: The converse constructs periodic demand vectors and applies two types of cuts to lower-bound the worst-case transmission rate.One cut separates a user’s cache and other received messages; another considers subsets of users and demand vectors.
  • Cut-set bounds: The two cut families produce the second and first terms, respectively, in the max-form converse bound of Theorem 2.The converse is tight for the appendix’s first three examples.
  • Gap analysis: The achievable-to-converse multiplicative gap is bounded by analyzing separately the regimes n = ω(m) and n = O(m).The proof further distinguishes cache-size and scaling cases, including M < 1/2.
  • Achievability: For noninteger caching parameter t, resource sharing or the convex lower envelope makes the corresponding achievable operating point attainable.This extends the deterministic scheme beyond integer values of t.
  • Spatial reuse: Under the protocol model, spatial reuse permits multiple concurrent transmissions, and the appendix bounds how many can serve users within a radius-r disk.The resulting throughput expression is obtained by combining local service bounds with concurrency limits.
  • Random caching: The decentralized random scheme independently samples MDS-coded symbols, while the analysis uses a simpler with-replacement selection procedure.The procedure is sufficient to show that the number of distinct cached symbols exceeds K with probability tending to one.
Loading 1405.5336v1…