api.dpfqn

dpfqn_ncld(P, N)

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

Convolution over the discrete-time product form with load dependence.

Parameters:

P – J-by-N matrix of service probabilities, P(j,n)=p_j(n) in (0,1).
N – Number of customers cycling in the J nodes.

Returns:

lG – Logarithm of the normalizing constant G(N,J). G: Row vector of normalizing constants G(k), k=0..N, in a common scale. W: J-by-(N+1) matrix of time-stationary node weights, same scale. Gc: J-by-(N+1) matrix of complement constants, cycle without node j. Wa: J-by-(N+1) matrix of arrival node weights, same scale as W.

PFQN_NCDTLD evaluates the discrete-time product form of a closed cycle of J state dependent Bernoulli servers. With q_j(n)=1-p_j(n) the queue length vector has the stationary law of Daduna (2001), theorem 3.2,

pi(n_1,…,n_J) = prod_j w_j(n_j) / G(N,J), w_j(n) = prod_{h=1}^{n-1} q_j(h) / prod_{h=1}^{n} p_j(h), w_j(0) = 1,

which reduces to the state independent form of PFQN_NCDT when p_j(n) does not depend on n. Note that w_j misses the factor q_j(n_j) in the numerator, so the extra 1/q_j on a busy node in the state independent case is not tied to the node being non-empty but to its actual queue length.

The constants are assembled by truncated convolution of the per-node weight vectors, together with the J complement constants (the cycle with node j removed) obtained from a prefix/suffix pass. All of G, W, Gc and Wa are returned in one common scale, so that the marginal law

P(X_j = n) = W(j,n+1) * Gc(j,N-n+1) / G(N+1)

is exact whatever the scale; lG carries the true log constant. Deconvolution is never used, so a node with a near-unit service probability does not destroy the accuracy of the other marginals.

Wa holds the weights of the arrival distribution of proposition 3.5, v_j(n) = w_j(n) q_j(n), the law seen by a customer joining node j with himself not counted:

Parr(X_j = n) = Wa(j,n+1) * Gc(j,N-n) / sum_m Wa(j,m+1) Gc(j,N-m),

defined on n = 0..N-1. It is not the time-stationary law, which is the discrete-time departure from the arrival theorem of continuous time.

Examples

P = repmat([0.5;0.25;0.7], 1, 5); [lG, G, W, Gc] = pfqn_ncdtld(P, 5); W(1,2)*Gc(1,5)/G(6) % P(X_1 = 1)

Reference: H. Daduna, Queueing Networks with Discrete Time Scale, LNCS 2046, Springer 2001, theorem 3.2 and proposition 3.5.

See also PFQN_NCDT, QSYS_BERNOULLI1, PFQN_NCLD

dpfqn_nc(p, N)

Normalizing constants of a discrete-time closed cycle of Bernoulli servers with state independent service probabilities.

Buzen-style recursions for the discrete-time closed cycle.

Parameters:

p – Row vector of per-slot service completion probabilities, p(j) in (0,1).
N – Number of customers cycling in the J nodes.

Returns:

lG – Logarithm of the time-stationary normalizing constant G(N,J). G: Time-stationary normalizing constant G(N,J). G1: Column vector of arrival normalizing constants, G1(k+1)=G_1(k,J).

PFQN_NCDT computes the two families of normalizing constants of a closed cycle of J state independent Bernoulli servers observed on a discrete time scale. With q(j)=1-p(j) the time-stationary law of the queue length vector is

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

i.e. the discrete-time product form of Daduna (2001), corollary 3.4, whose extra factor (1/q_j)^{1{n_j>0}} on the busy nodes is what distinguishes it from the continuous-time Gordon-Newell form. G(N,J) obeys 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),

with G(0,j)=1 and G(k,0)=0 for k>=1. Unlike the continuous-time convolution algorithm this recursion is not invariant to the numbering of the nodes.

G1 collects the arrival normalizing constants of proposition 3.17(b), the constants of the distribution seen by a customer joining a node, in which the arrival node carries the weight (q/p)^n with no 1/q factor. They obey proposition 3.19,

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

with G1(1,J)=1 and G1(2,J)=q_1/p_1 + sum_{j>=2} 1/p_j. By lemma 7.3 of the same reference the arrival constant is the same at every node, so one family suffices. Three consequences are what the discrete-time analyzer consumes:

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) of the reference 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.

G and G1 are returned in a common scale, which is unity unless the recursion had to be rescaled to keep (q/p)^N inside double range. Ratios such as G1(k)/G are exact in either case, and lG is always the true log constant.

Examples

[lG, G, G1] = pfqn_ncdt([0.5 0.25 0.7], 5); G1(end)/G % throughput per slot, 0.2483

Reference: H. Daduna, Queueing Networks with Discrete Time Scale, LNCS 2046, Springer 2001, corollary 3.4, propositions 3.17-3.19 and corollary 3.20.

See also PFQN_NCDTLD, QSYS_BERNOULLI1, PFQN_CA