PaperlayerView exact revision on arXiv

Source-linked AI summary

The Throughput-Outage Tradeoff of Wireless One-Hop Caching Networks

Mingyue Ji, Giuseppe Caire, Andreas F. Molisch

arXiv:1312.2637v2cs.IT

TL;DR

The paper asks how caching and local D2D communication can provide scalable service while accounting for outages. It analyzes the throughput-outage tradeoff using random caching and one-hop communication, and finds that in the small-library regime per-user throughput is proportional to M/m and independent of n. This supports turning device memory into bandwidth, although one-hop caching has an inherent limitation.

  • Problem

    The paper studies the throughput-outage tradeoff for D2D one-hop caching networks while accounting for fairness across users and requests.

  • Method

    The paper analyzes independent random caching at user nodes with one-hop D2D communication, deriving outer bounds and achievable scaling laws across system-parameter regimes.

  • Results

    In the small-library regime, per-user throughput is proportional to M/m and independent of n, with the achievable scheme matching coded multicasting in near-optimality.

  • Takeaways & Limitations

    Per-user throughput increases proportionally to cache capacity, allowing D2D one-hop caching networks to turn memory into bandwidth with a straightforward architecture.

  • Takeaways & Limitations

    One-hop networks with caching at user nodes have an inherent limitation.

Abstract

from arXiv · show

We consider a wireless device-to-device (D2D) network where the nodes have pre-cached information from a library of available files. Nodes request files at random. If the requested file is not in the on-board cache, then it is downloaded from some neighboring node via one-hop "local" communication. An outage event occurs when a requested file is not found in the neighborhood of the requesting node, or if the network admission control policy decides not to serve the request. We characterize the optimal throughput-outage tradeoff in terms of tight scaling laws for various regimes of the system parameters, when both the number of nodes and the number of files in the library grow to infinity. Our analysis is based on Gupta and Kumar {\em protocol model} for the underlying D2D wireless network, widely used in the literature on capacity scaling laws of wireless networks without caching. Our results show that the combination of D2D spectrum reuse and caching at the user nodes yields a per-user throughput independent of the number of users, for any fixed outage probability in $(0,1)$. This implies that the D2D caching network is "scalable": even though the number of users increases, each user achieves constant throughput. This behavior is very different from the classical Gupta and Kumar result on ad-hoc wireless networks, for which the per-user throughput vanishes as the number of users increases. Furthermore, we show that the user throughput is directly proportional to the fraction of cached information over the whole file library size. Therefore, we can conclude that D2D caching networks can turn "memory" into "bandwidth" (i.e., doubling the on-board cache memory on the user devices yields a 100\% increase of the user throughout).

I. INTRODUCTION

The paper studies random caching at user nodes combined with one-hop D2D communication, using spatial reuse while allowing some requests to remain in outage. It characterizes the throughput-outage tradeoff and shows that, in the small-library regime, per-user throughput scales with cache capacity rather than user count.

  • Motivation: Wireless traffic growth motivates caching and alternative uses of wireless resources beyond dedicated client-server connections.The introduction highlights asynchronous video-on-demand traffic, underused device storage, and spectrum reuse as relevant design opportunities.
  • Approach: Random independent caching at user nodes and one-hop D2D communication exploit concurrent short-range transmissions instead of coded multicasting.The approach uses spatial reuse and restricts communication to one hop, with outages permitted through network admission control.
  • Comparison: The proposed scheme has a more straightforward practical architecture than coded multicasting and can handle mobility through independent random caching.Its local transmissions exploit spatial reuse, whereas coded multicast transmissions are described as global.
  • Results: In the relevant small-library regime, per-user throughput is proportional to M/m and independent of n.The stated regime includes large n and m with nM ≫ m; throughput increases proportionally with user cache capacity.
  • Implication: The network turns memory into bandwidth because per-user throughput increases proportionally to user-device cache capacity.The paper presents this scaling as attractive when a relatively small library is requested by many users.
  • Results: The paper derives outer bounds and achievable bounds that characterize throughput-outage scaling laws within a small gap of the leading-term constants.The analysis also reports good agreement with finite-dimensional simulations.
  • Problem formulation: The throughput-outage region captures fairness through minimum per-user average throughput and the fraction of users denied service.This contrasts with sum throughput, which can favor serving only a small portion of users while leaving most in outage.

II. NETWORK MODEL AND PROBLEM FORMULATION

