api.cache

cache_miss_rmf(gamma, m, lambda, tspan, x0init, accost)

#ok<INUSL> Computes cache miss rates for RANDOM(m) replacement via refined mean field

This function computes global, per-user, and per-item miss rates for multi-list caches with RANDOM(m) replacement using the DDPP mean field approximation with 1/N correction (refined mean field). The cache occupancy is computed from the aggregate request stream; per-user miss rates weight the per-item miss probabilities by each user’s rates.

Reference: N. Gast, “Expected Values Estimated via Mean-Field Approximation are 1/N-Accurate”, Proc. ACM Meas. Anal. Comput. Syst., 2017.

Parameters:

gamma – Item access factors (used for sizing only)
m – Cache capacity vector
lambda – Arrival rates per user per item per list

Returns:

M – Global miss rate MU: Per-user miss rate MI: Per-item miss rate pi0: Per-item miss probability

Examples

[M, MU, MI, pi0] = cache_miss_rmf(gamma, m, lambda)

XSS is the converged occupancy vector (model_dim x 1, item-major through RMF_INDEX) and WCOV the stationary covariance of the SAME process under the linear noise approximation, i.e. the solution of the Lyapunov equation F’(pi) W + W F’(pi)’ + Q(pi) = 0 that RMF_EXPANSION_STEADY_STATE already solves on the way to the 1/N mean correction. It was discarded there; it is the second moment of the cache occupancy and is what SolverFLD’s moment closure reports for a cache node. WCOV is empty when the refinement did not run (a non-linear access graph has no 1/N path) or when its reduced linear system was singular.

Optional TSPAN = [t0, t1] and initial occupancy X0INIT request the transient mean-field trajectory: integrating the same drift F(x) that RMF_FIXED_POINT drives to steady state, over the finite window. Returns the time grid TOUT, the per-item list-0 occupancy PI0_T (n_items x nt) and the per-user miss-rate trajectory MU_T (u x nt). Omitting TSPAN preserves the original steady-state-only contract.

Optional ACCOST is the per-(user,item) access graph (each an (h+1)x(h+1) matrix): row 1 is miss admission (col 1 = reject, col 1+l = admit to list l), row 1+i is a hit in list i (col 1+b = promote to list b>=i). A non-linear graph modulates admission/promotion per item; the drift then follows the general RANDOM(m) dynamics (RMF_DRIFT_GRAPH) with the plain mean-field fixed point, while the standard linear chain keeps the 1/N-refined path unchanged.

cache_gamma(lambda, R)

Access factors of a multi-list cache over a general access graph

Companion of cache_gamma_lp, which requires the access structure to be a tree and walks the unique parent relation. Here the structure is only required to be reachable: the path to list j is the breadth-first shortest path in the access graph of item i, so a list with several parents is admissible and the first shortest path found in node order is the one taken. Along that path,

gamma(i,j) = (sum_v lambda(v,i,1)) prod_{edges (a,b)} sum_v lambda(v,i,a) R{v,i}(a,b)

THREE DIVERGENCES FROM cache_gamma_lp, all of which change the number, so the two are not substitutes: - the destination of column j is node j, not node 1+j: column 1 therefore has the trivial one-node path and carries no edge factor, where the tree version carries the miss-to-first-list edge; - the leading factor is the aggregate miss-node request rate, whereas the tree version starts the product at one; - each edge factor reads lambda at the source node a alone, whereas the tree version sums lambda(v,i,t) over every t <= a. See _kb/09-ldes-and-cache.md. Use cache_gamma_lp for the access factors a cache solver consumes.

The adjacency is read from user 1 only; the per-user rates are then summed along that one path, so a model whose users route an item differently is analysed on the first user’s graph. An unreachable list gives gamma(i,j)=0.

Parameters:

lambda – (u,n,h+1) request rate of user v for item i while at node t
R – (u,n) cell of (h+1)x(h+1) routing matrices

Returns:

gamma – (n,h) access factors u: Number of users n: Number of items h: Number of lists

Examples

[gamma, u, n, h] = cache_gamma(lambda, R)

cache_ttl_lrua(lambda, R, m, seed)

Computes steady-state probabilities for TTL-LRU cache with arrivals

This function computes the steady-state probability distribution for a TTL-LRU cache system with multiple users, items, and cache levels.

Parameters:

lambda – Arrival rates per user per item per list
R – Routing probability structure
m – Cache capacity vector
seed – (Optional) Random seed for initialization

Returns:

prob – Steady-state probability distribution

Examples

prob = cache_ttl_lrua(lambda, R, m)
prob = cache_ttl_lrua(lambda, R, m, seed)

