PaperlayerView exact revision on arXiv

Source-linked AI summary

Cache Placement in Fog-RANs: From Centralized to Distributed Algorithms

Juan Liu, Bo Bai, Jun Zhang, Khaled B. Letaief

arXiv:1710.00784v1eess.SPcs.ITmath.IT

TL;DR

The paper addresses cache placement in Fog-RANs, where users have diverse file preferences and transmission opportunities. It develops centralized and distributed transmission-aware algorithms, with simulations reporting improved delivery performance and comparable average delay for the distributed approach at lower per-BS computation cost.

  • Problem

    Existing cache-placement work has mainly addressed centralized strategies for specific network structures and transmission schemes, while Fog-RANs permit flexible operation and diverse user connections.

    Source: §I · p. 2

  • Method

    The paper develops centralized and distributed cache-placement strategies that account for user preferences and transmission opportunities, using submodular optimization and belief propagation, respectively.

    Source: §I · p. 2

  • Results

    The distributed algorithm achieves average delay performance comparable to the centralized algorithm while requiring much less computation at each BS.

    Source: §VII · p. 10

  • Takeaways & Limitations

    Simulations show that the proposed strategies improve cache-hit probability and provide more flexible cooperative transmission opportunities for users.

    Source: §VII · p. 10

Abstract

from arXiv · show

To deal with the rapid growth of high-speed and/or ultra-low latency data traffic for massive mobile users, fog radio access networks (Fog-RANs) have emerged as a promising architecture for next-generation wireless networks. In Fog-RANs, the edge nodes and user terminals possess storage, computation and communication functionalities to various degrees, which provides high flexibility for network operation, i.e., from fully centralized to fully distributed operation. In this paper, we study the cache placement problem in Fog-RANs, by taking into account flexible physical-layer transmission schemes and diverse content preferences of different users. We develop both centralized and distributed transmission aware cache placement strategies to minimize users' average download delay subject to the storage capacity constraints. In the centralized mode, the cache placement problem is transformed into a matroid constrained submodular maximization problem, and an approximation algorithm is proposed to find a solution within a constant factor to the optimum. In the distributed mode, a belief propagation based distributed algorithm is proposed to provide a suboptimal solution, with iterative updates at each BS based on locally collected information. Simulation results show that by exploiting caching and cooperation gains, the proposed transmission aware caching algorithms can greatly reduce the users' average download delay.

I. INTRODUCTION

Fog-RANs support flexible centralized or distributed operation, but cache-placement research has largely focused on centralized strategies for specific network structures and transmission schemes. This section presents a system model and transmission-aware caching strategies for diverse user preferences and service modes.

I. INTRODUCTION

  • The paper targets Fog-RAN cache placement across centralized and distributed operation, accounting for different user preferences and transmission opportunities.The objective is to improve content-delivery spectrum efficiency.Source: §I · p. 2

II. SYSTEM MODEL

  • Each user may be served by one or multiple BSs, and each finite-capacity BS stores selected files through collaborative cache placement.User preferences and candidate transmission schemes can differ.Source: §I · p. 2, §II · pp. 2–3

1) Non-cooperative Transmission:

  • For non-cooperative transmission, one serving BS sends a cached file directly to its user over the wireless channel.The scheme assumes efficient interference management and a fixed interference-power constraint.Source: 1) Non-cooperative Transmission · p. 3

2) Cooperative Beamforming:

  • For cooperative beamforming, multiple associated BSs can transmit a cached file when instantaneous channel-state information is available.The transmitting BSs may create the beamformer in a distributed way to avoid signaling overhead.Source: 2) Cooperative Beamforming · p. 3

III. PROBLEM FORMULATION FOR CACHE PLACEMENT

This section formulates cache placement as minimizing users’ average download delay under BS storage limits. It evaluates delay for cached and uncached files and identifies the resulting binary optimization problem as generally NP-hard.

III. PROBLEM FORMULATION FOR CACHE PLACEMENT

  • For a cached file, delay is based on the time needed to receive the file from serving BSs over the wireless link.The formulation evaluates average delay under i.i.d. channel coefficients across time slots.Source: §III · p. 3
  • For an uncached file, serving BSs first fetch it from the content server over backhaul links before wireless delivery.The model treats the content-server and backhaul delay as fixed when its impact from caching is negligible.Source: §III · pp. 3–4
  • The objective is to minimize average download delay across users while accounting for different candidate transmission schemes.Each BS is limited to storing at most its capacity Q_m.Source: §III · p. 4
  • The resulting binary cache-placement problem is generally NP-hard, with each BS constrained by its storage capacity.The paper therefore approaches the optimum through centralized and distributed algorithms.Source: §III · p. 4

IV. SUBMODULAR OPTIMIZATION BASED CENTRALIZED CACHE PLACEMENT ALGORITHM

The centralized approach recasts cache placement as monotone submodular maximization under a partition matroid that encodes BS storage limits. A greedy algorithm selects feasible placements by marginal gain, with a stated 1/2 approximation guarantee and O(NMK) worst-case complexity.

