pfqn_rgfmc.h File Reference

Multiclass Recursion by Generating Functions (RGF), with think times. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <limits>
#include <map>
#include <sstream>
#include <string>
#include <vector>
#include "line/api/pfqn/pfqn_asympt_common.h"
#include "line/api/pfqn/pfqn_rgf.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for pfqn_rgfmc.h:

Go to the source code of this file.

Classes
struct	line::pfqn::RgfmcResult< T >
	Return value of pfqn_rgfmc, mirroring [G, lG]. More...

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
RgfmcResult< T >	line::pfqn::pfqn_rgfmc (const Matrix< T > &L, const std::vector< int > &N, const std::vector< T > &Z, const T &tol, std::size_t maxterms, const T &maxcancel)
	Multiclass Recursion by Generating Functions (RGF), with think times.
template<class T>
RgfmcResult< T >	line::pfqn::pfqn_rgfmc (const Matrix< T > &L, const std::vector< int > &N, const std::vector< T > &Z)
	Overload with the reference defaults (tol 1e-12, 1e6 terms, 15 nats).

Detailed Description

Multiclass Recursion by Generating Functions (RGF), with think times.

Templated port of matlab/src/api/pfqn/pfqn_rgfmc.m: the normalizing constant of a closed MULTICLASS product-form network by eliminating one class at a time by residues, finishing in the single-class convolution of pfqn_rgf.

P. G. Harrison, S. Coury, "On the asymptotic behaviour of closed multiclass queueing networks", Perf. Eval. 47:131-138, 2002, Thm 1, expresses the generating function of a q-class network through those of (q-1)-class ones; P. G. Harrison, T. T. Lee, "A new recursive algorithm for computing generating functions in closed multi-class queueing networks", IEEE MASCOTS 2004, eqs. (4)-(5), turns it into the RGF algorithm, bottoming out in single-class constants memoised by load vector (Sec. 3.4).

THINK TIMES ARE NOT IN EITHER PAPER. Both write the generating function as the RATIONAL prod_i (1 - rho_i z)^-m_i, every node a load-independent single server. An infinite server multiplies it by the ENTIRE exp(sum_r Z_r z_r), which breaks the step Thm 1 rests on: G_n(z') = -sum_i r_i holds only because the residues of n(z)/d(z) sum to zero when deg d >= deg n + 2 (Bertozzi and McKenna, SIAM Review 35(2):239-268, 1993, fact (IV), p. 246), and an exponential numerator does not decay at infinity. The delay is carried by their own repair, eqs. (3.19)-(3.21): only the first k_r+1 Taylor coefficients of exp(Z_r z_r) can reach the coefficient of z_r^k_r, so replacing the exponential by that polynomial is EXACT and leaves a rational integrand. The price is that the eliminated class's population re-enters the term count, which is precisely the population-insensitivity Harrison-Lee Sec. 4 advertises; the class kept for the base case pays nothing.

DEGENERACY. Thm 1 assumes rho_iq != rho_lq and its Conclusion leaves the tied case open. Two affine forms name the SAME pole only when PROPORTIONAL, so fusing proportional forms into one factor of summed multiplicity disposes of it; a tie in the eliminated class alone leaves a form with no constant term, which the recursion carries unchanged.

ARITHMETIC. The elimination is exact in exact arithmetic but is an ALTERNATING sum over residues, so near-coincident loads over an eliminated class destroy significance; the worst cancellation ratio is tracked and the routine REFUSES past maxcancel rather than returning a confidently wrong lG. Coefficients are carried in the log domain with a separate sign, so no Poisson weight or binomial is ever formed as a naive ratio; that is why the routine is gated on num_traits<T>::has_transcendental, as pfqn_rgf is.

Definition in file pfqn_rgfmc.h.