 |
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
|
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
Infinite-state stochastic Petri nets (iSPN) by the matrix-geometric method. More...
#include <algorithm>#include <cctype>#include <cmath>#include <cstddef>#include <cstdio>#include <functional>#include <limits>#include <map>#include <string>#include <vector>#include "line/api/mam/qbd_r.h"#include "line/util/eig.h"#include "line/util/error.h"#include "line/util/matrix.h"Go to the source code of this file.
Classes | |
| struct | line::spn::IspnOptions |
| Options of spn_ispn. More... | |
| struct | line::spn::IspnResult |
| Result of spn_ispn; fields as in the MATLAB help. More... | |
| struct | line::spn::ispn_detail::Net |
| struct | line::spn::ispn_detail::Arc |
| struct | line::spn::ispn_detail::Walk |
| struct | line::spn::ispn_detail::Elim |
Namespaces | |
| namespace | line |
| Conservation laws of a layered queueing network, enumerated from its structure. | |
| namespace | line::spn |
| namespace | line::spn::ispn_detail |
Typedefs | |
| typedef std::vector< double > | line::spn::ispn_detail::Vec |
| typedef std::vector< Vec > | line::spn::ispn_detail::Mat |
Functions | |
| std::string | line::spn::ispn_detail::fmt (const char *f, double a=0, double b=0, double c=0, double d=0) |
| void | line::spn::ispn_detail::refuse (const std::string &m) |
| void | line::spn::ispn_detail::unstable (const std::string &m) |
| void | line::spn::ispn_detail::badarg (const std::string &m) |
| Mat | line::spn::ispn_detail::zeros (std::size_t n, std::size_t m) |
| Mat | line::spn::ispn_detail::eye (std::size_t n) |
| std::size_t | line::spn::ispn_detail::ncols (const Mat &A) |
| Mat | line::spn::ispn_detail::sub (const Mat &A, const std::vector< std::size_t > &r, const std::vector< std::size_t > &c) |
| bool | line::spn::ispn_detail::all_zero (const Mat &A) |
| double | line::spn::ispn_detail::max_abs (const Vec &a) |
| double | line::spn::ispn_detail::max_abs (const Mat &A) |
| double | line::spn::ispn_detail::max_abs_diff (const Mat &A, const Mat &B) |
| Mat | line::spn::ispn_detail::plus (const Mat &A, const Mat &B) |
| Mat | line::spn::ispn_detail::minus (const Mat &A, const Mat &B) |
| Mat | line::spn::ispn_detail::scale (const Mat &A, double s) |
| Mat | line::spn::ispn_detail::mult (const Mat &A, const Mat &B) |
| Vec | line::spn::ispn_detail::vec_mult (const Vec &x, const Mat &A) |
| double | line::spn::ispn_detail::sum (const Vec &a) |
| Vec | line::spn::ispn_detail::row_sums (const Mat &A) |
| double | line::spn::ispn_detail::dot (const Vec &a, const Vec &b) |
| std::vector< std::size_t > | line::spn::ispn_detail::lu (Mat &A) |
| LU with partial pivoting in place; returns the row permutation. | |
| Mat | line::spn::ispn_detail::solve (const Mat &A0, const Mat &B) |
| Solves A X = B. | |
| Mat | line::spn::ispn_detail::inv (const Mat &A) |
| Vec | line::spn::ispn_detail::solve_left (const Mat &A, const Vec &b) |
| Solves x A = b for the row vector x. | |
| double | line::spn::ispn_detail::norm1 (const Mat &A) |
| double | line::spn::ispn_detail::cond1 (const Mat &A) |
| Matrix< double > | line::spn::ispn_detail::to_matrix (const Mat &A) |
| Mat | line::spn::ispn_detail::from_matrix (const Matrix< double > &M) |
| Vec | line::spn::ispn_detail::enabled_weights (const Net &net, const Vec &m, std::vector< bool > &en) |
| std::size_t | line::spn::ispn_detail::lookup (Walk &W, std::map< std::vector< long long >, std::size_t > &keys, const Vec &m, const Net &net, int cap, const IspnOptions &opt) |
| Walk | line::spn::ispn_detail::explore (const Net &net, const Vec &m0, int cap, const IspnOptions &opt) |
| Elim | line::spn::ispn_detail::eliminate (const Walk &W, const Net &net, int Ktop) |
| int | line::spn::ispn_detail::find_K (const Elim &E, int Ktop, const IspnOptions &opt, std::size_t p0) |
| double | line::spn::ispn_detail::expect (const Vec &r, const std::string &what, const Mat &x, const std::vector< std::vector< std::size_t > > &lv, int K, int Ktop, const Vec &c1, const Vec &c2, double tol) |
| long long | line::spn::ispn_detail::gcd_ll (long long a, long long b) |
| std::vector< Vec > | line::spn::ispn_detail::minimal (const std::vector< Vec > &D, std::size_t T, std::size_t P) |
| std::vector< bool > | line::spn::spn_ispn_covered (const std::vector< std::vector< double > > &C) |
| Places covered by a non-negative S-invariant (P-semiflow) y' C = 0, by Farkas' algorithm on [C | I] keeping minimal supports. | |
| IspnResult | line::spn::spn_ispn (const std::vector< std::vector< double > > &pre, const std::vector< std::vector< double > > &post, std::vector< std::vector< double > > inh, const std::vector< double > &rate, std::vector< bool > imm, std::vector< double > srv, const std::vector< double > &m0, std::size_t p0, const IspnOptions &opt=IspnOptions()) |
| Steady state of an infinite-state SPN. | |
Infinite-state stochastic Petri nets (iSPN) by the matrix-geometric method.
A net whose single unbounded place P0 is the level of a quasi-birth-death process (B. R. Haverkort, "Performance of Computer Communication Systems: A Model-Based Approach", Wiley, 1998, ch. 17; B. R. Haverkort, A. Ost, "Steady- state analysis of infinite stochastic Petri nets: comparing the spectral expansion and the matrix-geometric method", PNPM 1997, 36-45).
The iSPN requirements of Haverkort sec. 17.2 are checked, and a violation is refused with LINE:unsupported:Structure naming the condition: every firing moves P0 by at most one token (also across a chain of immediate firings), every other place is bounded, and above a threshold level K the levels repeat with the same phase markings and level-independent rates. The threshold is found by exploring a window of levels and comparing the generator blocks.
Vanishing markings of immediate transitions are eliminated as Q = Q_TT + Q_TV (I - P_VV)^-1 P_VT. R solves A0 + R A1 + R^2 A2 = 0 by logarithmic reduction (G. Latouche, V. Ramaswami, J. Appl. Probab. 30(3), 1993) or successive substitution, the drift condition pi A0 1 < pi A2 1 (Haverkort (17.7)) is checked, and the boundary levels 0..K solve x B = 0 with the R A2 correction and the normalisation x_K (I-R)^-1 1 = 1 - sum.
NO TRUNCATION: a measure r of the marking that is affine in the level above K, r(K+j) = a + (j-1) b for j >= 1, has the closed form E[r] = sum_{i<=K} x_i r_i + x_K R N a + x_K R^2 N^2 b, N = (I-R)^-1, which covers the mean marking of every place, the marginals of the bounded places, the firing rates and the user rewards. A measure that is not affine is refused rather than truncated.
DOUBLE ONLY: R is a fixed point of a quadratic matrix equation, irrational in general, and the stability test needs the spectral radius of R.
Indices are 0-based: p0 is the row of the unbounded place in pre/post. MATLAB twin: matlab/src/api/spn/spn_ispn.m (1-based P0); Java twin: jline.api.spn.Spn_ispn; Python twin: line_solver.api.spn.ispn.
Definition in file spn_ispn.h.
1.18.0