Busy period of a subnetwork from point evaluations of the normalizing constant. More...

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

Include dependency graph for pfqn_busyp_clw.h:

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
std::vector< double >	line::pfqn::pfqn_busyp_clw (const Matrix< T > &alpha, const Matrix< T > &mu, const std::vector< Matrix< T > > &P, const std::vector< double > &N, const std::vector< std::size_t > &subnet, const std::vector< std::size_t > &n, const Matrix< T > &gamma=Matrix< T >(), const std::vector< bool > &isdelay=std::vector< bool >(), const std::string &method="clw")
	Mean busy period of order n for the subnetwork, via NC point evaluations.

Detailed Description

Busy period of a subnetwork from point evaluations of the normalizing constant.

Templated port of matlab/src/api/pfqn/pfqn_busyp_clw.m, jar/src/main/java/jline/api/pfqn/Pfqn_busyp_clw.java and python/line_solver/api/pfqn/busyp_clw.py.

WHAT THIS BUYS OVER pfqn_busyp / pfqn_busyp_multiclass. Those walk the whole population ladder (the whole lattice, multichain) because the numerator sums over {|m| >= n}. The complement of that set is the SHELLS |m| <= n-1, and summing the product form over the WHOLE lattice is the full network's own normalizing constant, G_I and H convolving to it:

sum_{m : |m| >= n} G_I(m) H(N-m) = G(N) - sum_{m : |m| <= n-1} G_I(m) H(N-m)

so order n needs only the n lowest shells plus ONE evaluation of G(N). The ordinary busy period n=1 collapses to three constants,

b(1,I) = [G(N) - H(N)] / sum_r A_r(I) H(N-e_r)

all point evaluations at or near the full population, which is what the normalizing-constant methods are built for. This routine calls CLW (Choudhury-Leung-Whitt, J. ACM 42, 1995, numerical inversion of the generating function); any method returning lG(N) can take its place. The cost stops depending on N.

THE OPEN CASE NEEDS NO INVERSION. The subnetwork's constant sequence has generating function g(z) = prod_{i in I} f_i(z) and the tail is g(1) minus a partial sum, with f_i(1) = 1/(1-rho_i) at a single server and exp(rho_i) at an infinite one. That removes the tail TRUNCATION of the ladder routine, not just its cost: the tail is exact, and the C++ test checks it at == against the closed form.

ACCURACY: the numerator is a difference of two nearly equal quantities when the level set is unlikely, so the relative error grows with n – 6e-12 at n=1 against 2.7e-08 at n=N on a three-station closed model at N=20. Cost grows with n too, so the routine is most accurate where it is fastest.

SCOPE: CLW's generating function covers single-server and infinite-server stations, so a general load-dependent scaling belongs to pfqn_busyp_multiclass. The identity is for the AGGREGATE level set: a per-class one has complement {m_r <= n-1}, the whole lattice in the other chains, which buys nothing.

ARITHMETIC: log domain in double, as in the three reference implementations.

Definition in file pfqn_busyp_clw.h.

Namespaces

Functions

Detailed Description