PaperlayerView exact revision on arXiv

Source-linked AI summary

A Utility Optimization Approach to Network Cache Design

Mostafa Dehghan, Laurent Massoulie, Don Towsley, Daniel Menasche, Y. C. Tay

arXiv:1601.06838v1cs.NI

TL;DR

Caching must account for the fact that hit probability has different value across contents and service requirements. The paper formulates utility-driven caching, implements it with online algorithms, and shows convergence to optimal solutions while modeling classical policies and controlling capacity violations.

  • Problem

    Traditional caching policies primarily target hit probability and couple contents, making differentiated service difficult when contents have different utility or service requirements.

  • Method

    The paper maximizes aggregate content utility under rigid or elastic cache constraints, using dual optimization, TTL controls, and decentralized online algorithms.

  • Results

    The online algorithms are globally stable and converge to the optimal solution; simulations show cache-capacity violations above 10% below 2.5 × 10^-4 for the evaluated LRU setting.

  • Takeaways & Limitations

    The framework can represent policies such as FIFO and LRU, support fairness-aware caching, and adapt to changing file request rates.

Abstract

from arXiv · show

In any caching system, the admission and eviction policies determine which contents are added and removed from a cache when a miss occurs. Usually, these policies are devised so as to mitigate staleness and increase the hit probability. Nonetheless, the utility of having a high hit probability can vary across contents. This occurs, for instance, when service level agreements must be met, or if certain contents are more difficult to obtain than others. In this paper, we propose utility-driven caching, where we associate with each content a utility, which is a function of the corresponding content hit probability. We formulate optimization problems where the objectives are to maximize the sum of utilities over all contents. These problems differ according to the stringency of the cache capacity constraint. Our framework enables us to reverse engineer classical replacement policies such as LRU and FIFO, by computing the utility functions that they maximize. We also develop online algorithms that can be used by service providers to implement various caching policies based on arbitrary utility functions.

I. INTRODUCTION

The paper motivates utility-driven caching for heterogeneous content and introduces a framework that allocates cache space by maximizing aggregate utility through tunable TTL policies.

  • Rising video traffic makes conventional spectrum expansion and base-station deployment insufficient, while caching reduces bandwidth use, server load, and delay.
  • Heterogeneous service expectations motivate differentiated treatment of content classes, but prior cache approaches can require extra controllers or use storage inefficiently.
  • Utility-driven caching assigns each content a utility based on hit probability and maximizes aggregate utility while trading user satisfaction against storage cost.
  • The framework models existing policies including LRU, LFU, and FIFO as utility-driven caches and relates LRU/FIFO characteristic time to the cache-capacity Lagrange multiplier.
  • Online algorithms are developed and proven to converge to optimal solutions, with simulations evaluating FIFO, LRU, proportionally fair, and max-min fair policies.
  • TTL timers control how long individual or classes of files remain cached, thereby adjusting their hit probabilities.

IV. CACHE UTILITY MAXIMIZATION

The paper formulates cache management as utility maximization over hit probabilities under capacity constraints, then implements the solution with TTL timers derived from the optimization variables.

  • Cache management maximizes the sum of file utilities using formulations with hard or soft capacity constraints.
  • The hard-constraint problem has a unique maximizer because its feasible set is convex and its objective is strictly concave and continuous.
  • TTL caching provides the implementation mechanism by adjusting timers to control different files’ hit probabilities and maximize aggregate utility.
  • The Lagrangian introduces α as the multiplier for cache capacity, and optimal hit probabilities satisfy a condition involving each utility derivative.
  • The multiplier α is determined from the storage constraint through a fixed-point equation, after which timer parameters are computed for non-reset and reset TTL caches.

B. Soft Constraint Formulation

The soft formulation prices additional cache storage, while buffer-violation analysis uses an overprovisioned buffer and concentration bounds to make violations increasingly unlikely.

  • B. Soft Constraint Formulation: The soft formulation replaces the hard capacity constraint with a convex, increasing cost for extra cache storage charged to the file provider.
  • B. Soft Constraint Formulation: The soft optimization restricts hit probabilities to 0 ≤ h_i ≤ 1 and derives optimality conditions and storage through fixed-point equations.
  • C. Buffer Constraint Violations: Buffer violations arise because the hard formulation constrains average occupancy, while the soft formulation has no explicit capacity constraint.
  • C. Buffer Constraint Violations: The proposed remedy provisions B(1 + ϵ) capacity, reserving ϵB space to handle violations while the optimization uses B.
  • C. Buffer Constraint Violations: For content i, X_i indicates cache presence with P(X_i = 1) = h_i, and the expected occupancy is constrained by the sum of hit probabilities.
  • C. Buffer Constraint Violations: A Chernoff-bound argument requires ϵ^2B(N) = ω(1), allowing B(N) = o(N) while ϵ = o(1).
  • C. Buffer Constraint Violations: The same buffer-sizing approach can also be applied to the soft-constraint formulation.
  • V. UTILITY FUNCTIONS AND FAIRNESS: Different utility functions produce different timers and therefore encode different fairness notions for allocating storage among files.

