Package jline.lang.nodes

Class Cache

java.lang.Object
jline.lang.Element
jline.lang.NetworkElement
jline.lang.nodes.Node
jline.lang.nodes.StatefulNode
jline.lang.nodes.Cache
All Implemented Interfaces:
Serializable, Copyable
public class Cache extends StatefulNode implements Serializable
A cache node that implements cache replacement policies and class switching based on cache hits and misses.

The Cache node models a caching system where incoming jobs request items from a finite cache. When a requested item is found in the cache (hit), the job may be routed to one class; when the item is not found (miss), it may be routed to a different class. This enables modeling of cache-aware queueing networks where performance depends on cache hit rates.

Key features:

  • Multi-level cache support with configurable capacity per level
  • Various replacement strategies (LRU, FIFO, RANDOM, etc.)
  • Popularity-based item access patterns (e.g., Zipf distribution)
  • Class switching based on hit/miss outcomes
  • Optional graph-based cache structures

Since:
1.0
See Also:

  • Field Details

  • Constructor Details

    • Cache

      public Cache(Network model, String name, int nitems, int itemLevelCap, ReplacementStrategy replPolicy)
      Creates a single-level cache with the specified item capacity and replacement policy.
      Parameters:
      model - The network model this cache belongs to
      name - The name of the cache node
      nitems - The total number of items that can be requested from this cache
      itemLevelCap - The capacity of the cache (number of items it can hold)
      replPolicy - The replacement strategy to use when the cache is full

    • Cache

      public Cache(Network model, String name, int nitems, int itemLevelCap, ReplacementStrategy replPolicy, Matrix[] graph)
      Creates a single-level cache with the specified item capacity, replacement policy, and graph structure.
      Parameters:
      model - The network model this cache belongs to
      name - The name of the cache node
      nitems - The total number of items that can be requested from this cache
      itemLevelCap - The capacity of the cache (number of items it can hold)
      replPolicy - The replacement strategy to use when the cache is full
      graph - Optional graph structure defining cache organization

    • Cache

      public Cache(Network model, String name, int nitems, Matrix itemLevelCap, ReplacementStrategy replPolicy)
      Creates a multi-level cache with different capacities per level and a replacement policy.
      Parameters:
      model - The network model this cache belongs to
      name - The name of the cache node
      nitems - The total number of items that can be requested from this cache
      itemLevelCap - A matrix specifying the capacity of each cache level
      replPolicy - The replacement strategy to use when the cache is full

    • Cache

      public Cache(Network model, String name, int nitems, Matrix itemLevelCap, ReplacementStrategy replPolicy, Matrix[] graph)
      Creates a multi-level cache with different capacities per level, replacement policy, and graph structure.

      This is the main constructor that all other constructors delegate to. It initializes the cache with all necessary components including input/output buffers, the cache server, and item management.

      Parameters:
      model - The network model this cache belongs to
      name - The name of the cache node
      nitems - The total number of items that can be requested from this cache
      itemLevelCap - A matrix specifying the capacity of each cache level
      replPolicy - The replacement strategy to use when the cache is full
      graph - Optional graph structure defining cache organization
      Throws:
      RuntimeException - if the total item capacity exceeds the number of items

  • Method Details

    • getAccessProb

      public Matrix getAccessProb(int i, int j)
      Gets the access probability matrix for a specific cache level and job class.
      Parameters:
      i - The cache level index
      j - The job class index
      Returns:
      The access probability matrix for the specified indices

    • getCacheServer

      public CacheClassSwitcher getCacheServer()
      Gets the internal cache server that handles class switching logic.
      Returns:
      The CacheClassSwitcher instance managing hit/miss class transitions

    • getGraph

      public Matrix[] getGraph()
      Gets the graph structure defining the cache organization.
      Returns:
      Array of matrices representing the cache graph structure, or null if not defined

    • getHitClass

      public Matrix getHitClass()
      For an incoming job of class r, HITCLASS[r] is the new class of that job after a hit
      Returns:
      - the matrix of hit classes

    • getHitRatio

      public Matrix getHitRatio()
      Gets the actual hit probability/ratio for each job class.

      This returns the observed hit rates from simulation or analysis, not the theoretical expected values.

      Returns:
      A matrix containing the hit ratio for each job class

    • getDelayedHitRatio

      public Matrix getDelayedHitRatio()
      Gets the delayed-hit fraction per class (retrieval system); empty when the cache has no retrieval system.
      Returns:
      A matrix containing the delayed-hit fraction for each job class

    • getHitRatioByList

      public Matrix getHitRatioByList()
      Gets the per-class, per-list (per-level) hit fraction matrix [classes x lists]; empty when not computed by the solver.
      Returns:
      A matrix of per-list hit fractions

    • getItemProb

      public Matrix getItemProb()
      Gets the per-item occupancy matrix [items x (lists+1)]: column 0 is the miss probability, columns 1.. the per-list probabilities; empty when not computed by the solver.
      Returns:
      A matrix of per-item, per-list occupancy probabilities

    • getItemLevelCap

      public Matrix getItemLevelCap()
      Gets the capacity configuration for each cache level.
      Returns:
      A matrix where each element specifies the item capacity of a cache level

    • getItems

      public ItemSet getItems()
      Gets the set of items that can be stored in this cache.
      Returns:
      The ItemSet object managing the cache items

    • getTotalCacheCapacity

      public int getTotalCacheCapacity()
      Gets the total capacity of the cache.
      Returns:
      The total capacity of the cache (sum of capacities of all levels)

    • getRetrievalSystemCapacity

      public int getRetrievalSystemCapacity()
      Gets the retrieval system capacity of the cache.

      By default the cache has no retrieval system, so it will be 0. However, if setRetrievalSystem is called with any arrival class, then the cache state must contain a list of items at the retrieval system.

      Returns:
      The total number of items that can be in the retrieval system at any one time.

    • getMissClass

      public Matrix getMissClass()
      For an incoming job of class r, MISSCLASS[r] is the new class of that job after a miss
      Returns:
      - the matrix of miss classes

    • getRetrievalClasses

      public Matrix getRetrievalClasses()
      For an incoming job of class r, RETRIEVALCLASSES[i, r] is the new class of the job after a retrieval begins
      Returns:
      - the matrix of retrieval classes

    • getMissRatio

      public Matrix getMissRatio()
      Gets the actual miss probability/ratio for each job class.

      This returns the observed miss rates from simulation or analysis, not the theoretical expected values.

      Returns:
      A matrix containing the miss ratio for each job class

    • getResidT

      public Matrix getResidT()
      Gets the actual expected latency of an item request for each job class.
      Returns:
      A matrix containing the expected latency for each job class

    • getNumberOfItems

      public int getNumberOfItems()
      Gets the total number of items that can be requested from this cache.
      Returns:
      The number of distinct items in the item set

    • getReplacementStrategy

      public ReplacementStrategy getReplacementStrategy()
      Gets the replacement strategy used when the cache is full.
      Returns:
      The cache replacement strategy (e.g., LRU, FIFO, RANDOM)

    • setAdmissionProb

      public void setAdmissionProb(double q)
      Probability q in [0,1] of admitting a missed item into the cache (q-LRU). Only used when the replacement strategy is QLRU.

    • getAdmissionProb

      public double getAdmissionProb()

    • getSections

      public List<Section> getSections()
      Gets the internal sections of this cache node.

      Returns the three main sections: input buffer, cache server, and output dispatcher.

      Overrides:
      getSections in class Node
      Returns:
      A list containing the input, server, and output sections

    • getnLevels

      public int getnLevels()
      Gets the number of cache levels.
      Returns:
      The number of levels in this multi-level cache

    • getRetrievalSystemQueueIndices

      public List<Integer> getRetrievalSystemQueueIndices(int jobClass)
      Get the node indices of the queues that comprise the retrieval system for a specific job class
      Parameters:
      jobClass - : The job class which read requests arrive in before routing to the retrieval system
      Returns:
      List containing all node indices for the retrieval system.

    • getRetrievalSystemQueueIndices

      public Map<Integer,List<Integer>> getRetrievalSystemQueueIndices()
      Get the map of arrival class to node indices of the queues that comprise the retrieval system
      Returns:
      Map containing all node indices for all retrieval systems

    • getRetrievalClassIndices

      public Set<Integer> getRetrievalClassIndices()
      Gets the set of indices of job classes that have completed retrieval
      Returns:
      The set of indices of job classes that have completed retrieval

    • popularityGet

      public Distribution popularityGet(int i)
      Gets the popularity distribution for a linear index.

      Converts a linear index to 2D coordinates and retrieves the distribution.

      Parameters:
      i - The linear index
      Returns:
      The popularity distribution at the specified index

    • popularityGet

      public Distribution popularityGet(int i, int j)
      Gets the popularity distribution for a specific item class and job class.
      Parameters:
      i - The item class index
      j - The job class index
      Returns:
      The popularity distribution, or null if not set

    • popularityLength

      public int popularityLength()
      Gets the maximum dimension of the popularity matrix.
      Returns:
      The maximum of rows and columns in the popularity matrix

    • popularitySet

      public void popularitySet(int i, Distribution o)
      Sets the popularity distribution for a linear index.

      Converts a linear index to 2D coordinates and sets the distribution.

      Parameters:
      i - The linear index
      o - The popularity distribution to set

    • popularitySet

      public void popularitySet(int i, int j, Distribution o)
      Sets the popularity distribution for a specific item class and job class.

      Automatically expands the popularity matrix dimensions if necessary.

      Parameters:
      i - The item class index
      j - The job class index
      o - The popularity distribution to set

    • reset

      public void reset()
      Resets the internal data structures when the network model is reset.

      Clears the actual hit and miss probability matrices to prepare for a new simulation or analysis run.

      Overrides:
      reset in class Node

    • setAccessProb

      public void setAccessProb(Matrix[][] R)
      Sets the access probability matrices for all cache levels and job classes.
      Parameters:
      R - A 2D array of matrices containing access probabilities

    • setHitClass

      public void setHitClass(JobClass jobinClass, JobClass joboutclass)
      Sets the output class for jobs that experience a cache hit.

      When a job of class jobinClass hits in the cache, it will be transformed to class joboutclass.

      Parameters:
      jobinClass - The incoming job class
      joboutclass - The job class after a cache hit

    • setMissClass

      public void setMissClass(JobClass jobinClass, JobClass joboutclass)
      Sets the output class for jobs that experience a cache miss.

      When a job of class jobinClass misses in the cache, it will be transformed to class joboutclass.

      Parameters:
      jobinClass - The incoming job class
      joboutclass - The job class after a cache miss

    • setRetrievalClass

      public void setRetrievalClass(JobClass jobinClass, JobClass joboutclass, int item)
      Sets the output class for jobs that experience a cache miss and need to be retrieved

      When a job of class jobinClass misses in the cache, it is routed to the retrieval system with class joboutclass. This method sets the output class for a specific item.

      Parameters:
      jobinClass - The incoming job class
      joboutclass - The outgoing job class
      item - The item to be retrieved

    • attachRetrievalSystem

      public void attachRetrievalSystem(JobClass jobinClass, List<Integer> queueIndices, JobClass[] retrievalClassByItem)
      Reconstruct the retrieval-system bookkeeping on a cache whose retrieval classes, routing and queue service already exist in the model (e.g. after deserialization). Unlike setRetrievalSystem(jline.lang.JobClass, jline.lang.JobClass, jline.lang.nodes.Queue[]), this does NOT create new job classes or routing; it only restores the cache-internal state that the simulator reads: the retrieval-system capacity, the per-arrival-class retrieval queue indices, the retrieval-class index set, and the per-item retrieval-class mapping.
      Parameters:
      jobinClass - arrival job class routed through the retrieval system
      queueIndices - node indices of the retrieval-system queues
      retrievalClassByItem - retrieval class for each item (length = nItems)

    • setProbRouting

      public void setProbRouting(JobClass jobClass, Node destination, double probability)
      Sets probabilistic routing for a job class to a destination node.
      Overrides:
      setProbRouting in class Node
      Parameters:
      jobClass - The job class to configure routing for
      destination - The destination node
      probability - The routing probability

    • removeJobClass

      public void removeJobClass(JobClass jobClass)
      Sets the read policy for a job class using a popularity distribution.

      The distribution determines which items are requested by jobs of this class. Common distributions include Zipf for modeling popularity skew.

      Overrides:
      removeJobClass in class Node
      Parameters:
      jobClass - The job class to configure
      distribution - The discrete popularity distribution over items
      Throws:
      RuntimeException - if the distribution is not discrete or has wrong support

    • setRead

      public void setRead(JobClass jobClass, Distribution distribution)

    • setReadItemEntry

      public void setReadItemEntry(JobClass jobClass, Distribution popularity, int cardinality)
      Sets the read policy for a job class with explicit item cardinality.

      Similar to setRead but allows specifying the number of items explicitly, useful when the distribution needs to be configured with a specific cardinality.

      Parameters:
      jobClass - The job class to configure
      popularity - The discrete popularity distribution
      cardinality - The number of items in the distribution support
      Throws:
      RuntimeException - if the distribution is not discrete

    • getRetrievalRoutingEntries

      public List<Cache.RetrievalRoutingEntry> getRetrievalRoutingEntries()

    • addRetrievalRoutingEntry

      public void addRetrievalRoutingEntry(JobClass fromClass, JobClass toClass, Node srcNode, Node destNode, double prob, boolean allowZero)
      Register a deferred routing edge for an auto-generated retrieval class. With allowZero=true an explicit prob==0 entry is recorded so it can override (delete) a default edge inherited from the read class; negative probabilities are always dropped and the internal broadcast path keeps allowZero=false (zeros = no edge).

    • setItemRoutingProbability

      public void setItemRoutingProbability(JobClass jobinClass, int item, Node source, Node dest, double probability)
      Sets the routing probability for an item retrieval transition between two nodes of the retrieval system. A node is either one of the retrieval queues or the cache itself: pass the cache as source for a cache->queue entry, or as destination for a queue->cache exit.
      Parameters:
      jobinClass - The job class for a request that can be routed through this system.
      item - The item whose retrieval routing is being updated.
      source - The node the retrieval departs from (a retrieval queue or the cache).
      dest - The node the retrieval is routed to (a retrieval queue or the cache).
      probability - The probability of routing the retrieval from source to dest.

    • setItemRoutingProb

      public void setItemRoutingProb(JobClass jobinClass, int item, Node source, Node dest, double probability)
      Short alias for setItemRoutingProbability(jline.lang.JobClass, int, jline.lang.nodes.Node, jline.lang.nodes.Node, double).

    • setRetrievalSystem

      public void setRetrievalSystem(JobClass jobinClass, JobClass missClass, Queue[] queues)
      Initializes the retrieval system when a job of class jobinClass arrives at the cache node. Neither service rates nor routing matrices are initialized and both must be set later.

      To set service rates for an item at a queue call queue.setItemServiceRate(Cache cache, JobClass jobinClass, int item, double rate). To set the retrieval routing for an item call cacheNode.setItemRoutingProb(JobClass jobinClass, int item, Node source, Node dest, double probability). source/dest are a retrieval queue or the cache itself: pass the cache as source for a cache->queue entry, or as dest for a queue->cache exit.

      Parameters:
      jobinClass - The job class for a request that can be routed through this system.
      missClass - The job class for retrieval misses.
      queues - Array of queues in the retrieval system.

    • setResultHitProb

      public void setResultHitProb(Matrix actualHitProb)
      Sets the actual hit probabilities from simulation or analysis results.
      Parameters:
      actualHitProb - Matrix containing the observed hit probabilities

    • setResultDelayedHitProb

      public void setResultDelayedHitProb(Matrix actualDelayedHitProb)
      Sets the delayed-hit fraction per class (retrieval system).
      Parameters:
      actualDelayedHitProb - Matrix containing the delayed-hit fractions

    • setResultHitProbList

      public void setResultHitProbList(Matrix actualHitProbList)
      Sets the per-class, per-list (per-level) hit fraction matrix [classes x lists]; rows sum to the aggregate hit fraction.
      Parameters:
      actualHitProbList - Matrix of per-list hit fractions

    • setResultItemProb

      public void setResultItemProb(Matrix actualItemProb)
      Sets the per-item occupancy matrix [items x (lists+1)]; column 0 = miss, columns 1.. = per-list.
      Parameters:
      actualItemProb - Matrix of per-item, per-list occupancy probabilities

    • setResultMissProb

      public void setResultMissProb(Matrix actualMissProb)
      Sets the actual miss probabilities from simulation or analysis results.
      Parameters:
      actualMissProb - Matrix containing the observed miss probabilities

    • setResultResidT

      public void setResultResidT(Matrix actualResidT)
      Sets the actual expected latency from simulation or analysis results.
      Parameters:
      actualResidT - Matrix containing the observed expected latencies

    • setScheduling

      public void setScheduling(int jobClass, SchedStrategy strategy)
      Sets the scheduling strategy for a job class.

      Note: Currently this method has no implementation as caches use FCFS scheduling.

      Parameters:
      jobClass - The job class index
      strategy - The scheduling strategy (unused)