File: queueingnetworks.texi

package info (click to toggle)
octave-queueing 1.2.8-1
links: PTS, VCS
area: main
in suites: forky, sid, trixie
size: 2,288 kB
sloc: makefile: 56
file content (3990 lines) | stat: -rw-r--r-- 122,091 bytes
@c This file has been automatically generated from queueingnetworks.txi
@c by proc.m. Do not edit this file, all changes will be lost

@c -*- texinfo -*-

@c Copyright (C) 2008, 2009, 2010, 2011, 2012, 2014, 2016, 2018 Moreno Marzolla
@c
@c This file is part of the queueing package.
@c
@c The queueing package is free software; you can redistribute it
@c and/or modify it under the terms of the GNU General Public License
@c as published by the Free Software Foundation; either version 3 of
@c the License, or (at your option) any later version.
@c
@c The queueing package is distributed in the hope that it will be
@c useful, but WITHOUT ANY WARRANTY; without even the implied warranty
@c of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
@c GNU General Public License for more details.
@c
@c You should have received a copy of the GNU General Public License
@c along with the queueing package; see the file COPYING.  If not, see
@c <http://www.gnu.org/licenses/>.

@node Queueing Networks
@chapter Queueing Networks

@menu
* Introduction to QNs::             A brief introduction to Queueing Networks
* Single Class Models::             Queueing models with a single job class
* Multiple Class Models::           Queueing models with multiple job classes
* Generic Algorithms::              High-level functions for QN analysis
* Bounds Analysis::                 Computation of asymptotic performance bounds
* QN Analysis Examples::            Queueing Networks analysis examples
@end menu

@cindex queueing networks

@c
@c INTRODUCTION
@c
@node Introduction to QNs
@section Introduction to QNs

Queueing Networks (QN) are a simple modeling notation that can be used
to analyze many kinds of systems. In its simplest form, a QN is made
of @math{K} service centers; center @math{k} has a queue connected to
@math{m_k} (usually identical) servers. Arriving customers (requests)
join the queue if there is at least one slot available. Requests are
served according to a (de)queueing policy (e.g., FIFO). After service
completes, requests leave the server and can join another queue or
exit from the system.

@cindex delay center
@cindex infinite server

Service centers where @math{m_k = \infty} are called @emph{delay
centers} or @emph{infinite servers}. In this kind of centers, there is
always one available server, so that queueing never occurs.

Requests join the queue according to a @emph{queueing policy}, such as:

@cindex First-Come-First-Served
@cindex FCFS
@cindex Last-Come-First-Served Preemptive Resume
@cindex LCFS-PR
@cindex Processor Sharing
@cindex PS
@cindex Infinite Server
@cindex IS

@table @strong

@item FCFS
First-Come-First-Served

@item LCFS-PR
Last-Come-First-Served, Preemptive Resume

@item PS
Processor Sharing

@item IS
Infinite Server (@math{m_k = \infty}).

@end table

Queueing networks can be @emph{open} or @emph{closed}. In open
networks there is an infinite population of requests; new customers
are generated outside the system, and eventually leave the network. In
closed networks there is a fixed population of request that never
leave the system.

@cindex single class queueing network
@cindex multiple class queueing network
@cindex queueing network, single class
@cindex queueing network, multiple class

Queueing models can have a single request class (@emph{single class
models}), meaning that all requests behave in the same way (e.g., they
spend the same average time on each particular server). In
@emph{multiple class models} there are multiple request classes, each
with its own parameters (e.g., with different service times or
different routing probabilities). Furthermore, in multiclass models
there can be open and closed chains of requests at the same time.

@cindex product-form queueing network
@cindex queueing network, product-form

A particular class of QN models, @emph{product-form} networks, is of
particular interest. Product-form networks fulfill the following
assumptions:

@itemize

@item The network can consist of open and closed job classes.

@item The following queueing disciplines are allowed: FCFS, PS, LCFS-PR and IS.

@item Service times for FCFS nodes must be exponentially distributed and
class-independent. Service centers at PS, LCFS-PR and IS nodes can
have any kind of service time distribution with a rational Laplace
transform.  Furthermore, for PS, LCFS-PR and IS nodes, different
classes of customers can have different service times.

@item The service rate of an FCFS node is only allowed to depend on the
number of jobs at this node; in a PS, LCFS-PR and IS node the service
rate for a particular job class can also depend on the number of jobs
of that class at the node.

@item In open networks two kinds of arrival processes are allowed: i) the
arrival process is Poisson, with arrival rate @math{\lambda} that can
depend on the number of jobs in the network. ii) the arrival process
consists of @math{C} independent Poisson arrival streams where the
@math{C} job sources are assigned to the @math{C} chains; the arrival
rate can be load dependent.

@end itemize

Product-form networks are attractive because steady-state performance
measures can be efficiently computed.

@c
@c Single Class Models
@c

@node Single Class Models
@section Single Class Models

@cindex single class queueing network
@cindex queueing network, single class

In single class models, all requests are indistinguishable and belong
to the same class. This means that every request has the same average
service time, and all requests move through the system with the same
routing probabilities.

@noindent @strong{Model Inputs}

@cindex external arrival rate
@cindex service time
@cindex routing probability matrix
@cindex average number of visits

@table @asis

@item @math{{@lambda}_k}
(Open models only) External arrival rate to service center @math{k}.

@item @math{@lambda}
(Open models only) Overall external arrival rate to the system as a whole: @math{\lambda = \sum_k \lambda_k}.

@item @math{N}
(Closed models only) Total number of requests in the system.

@item @math{S_k}
Mean service time at center @math{k}. @math{S_k} is the average time
elapsed from service start to service completion at center @math{k}.

@item @math{P_{i, j}}
Routing probability matrix. @math{{\bf P} = [P_{i, j}]} is a @math{K
\times K} matrix where @math{P_{i, j}} is the probability that a
request completing service at center @math{i} is routed to center
@math{j}. The probability that a request leaves the system after being
served at center @math{i} is @math{\left(1-\sum_{j=1}^K P_{i, j}\right)}.

@item @math{V_k}
Mean number of visits to center @math{k} (also called @emph{visit
ratio} or @emph{relative arrival rate}).

@end table

@noindent @strong{Model Outputs}

@cindex utilization
@cindex response time
@cindex average number of customers
@cindex throughput
@cindex system response time
@cindex system throughput

@table @math

@item U_k
Utilization of service center @math{k}. The utilization is defined as
the fraction of time in which the resource is busy (i.e., the server
is processing requests).  If center @math{k} is a single-server or
multiserver node, then @math{0 @leq{} U_k @leq{} 1}. If center
@math{k} is an infinite server node (delay center), then @math{U_k}
denotes the @emph{traffic intensity} and is defined as @math{U_k = X_k
S_k}; in this case the utilization may be greater than one.

@item R_k
Average response time of service center @math{k}, defined as the mean
time between the arrival of a request in the queue and service
completion of the same request.

@item Q_k
Average number of requests in center @math{k}; this includes both the
requests in the queue and those being served.

@item X_k
Throughput of service center @math{k}. The throughput is the rate of
job completions, i.e., the average number of jobs completed over a
given time interval.

@end table

@noindent Given the output parameters above, additional performance measures can
be computed:

@table @math

@item X
System throughput, @math{X = X_k / V_k} for any @math{k} for 
which @math{V_k \neq 0}

@item R
System response time, @math{R = \sum_{k=1}^K R_k V_k}

@item Q
Average number of requests in the system, @math{Q = \sum_{k=1}^K Q_k}; for
closed systems, this can be written as @math{Q = N-XZ};

@end table

For open, single class models, the scalar @math{\lambda} denotes the
external arrival rate of requests to the system. The average number of
visits @math{V_j} satisfy the following equation:

@iftex
@tex
$$ V_j = P_{0, j} + \sum_{i=1}^K V_i P_{i, j} \quad j=1, \ldots, K $$
@end tex
@end iftex
@ifnottex
@example
@group
                  K
                 ___
                \
V_j = P_(0, j) + >   V_i P_(i, j)    j=1,...,K
                /___
                 i=1
@end group
@end example
@end ifnottex

@noindent where @math{P_{0, j}} is the probability that an external
request goes to center @math{j}. If we denote with @math{\lambda_j}
the external arrival rate to center @math{j}, and @math{\lambda =
\sum_j \lambda_j} the overall external arrival rate, then @math{P_{0,
j} = \lambda_j / \lambda}.

For closed models, the visit ratios satisfy the following equation:

@iftex
@tex
$$\left\{\eqalign{V_j & = \sum_{i=1}^K V_i P_{i, j} \quad j=1, \ldots, K \cr
                  V_r & = 1 \quad \hbox{for a selected reference station $r$}}\right. $$
@end tex
@end iftex
@ifnottex
@example
/
|         K
|        ___
|       \
| V_j =  >   V_i P_(i, j)     j=1,...,K
|       /___
|        i=1
|
| V_r = 1                     for a selected reference station r
\
@end example
@end ifnottex

Note that the set of traffic equations @math{V_j = \sum_{i=1}^K V_i
P_{i, j}} alone can only be solved up to a multiplicative constant; to
get a unique solution we impose an additional constraint @math{V_r =
1} for some @math{1 @leq{} r @leq{} K}. This constraint is equivalent
to defining station @math{r} as the @emph{reference station}; the
default is @math{r=1}, @pxref{doc-qncsvisits}. A job that returns to
the reference station is assumed to have completed its activity
cycle. The network throughput is set to the throughput of the
reference station.

@anchor{doc-qncsvisits}


@deftypefn {Function File} {@var{V} =} qncsvisits (@var{P})
@deftypefnx {Function File} {@var{V} =} qncsvisits (@var{P}, @var{r})

Compute the mean number of visits to the service centers of a
single class, closed network with @math{K} service centers.

@strong{INPUTS}

@table @code

@item @var{P}(i,j)
probability that a request which completed service at center
@math{i} is routed to center @math{j} (@math{K \times K} matrix).
For closed networks it must hold that @code{sum(@var{P},2)==1}. The
routing graph must be strongly connected, meaning that each node
must be reachable from every other node.

@item @var{r}
Index of the reference station, @math{r \in @{1, @dots{}, K@}};
Default @code{@var{r}=1}. The traffic equations are solved by
imposing the condition @code{@var{V}(r) = 1}. A request returning to
the reference station completes its activity cycle.

@end table

@strong{OUTPUTS}

@table @code

@item @var{V}(k)
average number of visits to service center @math{k}, assuming
@math{r} as the reference station.

@end table

@end deftypefn


@anchor{doc-qnosvisits}


@deftypefn {Function File} {@var{V} =} qnosvisits (@var{P}, @var{lambda})

Compute the average number of visits to the service centers of a single
class open Queueing Network with @math{K} service centers.

@strong{INPUTS}

@table @code

@item @var{P}(i,j)
is the probability that a request which completed service at center
@math{i} is routed to center @math{j} (@math{K \times K} matrix).

@item @var{lambda}(k)
external arrival rate to center @math{k}.

@end table

@strong{OUTPUTS}

@table @code

@item @var{V}(k)
average number of visits to server @math{k}.

@end table

@end deftypefn


@c
@c
@c
@noindent @strong{EXAMPLE}

@float Figure,fig:qn_closed_single
@center @image{./qn_closed_single,3in}
@caption{Closed network with a single class of requests}
@end float

@ref{fig:qn_closed_single} shows a closed queueing network with a
single class of requests. The network has three service centers,
labeled @emph{CPU}, @emph{Disk1} and @emph{Disk2}, and is known as a
@emph{central server} model of a computer system. Requests spend some
time at the CPU, which is represented by a PS (Processor Sharing)
node. After that, requests are routed to Disk1 with probability
@math{0.3}, and to Disk2 with probability @math{0.7}. Both Disk1 and
Disk2 are FCFS nodes.

If we label the servers as CPU=1, Disk1=2, Disk2=3, we can define the
routing matrix as follows:

@iftex
@tex
$$
{\bf P} = \pmatrix{ 0 & 0.3 & 0.7 \cr
                    1 & 0 & 0 \cr
                    1 & 0 & 0 }
$$
@end tex
@end iftex
@ifnottex
@example
    / 0  0.3  0.7 \
P = | 1  0    0   |
    \ 1  0    0   /
@end example
@end ifnottex

The visit ratios @math{V}, using station 1 as the reference
station, can be computed with:

@example
@verbatim
 P = [0 0.3 0.7; ...
      1 0   0  ; ...
      1 0   0  ];
 V = qncsvisits(P)
@end verbatim
   @result{} V = 1.00000   0.30000   0.70000
@end example

@noindent @strong{EXAMPLE}

@float Figure,fig:qn_open_single
@center @image{./qn_open_single,3in}
@caption{Open Queueing Network with a single class of requests}
@end float

@ref{fig:qn_open_single} shows a open QN with a single class of
requests. The network has the same structure as the one in
@ref{fig:qn_closed_single}, with the difference that here we have a
stream of jobs arriving from outside the system, at a rate
@math{\lambda}. After service completion at the CPU, a job can leave
the system with probability @math{0.2}, or be transferred to other
nodes with the probabilities shown in the figure.

The routing matrix is

@iftex
@tex
$$
{\bf P} = \pmatrix{ 0 & 0.3 & 0.5 \cr
                    1 & 0 & 0 \cr
                    1 & 0 & 0 }
$$
@end tex
@end iftex
@ifnottex
@example
    / 0  0.3  0.5 \
P = | 1  0    0   |
    \ 1  0    0   /
@end example
@end ifnottex

If we let @math{\lambda = 1.2}, we can compute the visit ratios
@math{V} as follows:

@example
@verbatim
 p = 0.3;
 lambda = 1.2
 P = [0 0.3 0.5; 1 0 0; 1 0 0];
 V = qnosvisits(P,[1.2 0 0])
@end verbatim
   @result{} V = 5.0000   1.5000   2.5000
@end example

Function @command{qnosvisits} expects a vector with @math{K} elements
as a second parameter, for open networks only. The vector contains the
arrival rates at each individual node; since in our example external
arrivals exist only for node @math{S_1} with rate @math{\lambda =
1.2}, the second parameter is @code{[1.2, 0, 0]}.

@c
@c Open Networks
@c
@subsection Open Networks

Jackson networks satisfy the following conditions:

@itemize

@item
There is only one job class in the network; the total number of jobs
in the system is unbounded.

@item
There are @math{K} service centers in the network. Each service center
may have Poisson arrivals from outside the system. A job can leave
the system from any node.

@item
Arrival rates as well as routing probabilities are independent from
the number of nodes in the network.

@item
External arrivals and service times at the service centers are
exponentially distributed, and in general can be load-dependent.

@item
Service discipline at each node is FCFS

@end itemize

We define the @emph{joint probability vector} @math{\pi(n_1,
@dots{}, n_K)} as the steady-state probability that there are @math{n_k}
requests at service center @math{k}, for all @math{k=1, @dots{}, N}.
Jackson networks have the property that the joint probability is the
product of the marginal probabilities @math{\pi_k}:

@iftex
@tex
$$ \pi(n_1, \ldots, n_K) = \prod_{k=1}^K \pi_k(n_k) $$
@end tex
@end iftex
@ifnottex
@example
@var{joint_prob} = prod( @var{pi} )
@end example
@end ifnottex

@noindent where @math{\pi_k(n_k)} is the steady-state probability
that there are @math{n_k} requests at service center @math{k}.

@anchor{doc-qnos}


@deftypefn {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnos (@var{lambda}, @var{S}, @var{V})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnos (@var{lambda}, @var{S}, @var{V}, @var{m})

@cindex open network, single class
@cindex BCMP network

Analyze open, single class BCMP queueing networks with @math{K} service centers.

This function works for a subset of BCMP single-class open networks
satisfying the following properties:

@itemize

@item The allowed service disciplines at network nodes are: FCFS,
PS, LCFS-PR, IS (infinite server);

@item Service times are exponentially distributed and
load-independent;

@item Center @math{k} can consist of @code{@var{m}(k) @geq{} 1}
identical servers.

@item Routing is load-independent

@end itemize

@strong{INPUTS}

@table @code

@item @var{lambda}
Overall external arrival rate (@code{@var{lambda}>0}).

@item @var{S}(k)
average service time at center @math{k} (@code{@var{S}(k)>0}).

@item @var{V}(k)
average number of visits to center @math{k} (@code{@var{V}(k) @geq{} 0}).

@item @var{m}(k)
number of servers at center @math{i}. If @code{@var{m}(k) < 1},
enter @math{k} is a delay center (IS); otherwise it is a regular
queueing center with @code{@var{m}(k)} servers. Default is
@code{@var{m}(k) = 1} for all @math{k}.

@end table

@strong{OUTPUTS}

@table @code

@item @var{U}(k)
If @math{k} is a queueing center,
@code{@var{U}(k)} is the utilization of center @math{k}.
If @math{k} is an IS node, then @code{@var{U}(k)} is the
@emph{traffic intensity} defined as @code{@var{X}(k)*@var{S}(k)}.

@item @var{R}(k)
center @math{k} average response time.

@item @var{Q}(k)
average number of requests at center @math{k}.

@item @var{X}(k)
center @math{k} throughput.

@end table

@strong{REFERENCES}

@itemize
@item
G. Bolch, S. Greiner, H. de Meer and K. Trivedi, @cite{Queueing Networks
and Markov Chains: Modeling and Performance Evaluation with Computer
Science Applications}, Wiley, 1998
@end itemize

@xseealso{qnopen,qnclosed,qnosvisits}

@end deftypefn


From the results computed by this function, it is possible to derive
other quantities of interest as follows:

@itemize

@item
@strong{System Response Time}: The overall system response time
can be computed as
@iftex
@tex
$R_s = \sum_{k=1}^K V_k R_k$
@end tex
@end iftex
@ifnottex
@code{R_s = dot(V,R);}
@end ifnottex

@item
@strong{Average number of requests}: The average number of requests
in the system can be computed as:
@iftex
@tex
$$Q_{avg} = \sum_{k=1}^K Q_k$$
@end tex
@end iftex
@ifnottex
@code{Q_avg = sum(Q)}
@end ifnottex

@end itemize

@noindent @strong{EXAMPLE}

@example
@verbatim
 lambda = 3;
 V = [16 7 8];
 S = [0.01 0.02 0.03];
 [U R Q X] = qnos( lambda, S, V );
 R_s = dot(R,V) # System response time
 N = sum(Q) # Average number in system
@end verbatim
@print{} R_s =  1.4062
@print{} N =  4.2186
@end example

@c
@c Closed Networks
@c
@subsection Closed Networks

@anchor{doc-qncsmva}


@deftypefn {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}, @var{G}] =} qncsmva (@var{N}, @var{S}, @var{V})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}, @var{G}] =} qncsmva (@var{N}, @var{S}, @var{V}, @var{m})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}, @var{G}] =} qncsmva (@var{N}, @var{S}, @var{V}, @var{m}, @var{Z})