A. Identical Utilities

Identical or parameterized utility functions produce distinct fairness policies, ranging from throughput-maximizing LFU to proportional, minimum-delay, and max-min fairness.

  • TTL implementation: Non-reset and reset TTL implementations use different timer settings to realize the utility-derived policies.
  • Identical utilities: Identical utility functions yield identical hit probabilities for all files, independently of the particular utility function.
  • β-fair utilities: The β-fair utility family uses file weights w_i and unifies multiple fairness notions through the choice of β.
  • β = 0: With β = 0, weighted linear utility yields an allocation that stores the B highest-weight files permanently and excludes the rest.
  • β = 0: Setting w_i = λ_i makes this policy equivalent to LFU and maximizes overall throughput.
  • β = 1: With β = 1, logarithmic utility produces proportional fairness, and w_i = λ_i makes file i’s hit probability proportional to its request arrival rate.
  • β = 2: With β = 2, the utility is associated with minimum potential delay fairness, which prior work links to TCP congestion control.
  • β →∞: As β approaches infinity, the resulting utility maximizes the minimum hit probability and corresponds to max-min fairness.

VI. REVERSE ENGINEERING

The framework reproduces FIFO and LRU hit/miss behavior by selecting utility functions whose optimization conditions match each policy’s hit probabilities. This reverse engineering links cache characteristic time to the capacity-constraint multiplier.

  • Reverse engineering: FIFO and LRU hit/miss behaviors can be duplicated through appropriate utility functions.The construction uses the policies’ hit probabilities and corresponding utility maximization conditions.
  • Reverse engineering: The characteristic time T is a decreasing function of the Lagrange multiplier α for the cache-size constraint.Hit probabilities increase with T, while h_i = U′^-1(α) decreases with α.
  • Reverse engineering: Different choices of the function f(·) yield different utility functions for FIFO and LRU policies.The paper additionally considers the restriction U_i(h_i) = λ_iU_0(h_i).
  • Reverse engineering: For FIFO and LRU, the characteristic time is obtained as T = 1/α before deriving their corresponding utility functions.The policy-specific hit-probability expressions provide the substitution linking T and α.

A. FIFO

The FIFO policy is reverse engineered by matching its characteristic-time hit probability to the utility optimization condition. The resulting utility functions reproduce FIFO and, through the analogous construction, LRU behavior.

  • FIFO: Substituting T = 1/α gives h_i = 1 − 1/(1 + λ_i/α) for the FIFO optimization condition.This expression is then inverted and integrated to obtain the FIFO utility function.
  • LRU: For LRU, substituting h_i = 1 − e^−λ_iT and T = 1/α yields its utility-function derivation.The resulting expression is integrated to obtain the LRU utility function.
  • Validation: The derived utility functions reproduce the correct FIFO and LRU hit probabilities and are believed unique under multiplicative dependence on λ_i.The uniqueness claim is restricted to utilities multiplicative in λ_i.

VII. ONLINE ALGORITHMS

The paper develops online algorithms because offline optimization is infeasible and system parameters may change over time. The algorithms use dual optimization, timer control, and Lyapunov analysis to adapt toward the optimal solution.

  • Motivation: Online algorithms are needed because the optimization cannot feasibly be solved offline and system parameters can change over time.The proposed algorithms adapt using limited collected information.
  • Dual solution: The utility-driven caching problem is convex, so its optimal solution can be approached through the Lagrange dual problem.The dual formulation incorporates cache-capacity constraints using Lagrange multipliers.
  • Dual solution: Timer-based control ensures 0 < h_i < 1, which makes the associated nonnegative boundary multipliers ν_i and η_i equal to zero.The timers are set according to the expressions for reset and non-reset TTL caches.
  • Dual solution: The dual algorithm converges to the optimal solution because D(α) − D(α∗) is a Lyapunov function.Here α∗ denotes the optimal multiplier value.

B. Primal Solution

The primal approach updates hit probabilities through TTL timers, while a combined hit/miss controller can target desired policies. Lyapunov arguments establish convergence for the proposed algorithms, including fairness-oriented implementations.

  • Primal solution: The primal formulation seeks the maximum of W(h) using gradient ascent on hit probabilities.Because hit probabilities are controlled by TTL timers, timer updates move them toward the optimal point.
  • Primal solution: The primal algorithm converges to the optimal solution because W(h∗) − W(h) is a Lyapunov function.The result is stated for h∗, the optimal solution of the primal problem.
  • Fairness: The combined algorithm also converges to the optimal solution using Lyapunov techniques.The convergence claim is stated for the fairness-oriented control algorithm.
  • Hit/miss control: A hit/miss controller increases a file’s timer on a miss and decreases it on a hit.At equilibrium, the resulting hit probability is h_i = δ_m(t_i, α)/(δ_m(t_i, α) + δ_h(t_i, α)).
  • Hit/miss control: The miss and hit adjustments can be selected to achieve desired hit probabilities and caching policies.This provides a policy-control interpretation of the differential-equation formulation.
  • Fairness: Max-min fairness can use the content-agnostic utility U_i(h_i) = log h_i without requiring request arrival rates λ_i.The paper contrasts this with previous approaches that require knowledge of λ_i.

