PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning-Based Optimization of Cache Content in a Small Cell Base Station

Pol Blasco, Deniz Gunduz

arXiv:1402.3247v2cs.IT

TL;DR

The paper addresses cache placement in a backhaul-limited small-cell base station when file popularity is unknown and only cached-file demands are observed. It formulates placement as a combinatorial multi-armed bandit problem, proposes learning algorithms, and evaluates their trade-offs and computational approximations. The proposed methods learn effective caching behavior across a wide range of system parameters, with the greedy approximation reaching 99.99% of the B&B solution while being approximately 10^3 times faster.

  • Problem

    Cache placement must maximize traffic served locally despite unknown file popularity and observations limited to demands for cached files.

  • Method

    The paper models cache placement as a combinatorial multi-armed bandit problem and proposes three algorithms balancing exploration and exploitation, alongside a greedy knapsack approximation.

  • Results

    99.99% of the B&B solution is achieved by the greedy approximation, which is approximately 10^3 times faster; the proposed algorithms learn effective caching behavior across varied parameters.

  • Takeaways & Limitations

    The MCUCB and ϵ-greedy algorithms provide practical learning-based cache placement under partial demand observations and outperform the evaluated LRU version.

Abstract

from arXiv · show

Optimal cache content placement in a wireless small cell base station (sBS) with limited backhaul capacity is studied. The sBS has a large cache memory and provides content-level selective offloading by delivering high data rate contents to users in its coverage area. The goal of the sBS content controller (CC) is to store the most popular contents in the sBS cache memory such that the maximum amount of data can be fetched directly form the sBS, not relying on the limited backhaul resources during peak traffic periods. If the popularity profile is known in advance, the problem reduces to a knapsack problem. However, it is assumed in this work that, the popularity profile of the files is not known by the CC, and it can only observe the instantaneous demand for the cached content. Hence, the cache content placement is optimised based on the demand history. By refreshing the cache content at regular time intervals, the CC tries to learn the popularity profile, while exploiting the limited cache capacity in the best way possible. Three algorithms are studied for this cache content placement problem, leading to different exploitation-exploration trade-offs. We provide extensive numerical simulations in order to study the time-evolution of these algorithms, and the impact of the system parameters, such as the number of files, the number of users, the cache size, and the skewness of the popularity profile, on the performance. It is shown that the proposed algorithms quickly learn the popularity profile for a wide range of system parameters.

I. INTRODUCTION

The paper studies cache placement in a backhaul-limited small-cell base station when content popularity is unknown and only cached-file demands are observed. It models learning-based placement with multi-armed bandits, proposes three algorithms, and evaluates their performance and parameter sensitivity numerically.

  • Motivation: Small-cell caching can improve user quality of experience and alleviate scarce backhaul bandwidth by serving popular content locally.Large storage devices allow popular content to be stored and delivered without consuming backhaul capacity.
  • Problem and novelty: The paper addresses cache placement when neither instantaneous demands nor popularity profiles are known in advance, assuming stationary popularity over short time spans.The controller learns by observing instantaneous demands over time.
  • Problem and novelty: The content controller selects cached files to maximize traffic served from the sBS while observing only requests for cached files.This selective-offloading setup sends uncached requests to the macro base station.
  • Contributions: The placement problem is formulated as a multi-armed bandit problem, and three algorithms are proposed to learn the popularity profile and cache suitable files.The algorithms create different exploitation–exploration trade-offs.
  • Contributions: When popularity is known, cache placement becomes a computationally hard knapsack problem, for which the paper proposes a low-complexity approximation based on linear-relaxation structure.The paper also provides numerical results on parameter impacts and the loss caused by unknown popularity.

II. SYSTEM MODEL