IV. SUBMODULAR OPTIMIZATION BASED CENTRALIZED CACHE PLACEMENT ALGORITHM

  • The centralized design reformulates cache placement as monotone submodular maximization under a partition matroid representing per-BS cache capacities.The objective negates the average delay function; each BS's capacity constrains its own subset of placements.Source: §IV · p. 4, A. Matroid Constrained Submodular… · p. 4

A. Matroid Constrained Submodular Optimization

  • The matroid constraint limits each BS to caching up to its capacity, while the ground set groups possible file placements by BS.The ground set is partitioned into disjoint BS-specific sets.Source: A. Matroid Constrained Submodular… · p. 4

B. Centralized Algorithm Design for Cache Placement

The centralized algorithm greedily selects feasible cache placements by marginal gain. For controller-free operation, the paper introduces belief propagation based on a factor graph of delay and capacity functions over cache-placement variables.

B. Centralized Algorithm Design for Cache Placement

  • The centralized algorithm runs in O(NMK) worst-case time and, according to, the greedy algorithm achieves an expected 1/2 ratio of the optimal value in general.The procedure repeats until the marginal value ∆X(s) is zero for all s ∈ S\X or the set Y becomes empty.Source: B. Centralized Algorithm Design for… · p. 5

V. BELIEF PROPAGATION BASED DISTRIBUTED CACHE PLACEMENT ALGORITHM

  • In distributed mode, BSs use belief propagation for cooperative caching, relying on locally collected network and user information and interactions with neighboring BSs.This mode operates without a central controller.Source: §V · p. 5

A. Factor Graph Model for Cache Placement

  • The factor graph represents each cache-placement variable as a variable node and each delay or BS-capacity function as a function node.The underlying problem is transformed into an unconstrained product form using delay-performance and cache-capacity functions.Source: A. Factor Graph Model for Cache… · p. 5

B. Message Passing Procedure for Cache Placement

The message-passing procedure iteratively updates messages between cache-variable and function nodes to approach a solution. Since cache variables are binary, the algorithm passes scalar message ratios in the logarithmic domain to reduce computation and communication overhead.

B. Message Passing Procedure for Cache Placement

1) Message Update :

  • Variable nodes send messages to function nodes, and function nodes return messages that inform beliefs about the cache variables.The two directions are variable-to-function and function-to-variable messages.Source: 1) Message Update · p. 6
  • Because cache variables are binary, scalar message ratios in the logarithmic domain reduce computation and communication overhead.Only half of the messages are calculated and passed, while products become additive operations.Source: 1) Message Update · p. 6

2) Belief Update :

Each cache variable's belief combines its incident messages and drives an estimate that is updated until convergence. In the network implementation, BSs perform the updates locally, exchanging some messages with neighboring BSs.

2) Belief Update :

  • A variable node's belief is the product of its incident messages, and its estimate is updated from that belief in each iteration until convergence.The belief ratio can also be expressed in the logarithmic domain.Source: 2) Belief Update · p. 6

C. Distributed Cache Placement Algorithm

  • When mapped back to the network, message updates occur at BSs, with some messages exchanged between neighboring BSs.For a user served by one BS, that BS computes messages and updates beliefs for its own users.Source: C. Distributed Cache Placement Algorithm · pp. 6–7
  • The distributed algorithm iterates message updates and belief-based variable estimates, checks convergence, and returns an estimate of the cache placement.The procedure initializes messages and uses a sufficiently large iteration limit.Source: C. Distributed Cache Placement Algorithm · p. 7

1) Scenario I:

Scenario II distributes message processing among BSs, with exchanges for shared users; the simulations compare transmission-aware caching with popularity-based baselines.

2) Scenario II:

  • When multiple BSs cover a user, one BS processes that user's message update, and the serving BSs exchange messages over control links.The resulting communication overhead depends on the number of users covered by multiple BSs.Source: 2) Scenario II · p. 7

VI. SIMULATION RESULTS

  • Simulations use 10 BSs, 100 users, 40-s deadlines, and 150-m circular cells spaced 200 m apart.Users are uniformly distributed across the covered area; a random permutation models different request distributions across users.Source: §VI · p. 7
  • Fig. 3 reports average delay and hit probability for γk = 0.65 and N = 1000.Source: Figure 3 · p. 7
  • Non-CoTC uses individual preferences with single-BS service; CoTC selects single- or multi-BS cooperative beamforming by connectivity, while GPC/LPC cache network- or locally popular files.GPC uses network-wide average file popularity; LPC uses the average preferences of users served by each BS.Source: §VI · pp. 7–8

A. Performance Evaluation

Transmission-aware strategies reduce delay relative to popular caching baselines, with cooperative transmission widening the advantage. Approximate preferences preserve performance, the distributed algorithm converges, and its calculation count grows more slowly with cache capacity than the centralized algorithm.

A. Performance Evaluation

  • With heterogeneous popularity skewness, the delay gap over LPC becomes especially significant at small Q, while LPC can trail GPC for Q > 65 under non-cooperative transmission.Under γk = 0.65, the CoTC/Non-CoTC delay gap over LPC is smaller and GPC performs worst.Source: A. Performance Evaluation · p. 8
  • For Q < N, CoTC and Non-CoTC achieve lower average download delay than LPC and GPC; CoTC also outperforms Non-CoTC in delay and hit probability.The comparison is shown for the scenario γk = 0.2 + 4.8 k/K and N = 200.Source: A. Performance Evaluation · p. 8, Figure 4 · p. 9

