CTMC (Continuous Time Markov Chain)

The CTMC solver analyzes models by first generating the infinitesimal generator of the network and then solving the global balance equations for steady-state analysis. Transient analysis is carried out by numerically solving Kolmogorov's forward equations and value iteration for transient rewards. For models with infinite states, such as open networks, the cutoff option can be used to truncate the state space.

MethodAlgorithmReference
defaultSteady-state solution via global balance[1]
gpuGPU-accelerated steady-state solution—

Example

This example demonstrates a closed queueing network with 3 jobs circulating between two queues. The CTMC solver generates the state space and solves the global balance equations to compute steady-state probabilities.

% Create a closed queueing network (2 queues, 3 jobs)
model = Network('Closed Network');

% Create queues
queue1 = Queue(model, 'Queue1', SchedStrategy.PS);
queue2 = Queue(model, 'Queue2', SchedStrategy.FCFS);

% Closed class with 3 jobs starting at Queue1
jobclass = ClosedClass(model, 'Class1', 3, queue1);

% Set service times
queue1.setService(jobclass, Exp(1.0));
queue2.setService(jobclass, Exp(2.0));

% Set routing probabilities
P = model.initRoutingMatrix();
P.set(jobclass, jobclass, queue1, queue1, 0.4);
P.set(jobclass, jobclass, queue1, queue2, 0.6);
P.set(jobclass, jobclass, queue2, queue1, 1.0);
model.link(P);

% Solve with CTMC
solver = CTMC(model);
CTMC(model).avgTable()

Output:

CTMC analysis [method: default, lang: matlab] completed in 0.234s.

ans =
  2×8 table
    Station    JobClass     QLen       Util       RespT     ResidT     ArvR       Tput
    _______    ________    _______    _______    _______    ______    _______    _______
    Queue1      Class1      2.6041    0.98095     2.6547    2.6547    0.98095    0.98095
    Queue2      Class1     0.39591    0.29428    0.67266    0.4036    0.58857    0.58857
import jline.lang.*;
import jline.lang.constant.SchedStrategy;
import jline.lang.nodes.Queue;
import jline.lang.processes.Exp;
import jline.solvers.NetworkAvgTable;
import jline.solvers.ctmc.CTMC;
import java.util.List;

public class CTMCExample {
    public static void main(String[] args) {
        // Create a closed queueing network (2 queues, 3 jobs)
        Network model = new Network("Closed Network");

        Queue queue1 = new Queue(model, "Queue1", SchedStrategy.PS);
        Queue queue2 = new Queue(model, "Queue2", SchedStrategy.FCFS);

        // Closed class with 3 jobs starting at Queue1
        ClosedClass jobclass = new ClosedClass(model, "Class1", 3, queue1);

        queue1.setService(jobclass, Exp.fitRate(1.0));
        queue2.setService(jobclass, Exp.fitRate(2.0));

        // Set routing probabilities
        RoutingMatrix P = new RoutingMatrix(model,
            List.of(jobclass), List.of(queue1, queue2));
        P.addConnection(jobclass, jobclass, queue1, queue1, 0.4);
        P.addConnection(jobclass, jobclass, queue1, queue2, 0.6);
        P.addConnection(jobclass, jobclass, queue2, queue1, 1.0);
        model.link(P);

        // Solve with CTMC
        CTMC solver = new CTMC(model);
        NetworkAvgTable avgTable = solver.avgTable;
        System.out.println(avgTable);
    }
}

Output:

CTMC analysis [method: default, lang: java] completed.

Station    JobClass     QLen       Util       RespT     ResidT     ArvR       Tput
Queue1     Class1       2.6041     0.98095    2.6547    2.6547     0.98095    0.98095
Queue2     Class1       0.39591    0.29428    0.67266   0.4036     0.58857    0.58857
from line_solver import *

# Create a closed queueing network (2 queues, 3 jobs)
model = Network('Closed Network')

queue1 = Queue(model, 'Queue1', SchedStrategy.PS)
queue2 = Queue(model, 'Queue2', SchedStrategy.FCFS)

# Closed class with 3 jobs starting at Queue1
jobclass = ClosedClass(model, 'Class1', 3, queue1)

queue1.setService(jobclass, Exp(1.0))
queue2.setService(jobclass, Exp(2.0))

# Set routing probabilities
P = model.initRoutingMatrix()
P.set(jobclass, jobclass, queue1, queue1, 0.4)
P.set(jobclass, jobclass, queue1, queue2, 0.6)
P.set(jobclass, jobclass, queue2, queue1, 1.0)
model.link(P)

# Solve with CTMC
solver = CTMC(model)
print(solver.avg_table)

Output:

CTMC analysis [method: default, lang: python] completed.

  Station  JobClass    QLen      Util      RespT    ResidT    ArvR      Tput
0  Queue1    Class1     2.6041    0.98095   2.6547   2.6547    0.98095   0.98095
1  Queue2    Class1     0.39591   0.29428   0.67266  0.4036    0.58857   0.58857

References

  1. Bolch, G., Greiner, S., de Meer, H., & Trivedi, K. S. (2006). Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (2nd ed.). Wiley-Interscience.
← Back to Solvers