D. Estimation of λi

The paper estimates request rates from TTL timers and evaluates online implementations of four caching policies. Estimation bias affects proportional fairness under the dual algorithm, while the primal-dual approach avoids the observed mismatch.

  • Estimation: Request-rate estimation is needed for most policies when computing timer parameters, although estimation techniques can approximate unavailable rates.The paper notes that these estimates are required for timer computation and can be obtained online.
  • Estimation: The estimator ˆ¯ Xi = ti −ri is a one-sample unbiased estimator of the mean inter-arrival time and of 1/λi.The estimate uses the remaining TTL time and the timer parameter.
  • Simulation setup: The simulations evaluate FIFO, LRU, proportionally fair, and max-min fair policies using B = 1000 expected cached files and N = 104 files.Requests follow a Poisson process with aggregate rate one, and popularities follow a Zipf distribution with s = 0.8.
  • Results: The online dual algorithm reproduces the numerical hit probabilities for FIFO, LRU, and max-min fair policies, but not exactly for proportional fairness.The mismatch is attributed to estimating λi with an estimator that is unbiased for 1/λi but biased for λi.
  • Results: With perfect request-rate knowledge, proportional-fair simulation results exactly match the numerical values under the dual algorithm.This confirms that the earlier mismatch arises from request-rate estimation rather than the policy formulation itself.
  • Results: The primal-dual algorithm matches the numerical proportional-fair values even when estimated request rates are used.The comparison illustrates that algorithm choice can matter for implementing a specific policy.

IX. DISCUSSION

The discussion connects utility-driven caching to monetization, alternative cost models, and practical online implementation. It concludes that the framework models existing policies while decentralized algorithms adapt online, remain stable, and converge optimally, subject to policy- and implementation-specific trade-offs.

  • Monetization: Utility-driven caching can support monetization when content providers do not reveal their utility functions to service providers.The paper decomposes the optimization into provider and service-provider problems and considers pricing cache storage by achieved hit probability.
  • Cost models: The framework can use network-bandwidth costs instead of storage costs, especially for in-network caches with congested links.The discussion proposes defining utility through miss-related costs for applications such as hierarchical caches.
  • Cost models: The utility-driven formulation treats utility as a function of hit probability, while utility based on hit rate remains an open question for fairness.The paper also notes that request-rate pricing and internal bandwidth costs motivate alternative utility definitions.
  • Online algorithms: Algorithm effectiveness depends on the policy, request-rate knowledge, convergence rate, and the choice between reset and non-reset TTL caches.The paper identifies these implementation differences as subjects for further study.
  • Conclusions: The framework models fairness among file groups and existing FIFO and LRU policies under rigid and elastic cache-size constraints.It also connects caching policies with market implications for service providers and content publishers.
  • Online algorithms: Three decentralized online algorithms adapt to changing request rates, are globally stable, and converge to the optimal solution.Simulations illustrate their efficiency and the flexibility of the utility-driven approach.

APPENDIX A STABILITY OF DUAL SOLUTION

The appendix establishes convergence of the dual, primal, and combined system states by constructing Lyapunov functions tied to the optimization objectives. Under the stated hit-probability dynamics and concavity conditions, these functions certify convergence to the optimal solution from any initial condition.

  • Dual solution: V(α) = D(α) − D(α*) is non-negative and equals zero only at α = α*.D(α) has a unique minimizer α*, so the dual Lyapunov function measures the gap from optimality.
  • Dual solution: The dual-system Lyapunov function implies convergence to the optimum from any initial condition.The appendix identifies V(·) as a Lyapunov function for the dual dynamics.
  • Primal solution: W(h) is strictly concave, so it has a unique maximizer h*, and V(h) = W(h*) − W(h) measures the primal optimality gap.The primal Lyapunov function is non-negative and vanishes only at h = h*.
  • Primal solution: The primal-system Lyapunov function implies convergence to h* from any initial condition.This result applies to the primal dynamics associated with the cache-control system.
  • Primal-dual solution: The primal-dual analysis uses a Lyapunov function that is non-negative and zero only at (h*, α*), yielding convergence to the optimum.The combined system therefore converges to the joint optimal state from any initial condition.
Loading 1601.06838v1…