The system periodically serves requests from a capacity-limited sBS cache and refreshes its contents using observed cached-file demands. Unknown popularity creates a partial-observation exploration–exploitation problem that the caching policy must optimize over time.

  • System operation: Each period contains a user-request phase followed by a negligible-duration cache-replacement phase based on previously downloaded content.The sBS broadcasts the updated cache list after replacement.
  • System operation: Cached files are served directly by the sBS, while uncached files are downloaded from the macro base station because backhaul capacity is scarce.Only requests served by the sBS are observed by the content controller.
  • Demand model: File demands are modeled as iid random variables with mean θ_f and bounded support [0, U], under identical user popularity and independent user demands.The popularity profile follows a Zipf-like distribution whose skewness is controlled by γ.
  • Optimization objective: The controller chooses cache content from demand history to maximize expected accumulated reward, where fetching file f from the sBS yields reward S_f.The reward represents quality-of-experience gain or macro-system bandwidth alleviation.
  • Optimization objective: With known popularity, the finite-horizon problem decomposes into independent single-period knapsack-like optimization problems; unknown popularity requires estimating unobserved files.An (α, β)-solver returns a solution achieving at least α times optimal reward with probability β.
  • Exploration–exploitation: Because uncached-file rewards cannot be updated, the controller must explore files for information while exploiting files believed to be most popular.The paper introduces three algorithms to balance these competing objectives.

A. Multi-armed bandit problem

The caching problem is connected to multi-armed bandits, where repeated cache choices earn rewards while revealing information about file popularity. The central challenge is balancing exploration of uncertain files against exploitation of promising ones.

  • Bandit formulation: A multi-armed bandit models repeated decisions with partial system knowledge, where actions both accumulate reward and acquire information.Arm rewards have unknown expected means and are estimated from observations.
  • Exploration–exploitation: Exploration samples arms to estimate their rewards reliably, whereas exploitation selects arms with higher expected rewards to increase accumulated reward.The trade-off is fundamental to sequential caching decisions.
  • Evaluation: Bandit regret measures the loss from not knowing the reward profile relative to always selecting the best arm.The objective is to design a policy with small regret.
  • Evaluation: No policy can achieve asymptotic regret smaller than O(log(t)), while UCB achieves regret on the order of O(log(t)) uniformly over t.These results provide a theoretical benchmark for learning performance.

B. MAB for optimal caching: Regret bound

The caching problem is formulated as a combinatorial multi-armed bandit in which cached files are selected as arms and individual demands provide feedback. CUCB explores under-sampled files, with regret growing logarithmically over time.

  • Each file is an arm, and selecting the cache contents corresponds to pulling multiple arms simultaneously.The cache controller chooses a set of files at each period.
  • The problem is a combinatorial MAB because individual instantaneous demands for all cached files are observed.This distinguishes it from linear MAB settings that expose only aggregate rewards.
  • The CUCB perturbation boosts files placed infrequently by increasing their estimated rewards, thereby promoting exploration.The perturbation is additive, its square grows logarithmically with t, and it decreases linearly with T_f.
  • CUCB initializes by caching every file once, then updates demand estimates and observation counts during each period.Its subsequent cache replacement uses perturbed estimates in an optimization step.
  • Regret grows only logarithmically with t, although CUCB may require many iterations to learn the optimal cache content.Prior popularity estimates can avoid CUCB’s initial exploration phase.

C. MAB for optimal caching: Application

The paper compares ε-greedy with a modified CUCB algorithm designed for the cache setting. MCUCB uses the Zipf-like popularity structure and user-level reward observations to adjust exploration toward exploitation.

  • ε-greedy caches the estimated best file set with probability 1−ε and a random file set with probability ε.This creates an explicit exploitation–exploration trade-off.
  • MCUCB modifies CUCB’s perturbation to exploit the Zipf-like popularity distribution and the problem’s structure.The modification is applied in CUCB’s perturbation step.
  • The modified factor promotes exploitation when the Zipf distribution is skewed, with larger γ indicating few popular files.The parameter γ can be empirically approximated from prior work.
  • Larger U also promotes exploitation because each period provides U independent reward realizations.

IV. (α, β)-SOLVER FOR THE SPO-PROBLEM

When popularity is known, the optimal caching problem becomes a binary knapsack problem. File popularity determines values, while file sizes determine weights and cache-capacity feasibility.

  • Known popularity makes the optimal cache content independent of period t because rewards are iid with known means θ_fS_f.
  • The SPO-problem uses a binary indicator x_f to represent whether file f is stored in the cache.The cache-selection variables satisfy binary constraints.
  • The formulation is a knapsack problem with values v_f=θ_fS_f and weights w_f=S_f.Its objective and constraint are linear, but the optimization variables are binary.
  • Because knapsack problems are NP-hard, exact branch-and-bound methods have exponential worst-case complexity, motivating approximate solvers.

A. Approximate solution

