pfqn_rgf.h File Reference

Recursion by Generating Functions (RGF) for the normalizing constant of a SINGLE-CLASS closed product-form network with replicated stations. More...

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

Include dependency graph for pfqn_rgf.h:

Go to the source code of this file.

Classes
struct	line::pfqn::RgfResult< T >
	Return value of pfqn_rgf, mirroring [G, lG, lg]. More...

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
RgfResult< T >	line::pfqn::pfqn_rgf (const std::vector< T > &L, int N, const T &Z)
	Recursion by Generating Functions (RGF) for the normalizing constant of a SINGLE-CLASS closed product-form network with replicated stations.
template<class T>
RgfResult< T >	line::pfqn::pfqn_rgf (const std::vector< T > &L, int N)
	Overload without a delay.

Detailed Description

Recursion by Generating Functions (RGF) for the normalizing constant of a SINGLE-CLASS closed product-form network with replicated stations.

Templated port of matlab/src/api/pfqn/pfqn_rgf.m, i.e. Property 1 of J. Coury and P. G. Harrison, "Asymptotic properties of queuing networks", IEE Proc.-Comput. Digit. Tech. 144(5):247-254, 1997.

WHAT MAKES IT DIFFERENT FROM BUZEN. Convolution proceeds per GENERATING FUNCTION rather than per station: a group of m stations sharing one demand p collapses into the single negative-binomial sequence r(k) = C(k+m-1,k) p^k, so the group costs one convolution pass instead of m. The delay contributes the Poisson sequence r(k) = Z^k / k!. Convolving the G distinct sequences yields g(0..N) exactly, and lG = log g(N).

Cost O(G N^2) against Buzen's O(M N), so RGF is the cheaper route precisely when the model is heavily replicated and the population moderate (G N < M).

ARITHMETIC. The whole recursion runs in the LOG domain – that is the point of the routine, since no intermediate can then overflow or underflow – so it is gated on num_traits<T>::has_transcendental. A caller that wants the same constant in exact arithmetic wants pfqn_ca, which computes it by the ordinary convolution over the rationals.

SINGLE CLASS BY CONSTRUCTION. Grouping stations by their demand only defines a sequence when the demand is a scalar, so a multiclass argument is refused here by name; pfqn_nc's 'rgf' branch sends a multiclass model to pfqn_ca instead, which is what the reference does.

Definition in file pfqn_rgf.h.