The mdd method of SolverCTMC: stationary analysis of a closed single-class network whose state space is held in a decision diagram and solved by level aggregation. More...

#include <cmath>
#include <cstddef>
#include <string>
#include <vector>
#include "line/api/mdd/mdd.h"
#include "line/api/mdd/mdd_descriptor.h"
#include "line/api/mdd/mdd_mcd.h"
#include "line/api/mdd/mdd_ps.h"
#include "line/api/spn/spn_mdd.h"
#include "line/api/mdd/mdd_reachset.h"
#include "line/api/mdd/mdd_types.h"
#include "line/lang/lang_types.h"
#include "line/lang/qn/network_struct.h"
#include "line/num/number.h"
#include "line/solvers/ctmc/solver_ctmc.h"
#include "line/solvers/ctmc/solver_ctmc_analyzer.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for solver_ctmc_mdd_analyzer.h:

Classes
struct	line::ctmc::CtmcMddSolution< T >
	What one mdd solve produces beside the means, i.e. More...

Namespaces
namespace	line
namespace	line::ctmc

Functions
template<class T>
std::string	line::ctmc::solver_ctmc_mdd_supports (const NetworkStruct< T > &sn)
	Can the mdd decision-diagram method be asked for this model?
template<class T>
CtmcMddSolution< T >	line::ctmc::solver_ctmc_mdd_analyzer (const NetworkStruct< T > &sn, const CtmcOptions &opt, const mdd::MddMcdOptions &mcdopt=mdd::MddMcdOptions())
	Solve with the mdd method.
template<class T>
mva::AvgResult< T >	line::ctmc::solver_ctmc_mdd_run_analyzer (const NetworkStruct< T > &sn, const CtmcOptions &opt, const mdd::MddMcdOptions &mcdopt=mdd::MddMcdOptions())
	Solve with mdd and format, so a caller with no use for the diagram has one call.

Detailed Description

The mdd method of SolverCTMC: stationary analysis of a closed single-class network whose state space is held in a decision diagram and solved by level aggregation.

Port of matlab/src/solvers/CTMC/solver_ctmc_mdd_analyzer.m, after A.S. Miner, G. Ciardo, S. Donatelli, "Using the exact state space of a Markov model to compute approximate stationary measures", SIGMETRICS 2000.

IT NEVER FORMS THE |S|-STATE GENERATOR, which is the whole point and also why it sits beside solver_ctmc_analyzer rather than inside it: the reachable set lives 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. no_aggregation additionally certifies exactness STRUCTURALLY: when no diagram node is shared, conditioning on the node equals conditioning on the whole path and the approximation is an identity. False means "not certified", never "approximate" – a product-form model is exact however much its diagram shares.

WHICH ENCODING. Exponential service is discipline-insensitive for the queue-length law, so the compact count encoding of mdd_descriptor serves any work-conserving station. Phase-type service is not: mdd_descriptor's count-plus-one-phase local state is NON-preemptive, while a shared server has every job present in service holding its own phase and needs the per-phase counts of mdd_ps. A model that mixes the two cases is refused rather than modelled under whichever encoding happens to be picked.

Definition in file solver_ctmc_mdd_analyzer.h.

Classes

Namespaces

Functions

Detailed Description