The approximate solution relaxes the binary knapsack constraints and exploits the resulting LP structure to construct a greedy cache. Its approximation becomes especially strong for large caches or equal-sized files.

  • Relaxing 0≤x_i≤1 converts the binary knapsack formulation into a linear program solvable in polynomial time.
  • After sorting files by decreasing popularity, the LP solution has consecutive ones, at most one fractional coordinate β, and trailing zeros.
  • Rounding down the LP solution yields a feasible greedy approximation that differs from it in only the fractional element.The greedy procedure caches files sequentially from highest popularity until capacity is reached.
  • Under the regularity condition v_1/w_1≥...≥v_F/w_F, the greedy approximation satisfies δ≤2 and is an (α,β)-solver with α=0.5 and β=1.For Zipf popularity, the paper derives a tighter bound for δ.
  • When M≫s_1, δ≈1 and α≈1; with equal-sized files, the greedy approximation is optimal.

B. Optimal solution: B&B

The paper presents branch-and-bound (B&B) and greedy procedures for solving the single-period optimization problem, both usable as solvers within the MAB caching algorithms.

  • B&B: B&B reduces solution time by pruning feasible-set branches whose upper bounds fall below the best lower bound found so far.Upper bounds are obtained from the linear relaxation, and branches are split iteratively when they cannot be discarded.
  • Use in MAB algorithms: Both greedy and B&B can serve as (α, β)-solvers for the CUCB, MCUCB, and ϵ-greedy caching algorithms.The (α, β)-solver supplies approximate solutions to the single-period optimization problem used by these MAB methods.

V. NUMERICAL RESULTS

Numerical experiments compare MAB caching algorithms with informed upper bounds across time and system parameters. MCUCB learns near-optimal caching quickly, while performance depends on popularity skew, cache size, user count, and file-set size.

  • Solver validation: 99.99% close to B&B’s optimum, the greedy approximation is approximately 10^3 times faster in solution time.B&B finds an optimal SPO solution 95.5% of the time within a 50-second timeout across 2 · 10^4 problems.
  • Time evolution: MCUCB achieves near-optimal performance after 5000 iterations, while ϵ-greedy converges within a constant gap to the IUB optimum.The gap is attributed to ϵ-greedy’s constant exploration factor; greedy and B&B produce insignificant differences for IUB.
  • Popularity profile: When popularity is uniform, all algorithms achieve performance close to 5%, whereas increasing Zipf skew raises MCUCB and ϵ-greedy performance to almost 100%.The 5% baseline corresponds to the relative cache size, and the IUB upper bound follows the same improvement with skewness.
  • Cache size and algorithm comparison: MCUCB outperforms ϵ-greedy for the less-skewed profile γ = 0.56 and estimates file popularity more uniformly.The more skewed the popularity profile, the better ϵ-greedy performs because it estimates the best files especially accurately.
  • Number of users: Low user counts reduce MCUCB and ϵ-greedy performance by 5%, while performance remains steady above 13 sBS users.The reduction is associated with less accurate instantaneous-demand observations.
  • Number of files: With cache capacity fixed at approximately 5% of content size, IUB, MCUCB, and ϵ-greedy performance drops approximately 5% for small F and grows steadily with F.For small F, popular files may not fit into the cache despite the fixed percentage capacity.

VI. CONCLUSIONS

The paper studies cache placement in a backhaul-limited sBS with unknown file popularity, using only observed instantaneous demands for cached files. MCUCB and ϵ-greedy perform better than CUCB and LRU in the studied setting, while CUCB alone guarantees the theoretical logarithmic loss bound.

  • The sBS cache-placement problem assumes unknown file popularity and observes only instantaneous demands for files currently stored in the cache.The sBS provides selective offloading, serving cached high-data-rate content directly while otherwise relying on the backhaul.
  • Theoretical MAB results bound information loss to grow logarithmically over time, but CUCB performs poorly in practical simulations.CUCB satisfies the theoretical bound, yet its practical performance is weak.
  • MCUCB, adapted to the files’ demand distribution, performs significantly better than CUCB.
  • ϵ-greedy performs reasonably well across a wide range of system parameters.
  • MCUCB and ϵ-greedy outperform a version of LRU when only cached-file instantaneous demands are observed.This comparison applies to the case studied in the paper.
Loading 1402.3247v2…