The model studies one-hop D2D caching on a grid, with random file-segment requests, randomized cache placement, protocol-model interference, and transmission scheduling. It characterizes throughput–outage behavior through a tradeoff parameter controlling content reuse and spatial reuse.

  • Network and interference model: The network has n user nodes in a unit-area square and m library files, with nodes placed on a grid under the protocol model.The protocol model permits reception within range R only when no interfering transmitter lies within distance (1+∆)R.
  • Caching and requests: Each user independently caches M files sampled with replacement from a common caching distribution over the library.Cache placements are represented by a feasible bipartite graph between users and files.
  • Caching and requests: At request times, each user independently requests an L′-packet segment from a Zipf-distributed file, with a uniformly random starting position.The requested segment is downloaded sequentially from a neighboring node that stores the requested file.
  • Transmission and throughput: The transmission policy schedules feasible independent sets of directed links, while useful throughput counts only transmissions from nodes caching the requested file.Each active link has rate C under the simplifying protocol-model assumption.
  • Throughput–outage tradeoff: The parameter g controls the tradeoff between content reuse and spatial reuse, producing a throughput–outage Pareto boundary that rises initially and eventually reaches unconstrained maximum throughput.As the outage target increases, throughput follows a concave increasing portion before flattening at the unconstrained maximum.

III. OUTER BOUNDS

The outer-bound analysis limits the throughput–outage region across scaling regimes and identifies when fixed outage probabilities can remain feasible. Its practically relevant regime requires the library to remain small relative to aggregate caching memory, where the bounds are tight in scaling order.

  • Outer-bound construction: The analysis provides an outer bound T^ub(p) on the throughput–outage tradeoff under the one-hop restriction.The bound is expressed through ensembles of throughput–outage points across the relevant asymptotic regimes.
  • Scaling regimes: The practically interesting regime is the first regime of Theorem 1; other identified regimes force outage probability toward 1 or provide limited benefit.The paper explicitly distinguishes this regime from the remaining theorem regimes.
  • Scaling regimes: Fixed target outage probabilities p∈[0,1) may be achievable as n,m→∞ in the regime covered by the outer bounds.The stated range in Theorems 2 and 3 begins at p_o,min and extends to 1.
  • Achievable scaling: Throughput–outage points with throughput Ω(M/m) and fixed outage bounded away from 1 are achievable when the outer bound contains zero-outage points of order O(M/m).For κ≤M, choosing β=1/M yields outer-bound points of type (O(M/m),0).
  • Comparison and scope: Caching gains are significant only when the library size m is small relative to aggregate cache memory nM; otherwise conventional base-station unicast has better scaling and zero outage.When asynchronous content reuse is essentially absent, caching does not provide significant throughput gains over conventional unicast.
  • Tightness: The outer bounds are tight in scaling laws, with leading constants determined within constant gaps through an explicit achievability strategy.The paper establishes this by constructing and analyzing a specific strategy.

IV. ACHIEVABLE THROUGHPUT-OUTAGE TRADEOFF

The section constructs an achievable throughput-outage tradeoff using clustered random caching and TDMA spatial reuse, then compares its scaling with outer bounds and alternatives. The resulting throughput laws are tight up to bounded leading-term constants and can scale linearly with cache size in dense regimes.

  • Clustering and transmission policy: The achievability scheme partitions the network into equal-size cooperation clusters and uses independent random caching at each node.Each cluster schedules potential links with equal probability and employs K-color TDMA reuse so same-color clusters transmit concurrently without protocol-model interference.
  • Clustering and transmission policy: Theorem 4 identifies a caching distribution that maximizes the probability that a user's requested file is found within its cluster.The construction then yields an inner bound on the achievable throughput-outage tradeoff.
  • Throughput-outage tradeoff: K m^-α + o(m^-α) is an achievable throughput expression over the stated outage range 1 − aρ1−γ 2 m^-α ≤ p ≤ 1 − ab1−γm^-α.The result applies under the stated positive-parameter and cluster-size conditions.
  • Throughput-outage tradeoff: The achievable throughput scaling coincides with the outer bounds for both outage probabilities bounded away from one and outage probabilities approaching one.Consequently, the scaling laws are tight up to a bounded gap in the constants of the leading terms.
  • Scaling interpretation: When nM ≫ m, per-user throughput increases linearly with M, linking user-side caching and dense spatial reuse to increased throughput.The authors contrast this regime with approaches that rely on scarce bandwidth or dense base-station deployment.
  • Comparison with alternatives: Harmonic Broadcasting requires bandwidth expansion Θ(m log L) and therefore has throughput scaling Θ(1/(m log L)) in the considered regime.This provides an alternative benchmark for comparison with the D2D caching construction.

