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

    • 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

    • getExpectedLatency

      public Matrix getExpectedLatency()
      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)

    • 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

    • 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

    • setItemQueueExitProbability

      public void setItemQueueExitProbability(JobClass jobinClass, int item, Queue queue, double probability)

    • setItemQueueEntryProbability

      public void setItemQueueEntryProbability(JobClass jobinClass, int item, Queue queue, double probability)

    • setItemRoutingProbability

      public void setItemRoutingProbability(JobClass jobinClass, int item, Queue sourceQueue, Queue destQueue, double probability)
      Sets the routing probability for an item retrieval transition between two queues in the retrieval system.
      Parameters:
      jobinClass - The job class for a request that can be routed through this system.
      item - The item whose retrieval routing is being updated.
      sourceQueue - The queue from which the retrieval departs.
      destQueue - The queue to which the retrieval is routed.
      probability - The probability of routing the retrieval from sourceQueue to destQueue.

    • setItemServiceRateAtQueue

      public void setItemServiceRateAtQueue(JobClass jobinClass, int item, Queue queue, double serviceRate)
      Set the service rate for an individual item at a queue in the retrieval system for read requests originating from job class jobinClass
      Parameters:
      jobinClass - job class that creates a read request
      item - the requested item
      queue - queue in the retrieval system
      serviceRate - rate of service for the item at the queue

    • 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 cacheNode.setItemServiceRateAtQueue(JobClass jobinClass, int item, Queue queue, double rate). To set routing probabilities for an item for queue_1 -> queue_2 call cacheNode.setItemRoutingProbability(JobClass jobinClass, int item, Queue sourceQueue, Queue destQueue, double probability). To set entry probability for queue_1 call cacheNode.setItemQueueEntryProbability(JobClass jobinClass, int item, Queue queue, double probability). To set exit probability for queue_1 call cacheNode.setItemQueueExitProbability(int item, Queue queue, double probability).

      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.

    • setRetrievalSystem

      public void setRetrievalSystem(JobClass jobinClass, JobClass missClass, Queue[] queues, Matrix serviceRates)
      Initializes the retrieval system when a job of class jobinClass arrives at the cache node. Service rates are initialized. Routing matrices are not initialized and must be set later.

      To set routing probabilities for an item for queue_1 -> queue_2 call cacheNode.setItemRoutingProbability(int item, Queue sourceQueue, Queue destQueue, double probability). To set entry probability for queue_1 call cacheNode.setItemQueueEntryProbability(int item, Queue queue, double rate). To set exit probability for queue_1 call cacheNode.setItemQueueExitProbability(int item, Queue queue, double rate).

      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.
      serviceRates - Matrix containing the service rates for each requestable item. [nQueues, nItems]

    • setRetrievalSystem

      public void setRetrievalSystem(JobClass jobinClass, JobClass missClass, Queue[] queues, double serviceRate, Matrix routingMatrix)
      Initializes the retrieval system when a job of class jobinClass arrives at the cache node. Every item shares the same routing matrix, and every queue-item pair shares the same service rate.
      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.
      serviceRate - Service rate to use for every item at every queue.
      routingMatrix - Routing matrix shared by every item.

    • setRetrievalSystem

      public void setRetrievalSystem(JobClass jobinClass, JobClass missClass, Queue[] queues, double[] serviceRates, Matrix routingMatrix)
      Initializes the retrieval system when a job of class jobinClass arrives at the cache node. Every item shares the same routing matrix, and each queue shares the same per-item service rates.
      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.
      serviceRates - Service rates for each item, duplicated across every queue. Length must be nItems.
      routingMatrix - Routing matrix shared by every item.

    • setRetrievalSystem

      public void setRetrievalSystem(JobClass jobinClass, JobClass missClass, Queue queue, double[] serviceRates, Matrix routingMatrix)
      Initializes the retrieval system when a job of class jobinClass arrives at the cache node. Every item shares the same routing matrix, and the queue uses the given per-item service rates.
      Parameters:
      jobinClass - The job class for a request that can be routed through this system.
      missClass - The job class for retrieval misses.
      queue - Queue in the retrieval system.
      serviceRates - Service rates for each item at the queue. Length must be nItems.
      routingMatrix - Routing matrix shared by every item.

    • setRetrievalSystem

      public void setRetrievalSystem(JobClass jobinClass, JobClass missClass, Queue[] queues, Matrix serviceRates, Matrix[] routingMatrices)
      Initializes the retrieval system when a job of class jobinClass arrives at the cache node.

      When a request for an item arrives at the cache node, if there is a cache miss, then the job is routed to the retrieval system to fetch the item. After retrieval, the job switches to missClass to be logged as a miss. A class switcher is required to change a retrieval from departing to arriving at the cache node. A retrieval complete class has a one-hot vector representing its reading probability for its item, as after retrieval has begun, the item to read is now fixed.

      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.
      serviceRates - Matrix containing the service rates (Exponential distribution) for each requestable item. [nQueues, nItems]
      routingMatrices - Array of routing matrices for each item. Length must be nItems. Each matrix has shape [nQueues + 1, nQueues + 1] with index nQueue corresponding to entering/leaving the retrieval system to/from the cache node. Entry[row, col] represents probability of routing from queue_row to queue_col.

    • setRetrievalSystem

      public void setRetrievalSystem(JobClass jobinClass, JobClass missClass, Queue[] queues, Distribution[][] serviceDistributions, Matrix[] routingMatrices)
      Initializes the retrieval system when a job of class jobinClass arrives at the cache node.

      When a request for an item arrives at the cache node, if there is a cache miss, then the job is routed to the retrieval system to fetch the item. After retrieval, the job switches to missClass to be logged as a miss. A class switcher is required to change a retrieval from departing to arriving at the cache node. A retrieval complete class has a one-hot vector representing its reading probability for its item, as after retrieval has begun, the item to read is now fixed.

      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.
      serviceDistributions - 2D array containing the service distributions for each requestable item. [nQueues, nItems]
      routingMatrices - Array of routing matrices for each item. Length must be nItems. Each matrix has shape [nQueues + 1, nQueues + 1] with index nQueue corresponding to entering/leaving the retrieval system to/from the cache node. Entry[row, col] represents probability of routing from queue_row to queue_col.

    • setResultHitProb

      public void setResultHitProb(Matrix actualHitProb)
      Sets the actual hit probabilities from simulation or analysis results.
      Parameters:
      actualHitProb - Matrix containing the observed hit 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

    • setResultExpectedLatency

      public void setResultExpectedLatency(Matrix actualExpectedLatency)
      Sets the actual expected latency from simulation or analysis results.
      Parameters:
      actualExpectedLatency - 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)