B. Approximation of File Preferences

  • For 0.3 ≤ γ ≤ 3, average delay falls as γ rises; above 3 it changes little, and averaged file preferences leave only a very small delay gap.The experiment uses Q = 50 and N = 100.Source: B. Approximation of File Preferences · p. 9
  • The distributed algorithm’s average delay fluctuates for dozens of iterations before gradually converging to a suboptimal solution.This convergence behavior is shown for CoTC with N = 100.Source: B. Approximation of File Preferences · p. 9

C. Algorithm Complexity

  • With M = 10, K = 100, and N = 100, centralized calculations rise rapidly with Q, while distributed calculations increase slowly.The paper attributes this difference to Q adding greedy elements and iterations centrally, but changing message values rather than the factor graph in the distributed algorithm.Source: C. Algorithm Complexity · p. 10

VII. CONCLUSIONS

  • Simulations show that the distributed algorithm achieves delay comparable to the centralized algorithm while requiring much fewer calculations at each BS.The proposed algorithms also improve hit probability and provide more flexible cooperative-transmission opportunities.Source: §VII · p. 10

APPENDIX

The appendix derives average download delay by distinguishing cached from uncached requests and accounting for wireless transmission and backhaul delivery.

APPENDIX

  • When a requested file is cached at one or more serving BSs, the BSs transmit it to the user over the wireless channel at a scheme-dependent rate.The proof treats the resulting file-delivery rates across time slots as identically distributed random variables.Source: A. Proof of Theorem 1 · p. 10
  • The delay derivation invokes Wald’s Equation for the random stopping time of completing transmission under the time-varying delivery rates.The proof identifies the stopping time and the nonnegative, identically distributed rate sequence before applying the equation.Source: A. Proof of Theorem 1 · p. 10
  • When no serving BS caches the file, the BSs fetch it from the content server over the backhaul before transmitting it wirelessly to the user.The uncached case includes an extra delivery delay from the content server to the serving BSs.Source: A. Proof of Theorem 1 · p. 10

B. Proof of Theorem 2

The proof establishes that the transformed average-delay function is monotone submodular for candidate transmission schemes. It handles cases where adding a cache element leaves delivery unchanged or changes the achievable rate.

B. Proof of Theorem 2

  • Adding a cache element has no effect when it is outside the user’s serving BSs or already present in the larger cache set considered by the proof.These cases yield zero change in transformed delay.Source: B. Proof of Theorem 2 · p. 11
  • For an element that adds a serving BS, the proof compares its marginal delay change across nested cache sets using the resulting wireless rates.The rate expression accounts for the additional serving BS’s received signal contribution.Source: B. Proof of Theorem 2 · p. 11
  • The transformed average-delay function is monotone submodular, and the property holds for any candidate transmission scheme.The proof uses cooperative beamforming to illustrate the property, then states its generality.Source: B. Proof of Theorem 2 · p. 11

C. Basics of the Message Passing Procedure

The message-passing procedure represents a global objective with a bipartite factor graph and applies max-product updates. Variable and function nodes exchange messages iteratively to seek an optimum in a distributed manner.

C. Basics of the Message Passing Procedure

  • A factor graph is bipartite, with variable nodes and function nodes representing the global function’s factors.The paper writes the global function as a product of function-node terms.Source: C. Basics of the Message Passing… · p. 11
  • Max-product uses the factor graph to seek an optimum of the global function in a distributed manner.The paper points to a tutorial for further details.Source: C. Basics of the Message Passing… · p. 11
  • At each iteration, a variable node sends a message to a neighboring function node based on messages from its other neighboring function nodes.A function node’s return message maximizes its local function multiplied by incident messages over neighboring configurations.Source: C. Basics of the Message Passing… · p. 11

D. Proof of Theorem 4

The proof derives belief-propagation message updates by substituting the average-delay metric and cache-capacity constraint, then forms caching vectors from positive input messages.

D. Proof of Theorem 4

  • Function-node updates maximize over neighboring variable assignments, with separate cases for delay factors η_nk and capacity factors g_m.The proof also derives the β message through a maximization over possible neighboring values.Source: D. Proof of Theorem 4 · p. 11
  • For delay factors η_nk, the update evaluates neighboring assignments with μ_i=1 and with selected neighboring variables set to one.The proof describes the corresponding factor-to-variable message using the average-delay metric.Source: D. Proof of Theorem 4 · p. 11
  • The caching vector selects variable nodes with positive incoming α messages and assigns their associated cache elements to one.The proof identifies these selected elements as the set E+.Source: D. Proof of Theorem 4 · p. 12
  • For a capacity factor, at most Q_m−1 neighboring variables can be cached when μ_i=1, and at most Q_m when μ_i=0.These bounds follow from the cache-capacity constraint.Source: D. Proof of Theorem 4 · p. 12
Loading 1710.00784v1…