V. CONCLUSIONS

The paper formulates and tightly characterizes the throughput–outage tradeoff for one-hop D2D caching networks under asynchronous demands and protocol-model wireless interference. In the small-library regime, caching and spatial reuse yield throughput proportional to M/m and independent of n, while the gains arise from local replication rather than network coding.

  • Model: The paper models asynchronous content reuse for popular but independently requested files, with outage when a requested file is unavailable within the allowed transmission range.The network uses one-hop local communication and the Gupta–Kumar protocol model.
  • Tradeoff: The optimal tradeoff is between minimum per-user average throughput and the average fraction of users in outage, characterized by tight scaling laws as n and m grow.The formulation treats outage probability as the average fraction of users in outage.
  • Main result: When m = O(n) and aggregate cache capacity nM exceeds the library size m, per-user throughput is proportional to M/m and independent of n.This is the paper’s main result for the relevant small-library regime.
  • Implications: The resulting system is suited to many users requesting a relatively small set of popular files, including dense urban video-streaming settings.The paper describes examples such as hundreds of popular movies and thousands of users per square kilometer.
  • Implications: The paper concludes that user-device caching can turn memory into bandwidth because per-user throughput increases proportionally with cache capacity M.The authors connect this scaling to the possibility of substantial throughput gains without additional wireless resources.
  • Mechanism: The throughput gain comes from replicating files near users to enable dense spatial reuse, unlike coded multicasting, which creates one message useful to many users.D2D transmissions should be local, whereas coded-multicast transmissions are global; the two gains do not cumulate.

APPENDIX A

The appendix outlines how the throughput–outage region is bounded by parameterizing the problem with disk size and then eliminating that parameter. It combines outage bounds from local file availability with protocol-model bounds on simultaneous transmissions.

  • Proof outline: The proof defines aggregate throughput T_sum as the sum of user throughputs and studies optimal throughput and outage as functions of disk size g.The disk size is the number of nodes in a radius-R disk, while T_sum(g) and p_o(g) describe the corresponding optimum and outage.
  • Proof outline: Varying g produces points that dominate the Pareto boundary of the throughput–outage region.The construction uses lower and upper bounds on outage and throughput for each disk size.
  • Outage bound: The outage lower bound follows because a request can be served only if its file appears in a cache within the disk around the requesting user.The analysis bounds service probability through the local availability event F_u and cache placements within a radius R.
  • Throughput bound: The throughput upper bound uses the protocol model’s separation requirement to limit the number of simultaneously active receivers.Disjoint disks around receivers constrain the number of active links, as illustrated by Fig. 6.

2 R. Now, any of these receivers

The outer-bound analysis maximizes throughput over cluster or disk size and derives the resulting outage-throughput boundary across scaling regimes.

  • The maximum-throughput outer bound is obtained by optimizing the sum-throughput upper bound over g.The optimizer has the form g*=ρ*m^α, with ρ* determined by the stated optimization.
  • The optimized point ((T^ub)*, (p^lb)*) dominates the achievable throughput-outage boundary for all p≥(p^lb)*.
  • The outer-bound regimes are obtained by analyzing different growth rates of the disk size g^R(m).
  • Increasing g beyond g* decreases the outage-probability lower bound.
  • When g=ω(m^α), the relevant throughput-limit term vanishes as the disk size grows rapidly.

APPENDIX C

The appendix derives the optimal caching distribution by formulating a convex optimization over file-caching probabilities and characterizing its unique solution under Zipf demands.

  • The caching distribution P^*_c(f) is chosen to maximize the probability that a user finds its requested file within its cluster.
  • With independent random caching, the cluster discovery probability is 1−(1−P_c(f))^M(g_c(m)−1) for requests to uncached files.
  • The optimization is convex, and KKT conditions characterize the minimizing caching probabilities subject to the sum-probability constraint.
  • The unique solution is identified through an index m* satisfying interval conditions involving the Lagrange multiplier ν and coefficients z_f.
  • Under the Zipf demand assumption, integral bounds are used to evaluate the conditions determining m* as cluster size grows.

APPENDIX D

The achievable tradeoff is derived by bounding the number of active links and good clusters, then optimizing cluster size under different outage targets.

  • For p≥p*o, the achievable tradeoff is obtained with the baseline cluster choice and the corresponding lower throughput bound.
  • For p<p*o, increasing g_c(m) above its baseline value produces lower-outage operating points with corresponding throughput bounds.
  • The symmetric clustering and transmission policies give every user the same average throughput, allowing T_min to be optimized through cluster size.
  • The Paley-Zygmund inequality lower-bounds the probability that a cluster is good by using the first two moments of W.
  • Increasing cluster size can therefore drive outage lower while reducing throughput, with separate regimes determined by the cluster-size scaling.
  • When g_c(m)=ω(m^α), the expected number of good links diverges and P(W>0)=1−o(1).

