Exact normalizing constant of a closed multiclass product-form network whose state space carries arbitrary linear integer constraints (Manjunath-Sikdar). More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <cstdlib>
#include <limits>
#include <string>
#include <type_traits>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for pfqn_manjunath.h:

Classes
struct	line::pfqn::PfqnManjunathOptions
	Controls of pfqn_manjunath. More...
struct	line::pfqn::PfqnManjunathResult< T >
	Result of pfqn_manjunath. More...

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
PfqnManjunathResult< T >	line::pfqn::pfqn_manjunath (const Matrix< T > &L, const std::vector< int > &N, const Matrix< T > &Z, const Matrix< T > &A, const std::vector< long > &b, const std::string &sense, const PfqnManjunathOptions &options={})
	Exact normalizing constant of a closed multiclass product-form network whose state space carries arbitrary linear integer constraints (Manjunath-Sikdar).
template<class T>
PfqnManjunathResult< T >	line::pfqn::pfqn_manjunath (const Matrix< T > &L, const std::vector< int > &N, const Matrix< T > &Z, const PfqnManjunathOptions &options={})
	Overload without extra constraints: the plain closed-network constant.
template<class T>
PfqnManjunathResult< T >	line::pfqn::pfqn_manjunath (const Matrix< T > &L, const std::vector< int > &N, const PfqnManjunathOptions &options={})
	Overload without think times or extra constraints.

Detailed Description

Exact normalizing constant of a closed multiclass product-form network whose state space carries arbitrary linear integer constraints (Manjunath-Sikdar).

Templated port of matlab/src/api/pfqn/pfqn_manjunath.m and jar/src/main/java/jline/api/pfqn/nc/Pfqn_manjunath.java.

This is the queueing-network half of the transform technique of which lossn_manjunath is the loss-network half. The two solve the same problem – sum a product form over an irregular integer state space – from opposite ends of the paper: lossn_manjunath implements Section 2.2, a set of '<=' rows over the Poisson terms nu^n/n!, while this routine implements Section 3 together with Section 5.3, a MIXED set of '=', '<=' and '>' rows over the BCMP terms, where the population constraint of a closed network is itself one of the equalities.

THE MODEL. M queueing stations (rows of L) and Mz delay stations (rows of Z) serve R closed classes with populations N. With n_i = sum_r n_ir,

p(n) = (1/G) prod_{i queueing} n_i! prod_r L_ir^{n_ir}/n_ir! prod_{i delay} prod_r Z_ir^{n_ir}/n_ir!

Every state obeys the R population equalities sum_i n_ir = N_r; the caller may impose any number of further rows sum_{i,r} A(j, i + S*r) n_ir {=,<=,>} b(j) with S = M + Mz, i.e. A acts on the (M+Mz) x R occupancy read column by column with the queueing stations first. With no extra rows the result is exactly pfqn_ca's normalizing constant, which is the parity oracle used by the tests.

WHY THE GENERATING FUNCTION IS A PRODUCT, AND WHERE THE n_i! GOES. Marking class r by z_r and row j by y_j, and writing u_ir = z_r prod_j y_j^{A(j,i+S r)}, the sum over the occupancies of a single QUEUEING station is, by the multinomial theorem,

sum_{n_i.} n_i! prod_r (L_ir u_ir)^{n_ir}/n_ir! = sum_k (sum_r L_ir u_ir)^k = 1 / (1 - sum_r L_ir u_ir),

so the n_i! that couples the classes is exactly what turns the station's factor from an exponential into a geometric one. The paper reaches the same place through the Euler integral n! = int_0^inf e^-t t^n dt (Eqns 16-18), which is that geometric series evaluated; the closed form is used here because there is then no quadrature to discretize – and, decisively for this port, no transcendental, so the whole computation stays rational.

WHY THIS ONE RUNS AT EXACT ARITHMETIC. Every operation on the series is an addition or a multiplication of demands, plus a division by a small integer in the delay convolution, all of which are rational whenever L and Z are. G is therefore exact under Arith::Exact and only lG is transcendental, obtained through num_traits<T>::log_as_double. The double-only power-of-two rescaling of pfqn_ca is applied on the same terms and for the same reason: exact rationals have no exponent range to leave, and scaling them would only inflate their denominators.

THE ELIMINATION ORDER IS THE MEMORY BOUND. Variable y_j is created when the first station its row touches is multiplied in and discharged immediately after the last, so peak memory is prod_r (N_r+1) times the product of (b_j+1) over the SIMULTANEOUSLY LIVE rows, not over all rows. The class axes are live throughout, so prod_r (N_r+1) is a floor – the same lattice pfqn_ca walks. The peak is bounded by PfqnManjunathOptions::max_live_states and a model above it is refused by name rather than allowed to exhaust the machine.

SCOPE. Load-dependent and multiserver stations are NOT covered: their per-station term is not geometric, and the multiclass n_i! coupling used above then breaks. Use pfqn_gld or pfqn_conwayms. A and b must be integer valued and A nonnegative, since the residue argument counts whole units; a fractional entry is refused rather than rounded.

Reference: D. Manjunath and B. Sikdar, Integral Expressions for the Numerical Evaluation of Product Form Expressions Over Irregular Multidimensional Integer Spaces. Sections 3 and 5.3.

Definition in file pfqn_manjunath.h.

Classes

Namespaces

Functions

Detailed Description