pfqn_explicit.h File Reference

Explicit closed-form normalizing constant of a multiclass closed network. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <limits>
#include <string>
#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_explicit.h:

Go to the source code of this file.

Classes
struct	line::pfqn::ExplicitResult< T >
	Return value of pfqn_explicit, mirroring [lG, G, method, lossDigits]. More...

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
ExplicitResult< T >	line::pfqn::pfqn_explicit (const Matrix< T > &L, const std::vector< int > &N, double tol=std::numeric_limits< double >::epsilon(), const std::string &method="auto", double maxloss=std::numeric_limits< double >::infinity())
	Explicit closed-form normalizing constant of a multiclass closed network.

Detailed Description

Explicit closed-form normalizing constant of a multiclass closed network.

Templated port of matlab/src/api/pfqn/pfqn_explicit.m, i.e. Eqs. (15) and (16) of G. Casale, "Accelerating Performance Inference over Closed Systems by Asymptotic Methods", ACM SIGMETRICS 2017. Both instantiate the divided-difference form of Corollary 3.2,

G(N) = sum_{0<=t<=N} (-1)^(|N|-|t|)/(N_1!...N_R!) prod_r C(N_r,t_r) g_t(|N|)

by substituting a closed form for the single-class constant g_t(|N|) at the induced demands theta_k(t) = sum_r t_r L(k,r). Eq. (15) is Gordon's partial fraction and needs the induced demands PAIRWISE DISTINCT; Eq. (16) is the general partial-fraction expansion over the distinct values and their multiplicities, and reduces term by term to Eq. (15) when every multiplicity is one. The choice is automatic.

SINGLE CLASS. At R=1 the multiclass constant IS the single-class constant at demands L, so the outer sum is skipped: g_t(N) = t^N g_1(N) and sum_t (-1)^(N-t) t^N/(t!(N-t)!) = S(N,N) = 1. Running the difference anyway would add N alternating terms, and their cancellation, to a closed form that carries none of them. What is left is O(K^2) work at any population, which is why the single-class route is the cheap one on large populations.

ARITHMETIC. Both expressions alternate in sign with terms far larger than the result, so they are evaluated as SIGNED log-sum-exps: that removes the floating-point RANGE problem but not the cancellation, which is what makes multiprecision arithmetic necessary on all but small models. The routine is therefore gated on num_traits<T>::has_transcendental; a caller that wants the same constant in exact arithmetic wants pfqn_ca.

ADMISSIBILITY. Single-server load-independent queues only: infinite servers need the integral form of Corollary 3.4 and load-dependent rates need pfqn_explicit_ld, which keeps this closed form as its inner kernel.

Definition in file pfqn_explicit.h.