2) Case gc(m) = ρ1m/M, where ρ1

This case analyzes outage and throughput bounds when the cluster size scales as ρ_1m/M, using direct probability bounds and geometric packing arguments.

  • The resulting argument combines the outage estimate with the geometric transmission bound for this cluster-size regime.
  • The outage calculation uses direct substitution and integral approximations rather than the earlier bounds on ν.
  • The protocol-model geometry partitions the network into squarelets and studies when active-link interference regions intersect them.
  • A squarelet can be consumed when an active receiver lies within the relevant disk, linking receiver geometry to the throughput bound.
  • Disjoint receiver-centered disks and sector packing provide an upper bound on the number of concurrent transmissions.

2 R are disjoint. However,

The proof uses squarelets and sectors to bound how many communication regions can be activated or intersect a receiver’s interference neighborhood. It then applies these geometric bounds to establish the target result.

  • 2 R are disjoint. However: Each sector is treated as an analogue of a squarelet when bounding active regions around receivers.The sector construction transfers the squarelet-based argument to receiver-centered regions.
  • 2 R are disjoint. However: An active receiver u consumes a disk centered at u with radius (1 + Δ)R, while the corresponding activated squarelets or sectors are counted geometrically.The blue regions represent the maximum activated regions caused by u.
  • 2 R are disjoint. However: For an arbitrary node v, the proof distinguishes whether an active receiver lies inside a disk centered at v of the relevant radius.This case distinction connects local receiver geometry to the activation bound.
  • 2 R are disjoint. However: The resulting geometric inequalities are combined using (102) and (103) to prove (101).The final step invokes the preceding bounds rather than introducing a new construction.

APPENDIX G

Appendix G analyzes an optimization over three asymptotic regimes for g and derives the optimal constant through a fixed-point equation. The positive solution lies above α and can be obtained numerically by iteration under the contraction argument.

  • APPENDIX G: The analysis considers g = o(m^α), g = ω(m^α), and g = Θ(m^α) = ρm^α.These are the three asymptotic regimes used for g.
  • APPENDIX G: The optimal constant ρ̃ is computed by maximizing the relevant expression with respect to ρ̃.The proof differentiates the objective and sets the derivative to zero.
  • APPENDIX G: The optimization yields a fixed-point equation x = log(1 + (2 − γ)x), with a non-negative solution for x > α.The solution is associated with x = ρ̃^(2−γ)M^(1−γ).
  • APPENDIX G: The function f(x) = log(1 + (2 − γ)x) − x reaches its maximum at x = α.Its derivative is positive below α, zero at α, and negative above α.
  • APPENDIX G: The positive root of f(x) = 0 is greater than α when 0 ≤ γ < 1.The zero root is excluded because the relevant x is positive.
  • APPENDIX G: Because φ(x) = log(1 + (2 − γ)x) is a contraction for x > α, the fixed point can be solved numerically by iteration.The contraction proof bounds the slope factor below one.

APPENDIX H

Appendix H derives asymptotic bounds by splitting the target expression into separate terms and analyzing them across regimes of γ. The resulting bounds are then combined to obtain the desired scaling behavior.

  • APPENDIX H: The target expression is decomposed into a first and second term before deriving an upper bound.The two terms are treated separately because their scaling requires different case analyses.
  • APPENDIX H: The first term is upper-bounded using Lemma 1, with separate consideration of γ ≠ 1.The appendix then develops bounds for the relevant γ regimes.
  • APPENDIX H: The scaling analysis distinguishes γ < 1, γ > 1/2, and γ = 1/2.These cases determine how the bound is evaluated asymptotically.
  • APPENDIX H: For γ ≠ 1, the appendix introduces g_c(m) = c_1γm^α/M and applies Lemma 1 together with earlier bounds.The resulting estimates are used to settle the scaling behavior of the term P_m*.
  • APPENDIX H: The derived intermediate bounds and case analyses are combined to obtain the desired result.The appendix explicitly concludes that the preceding equations give the desired result.
  • APPENDIX H: The analysis sets g_R(m) = g and defines p = p_lb(g*) = 1 − (Mρ*)^(1−γ)m^(−α).This parameterization is used in the subsequent upper-bound calculation.
Loading 1312.2637v2…