@cindex Mean Value Analysys (MVA)
@cindex closed network, single class
@cindex normalization constant

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 @code{qncsmvald} instead.

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

@strong{INPUTS}

@table @code

@item @var{N}
Population size (number of requests in the system, @code{@var{N} @geq{} 0}).
If @code{@var{N} == 0}, this function returns
@code{@var{U} = @var{R} = @var{Q} = @var{X} = 0}

@item @var{S}(k)
mean service time at center @math{k} (@code{@var{S}(k) @geq{} 0}).

@item @var{V}(k)
average number of visits to service center @math{k} (@code{@var{V}(k) @geq{} 0}).

@item @var{Z}
External delay for customers (@code{@var{Z} @geq{} 0}). Default is 0.

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

@end table

@strong{OUTPUTS}

@table @code

@item @var{U}(k)
If @math{k} is a FCFS, LCFS-PR or PS node (@code{@var{m}(k) @geq{}
1}), then @code{@var{U}(k)} is the utilization of center @math{k},
@math{0 @leq{} U(k) @leq{} 1}. If @math{k} is an IS node
(@code{@var{m}(k) < 1}), then @code{@var{U}(k)} is the @emph{traffic
intensity} defined as @code{@var{X}(k)*@var{S}(k)}. In this case the
value of @code{@var{U}(k)} may be greater than one.

@item @var{R}(k)
center @math{k} response time. The @emph{Residence Time} at center
@math{k} is @code{@var{R}(k) * @var{V}(k)}. The system response
time @var{Rsys} can be computed either as @code{@var{Rsys} =
@var{N}/@var{Xsys} - Z} or as @code{@var{Rsys} =
dot(@var{R},@var{V})}

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

@item @var{X}(k)
center @math{K} throughput. The system throughput @var{Xsys} can be
computed as @code{@var{Xsys} = @var{X}(1) / @var{V}(1)}

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

@end table

@strong{NOTES}

