Package jline.solvers.ctmc.analyzers

Class Solver_ctmc_mdd_analyzer

java.lang.Object
jline.solvers.ctmc.analyzers.Solver_ctmc_mdd_analyzer
public class Solver_ctmc_mdd_analyzer extends Object
Stationary analysis by decision-diagram level aggregation.

Analyses a closed single-class network whose CTMC state space is held in a decision diagram and solved by level aggregation, after A.S. Miner, G. Ciardo, S. Donatelli, "Using the exact state space of a Markov model to compute approximate stationary measures", SIGMETRICS 2000.

This is the 'mdd' method of SolverCTMC. It never forms the |S|-state generator: the reachable set is stored in an MDD and K coupled level-CTMCs are iterated to a fixed point, so the memory cost is O(sum_k |M_k|) rather than O(|S|). The saving grows with the number of stations, and is negative at K=3, where the diagram compresses nothing.

Exactness. The single approximation is Pr{i_k | alpha} = Pr{i_k | p}. It is EXACT on product-form networks (paper Sec. 5), which covers exponential service under any work-conserving discipline and general service at PS or IS stations (BCMP types 2 and 3). It is an approximation otherwise, notably phase-type service at FCFS or LCFS, where errors of a fraction of a percent on the mean queue lengths have been observed.

MATLAB twin: solver_ctmc_mdd_analyzer.m. Python twin: api/solvers/ctmc/solver_ctmc_mdd_analyzer.py.

  • Method Details

    • solver_ctmc_mdd

      public static Solver_ctmc_mdd_analyzer.MddResult solver_ctmc_mdd(NetworkStruct sn, SolverOptions options)
      Analyse a closed single-class network by MDD level aggregation.
      Parameters:
      sn - the network structure
      options - solver options; the level knobs are read from options.config.mdd_tol / mdd_maxiter, never from iter_tol

    • supportsReason

      public static String supportsReason(NetworkStruct sn)
      Can the mdd decision-diagram method be asked for this model?

      The model-shape gate asked as a predicate rather than thrown. The analyzer refuses with it before it builds anything, and SolverCTMC.supportsModelMethod asks the very same call so that a caller (model.help, findSolver, SolverAUTO) sees the verdict without paying for a run. One predicate with two callers is what stops the report and the analyzer from disagreeing about which models the method serves.

      A STOCHASTIC PETRI NET IS EXEMPT: a Place model is read through Spn_mdd, which builds the reachable set and the Kronecker descriptor from the marking rather than from the (station,class) encoding, so neither the single-class rule nor the closed-population rule applies to it.

      The deeper refusals the analyzer still raises -- a station-to-station chain that is not stochastic, and a phase-type law at a discipline neither local encoding represents -- are not restated here: they are decided from quantities the analyzer computes on its way through, not from the model shape, so a caller cannot be told about them without doing the work.

      Parameters:
      sn - the network structure
      Returns:
      empty string when the method may run, else the refusal

    • solver_ctmc_mdd

      public static Solver_ctmc_mdd_analyzer.MddResult solver_ctmc_mdd(NetworkStruct sn, SolverOptions options, Network model)
      Analyse a closed single-class network, or a stochastic Petri net, by MDD level aggregation.

      Passing model routes a net holding Places and Transitions through Spn_mdd instead of Mdd_descriptor: the levels are then (place, class) pairs plus one phase level per phase-type mode, and the measures come back per place. The approximation is the same Eq. 5 as for a queueing network, and it is exact on a product-form net, which SolverNC's "rec" method solves exactly and far more cheaply -- the aggregation earns its place on the nets that have NO product form.

      A net carries no per-station service rate, so Mdd_mcd returns only the level marginals. The token throughput is then assembled here from the mode rates and those marginals, under the SAME independence across levels that the aggregation already assumes: it is the method's own approximation applied once more, not a second one layered on top.

      Parameters:
      sn - the network structure
      options - solver options
      model - the model object, needed only for the Petri-net route