Package jline.api

Class CACHE

java.lang.Object
jline.api.CACHE
public class CACHE extends Object
APIs for stochastic models of caches

  • Constructor Details

    • CACHE

      public CACHE()

  • Method Details

    • cache_gamma_lp

      public static Ret.cacheGammaLp cache_gamma_lp(Matrix[] lambda, Matrix[][] R)
      Computes access factors for the cache.
      Parameters:
      lambda - - Matrix array representing request arrival rates from users to items of individual lists.
      R - - 2D Matrix array representing the reachability graph of a list for different streams and items.
      Returns:
      cacheGammaLpReturn - An object containing access factors (gamma), the number of users (u), the number of items (n), and the number of lists (h).

    • cache_mva

      public static Ret.cacheMVA cache_mva(Matrix gamma, Matrix m)
      Exact recursive solution of the caching model.
      Parameters:
      gamma - - Matrix representing access factors for item i to access list j.
      m - - Matrix representing the cache capacity vector.
      Returns:
      cacheMVAReturn - An object containing cache state probabilities at equilibrium and other related metrics. Reference: Giuliano Casale, Nicolas Gast. Performance analysis methods for list-based caches with non-uniform access. IEEE/ACM Transactions on Networking, 2020, pp.1-18, for details.

    • cache_t_lrum

      public static Matrix cache_t_lrum(Matrix gamma, Matrix m)
      Computes the characteristic time of each list in the TTL approximation of LRU(m).
      Parameters:
      gamma - - Matrix representing access factors for items across different levels.
      m - - Matrix representing cache capacity vector.
      Returns:
      Matrix - A matrix containing the computed characteristic times.

    • cache_ttl_lrum

      public static Matrix cache_ttl_lrum(Matrix[] gamma, Matrix m)
      Solve multi-list least-recently-used caches LRU(m) using the TTL approximation.
      Parameters:
      gamma - - Array of matrices representing access factors for items across different lists.
      m - - Matrix representing cache capacity vector.
      Returns:
      Matrix - A matrix containing the computed probabilities for the cache.

    • cache_ttl_hlru

      public static Matrix cache_ttl_hlru(Matrix[] lambda, Matrix m)
      Solve hierarchical least-recently-used caches h-LRU using the TTL approximation.
      Parameters:
      lambda - - Array of matrices representing request arrival rates from users to items of individual lists.
      m - - Matrix representing cache capacity vector.
      Returns:
      Matrix - A matrix containing the computed steady-state probabilities for the cache.

    • cache_t_hlru_aux

      public static Matrix cache_t_hlru_aux(double[] x, Matrix gamma, Matrix m, int n, int h)
      Auxiliary function for cache_t_hlru inner optimization.
      Parameters:
      x - - Array of double values representing certain parameters for the computation.
      gamma - - Matrix representing access factors for items across different levels.
      m - - Matrix representing cache capacity vector.
      n - - Integer representing the number of items.
      h - - Integer representing the number of levels.
      Returns:
      Matrix - A matrix containing the computed objective function.

    • cache_t_hlru

      public static Matrix cache_t_hlru(Matrix gamma, Matrix m)
      Computes the characteristic time of each list in the TTL approximation of h-LRU.
      Parameters:
      gamma - - Matrix representing access factors for items across different levels.
      m - - Matrix representing cache capacity vector.
      Returns:
      Matrix - A matrix containing the computed TTL values.

    • hlruTime

      public static Matrix hlruTime(double[] x, Matrix gamma, Matrix m, int n, int h)

    • cache_ttl_lrum_map

      public static Matrix cache_ttl_lrum_map(Matrix[][] D0Matrix, Matrix[][] D1Matrix, Matrix m)

    • cache_ttl_lrua

      public static Matrix cache_ttl_lrua(Matrix[] lambda, Matrix[][] R, Matrix m)

    • cache_prob_asy

      public static Matrix cache_prob_asy(Matrix gamma, Matrix m)
      Estimate asymptotic values of the cache state probabilities at steady-state.
      Parameters:
      gamma - - Matrix representing the cache access factors.
      m - - Matrix representing the cache capacity vector.
      Returns:
      Matrix - A matrix containing the estimated cache state probabilities at equilibrium.

    • cache_xi_fp

      public static Ret.cacheXiFp cache_xi_fp(Matrix gamma, Matrix m, Matrix xi)
      Estimate cache xi terms using a fixed-point algorithm. The xi terms represent duals of the throughput of a queueing network but in the caching setting.
      Parameters:
      gamma - - Matrix representing the cache access factors.
      m - - Matrix representing the cache capacity vector.
      xi - - Optional matrix representing the initial value of the fixed-point iteration.
      Returns:
      cacheXiFpReturn - An object containing the calculated xi terms, initial state probabilities (pi0), the cache state probabilities (pij), and the number of iterations (it).

    • cache_xi_bvh

      public static Matrix cache_xi_bvh(Matrix gamma, Matrix m)
      Computes the cache xi terms using the iterative method used in Gast-van Houdt, SIGMETRICS 2015. This method calculates the xi values, which are important for understanding the distribution of items in the cache. The script assumes (like the paper) that the access factors are monotone with the list index, so it may not work with arbitrary (non-monotone) access costs.
      Parameters:
      gamma - - Matrix representing the cache access factors.
      m - - Matrix representing the cache capacity vector.
      Returns:
      Matrix - A matrix containing the computed xi terms.

    • cache_rayint

      public static Ret.cacheRayInt cache_rayint(Matrix gamma, Matrix m)
      Approximate the normalizing constant of the cache steady state distribution using the ray method.
      Parameters:
      gamma - - Matrix representing the cache access factors.
      m - - Matrix representing the cache capacity vector.
      Returns:
      cacheRayIntReturn - the approximated normalizing constant (Z, and its logarithm lE) and the xi terms.

    • cache_miss_rayint

      public static Ret.cacheMissRayInt cache_miss_rayint(Matrix gamma, Matrix m, MatrixCell lambda)
      Estimates the cache miss rate and related metrics using the ray method for PDEs. This method computes the miss rate (M), user-specific miss rates (MU), item-specific miss rates (MI), initial state probabilities (pi0), and the logarithm of the normalizing constant (lZ).
      Parameters:
      gamma - - Matrix representing the cache access factors.
      m - - Matrix representing the cache capacity vector.
      lambda - - MatrixCell representing the request rates for different users or items.
      Returns:
      cacheMissRayIntReturn - An object containing the miss rate metrics and probabilities.

    • cache_erec

      public static Matrix cache_erec(Matrix gamma, Matrix m)
      Computes the cache miss rate using an exact recursive method. This method serves as a wrapper that calls the auxiliary function to perform the actual computation.
      Parameters:
      gamma - - Matrix representing the cache access factors.
      m - - Matrix representing the cache capacity vector.
      Returns:
      Matrix - A matrix containing the computed cache miss rates.

    • cache_prob_erec

      public static Matrix cache_prob_erec(Matrix gamma, Matrix m)
      Computes the cache state probabilities using an exact recursive method. This method calculates the probabilities of the cache being in different states based on the cache access factors and capacity.
      Parameters:
      gamma - - Matrix representing the cache access factors.
      m - - Matrix representing the cache capacity vector.
      Returns:
      Matrix - A matrix containing the computed cache state probabilities for each item and level.

    • cache_prob_rayint

      public static Matrix cache_prob_rayint(Matrix gamma, Matrix m)
      Computes the cache state probabilities using the ray method. This method calculates the probabilities of the cache being in different states based on the access factors and capacity, utilizing the logarithm of the partition function obtained through the ray method.
      Parameters:
      gamma - - Matrix representing the cache access factors.
      m - - Matrix representing the cache capacity vector.
      Returns:
      Matrix - A matrix containing the computed cache state probabilities for each item and level.