cache_miss_sfifo_rmf(gamma, m, lambda, tspan, x0init, accost)

#ok<INUSL> Miss rates for strict FIFO(m) replacement via a position-resolved density-dependent population process (DDPP) mean field.

Strict FIFO(m) is NOT equivalent to RANDOM(m)/FIFO(m). Gast and Van Houdt (SIGMETRICS 2015) prove pi_FIFO(m) = pi_RAND(m) exactly but show strict FIFO(m) differs and give it no mean-field model (only trace simulation). The difference is the within-list age ordering: on a hit in list i < h the demoted tail of list i+1 is reinserted at position 1 of list i (positions 1..j-1 shift back), which the per-item per-list occupancy of RANDOM(m) cannot express. This routine tracks x[k,i,j] = P(item k in position j of list i) with deterministic (age-based) demotion/eviction and returns the plain mean-field fixed point; it reduces to the RANDOM(m)/FIFO(m) result when m_1 = … = m_{h-1} = 1 (the strict-FIFO == FIFO degeneracy).

Strict FIFO(m) dynamics (aggregate IRM stream): - miss: insert missed item at position 1 of list 1; list 1 shifts back; tail (position m_1) is evicted. - hit at position j of list i < h: promote that item to position 1 of list i+1 (list i+1 shifts back, tail demoted); demoted tail enters position 1 of list i and positions 1..j-1 of list i shift back. - hit in the top list h: no change.

Reference: N. Gast and B. Van Houdt, “Transient and Steady-state Regime of a Family of List-based Cache Replacement Algorithms”, ACM SIGMETRICS 2015.

Examples

[M, MU, MI, pi0] = cache_miss_sfifo_rmf(gamma, m, lambda)

cache_miss_fifo_rmf(gamma, m, lambda, tspan, x0init, accost)

#ok<INUSL> Miss rates for FIFO(m) replacement via a position-resolved density-dependent population process (DDPP) mean field.

FIFO(m) and RANDOM(m) share the exact stationary distribution (Gast and Van Houdt, SIGMETRICS 2015, Thm 1: pi_FIFO(m) = pi_RAND(m)), so their steady- state hit ratios coincide and SolverFLD serves FIFO steady state from the cheaper RAND(m) refined mean field (cache_miss_rmf). Their mean-field TRANSIENTS differ: FIFO evicts the deterministic tail (residence of exactly m insertions) whereas RANDOM evicts a uniformly random victim (geometric residence), so H(t) from a cold cache ramps differently even though H(inf) agrees. This routine provides that dedicated FIFO transient.

FIFO(m) differs from strict FIFO(m) only in the reinsertion position on a hit: the demoted tail of list i+1 lands at the vacated position j of list i (in place, no within-list shift), whereas strict FIFO reinserts at position 1.

Reference: N. Gast and B. Van Houdt, “Transient and Steady-state Regime of a Family of List-based Cache Replacement Algorithms”, ACM SIGMETRICS 2015.

Examples

[M, MU, MI, pi0] = cache_miss_fifo_rmf(gamma, m, lambda)

cache_ttl_hlru(lambda, m)

Steady-state list occupancy probabilities for an h-LRU cache

Computes the characteristic-time (TTL) approximation of the list-based h-LRU (LRU(m)) replacement policy: h LRU lists of capacities m(1..h), a miss inserts the item at the head of list 1, a hit in list l exchanges the item with the tail of list l+1 (Gast and Van Houdt, SIGMETRICS 2015). Under the approximation each list l has a characteristic time T(l); the level process of an item with request rate lam is a birth-death chain with up-probability 1-e(l) and down-probability e(l), e(l)=exp(-lam*T(l)), giving pi(l) proportional to prod_{s<=l} (1-e(s))/e(s). For h=1 this reduces exactly to the Che approximation for LRU.

Parameters:

