pfqn_scat.h File Reference

Neuse-Chandy SCAT (Self-Correcting Approximation Technique) approximate MVA. More...

#include <cstddef>
#include <vector>
#include "line/api/pfqn/pfqn_amva_common.h"
#include "line/api/pfqn/pfqn_egflinearizer.h"
#include "line/num/number.h"
#include "line/util/matrix.h"

Include dependency graph for pfqn_scat.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
LinearizerResult< T >	line::pfqn::pfqn_scat (const Matrix< T > &L, const std::vector< int > &N, const Matrix< T > &Z, const std::vector< SchedStrategy > &type, double tol, int maxiter, const Matrix< T > &QN0)
	Neuse-Chandy SCAT (Self-Correcting Approximation Technique) approximate MVA.
template<class T>
LinearizerResult< T >	line::pfqn::pfqn_scat (const Matrix< T > &L, const std::vector< int > &N, const Matrix< T > &Z)
template<class T>
LinearizerResult< T >	line::pfqn::pfqn_scat (const Matrix< T > &L, const std::vector< int > &N)

Detailed Description

Neuse-Chandy SCAT (Self-Correcting Approximation Technique) approximate MVA.

Templated port of matlab/src/api/pfqn/pfqn_scat.m, cross-checked against jar/src/main/java/jline/api/pfqn/mva/Pfqn_scat.java.

SCAT shares the Linearizer fixed point: it carries the mean queue lengths at the target population N and at the R reduced populations N - e_s, and corrects the Bard-Schweitzer proportionality assumption with

Delta(i,r,s) = Q(i,r | N - e_s)/(N - e_s)_r - Q(i,r | N)/N_r,

held fixed while an inner MVA fixed point is iterated. It differs from Linearizer in that this correction is refreshed ONCE: SCAT stops after the first pass, where Linearizer performs the fixed three passes of Chandy and Neuse (1982), Sec. 4. Cost is therefore about one third of Linearizer's, and accuracy sits between Bard-Schweitzer (the Delta == 0 special case, pfqn_bs) and Linearizer. So this is pfqn_egflinearizer with alpha == 1 and one refresh round, exactly as pfqn_linearizer is the same call with three.

SCAT's second departure from Linearizer, fitting a probability mass function centred on the mean queue length at queue-dependent centres instead of propagating the MVA distribution recursion (Krzesinski and Greyling 1984, Sec. 4), does not arise here: this entry point covers single-server and delay stations only, exactly as pfqn_linearizer does. That mass function is available separately as the "scat" marginal rule of pfqn_ab_amva.

Arithmetic: inherited from pfqn_egflinearizer. At alpha == 1 the real power degenerates to a rational operation, but the inner Core loop still stops on enorm(Q_{k+1} - Q_k) < tol, so what comes back is the iterate the stopping rule selected rather than the solution of a finite rational problem.

Reference: D. Neuse, K. M. Chandy, "SCAT: A Heuristic Algorithm for Queueing Network Models of Computing Systems", ACM SIGMETRICS Perform. Eval. Rev. 10(3), 1981.

Definition in file pfqn_scat.h.