In presence of load-dependent servers (i.e., if @code{@var{m}(k)>1}
for some @math{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 @code{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 @code{warning("off", "qn:numerical-instability")}.

@strong{REFERENCES}

@itemize
@item
M. Reiser and S. S. Lavenberg, @cite{Mean-Value Analysis of Closed
Multichain Queuing Networks}, Journal of the ACM, vol. 27, n. 2, April
1980, pp. 313--322. @uref{http://doi.acm.org/10.1145/322186.322195, 10.1145/322186.322195}
@end itemize

This implementation is described in R. Jain , @cite{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, @cite{Queueing Networks and Markov Chains:
Modeling and Performance Evaluation with Computer Science
Applications}, Wiley, 1998, Section 8.2.1, "Single Class Queueing
Networks".

@xseealso{qncsmvald,qncscmva}

@end deftypefn



@noindent @strong{EXAMPLE}

@example
@verbatim
 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 );
@end verbatim
@end example

@c
@c MVA for single class, closed networks with load dependent servers
@c
@anchor{doc-qncsmvald}


@deftypefn {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncsmvald (@var{N}, @var{S}, @var{V})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncsmvald (@var{N}, @var{S}, @var{V}, @var{Z})

@cindex Mean Value Analysys (MVA)
@cindex MVA
@cindex closed network, single class
@cindex load-dependent service center

Mean Value Analysis algorithm for closed, single class queueing
networks with @math{K} service centers and load-dependent service
times. This function supports FCFS, LCFS-PR, PS and IS nodes. For
networks with only fixed-rate centers and multiple-server
nodes, the function @code{qncsmva} is more efficient.

@strong{INPUTS}

@table @code

@item @var{N}
Population size (number of requests in the system, @code{@var{N} @geq{} 0}).
If @code{@var{N} == 0}, this function returns @code{@var{U} = @var{R} = @var{Q} = @var{X} = 0}

@item @var{S}(k,n)
mean service time at center @math{k}
where there are @math{n} requests, @math{1 @leq{} n
@leq{} N}. @code{@var{S}(k,n)} @math{= 1 / \mu_{k}(n)},
where @math{\mu_{k}(n)} is the service rate of center @math{k}
when there are @math{n} requests.

@item @var{V}(k)
average number of visits to service center @math{k} (@code{@var{V}(k) @geq{} 0}).

@item @var{Z}
external delay ("think time", @code{@var{Z} @geq{} 0}); default 0.

@end table

@strong{OUTPUTS}

@table @code

@item @var{U}(k)
utilization of service center @math{k}. The
utilization is defined as the probability that service center
@math{k} is not empty, that is, @math{U_k = 1-\pi_k(0)} where
@math{\pi_k(0)} is the steady-state probability that there are 0
jobs at service center @math{k}.

@item @var{R}(k)
response time on service center @math{k}.

@item @var{Q}(k)
average number of requests in service center @math{k}.

@item @var{X}(k)
throughput of service center @math{k}.

@end table

@strong{NOTES}

In presence of load-dependent servers, the MVA algorithm is known
to be numerically unstable. Generally this problem manifests itself
as negative response times or utilization.

@strong{REFERENCES}

@itemize
@item
M. Reiser and S. S. Lavenberg, @cite{Mean-Value Analysis of Closed
Multichain Queuing Networks}, Journal of the ACM, vol. 27, n. 2,
April 1980, pp. 313--322. @uref{http://doi.acm.org/10.1145/322186.322195, 10.1145/322186.322195}
@end itemize

This implementation is described in G. Bolch, S. Greiner, H. de Meer
and K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling
and Performance Evaluation with Computer Science Applications}, Wiley,
1998, Section 8.2.4.1, ``Networks with Load-Dependent Service: Closed
Networks''.

@xseealso{qncsmva}

@end deftypefn


@c
@c CMVA for single class, closed networks with a single load dependent servers
@c
@anchor{doc-qncscmva}


@deftypefn {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncscmva (@var{N}, @var{S}, @var{Sld}, @var{V})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncscmva (@var{N}, @var{S}, @var{Sld}, @var{V}, @var{Z})

@cindex conditional MVA (CMVA)
@cindex Mean Value Analysis, conditional (CMVA)
@cindex closed network, single class
@cindex CMVA

Conditional MVA (CMVA) algorithm, a numerically stable variant of
MVA. This function supports a network of @math{M @geq{} 1} service
centers and a single delay center. Servers @math{1, @dots{}, (M-1)}
are load-independent; server @math{M} is load-dependent.

@strong{INPUTS}

@table @code

@item @var{N}
Number of requests in the system, @code{@var{N} @geq{} 0}. If
@code{@var{N} == 0}, this function returns @code{@var{U} = @var{R}
= @var{Q} = @var{X} = 0}

@item @var{S}(k)
mean service time on server @math{k = 1, @dots{}, (M-1)}
(@code{@var{S}(k) > 0}). If there are no fixed-rate servers, then
@code{S = []}

@item @var{Sld}(n)
inverse service rate at server @math{M} (the load-dependent server)
when there are @math{n} requests, @math{n=1, @dots{}, N}.
@code{@var{Sld}(n) = } @math{1 / \mu(n)}.

@item @var{V}(k)
average number of visits to service center @math{k=1, @dots{}, M},
where @code{@var{V}(k) @geq{} 0}. @code{@var{V}(1:M-1)} are the
visit rates to the fixed rate servers; @code{@var{V}(M)} is the
visit rate to the load dependent server.

@item @var{Z}
External delay for customers (@code{@var{Z} @geq{} 0}). Default is 0.

@end table

@strong{OUTPUTS}

@table @code

@item @var{U}(k)
center @math{k} utilization (@math{k=1, @dots{}, M})

@item @var{R}(k)
response time of center @math{k} (@math{k=1, @dots{}, M}). The
system response time @var{Rsys} can be computed as @code{@var{Rsys}
= @var{N}/@var{Xsys} - Z}

@item @var{Q}(k)
average number of requests at center @math{k} (@math{k=1, @dots{}, M}).

@item @var{X}(k)
center @math{k} throughput (@math{k=1, @dots{}, M}).

@end table

@strong{REFERENCES}

@itemize
@item
G. Casale. @cite{A note on stable flow-equivalent aggregation in
closed networks}. Queueing Syst. Theory Appl., 60:193–-202, December
2008, @uref{http://dx.doi.org/10.1007/s11134-008-9093-6, 10.1007/s11134-008-9093-6}
@end itemize

@end deftypefn


@c
@c Approximate MVA for single class, closed networks
@c
@anchor{doc-qncsmvaap}


@deftypefn {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncsmvaap (@var{N}, @var{S}, @var{V})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncsmvaap (@var{N}, @var{S}, @var{V}, @var{m})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncsmvaap (@var{N}, @var{S}, @var{V}, @var{m}, @var{Z})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncsmvaap (@var{N}, @var{S}, @var{V}, @var{m}, @var{Z}, @var{tol})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncsmvaap (@var{N}, @var{S}, @var{V}, @var{m}, @var{Z}, @var{tol}, @var{iter_max})

@cindex Mean Value Analysys (MVA), approximate
@cindex MVA, approximate
@cindex approximate MVA
@cindex closed network, single class
@cindex closed network, approximate analysis

Analyze closed, single class queueing networks using the Approximate
Mean Value Analysis (MVA) algorithm. This function is based on
approximating the number of customers seen at center @math{k} when a
new request arrives as @math{Q_k(N) \times (N-1)/N}. This function
only handles single-server and delay centers; if your network
contains general load-dependent service centers, use the function
@code{qncsmvald} instead.

@strong{INPUTS}

@table @code

@item @var{N}
Population size (number of requests in the system, @code{@var{N} > 0}).

@item @var{S}(k)
mean service time on server @math{k}
(@code{@var{S}(k)>0}).

@item @var{V}(k)
average number of visits to service center
@math{k} (@code{@var{V}(k) @geq{} 0}).

@item @var{m}(k)
number of servers at center @math{k}
(if @var{m} is a scalar, all centers have that number of servers). If
@code{@var{m}(k) < 1}, center @math{k} is a delay center (IS); if
@code{@var{m}(k) == 1}, center @math{k} is a regular queueing
center (FCFS, LCFS-PR or PS) with one server (default). This function
does not support multiple server nodes (@code{@var{m}(k) > 1}).

@item @var{Z}
External delay for customers (@code{@var{Z} @geq{} 0}). Default is 0.

@item @var{tol}
Stopping tolerance. The algorithm stops when the maximum relative
difference between the new and old value of the queue lengths
@var{Q} becomes less than the tolerance. Default is @math{10^{-5}}.

@item @var{iter_max}
Maximum number of iterations (@code{@var{iter_max}>0}.
The function aborts if convergenge is not reached within the maximum
number of iterations. Default is 100.

@end table

@strong{OUTPUTS}

@table @code

@item @var{U}(k)
If @math{k} is a FCFS, LCFS-PR or PS node (@code{@var{m}(k) == 1}),
then @code{@var{U}(k)} is the utilization of center @math{k}. If
@math{k} is an IS node (@code{@var{m}(k) < 1}), then
@code{@var{U}(k)} is the @emph{traffic intensity} defined as
@code{@var{X}(k)*@var{S}(k)}.

@item @var{R}(k)
response time at center @math{k}.
The system response time @var{Rsys}
can be computed as @code{@var{Rsys} = @var{N}/@var{Xsys} - Z}

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

@item @var{X}(k)
center @math{k} throughput. The system throughput @var{Xsys} can be
computed as @code{@var{Xsys} = @var{X}(1) / @var{V}(1)}

@end table

@strong{REFERENCES}

This implementation is based on Edward D. Lazowska, John Zahorjan,
G. Scott Graham, and Kenneth C. Sevcik, @cite{Quantitative System
Performance: Computer System Analysis Using Queueing Network Models},
Prentice Hall,
1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In
particular, see section 6.4.2.2 ("Approximate Solution Techniques").

@xseealso{qncsmva,qncsmvald}

@end deftypefn


@c
@c Convolution
@c

According to the BCMP theorem, the state probability of a closed
single class queueing network with @math{K} nodes and @math{N} requests
can be expressed as:

@iftex
@tex
$$ \pi(n_1, \ldots, n_K) = {1 \over G(N)} \prod_{k=1}^K F_k(n_k) $$
@end tex
@end iftex
@ifnottex
@example
@group
n = [n1, @dots{} nK]; @r{population vector}
p = 1/G(N+1) \prod F(k,k);
@end group
@end example
@end ifnottex

Here @math{\pi(n_1, @dots{}, n_K)} is the joint probability of
having @math{n_k} requests at node @math{k}, for all @math{k=1,
@dots{}, K}; we have that @math{\sum_{k=1}^K n_k = N}

The @emph{convolution algorithms} computes the normalization constants
@math{{\bf G} = \left[G(0), @dots{}, G(N)\right]} for single-class,
closed networks with @math{N} requests.  The normalization constants
are returned as vector @code{@var{G}=[@var{G}(1), @dots{}
@var{G}(N+1)]} where @code{@var{G}(i+1)} is the value of @math{G(i)}
(remember that Octave uses 1-base vectors). The normalization constant
can be used to compute all performance measures of interest
(utilization, average response time and so on).

@command{queueing} implements the convolution algorithm, in the function
@command{qncsconv} and @command{qncsconvld}. The first one
supports single-station nodes, multiple-station nodes and IS nodes.
The second one supports networks with general load-dependent service
centers.


@anchor{doc-qncsconv}


@deftypefn {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}, @var{G}] =} qncsconv (@var{N}, @var{S}, @var{V})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}, @var{G}] =} qncsconv (@var{N}, @var{S}, @var{V}, @var{m})

@cindex closed network, single class
@cindex normalization constant
@cindex convolution algorithm

Analyze product-form, single class closed networks with @math{K} service centers using the convolution algorithm.

Load-independent service centers, multiple servers (@math{M/M/m}
queues) and IS nodes are supported. For general load-dependent
service centers, use @code{qncsconvld} instead.

@strong{INPUTS}

@table @code

@item @var{N}
Number of requests in the system (@code{@var{N}>0}).

@item @var{S}(k)
average service time on center @math{k} (@code{@var{S}(k) @geq{} 0}).

@item @var{V}(k)
visit count of service center @math{k} (@code{@var{V}(k) @geq{} 0}).

@item @var{m}(k)
number of servers at center @math{k}. If @code{@var{m}(k) < 1},
center @math{k} is a delay center (IS); if @code{@var{m}(k) @geq{}
1}, center @math{k} it is a regular @math{M/M/m} queueing center
with @code{@var{m}(k)} identical servers. Default is
@code{@var{m}(k) = 1} for all @math{k}.

@end table

@strong{OUTPUT}

@table @code

@item @var{U}(k)
center @math{k} utilization.
For IS nodes, @code{@var{U}(k)} is the @emph{traffic intensity}
@code{@var{X}(k) * @var{S}(k)}.

@item @var{R}(k)
average response time of center @math{k}.

@item @var{Q}(k)
average number of customers at center @math{k}.

@item @var{X}(k)
throughput of center @math{k}.

@item @var{G}(n)
Vector of normalization constants. @code{@var{G}(n+1)} contains the value of
the normalization constant with @math{n} requests
@math{G(n)}, @math{n=0, @dots{}, N}.

@end table

@strong{NOTE}

For a network with @math{K} service centers and @math{N} requests,
this implementation of the convolution algorithm has time and space
complexity @math{O(NK)}.

@strong{REFERENCES}

@itemize
@item
Jeffrey P. Buzen, @cite{Computational Algorithms for Closed Queueing
Networks with Exponential Servers}, Communications of the ACM, volume
16, number 9, September 1973,
pp. 527--531. @uref{http://doi.acm.org/10.1145/362342.362345, 10.1145/362342.362345}
@end itemize

This implementation is based on G. Bolch, S. Greiner, H. de Meer and
K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and
Performance Evaluation with Computer Science Applications}, Wiley,
1998, pp. 313--317.

@xseealso{qncsconvld}

@end deftypefn



@noindent @strong{EXAMPLE}

The normalization constant @math{G} can be used to compute the
steady-state probabilities for a closed single class product-form
Queueing Network with @math{K} nodes and @math{N} requests. Let
@code{@var{n} = [@math{n_1, @dots{}, n_K}]} be a valid
population vector, @math{\sum_{k=1}^K n_k = N}. Then, the steady-state
probability @code{@var{p}(k)} to have @code{@var{n}(k)} requests at
service center @math{k} can be computed as:

@iftex
@tex
$$
p_k(n_k) = {(V_k S_k)^{n_k} \over G(N)} \left(G(N-n_k) - V_k S_k G(N-n_k-1)\right), \quad k=1, \ldots, K
$$
@end tex
@end iftex

@example
@verbatim
 n = [1 2 0];
 N = sum(n); # Total population size
 S = [ 1/0.8 1/0.6 1/0.4 ];
 m = [ 2 3 1 ];
 V = [ 1 .667 .2 ];
 [U R Q X G] = qncsconv( N, S, V, m );
 p = [0 0 0]; # initialize p
 # Compute the probability to have n(k) jobs at service center k
 for k=1:3
   p(k) = (V(k)*S(k))^n(k) / G(N+1) * ...
          (G(N-n(k)+1) - V(k)*S(k)*G(N-n(k)) );
   printf("Prob( n(%d) = %d )=%f\n", k, n(k), p(k) );
 endfor
@end verbatim
@print{} Prob( n(1) = 1 ) = 0.17975
@print{} Prob( n(2) = 2 ) = 0.48404
@print{} Prob( n(3) = 0 ) = 0.52779
@end example

@noindent 
(recall that @code{@var{G}(@var{N}+1)} represents @math{G(N)}, since
in Octave array indices start at one).


@c
@anchor{doc-qncsconvld}


@deftypefn {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}, @var{G}] =} qncsconvld (@var{N}, @var{S}, @var{V})

@cindex closed network
@cindex normalization constant
@cindex convolution algorithm
@cindex load-dependent service center

Convolution algorithm for product-form, single-class closed
queueing networks with @math{K} general load-dependent service
centers.

This function computes steady-state performance measures for
single-class, closed networks with load-dependent service centers
using the convolution algorithm; the normalization constants are also
computed. The normalization constants are returned as vector
@code{@var{G}=[@var{G}(1), @dots{}, @var{G}(N+1)]} where
@code{@var{G}(i+1)} is the value of @math{G(i)}.

@strong{INPUTS}

@table @code

@item @var{N}
Number of requests in the system (@code{@var{N}>0}).

@item @var{S}(k,n)
mean service time at center @math{k} where there are @math{n}
requests, @math{1 @leq{} n @leq{} N}. @code{@var{S}(k,n)} @math{= 1 / \mu_{k,n}}, where @math{\mu_{k,n}} is the service rate of center
@math{k} when there are @math{n} requests.

@item @var{V}(k)
visit count of service center @math{k}
(@code{@var{V}(k) @geq{} 0}). The length of @var{V} is the number of
servers @math{K} in the network.

@end table

@strong{OUTPUT}

@table @code

@item @var{U}(k)
center @math{k} utilization.

@item @var{R}(k)
average response time at center @math{k}.

@item @var{Q}(k)
average number of requests in center @math{k}.

@item @var{X}(k)
center @math{k} throughput.

@item @var{G}(n)
Normalization constants (vector). @code{@var{G}(n+1)}
corresponds to @math{G(n)}, as array indexes in Octave start
from 1.

@end table

@strong{REFERENCES}

@itemize
@item
Herb Schwetman, @cite{Some Computational Aspects of Queueing Network
Models}, Technical Report
@uref{http://docs.lib.purdue.edu/cstech/285/, CSD-TR-354}, Department
of Computer Sciences, Purdue University, February 1981 (revised).

@item
M. Reiser, H. Kobayashi, @cite{On The Convolution Algorithm for
Separable Queueing Networks}, In Proceedings of the 1976 ACM
SIGMETRICS Conference on Computer Performance Modeling Measurement and
Evaluation (Cambridge, Massachusetts, United States, March 29--31,
1976). SIGMETRICS '76. ACM, New York, NY,
pp. 109--117. @uref{http://doi.acm.org/10.1145/800200.806187, 10.1145/800200.806187}
@end itemize

This implementation is based on G. Bolch, S. Greiner, H. de Meer and
K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and
Performance Evaluation with Computer Science Applications}, Wiley,
1998, pp. 313--317. Function @command{qncsconvld} is slightly
different from the version described in Bolch et al. because it
supports general load-dependent centers (while the version in the book
does not). The modification is in the definition of function
@code{F()} in @command{qncsconvld} which has been made similar to
function @math{f_i} defined in Schwetman, @cite{Some Computational
Aspects of Queueing Network Models}.

@xseealso{qncsconv}

@end deftypefn



@c
@c
@c
@subsection Non Product-Form QNs
@anchor{Non Product-Form QNs}

@c
@c MVABLO algorithm for approximate analysis of closed, single class
@c QN with blocking
@c
@anchor{doc-qncsmvablo}


@deftypefn {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncsmvablo (@var{N}, @var{S}, @var{M}, @var{P} )

@cindex queueing network with blocking
@cindex blocking queueing network
@cindex closed network, finite capacity
@cindex MVABLO

Approximate MVA algorithm for closed queueing networks with blocking.

@strong{INPUTS}

@table @code

@item @var{N}
number of requests in the system. @var{N} must be strictly greater
than zero, and less than the overall network capacity: @code{0 <
@var{N} < sum(@var{M})}.

@item @var{S}(k)
average service time on server @math{k} (@code{@var{S}(k) > 0}).

@item @var{M}(k)
capacity of center @math{k}. The capacity is the maximum number of requests in a service
center, including the request in service (@code{@var{M}(k) @geq{} 1}).

@item @var{P}(i,j)
probability that a request which completes
service at server @math{i} will be transferred to server @math{j}.

@end table

@strong{OUTPUTS}

@table @code

@item @var{U}(k)
center @math{k} utilization.

@item @var{R}(k)
average response time of service center @math{k}.

@item @var{Q}(k)
average number of requests in service center @math{k} (including
the request in service).

@item @var{X}(k)
center @math{k} throughput.

@end table

@strong{REFERENCES}

@itemize
@item
Ian F. Akyildiz, @cite{Mean Value Analysis for Blocking Queueing
Networks}, IEEE Transactions on Software Engineering, vol. 14, n. 2,
april 1988, pp. 418--428.  @uref{http://dx.doi.org/10.1109/32.4663, 10.1109/32.4663}
@end itemize

@xseealso{qnopen, qnclosed}

@end deftypefn


@c
@anchor{doc-qnmarkov}


@deftypefn {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnmarkov (@var{lambda}, @var{S}, @var{C}, @var{P})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnmarkov (@var{lambda}, @var{S}, @var{C}, @var{P}, @var{m})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnmarkov (@var{N}, @var{S}, @var{C}, @var{P})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnmarkov (@var{N}, @var{S}, @var{C}, @var{P}, @var{m})

@cindex closed network, single class
@cindex open network, single class
@cindex closed network, finite capacity
@cindex blocking queueing network
@cindex RS blocking

Compute utilization, response time, average queue length and
throughput for open or closed queueing networks with finite capacity
and a single class of requests.
Blocking type is Repetitive-Service (RS). This function explicitly
generates and solve the underlying Markov chain, and thus might
require a large amount of memory.

More specifically, networks which can me analyzed by this
function have the following properties:

@itemize @bullet

@item There exists only a single class of customers.

@item The network has @math{K} service centers. Center
@math{k \in @{1, @dots{}, K@}}
has @math{m_k > 0} servers, and has a total (finite) capacity of
@math{C_k \geq m_k} which includes both buffer space and servers.
The buffer space at service center @math{k} is therefore
@math{C_k - m_k}.

@item The network can be open, with external arrival rate to
center @math{k} equal to
@math{\lambda_k}, or closed with fixed
population size @math{N}. For closed networks, the population size
@math{N} must be strictly less than the network capacity:
@math{N < \sum_{k=1}^K C_k}.

@item Average service times are load-independent.

@item @math{P_{i, j}} is the probability that requests completing
execution at center @math{i} are transferred to
center @math{j}, @math{i \neq j}. For open networks, a request may leave the system
from any node @math{i} with probability @math{1-\sum_{j=1}^K P_{i, j}}.

@item Blocking type is Repetitive-Service (RS). Service
center @math{j} is @emph{saturated} if the number of requests is equal
to its capacity @math{C_j}. Under the RS blocking discipline,
a request completing service at center @math{i} which is being
transferred to a saturated server @math{j} is put back at the end of
the queue of @math{i} and will receive service again. Center @math{i}
then processes the next request in queue. External arrivals to a
saturated servers are dropped.

@end itemize

@strong{INPUTS}

@table @code

@item @var{lambda}(k)
@itemx @var{N}
If the first argument is a vector @var{lambda}, it is considered to be
the external arrival rate @code{@var{lambda}(k) @geq{} 0} to service center
@math{k} of an open network. If the first argument is a scalar, it is
considered as the population size @var{N} of a closed network; in this case
@var{N} must be strictly
less than the network capacity: @code{@var{N} < sum(@var{C})}.

@item @var{S}(k)
average service time at service center @math{k}

@item @var{C}(k)
capacity of service center @math{k}. The capacity includes both
the buffer and server space @code{@var{m}(k)}. Thus the buffer space is
@code{@var{C}(k)-@var{m}(k)}.

@item @var{P}(i,j)
transition probability from service center
@math{i} to service center @math{j}.

@item @var{m}(k)
number of servers at service center
@math{k}. Note that @code{@var{m}(k) @geq{} @var{C}(k)} for each @var{k}.
If @var{m} is omitted, all service centers are assumed to have a
single server (@code{@var{m}(k) = 1} for all @math{k}).

@end table

@strong{OUTPUTS}

@table @code

@item @var{U}(k)
center @math{k} utilization.

@item @var{R}(k)
response time on service center @math{k}.

@item @var{Q}(k)
average number of customers in the
service center @math{k}, @emph{including} the request in service.

@item @var{X}(k)
throughput of service center @math{k}.

@end table

@strong{NOTES}

The space complexity of this implementation is @math{O(\prod_{k=1}^K (C_k + 1)^2)}. The time complexity is dominated by
the time needed to solve a linear system with @math{\prod_{k=1}^K (C_k + 1)} unknowns.

@end deftypefn


@c
@c
@c
@node Multiple Class Models
@section Multiple Class Models

@cindex multiple class queueing network
@cindex queueing network, multiple class

In multiple class queueing models, we assume that there exist @math{C}
different classes of requests. Each request from class @math{c} spends
on average time @math{S_{c, k}} in service at center @math{k}. For
open models, we denote with @math{{\bf \lambda} = \lambda_{c, k}} the
arrival rates, where @math{\lambda_{c, k}} is the external arrival
rate of class @math{c} requests at center @math{k}. For closed models,
we denote with @math{{\bf N} = \left[N_1, @dots{}, N_C\right]} the population
vector, where @math{N_c} is the number of class @math{c} requests in
the system.

The transition probability matrix for multiple class networks is a
@math{C \times K \times C \times K} matrix @math{{\bf P} = [P_{r, i,
s, j}]} where @math{P_{r, i, s, j}} is the probability that a class
@math{r} request which completes service at center @math{i} will join
server @math{j} as a class @math{s} request.

Model input and outputs can be adjusted by adding additional indexes
for the customer classes.

@noindent @strong{Model Inputs}

@cindex external arrival rate
@cindex service time
@cindex routing probability matrix
@cindex average number of visits

@table @asis

@item @math{@lambdack}
(open networks) External arrival rate of class-@math{c} requests to service center @math{k}

@item @math{@lambda}
(open networks) Overall external arrival rate to the whole system: @math{\lambda = \sum_{c=1}^C \sum_{k=1}^K \lambda_{c, k}}

@item @math{N_c}
(closed networks) Number of class @math{c} requests in the system.

@item @math{S_{c, k}}
Average service time. @math{S_{c, k}} is the average service time on
service center @math{k} for class @math{c} requests.

@item @math{P_{r, i, s, j}}
Routing probability matrix. @math{{\bf P} = [P_{r, i, s, j}]} is a @math{C
\times K \times C \times K} matrix such that @math{P_{r, i, s, j}} is
the probability that a class @math{r} request which completes service
at server @math{i} will move to server @math{j} as a class @math{s}
request.

@item @math{V_{c, k}}
Mean number of visits of class @math{c} requests to center @math{k}.

@end table

@noindent @strong{Model Outputs}

@cindex utilization
@cindex response time
@cindex average number of customers
@cindex throughput
@cindex system response time
@cindex system throughput

@table @asis

@item @math{U_{c, k}}
Utilization of service center @math{k} by class @math{c} requests. The
utilization is defined as the fraction of time in which the resource
is busy (i.e., the server is processing requests).  If center @math{k}
is a single-server or multiserver node, then 
@math{0 @leq{} U_{c, k} @leq{} 1}. 
If center @math{k} is an infinite server node (delay
center), then @math{U_{c, k}} denotes the @emph{traffic intensity} and
is defined as @math{U_{c, k} = X_{c, k} S_{c, k}}; in this case the
utilization may be greater than one.

@item @math{R_{c, k}}
Average response time experienced by class @math{c} requests on service
center @math{k}. The average response time is defined as the average
time between the arrival of a customer in the queue, and the completion
of service.

@item @math{Q_{c, k}}
Average number of class @math{c} requests on service center
@math{k}. This includes both the requests in the queue, and the request
being served.

@item @math{X_{c, k}}
Throughput of service center @math{k} for class @math{c} requests.  The
throughput is defined as the rate of completion of class @math{c}
requests.

@end table

@noindent It is possible to define aggregate performance measures as follows:

@table @math

@item U_k
Utilization of service center @math{k}:
@iftex
@tex
$U_k = \sum_{c=1}^C U_{c, k}$
@end tex
@end iftex
@ifnottex
@code{Uk = sum(U,k);}
@end ifnottex

@item R_c
System response time for class @math{c} requests:
@iftex
@tex
$R_c = \sum_{k=1}^K R_{c, k} V_{c, k}$
@end tex
@end iftex
@ifnottex
@code{Rc = sum( V.*R, 1 );}
@end ifnottex

@item Q_c
Average number of class @math{c} requests in the system:
@iftex
@tex
$Q_c = \sum_{k=1}^K Q_{c, k}$
@end tex
@end iftex
@ifnottex
@code{Qc = sum( Q, 2 );}
@end ifnottex

@item X_c
Class @math{c} throughput:
@iftex
@tex
$X_c = X_{c, k} / V_{c, k}$ for any @math{k} for which @math{V_{c,k} \neq 0}
@end tex
@end iftex
@ifnottex
@code{X(c) = X(c,k) ./ V(c,k);} for any @math{k} for which @code{V(c,k) != 0}
@end ifnottex

@end table

For closed networks, we can define the visit ratios @math{V_{s, j}}
for class @math{s} customers at service center @math{j} as follows:

@iftex
@tex
$$\left\{\eqalign{ V_{s, j} & = \sum_{r=1}^C \sum_{i=1}^K V_{r, i} P_{r, i, s, j}, \quad s=1, \ldots, C, j=1, \ldots, K \cr
                   V_{s, r_s} & = 1, \quad s=1, \ldots, C}\right. $$
@end tex
@end iftex
@ifnottex
@group
V_sj = sum_r sum_i V_ri P_risj    s=1,...,C, j=1,...,K
V_s r_s = 1                       s=1,...,C
@end group
@end ifnottex

@noindent where @math{r_s} is the class @math{s}
reference station. Similarly to single class models, the traffic
equation for closed multiclass networks can be solved up to
multiplicative constants unless we choose one reference station for
each closed class and set its visit ratio to 1.

For open networks the traffic equations are as follows:

@iftex
@tex
$$V_{s, j} = P_{0, s, j} + \sum_{r=1}^C \sum_{i=1}^K V_{r, i} P_{r, i, s, j} \quad s=1, \ldots, C, j=1, \ldots, K$$
@end tex
@end iftex
@ifnottex
@group
V_sj = P_0sj + sum_r sum_i V_ri P_risj  s=1,...,C, j=1,...,K
@end group
@end ifnottex

@noindent where @math{P_{0, s, j}} is the probability that an external
arrival goes to service center @math{j} as a class-@math{s} request.
If @math{\lambda_{s, j}} is the external arrival rate of class
@math{s} requests to service center @math{j}, and @math{\lambda =
\sum_s \sum_j \lambda_{s, j}} is the overall external arrival rate,
then @math{P_{0, s, j} = \lambda_{s, j} / \lambda}.

@anchor{doc-qncmvisits}


@deftypefn {Function File} {[@var{V} @var{ch}] =} qncmvisits (@var{P})
@deftypefnx {Function File} {[@var{V} @var{ch}] =} qncmvisits (@var{P}, @var{r})

Compute the average number of visits for the nodes of a closed multiclass network with @math{K} service centers and @math{C} customer classes.

@strong{INPUTS}

@table @code

@item @var{P}(r,i,s,j)
probability that a
class @math{r} request which completed service at center @math{i} is
routed to center @math{j} as a class @math{s} request. Class switching
is allowed.

@item @var{r}(c)
index of class @math{c} reference station,
@math{r(c) \in @{1, @dots{}, K@}}, @math{1 @leq{} c @leq{} C}.
The class @math{c} visit count to server @code{@var{r}(c)}
(@code{@var{V}(c,r(c))}) is conventionally set to 1. The reference
station serves two purposes: (i) its throughput is assumed to be the
system throughput, and (ii) a job returning to the reference station
is assumed to have completed one cycle. Default is to consider
station 1 as the reference station for all classes.

@end table

@strong{OUTPUTS}

@table @code

@item @var{V}(c,i)
number of visits of class @math{c} requests at center @math{i}.

@item @var{ch}(c)
chain number that class @math{c} belongs
to. Different classes can belong to the same chain. Chains are
numbered sequentially starting from 1 (@math{1, 2, @dots{}}). The
total number of chains is @code{max(@var{ch})}.

@end table

@end deftypefn


@anchor{doc-qnomvisits}


@deftypefn {Function File} {@var{V} =} qnomvisits (@var{P}, @var{lambda})

Compute the visit ratios to the service centers of an open multiclass network with @math{K} service centers and @math{C} customer classes.

@strong{INPUTS}

@table @code

@item @var{P}(r,i,s,j)
probability that a class @math{r} request which completed service at center @math{i} is
routed to center @math{j} as a class @math{s} request. Class switching
is supported.

@item @var{lambda}(r,i)
external arrival rate of class @math{r} requests to center @math{i}.

@end table

@strong{OUTPUTS}

@table @code

@item @var{V}(r,i)
visit ratio of class @math{r} requests at center @math{i}.

@end table

@end deftypefn


@c
@c Open Networks
@c
@subsection Open Networks

@c
@c Open network with multiple classes
@c
@anchor{doc-qnom}


@deftypefn {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnom (@var{lambda}, @var{S}, @var{V})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnom (@var{lambda}, @var{S}, @var{V}, @var{m})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnom (@var{lambda}, @var{S}, @var{P})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnom (@var{lambda}, @var{S}, @var{P}, @var{m})

@cindex open network, multiple classes
@cindex multiclass network, open

Exact analysis of open, multiple-class BCMP networks. The network can
be made of @emph{single-server} queueing centers (FCFS, LCFS-PR or
PS) or delay centers (IS). This function assumes a network with
@math{K} service centers and @math{C} customer classes.

@strong{INPUTS}

@table @code

@item @var{lambda}(c)
If this function is invoked as @code{qnom(lambda, S, V, @dots{})},
then @code{@var{lambda}(c)} is the external arrival rate of class
@math{c} customers (@code{@var{lambda}(c) @geq{} 0}). If this
function is invoked as @code{qnom(lambda, S, P, @dots{})}, then
@code{@var{lambda}(c,k)} is the external arrival rate of class
@math{c} customers at center @math{k} (@code{@var{lambda}(c,k)
@geq{} 0}).

@item @var{S}(c,k)
mean service time of class @math{c} customers on the service center
@math{k} (@code{@var{S}(c,k)>0}). For FCFS nodes, mean service
times must be class-independent.

@item @var{V}(c,k)
visit ratio of class @math{c} customers to service center @math{k}
(@code{@var{V}(c,k) @geq{} 0 }). @strong{If you pass this argument,
class switching is not allowed}

@item @var{P}(r,i,s,j)
probability that a class @math{r} job completing service at center
@math{i} is routed to center @math{j} as a class @math{s} job.
@strong{If you pass argument @var{P}, class switching is allowed};
however, all servers must be fixed-rate or infinite-server nodes
(@code{@var{m}(k) @leq{} 1} for all @math{k}).

@item @var{m}(k)
number of servers at center @math{k}. If @code{@var{m}(k) < 1},
enter @math{k} is a delay center (IS); otherwise it is a regular
queueing center with @code{@var{m}(k)} servers. Default is
@code{@var{m}(k) = 1} for all @math{k}.

@end table

@strong{OUTPUTS}

@table @code

@item @var{U}(c,k)
If @math{k} is a queueing center, then @code{@var{U}(c,k)} is the
class @math{c} utilization of center @math{k}. If @math{k} is an IS
node, then @code{@var{U}(c,k)} is the class @math{c} @emph{traffic
intensity} defined as @code{@var{X}(c,k)*@var{S}(c,k)}.

@item @var{R}(c,k)
class @math{c} response time at center @math{k}. The system
response time for class @math{c} requests can be computed as
@code{dot(@var{R}, @var{V}, 2)}.

@item @var{Q}(c,k)
average number of class @math{c} requests at center @math{k}. The
average number of class @math{c} requests in the system @var{Qc}
can be computed as @code{Qc = sum(@var{Q}, 2)}

@item @var{X}(c,k)
class @math{c} throughput at center @math{k}.

@end table

@strong{NOTES}

If the function call specifies the visit ratios @var{V},
class switching is @strong{not} allowed. If the function call
specifies the routing probability matrix @var{P}, then class
switching @strong{is} allowed; however, all nodes are
restricted to be fixed rate servers or delay centers:
multiple-server and general load-dependent centers are not
supported. Note that the meaning of parameter @var{lambda} is
different from one case to the other (see below).

@strong{REFERENCES}

@itemize
@item
Edward D. Lazowska, John Zahorjan, G. Scott Graham, and Kenneth C.
Sevcik, @cite{Quantitative System Performance: Computer System
Analysis Using Queueing Network Models}, Prentice Hall,
1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In
particular, see section 7.4.1 ("Open Model Solution Techniques").
@end itemize

@xseealso{qnopen,qnos,qnomvisits}

@end deftypefn


@c
@c Closed Networks
@c
@subsection Closed Networks

@c
@anchor{doc-qncmpopmix}


@deftypefn {Function File} {pop_mix =} qncmpopmix (@var{k}, @var{N})

@cindex population mix
@cindex closed network, multiple classes

Return the set of population mixes for a closed multiclass queueing
network with exactly @var{k} customers. Specifically, given a
closed multiclass QN with @math{C} customer classes, where there
are @code{@var{N}(c)} class @math{c} requests, @math{c = 1, @dots{}, C}
a @math{k}-mix @math{M} is a vector of length @math{C} with the following
properties:

@itemize
@item @math{0 @leq{} M_c @leq{} @var{N}(c)} for all @math{c = 1, @dots{}, C};
@item @math{\sum_{c=1}^C M_c = k}
@end itemize

In other words, a @math{k}-mix is an allocation of @math{k}
requests to @math{C} classes such that the number of requests
assigned to class @math{c} does not exceed the maximum value
@code{@var{N}(c)}.

@var{pop_mix} is a matrix with @math{C} columns, such
that each row represents a valid mix.

@strong{INPUTS}

@table @code

@item @var{k}
Size of the requested mix (scalar, @code{@var{k} @geq{} 0}).

@item @var{N}(c)
number of class @math{c} requests (@code{@var{k} @leq{} sum(@var{N})}).

@end table

@strong{OUTPUTS}

@table @code

@item @var{pop_mix}(i,c)
number of class @math{c} requests in the @math{i}-th population
mix. The number of mixes is @code{rows(@var{pop_mix})}.

@end table

If you are interested in the number of @math{k}-mixes only, you can
use the funcion @code{qnmvapop}.

@strong{REFERENCES}

@itemize
@item
Herb Schwetman, @cite{Implementing the Mean Value Algorithm for the
Solution of Queueing Network Models}, Technical Report
@uref{http://docs.lib.purdue.edu/cstech/286/, 80-355}, Department of Computer
Sciences, Purdue University, revised February 15, 1982.
@end itemize

The slightly different problem of enumerating all tuples @math{k_1,
@dots{}, k_N} such that @math{\sum_i k_i = k} and @math{k_i
@geq{} 0}, for a given @math{k @geq{} 0} has been described in
S. Santini, @cite{Computing the Indices for a Complex Summation},
unpublished report, available at
@url{http://arantxa.ii.uam.es/~ssantini/writing/notes/s668_summation.pdf}

@xseealso{qncmnpop}

@end deftypefn


@noindent @strong{EXAMPLE}

Let us consider a multiclass network with @math{C=2} customer classes;
the maximum number of class 1 requests is 2, and the maximum number of
class 2 requests is 3. How is it possible to allocate 3 requests to
the two classes so that the maximum number of requests per class is
not exceeded?

@example
@verbatim
 N = [2 3];
 mix = qncmpopmix(3, N)
@end verbatim
@print{} mix = [ [2 1] [1 2] [0 3] ]
@end example


@c
@anchor{doc-qncmnpop}


@deftypefn {Function File} {@var{H} =} qncmnpop (@var{N})

@cindex population mix
@cindex closed network, multiple classes

Given a network with @math{C} customer classes, this function
computes the number of @math{k}-mixes @code{@var{H}(r,k)} that can
be constructed by the multiclass MVA algorithm by allocating
@math{k} customers to the first @math{r} classes.
@xref{doc-qncmpopmix} for the definition of @math{k}-mix.

@strong{INPUTS}

@table @code

@item @var{N}(c)
number of class-@math{c} requests in the system. The total number
of requests in the network is @code{sum(@var{N})}.

@end table

@strong{OUTPUTS}

@table @code

@item @var{H}(r,k)
is the number of @math{k} mixes that can be constructed allocating
@math{k} customers to the first @math{r} classes.

@end table

@strong{REFERENCES}

@itemize
@item Zahorjan, J. and Wong, E. @cite{The solution of separable queueing
network models using mean value analysis}. SIGMETRICS
Perform. Eval. Rev. 10, 3 (Sep. 1981), 80-85. DOI
@uref{http://doi.acm.org/10.1145/1010629.805477, 10.1145/1010629.805477}
@end itemize

@xseealso{qncmmva,qncmpopmix}

@end deftypefn



@c
@c MVA for multiple class, closed networks
@c
@anchor{doc-qncmmva}


@deftypefn {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncmmva (@var{N}, @var{S} )
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncmmva (@var{N}, @var{S}, @var{V})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncmmva (@var{N}, @var{S}, @var{V}, @var{m})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncmmva (@var{N}, @var{S}, @var{V}, @var{m}, @var{Z})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncmmva (@var{N}, @var{S}, @var{P})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncmmva (@var{N}, @var{S}, @var{P}, @var{r})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncmmva (@var{N}, @var{S}, @var{P}, @var{r}, @var{m})

@cindex Mean Value Analysys (MVA)
@cindex closed network, multiple classes
@cindex multiclass network, closed

Compute steady-state performance measures for closed, multiclass
queueing networks using the Mean Value Analysys (MVA) algorithm.

Queueing policies at service centers can be any of the following:

@table @strong

@item FCFS
(First-Come-First-Served) customers are served in order of arrival;
multiple servers are allowed. For this kind of queueing discipline,
average service times must be class-independent.

@item PS
(Processor Sharing) customers are served in parallel by a single
server, each customer receiving an equal share of the service rate.

@item LCFS-PR
(Last-Come-First-Served, Preemptive Resume) customers are served in
reverse order of arrival by a single server and the last arrival
preempts the customer in service who will later resume service at the
point of interruption.

@item IS
(Infinite Server) customers are delayed independently of other
customers at the service center (there is effectively an infinite
number of servers).

@end table

@strong{INPUTS}

@table @code

@item @var{N}(c)
number of class @math{c} requests; @code{@var{N}(c) @geq{} 0}. If
class @math{c} has no requests (@code{@var{N}(c) == 0}), then for
all @var{k}, this function returns
@code{@var{U}(c,k) = @var{R}(c,k) = @var{Q}(c,k) = @var{X}(c,k) = 0}

@item @var{S}(c,k)
mean service time for class @math{c} requests at center @math{k}
(@code{@var{S}(c,k) @geq{} 0}). If the service time at center
@math{k} is class-dependent, then center @math{k} is assumed
to be of type @math{-/G/1}--PS (Processor Sharing). If center
@math{k} is a FCFS node (@code{@var{m}(k)>1}), then the service
times @strong{must} be class-independent, i.e., all classes
@strong{must} have the same service time.

@item @var{V}(c,k)
average number of visits of class @math{c} requests at
center @math{k}; @code{@var{V}(c,k) @geq{} 0}, default is 1.
@strong{If you pass this argument, class switching is not allowed}

@item @var{P}(r,i,s,j)
probability that a class @math{r} request completing service at center
@math{i} is routed to center @math{j} as a class @math{s} request; the
reference stations for each class are specified with the paramter
@var{r}. @strong{If you pass argument @var{P}, class switching is
allowed}; however, you can not specify any external delay (i.e.,
@var{Z} must be zero) and all servers must be fixed-rate or
infinite-server nodes (@code{@var{m}(k) @leq{} 1} for all
@math{k}).

@item @var{r}(c)
reference station for class @math{c}. If omitted, station 1 is the
reference station for all classes. See @command{qncmvisits}.

@item @var{m}(k)
If @code{@var{m}(k)<1}, then center @math{k} is assumed to be a delay
center (IS node @math{-/G/\infty}). If @code{@var{m}(k)==1}, then
service center @math{k} is a regular queueing center
(@math{M/M/1}--FCFS, @math{-/G/1}--LCFS-PR or @math{-/G/1}--PS).
Finally, if @code{@var{m}(k)>1}, center @math{k} is a
@math{M/M/m}--FCFS center with @code{@var{m}(k)} identical servers.
Default is @code{@var{m}(k)=1} for each @math{k}.

@item @var{Z}(c)
class @math{c} external delay (think time); @code{@var{Z}(c) @geq{}
0}. Default is 0. This parameter can not be used if you pass a
routing matrix as the second parameter of @code{qncmmva}.

@end table

@strong{OUTPUTS}

@table @code

@item @var{U}(c,k)
If @math{k} is a FCFS, LCFS-PR or PS node (@code{@var{m}(k) @geq{}
1}), then @code{@var{U}(c,k)} is the class @math{c} utilization at
center @math{k}, @math{0 @leq{} U(c,k) @leq{} 1}. If @math{k} is an
IS node, then @code{@var{U}(c,k)} is the class @math{c} @emph{traffic
intensity} at center @math{k}, defined as @code{@var{U}(c,k) =
@var{X}(c,k)*@var{S}(c,k)}. In this case the value of
@code{@var{U}(c,k)} may be greater than one.

@item @var{R}(c,k)
class @math{c} response time at center @math{k}. The class @math{c}
@emph{residence time} at center @math{k} is @code{@var{R}(c,k) *
@var{C}(c,k)}. The total class @math{c} system response time is
@code{dot(@var{R}, @var{V}, 2)}.

@item @var{Q}(c,k)
average number of class @math{c} requests at center @math{k}. The
total number of requests at center @math{k} is
@code{sum(@var{Q}(:,k))}. The total number of class @math{c}
requests in the system is @code{sum(@var{Q}(c,:))}.

@item @var{X}(c,k)
class @math{c} throughput at center @math{k}. The class @math{c}
throughput can be computed as @code{@var{X}(c,1) / @var{V}(c,1)}.

@end table

@strong{NOTES}

If the function call specifies the visit ratios @var{V}, then class
switching is @strong{not} allowed. If the function call specifies
the routing probability matrix @var{P}, then class switching
@strong{is} allowed; however, in this case all nodes are restricted
to be fixed rate servers or delay centers: multiple-server and
general load-dependent centers are not supported.

In presence of load-dependent servers (e.g., if @code{@var{m}(i)>1}
for some @math{i}), the MVA algorithm is known to be numerically
unstable. Generally this problem shows up as negative values for the
computed response times or utilizations. This is not a problem with the
@code{queueing} package, but with the MVA algorithm;
as such, there is no known workaround at the moment (aoart from using a
different solution technique, if available). This function prints a
warning if it detects numerical problems; you can disable the warning
with the command @code{warning("off", "qn:numerical-instability")}.

Given a network with @math{K} service centers, @math{C} job classes
and population vector @math{{\bf N}=\left[N_1, @dots{}, N_C\right]}, the MVA
algorithm requires space @math{O(C \prod_i (N_i + 1))}. The time
complexity is @math{O(CK\prod_i (N_i + 1))}. This implementation is
slightly more space-efficient (see details in the code). While the
space requirement can be mitigated by using some optimizations, the
time complexity can not. If you need to analyze large closed networks
you should consider the @command{qncmmvaap} function, which implements
the approximate MVA algorithm. Note however that @command{qncmmvaap}
will only provide approximate results.

@strong{REFERENCES}

@itemize
@item
M. Reiser and S. S. Lavenberg, @cite{Mean-Value Analysis of Closed
Multichain Queuing Networks}, Journal of the ACM, vol. 27, n. 2, April
1980, pp. 313--322. @uref{http://doi.acm.org/10.1145/322186.322195, 10.1145/322186.322195}
@end itemize

This implementation is based on G. Bolch, S. Greiner, H. de Meer and
K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and
Performance Evaluation with Computer Science Applications}, Wiley,
1998 and Edward D. Lazowska, John Zahorjan, G. Scott Graham, and
Kenneth C. Sevcik, @cite{Quantitative System Performance: Computer
System Analysis Using Queueing Network Models}, Prentice Hall,
1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In
particular, see section 7.4.2.1 ("Exact Solution Techniques").

@xseealso{qnclosed, qncmmvaapprox, qncmvisits}

@end deftypefn



@c
@c Approximate MVA, with Bard-Schweitzer approximation
@c
@anchor{doc-qncmmvabs}


@deftypefn {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncmmvabs (@var{N}, @var{S}, @var{V})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncmmvabs (@var{N}, @var{S}, @var{V}, @var{m})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncmmvabs (@var{N}, @var{S}, @var{V}, @var{m}, @var{Z})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncmmvabs (@var{N}, @var{S}, @var{V}, @var{m}, @var{Z}, @var{tol})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qncmmvabs (@var{N}, @var{S}, @var{V}, @var{m}, @var{Z}, @var{tol}, @var{iter_max})

@cindex Mean Value Analysys (MVA), approximate
@cindex MVA, approximate
@cindex closed network, multiple classes
@cindex multiclass network, closed

Approximate Mean Value Analysis (MVA) for closed, multiclass
queueing networks with @math{K} service centers and @math{C}
customer classes.

This implementation uses Bard and Schweitzer approximation. It is
based on the assumption that the queue length at service center
@math{k} with population set @math{{\bf N}-{\bf 1}_c} is
approximated with

@tex
$$Q_k({\bf N}-{\bf 1}_c) \approx {n-1 \over n} Q_k({\bf N})$$
@end tex
@ifnottex
@example
@group
Q_k(N-1c) ~ (n-1)/n Q_k(N)
@end group
@end example
@end ifnottex

where @math{\bf N} is a valid population mix, @math{{\bf N}-{\bf 1}_c}
is the population mix @math{\bf N} with one class @math{c} customer
removed, and @math{n = \sum_c N_c} is the total number of requests.

This implementation works for networks with infinite server (IS)
and single-server nodes only.

@strong{INPUTS}

@table @code

@item @var{N}(c)
number of class @math{c} requests in the system (@code{@var{N}(c) @geq{} 0}).

@item @var{S}(c,k)
mean service time for class @math{c} customers at center @math{k}
(@code{@var{S}(c,k) @geq{} 0}).

@item @var{V}(c,k)
average number of visits of class @math{c} requests to center
@math{k} (@code{@var{V}(c,k) @geq{} 0}).

@item @var{m}(k)
number of servers at center @math{k}. If @code{@var{m}(k) < 1},
then the service center @math{k} is assumed to be a delay center
(IS). If @code{@var{m}(k) == 1}, service center @math{k} is a
regular queueing center (FCFS, LCFS-PR or PS) with a single server
node. If omitted, each service center has a single server. Note
that multiple server nodes are not supported.

@item @var{Z}(c)
class @math{c} external delay (@code{@var{Z} @geq{} 0}). Default is 0.

@item @var{tol}
Stopping tolerance (@code{@var{tol}>0}). The algorithm stops if
the queue length computed on two subsequent iterations are less than
@var{tol}. Default is @math{10^{-5}}.

@item @var{iter_max}
Maximum number of iterations (@code{@var{iter_max}>0}.
The function aborts if convergenge is not reached within the maximum
number of iterations. Default is 100.

@end table

@strong{OUTPUTS}

@table @code

@item @var{U}(c,k)
If @math{k} is a FCFS, LCFS-PR or PS node, then @code{@var{U}(c,k)}
is the utilization of class @math{c} requests on service center
@math{k}. If @math{k} is an IS node, then @code{@var{U}(c,k)} is the
class @math{c} @emph{traffic intensity} at device @math{k},
defined as @code{@var{U}(c,k) = @var{X}(c)*@var{S}(c,k)}

@item @var{R}(c,k)
response time of class @math{c} requests at service center @math{k}.

@item @var{Q}(c,k)
average number of class @math{c} requests at service center @math{k}.

@item @var{X}(c,k)
class @math{c} throughput at service center @math{k}.

@end table

@strong{REFERENCES}

@itemize
@item
Y. Bard, @cite{Some Extensions to Multiclass Queueing Network Analysis},
proc. 4th Int. Symp. on Modelling and Performance Evaluation of
Computer Systems, Feb 1979, pp. 51--62.

@item
P. Schweitzer, @cite{Approximate Analysis of Multiclass Closed
Networks of Queues}, Proc. Int. Conf. on Stochastic Control and
Optimization, jun 1979, pp. 25--29.
@end itemize

This implementation is based on Edward D. Lazowska, John Zahorjan, G.
Scott Graham, and Kenneth C. Sevcik, @cite{Quantitative System
Performance: Computer System Analysis Using Queueing Network Models},
Prentice Hall,
1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}.  In
particular, see section 7.4.2.2 ("Approximate Solution
Techniques"). This implementation is slightly different from the one
described above, as it computes the average response times @math{R}
instead of the residence times.

@xseealso{qncmmva}

@end deftypefn


@c
@c Mixed networks
@c
@subsection Mixed Networks

@c
@c MVA for mixed networks
@c
@anchor{doc-qnmix}


@deftypefn {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnmix (@var{lambda}, @var{N}, @var{S}, @var{V}, @var{m})

@cindex Mean Value Analysys (MVA)
@cindex mixed network

Mean Value Analysis for mixed queueing networks. The network
consists of @math{K} service centers (single-server or delay
centers) and @math{C} independent customer chains. Both open and
closed chains are possible. @var{lambda} is the vector of per-chain
arrival rates (open classes); @var{N} is the vector of populations
for closed chains.

Class switching is @strong{not} allowed. Each customer class
@emph{must} correspond to an independent chain.

If the network is made of open or closed classes only, then this
function calls @code{qnom} or @code{qncmmva} respectively, and
prints a warning message.

@strong{INPUTS}

@table @code

@item @var{lambda}(c)
@itemx @var{N}(c)
For each customer chain @math{c}:

@itemize

@item if @math{c} is a closed chain, then @code{@var{N}(c)>0} is the
number of class @math{c} requests and @code{@var{lambda}(c)} must be
zero;

@item If @math{c} is an open chain,
@code{@var{lambda}(c)>0} is the arrival rate of class @math{c}
requests and @code{@var{N}(c)} must be zero;

@end itemize

@noindent In other words, for each class @math{c} the following must hold:

@example
(@var{lambda}(c)>0 && @var{N}(c)==0) || (@var{lambda}(c)==0 && @var{N}(c)>0)
@end example

@item @var{S}(c,k)
mean class @math{c} service time at center @math{k},
@code{@var{S}(c,k) @geq{} 0}. For FCFS nodes, service times must be
class-independent.

@item @var{V}(c,k)
average number of visits of class @math{c} customers to center
@math{k} (@code{@var{V}(c,k) @geq{} 0}).

@item @var{m}(k)
number of servers at center @math{k}. Only single-server
(@code{@var{m}(k)==1}) or IS (Infinite Server) nodes
(@code{@var{m}(k)<1}) are supported. If omitted, each center is
assumed to be of type @math{M/M/1}-FCFS. Queueing discipline for
single-server nodes can be FCFS, PS or LCFS-PR.

@end table

@strong{OUTPUTS}

@table @code

@item @var{U}(c,k)
class @math{c} utilization at center @math{k}.

@item @var{R}(c,k)
class @math{c} response time at center @math{k}.

@item @var{Q}(c,k)
average number of class @math{c} requests at center @math{k}.

@item @var{X}(c,k)
class @math{c} throughput at center @math{k}.

@end table

@strong{REFERENCES}

@itemize
@item
Edward D. Lazowska, John Zahorjan, G. Scott Graham, and Kenneth C.
Sevcik, @cite{Quantitative System Performance: Computer System
Analysis Using Queueing Network Models}, Prentice Hall,
1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In
particular, see section 7.4.3 ("Mixed Model Solution Techniques").
Note that in this function we compute the mean response time @math{R}
instead of the mean residence time as in the reference.

@item
Herb Schwetman, @cite{Implementing the Mean Value Algorithm for the
Solution of Queueing Network Models}, Technical Report
@uref{http://docs.lib.purdue.edu/cstech/286/, CSD-TR-355}, Department
of Computer Sciences, Purdue University, revised Feb 15, 1982.
@end itemize

@xseealso{qncmmva, qncm}

@end deftypefn


@c
@c
@c
@node Generic Algorithms
@section Generic Algorithms

The @code{queueing} package provides a high-level function
@command{qnsolve} for analyzing QN models. @command{qnsolve} takes as
input a high-level description of the queueing model, and delegates
the actual solution of the model to one of the lower-level
function. @command{qnsolve} supports single or multiclass models, but at
the moment only product-form networks can be analyzed. For non
product-form networks @xref{Non Product-Form QNs}.

@command{qnsolve} accepts two input parameters. The first one is the list
of nodes, encoded as an Octave @emph{cell array}. The second parameter
is the vector of visit ratios @var{V}, which can be either a vector
(for single-class models) or a two-dimensional matrix (for
multiple-class models).

Individual nodes in the network are structures build using the
@command{qnmknode} function.

@anchor{doc-qnmknode}


@deftypefn {Function File} {@var{Q} =} qnmknode (@var{"m/m/m-fcfs"}, @var{S})
@deftypefnx {Function File} {@var{Q} =} qnmknode (@var{"m/m/m-fcfs"}, @var{S}, @var{m})
@deftypefnx {Function File} {@var{Q} =} qnmknode (@var{"m/m/1-lcfs-pr"}, @var{S})
@deftypefnx {Function File} {@var{Q} =} qnmknode (@var{"-/g/1-ps"}, @var{S})
@deftypefnx {Function File} {@var{Q} =} qnmknode (@var{"-/g/1-ps"}, @var{S}, @var{s2})
@deftypefnx {Function File} {@var{Q} =} qnmknode (@var{"-/g/inf"}, @var{S})
@deftypefnx {Function File} {@var{Q} =} qnmknode (@var{"-/g/inf"}, @var{S}, @var{s2})

Creates a node; this function can be used together with
@code{qnsolve}. It is possible to create either single-class nodes
(where there is only one customer class), or multiple-class nodes
(where the service time is given per-class). Furthermore, it is
possible to specify load-dependent service times. String literals
are case-insensitive, so for example @var{"-/g/inf"}, @var{"-/G/inf"}
and @var{"-/g/INF"} are all equivalent.

@strong{INPUTS}

@table @code

@item @var{S}
Mean service time.

@itemize

@item If @math{S} is a scalar,
it is assumed to be a load-independent, class-independent service time.

@item If @math{S} is a column vector, then @code{@var{S}(c)} is assumed to
the the load-independent service time for class @math{c} customers.

@item If @math{S} is a row vector, then @code{@var{S}(n)} is assumed to be
the class-independent service time at the node, when there are @math{n}
requests.

@item Finally, if @var{S} is a two-dimensional matrix, then
@code{@var{S}(c,n)} is assumed to be the class @math{c} service time
when there are @math{n} requests at the node.

@end itemize

@item @var{m}
Number of identical servers at the node. Default is @code{@var{m}=1}.

@item @var{s2}
Squared coefficient of variation for the service time. Default is 1.0.

@end table

The returned struct @var{Q} should be considered opaque to the client.

@c The returned struct @var{Q} has the following fields:

@c @table @var

@c @item Q.node
@c (String) type of the node; valid values are @code{"m/m/m-fcfs"},
@c @code{"-/g/1-lcfs-pr"}, @code{"-/g/1-ps"} (Processor-Sharing)
@c and @code{"-/g/inf"} (Infinite Server, or delay center).

@c @item Q.S
@c Average service time. If @code{@var{Q}.S} is a vector, then
@c @code{@var{Q}.S(i)} is the average service time at that node
@c if there are @math{i} requests.

@c @item Q.m
@c Number of identical servers at a @code{"m/m/m-fcfs"}. Default is 1.

@c @item Q.c
@c Number of customer classes. Default is 1.

@c @end table

@xseealso{qnsolve}

@end deftypefn


After the network has been defined, it is possible to solve it using
@command{qnsolve}.

@anchor{doc-qnsolve}


@deftypefn {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnsolve (@var{"closed"}, @var{N}, @var{QQ}, @var{V})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnsolve (@var{"closed"}, @var{N}, @var{QQ}, @var{V}, @var{Z})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnsolve (@var{"open"}, @var{lambda}, @var{QQ}, @var{V})
@deftypefnx {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnsolve (@var{"mixed"}, @var{lambda}, @var{N}, @var{QQ}, @var{V})

High-level function for analyzing QN models.

@itemize

@item For @strong{closed} networks, the following server types are
supported: @math{M/M/m}--FCFS, @math{-/G/\infty}, @math{-/G/1}--LCFS-PR,
@math{-/G/1}--PS and load-dependent variants.

@item For @strong{open} networks, the following server types are supported:
@math{M/M/m}--FCFS, @math{-/G/\infty} and @math{-/G/1}--PS. General
load-dependent nodes are @emph{not} supported. Multiclass open networks
do not support multiple server @math{M/M/m} nodes, but only
single server @math{M/M/1}--FCFS.

@item For @strong{mixed} networks, the following server types are supported:
@math{M/M/1}--FCFS, @math{-/G/\infty} and @math{-/G/1}--PS. General
load-dependent nodes are @emph{not} supported.

@end itemize

@strong{INPUTS}

@table @code

@item @var{N}
@itemx @var{N}(c)
Number of requests in the system for closed networks. For
single-class networks, @var{N} must be a scalar. For multiclass
networks, @code{@var{N}(c)} is the population size of closed class
@math{c}.

@item @var{lambda}
@itemx @var{lambda}(c)
External arrival rate (scalar) for open networks. For single-class
networks, @var{lambda} must be a scalar. For multiclass networks,
@code{@var{lambda}(c)} is the class @math{c} overall arrival rate.

@item @var{QQ}@{i@}
List of queues in the network. This must be a cell array
with @math{N} elements, such that @code{@var{QQ}@{i@}} is
a struct produced by the @code{qnmknode} function.

@item @var{Z}
External delay ("think time") for closed networks. Default 0.

@end table

@strong{OUTPUTS}

@table @code

@item @var{U}(k)
If @math{k} is a FCFS node, then @code{@var{U}(k)} is the utilization
of service center @math{k}. If @math{k} is an IS node, then
@code{@var{U}(k)} is the @emph{traffic intensity} defined as
@code{@var{X}(k)*@var{S}(k)}.

@item @var{R}(k)
average response time of service center @math{k}.

@item @var{Q}(k)
average number of customers in service center @math{k}.

@item @var{X}(k)
throughput of service center @math{k}.

@end table

Note that for multiclass networks, the computed results are per-class
utilization, response time, number of customers and throughput:
@code{@var{U}(c,k)}, @code{@var{R}(c,k)}, @code{@var{Q}(c,k)},
@code{@var{X}(c,k)}.

String literals are case-insensitive, so @var{"closed"}, @var{"Closed"}
and @var{"CLoSEd"} are all equivalent.

@end deftypefn


@noindent @strong{EXAMPLE}

Let us consider a closed, multiclass network with @math{C=2} classes
and @math{K=3} service center. Let the population be @math{M=(2, 1)}
(class 1 has 2 requests, and class 2 has 1 request). The nodes are as
follows:

@itemize

@item Node 1 is a @math{M/M/1}--FCFS node, with load-dependent service
times. Service times are class-independent, and are defined by the
matrix @code{[0.2 0.1 0.1; 0.2 0.1 0.1]}. Thus, @code{@var{S}(1,2) =
0.2} means that service time for class 1 customers where there are 2
requests in 0.2. Note that service times are class-independent;

@item Node 2 is a @math{-/G/1}--PS node, with service times
@math{S_{1, 2} = 0.4} for class 1, and @math{S_{2, 2} = 0.6} for class 2
requests;

@item Node 3 is a @math{-/G/\infty} node (delay center), with service
times @math{S_{1, 3}=1} and @math{S_{2, 3}=2} for class 1 and 2
respectively.

@end itemize

After defining the per-class visit count @var{V} such that
@code{@var{V}(c,k)} is the visit count of class @math{c} requests to
service center @math{k}.  We can define and solve the model as
follows:

@example


@verbatim
 QQ = { qnmknode( "m/m/m-fcfs", [0.2 0.1 0.1; 0.2 0.1 0.1] ), ...
        qnmknode( "-/g/1-ps", [0.4; 0.6] ), ...
        qnmknode( "-/g/inf", [1; 2] ) };
 V = [ 1 0.6 0.4; ...
       1 0.3 0.7 ];
 N = [ 2 1 ];
 [U R Q X] = qnsolve( "closed", N, QQ, V );
@end verbatim
@end example

@anchor{doc-qnclosed}


@deftypefn {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnclosed (@var{N}, @var{S}, @var{V}, @dots{})

@cindex closed network, single class
@cindex closed network, multiple classes

This function computes steady-state performance measures of closed
queueing networks using the Mean Value Analysis (MVA) algorithm. The
qneneing network is allowed to contain fixed-capacity centers, delay
centers or general load-dependent centers. Multiple request
classes are supported.

This function dispatches the computation to one of
@code{qncsemva}, @code{qncsmvald} or @code{qncmmva}.

@itemize

@item If @var{N} is a scalar, the network is assumed to have a single
class of requests; in this case, the exact MVA algorithm is used to
analyze the network. If @var{S} is a vector, then @code{@var{S}(k)}
is the average service time of center @math{k}, and this function
calls @code{qncsmva} which supports load-independent
service centers. If @var{S} is a matrix, @code{@var{S}(k,i)} is the
average service time at center @math{k} when @math{i=1, @dots{}, N}
jobs are present; in this case, the network is analyzed with the
@code{qncmmvald} function.

@item If @var{N} is a vector, the network is assumed to have multiple
classes of requests, and is analyzed using the exact multiclass
MVA algorithm as implemented in the @code{qncmmva} function.

@end itemize

@xseealso{qncsmva, qncsmvald, qncmmva}

@end deftypefn


@noindent @strong{EXAMPLE}

@example
@verbatim
 P = [0 0.3 0.7; 1 0 0; 1 0 0]; # Transition probability matrix
 S = [1 0.6 0.2];               # Average service times
 m = ones(size(S));             # All centers are single-server
 Z = 2;                         # External delay
 N = 15;                        # Maximum population to consider
 V = qncsvisits(P);             # Compute number of visits
 X_bsb_lower = X_bsb_upper = X_ab_lower = X_ab_upper = X_mva = zeros(1,N);
 for n=1:N
   [X_bsb_lower(n) X_bsb_upper(n)] = qncsbsb(n, S, V, m, Z);
   [X_ab_lower(n) X_ab_upper(n)] = qncsaba(n, S, V, m, Z);
   [U R Q X] = qnclosed( n, S, V, m, Z );
   X_mva(n) = X(1)/V(1);
 endfor
 close all;
 plot(1:N, X_ab_lower,"g;Asymptotic Bounds;", ...
      1:N, X_bsb_lower,"k;Balanced System Bounds;", ...
      1:N, X_mva,"b;MVA;", "linewidth", 2, ...
      1:N, X_bsb_upper,"k", 1:N, X_ab_upper,"g" );
 axis([1,N,0,1]); legend("location","southeast"); legend("boxoff");
 xlabel("Number of Requests n"); ylabel("System Throughput X(n)");
@end verbatim
@end example

@anchor{doc-qnopen}


@deftypefn {Function File} {[@var{U}, @var{R}, @var{Q}, @var{X}] =} qnopen (@var{lambda}, @var{S}, @var{V}, @dots{})

@cindex open network

Compute utilization, response time, average number of requests in the
system, and throughput for open queueing networks. If @var{lambda} is
a scalar, the network is considered a single-class QN and is solved
using @code{qnopensingle}. If @var{lambda} is a vector, the network
is considered as a multiclass QN and solved using @code{qnopenmulti}.

@xseealso{qnos, qnom}

@end deftypefn



@c
@c
@c
@node Bounds Analysis
@section Bounds Analysis

@c
@anchor{doc-qnosaba}


@deftypefn {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnosaba (@var{lambda}, @var{D})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnosaba (@var{lambda}, @var{S}, @var{V})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnosaba (@var{lambda}, @var{S}, @var{V}, @var{m})

@cindex bounds, asymptotic
@cindex open network

Compute Asymptotic Bounds for open, single-class networks with @math{K} service centers.

@strong{INPUTS}

@table @code

@item @var{lambda}
Arrival rate of requests (scalar, @code{@var{lambda} @geq{} 0}).

@item @var{D}(k)
service demand at center @math{k}.
(vector of length @math{K}, @code{@var{D}(k) @geq{} 0}).

@item @var{S}(k)
mean service time at center @math{k}.
(vector of length @math{K}, @code{@var{S}(k) @geq{} 0}).

@item @var{V}(k)
mean number of visits to center @math{k}.
(vector of length @math{K}, @code{@var{V}(k) @geq{} 0}).

@item @var{m}(k)
number of servers at center @math{k}.
This function only supports @math{M/M/1} queues, therefore
@var{m} must be @code{ones(size(S))}.

@end table

@strong{OUTPUTS}

@table @code

@item @var{Xl}
@item @var{Xu}
Lower and upper bounds on the system throughput. @var{Xl} is
always set to @math{0} since there can be no lower bound on the
throughput of open networks (scalar).

@item @var{Rl}
@item @var{Ru}
Lower and upper bounds on the system response time. @var{Ru}
is always set to @code{+inf} since there can be no upper bound on the
throughput of open networks (scalar).

@end table

@xseealso{qnomaba}

@end deftypefn


@c
@anchor{doc-qnomaba}


@deftypefn {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnomaba (@var{lambda}, @var{D})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Rl}] =} qnomaba (@var{lambda}, @var{S}, @var{V})

@cindex bounds, asymptotic
@cindex open network
@cindex multiclass network, open

Compute Asymptotic Bounds for open, multiclass networks with @math{K}
service centers and @math{C} customer classes.

@strong{INPUTS}

@table @code

@item @var{lambda}(c)
class @math{c} arrival rate to the system (vector of length
@math{C}, @code{@var{lambda}(c) > 0}).

@item @var{D}(c, k)
class @math{c} service demand at center @math{k} (@math{C \times K}
matrix, @code{@var{D}(c, k) @geq{} 0}).

@item @var{S}(c, k)
mean service time of class @math{c} requests at center @math{k}
(@math{C \times K} matrix, @code{@var{S}(c, k) @geq{} 0}).

@item @var{V}(c, k)
mean number of visits of class @math{c} requests at center @math{k}
(@math{C \times K} matrix, @code{@var{V}(c, k) @geq{} 0}).

@end table

@strong{OUTPUTS}

@table @code

@item @var{Xl}(c)
@item @var{Xu}(c)
lower and upper bounds of class @math{c} throughput.
@code{@var{Xl}(c)} is always @math{0} since there can be no lower
bound on the throughput of open networks (vector of length
@math{C}).

@item @var{Rl}(c)
@item @var{Ru}(c)
lower and upper bounds of class @math{c} response time.
@code{@var{Ru}(c)} is always @code{+inf} since there can be no
upper bound on the response time of open networks (vector of length
@math{C}).

@end table

@end deftypefn


@c
@anchor{doc-qncsaba}


@deftypefn {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncsaba (@var{N}, @var{D})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncsaba (@var{N}, @var{S}, @var{V})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncsaba (@var{N}, @var{S}, @var{V}, @var{m})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncsaba (@var{N}, @var{S}, @var{V}, @var{m}, @var{Z})

@cindex bounds, asymptotic
@cindex asymptotic bounds
@cindex closed network, single class

Compute Asymptotic Bounds for the system throughput and response
time of closed, single-class networks with @math{K} service
centers.

Single-server and infinite-server nodes are supported.
Multiple-server nodes and general load-dependent servers are not
supported.

@strong{INPUTS}

@table @code

@item @var{N}
number of requests in the system (scalar, @code{@var{N}>0}).

@item @var{D}(k)
service demand at center @math{k}
(@code{@var{D}(k) @geq{} 0}).

@item @var{S}(k)
mean service time at center @math{k}
(@code{@var{S}(k) @geq{} 0}).

@item @var{V}(k)
average number of visits to center
@math{k} (@code{@var{V}(k) @geq{} 0}).

@item @var{m}(k)
number of servers at center @math{k}
(if @var{m} is a scalar, all centers have that number of servers). If
@code{@var{m}(k) < 1}, center @math{k} is a delay center (IS);
if @code{@var{m}(k) = 1}, center @math{k} is a M/M/1-FCFS server.
This function does not support multiple-server nodes. Default
is 1.

@item @var{Z}
External delay (scalar, @code{@var{Z} @geq{} 0}). Default is 0.

@end table

@strong{OUTPUTS}

@table @code

@item @var{Xl}
@itemx @var{Xu}
Lower and upper bounds on the system throughput.

@item @var{Rl}
@itemx @var{Ru}
Lower and upper bounds on the system response time.

@end table

@xseealso{qncmaba}

@end deftypefn


@c
@anchor{doc-qncmaba}


@deftypefn {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncmaba (@var{N}, @var{D})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncmaba (@var{N}, @var{S}, @var{V})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncmaba (@var{N}, @var{S}, @var{V}, @var{m})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncmaba (@var{N}, @var{S}, @var{V}, @var{m}, @var{Z})

@cindex bounds, asymptotic
@cindex asymptotic bounds
@cindex closed network
@cindex multiclass network, closed
@cindex closed multiclass network

Compute Asymptotic Bounds for closed, multiclass networks
with @math{K} service centers and @math{C} customer classes.
Single-server and infinite-server nodes are supported.
Multiple-server nodes and general load-dependent servers are not
supported.

@strong{INPUTS}

@table @code

@item @var{N}(c)
number of class @math{c} requests in the system
(vector of length @math{C}, @code{@var{N}(c) @geq{} 0}).

@item @var{D}(c, k)
class @math{c} service demand
at center @math{k} (@math{C \times K} matrix, @code{@var{D}(c,k) @geq{} 0}).

@item @var{S}(c, k)
mean service time of class @math{c}
requests at center @math{k} (@math{C \times K} matrix, @code{@var{S}(c,k) @geq{} 0}).

@item @var{V}(c,k)
average number of visits of class @math{c}
requests to center @math{k} (@math{C \times K} matrix, @code{@var{V}(c,k) @geq{} 0}).

@item @var{m}(k)
number of servers at center @math{k}
(if @var{m} is a scalar, all centers have that number of servers). If
@code{@var{m}(k) < 1}, center @math{k} is a delay center (IS);
if @code{@var{m}(k) = 1}, center @math{k} is a M/M/1-FCFS server.
This function does not support multiple-server nodes. Default
is 1.

@item @var{Z}(c)
class @math{c} external delay
(vector of length @math{C}, @code{@var{Z}(c) @geq{} 0}). Default is 0.

@end table

@strong{OUTPUTS}

@table @code

@item @var{Xl}(c)
@itemx @var{Xu}(c)
Lower and upper bounds for class @math{c} throughput.

@item @var{Rl}(c)
@itemx @var{Ru}(c)
Lower and upper bounds for class @math{c} response time.

@end table

@strong{REFERENCES}

@itemize
@item
Edward D. Lazowska, John Zahorjan, G.  Scott Graham, and Kenneth
C. Sevcik, @cite{Quantitative System Performance: Computer System
Analysis Using Queueing Network Models}, Prentice Hall,
1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In
particular, see section 5.2 ("Asymptotic Bounds").
@end itemize

@xseealso{qncsaba}

@end deftypefn


@c
@anchor{doc-qnosbsb}


@deftypefn {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnosbsb (@var{lambda}, @var{D})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qnosbsb (@var{lambda}, @var{S}, @var{V})

@cindex bounds, balanced system
@cindex open network

Compute Balanced System Bounds for single-class, open networks with
@math{K} service centers.

@strong{INPUTS}

@table @code

@item @var{lambda}
overall arrival rate to the system (scalar, @code{@var{lambda} @geq{} 0}).

@item @var{D}(k)
service demand at center @math{k} (@code{@var{D}(k) @geq{} 0}).

@item @var{S}(k)
service time at center @math{k} (@code{@var{S}(k) @geq{} 0}).

@item @var{V}(k)
mean number of visits at center @math{k} (@code{@var{V}(k) @geq{} 0}).

@item @var{m}(k)
number of servers at center @math{k}. This function only supports
@math{M/M/1} queues, therefore @var{m} must be
@code{ones(size(S))}.

@end table

@strong{OUTPUTS}

@table @code

@item @var{Xl}
@item @var{Xu}
Lower and upper bounds on the system throughput. @var{Xl} is always
set to @math{0}, since there can be no lower bound on open
networks throughput.

@item @var{Rl}
@itemx @var{Ru}
Lower and upper bounds on the system response time.

@end table

@xseealso{qnosaba}

@end deftypefn


@c
@anchor{doc-qncsbsb}


@deftypefn {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncsbsb (@var{N}, @var{D})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncsbsb (@var{N}, @var{S}, @var{V})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncsbsb (@var{N}, @var{S}, @var{V}, @var{m})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncsbsb (@var{N}, @var{S}, @var{V}, @var{m}, @var{Z})

@cindex bounds, balanced system
@cindex closed network, single class
@cindex balanced system bounds

Compute Balanced System Bounds on system throughput and response time for closed, single-class networks with @math{K} service centers.

@strong{INPUTS}

@table @code

@item @var{N}
number of requests in the system (scalar, @code{@var{N} @geq{} 0}).

@item @var{D}(k)
service demand at center @math{k} (@code{@var{D}(k) @geq{} 0}).

@item @var{S}(k)
mean service time at center @math{k} (@code{@var{S}(k) @geq{} 0}).

@item @var{V}(k)
average number of visits to center @math{k} (@code{@var{V}(k)
@geq{} 0}). Default is 1.

@item @var{m}(k)
number of servers at center @math{k}. This function supports
@code{@var{m}(k) = 1} only (single-eserver FCFS nodes); this
parameter is only for compatibility with @code{qncsaba}. Default is
1.

@item @var{Z}
External delay (@code{@var{Z} @geq{} 0}). Default is 0.

@end table

@strong{OUTPUTS}

@table @code

@item @var{Xl}
@itemx @var{Xu}
Lower and upper bound on the system throughput.

@item @var{Rl}
@itemx @var{Ru}
Lower and upper bound on the system response time.

@end table

@strong{REFERENCES}

@itemize
@item
Edward D. Lazowska, John Zahorjan, G.  Scott Graham, and Kenneth
C. Sevcik, @cite{Quantitative System Performance: Computer System
Analysis Using Queueing Network Models}, Prentice Hall,
1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In
particular, see section 5.4 ("Balanced Systems Bounds").
@end itemize

@xseealso{qncmbsb}

@end deftypefn


@c
@anchor{doc-qncmbsb}


@deftypefn {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncmbsb (@var{N}, @var{D})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncmbsb (@var{N}, @var{S}, @var{V})

@cindex bounds, balanced system
@cindex balanced system bounds
@cindex multiclass network, closed
@cindex closed multiclass network

Compute Balanced System Bounds for closed, multiclass networks
with @math{K} service centers and @math{C} customer classes.
Only single-server nodes are supported.

@strong{INPUTS}

@table @code

@item @var{N}(c)
number of class @math{c} requests in the system (vector of length
@math{C}).

@item @var{D}(c, k)
class @math{c} service demand  at center @math{k} (@math{C \times K}
matrix, @code{@var{D}(c,k) @geq{} 0}).

@item @var{S}(c, k)
mean service time of class @math{c}
requests at center @math{k} (@math{C \times K} matrix, @code{@var{S}(c,k) @geq{} 0}).

@item @var{V}(c,k)
average number of visits of class @math{c}
requests to center @math{k} (@math{C \times K} matrix, @code{@var{V}(c,k) @geq{} 0}).

@end table

@strong{OUTPUTS}

@table @code

@item @var{Xl}(c)
@itemx @var{Xu}(c)
Lower and upper class @math{c} throughput bounds (vector of length @math{C}).

@item @var{Rl}(c)
@itemx @var{Ru}(c)
Lower and upper class @math{c} response time bounds (vector of length @math{C}).

@end table

@xseealso{qncsbsb}

@end deftypefn


@c
@anchor{doc-qncmcb}


@deftypefn {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncmcb (@var{N}, @var{D})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncmcb (@var{N}, @var{S}, @var{V})

@cindex multiclass network, closed
@cindex closed multiclass network
@cindex bounds, composite
@cindex composite bounds

Compute Composite Bounds (CB) on system throughput and response time for closed multiclass networks.

@strong{INPUTS}

@table @code

@item @var{N}(c)
number of class @math{c} requests in the system.

@item @var{D}(c, k)
class @math{c} service demand
at center @math{k} (@code{@var{S}(c,k) @geq{} 0}).

@item @var{S}(c, k)
mean service time of class @math{c}
requests at center @math{k} (@code{@var{S}(c,k) @geq{} 0}).

@item @var{V}(c,k)
average number of visits of class @math{c}
requests to center @math{k} (@code{@var{V}(c,k) @geq{} 0}).

@end table

@strong{OUTPUTS}

@table @code

@item @var{Xl}(c)
@itemx @var{Xu}(c)
Lower and upper bounds on class @math{c} throughput.

@item @var{Rl}(c)
@itemx @var{Ru}(c)
Lower and upper bounds on class @math{c} response time.

@end table

@strong{REFERENCES}

@itemize
@item
Teemu Kerola, @cite{The Composite Bound Method (CBM) for Computing
Throughput Bounds in Multiple Class Environments}, Performance
Evaluation Vol. 6, Issue 1, March 1986, DOI
@uref{http://dx.doi.org/10.1016/0166-5316(86)90002-7,
10.1016/0166-5316(86)90002-7}. Also available as
@uref{http://docs.lib.purdue.edu/cstech/395/, Technical Report
CSD-TR-475}, Department of Computer Sciences, Purdue University, mar
13, 1984 (Revised Aug 27, 1984).
@end itemize

@end deftypefn


@c
@anchor{doc-qncspb}


@deftypefn {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncspb (@var{N}, @var{D} )
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncspb (@var{N}, @var{S}, @var{V} )
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncspb (@var{N}, @var{S}, @var{V}, @var{m} )
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}] =} qncspb (@var{N}, @var{S}, @var{V}, @var{m}, @var{Z} )

@cindex bounds, PB
@cindex PB bounds
@cindex closed network, single class

Compute PB Bounds (C. H. Hsieh and S. Lam, 1987) for single-class,
closed networks with @math{K} service centers.

@strong{INPUTS}

@table @code

@item @var{}
number of requests in the system (scalar, @code{@var{N} > 0}).

@item @var{D}(k)
service demand of service center @math{k} (@code{@var{D}(k) @geq{} 0}).

@item @var{S}(k)
mean service time at center @math{k} (@code{@var{S}(k) @geq{} 0}).

@item @var{V}(k)
visit ratio to center @math{k} (@code{@var{V}(k) @geq{} 0}).

@item @var{m}(k)
number of servers at center @math{k}. This function only supports
@math{M/M/1} queues, therefore @var{m} must be
@code{ones(size(S))}.

@item @var{Z}
external delay (think time, @code{@var{Z} @geq{} 0}). Default 0.

@end table

@strong{OUTPUTS}

@table @code

@item @var{Xl}
@itemx @var{Xu}
Lower and upper bounds on the system throughput.

@item @var{Rl}
@itemx @var{Ru}
Lower and upper bounds on the system response time.

@end table

@strong{REFERENCES}

@itemize
@item
C. H. Hsieh and S. Lam, @cite{Two classes of performance bounds for
closed queueing networks}, Performance Evaluation, Vol. 7 Issue 1,
pp. 3--30, February 1987, DOI
@uref{http://dx.doi.org/10.1016/0166-5316(87)90054-X,
10.1016/0166-5316(87)90054-X}. Also available as
@uref{ftp://ftp.cs.utexas.edu/pub/techreports/tr85-09.pdf, Technical
Report TR-85-09}, Department of Computer Science, University of Texas
at Austin, June 1985
@end itemize

This function implements the non-iterative variant described in G.
Casale, R. R. Muntz, G. Serazzi, @cite{Geometric Bounds: a
Non-Iterative Analysis Technique for Closed Queueing Networks}, IEEE
Transactions on Computers, 57(6):780-794, June 2008.

@xseealso{qncsaba, qbcsbsb, qncsgb}

@end deftypefn


@c
@anchor{doc-qncsgb}


@deftypefn {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}, @var{Ql}, @var{Qu}] =} qncsgb (@var{N}, @var{D})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}, @var{Ql}, @var{Qu}] =} qncsgb (@var{N}, @var{S}, @var{V})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}, @var{Ql}, @var{Qu}] =} qncsgb (@var{N}, @var{S}, @var{V}, @var{m})
@deftypefnx {Function File} {[@var{Xl}, @var{Xu}, @var{Rl}, @var{Ru}, @var{Ql}, @var{Qu}] =} qncsgb (@var{N}, @var{S}, @var{V}, @var{m}, @var{Z})

@cindex bounds, geometric
@cindex geometric bounds
@cindex closed network

Compute Geometric Bounds (GB) on system throughput, system response
time and server queue lenghts for closed, single-class networks
with @math{K} service centers and @math{N} requests.

@strong{INPUTS}

@table @code

@item @var{N}
number of requests in the system (scalar, @code{@var{N} > 0}).

@item @var{D}(k)
service demand of service center @math{k} (vector of length
@math{K}, @code{@var{D}(k) @geq{} 0}).

@item @var{S}(k)
mean service time at center @math{k} (vector of length @math{K},
@code{@var{S}(k) @geq{} 0}).

@item @var{V}(k)
visit ratio to center @math{k}
(vector of length @math{K}, @code{@var{V}(k) @geq{} 0}).

@item @var{m}(k)
number of servers at center @math{k}. This function only supports
@math{M/M/1} queues, therefore @var{m} must be
@code{ones(size(S))}.

@item @var{Z}
external delay (think time, @code{@var{Z} @geq{} 0}, scalar). Default is 0.

@end table

@strong{OUTPUTS}

@table @code

@item @var{Xl}
@itemx @var{Xu}
Lower and upper bound on the system throughput. If @code{@var{Z}>0},
these bounds are computed using @emph{Geometric Square-root Bounds}
(GSB). If @code{@var{Z}==0}, these bounds are computed using @emph{Geometric Bounds} (GB)

@item @var{Rl}
@itemx @var{Ru}
Lower and upper bound on the system response time. These bounds
are derived from @var{Xl} and @var{Xu} using Little's Law:
@code{@var{Rl} = @var{N} / @var{Xu} - @var{Z}},
@code{@var{Ru} = @var{N} / @var{Xl} - @var{Z}}

@item @var{Ql}(k)
@itemx @var{Qu}(k)
lower and upper bounds of center @math{K} queue length.

@end table

@strong{REFERENCES}

@itemize
@item
G. Casale, R. R. Muntz, G. Serazzi, @cite{Geometric Bounds: a
Non-Iterative Analysis Technique for Closed Queueing Networks}, IEEE
Transactions on Computers, 57(6):780-794, June
2008. @uref{http://doi.ieeecomputersociety.org/10.1109/TC.2008.37,
10.1109/TC.2008.37}
@end itemize

In this implementation we set @math{X^+} and @math{X^-} as the upper
and lower Asymptotic Bounds as computed by the @command{qncsab}
function, respectively.

@end deftypefn


@c
@c Examples
@c

@node QN Analysis Examples
@section QN Analysis Examples

In this section we illustrate with a few examples how the
@code{queueing} package can be used to analyze queueing network
models. Further examples can be found in the functions demo blocks,
and can be inspected with the @code{demo @emph{function}} Octave
command.

@subsection Closed, Single Class Network

Let us consider again the network shown in
@ref{fig:qn_closed_single}. We denote with @math{S_k} the average
service time at center @math{k}, @math{k=1, 2, 3}. Let the service
times be @math{S_1 = 1.0}, @math{S_2 = 2.0} and @math{S_3 = 0.8}. The
routing of jobs within the network is described with a @emph{routing
probability matrix} @math{\bf P}: a request completing service at
center @math{i} is enqueued at center @math{j} with probability
@math{P_{i, j}}.  We use the following routing matrix:

@iftex
@tex
$$
{\bf P} = \pmatrix{ 0 & 0.3 & 0.7 \cr
                    1 & 0 & 0 \cr
                    1 & 0 & 0 }
$$
@end tex
@end iftex
@ifnottex
@example
    / 0  0.3  0.7 \
P = | 1  0    0   |
    \ 1  0    0   /
@end example
@end ifnottex

The network above can be analyzed with the @command{qnclosed} function
@pxref{doc-qnclosed}. @command{qnclosed} requires the following
parameters:

@table @var

@item N
Number of requests in the network (since we are considering a closed
network, the number of requests is fixed)

@item S
Array of average service times at the centers: @code{@var{S}(k)} is
the average service time at center @math{k}.

@item V
Array of visit ratios: @code{@var{V}(k)} is the average number of
visits to center @math{k}.

@end table

We can compute @math{V_k} from the routing probability matrix
@math{P_{i, j}} using the @command{qncsvisits} function
@pxref{doc-qncsvisits}.  Therefore, we can analyze the network for a
given population size @math{N} (e.g., @math{N=10}) as follows:

@example
@group
@kbd{N = 10;}
@kbd{S = [1 2 0.8];}
@kbd{P = [0 0.3 0.7; 1 0 0; 1 0 0];}
@kbd{V = qncsvisits(P);}
@kbd{[U R Q X] = qnclosed( N, S, V )}
   @result{} U = 0.99139 0.59483 0.55518
   @result{} R = 7.4360  4.7531  1.7500
   @result{} Q = 7.3719  1.4136  1.2144
   @result{} X = 0.99139 0.29742 0.69397
@end group
@end example

The output of @command{qnclosed} includes the vectors of utilizations
@math{U_k} at center @math{k}, response time @math{R_k}, average
number of customers @math{Q_k} and throughput @math{X_k}. In our
example, the throughput of center 1 is @math{X_1 = 0.99139}, and the
average number of requests in center 3 is @math{Q_3 = 1.2144}. The
utilization of center 1 is @math{U_1 = 0.99139}, which is the highest
among the service centers. Thus, center 1 is the @emph{bottleneck
device}.

This network can also be analyzed with the @command{qnsolve} function
@pxref{doc-qnsolve}. @command{qnsolve} can handle open, closed or
mixed networks, and allows the network to be described in a very
flexible way.  First, let @var{Q1}, @var{Q2} and @var{Q3} be the
variables describing the service centers. Each variable is
instantiated with the @command{qnmknode} function.

@example
@group
@kbd{Q1 = qnmknode( "m/m/m-fcfs", 1 );}
@kbd{Q2 = qnmknode( "m/m/m-fcfs", 2 );}
@kbd{Q3 = qnmknode( "m/m/m-fcfs", 0.8 );}
@end group
@end example

The first parameter of @command{qnmknode} is a string describing the
type of the node; @code{"m/m/m-fcfs"} denotes a @math{M/M/m}--FCFS
center (this parameter is case-insensitive). The second parameter
gives the average service time. An optional third parameter can be
used to specify the number @math{m} of service centers. If omitted, it
is assumed @math{m=1} (single-server node).

Now, the network can be analyzed as follows:

@example
@group
@kbd{N = 10;}
@kbd{V = [1 0.3 0.7];}
@kbd{[U R Q X] = qnsolve( "closed", N, @{ Q1, Q2, Q3 @}, V )}
   @result{} U = 0.99139 0.59483 0.55518
   @result{} R = 7.4360  4.7531  1.7500
   @result{} Q = 7.3719  1.4136  1.2144
   @result{} X = 0.99139 0.29742 0.69397
@end group
@end example

@subsection Open, Single Class Network

Let us consider an open network with @math{K=3} service centers and
the following routing probabilities:

@iftex
@tex
$$
{\bf P} = \pmatrix{ 0 & 0.3 & 0.5 \cr
                    1 & 0 & 0 \cr
                    1 & 0 & 0 }
$$
@end tex
@end iftex
@ifnottex
@example
    / 0  0.3  0.5 \
P = ! 1  0    0   |
    \ 1  0    0   /
@end example
@end ifnottex

In this network, requests can leave the system from center 1 with
probability @math{1-(0.3+0.5) = 0.2}. We suppose that external jobs
arrive at center 1 with rate @math{\lambda_1 = 0.15}; there are no
arrivals at centers 2 and 3.

Similarly to closed networks, we first compute the visit counts
@math{V_k} to center @math{k}, @math{k = 1, 2, 3}. We use the
@command{qnosvisits} function as follows:

@example
@group
@kbd{P = [0 0.3 0.5; 1 0 0; 1 0 0];}
@kbd{lambda = [0.15 0 0];}
@kbd{V = qnosvisits(P, lambda)}
   @result{} V = 5.00000 1.50000 2.50000
@end group
@end example

@noindent where @code{@var{lambda}(k)} is the arrival rate at center @math{k},
and @math{\bf P} is the routing matrix. Assuming the same service times as
in the previous example, the network can be analyzed with the
@command{qnopen} function @pxref{doc-qnopen}, as follows:

@example
@group
@kbd{S = [1 2 0.8];}
@kbd{[U R Q X] = qnopen( sum(lambda), S, V )}
   @result{} U = 0.75000 0.45000 0.30000
   @result{} R = 4.0000  3.6364  1.1429
   @result{} Q = 3.00000 0.81818 0.42857
   @result{} X = 0.75000 0.22500 0.37500
@end group
@end example

The first parameter of the @command{qnopen} function is the (scalar)
aggregate arrival rate.

Again, it is possible to use the @command{qnsolve} high-level function:

@example
@group
@kbd{Q1 = qnmknode( "m/m/m-fcfs", 1 );}
@kbd{Q2 = qnmknode( "m/m/m-fcfs", 2 );}
@kbd{Q3 = qnmknode( "m/m/m-fcfs", 0.8 );}
@kbd{lambda = [0.15 0 0];}
@kbd{[U R Q X] = qnsolve( "open", sum(lambda), @{ Q1, Q2, Q3 @}, V )}
   @result{} U = 0.75000 0.45000 0.30000
   @result{} R = 4.0000  3.6364  1.1429
   @result{} Q = 3.00000 0.81818 0.42857
   @result{} X = 0.75000 0.22500 0.37500
@end group
@end example

@subsection Closed Multiclass Network/1

The following example is taken from Herb Schwetman, @cite{Implementing
the Mean Value Algorithm for the Solution of Queueing Network Models},
Technical Report CSD-TR-355, Department of Computer Sciences, Purdue
University, Feb 15, 1982.

Let us consider the following multiclass QN with three servers and two classes

@float Figure,fig:apl
@center @image{./qn_closed_multi_apl}
@end float

Servers 1 and 2 (labeled @emph{APL} and @emph{IMS}, respectively) are
infinite server nodes; server 3 (labeled @emph{SYS}) is Processor
Sharing (PS). Mean service times are given in the following table:

@multitable @columnfractions .15 .15 .15 .15
@headitem @tab  APL @tab IMS @tab SYS
@item Class 1 @tab 1 @tab - @tab 0.025
@item Class 2 @tab - @tab 15 @tab 0.500
@end multitable

There is no class switching. If  we assume a population of 15 requests
for  class 1,  and  5 requests  for class  2,  then the  model can  be
analyzed as follows:

@example
@verbatim
 S = [1 0 .025; 0 15 .5];
 P = zeros(2,3,2,3);
 P(1,1,1,3) = P(1,3,1,1) = 1;
 P(2,2,2,3) = P(2,3,2,2) = 1;
 V = qncmvisits(P,[3 3]); # reference station is station 3
 N = [15 5];
 m = [-1 -1 1];
 [U R Q X] = qncmmva(N,S,V,m)
@end verbatim
  @result{}
U =

   14.32312    0.00000    0.35808
    0.00000    4.70699    0.15690

R =

    1.00000    0.00000    0.04726
    0.00000   15.00000    0.93374

Q =

   14.32312    0.00000    0.67688
    0.00000    4.70699    0.29301

X =

   14.32312    0.00000   14.32312
    0.00000    0.31380    0.31380
@end example

@subsection Closed Multiclass Network/2

The following example is from M. Marzolla, @cite{The qnetworks
Toolbox: A Software Package for Queueing Networks Analysis}, Technical
Report
@uref{https://www.moreno.marzolla.name/publications/papers/UBLCS-2010-04.pdf,
UBLCS-2010-04}, Department of Computer Science, University of Bologna,
Italy, February 2010.

@float Figure,fig:web_model
@center @image{./qn_web_model,3in}
@caption{Three-tier enterprise system model}
@end float

The model shown in @ref{fig:web_model} shows a three-tier enterprise
system with @math{K=6} service centers. The first tier contains the
@emph{Web server} (node 1), which is responsible for generating Web
pages and transmitting them to clients. The application logic is
implemented by nodes 2 and 3, and the storage tier is made of nodes
4--6.The system is subject to two workload classes, both represented
as closed populations of @math{N_1} and @math{N_2} requests,
respectively. Let @math{D_{c, k}} denote the service demand of class
@math{c} requests at center @math{k}. We use the parameter values:

@multitable @columnfractions .2 .33 .1 .1
@headitem Serv. no. @tab  Name @tab Class 1 @tab Class 2
@item 1 @tab Web Server    @tab 12 @tab 2
@item 2 @tab App. Server 1 @tab 14 @tab 20
@item 3 @tab App. Server 2 @tab 23 @tab 14
@item 4 @tab DB Server 1   @tab 20 @tab 90
@item 5 @tab DB Server 2   @tab 80 @tab 30
@item 6 @tab DB Server 3   @tab 31 @tab 33
@end multitable

We set the total number of requests to 100, that is @math{N_1 + N_2 =
N = 100}, and we study how different population mixes @math{(N_1,
N_2)} affect the system throughput and response time. Let
@math{0 < \beta_1 < 1} denote the fraction of class 1 requests:
@math{N_1 = \beta_1 N}, @math{N_2 = (1-\beta_1)N}. The following
Octave code defines the model for @math{\beta_1 = 0.1}:

@example
@group
N = 100;     # total population size
beta1 = 0.1; # fraction of class 1 reqs.
S = [12 14 23 20 80 31; ...
      2 20 14 90 30 33 ];
V = ones(size(S));
pop = [fix(beta1*N) N-fix(beta1*N)];
[U R Q X] = qncmmva(pop, S, V);
@end group
@end example

The @command{qncmmva(pop, S, V)} function invocation uses the
multiclass MVA algorithm to compute per-class utilizations @math{U_{c,
k}}, response times @math{R_{c,k}}, mean queue lengths @math{Q_{c,k}}
and throughputs @math{X_{c,k}} at each service center @math{k}, given
a population vector @var{pop}, mean service times @var{S} and visit
ratios @var{V}. Since we are given the service demands @math{D_{c, k}
= S_{c, k} V_{c,k}}, but function @command{qncmmva} requires separate
service times and visit ratios, we set the service times equal to the
demands, and all visit ratios equal to one. Overall class and system
throughputs and response times can also be computed:

@example
@group
X1 = X(1,1) / V(1,1)     # class 1 throughput
        @result{} X1 =  0.0044219
X2 = X(2,1) / V(2,1)     # class 2 throughput
        @result{} X2 =  0.010128
XX = X1 + X2             # system throughput
        @result{} XX =  0.014550
R1 = dot(R(1,:), V(1,:)) # class 1 resp. time
        @result{} R1 =  2261.5
R2 = dot(R(2,:), V(2,:)) # class 2 resp. time
        @result{} R2 =  8885.9
RR = N / XX              # system resp. time
        @result{} RR =  6872.7
@end group
@end example

@code{dot(X,Y)} computes the dot product of two vectors.
@code{R(1,:)} is the first row of matrix @var{R} and @code{V(1,:)} is
the first row of matrix @var{V}, so @code{dot(R(1,:), V(1,:))}
computes @math{\sum_k R_{1,k} V_{1,k}}.

@float Figure,fig:web
@center @image{./web,5in}
@caption{Throughput and Response Times as a function of the population mix}
@end float

We can also compute the system power @math{\Phi = X / R}, which
defines how efficiently resources are being used: high values of
@math{\Phi} denote the desirable situation of high throughput and low
response time. @ref{fig:power} shows @math{\Phi} as a function of
@math{\beta_1}. We observe a ``plateau'' of the global system power,
corresponding to values of @math{\beta_1} which approximately lie
between @math{0.3} and @math{0.7}. The per-class power exhibits an
interesting (although not completely surprising) pattern, where the
class with higher population exhibits worst efficiency as it produces
higher contention on the resources.

@float Figure,fig:power
@center @image{./power,5in}
@caption{System Power as a function of the population mix}
@end float

@subsection Closed Multiclass Network/3

We now consider an example of multiclass network with class switching.
The example is taken from @ref{Sch82}, and is shown in Figure
@ref{fig:class_switching}.

@float Figure,fig:class_switching
@center @image{./qn_closed_multi_cs,3in}
@caption{Multiclass Model with Class Switching}
@end float

The system consists of three devices and two job classes. The CPU node
is a PS server, while the two nodes labeled I/O are FCFS. Class 1 mean
service time at the CPU is @math{0.01}; class 2 mean service time at
the CPU is @math{0.05}. The mean service time at node 2 is @math{0.1},
and is class-independent. Similarly, the mean service time at node 3
is @math{0.07}. Jobs in class 1 leave the CPU and join class 2 with
probability @math{0.1}; jobs of class 2 leave the CPU and join class 1
with probability @math{0.2}. There are @math{N=3} jobs, which are
initially allocated to class 1. However, note that since class
switching is allowed, the total number of jobs in each class does not
remain constant; however the total number of jobs does.

@example
@verbatim
 C = 2; K = 3;
 S = [.01 .07 .10; ...
      .05 .07 .10 ];
 P = zeros(C,K,C,K);
 P(1,1,1,2) = .7; P(1,1,1,3) = .2; P(1,1,2,1) = .1;
 P(2,1,2,2) = .3; P(2,1,2,3) = .5; P(2,1,1,1) = .2;
 P(1,2,1,1) = P(2,2,2,1) = 1;
 P(1,3,1,1) = P(2,3,2,1) = 1;
 N = [3 0];
 [U R Q X] = qncmmva(N, S, P)
@end verbatim
  @result{}
U =

   0.12609   0.61784   0.25218
   0.31522   0.13239   0.31522

R =

   0.014653   0.133148   0.163256
   0.073266   0.133148   0.163256

Q =

   0.18476   1.17519   0.41170
   0.46190   0.25183   0.51462

X =

   12.6089    8.8262    2.5218
    6.3044    1.8913    3.1522
@end example