Multichain convolution algorithm with class-dependent service rates (Sauer 1983, "Computational Algorithms for State-Dependent Queueing Networks", ACM TOCS 1(1):67-92, Section 5.2). More...

#include <cstddef>
#include <vector>
#include "line/api/pfqn/pfqn_ca.h"
#include "line/api/pfqn/pfqn_cdfun.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"
#include "line/util/population.h"

Include dependency graph for pfqn_conv.h:

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
NcResult< T >	line::pfqn::pfqn_conv (const Matrix< T > &L, const std::vector< int > &N, const Matrix< T > &Z, const std::vector< CdScaling< T > > &cdscaling)
	Multichain convolution algorithm with class-dependent service rates (Sauer 1983, "Computational Algorithms for State-Dependent Queueing Networks", ACM TOCS 1(1):67-92, Section 5.2).
template<class T>
NcResult< T >	line::pfqn::pfqn_conv (const Matrix< T > &L, const std::vector< int > &N, const Matrix< T > &Z)
	Overload with no class dependence, i.e.
template<class T>
NcResult< T >	line::pfqn::pfqn_conv (const Matrix< T > &L, const std::vector< int > &N)

Detailed Description

Multichain convolution algorithm with class-dependent service rates (Sauer 1983, "Computational Algorithms for State-Dependent Queueing Networks", ACM TOCS 1(1):67-92, Section 5.2).

Templated port of matlab/src/api/pfqn/pfqn_conv.m.

G(N) is the multivariate discrete convolution of the M station factors and the delay factor,

G_0(n) = F_Z(n) = prod_r Z_r^{n_r} / n_r!, G_m(n) = sum_{0 <= i <= n} X_m(i) G_{m-1}(n - i),

where a class-dependent station builds its factor from Sauer eq. (40),

X_m(n) = (|n| / n_r) (L(m,r) / beta_{m,r}(n)) X_m(n - e_r), X_m(0) = 1,

for the first class r with n_r > 0. beta is the DIMENSIONLESS scaling of the service demand supplied by the caller, so beta = 1 means "no correction" and the recurrence collapses to the load-independent multinomial form. A station with no scaling callable is folded in by the classical in-place Buzen update

G_m(n) = G_{m-1}(n) + sum_r L(m,r) G_m(n - e_r)

in O(P R) rather than O(P^2), P = prod_r (N_r + 1), so a model with no class-dependent station reduces operation for operation to pfqn_ca on the same demands and returns the identical value.

Arithmetic: EXACT-CAPABLE. Every operation is an addition, a multiplication or a division in the field of the inputs; the reference's use of log/exp inside its local Fz is a range-management device for the delay factor and is replaced here by the same detail::pff_delay that pfqn_ca uses. Whether the result is exact for a class-dependent station is a property of the supplied beta callables, which are evaluated but never inspected. Note that unlike pfqn_ca this routine applies NO power-of-two rescaling in double: the reference does not, and a class-dependent station factor is not homogeneous in the demands once beta is state dependent, so no exact exponent shift exists in general. Use T = Real<D> or T = Rational when the constant leaves the double range.

Definition in file pfqn_conv.h.

Namespaces

Functions

Detailed Description