dpfqn_nc.h File Reference

Normalizing constants of a discrete-time closed cycle of Bernoulli servers. More...

#include <cmath>
#include <cstddef>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"

Include dependency graph for dpfqn_nc.h:

Go to the source code of this file.

Classes
struct	line::dpfqn::DtNcResult< T >
	Constants of the state independent cycle, in one common scale. More...
struct	line::dpfqn::DtNcLdResult< T >
	Constants of the state dependent cycle, in one common scale. More...

Namespaces
namespace	line
namespace	line::dpfqn

Functions
template<class T>
DtNcResult< T >	line::dpfqn::dpfqn_nc (const std::vector< T > &p, std::size_t N)
	Propositions 3.18 and 3.19 for a cycle with state independent service probabilities.
template<class T>
DtNcLdResult< T >	line::dpfqn::dpfqn_ncld (const std::vector< std::vector< T > > &P, std::size_t N)
	Theorem 3.2 for a cycle whose service probabilities depend on the local queue length.

Detailed Description

Normalizing constants of a discrete-time closed cycle of Bernoulli servers.

Templated port of matlab/src/api/dpfqn/dpfqn_nc.m and dpfqn_ncld.m. With q_j = 1 - p_j the queue length vector has the product form of Daduna (2001), corollary 3.4,

pi(n_1,...,n_J) = prod_j (q_j/p_j)^n_j (1/q_j)^{1{n_j>0}} / G(N,J),

whose extra factor on the busy nodes is what separates it from the continuous-time Gordon-Newell form: a homogeneous cycle is uniform on the state space in continuous time and is not here.

dpfqn_nc runs the three-term recursion of proposition 3.18,

G(k,j) = G(k,j-1) + (q_j/p_j) G(k-1,j) + G(k-1,j-1),

together with the arrival constants of proposition 3.19,

G1(k,J) = G(k-1,J-1) + (q_J/p_J) G1(k-1,J), k >= 3.

Unlike the continuous-time convolution algorithm neither recursion is invariant to the numbering of the nodes. By lemma 7.3 the arrival constant is the same at every node, so one family suffices and

throughput per slot X = G1(N,J) / G(N,J) (equal at every node), utilization U_j = X / p_j, tail probability P(X_j >= k) = (q_j/p_j)^k (1/q_j) G1(N-k+1,J) / G(N,J).

The last identity is corollary 3.20(a) with its index corrected: as printed there the right-hand side evaluates to P(X_j >= k+1). Corollary 3.20(c), which transfers the tail from node 1 to node j, holds for k >= 1 only; at k = 0 both tails are 1 while the stated ratio is q_1/q_j.

dpfqn_ncld takes the state dependent case of theorem 3.2 by truncated convolution of the per-node weights

w_j(n) = prod_{h=1}^{n-1} q_j(h) / prod_{h=1}^{n} p_j(h),

with the complement constants (the cycle without node j) from a prefix/suffix pass, so that P(X_j = n) = W[j][n] * Gc[j][N-n] / G[N]. Deconvolution is never used, so a node with a near-unit service probability does not spoil the accuracy of the other marginals.

Everything here is a rational function of the service probabilities, so the exact instantiation returns the constants with no rounding. That matters in the interesting regime: a slow node makes (q/p)^N large, and the double evaluation of the ratio G1(N-k+1)/G loses digits exactly there. No transcendental appears in any metric: every quantity the analyzer reads is a ratio of constants in the same common scale, and lG is a double-valued diagnostic obtained through to_double, as in solver_nc.h.

Definition in file dpfqn_nc.h.