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

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

Include dependency graph for pfqn_explicit_ld.h:

Namespaces
namespace	line
namespace	line::pfqn

Functions
template<class T>
ExplicitResult< T >	line::pfqn::pfqn_explicit_ld (const Matrix< T > &L, const std::vector< int > &N, const Matrix< T > &mu, 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 LIMITED LOAD-DEPENDENT network.

Detailed Description

Explicit closed-form normalizing constant of a multiclass LIMITED LOAD-DEPENDENT network.

Templated port of matlab/src/api/pfqn/pfqn_explicit_ld.m. Load-dependent counterpart of pfqn_explicit: it evaluates the same divided-difference form of G. Casale, "Accelerating Performance Inference over Closed Systems by Asymptotic Methods", ACM SIGMETRICS 2017, Corollary 3.2,

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

but substitutes for the single-class constant h_t(|N|) the limited load-dependent closed form of G. Casale, P. G. Harrison, W. H. Ong, "Facilitating Load-Dependent Queueing Analysis Through Factorization", Perform. Eval. 2021, Theorem 1, Eq. (8),

h_theta(N) = sum_{0<=v<s} g_sigma(N-|v|) prod_k phi_k(v_k) phi_k(v_k) = theta_k^v_k / prod_{t=1..v_k} alpha_k(t) * (1 - alpha_k(v_k)/alpha_k(s_k))

at the induced demands theta_k(t) = sum_r t_r L(k,r). Here alpha_k(.) = mu(k,.) is the load-dependent scaling of station k, s_k the population past which it stays constant, sigma_k = theta_k/alpha_k(s_k) the SCALED demands, and g_sigma the FIXED-RATE single-class constant at those scaled demands, which is exactly what pfqn_explicit evaluates in closed form (Eqs. 15 and 16). The result is explicit throughout, with no recursion over population; pfqn_gldsingle is the same constant by an O(M|N|^2) recursion instead.

TWO CONVENTIONS OF THEOREM 1 ARE NOT THOSE OF THE EQUILIBRIUM DISTRIBUTION. alpha_k(0) is taken as ZERO inside the bracket of phi_k, so that phi_k(0) = 1, even though the state probabilities use alpha_k(0) = 1; and g_sigma(n) = 0 for n < 0, which caps the outer sum at |v| <= |N|. With alpha_k(n) = min(n,s_k) the expression collapses to Gordon's multi-server formula, Oper. Res. 38(5), 1990, Eq. (29), but unlike that one it needs neither a multi-server shape nor distinct scaled demands.

LIMITED LOAD DEPENDENCE. Theorem 1 holds for any s_k with alpha_k(n) = alpha_k(s_k) for all n >= s_k, and a LARGER s_k is always admissible, so s_k is detected here as the smallest index whose value the tail of mu(k,:) repeats to within tol. A station whose rates never settle (an infinite server, mu(k,n) = n) gets s_k = |N|, which is still exact: populations above |N| do not occur, so redefining alpha_k there changes nothing. It is merely expensive, since the inner sum costs prod_k s_k terms, capped by |v| <= |N|. Think time is not admissible: a delay would have to enter g_sigma, whose closed form covers queues only.

ARITHMETIC. Both sums alternate in sign with terms far larger than the result, so they are evaluated as SIGNED log-sum-exps, and the routine is gated on num_traits<T>::has_transcendental exactly as pfqn_explicit is; a caller that wants the same constant in exact arithmetic wants pfqn_gld. phi_k is sign-definite when alpha_k increases, as a multi-server station does, and changes sign where alpha_k decreases, so a decreasing rate function costs digits in the inner sum too.

Definition in file pfqn_explicit_ld.h.

Namespaces

Functions

Detailed Description