lambda – (u x n x h+1) per-class per-item request rates (as built
m – (1 x h) list capacities

Returns:

pij – (n x h+1) probabilities; column 1 = not cached, column

Examples

pij = cache_ttl_hlru(lambda, m)

aggregate the request rate of each item over the user classes; the analyzer replicates the same rate on every list slice, so read slice 2

cache_t_hlru(gamma, m)

Characteristic time of each list of an h-LRU cache

Solves the TTL (characteristic-time) fixed point of the list-based h-LRU (LRU(m)) policy: sum_k pi_l(k;T) = m(l) for each list l, where the level probabilities follow the birth-death form pi_l ~ prod_{s<=l} (1-e_s)/e_s with e_s = exp(-gamma_k*T(s)) (Gast and Van Houdt, SIGMETRICS 2015). Solved by per-list bisection with Gauss-Seidel sweeps; no Optimization Toolbox dependency.

Parameters:

gamma – (n x 1) per-item request rates; an (n x h) matrix is
m – (1 x h) list capacities

Returns:

t – (1 x h) characteristic time of each list

Examples

t = cache_t_hlru(gamma, m)

cache_prob_fpi(gamma, m)

Computes cache hit probabilities using FPI method

This function computes cache hit probability distribution using the fixed-point iteration (FPI) method.

Parameters:

gamma – Item popularity probabilities
m – Cache capacity vector

Returns:

prob – Cache hit probability distribution

Examples

prob = cache_prob_fpi(gamma, m)

FPI method

cache_mva_miss(p, m, R)

Computes cache miss rates using Mean Value Analysis

This function computes global and per-item miss rates for cache models using Mean Value Analysis with given item popularities and routing.

Parameters:

p – Item popularity probabilities
m – Cache capacity vector
R – Routing probabilities

Returns:

M – Global miss rate Mk: Per-item miss rate

Examples

[M, Mk] = cache_mva_miss(p, m, R)

cache_mva(gamma, m)

Performs exact Mean Value Analysis for cache systems

This function computes exact performance metrics for cache systems using Mean Value Analysis with given item popularity probabilities or arrival rates and cache capacity.

Parameters:

gamma – Item popularity probabilities or arrival rates
m – Cache capacity vector (size h for h levels)

Returns:

pi – State probability vector pi0: Miss probability per item pij: Hit probability per item per list x: Throughput vector u: Utilization per item E: Normalizing constant

Examples

[pi, pi0, pij, x, u, E] = cache_mva(gamma, m)

cache_miss_spm(gamma, m, lambda)

Computes cache miss rates using saddle-point approximation

This function computes global, per-user, and per-item miss rates for cache models using the saddle-point method (SPM).

Parameters:

gamma – Item popularity probabilities
m – Cache capacity vector
lambda – (Optional) Arrival rates per user per item

Returns:

M – Global miss rate MU: Per-user miss rate MI: Per-item miss rate pi0: Per-item miss probability lE: Log of normalizing constant

Examples

[M, MU, MI, pi0, lE] = cache_miss_spm(gamma, m, lambda)

M: global miss rate MU: per-user miss rate MI: per-item miss rate

cache_miss_fpi(gamma, m, lambda)

Computes cache miss rates using FPI method

This function computes global, per-user, and per-item miss rates for cache models using the fixed-point iteration (FPI) method.

Parameters:

gamma – Item popularity probabilities
m – Cache capacity vector
lambda – (Optional) Arrival rates per user per item

Returns:

M – Global miss rate MU: Per-user miss rate MI: Per-item miss rate pi0: Per-item miss probability

Examples

[M, MU, MI, pi0] = cache_miss_fpi(gamma, m, lambda)

FPI method

cache_miss_asy(gamma, m, maxiter, tol)

Asymptotic miss ratio of a multi-list cache

The deterministic limit of a multi-list cache: as the item count grows, list l holds exactly the m(l) items of largest effective popularity, so an item’s membership becomes a threshold test rather than a probability. Writing pi(k) for the miss probability of item k, the effective popularity of item j in list l is gamma(l,j)*(1-pi(j)) and the fixed point is

pi(k) = sum_l gamma(l,k) 1{item k outside the top m(l)} / sum_l gamma(l,k),

iterated to a sup-norm tolerance from the uniform start pi = 1/n. The returned scalar is the request-weighted miss ratio sum_{l,k} gamma(l,k) pi(k) / sum_{l,k} gamma(l,k).

INDEX CONVENTION, AND IT IS THE REVERSE OF EVERY OTHER CACHE FUNCTION HERE: gamma is (h,n), LIST-major, whereas cache_spm, cache_erec and cache_miss all take gamma as (n,h), ITEM-major. Callers holding an item-major gamma must transpose. The threshold is strict, so an item exactly at the cutoff is admitted. A degenerate capacity (zero total, or any negative entry) returns 1, i.e. every request misses.

Reference: N. Gast, B. Van Houdt, “Transient and steady-state regime of a family of list-based cache replacement algorithms”, Queueing Syst. 83, 2016.

Parameters:

gamma – (h,n) list-major access factors
m – (1,h) list capacities
maxiter – Cap on fixed-point sweeps (default 1000)
tol – Sup-norm stopping tolerance on pi (default 1e-8)

Returns:

missratio – Request-weighted asymptotic miss ratio

Examples

missratio = cache_miss_asy(gamma, m)
missratio = cache_miss_asy(gamma, m, maxiter, tol)

cache_is(gamma, m, samples, sigma, k)

Computes cache normalizing constant via importance sampling

This function estimates the normalizing constant for cache models using Monte Carlo importance sampling. It provides an alternative to exact enumeration (cache_erec) and saddle-point approximation (cache_spm) that scales better for large item counts while providing confidence bounds.

Parameters:

gamma – Item popularity probabilities (n x h matrix)
m – Cache capacity vector (1 x h)
samples – (Optional) Number of Monte Carlo samples (default: 1e5)

Returns:

E – Normalizing constant estimate lE: Log of normalizing constant

Examples

[E, lE] = cache_is(gamma, m)
[E, lE] = cache_is(gamma, m, samples)

[E, LE] = CACHE_IS(GAMMA, M, SAMPLES, SIGMA, K)

Importance sampling estimation of cache normalizing constant.

The normalizing constant E is defined as the sum over all valid cache configurations of the product of gamma values for items in each level. With item sizes SIGMA and per-list storage cost caps K the estimator carries the feasibility indicator I{S in O} of Casale-Gast (IEEE/ACM ToN, 2021), Sec. IX-B, and returns E(m,k).

Input:: gamma - (n x h) item popularity probabilities at each cache level m - (1 x h) cache capacity vector samples - (optional) number of Monte Carlo samples, default 1e5 sigma - (optional) (1 x n) item storage costs (sizes) k - (optional) (1 x h) per-list storage cost caps
Output:: E - normalizing constant estimate lE - log of normalizing constant

cache_erec(gamma, m, sigma, k)

Computes the normalizing constant for cache models recursively

This function recursively computes the normalizing constant E for cache models with given item popularity probabilities and cache capacity. With item sizes and per-list storage cost caps it evaluates instead the constrained normalizing constant E(m,k) of Casale-Gast (IEEE/ACM ToN, 2021), Sec. IX, using the recursion E(m,k) = E_i(m,k) + sum_j m_j gamma_ij E_i(m-1_j, k-sigma_i 1_j) with the extra boundary E(m,k)=0 whenever some k_j is negative.

Parameters:

gamma – Item popularity probabilities
m – Cache capacity
sigma – (Optional) item storage costs (sizes), 1 x n, positive integers
k – (Optional) per-list storage cost caps, 1 x h, non-negative integers

Returns:

E – Normalizing constant

Examples

E = cache_erec(gamma, m)
E = cache_erec(gamma, m, sigma, k)

cache_cost_pathcheck(gamma, sigma, k, parent)

Detects promotion paths blocked by storage cost caps

The constrained normalizing constant E(m,k) of Casale-Gast (IEEE/ACM ToN, 2021), Sec. IX, sums the product form over every size-feasible cache state. Under RR-C(m) an item only reaches list j by being promoted along the path from the miss list to j, one list at a time, so a cap on an intermediate list can make size-feasible states unreachable. When that happens the size-feasible set is no longer a single recurrent class and E(m,k) normalizes over states the cache never visits.

This routine reports each (item, list) pair that is size-feasible for the list but blocked on the way to it. An empty report is a necessary, not sufficient, condition: a list of capacity above one may still be unreachable when its cap admits no combination containing the item.

Parameters:

gamma – Item access factors (n x h)
sigma – Item storage costs (sizes), 1 x n
k – Per-list storage cost caps, 1 x h
parent – Parent list of each list, 1 x h, 0 for lists rooted in the miss list

Returns:

viol – Matrix of blocked pairs, one row [item, list, blockinglist]

See also

cache_erec()

Examples

viol = cache_cost_pathcheck(gamma, sigma, k, parent)

cache_cost(gamma, m, sigma, k, pij)

Computes the mean storage cost held by each cache list

Evaluates K_j = sum_i sigma_i pi_ij, the expected storage cost of the items resident in list j at steady state, as defined in Casale-Gast (IEEE/ACM ToN, 2021), Sec. IX. With no cost caps supplied the same expression still applies and reports the mean cost of the unconstrained model.

Parameters:

gamma – Item popularity probabilities (n x h)
sigma – Item storage costs (sizes), 1 x n
m – Cache capacity vector, 1 x h
k – (Optional) per-list storage cost caps, 1 x h
pij – (Optional) precomputed occupancy matrix, n x (h+1) with column 1 the miss probability

Returns:

K – Mean storage cost of each list, 1 x h pij: Occupancy matrix used, n x (h+1)

See also

cache_prob_erec()

Examples

[K,pij] = cache_cost(gamma, m, sigma)
[K,pij] = cache_cost(gamma, m, sigma, k)
[K,pij] = cache_cost(gamma, m, sigma, k, pij)

cache_pos_drift_graph(x, p, G, m, n, h, slots, sidx, S, reinsert)

Position-resolved DDPP drift with a per-item access graph.

G{k} is the (h+1)x(h+1) access graph of item k: row 1 is miss admission (col 1 = reject, col 1+l = admit to list l), row 1+i is a hit in list i (col 1+b = promote to list b>=i; b==i means STAY in place, the FIFO/SFIFO convention). A miss admits at the head of the target list (its tail evicted); a hit at position j of list i promotes to the head of target b>i (the tail of b demoted to list i – to the vacated position j for FIFO, to the head with a 1..j-1 shift for SFIFO). REINSERT is ‘head’ (SFIFO) or ‘pos’ (FIFO). Reduces exactly to the linear drift when G is the standard chain; requires a cold (empty) initial state so non-admissible items drain.

cache_build_item_graphs(accost, lambda, n, h)

Build per-item (h+1)x(h+1) access graphs from ACCOST.

ACCOST is the per-(user,item) access graph cell{v,k} (each an (h+1)x(h+1) matrix). Returns a 1xN cell of per-item graphs aggregated over users by request rate, or {} when ACCOST is absent or the standard linear chain (so the caller keeps the refined/linear path). Row 1 is miss admission, row 1+i a hit in list i.

cache_ttl_lrum_map(D0c, D1c, m)

Request-weighted hit/miss probabilities for LRU(m) with MAP requests

Front-end of the Gast-Van Houdt (Performance Evaluation 2017) TTL approximation for LRU(m) caches whose items have Markovian arrival process request streams. Intended for items with genuinely distinct or correlated request processes (e.g. marked MAP arrivals); when items are i.i.d. marks of a common stream the request sequence is IRM and the Poisson-based TTL approximations already apply.

Parameters:

D0c – Cell (1,n); D0c{k} is the (d,d) hidden-transition matrix of item k
D1c – Cell (1,n); D1c{k} is the (d,d) arrival matrix of item k
m – Cache capacity vector (1,h)

Returns:

pij – (n,h+1) request-weighted probabilities; column 1 is the pijtime: (n,h+1) time-stationary level occupancy probabilities

Examples

[pij, pijtime] = cache_ttl_lrum_map(D0c, D1c, m)

cache_t_lrum_map(D0c, D1c, m)

Characteristic times for the LRU(m)-MAP TTL approximation

TTL approximation of LRU(m) with per-item Markovian arrival processes (Gast and Van Houdt, Performance Evaluation 2017, Section 3.1.2). Each item is modeled by an embedded Markov chain over (list, phase) states; the level vectors obey pi_l = pi_0 prod_s R_s with the R-recursions of eqs. (6)-(7) and pi_0 the left Perron vector of R_1 expm(D0 T_1). The characteristic times T_1..T_h equate the expected occupancy of each list to its capacity; the joint root is found by fsolve on log(T).

Parameters:

D0c – Cell (1,n); D0c{k} is the (d,d) hidden-transition matrix of item k
D1c – Cell (1,n); D1c{k} is the (d,d) arrival matrix of item k
m – Cache capacity vector (1,h)

Returns:

t – Characteristic time of each list (1,h)

Examples

t = cache_t_lrum_map(D0c, D1c, m)

cache_lrum_map_levelstats(D0, D1, T)

Level statistics of one item’s embedded (list, phase) chain

Evaluates eqs. (5)-(9) of Gast and Van Houdt (Performance Evaluation 2017) for a single item with MAP request process (D0, D1) and characteristic times T: the R-recursions of the embedded chain, the level-0 boundary vector pi_0 (left Perron vector of R_1 expm(D0 T_1)), the time-stationary level probabilities, and the request-weighted hit fractions per list.

Returns:: prob – (1,h+1) time-stationary probability of level 0..h occ: (1,h) occupancy contribution of lists 1..h (= prob(2:end)) hitfrac: (1,h) fraction of the item’s requests hitting in list l

Examples

[prob, occ, hitfrac] = cache_lrum_map_levelstats(D0, D1, T)

cache_xi_iter(gamma, m, tmax)

Computes Lagrange multipliers using Gast-van Houdt fixed-point iteration

This function computes Lagrange multipliers for cache models using the Gast-van Houdt algorithm fixed-point iteration method.

Parameters:

gamma – Item popularity probabilities
m – Cache capacity
tmax – (Optional) Maximum time limit

Returns:

z – Converged Lagrange multipliers

Examples

z = cache_xi_iter(gamma, m)
z = cache_xi_iter(gamma, m, tmax)

cache_xi_fp(gamma, m, xi)

Computes cache performance metrics using fixed-point iteration

This function uses fixed-point iteration to compute cache performance metrics including Lagrange multipliers, miss probabilities, and hit probabilities for given item popularity and cache capacity.

Parameters:

gamma – Item popularity probabilities
m – Cache capacity
xi – (Optional) Initial guess for Lagrange multipliers

Returns:

xi – Converged Lagrange multipliers pi0: Miss probability per item pij: Hit probability per item per list it: Number of iterations

Examples

[xi, pi0, pij, it] = cache_xi_fp(gamma, m)
[xi, pi0, pij, it] = cache_xi_fp(gamma, m, xi)

cache_spm(gamma, m, xi0)

Computes normalizing constant using saddle-point approximation

This function computes the normalizing constant for cache models using the saddle-point method (SPM) for approximation.

Parameters:

gamma – Item popularity probabilities
m – Cache capacity vector
xi0 – (Optional) Initial guess for Lagrange multipliers

Returns:

Z – Normalizing constant lZ: Log of normalizing constant xi: Lagrange multipliers

Examples

[Z, lZ, xi] = cache_spm(gamma, m)
[Z, lZ, xi] = cache_spm(gamma, m, xi0)

cache_rrm_meanfield_ode(~, x, lambda, m, n, h)

Computes ODE dynamics for RRM mean-field cache model

This function defines the ODE system for the Random Replacement Model (RRM) mean-field cache dynamics.

Parameters:

t – Time variable (unused)
x – State vector
lambda – Arrival rates per item
m – Cache capacity vector
n – Number of items
h – Number of cache levels

Returns:

dxdt – Time derivative of state vector

Examples

dxdt = cache_rrm_meanfield_ode(t, x, lambda, m, n, h)

Reshape state vector to matrix form: x_{k,s}

cache_rrm_meanfield: Parameters

cache_prob_spm(gamma, m, lE)

Computes cache hit probabilities using saddle-point approximation

This function computes cache hit probability distribution using the saddle-point method (SPM) for approximation.

Parameters:

gamma – Item popularity probabilities
m – Cache capacity vector
lE – (Optional) Pre-computed log of normalizing constant

Returns:

prob – Cache hit probability distribution

Examples

prob = cache_prob_spm(gamma, m)
prob = cache_prob_spm(gamma, m, lE)

cache_spm_size(gamma, m, sigma, k, costmode)

Approximates the cost-constrained cache normalizing constant E(m,k) by the ray expansion

Evaluates the geometrical-optics (WKB) asymptotic expansion of the cost-capped normalizing constant computed exactly by cache_erec(gamma,m,sigma,k), and returns it in the SAME normalization, so that the two are interchangeable. This is the item-size extension of retrieval_rayint, which carries the size-free expansion; call that one when there are no storage costs.

Writing E = prod_j m_j! * H, the size-free recursion E(m,n) = E(m,n-1) + sum_j gamma_{n,j} m_j E(m-1_j,n-1), E(0,0)=1 relaxes to H ~ exp(phi/eps) with n = y/eps, m_j = x_j/eps, whose eikonal e^{phi_y} = 1 + sum_j gamma_j(y) e^{-phi_j} carries the ray constants xi_j = e^{-phi_j}. With per-item storage costs sigma_i and per-list cost caps k_j the recursion gains the cost coordinate, E(m,k) = E_i(m,k) + sum_j m_j gamma_ij E_i(m-1_j, k-sigma_i 1_j), so the shift 1_j becomes e_j(y) = (1_j, s(y) 1_j) in the enlarged space X = (x,kappa) and the eikonal picks up the size tilt e^{phi_y} = 1 + sum_j gamma_j(y) e^{-phi_{x_j} - s(y) phi_{kappa_j}}, with the second family of ray constants zeta_j = e^{-phi_{kappa_j}}. The rays integrate to the discrete saddle point of the product generating function sum_{m,k} H(m,k) prod_j z_j^{m_j} w_j^{k_j} = prod_i ( 1 + sum_j gamma_ij z_j w_j^{sigma_i} ), namely, with D_i = 1 + sum_j gamma_ij xi_j zeta_j^{sigma_i} and Psi = sum_i log D_i, m_j = sum_i gamma_ij xi_j zeta_j^{sigma_i} / D_i, k_j = sum_i sigma_i gamma_ij xi_j zeta_j^{sigma_i} / D_i, log H(m,k) ~ Psi - sum_j m_j log xi_j - sum_j k_j log zeta_j - (d/2) log(2 pi) - (1/2) log det grad^2 Psi, where d is the number of saddle coordinates and, with pi_ij = gamma_ij xi_j zeta_j^{sigma_i} / D_i and Q^i_{jl} = delta_{jl} pi_ij - pi_ij pi_il, grad^2 Psi = sum_i [1; sigma_i] [1; sigma_i]’ (x) Q^i . Setting zeta_j = 1 recovers the size-free expansion exactly.

CAPS ARE CUMULATIVE. cache_erec sums over the states of cost AT MOST k_j, so this function does the same by default (‘atmost’). The shadow price eta_j = log zeta_j <= 0 obeys complementary slackness: a list whose unconstrained mean cost already meets its cap is SLACK, keeps zeta_j = 1, and drops out of the saddle, which then degenerates continuously to the size-free expansion; a list whose cap BINDS sits at eta_j < 0, and the states below the boundary decay geometrically with ratio zeta_j, contributing the amplitude factor 1/(1-zeta_j). Pass ‘exact’ to obtain instead the constant resolving the cost exactly at k_j, which is the raw Laplace formula above with no such factor.

SIZE DIVERSITY IS REQUIRED. The Hessian integrand [1;sigma_i][1;sigma_i]’ (x) Q^i has rank h, not 2h, so grad^2 Psi is nonsingular only if the sizes actually vary. This is not an artefact: with a single item size the cost of list j is sigma*m_j identically and the cap carries no information. That case is detected and answered exactly (slack, or zero when the cap cannot be met) rather than passed to a singular saddle. If the sizes share a common divisor the cost lives on a sublattice; the sizes and caps are divided through by their gcd, which is an exact reduction and removes the corresponding lattice factor.

OCCUPANCY. out.pij is the saddle occupancy pi_il = gamma_il zeta_l^{sigma_i} xi_l / D_i and out.K its per-list cost. These are EXACT-COST quantities: the saddle conditions are sum_i pi_ij = m_j and sum_i sigma_i pi_ij = k_j, so out.K equals the cap exactly on every binding list. Under cumulative caps the true mean cost is strictly below the cap; use cache_cost and cache_prob_erec for that.

ACCURACY. The expansion is O(1/n) at fixed occupancy. With a well-separated cap the observed error in log E is around 1e-2 at n = 200 and halves at each doubling of n. It degrades as a binding zeta_j approaches 1, i.e. in the transition between the binding and slack regimes, where the geometric resummation 1/(1-zeta_j) is no longer sharp; out.zeta and out.binding report where the saddle sits and a warning is raised inside that region.

Parameters:

gamma – Item popularity probabilities (access factors), n x h
m – Cache list capacities, 1 x h
sigma – Item storage costs (sizes), 1 x n, positive integers
k – Per-list storage cost caps, 1 x h, non-negative integers
costmode – (Optional) ‘atmost’ (default, matches cache_erec) or ‘exact’

Returns:

E – Normalizing constant, same normalization as cache_erec (Inf on overflow; use logE) logE: Natural logarithm of E, safe for large n out: Struct with xi, zeta, binding, pij, K, phi, logdetSigma, span, method, relerrEst, iter

Examples

E = cache_spm_size(gamma, m, sigma, k)
E = cache_spm_size(gamma, m, sigma, k, costmode)
[E, logE, out] = cache_spm_size(...)

References

G. Casale, N. Gast, “Performance Analysis Methods for List-Based Caches With Non-Uniform Access”, IEEE/ACM Trans. Networking 29(2), 2021 (product form and the cost-capped recursion, Sec. IX); G. Casale, “Accelerating Performance Inference over Closed Systems by Asymptotic Methods”, ACM SIGMETRICS, 2017 (the asymptotic expansion of the normalizing constant integral).

cache_miss_is(gamma, m, lambda, samples, sigma, k)

Computes cache miss rates using importance sampling

This function computes global, per-user, and per-item miss rates for cache models using Monte Carlo importance sampling.

Parameters:

gamma – Item popularity probabilities (n x h matrix)
m – Cache capacity vector (1 x h)
lambda – Arrival rates per user per item (u x n x h+1)
samples – (Optional) Number of Monte Carlo samples (default: 1e5)

Returns:

M – Global miss rate MU: Per-user miss rate (u x 1) MI: Per-item miss rate (n x 1) pi0: Per-item miss probability (1 x n) lE: Log of normalizing constant

Examples

[M, MU, MI, pi0, lE] = cache_miss_is(gamma, m, lambda)
[M, MU, MI, pi0, lE] = cache_miss_is(gamma, m, lambda, samples)

[M, MU, MI, PI0, LE] = CACHE_MISS_IS(GAMMA, M, LAMBDA, SAMPLES, SIGMA, K)

Importance sampling estimation of cache miss rates.

Input:: gamma - (n x h) item popularity probabilities m - (1 x h) cache capacity vector lambda - (u x n x h+1) arrival rates per user per item per level samples - (optional) number of Monte Carlo samples, default 1e5 sigma - (optional) (1 x n) item storage costs (sizes) k - (optional) (1 x h) per-list storage cost caps
Output:: M - global miss rate MU - per-user miss rate MI - per-item miss rate pi0 - per-item miss probability lE - log of normalizing constant

cache_gamma_lp(lambda, R)

Computes gamma parameters for cache models

This function computes item popularity probabilities at each cache level using a linear programming approach based on arrival rates and routing probabilities.

Parameters:

lambda – Arrival rates per user per item per list
R – Routing probability structure

Returns:

gamma – Item popularity probabilities at each level u: Number of users n: Number of items h: Number of cache levels parent: Parent list of each list, 1 x h, with 0 for the lists rooted in the miss list

Examples

[gamma, u, n, h] = cache_gamma_lp(lambda, R)
[gamma, u, n, h, parent] = cache_gamma_lp(lambda, R)

mexify_cache

@brief MATLAB Coder script to generate MEX functions for cache_ module.

This script generates MEX (MATLAB Executable) versions of cache_ functions for improved performance. Cache functions compute hit/miss probabilities and normalizing constants for cache replacement models.

Skipped functions (Coder-incompatible):: cache_mva - State.cartesian() OOP dependency cache_t_hlru - nested bisection helper (function handles) cache_ttl_lrua - fsolve() + rng() + function handles cache_rrm_meanfield - ode23s() script (not a function)

See also CODER, CODER.CONFIG, CODER.TYPEOF, CODEGEN.

cache_prob_is(gamma, m, samples, sigma, k)

Computes cache hit probabilities via importance sampling

This function estimates cache hit probability distribution using Monte Carlo importance sampling. For each item i, it estimates the probability that item i is cached at level j (hit) or not cached (miss).

Parameters:

gamma – Item popularity probabilities (n x h matrix)
m – Cache capacity vector (1 x h)
samples – (Optional) Number of Monte Carlo samples (default: 1e5)

Returns:

prob – Cache hit probability distribution (n x h+1 matrix)

Examples

prob = cache_prob_is(gamma, m)
prob = cache_prob_is(gamma, m, samples)

PROB = CACHE_PROB_IS(GAMMA, M, SAMPLES, SIGMA, K)

Importance sampling estimation of cache hit probabilities.

With item sizes SIGMA and per-list storage cost caps K the sampler discards states that violate a cap, which is the feasibility indicator I{S in O} of Casale-Gast (IEEE/ACM ToN, 2021), Sec. IX-B.

Input:

gamma - (n x h) item popularity probabilities at each cache level m - (1 x h) cache capacity vector samples - (optional) number of Monte Carlo samples, default 1e5 sigma - (optional) (1 x n) item storage costs (sizes) k - (optional) (1 x h) per-list storage cost caps

Output:

prob - (n x h+1) hit probability matrix: prob(i,1) = miss probability for item i prob(i,1+j) = hit probability for item i at cache level j

cache_prob_erec(gamma, m, sigma, k)

Computes cache hit probabilities recursively

This function computes cache hit probability distribution using a recursive method based on normalizing constants.

Parameters:

gamma – Item popularity probabilities
m – Cache capacity vector
sigma – (Optional) item storage costs (sizes), 1 x n
k – (Optional) per-list storage cost caps, 1 x h

Returns:

prob – Cache hit probability distribution

Examples

prob = cache_prob_erec(gamma, m)
prob = cache_prob_erec(gamma, m, sigma, k)

cache_miss(gamma, m, lambda, sigma, cap)

Computes miss rates for a cache system

This function computes various miss rate metrics for a cache system with given item popularity distribution and cache capacity.

Parameters:

gamma – Item popularity probabilities
m – Cache capacity
lambda – (Optional) Arrival rates per user per item
sigma – (Optional) item storage costs (sizes), 1 x n
k – (Optional) per-list storage cost caps, 1 x h

Returns:

M – Global miss rate MU: Per-user miss rate MI: Per-item miss rate pi0: Per-item miss probability

See also

cache_erec()

Examples

[M,MU,MI,pi0] = cache_miss(gamma, m)
[M,MU,MI,pi0] = cache_miss(gamma, m, lambda)
[M,MU,MI,pi0] = cache_miss(gamma, m, lambda, sigma, k)

M: global miss rate MU: per-user miss rate MI: per-item miss rate pi0: per-item miss probability