Function File: [U, R, Q, X, G] = qncsmva (N, S, V)
Function File: [U, R, Q, X, G] = qncsmva (N, S, V, m)
Function File: [U, R, Q, X, G] = qncsmva (N, S, V, m, Z)

Analyze closed, single class queueing networks using the exact Mean Value Analysis (MVA) algorithm.

The following queueing disciplines are supported: FCFS, LCFS-PR, PS and IS (Infinite Server). This function supports fixed-rate service centers or multiple server nodes. For general load-dependent service centers, use the function qncsmvald instead.

Additionally, the normalization constant G(n), n=0, …, N is computed; G(n) can be used in conjunction with the BCMP theorem to compute steady-state probabilities.

INPUTS

N

Population size (number of requests in the system, N ≥ 0). If N == 0, this function returns U = R = Q = X = 0

S(k)

mean service time at center k (S(k) ≥ 0).

V(k)

average number of visits to service center k (V(k) ≥ 0).

Z

External delay for customers (Z ≥ 0). Default is 0.

m(k)

number of servers at center k (if m is a scalar, all centers have that number of servers). If m(k) < 1, center k is a delay center (IS); otherwise it is a regular queueing center (FCFS, LCFS-PR or PS) with m(k) servers. Default is m(k) = 1 for all k (each service center has a single server).

OUTPUTS

U(k)

If k is a FCFS, LCFS-PR or PS node (m(k) ≥ 1), then U(k) is the utilization of center k, 0 ≤ U(k) ≤ 1. If k is an IS node (m(k) < 1), then U(k) is the traffic intensity defined as X(k)*S(k). In this case the value of U(k) may be greater than one.

R(k)

center k response time. The Residence Time at center k is R(k) * V(k). The system response time Rsys can be computed either as Rsys = N/Xsys - Z or as Rsys = dot(R,V)

Q(k)

average number of requests at center k. The number of requests in the system can be computed either as sum(Q), or using the formula N-Xsys*Z.

X(k)

center K throughput. The system throughput Xsys can be computed as Xsys = X(1) / V(1)

G(n)

Normalization constants. G(n+1) contains the value of the normalization constant G(n), n=0, …, N as array indexes in Octave start from 1. G(n) can be used in conjunction with the BCMP theorem to compute steady-state probabilities.

NOTES

In presence of load-dependent servers (i.e., if m(k)>1 for some k), the MVA algorithm is known to be numerically unstable. Generally, this issue manifests itself as negative values for the response times or utilizations. This is not a problem of the queueing toolbox, but of the MVA algorithm, and has currently no known solution. This function prints a warning if numerical problems are detected; the warning can be disabled with the command warning("off", "qn:numerical-instability").

REFERENCES

  • M. Reiser and S. S. Lavenberg, Mean-Value Analysis of Closed Multichain Queuing Networks, Journal of the ACM, vol. 27, n. 2, April 1980, pp. 313–322. 10.1145/322186.322195

This implementation is described in R. Jain , The Art of Computer Systems Performance Analysis, Wiley, 1991, p. 577. Multi-server nodes are treated according to G. Bolch, S. Greiner, H. de Meer and K. Trivedi, Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications, Wiley, 1998, Section 8.2.1, "Single Class Queueing Networks".

See also: qncsmvald,qncscmva.

Demonstration 1

The following code

 S = [ 0.125 0.3 0.2 ];
 V = [ 16 10 5 ];
 N = 20;
 m = ones(1,3);
 Z = 4;
 [U R Q X] = qncsmva(N,S,V,m,Z);
 X_s = X(1)/V(1); # System throughput
 R_s = dot(R,V); # System response time
 printf("\t    Util      Qlen     RespT      Tput\n");
 printf("\t--------  --------  --------  --------\n");
 for k=1:length(S)
   printf("Dev%d\t%8.4f  %8.4f  %8.4f  %8.4f\n", k, U(k), Q(k), R(k), X(k) );
 endfor
 printf("\nSystem\t          %8.4f  %8.4f  %8.4f\n\n", N-X_s*Z, R_s, X_s );

Produces the following output

Util      Qlen     RespT      Tput
	--------  --------  --------  --------
Dev1	  0.6665    1.9906    0.3733    5.3319
Dev2	  0.9997   16.1767    4.8543    3.3325
Dev3	  0.3332    0.4997    0.2999    1.6662

System	           18.6670   56.0156    0.3332

Package: queueing