cache_ttl_hlru.h File Reference

TTL (characteristic-time) approximation of an h-LRU / LRU(m) cache. More...

#include <cstddef>
#include <vector>
#include "line/api/cache/cache_t_hlru.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for cache_ttl_hlru.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
Matrix< T >	line::cache::cache_ttl_hlru (const Matrix< T > &lambda, const std::vector< int > &m)
	TTL (characteristic-time) approximation of an h-LRU / LRU(m) cache.

Detailed Description

TTL (characteristic-time) approximation of an h-LRU / LRU(m) cache.

Templated port of matlab/src/api/cache/cache_ttl_hlru.m, cross-checked against jar/src/main/java/jline/api/cache/Cache_ttl_hlru.java.

The policy is h LRU lists of capacities m(1..h): a miss inserts the item at the head of list 1 and a hit in list l exchanges it with the tail of list l+1. Under the characteristic-time approximation the level 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)), so

pi(l) proportional to prod_{s<=l} (1 - e(s))/e(s),

with the times T solved from the capacity constraints by cache_t_hlru. For h = 1 this is exactly the Che approximation of LRU, so an M/LRU/1 cache can be checked against the closed form 1 - exp(-lam T) directly.

ARITHMETIC: transcendental, as cache_t_hlru.

The MATLAB reference takes lambda as the (u x n x h+1) array built by solver_mva_cache_analyzer and sums slice min(2,h+1) over the user classes; that slice carries the same per-item rate as every other one. The port takes that slice directly as a (u x n) matrix, which is the same reduction without the three-dimensional container.

Definition in file cache_ttl_hlru.h.