Mercurial > forge
changeset 9991:88af7493d626 octave-forge
improved documentation
| author | mmarzolla |
|---|---|
| date | Mon, 09 Apr 2012 12:50:58 +0000 |
| parents | 4b1a8882cdc3 |
| children | 3dae0b025ccb |
| files | main/queueing/doc/gettingstarted.txi main/queueing/doc/markovchains.txi main/queueing/doc/munge-texi.m main/queueing/doc/queueing.html main/queueing/doc/queueing.pdf main/queueing/doc/queueing.texi main/queueing/doc/queueingnetworks.txi main/queueing/doc/references.txi |
| diffstat | 8 files changed, 1056 insertions(+), 1216 deletions(-) [+] |
line wrap: on
line diff
--- a/main/queueing/doc/gettingstarted.txi Sun Apr 08 20:54:02 2012 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,316 +0,0 @@ -@c -*- texinfo -*- - -@c Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla -@c -@c This file is part of the queueing toolbox, a Queueing Networks -@c analysis package for GNU Octave. -@c -@c The queueing toolbox 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 toolbox 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 toolbox; see the file COPYING. If not, see -@c <http://www.gnu.org/licenses/>. - -@node Getting Started -@chapter Introduction and Getting Started - -@menu -* Analysis of Closed Networks:: -* Analysis of Open Networks:: -@end menu - -In this chapter we give some usage examples of the @code{queueing} -package. The reader is assumed to be familiar with Queueing Networks -(although some basic terminology and notation will be given -here). Additional usage examples are embedded in most of the function -files; to display and execute the demos associated with function -@emph{fname} you can type @command{demo @emph{fname}} at the Octave -prompt. For example - -@example -@kbd{demo qnclosed} -@end example - -@noindent executes all demos (if any) for the @command{qnclosed} function. - -@node Analysis of Closed Networks -@section Analysis of Closed Networks - -Let us consider a simple closed network with @math{K=3} service -centers. Each center is of type @math{M/M/1}--FCFS. We denote with -@math{S_i} the average service time at center @math{i}, @math{i=1, 2, -3}. Let @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{P}. Specifically, a request completing -service at center @math{i} is enqueued at center @math{j} with -probability @math{P_{i, j}}. Let us assume the following routing -probability matrix: - -@iftex -@tex -$$ -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 - -For example, according to matric @math{P} a job completing service at -center 1 is routed to center 2 with probability 0.3, and is routed to -center 3 with probability 0.7. - -The network above can be analyzed with the @command{qnclosed} -function; if there is just a single class of requests, as in the -example above, @command{qnclosed} calls @command{qnclosedsinglemva} -which implements the Mean Value Analysys (MVA) algorithm for -single-class, product-form network. - -@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 - -As can be seen, we must compute the @emph{visit ratios} (or visit -counts) @math{V_k} for each center @math{k}. The visit counts satisfy -the following equations: - -@iftex -@tex -$$ -V_j = \sum_{i=1}^K V_i P_{i, j} -$$ -@end tex -@end iftex -@ifnottex -@example -V_j = sum_i V_i P_ij -@end example -@end ifnottex - -We can compute @math{V_k} from the routing probability matrix -@math{P_{i, j}} using the @command{qnvisits} function: - -@example -@group -@kbd{P = [0 0.3 0.7; 1 0 0; 1 0 0];} -@kbd{V = qnvisits(P)} - @result{} V = 1.00000 0.30000 0.70000 -@end group -@end example - -We can check that the computed values satisfy the above equation by -evaluating the following expression: - -@example -@kbd{V*P} - @result{} ans = 1.00000 0.30000 0.70000 -@end example - -@noindent which is equal to @math{V}. -Hence, we can analyze the network for a given population size @math{N} -(for example, @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 = qnvisits(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 vector 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 higher -value among the service centers. Tus, center 1 is the @emph{bottleneck -device}. - -This network can also be analyzed with the @command{qnsolve} -function. @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. Here we use @code{"m/m/m-fcfs"} to denote a -@math{M/M/m}--FCFS center. 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 - -Of course, we get exactly the same results. Other functions can be used -for closed networks, @pxref{Algorithms for Product-Form QNs}. - -@node Analysis of Open Networks -@section Analysis of Open Networks - -Open networks can be analyzed in a similar way. Let us consider -an open network with @math{K=3} service centers, and routing -probability matrix as follows: - -@iftex -@tex -$$ -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 need to compute the visit -counts @math{V_k} to center @math{k}. Again, we use the -@command{qnvisits} 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 = qnvisits(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 @var{P} is the routing matrix. The visit counts @math{V_k} for -open networks satisfy the following equation: - -@iftex -@tex -$$ -V_j = P_{0, j} + \sum_{i=1}^K V_i P_{i, j} -$$ -@end tex -@end iftex -@ifnottex -@example -V_j = sum_i V_i P_ij -@end example -@end ifnottex - -where @math{P_{0, j}} is the probability of an external arrival to -center @math{j}. This can be computed as: - -@tex -$$ -P_{0, j} = {\lambda_j \over \sum_{i=1}^K \lambda_i } -$$ -@end tex - -Assuming the same service times as in the previous example, the -network can be analyzed with the @command{qnopen} function, 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 - -@c @node Markov Chains Analysis -@c @section Markov Chains Analysis - -@c @subsection Discrete-Time Markov Chains - -@c (TODO) - -@c @subsection Continuous-Time Markov Chains - -@c (TODO) -
--- a/main/queueing/doc/markovchains.txi Sun Apr 08 20:54:02 2012 +0000 +++ b/main/queueing/doc/markovchains.txi Mon Apr 09 12:50:58 2012 +0000 @@ -139,8 +139,8 @@ @noindent @strong{EXAMPLE} -This example is from [GrSn97]. Let us consider a maze with nine rooms, -as shown in the following figure +This example is from @ref{GrSn97}. Let us consider a maze with nine +rooms, as shown in the following figure @example @group
--- a/main/queueing/doc/munge-texi.m Sun Apr 08 20:54:02 2012 +0000 +++ b/main/queueing/doc/munge-texi.m Mon Apr 09 12:50:58 2012 +0000 @@ -40,7 +40,7 @@ ## Texinfo crashes if @end tex does not appear first on the line. text = regexprep (text, '^ +@end tex', '@end tex', 'lineanchors'); - printf("%s\n", text); + printf("@anchor{doc-%s}\n%s\n", func, text); endfunction ##############################################################################
--- a/main/queueing/doc/queueing.html Sun Apr 08 20:54:02 2012 +0000 +++ b/main/queueing/doc/queueing.html Mon Apr 09 12:50:58 2012 +0000 @@ -52,69 +52,66 @@ <li><a href="#Development-sources">2.3 Development sources</a> <li><a href="#Using-the-queueing-toolbox">2.4 Using the queueing toolbox</a> </li></ul> -<li><a name="toc_Getting-Started" href="#Getting-Started">3 Introduction and Getting Started</a> +<li><a name="toc_Markov-Chains" href="#Markov-Chains">3 Markov Chains</a> <ul> -<li><a href="#Analysis-of-Closed-Networks">3.1 Analysis of Closed Networks</a> -<li><a href="#Analysis-of-Open-Networks">3.2 Analysis of Open Networks</a> -</li></ul> -<li><a name="toc_Markov-Chains" href="#Markov-Chains">4 Markov Chains</a> -<ul> -<li><a href="#Discrete_002dTime-Markov-Chains">4.1 Discrete-Time Markov Chains</a> +<li><a href="#Discrete_002dTime-Markov-Chains">3.1 Discrete-Time Markov Chains</a> <ul> -<li><a href="#State-occupancy-probabilities-_0028DTMC_0029">4.1.1 State occupancy probabilities</a> -<li><a href="#Birth_002ddeath-process-_0028DTMC_0029">4.1.2 Birth-death process</a> -<li><a href="#Expected-number-of-visits-_0028DTMC_0029">4.1.3 Expected Number of Visits</a> -<li><a href="#Time_002daveraged-expected-sojourn-times-_0028DTMC_0029">4.1.4 Time-averaged expected sojourn times</a> -<li><a href="#Mean-time-to-absorption-_0028DTMC_0029">4.1.5 Mean Time to Absorption</a> -<li><a href="#First-passage-times-_0028DTMC_0029">4.1.6 First Passage Times</a> +<li><a href="#State-occupancy-probabilities-_0028DTMC_0029">3.1.1 State occupancy probabilities</a> +<li><a href="#Birth_002ddeath-process-_0028DTMC_0029">3.1.2 Birth-death process</a> +<li><a href="#Expected-number-of-visits-_0028DTMC_0029">3.1.3 Expected Number of Visits</a> +<li><a href="#Time_002daveraged-expected-sojourn-times-_0028DTMC_0029">3.1.4 Time-averaged expected sojourn times</a> +<li><a href="#Mean-time-to-absorption-_0028DTMC_0029">3.1.5 Mean Time to Absorption</a> +<li><a href="#First-passage-times-_0028DTMC_0029">3.1.6 First Passage Times</a> </li></ul> -<li><a href="#Continuous_002dTime-Markov-Chains">4.2 Continuous-Time Markov Chains</a> +<li><a href="#Continuous_002dTime-Markov-Chains">3.2 Continuous-Time Markov Chains</a> <ul> -<li><a href="#State-occupancy-probabilities-_0028CTMC_0029">4.2.1 State occupancy probabilities</a> -<li><a href="#Birth_002ddeath-process-_0028CTMC_0029">4.2.2 Birth-Death Process</a> -<li><a href="#Expected-sojourn-times-_0028CTMC_0029">4.2.3 Expected Sojourn Times</a> -<li><a href="#Time_002daveraged-expected-sojourn-times-_0028CTMC_0029">4.2.4 Time-Averaged Expected Sojourn Times</a> -<li><a href="#Mean-time-to-absorption-_0028CTMC_0029">4.2.5 Mean Time to Absorption</a> -<li><a href="#First-passage-times-_0028CTMC_0029">4.2.6 First Passage Times</a> +<li><a href="#State-occupancy-probabilities-_0028CTMC_0029">3.2.1 State occupancy probabilities</a> +<li><a href="#Birth_002ddeath-process-_0028CTMC_0029">3.2.2 Birth-Death Process</a> +<li><a href="#Expected-sojourn-times-_0028CTMC_0029">3.2.3 Expected Sojourn Times</a> +<li><a href="#Time_002daveraged-expected-sojourn-times-_0028CTMC_0029">3.2.4 Time-Averaged Expected Sojourn Times</a> +<li><a href="#Mean-time-to-absorption-_0028CTMC_0029">3.2.5 Mean Time to Absorption</a> +<li><a href="#First-passage-times-_0028CTMC_0029">3.2.6 First Passage Times</a> </li></ul> </li></ul> -<li><a name="toc_Single-Station-Queueing-Systems" href="#Single-Station-Queueing-Systems">5 Single Station Queueing Systems</a> +<li><a name="toc_Single-Station-Queueing-Systems" href="#Single-Station-Queueing-Systems">4 Single Station Queueing Systems</a> <ul> -<li><a href="#The-M_002fM_002f1-System">5.1 The M/M/1 System</a> -<li><a href="#The-M_002fM_002fm-System">5.2 The M/M/m System</a> -<li><a href="#The-M_002fM_002finf-System">5.3 The M/M/inf System</a> -<li><a href="#The-M_002fM_002f1_002fK-System">5.4 The M/M/1/K System</a> -<li><a href="#The-M_002fM_002fm_002fK-System">5.5 The M/M/m/K System</a> -<li><a href="#The-Asymmetric-M_002fM_002fm-System">5.6 The Asymmetric M/M/m System</a> -<li><a href="#The-M_002fG_002f1-System">5.7 The M/G/1 System</a> -<li><a href="#The-M_002fHm_002f1-System">5.8 The M/H_m/1 System</a> +<li><a href="#The-M_002fM_002f1-System">4.1 The M/M/1 System</a> +<li><a href="#The-M_002fM_002fm-System">4.2 The M/M/m System</a> +<li><a href="#The-M_002fM_002finf-System">4.3 The M/M/inf System</a> +<li><a href="#The-M_002fM_002f1_002fK-System">4.4 The M/M/1/K System</a> +<li><a href="#The-M_002fM_002fm_002fK-System">4.5 The M/M/m/K System</a> +<li><a href="#The-Asymmetric-M_002fM_002fm-System">4.6 The Asymmetric M/M/m System</a> +<li><a href="#The-M_002fG_002f1-System">4.7 The M/G/1 System</a> +<li><a href="#The-M_002fHm_002f1-System">4.8 The M/H_m/1 System</a> </li></ul> -<li><a name="toc_Queueing-Networks" href="#Queueing-Networks">6 Queueing Networks</a> +<li><a name="toc_Queueing-Networks" href="#Queueing-Networks">5 Queueing Networks</a> <ul> -<li><a href="#Introduction-to-QNs">6.1 Introduction to QNs</a> +<li><a href="#Introduction-to-QNs">5.1 Introduction to QNs</a> <ul> -<li><a href="#Introduction-to-QNs">6.1.1 Single class models</a> -<li><a href="#Introduction-to-QNs">6.1.2 Multiple class models</a> +<li><a href="#Introduction-to-QNs">5.1.1 Single class models</a> +<li><a href="#Introduction-to-QNs">5.1.2 Multiple class models</a> +<li><a href="#Introduction-to-QNs">5.1.3 Closed Network Example</a> +<li><a href="#Introduction-to-QNs">5.1.4 Open Network Example</a> </li></ul> -<li><a href="#Generic-Algorithms">6.2 Generic Algorithms</a> -<li><a href="#Algorithms-for-Product_002dForm-QNs">6.3 Algorithms for Product-Form QNs</a> +<li><a href="#Algorithms-for-Product_002dForm-QNs">5.2 Algorithms for Product-Form QNs</a> <ul> -<li><a href="#Algorithms-for-Product_002dForm-QNs">6.3.1 Jackson Networks</a> -<li><a href="#Algorithms-for-Product_002dForm-QNs">6.3.2 The Convolution Algorithm</a> -<li><a href="#Algorithms-for-Product_002dForm-QNs">6.3.3 Open networks</a> -<li><a href="#Algorithms-for-Product_002dForm-QNs">6.3.4 Closed Networks</a> -<li><a href="#Algorithms-for-Product_002dForm-QNs">6.3.5 Mixed Networks</a> +<li><a href="#Algorithms-for-Product_002dForm-QNs">5.2.1 Jackson Networks</a> +<li><a href="#Algorithms-for-Product_002dForm-QNs">5.2.2 The Convolution Algorithm</a> +<li><a href="#Algorithms-for-Product_002dForm-QNs">5.2.3 Open networks</a> +<li><a href="#Algorithms-for-Product_002dForm-QNs">5.2.4 Closed Networks</a> +<li><a href="#Algorithms-for-Product_002dForm-QNs">5.2.5 Mixed Networks</a> </li></ul> -<li><a href="#Algorithms-for-non-Product_002dform-QNs">6.4 Algorithms for non Product-Form QNs</a> -<li><a href="#Bounds-on-performance">6.5 Bounds on performance</a> -<li><a href="#Utility-functions">6.6 Utility functions</a> +<li><a href="#Algorithms-for-non-Product_002dForm-QNs">5.3 Algorithms for non Product-Form QNs</a> +<li><a href="#Generic-Algorithms">5.4 Generic Algorithms</a> +<li><a href="#Bounds-on-performance">5.5 Bounds on performance</a> +<li><a href="#Utility-functions">5.6 Utility functions</a> <ul> -<li><a href="#Utility-functions">6.6.1 Open or closed networks</a> -<li><a href="#Utility-functions">6.6.2 Computation of the visit counts</a> -<li><a href="#Utility-functions">6.6.3 Other utility functions</a> +<li><a href="#Utility-functions">5.6.1 Open or closed networks</a> +<li><a href="#Utility-functions">5.6.2 Computation of the visit counts</a> +<li><a href="#Utility-functions">5.6.3 Other utility functions</a> </li></ul> </li></ul> -<li><a name="toc_References" href="#References">7 References</a> +<li><a name="toc_References" href="#References">6 References</a> <li><a name="toc_Copying" href="#Copying">Appendix A GNU GENERAL PUBLIC LICENSE</a> <li><a name="toc_Concept-Index" href="#Concept-Index">Concept Index</a> <li><a name="toc_Function-Index" href="#Function-Index">Function Index</a> @@ -139,14 +136,13 @@ <ul class="menu"> <li><a accesskey="1" href="#Summary">Summary</a> <li><a accesskey="2" href="#Installation">Installation</a>: Installation of the queueing toolbox. -<li><a accesskey="3" href="#Getting-Started">Getting Started</a>: Getting started with the queueing toolbox. -<li><a accesskey="4" href="#Markov-Chains">Markov Chains</a>: Functions for Markov Chains. -<li><a accesskey="5" href="#Single-Station-Queueing-Systems">Single Station Queueing Systems</a>: Functions for single-station queueing systems. -<li><a accesskey="6" href="#Queueing-Networks">Queueing Networks</a>: Functions for queueing networks. -<li><a accesskey="7" href="#References">References</a>: References -<li><a accesskey="8" href="#Copying">Copying</a>: The GNU General Public License. -<li><a accesskey="9" href="#Concept-Index">Concept Index</a>: An item for each concept. -<li><a href="#Function-Index">Function Index</a>: An item for each function. +<li><a accesskey="3" href="#Markov-Chains">Markov Chains</a>: Functions for Markov Chains. +<li><a accesskey="4" href="#Single-Station-Queueing-Systems">Single Station Queueing Systems</a>: Functions for single-station queueing systems. +<li><a accesskey="5" href="#Queueing-Networks">Queueing Networks</a>: Functions for queueing networks. +<li><a accesskey="6" href="#References">References</a>: References +<li><a accesskey="7" href="#Copying">Copying</a>: The GNU General Public License. +<li><a accesskey="8" href="#Concept-Index">Concept Index</a>: An item for each concept. +<li><a accesskey="9" href="#Function-Index">Function Index</a>: An item for each function. <li><a href="#Author-Index">Author Index</a>: An item for each author. </ul> @@ -369,7 +365,7 @@ <div class="node"> <a name="Installation"></a> <p><hr> -Next: <a rel="next" accesskey="n" href="#Getting-Started">Getting Started</a>, +Next: <a rel="next" accesskey="n" href="#Markov-Chains">Markov Chains</a>, Previous: <a rel="previous" accesskey="p" href="#Summary">Summary</a>, Up: <a rel="up" accesskey="u" href="#Top">Top</a> @@ -597,246 +593,7 @@ <pre class="example"> octave:4> <kbd>demo qnclosed</kbd> </pre> - <!-- This file has been automatically generated from gettingstarted.txi --> -<!-- by proc.m. Do not edit this file, all changes will be lost --> -<!-- *- texinfo -*- --> -<!-- Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla --> -<!-- This file is part of the queueing toolbox, a Queueing Networks --> -<!-- analysis package for GNU Octave. --> -<!-- The queueing toolbox is free software; you can redistribute it --> -<!-- and/or modify it under the terms of the GNU General Public License --> -<!-- as published by the Free Software Foundation; either version 3 of --> -<!-- the License, or (at your option) any later version. --> -<!-- The queueing toolbox is distributed in the hope that it will be --> -<!-- useful, but WITHOUT ANY WARRANTY; without even the implied warranty --> -<!-- of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the --> -<!-- GNU General Public License for more details. --> -<!-- You should have received a copy of the GNU General Public License --> -<!-- along with the queueing toolbox; see the file COPYING. If not, see --> -<!-- <http://www.gnu.org/licenses/>. --> -<div class="node"> -<a name="Getting-Started"></a> -<p><hr> -Next: <a rel="next" accesskey="n" href="#Markov-Chains">Markov Chains</a>, -Previous: <a rel="previous" accesskey="p" href="#Installation">Installation</a>, -Up: <a rel="up" accesskey="u" href="#Top">Top</a> - -</div> - -<h2 class="chapter">3 Introduction and Getting Started</h2> - -<ul class="menu"> -<li><a accesskey="1" href="#Analysis-of-Closed-Networks">Analysis of Closed Networks</a> -<li><a accesskey="2" href="#Analysis-of-Open-Networks">Analysis of Open Networks</a> -</ul> - -<p>In this chapter we give some usage examples of the <code>queueing</code> -package. The reader is assumed to be familiar with Queueing Networks -(although some basic terminology and notation will be given -here). Additional usage examples are embedded in most of the function -files; to display and execute the demos associated with function -<em>fname</em> you can type <samp><span class="command">demo </span><em>fname</em></samp> at the Octave -prompt. For example - -<pre class="example"> <kbd>demo qnclosed</kbd> -</pre> - <p class="noindent">executes all demos (if any) for the <samp><span class="command">qnclosed</span></samp> function. - -<div class="node"> -<a name="Analysis-of-Closed-Networks"></a> -<p><hr> -Next: <a rel="next" accesskey="n" href="#Analysis-of-Open-Networks">Analysis of Open Networks</a>, -Up: <a rel="up" accesskey="u" href="#Getting-Started">Getting Started</a> - -</div> - -<h3 class="section">3.1 Analysis of Closed Networks</h3> - -<p>Let us consider a simple closed network with K=3 service -centers. Each center is of type M/M/1–FCFS. We denote with -S_i the average service time at center i, i=1, 2, -3. Let S_1 = 1.0, S_2 = 2.0 and S_3 = 0.8. The -routing of jobs within the network is described with a <em>routing -probability matrix</em> P. Specifically, a request completing -service at center i is enqueued at center j with -probability P_i, j. Let us assume the following routing -probability matrix: - -<pre class="example"> [ 0 0.3 0.7 ] - P = [ 1 0 0 ] - [ 1 0 0 ] -</pre> - <p>For example, according to matric P a job completing service at -center 1 is routed to center 2 with probability 0.3, and is routed to -center 3 with probability 0.7. - - <p>The network above can be analyzed with the <samp><span class="command">qnclosed</span></samp> -function; if there is just a single class of requests, as in the -example above, <samp><span class="command">qnclosed</span></samp> calls <samp><span class="command">qnclosedsinglemva</span></samp> -which implements the Mean Value Analysys (MVA) algorithm for -single-class, product-form network. - - <p><samp><span class="command">qnclosed</span></samp> requires the following parameters: - - <dl> -<dt><var>N</var><dd>Number of requests in the network (since we are considering a closed -network, the number of requests is fixed) - - <br><dt><var>S</var><dd>Array of average service times at the centers: <var>S</var><code>(k)</code> is -the average service time at center k. - - <br><dt><var>V</var><dd>Array of visit ratios: <var>V</var><code>(k)</code> is the average number of -visits to center k. - - </dl> - - <p>As can be seen, we must compute the <em>visit ratios</em> (or visit -counts) V_k for each center k. The visit counts satisfy -the following equations: - -<pre class="example"> V_j = sum_i V_i P_ij -</pre> - <p>We can compute V_k from the routing probability matrix -P_i, j using the <samp><span class="command">qnvisits</span></samp> function: - -<pre class="example"> <kbd>P = [0 0.3 0.7; 1 0 0; 1 0 0];</kbd> - <kbd>V = qnvisits(P)</kbd> - ⇒ V = 1.00000 0.30000 0.70000 -</pre> - <p>We can check that the computed values satisfy the above equation by -evaluating the following expression: - -<pre class="example"> <kbd>V*P</kbd> - ⇒ ans = 1.00000 0.30000 0.70000 -</pre> - <p class="noindent">which is equal to V. -Hence, we can analyze the network for a given population size N -(for example, N=10) as follows: - -<pre class="example"> <kbd>N = 10;</kbd> - <kbd>S = [1 2 0.8];</kbd> - <kbd>P = [0 0.3 0.7; 1 0 0; 1 0 0];</kbd> - <kbd>V = qnvisits(P);</kbd> - <kbd>[U R Q X] = qnclosed( N, S, V )</kbd> - ⇒ U = 0.99139 0.59483 0.55518 - ⇒ R = 7.4360 4.7531 1.7500 - ⇒ Q = 7.3719 1.4136 1.2144 - ⇒ X = 0.99139 0.29742 0.69397 -</pre> - <p>The output of <samp><span class="command">qnclosed</span></samp> includes the vector of utilizations -U_k at center k, response time R_k, average -number of customers Q_k and throughput X_k. In our -example, the throughput of center 1 is X_1 = 0.99139, and the -average number of requests in center 3 is Q_3 = 1.2144. The -utilization of center 1 is U_1 = 0.99139, which is the higher -value among the service centers. Tus, center 1 is the <em>bottleneck -device</em>. - - <p>This network can also be analyzed with the <samp><span class="command">qnsolve</span></samp> -function. <samp><span class="command">qnsolve</span></samp> can handle open, closed or mixed networks, -and allows the network to be described in a very flexible way. First, -let <var>Q1</var>, <var>Q2</var> and <var>Q3</var> be the variables describing the -service centers. Each variable is instantiated with the -<samp><span class="command">qnmknode</span></samp> function. - -<pre class="example"> <kbd>Q1 = qnmknode( "m/m/m-fcfs", 1 );</kbd> - <kbd>Q2 = qnmknode( "m/m/m-fcfs", 2 );</kbd> - <kbd>Q3 = qnmknode( "m/m/m-fcfs", 0.8 );</kbd> -</pre> - <p>The first parameter of <samp><span class="command">qnmknode</span></samp> is a string describing the -type of the node. Here we use <code>"m/m/m-fcfs"</code> to denote a -M/M/m–FCFS center. The second parameter gives the average -service time. An optional third parameter can be used to specify the -number m of service centers. If omitted, it is assumed -m=1 (single-server node). - - <p>Now, the network can be analyzed as follows: - -<pre class="example"> <kbd>N = 10;</kbd> - <kbd>V = [1 0.3 0.7];</kbd> - <kbd>[U R Q X] = qnsolve( "closed", N, { Q1, Q2, Q3 }, V )</kbd> - ⇒ U = 0.99139 0.59483 0.55518 - ⇒ R = 7.4360 4.7531 1.7500 - ⇒ Q = 7.3719 1.4136 1.2144 - ⇒ X = 0.99139 0.29742 0.69397 -</pre> - <p>Of course, we get exactly the same results. Other functions can be used -for closed networks, see <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a>. - -<div class="node"> -<a name="Analysis-of-Open-Networks"></a> -<p><hr> -Previous: <a rel="previous" accesskey="p" href="#Analysis-of-Closed-Networks">Analysis of Closed Networks</a>, -Up: <a rel="up" accesskey="u" href="#Getting-Started">Getting Started</a> - -</div> - -<h3 class="section">3.2 Analysis of Open Networks</h3> - -<p>Open networks can be analyzed in a similar way. Let us consider -an open network with K=3 service centers, and routing -probability matrix as follows: - -<pre class="example"> [ 0 0.3 0.5 ] - P = [ 1 0 0 ] - [ 1 0 0 ] -</pre> - <p>In this network, requests can leave the system from center 1 with -probability (1-(0.3+0.5) = 0.2. We suppose that external jobs -arrive at center 1 with rate \lambda_1 = 0.15; there are no -arrivals at centers 2 and 3. - - <p>Similarly to closed networks, we first need to compute the visit -counts V_k to center k. Again, we use the -<samp><span class="command">qnvisits</span></samp> function as follows: - -<pre class="example"> <kbd>P = [0 0.3 0.5; 1 0 0; 1 0 0];</kbd> - <kbd>lambda = [0.15 0 0];</kbd> - <kbd>V = qnvisits(P, lambda)</kbd> - ⇒ V = 5.00000 1.50000 2.50000 -</pre> - <p class="noindent">where <var>lambda</var><code>(k)</code> is the arrival rate at center k, -and <var>P</var> is the routing matrix. The visit counts V_k for -open networks satisfy the following equation: - -<pre class="example"> V_j = sum_i V_i P_ij -</pre> - <p>where P_0, j is the probability of an external arrival to -center j. This can be computed as: - - <p>Assuming the same service times as in the previous example, the -network can be analyzed with the <samp><span class="command">qnopen</span></samp> function, as -follows: - -<pre class="example"> <kbd>S = [1 2 0.8];</kbd> - <kbd>[U R Q X] = qnopen( sum(lambda), S, V )</kbd> - ⇒ U = 0.75000 0.45000 0.30000 - ⇒ R = 4.0000 3.6364 1.1429 - ⇒ Q = 3.00000 0.81818 0.42857 - ⇒ X = 0.75000 0.22500 0.37500 -</pre> - <p>The first parameter of the <samp><span class="command">qnopen</span></samp> function is the (scalar) -aggregate arrival rate. - - <p>Again, it is possible to use the <samp><span class="command">qnsolve</span></samp> high-level function: - -<pre class="example"> <kbd>Q1 = qnmknode( "m/m/m-fcfs", 1 );</kbd> - <kbd>Q2 = qnmknode( "m/m/m-fcfs", 2 );</kbd> - <kbd>Q3 = qnmknode( "m/m/m-fcfs", 0.8 );</kbd> - <kbd>lambda = [0.15 0 0];</kbd> - <kbd>[U R Q X] = qnsolve( "open", sum(lambda), { Q1, Q2, Q3 }, V )</kbd> - ⇒ U = 0.75000 0.45000 0.30000 - ⇒ R = 4.0000 3.6364 1.1429 - ⇒ Q = 3.00000 0.81818 0.42857 - ⇒ X = 0.75000 0.22500 0.37500 -</pre> - <!-- @node Markov Chains Analysis --> -<!-- @section Markov Chains Analysis --> -<!-- @subsection Discrete-Time Markov Chains --> -<!-- (TODO) --> -<!-- @subsection Continuous-Time Markov Chains --> -<!-- (TODO) --> -<!-- This file has been automatically generated from markovchains.txi --> + <!-- This file has been automatically generated from markovchains.txi --> <!-- by proc.m. Do not edit this file, all changes will be lost --> <!-- *- texinfo -*- --> <!-- Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla --> @@ -857,12 +614,12 @@ <a name="Markov-Chains"></a> <p><hr> Next: <a rel="next" accesskey="n" href="#Single-Station-Queueing-Systems">Single Station Queueing Systems</a>, -Previous: <a rel="previous" accesskey="p" href="#Getting-Started">Getting Started</a>, +Previous: <a rel="previous" accesskey="p" href="#Installation">Installation</a>, Up: <a rel="up" accesskey="u" href="#Top">Top</a> </div> -<h2 class="chapter">4 Markov Chains</h2> +<h2 class="chapter">3 Markov Chains</h2> <ul class="menu"> <li><a accesskey="1" href="#Discrete_002dTime-Markov-Chains">Discrete-Time Markov Chains</a> @@ -878,7 +635,7 @@ </div> -<h3 class="section">4.1 Discrete-Time Markov Chains</h3> +<h3 class="section">3.1 Discrete-Time Markov Chains</h3> <p>Let X_0, X_1, <small class="dots">...</small>, X_n, <small class="dots">...</small> be a sequence of random variables defined over a discete state space 0, 1, 2, @@ -905,6 +662,8 @@ following two properties: (1) P_i, j ≥ 0 for all i, j, and (2) \sum_j=1^N P_i,j = 1 for all i + <p><a name="doc_002ddtmc_005fcheck_005fP"></a> + <div class="defun"> — Function File: [<var>r</var> <var>err</var>] = <b>dtmc_check_P</b> (<var>P</var>)<var><a name="index-dtmc_005fcheck_005fP-1"></a></var><br> <blockquote> @@ -934,7 +693,7 @@ </div> -<h4 class="subsection">4.1.1 State occupancy probabilities</h4> +<h4 class="subsection">3.1.1 State occupancy probabilities</h4> <p>We denote with \bf \pi(n) = \left(\pi_1(n), \pi_2(n), <small class="dots">...</small>, \pi_N(n) \right) the <em>state occupancy probability vector</em> at @@ -962,6 +721,8 @@ <p class="noindent">where \bf 1 is the row vector of ones, and ( \cdot )^T the transpose operator. + <p><a name="doc_002ddtmc"></a> + <div class="defun"> — Function File: <var>p</var> = <b>dtmc</b> (<var>P</var>)<var><a name="index-dtmc-3"></a></var><br> — Function File: <var>p</var> = <b>dtmc</b> (<var>P, n, p0</var>)<var><a name="index-dtmc-4"></a></var><br> @@ -1008,8 +769,8 @@ <p class="noindent"><strong>EXAMPLE</strong> - <p>This example is from [GrSn97]. Let us consider a maze with nine rooms, -as shown in the following figure + <p>This example is from <a href="#GrSn97">GrSn97</a>. Let us consider a maze with nine +rooms, as shown in the following figure <pre class="example"> +-----+-----+-----+ | | | | @@ -1074,7 +835,9 @@ </div> -<h4 class="subsection">4.1.2 Birth-death process</h4> +<h4 class="subsection">3.1.2 Birth-death process</h4> + +<p><a name="doc_002ddtmc_005fbd"></a> <div class="defun"> — Function File: <var>P</var> = <b>dtmc_bd</b> (<var>b, d</var>)<var><a name="index-dtmc_005fbd-11"></a></var><br> @@ -1112,7 +875,7 @@ </div> -<h4 class="subsection">4.1.3 Expected Number of Visits</h4> +<h4 class="subsection">3.1.3 Expected Number of Visits</h4> <p>Given a N state discrete-time Markov chain with transition matrix \bf P and an integer n ≥ 0, we let @@ -1149,6 +912,8 @@ to the size of \bf P (filling missing entries with zeros), we have that, for absorbing chains \bf L = \bf \pi(0)\bf N. + <p><a name="doc_002ddtmc_005fexps"></a> + <div class="defun"> — Function File: <var>L</var> = <b>dtmc_exps</b> (<var>P, n, p0</var>)<var><a name="index-dtmc_005fexps-14"></a></var><br> — Function File: <var>L</var> = <b>dtmc_exps</b> (<var>P, p0</var>)<var><a name="index-dtmc_005fexps-15"></a></var><br> @@ -1199,7 +964,9 @@ </div> -<h4 class="subsection">4.1.4 Time-averaged expected sojourn times</h4> +<h4 class="subsection">3.1.4 Time-averaged expected sojourn times</h4> + +<p><a name="doc_002ddtmc_005ftaexps"></a> <div class="defun"> — Function File: <var>L</var> = <b>dtmc_exps</b> (<var>P, n, p0</var>)<var><a name="index-dtmc_005fexps-17"></a></var><br> @@ -1238,7 +1005,7 @@ </dl> - </blockquote></div> + </blockquote></div> <div class="node"> <a name="Mean-time-to-absorption-(DTMC)"></a> @@ -1250,7 +1017,7 @@ </div> -<h4 class="subsection">4.1.5 Mean Time to Absorption</h4> +<h4 class="subsection">3.1.5 Mean Time to Absorption</h4> <p>The <em>mean time to absorption</em> is defined as the average number of transitions which are required to reach an absorbing state, starting @@ -1271,7 +1038,9 @@ <pre class="example"> B = N R </pre> - <div class="defun"> + <p><a name="doc_002ddtmc_005fmtta"></a> + +<div class="defun"> — Function File: [<var>t</var> <var>N</var> <var>B</var>] = <b>dtmc_mtta</b> (<var>P</var>)<var><a name="index-dtmc_005fmtta-20"></a></var><br> — Function File: [<var>t</var> <var>N</var> <var>B</var>] = <b>dtmc_mtta</b> (<var>P, p0</var>)<var><a name="index-dtmc_005fmtta-21"></a></var><br> <blockquote> @@ -1335,7 +1104,7 @@ </div> -<h4 class="subsection">4.1.6 First Passage Times</h4> +<h4 class="subsection">3.1.6 First Passage Times</h4> <p>The First Passage Time M_i, j is the average number of transitions needed to visit state j for the first time, @@ -1372,7 +1141,9 @@ r_i = ----- \pi_i </pre> - <div class="defun"> + <p><a name="doc_002ddtmc_005ffpt"></a> + +<div class="defun"> — Function File: <var>M</var> = <b>dtmc_fpt</b> (<var>P</var>)<var><a name="index-dtmc_005ffpt-25"></a></var><br> <blockquote> <p><a name="index-First-passage-times-26"></a><a name="index-Mean-recurrence-times-27"></a> @@ -1417,7 +1188,7 @@ </div> -<h3 class="section">4.2 Continuous-Time Markov Chains</h3> +<h3 class="section">3.2 Continuous-Time Markov Chains</h3> <p>A stochastic process {X(t), t ≥ 0} is a continuous-time Markov chain if, for all integers n, and for any sequence @@ -1433,6 +1204,8 @@ satisfy the property that, for all i, \sum_j=1^N Q_i, j = 0. + <p><a name="doc_002dctmc_005fcheck_005fQ"></a> + <div class="defun"> — Function File: [<var>result</var> <var>err</var>] = <b>ctmc_check_Q</b> (<var>Q</var>)<var><a name="index-ctmc_005fcheck_005fQ-28"></a></var><br> <blockquote> @@ -1462,7 +1235,7 @@ </div> -<h4 class="subsection">4.2.1 State occupancy probabilities</h4> +<h4 class="subsection">3.2.1 State occupancy probabilities</h4> <p>Similarly to the discrete case, we denote with \bf \pi(t) = (\pi_1(t), \pi_2(t), <small class="dots">...</small>, \pi_N(t) ) the <em>state occupancy @@ -1489,7 +1262,9 @@ | \pi 1^T = 1 \ </pre> - <div class="defun"> + <p><a name="doc_002dctmc"></a> + +<div class="defun"> — Function File: <var>p</var> = <b>ctmc</b> (<var>Q</var>)<var><a name="index-ctmc-30"></a></var><br> — Function File: <var>p</var> = <b>ctmc</b> (<var>Q, t. p0</var>)<var><a name="index-ctmc-31"></a></var><br> <blockquote> @@ -1556,7 +1331,9 @@ </div> -<h4 class="subsection">4.2.2 Birth-Death Process</h4> +<h4 class="subsection">3.2.2 Birth-Death Process</h4> + +<p><a name="doc_002dctmc_005fbd"></a> <div class="defun"> — Function File: <var>Q</var> = <b>ctmc_bd</b> (<var>b, d</var>)<var><a name="index-ctmc_005fbd-36"></a></var><br> @@ -1593,7 +1370,7 @@ </div> -<h4 class="subsection">4.2.3 Expected Sojourn Times</h4> +<h4 class="subsection">3.2.3 Expected Sojourn Times</h4> <p>Given a N state continuous-time Markov Chain with infinitesimal generator matrix \bf Q, we define the vector \bf L(t) = @@ -1618,6 +1395,8 @@ the state occupancy probability at time t; \exp(\bf Qt) is the matrix exponential of \bf Qt. + <p><a name="doc_002dctmc_005fexps"></a> + <div class="defun"> — Function File: <var>L</var> = <b>ctmc_exps</b> (<var>Q, t, p </var>)<var><a name="index-ctmc_005fexps-39"></a></var><br> — Function File: <var>L</var> = <b>ctmc_exps</b> (<var>Q, p</var>)<var><a name="index-ctmc_005fexps-40"></a></var><br> @@ -1697,7 +1476,9 @@ </div> -<h4 class="subsection">4.2.4 Time-Averaged Expected Sojourn Times</h4> +<h4 class="subsection">3.2.4 Time-Averaged Expected Sojourn Times</h4> + +<p><a name="doc_002dctmc_005ftaexps"></a> <div class="defun"> — Function File: <var>M</var> = <b>ctmc_taexps</b> (<var>Q, t, p</var>)<var><a name="index-ctmc_005ftaexps-43"></a></var><br> @@ -1736,7 +1517,7 @@ </dl> - </blockquote></div> + </blockquote></div> <p class="noindent"><strong>EXAMPLE</strong> @@ -1772,7 +1553,7 @@ </div> -<h4 class="subsection">4.2.5 Mean Time to Absorption</h4> +<h4 class="subsection">3.2.5 Mean Time to Absorption</h4> <p>If we consider a Markov Chain with absorbing states, it is possible to define the <em>expected time to absorption</em> as the expected time @@ -1789,6 +1570,8 @@ state occupancy probability at time 0, restricted to states in A. + <p><a name="doc_002dctmc_005fmtta"></a> + <div class="defun"> — Function File: <var>t</var> = <b>ctmc_mtta</b> (<var>Q, p</var>)<var><a name="index-ctmc_005fmtta-47"></a></var><br> <blockquote> @@ -1870,7 +1653,9 @@ </div> -<h4 class="subsection">4.2.6 First Passage Times</h4> +<h4 class="subsection">3.2.6 First Passage Times</h4> + +<p><a name="doc_002dctmc_005ffpt"></a> <div class="defun"> — Function File: <var>M</var> = <b>ctmc_fpt</b> (<var>Q</var>)<var><a name="index-ctmc_005ffpt-54"></a></var><br> @@ -1911,7 +1696,7 @@ </pre> <strong>See also:</strong> dtmc_fpt. - </blockquote></div> + </blockquote></div> <!-- This file has been automatically generated from singlestation.txi --> <!-- by proc.m. Do not edit this file, all changes will be lost --> @@ -1939,7 +1724,7 @@ </div> -<h2 class="chapter">5 Single Station Queueing Systems</h2> +<h2 class="chapter">4 Single Station Queueing Systems</h2> <p>Single Station Queueing Systems contain a single station, and are thus quite easy to analyze. The <code>queueing</code> package contains functions @@ -1972,7 +1757,7 @@ </div> -<h3 class="section">5.1 The M/M/1 System</h3> +<h3 class="section">4.1 The M/M/1 System</h3> <p>The M/M/1 system is made of a single server connected to an unlimited FCFS queue. The mean arrival rate is Poisson with arrival @@ -2040,7 +1825,7 @@ </div> -<h3 class="section">5.2 The M/M/m System</h3> +<h3 class="section">4.2 The M/M/m System</h3> <p>The M/M/m system is similar to the M/M/1 system, except that there are m \geq 1 identical servers connected to a single @@ -2119,7 +1904,7 @@ </div> -<h3 class="section">5.3 The M/M/inf System</h3> +<h3 class="section">4.3 The M/M/inf System</h3> <p>The M/M/\infty system is similar to the M/M/m system, except that there are infinitely many identical servers (that is, @@ -2194,7 +1979,7 @@ </div> -<h3 class="section">5.4 The M/M/1/K System</h3> +<h3 class="section">4.4 The M/M/1/K System</h3> <p>In a M/M/1/K finite capacity system there can be at most k jobs at any time. If a new request tries to join the system @@ -2263,7 +2048,7 @@ </div> -<h3 class="section">5.5 The M/M/m/K System</h3> +<h3 class="section">4.5 The M/M/m/K System</h3> <p>The M/M/m/K finite capacity system is similar to the M/M/1/k system except that the number of servers is m, @@ -2343,7 +2128,7 @@ </div> -<h3 class="section">5.6 The Asymmetric M/M/m System</h3> +<h3 class="section">4.6 The Asymmetric M/M/m System</h3> <p>The Asymmetric M/M/m system contains m servers connected to a single queue. Differently from the M/M/m system, in the @@ -2410,7 +2195,7 @@ </div> -<h3 class="section">5.7 The M/G/1 System</h3> +<h3 class="section">4.7 The M/G/1 System</h3> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>] = <b>qnmg1</b> (<var>lambda, xavg, x2nd</var>)<var><a name="index-qnmg1-91"></a></var><br> @@ -2467,7 +2252,7 @@ </div> -<h3 class="section">5.8 The M/H_m/1 System</h3> +<h3 class="section">4.8 The M/H_m/1 System</h3> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>] = <b>qnmh1</b> (<var>lambda, mu, alpha</var>)<var><a name="index-qnmh1-93"></a></var><br> @@ -2544,13 +2329,13 @@ </div> -<h2 class="chapter">6 Queueing Networks</h2> +<h2 class="chapter">5 Queueing Networks</h2> <ul class="menu"> <li><a accesskey="1" href="#Introduction-to-QNs">Introduction to QNs</a>: A brief introduction to Queueing Networks. -<li><a accesskey="2" href="#Generic-Algorithms">Generic Algorithms</a>: High-level functions for QN analysis -<li><a accesskey="3" href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a>: Functions to analyze product-form QNs -<li><a accesskey="4" href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a>: Functions to analyze non product-form QNs +<li><a accesskey="2" href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a>: Functions to analyze product-form QNs +<li><a accesskey="3" href="#Algorithms-for-non-Product_002dForm-QNs">Algorithms for non Product-Form QNs</a>: Functions to analyze non product-form QNs +<li><a accesskey="4" href="#Generic-Algorithms">Generic Algorithms</a>: High-level functions for QN analysis <li><a accesskey="5" href="#Bounds-on-performance">Bounds on performance</a>: Functions to compute performance bounds <li><a accesskey="6" href="#Utility-functions">Utility functions</a>: Utility functions to compute miscellaneous quantities </ul> @@ -2560,26 +2345,25 @@ <div class="node"> <a name="Introduction-to-QNs"></a> <p><hr> -Next: <a rel="next" accesskey="n" href="#Generic-Algorithms">Generic Algorithms</a>, +Next: <a rel="next" accesskey="n" href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a>, Up: <a rel="up" accesskey="u" href="#Queueing-Networks">Queueing Networks</a> </div> -<h3 class="section">6.1 Introduction to QNs</h3> +<h3 class="section">5.1 Introduction to QNs</h3> <p>Queueing Networks (QN) are a very simple yet powerful modeling tool -which is used to analyze many kind of systems. In its simplest form, a -QN is made of K service centers. Each service center i -has a queue, which is connected to m_i (generally identical) -<em>servers</em>. Customers (or requests) arrive at the service center, -and join the queue if there is a slot available. Then, requests are -served according to a (de)queueing policy. After service completes, -the requests leave the service center. - - <p>The service centers for which m_i = \infty are called -<em>delay centers</em> or <em>infinite servers</em>. If a service center -has infinite servers, of course each new request will find one server -available, so there will never be queueing. +which can be used to analyze many kind of systems. In its simplest +form, a QN is made of K service centers. Each center k +has a queue, which is connected to m_k (generally identical) +<em>servers</em>. Arriving customers (requests) join the queue if there +is a slot available. Then, 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. + + <p>Service centers for which m_k = \infty are called <em>delay +centers</em> or <em>infinite servers</em>. In this kind of centers, every +request always finds one available server, so queueing never occurs. <p>Requests join the queue according to a <em>queueing policy</em>, such as: @@ -2590,74 +2374,72 @@ <br><dt><strong>PS</strong><dd>Processor Sharing - <br><dt><strong>IS</strong><dd>Infinite Server, there is an infinite number of identical servers so -that each request always finds a server available, and there is no -queueing + <br><dt><strong>IS</strong><dd>Infinite Server (for which m_k = \infty). </dl> - <p>A population of <em>requests</em> or <em>customers</em> arrives to the -system system, requesting service to the service centers. The request -population may be <em>open</em> or <em>closed</em>. In open systems there -is an infinite population of requests. New customers arrive from -outside the system, and eventually leave the system. In closed systems -there is a fixed population of request which continuously interacts -with the system. - - <p>There might be a single class of requests, meaning that all requests -behave in the same way (e.g., they spend the same average time on each -particular server), or there might be multiple classes of requests. - -<h4 class="subsection">6.1.1 Single class models</h4> - -<p>In single class models, all requests are indistinguishable and belong to -the same class. This means that every request has the same average + <p>Queueing models can be <em>open</em> or <em>closed</em>. In open models +there is an infinite population of requests; new customers are +generated outside the system, and eventually leave the system. In +closed systems there is a fixed population of request. + + <p>Queueing models can have a single request class, meaning that all +requests behave in the same way (e.g., they spend the same average +time on each particular server). In multiclass models there are +multiple request classes, each one with its own +parameters. Furthermore, in multiclass models there can be open and +closed classes of requests within the same system. + +<h4 class="subsection">5.1.1 Single class models</h4> + +<p>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. <p class="noindent"><strong>Model Inputs</strong> <dl> -<dt>\lambda_i<dd>External arrival rate to service center i. +<dt>\lambda_k<dd>External arrival rate to service center k. <br><dt>\lambda<dd>Overall external arrival rate to the whole system: \lambda = -\sum_i \lambda_i. - - <br><dt>S_i<dd>Average service time. S_i is the average service time on service -center i. In other words, S_i is the average time from the +\sum_k \lambda_k. + + <br><dt>S_k<dd>Average service time. S_k is the average service time on service +center k. In other words, S_k is the average time from the instant in which a request is extracted from the queue and starts being service, and the instant at which service finishes and the request moves to another queue (or exits the system). - <br><dt>P_i, j<dd>Routing probability matrix. \bf P = P_i, j is a K + <br><dt>P_i, j<dd>Routing probability matrix. \bf P = [P_i, j] is a K \times K matrix such that P_i, j is the probability that a request completing service at server i will move directly to server j, The probability that a request leaves the system after service at service center i is 1-\sum_j=1^K P_i, j. - <br><dt>V_i<dd>Average number of visits. V_i is the average number of visits to -the service center i. This quantity will be described shortly. + <br><dt>V_k<dd>Average number of visits. V_k is the average number of visits to +the service center k. This quantity will be described shortly. </dl> <p class="noindent"><strong>Model Outputs</strong> <dl> -<dt>U_i<dd>Service center utilization. U_i is the utilization of service -center i. The utilization is defined as the fraction of time in +<dt>U_k<dd>Service center utilization. U_k is the utilization of service +center k. The utilization is defined as the fraction of time in which the resource is busy (i.e., the server is processing requests). - <br><dt>R_i<dd>Average response time. R_i is the average response time of -service center i. The average response time is defined as the + <br><dt>R_k<dd>Average response time. R_k is the average response time of +service center 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. - <br><dt>Q_i<dd>Average number of customers. Q_i is the average number of -requests in service center i. This includes both the requests in + <br><dt>Q_k<dd>Average number of customers. Q_k is the average number of +requests in service center k. This includes both the requests in the queue, and the request being served. - <br><dt>X_i<dd>Throughput. X_i is the throughput of service center i. + <br><dt>X_k<dd>Throughput. X_k is the throughput of service center k. The throughput is defined as the ratio of job completions (i.e., average number of jobs completed over a fixed interval of time). @@ -2705,7 +2487,7 @@ i=1 </pre> - <h4 class="subsection">6.1.2 Multiple class models</h4> + <h4 class="subsection">5.1.2 Multiple class models</h4> <p>In multiple class QN models, we assume that there exist C different classes of requests. Each request from class c spends @@ -2718,7 +2500,7 @@ class c requests in the system. <p>The transition probability matrix for these kind of networks will be a -C \times K \times C \times K matrix \bf P = P_r, i, s, j +C \times K \times C \times K matrix \bf P = [P_r, i, s, j] such that P_r, i, s, j is the probability that a class r request which completes service at center i will join server j as a class s request. @@ -2729,41 +2511,41 @@ <p class="noindent"><strong>Model Inputs</strong> <dl> -<dt>\lambda_c, i<dd>External arrival rate of class-c requests to service center i - - <br><dt>\lambda<dd>Overall external arrival rate to the whole system: \lambda = \sum_c \sum_i \lambda_c, i - - <br><dt>S_c, i<dd>Average service time. S_c, i is the average service time on -service center i for class c requests. - - <br><dt>P_r, i, s, j<dd>Routing probability matrix. \bf P = P_r, i, s, j is a C +<dt>\lambda_c, k<dd>External arrival rate of class-c requests to service center k + + <br><dt>\lambda<dd>Overall external arrival rate to the whole system: \lambda = \sum_c \sum_k \lambda_c, k + + <br><dt>S_c, k<dd>Average service time. S_c, k is the average service time on +service center k for class c requests. + + <br><dt>P_r, i, s, j<dd>Routing probability matrix. \bf P = [P_r, i, s, j] is a C \times K \times C \times K matrix such that P_r, i, s, j is the probability that a class r request which completes service at server i will move to server j as a class s request. - <br><dt>V_c, i<dd>Average number of visits. V_c, i is the average number of visits -of class c requests to the service center i. + <br><dt>V_c, k<dd>Average number of visits. V_c, k is the average number of visits +of class c requests to center k. </dl> <p class="noindent"><strong>Model Outputs</strong> <dl> -<dt>U_c, i<dd>Utilization of service center i by class c requests. The +<dt>U_c, k<dd>Utilization of service center k by class c requests. The utilization is defined as the fraction of time in which the resource is busy (i.e., the server is processing requests). - <br><dt>R_c, i<dd>Average response time experienced by class c requests on service -center i. The average response time is defined as the average + <br><dt>R_c, k<dd>Average response time experienced by class c requests on service +center 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. - <br><dt>Q_c, i<dd>Average number of class c requests on service center -i. This includes both the requests in the queue, and the request + <br><dt>Q_c, k<dd>Average number of class c requests on service center +k. This includes both the requests in the queue, and the request being served. - <br><dt>X_c, i<dd>Throughput of service center i for class c requests. The + <br><dt>X_c, k<dd>Throughput of service center k for class c requests. The throughput is defined as the rate of completion of class c requests. @@ -2772,8 +2554,8 @@ <p class="noindent">It is possible to define aggregate performance measures as follows: <dl> -<dt>U_i<dd>Utilization of service center i: -<code>Ui = sum(U,1);</code> +<dt>U_k<dd>Utilization of service center k: +<code>Uk = sum(U,k);</code> <br><dt>R_c<dd>System response time for class c requests: <code>Rc = sum( V.*R, 1 );</code> @@ -2802,224 +2584,155 @@ \sum_s \sum_j \lambda_s, j is the overall external arrival rate to the whole system, then P_0, s, j = \lambda_s, j / \lambda. -<div class="node"> -<a name="Generic-Algorithms"></a> -<p><hr> -Next: <a rel="next" accesskey="n" href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a>, -Previous: <a rel="previous" accesskey="p" href="#Introduction-to-QNs">Introduction to QNs</a>, -Up: <a rel="up" accesskey="u" href="#Queueing-Networks">Queueing Networks</a> - -</div> - -<h3 class="section">6.2 Generic Algorithms</h3> - -<p>The <code>queueing</code> package provides a couple of high-level functions -for defining and solving QN models. These functions can be used to -define a open or closed QN model (with single or multiple job -classes), with arbitrary configuration and queueing disciplines. At -the moment only product-form networks can be solved, See <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a>. - - <p>The network is defined by two parameters. The first one is the list of -nodes, encoded as an Octave <em>cell array</em>. The second parameter is -the visit ration <var>V</var>, which can be either a vector (for -single-class models) or a two-dimensional matrix (for multiple-class -models). - - <p>Individual nodes in the network are structures build using the -<code>qnmknode</code> function. - -<div class="defun"> -— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"m/m/m-fcfs", S</var>)<var><a name="index-qnmknode-96"></a></var><br> -— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"m/m/m-fcfs", S, m</var>)<var><a name="index-qnmknode-97"></a></var><br> -— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"m/m/1-lcfs-pr", S</var>)<var><a name="index-qnmknode-98"></a></var><br> -— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"-/g/1-ps", S</var>)<var><a name="index-qnmknode-99"></a></var><br> -— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"-/g/1-ps", S, s2</var>)<var><a name="index-qnmknode-100"></a></var><br> -— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"-/g/inf", S</var>)<var><a name="index-qnmknode-101"></a></var><br> -— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"-/g/inf", S, s2</var>)<var><a name="index-qnmknode-102"></a></var><br> -<blockquote> - <p>Creates a node; this function can be used together with -<code>qnsolve</code>. 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. - - <p><strong>INPUTS</strong> - - <dl> -<dt><var>S</var><dd>Average service time. S can be either a scalar, a row vector, -a column vector or a two-dimensional matrix. - - <ul> -<li>If S is a scalar, -it is assumed to be a load-independent, class-independent service time. - - <li>If S is a column vector, then <var>S</var><code>(c)</code> is assumed to -the the load-independent service time for class c customers. - - <li>If S is a row vector, then <var>S</var><code>(n)</code> is assumed to be -the class-independent service time at the node, when there are n -requests. - - <li>Finally, if <var>S</var> is a two-dimensional matrix, then -<var>S</var><code>(c,n)</code> is assumed to be the class c service time -when there are n requests at the node. - - </ul> - - <br><dt><var>m</var><dd>Number of identical servers at the node. Default is <var>m</var><code>=1</code>. - - <br><dt><var>s2</var><dd>Squared coefficient of variation for the service time. Default is 1.0. - - </dl> - - <p>The returned struct <var>Q</var> should be considered opaque to the client. - - <!-- The returned struct @var{Q} has the following fields: --> - <!-- @table @var --> - <!-- @item Q.node --> - <!-- (String) type of the node; valid values are @code{"m/m/m-fcfs"}, --> - <!-- @code{"-/g/1-lcfs-pr"}, @code{"-/g/1-ps"} (Processor-Sharing) --> - <!-- and @code{"-/g/inf"} (Infinite Server, or delay center). --> - <!-- @item Q.S --> - <!-- Average service time. If @code{@var{Q}.S} is a vector, then --> - <!-- @code{@var{Q}.S(i)} is the average service time at that node --> - <!-- if there are @math{i} requests. --> - <!-- @item Q.m --> - <!-- Number of identical servers at a @code{"m/m/m-fcfs"}. Default is 1. --> - <!-- @item Q.c --> - <!-- Number of customer classes. Default is 1. --> - <!-- @end table --> - <pre class="sp"> - - </pre> - <strong>See also:</strong> qnsolve. - - </blockquote></div> - - <p>After the network has been defined, it is possible to solve it using -the <code>qnsolve</code> function. Note that this function is somewhat less -efficient than those described in later sections, but -generally easier to use. - -<div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"closed", N, QQ, V</var>)<var><a name="index-qnsolve-103"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"closed", N, QQ, V, Z</var>)<var><a name="index-qnsolve-104"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"open", lambda, QQ, V</var>)<var><a name="index-qnsolve-105"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"mixed", lambda, N, QQ, V</var>)<var><a name="index-qnsolve-106"></a></var><br> -<blockquote> - <p>General evaluator of QN models. Networks can be open, -closed or mixed; single as well as multiclass networks are supported. - - <ul> -<li>For <strong>closed</strong> networks, the following server types are -supported: M/M/m–FCFS, -/G/\infty, -/G/1–LCFS-PR, --/G/1–PS and load-dependent variants. - - <li>For <strong>open</strong> networks, the following server types are supported: -M/M/m–FCFS, -/G/\infty and -/G/1–PS. General -load-dependent nodes are <em>not</em> supported. Multiclass open networks -do not support multiple server M/M/m nodes, but only -single server M/M/1–FCFS. - - <li>For <strong>mixed</strong> networks, the following server types are supported: -M/M/1–FCFS, -/G/\infty and -/G/1–PS. General -load-dependent nodes are <em>not</em> supported. - - </ul> - - <p><strong>INPUTS</strong> - - <dl> -<dt><var>N</var><dd>Number of requests in the system for closed networks. For -single-class networks, <var>N</var> must be a scalar. For multiclass -networks, <var>N</var><code>(c)</code> is the population size of closed class -c. - - <br><dt><var>lambda</var><dd>External arrival rate (scalar) for open networks. For single-class -networks, <var>lambda</var> must be a scalar. For multiclass networks, -<var>lambda</var><code>(c)</code> is the class c overall arrival rate. - - <br><dt><var>QQ</var><dd>List of queues in the network. This must be a cell array -with N elements, such that <var>QQ</var><code>{i}</code> is -a struct produced by the <code>qnmknode</code> function. - - <br><dt><var>Z</var><dd>External delay ("think time") for closed networks. Default 0. - - </dl> - - <p><strong>OUTPUTS</strong> - - <dl> -<dt><var>U</var><dd>If i is a FCFS node, then <var>U</var><code>(i)</code> is the utilization -of service center i. If i is an IS node, then -<var>U</var><code>(i)</code> is the <em>traffic intensity</em> defined as -<var>X</var><code>(i)*</code><var>S</var><code>(i)</code>. - - <br><dt><var>R</var><dd><var>R</var><code>(i)</code> is the average response time of service center i. - - <br><dt><var>Q</var><dd><var>Q</var><code>(i)</code> is the average number of customers in service center -i. - - <br><dt><var>X</var><dd><var>X</var><code>(i)</code> is the throughput of service center i. - - </dl> - - <p>Note that for multiclass networks, the computed results are per-class -utilization, response time, number of customers and throughput: -<var>U</var><code>(c,k)</code>, <var>R</var><code>(c,k)</code>, <var>Q</var><code>(c,k)</code>, -<var>X</var><code>(c,k)</code>, - - </blockquote></div> - -<p class="noindent"><strong>EXAMPLE</strong> - - <p>Let us consider a closed, multiclass network with C=2 classes -and K=3 service center. Let the population be M=(2, 1) -(class 1 has 2 requests, and class 2 has 1 request). The nodes are as -follows: - - <ul> -<li>Node 1 is a 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]</code>. Thus, <var>S</var><code>(1,2) = -0.2</code> means that service time for class 1 customers where there are 2 -requests in 0.2. Note that service times are class-independent; - - <li>Node 2 is a -/G/1–PS node, with service times -S_1, 2 = 0.4 for class 1, and S_2, 2 = 0.6 for class 2 -requests; - - <li>Node 3 is a -/G/\infty node (delay center), with service -times S_1, 3=1 and S_2, 3=2 for class 1 and 2 -respectively. - - </ul> - - <p>After defining the per-class visit count <var>V</var> such that -<var>V</var><code>(c,k)</code> is the visit count of class c requests to -service center k. We can define and solve the model as -follows: - -<pre class="example"><pre class="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 ); +<h4 class="subsection">5.1.3 Closed Network Example</h4> + +<p>We now give a simple example on how the queueing toolbox can be used +to analyze a closed network. Let us consider a simple closed network +with K=3 M/M/1–FCFS centers. We denote with S_k +the average service time at center k, k=1, 2, 3. We use +S_1 = 1.0, S_2 = 2.0 and S_3 = 0.8. The routing +of jobs within the network is described with a <em>routing +probability matrix</em> \bf P. Specifically, a request completing +service at center i is enqueued at center j with +probability P_i, j. We use the following routing matrix: + +<pre class="example"> / 0 0.3 0.7 \ + P = | 1 0 0 | + \ 1 0 0 / +</pre> + <p>The network above can be analyzed with the <samp><span class="command">qnclosed</span></samp> function +see <a href="#doc_002dqnclosed">doc-qnclosed</a>. <samp><span class="command">qnclosed</span></samp> requires the following +parameters: + + <dl> +<dt><var>N</var><dd>Number of requests in the network (since we are considering a closed +network, the number of requests is fixed) + + <br><dt><var>S</var><dd>Array of average service times at the centers: <var>S</var><code>(k)</code> is +the average service time at center k. + + <br><dt><var>V</var><dd>Array of visit ratios: <var>V</var><code>(k)</code> is the average number of +visits to center k. + + </dl> + + <p>We can compute V_k from the routing probability matrix +P_i, j using the <samp><span class="command">qnvisits</span></samp> function +see <a href="#doc_002dqnvisits">doc-qnvisits</a>. We can analyze the network for a given +population size N (for example, N=10) as follows: + +<pre class="example"> <kbd>N = 10;</kbd> + <kbd>S = [1 2 0.8];</kbd> + <kbd>P = [0 0.3 0.7; 1 0 0; 1 0 0];</kbd> + <kbd>V = qnvisits(P);</kbd> + <kbd>[U R Q X] = qnclosed( N, S, V )</kbd> + ⇒ U = 0.99139 0.59483 0.55518 + ⇒ R = 7.4360 4.7531 1.7500 + ⇒ Q = 7.3719 1.4136 1.2144 + ⇒ X = 0.99139 0.29742 0.69397 +</pre> + <p>The output of <samp><span class="command">qnclosed</span></samp> includes the vector of utilizations +U_k at center k, response time R_k, average +number of customers Q_k and throughput X_k. In our +example, the throughput of center 1 is X_1 = 0.99139, and the +average number of requests in center 3 is Q_3 = 1.2144. The +utilization of center 1 is U_1 = 0.99139, which is the higher +value among the service centers. Tus, center 1 is the <em>bottleneck +device</em>. + + <p>This network can also be analyzed with the <samp><span class="command">qnsolve</span></samp> function +see <a href="#doc_002dqnsolve">doc-qnsolve</a>. <samp><span class="command">qnsolve</span></samp> can handle open, closed or +mixed networks, and allows the network to be described in a very +flexible way. First, let <var>Q1</var>, <var>Q2</var> and <var>Q3</var> be the +variables describing the service centers. Each variable is +instantiated with the <samp><span class="command">qnmknode</span></samp> function. + +<pre class="example"> <kbd>Q1 = qnmknode( "m/m/m-fcfs", 1 );</kbd> + <kbd>Q2 = qnmknode( "m/m/m-fcfs", 2 );</kbd> + <kbd>Q3 = qnmknode( "m/m/m-fcfs", 0.8 );</kbd> </pre> + <p>The first parameter of <samp><span class="command">qnmknode</span></samp> is a string describing the +type of the node. Here we use <code>"m/m/m-fcfs"</code> to denote a +M/M/m–FCFS center. The second parameter gives the average +service time. An optional third parameter can be used to specify the +number m of service centers. If omitted, it is assumed +m=1 (single-server node). + + <p>Now, the network can be analyzed as follows: + +<pre class="example"> <kbd>N = 10;</kbd> + <kbd>V = [1 0.3 0.7];</kbd> + <kbd>[U R Q X] = qnsolve( "closed", N, { Q1, Q2, Q3 }, V )</kbd> + ⇒ U = 0.99139 0.59483 0.55518 + ⇒ R = 7.4360 4.7531 1.7500 + ⇒ Q = 7.3719 1.4136 1.2144 + ⇒ X = 0.99139 0.29742 0.69397 +</pre> + <p>Of course, we get exactly the same results. Other functions can be used +for closed networks, see <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a>. + +<h4 class="subsection">5.1.4 Open Network Example</h4> + +<p>Open networks can be analyzed in a similar way. Let us consider +an open network with K=3 service centers, and routing +probability matrix as follows: + +<pre class="example"> / 0 0.3 0.5 \ + P = ! 1 0 0 | + \ 1 0 0 / +</pre> + <p>In this network, requests can leave the system from center 1 with +probability 1-(0.3+0.5) = 0.2. We suppose that external jobs +arrive at center 1 with rate \lambda_1 = 0.15; there are no +arrivals at centers 2 and 3. + + <p>Similarly to closed networks, we first need to compute the visit +counts V_k to center k. Again, we use the +<samp><span class="command">qnvisits</span></samp> function as follows: + +<pre class="example"> <kbd>P = [0 0.3 0.5; 1 0 0; 1 0 0];</kbd> + <kbd>lambda = [0.15 0 0];</kbd> + <kbd>V = qnvisits(P, lambda)</kbd> + ⇒ V = 5.00000 1.50000 2.50000 +</pre> + <p class="noindent">where <var>lambda</var><code>(k)</code> is the arrival rate at center k, +and <var>P</var> is the routing matrix. Assuming the same service times as +in the previous example, the network can be analyzed with the +<samp><span class="command">qnopen</span></samp> function see <a href="#doc_002dqnopen">doc-qnopen</a>, as follows: + +<pre class="example"> <kbd>S = [1 2 0.8];</kbd> + <kbd>[U R Q X] = qnopen( sum(lambda), S, V )</kbd> + ⇒ U = 0.75000 0.45000 0.30000 + ⇒ R = 4.0000 3.6364 1.1429 + ⇒ Q = 3.00000 0.81818 0.42857 + ⇒ X = 0.75000 0.22500 0.37500 +</pre> + <p>The first parameter of the <samp><span class="command">qnopen</span></samp> function is the (scalar) +aggregate arrival rate. + + <p>Again, it is possible to use the <samp><span class="command">qnsolve</span></samp> high-level function: + +<pre class="example"> <kbd>Q1 = qnmknode( "m/m/m-fcfs", 1 );</kbd> + <kbd>Q2 = qnmknode( "m/m/m-fcfs", 2 );</kbd> + <kbd>Q3 = qnmknode( "m/m/m-fcfs", 0.8 );</kbd> + <kbd>lambda = [0.15 0 0];</kbd> + <kbd>[U R Q X] = qnsolve( "open", sum(lambda), { Q1, Q2, Q3 }, V )</kbd> + ⇒ U = 0.75000 0.45000 0.30000 + ⇒ R = 4.0000 3.6364 1.1429 + ⇒ Q = 3.00000 0.81818 0.42857 + ⇒ X = 0.75000 0.22500 0.37500 </pre> <div class="node"> <a name="Algorithms-for-Product-Form-QNs"></a> <a name="Algorithms-for-Product_002dForm-QNs"></a> <p><hr> -Next: <a rel="next" accesskey="n" href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a>, -Previous: <a rel="previous" accesskey="p" href="#Generic-Algorithms">Generic Algorithms</a>, +Next: <a rel="next" accesskey="n" href="#Algorithms-for-non-Product_002dForm-QNs">Algorithms for non Product-Form QNs</a>, +Previous: <a rel="previous" accesskey="p" href="#Introduction-to-QNs">Introduction to QNs</a>, Up: <a rel="up" accesskey="u" href="#Queueing-Networks">Queueing Networks</a> </div> -<h3 class="section">6.3 Algorithms for Product-Form QNs</h3> +<h3 class="section">5.2 Algorithms for Product-Form QNs</h3> <p>Product-form queueing networks fulfill the following assumptions: @@ -3049,7 +2762,7 @@ </ul> <!-- Jackson Networks --> -<h4 class="subsection">6.3.1 Jackson Networks</h4> +<h4 class="subsection">5.2.1 Jackson Networks</h4> <p>Jackson networks satisfy the following conditions: @@ -3082,12 +2795,14 @@ <p class="noindent">where \pi_i(k_i) is the steady-state probability that there are k_i requests at service center i. + <p><a name="doc_002dqnjackson"></a> + <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnjackson</b> (<var>lambda, S, P </var>)<var><a name="index-qnjackson-107"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnjackson</b> (<var>lambda, S, P, m </var>)<var><a name="index-qnjackson-108"></a></var><br> -— Function File: <var>pr</var> = <b>qnjackson</b> (<var>lambda, S, P, m, k</var>)<var><a name="index-qnjackson-109"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnjackson</b> (<var>lambda, S, P </var>)<var><a name="index-qnjackson-96"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnjackson</b> (<var>lambda, S, P, m </var>)<var><a name="index-qnjackson-97"></a></var><br> +— Function File: <var>pr</var> = <b>qnjackson</b> (<var>lambda, S, P, m, k</var>)<var><a name="index-qnjackson-98"></a></var><br> <blockquote> - <p><a name="index-open-network_002c-single-class-110"></a><a name="index-Jackson-network-111"></a> + <p><a name="index-open-network_002c-single-class-99"></a><a name="index-Jackson-network-100"></a> With three or four input parameters, this function computes the steady-state occupancy probabilities for a Jackson network. With five input parameters, this function computes the steady-state probability @@ -3169,9 +2884,9 @@ Performance Evaluation with Computer Science Applications</cite>, Wiley, 1998, pp. 284–287. - <p><a name="index-Bolch_002c-G_002e-112"></a><a name="index-Greiner_002c-S_002e-113"></a><a name="index-de-Meer_002c-H_002e-114"></a><a name="index-Trivedi_002c-K_002e-115"></a> - -<h4 class="subsection">6.3.2 The Convolution Algorithm</h4> + <p><a name="index-Bolch_002c-G_002e-101"></a><a name="index-Greiner_002c-S_002e-102"></a><a name="index-de-Meer_002c-H_002e-103"></a><a name="index-Trivedi_002c-K_002e-104"></a> + +<h4 class="subsection">5.2.2 The Convolution Algorithm</h4> <p>According to the BCMP theorem, the state probability of a closed single class queueing network with K nodes and N requests @@ -3200,11 +2915,13 @@ centers. <!-- The Convolution Algorithm --> + <p><a name="doc_002dqnconvolution"></a> + <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnconvolution</b> (<var>N, S, V</var>)<var><a name="index-qnconvolution-116"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnconvolution</b> (<var>N, S, V, m</var>)<var><a name="index-qnconvolution-117"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnconvolution</b> (<var>N, S, V</var>)<var><a name="index-qnconvolution-105"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnconvolution</b> (<var>N, S, V, m</var>)<var><a name="index-qnconvolution-106"></a></var><br> <blockquote> - <p><a name="index-closed-network-118"></a><a name="index-normalization-constant-119"></a><a name="index-convolution-algorithm-120"></a> + <p><a name="index-closed-network-107"></a><a name="index-normalization-constant-108"></a><a name="index-convolution-algorithm-109"></a> This function implements the <em>convolution algorithm</em> for computing steady-state performance measures of product-form, single-class closed queueing networks. Load-independent service @@ -3297,19 +3014,20 @@ 16, number 9, september 1973, pp. 527–531. <a href="http://doi.acm.org/10.1145/362342.362345">http://doi.acm.org/10.1145/362342.362345</a> - <p><a name="index-Buzen_002c-J_002e-P_002e-121"></a> + <p><a name="index-Buzen_002c-J_002e-P_002e-110"></a> 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</cite>, Wiley, 1998, pp. 313–317. - <p><a name="index-Bolch_002c-G_002e-122"></a><a name="index-Greiner_002c-S_002e-123"></a><a name="index-de-Meer_002c-H_002e-124"></a><a name="index-Trivedi_002c-K_002e-125"></a> + <p><a name="index-Bolch_002c-G_002e-111"></a><a name="index-Greiner_002c-S_002e-112"></a><a name="index-de-Meer_002c-H_002e-113"></a><a name="index-Trivedi_002c-K_002e-114"></a> <!-- Convolution for load-dependent service centers --> +<a name="doc_002dqnconvolutionld"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnconvolutionld</b> (<var>N, S, V</var>)<var><a name="index-qnconvolutionld-126"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnconvolutionld</b> (<var>N, S, V</var>)<var><a name="index-qnconvolutionld-115"></a></var><br> <blockquote> - <p><a name="index-closed-network-127"></a><a name="index-normalization-constant-128"></a><a name="index-convolution-algorithm-129"></a><a name="index-load_002ddependent-service-center-130"></a> + <p><a name="index-closed-network-116"></a><a name="index-normalization-constant-117"></a><a name="index-convolution-algorithm-118"></a><a name="index-load_002ddependent-service-center-119"></a> This function implements the <em>convolution algorithm</em> for product-form, single-class closed queueing networks with general load-dependent service centers. @@ -3369,7 +3087,7 @@ Purdue University, feb, 1981 (revised). <a href="http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-354.pdf">http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-354.pdf</a> - <p><a name="index-Schwetman_002c-H_002e-131"></a> + <p><a name="index-Schwetman_002c-H_002e-120"></a> M. Reiser, H. Kobayashi, <cite>On The Convolution Algorithm for Separable Queueing Networks</cite>, In Proceedings of the 1976 ACM SIGMETRICS Conference on Computer Performance Modeling Measurement and @@ -3377,7 +3095,7 @@ 1976). SIGMETRICS '76. ACM, New York, NY, pp. 109–117. <a href="http://doi.acm.org/10.1145/800200.806187">http://doi.acm.org/10.1145/800200.806187</a> - <p><a name="index-Reiser_002c-M_002e-132"></a><a name="index-Kobayashi_002c-H_002e-133"></a> + <p><a name="index-Reiser_002c-M_002e-121"></a><a name="index-Kobayashi_002c-H_002e-122"></a> 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</cite>, Wiley, @@ -3389,16 +3107,18 @@ function f_i defined in Schwetman, <code>Some Computational Aspects of Queueing Network Models</code>. - <p><a name="index-Bolch_002c-G_002e-134"></a><a name="index-Greiner_002c-S_002e-135"></a><a name="index-de-Meer_002c-H_002e-136"></a><a name="index-Trivedi_002c-K_002e-137"></a> - -<h4 class="subsection">6.3.3 Open networks</h4> + <p><a name="index-Bolch_002c-G_002e-123"></a><a name="index-Greiner_002c-S_002e-124"></a><a name="index-de-Meer_002c-H_002e-125"></a><a name="index-Trivedi_002c-K_002e-126"></a> + +<h4 class="subsection">5.2.3 Open networks</h4> <!-- Open networks with single class --> +<p><a name="doc_002dqnopensingle"></a> + <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopensingle</b> (<var>lambda, S, V</var>)<var><a name="index-qnopensingle-138"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopensingle</b> (<var>lambda, S, V, m</var>)<var><a name="index-qnopensingle-139"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopensingle</b> (<var>lambda, S, V</var>)<var><a name="index-qnopensingle-127"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopensingle</b> (<var>lambda, S, V, m</var>)<var><a name="index-qnopensingle-128"></a></var><br> <blockquote> - <p><a name="index-open-network_002c-single-class-140"></a><a name="index-BCMP-network-141"></a> + <p><a name="index-open-network_002c-single-class-129"></a><a name="index-BCMP-network-130"></a> Analyze open, single class BCMP queueing networks. <p>This function works for a subset of BCMP single-class open networks @@ -3459,7 +3179,7 @@ </pre> <strong>See also:</strong> qnopen,qnclosed,qnvisits. - </blockquote></div> + </blockquote></div> <p>From the results computed by this function, it is possible to derive other quantities of interest as follows: @@ -3493,14 +3213,16 @@ Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications</cite>, Wiley, 1998. - <p><a name="index-Bolch_002c-G_002e-142"></a><a name="index-Greiner_002c-S_002e-143"></a><a name="index-de-Meer_002c-H_002e-144"></a><a name="index-Trivedi_002c-K_002e-145"></a> + <p><a name="index-Bolch_002c-G_002e-131"></a><a name="index-Greiner_002c-S_002e-132"></a><a name="index-de-Meer_002c-H_002e-133"></a><a name="index-Trivedi_002c-K_002e-134"></a> <!-- Open network with multiple classes --> + <p><a name="doc_002dqnopenmulti"></a> + <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopenmulti</b> (<var>lambda, S, V</var>)<var><a name="index-qnopenmulti-146"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopenmulti</b> (<var>lambda, S, V, m</var>)<var><a name="index-qnopenmulti-147"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopenmulti</b> (<var>lambda, S, V</var>)<var><a name="index-qnopenmulti-135"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopenmulti</b> (<var>lambda, S, V, m</var>)<var><a name="index-qnopenmulti-136"></a></var><br> <blockquote> - <p><a name="index-open-network_002c-multiple-classes-148"></a> + <p><a name="index-open-network_002c-multiple-classes-137"></a> Exact analysis of open, multiple-class BCMP networks. The network can be made of <em>single-server</em> queueing centers (FCFS, LCFS-PR or PS) or delay centers (IS). This function assumes a network with @@ -3565,17 +3287,19 @@ 1984. <a href="http://www.cs.washington.edu/homes/lazowska/qsp/">http://www.cs.washington.edu/homes/lazowska/qsp/</a>. In particular, see section 7.4.1 ("Open Model Solution Techniques"). - <p><a name="index-Lazowska_002c-E_002e-D_002e-149"></a><a name="index-Zahorjan_002c-J_002e-150"></a><a name="index-Graham_002c-G_002e-S_002e-151"></a><a name="index-Sevcik_002c-K_002e-C_002e-152"></a> - -<h4 class="subsection">6.3.4 Closed Networks</h4> + <p><a name="index-Lazowska_002c-E_002e-D_002e-138"></a><a name="index-Zahorjan_002c-J_002e-139"></a><a name="index-Graham_002c-G_002e-S_002e-140"></a><a name="index-Sevcik_002c-K_002e-C_002e-141"></a> + +<h4 class="subsection">5.2.4 Closed Networks</h4> <!-- MVA for single class, closed networks --> +<p><a name="doc_002dqnclosedsinglemva"></a> + <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnclosedsinglemva</b> (<var>N, S, V</var>)<var><a name="index-qnclosedsinglemva-153"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnclosedsinglemva</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedsinglemva-154"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnclosedsinglemva</b> (<var>N, S, V, m, Z</var>)<var><a name="index-qnclosedsinglemva-155"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnclosedsinglemva</b> (<var>N, S, V</var>)<var><a name="index-qnclosedsinglemva-142"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnclosedsinglemva</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedsinglemva-143"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnclosedsinglemva</b> (<var>N, S, V, m, Z</var>)<var><a name="index-qnclosedsinglemva-144"></a></var><br> <blockquote> - <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-156"></a><a name="index-closed-network_002c-single-class-157"></a><a name="index-normalization-constant-158"></a> + <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-145"></a><a name="index-closed-network_002c-single-class-146"></a><a name="index-normalization-constant-147"></a> 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 @@ -3649,7 +3373,7 @@ </pre> <strong>See also:</strong> qnclosedsinglemvald. - </blockquote></div> + </blockquote></div> <p>From the results provided by this function, it is possible to derive other quantities of interest as follows: @@ -3678,7 +3402,7 @@ Multichain Queuing Networks</cite>, Journal of the ACM, vol. 27, n. 2, April 1980, pp. 313–322. <a href="http://doi.acm.org/10.1145/322186.322195">http://doi.acm.org/10.1145/322186.322195</a> - <p><a name="index-Reiser_002c-M_002e-159"></a><a name="index-Lavenberg_002c-S_002e-S_002e-160"></a> + <p><a name="index-Reiser_002c-M_002e-148"></a><a name="index-Lavenberg_002c-S_002e-S_002e-149"></a> This implementation is described in R. Jain , <cite>The Art of Computer Systems Performance Analysis</cite>, Wiley, 1991, p. 577. Multi-server nodes <!-- and the computation of @math{G(N)}, --> @@ -3687,14 +3411,15 @@ Performance Evaluation with Computer Science Applications</cite>, Wiley, 1998, Section 8.2.1, "Single Class Queueing Networks". - <p><a name="index-Jain_002c-R_002e-161"></a><a name="index-Bolch_002c-G_002e-162"></a><a name="index-Greiner_002c-S_002e-163"></a><a name="index-de-Meer_002c-H_002e-164"></a><a name="index-Trivedi_002c-K_002e-165"></a> + <p><a name="index-Jain_002c-R_002e-150"></a><a name="index-Bolch_002c-G_002e-151"></a><a name="index-Greiner_002c-S_002e-152"></a><a name="index-de-Meer_002c-H_002e-153"></a><a name="index-Trivedi_002c-K_002e-154"></a> <!-- MVA for single class, closed networks with load dependent servers --> +<a name="doc_002dqnclosedsinglemvald"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvald</b> (<var>N, S, V</var>)<var><a name="index-qnclosedsinglemvald-166"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvald</b> (<var>N, S, V, Z</var>)<var><a name="index-qnclosedsinglemvald-167"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvald</b> (<var>N, S, V</var>)<var><a name="index-qnclosedsinglemvald-155"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvald</b> (<var>N, S, V, Z</var>)<var><a name="index-qnclosedsinglemvald-156"></a></var><br> <blockquote> - <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-168"></a><a name="index-closed-network_002c-single-class-169"></a><a name="index-load_002ddependent-service-center-170"></a> + <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-157"></a><a name="index-closed-network_002c-single-class-158"></a><a name="index-load_002ddependent-service-center-159"></a> Exact MVA algorithm for closed, single class queueing networks with load-dependent service centers. This function supports FCFS, LCFS-PR, PS and IS nodes. For networks with only fixed-rate @@ -3752,14 +3477,15 @@ 1998, Section 8.2.4.1, “Networks with Load-Deèpendent Service: Closed Networks”. - <p><a name="index-Bolch_002c-G_002e-171"></a><a name="index-Greiner_002c-S_002e-172"></a><a name="index-de-Meer_002c-H_002e-173"></a><a name="index-Trivedi_002c-K_002e-174"></a> + <p><a name="index-Bolch_002c-G_002e-160"></a><a name="index-Greiner_002c-S_002e-161"></a><a name="index-de-Meer_002c-H_002e-162"></a><a name="index-Trivedi_002c-K_002e-163"></a> <!-- CMVA for single class, closed networks with a single load dependent servers --> +<a name="doc_002dqncmva"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qncmva</b> (<var>N, S, Sld, V</var>)<var><a name="index-qncmva-175"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qncmva</b> (<var>N, S, Sld, V, Z</var>)<var><a name="index-qncmva-176"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qncmva</b> (<var>N, S, Sld, V</var>)<var><a name="index-qncmva-164"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qncmva</b> (<var>N, S, Sld, V, Z</var>)<var><a name="index-qncmva-165"></a></var><br> <blockquote> - <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-177"></a><a name="index-CMVA-178"></a> + <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-166"></a><a name="index-CMVA-167"></a> Implementation of the Conditional MVA (CMVA) algorithm, a numerically stable variant of MVA for load-dependent servers. CMVA is described in G. Casale, <cite>A Note on Stable Flow-Equivalent Aggregation in @@ -3813,17 +3539,19 @@ closed networks</cite>. Queueing Syst. Theory Appl., 60:193–202, December 2008. - <p><a name="index-Casale_002c-G_002e-179"></a> + <p><a name="index-Casale_002c-G_002e-168"></a> <!-- Approximate MVA for single class, closed networks --> + <p><a name="doc_002dqnclosedsinglemvaapprox"></a> + <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V</var>)<var><a name="index-qnclosedsinglemvaapprox-180"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedsinglemvaapprox-181"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m, Z</var>)<var><a name="index-qnclosedsinglemvaapprox-182"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m, Z, tol</var>)<var><a name="index-qnclosedsinglemvaapprox-183"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m, Z, tol, iter_max</var>)<var><a name="index-qnclosedsinglemvaapprox-184"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V</var>)<var><a name="index-qnclosedsinglemvaapprox-169"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedsinglemvaapprox-170"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m, Z</var>)<var><a name="index-qnclosedsinglemvaapprox-171"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m, Z, tol</var>)<var><a name="index-qnclosedsinglemvaapprox-172"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m, Z, tol, iter_max</var>)<var><a name="index-qnclosedsinglemvaapprox-173"></a></var><br> <blockquote> - <p><a name="index-Mean-Value-Analysys-_0028MVA_0029_002c-approximate-185"></a><a name="index-Approximate-MVA-186"></a><a name="index-Closed-network_002c-single-class-187"></a><a name="index-Closed-network_002c-approximate-analysis-188"></a> + <p><a name="index-Mean-Value-Analysys-_0028MVA_0029_002c-approximate-174"></a><a name="index-Approximate-MVA-175"></a><a name="index-Closed-network_002c-single-class-176"></a><a name="index-Closed-network_002c-approximate-analysis-177"></a> 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 k when a @@ -3902,18 +3630,20 @@ 1984. <a href="http://www.cs.washington.edu/homes/lazowska/qsp/">http://www.cs.washington.edu/homes/lazowska/qsp/</a>. In particular, see section 6.4.2.2 ("Approximate Solution Techniques"). - <p><a name="index-Lazowska_002c-E_002e-D_002e-189"></a><a name="index-Zahorjan_002c-J_002e-190"></a><a name="index-Graham_002c-G_002e-S_002e-191"></a><a name="index-Sevcik_002c-K_002e-C_002e-192"></a> + <p><a name="index-Lazowska_002c-E_002e-D_002e-178"></a><a name="index-Zahorjan_002c-J_002e-179"></a><a name="index-Graham_002c-G_002e-S_002e-180"></a><a name="index-Sevcik_002c-K_002e-C_002e-181"></a> <!-- MVA for multiple class, closed networks --> + <p><a name="doc_002dqnclosedmultimva"></a> + <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S </var>)<var><a name="index-qnclosedmultimva-193"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, V</var>)<var><a name="index-qnclosedmultimva-194"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedmultimva-195"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, V, m, Z</var>)<var><a name="index-qnclosedmultimva-196"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, P</var>)<var><a name="index-qnclosedmultimva-197"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, P, m</var>)<var><a name="index-qnclosedmultimva-198"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S </var>)<var><a name="index-qnclosedmultimva-182"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, V</var>)<var><a name="index-qnclosedmultimva-183"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedmultimva-184"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, V, m, Z</var>)<var><a name="index-qnclosedmultimva-185"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, P</var>)<var><a name="index-qnclosedmultimva-186"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, P, m</var>)<var><a name="index-qnclosedmultimva-187"></a></var><br> <blockquote> - <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-199"></a><a name="index-closed-network_002c-multiple-classes-200"></a> + <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-188"></a><a name="index-closed-network_002c-multiple-classes-189"></a> Analyze closed, multiclass queueing networks with K service centers and C independent customer classes (chains) using the Mean Value Analysys (MVA) algorithm. @@ -4043,7 +3773,7 @@ Multichain Queuing Networks</cite>, Journal of the ACM, vol. 27, n. 2, April 1980, pp. 313–322. <a href="http://doi.acm.org/10.1145/322186.322195">http://doi.acm.org/10.1145/322186.322195</a> - <p><a name="index-Reiser_002c-M_002e-201"></a><a name="index-Lavenberg_002c-S_002e-S_002e-202"></a> + <p><a name="index-Reiser_002c-M_002e-190"></a><a name="index-Lavenberg_002c-S_002e-S_002e-191"></a> 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</cite>, Wiley, @@ -4053,17 +3783,18 @@ 1984. <a href="http://www.cs.washington.edu/homes/lazowska/qsp/">http://www.cs.washington.edu/homes/lazowska/qsp/</a>. In particular, see section 7.4.2.1 ("Exact Solution Techniques"). - <p><a name="index-Bolch_002c-G_002e-203"></a><a name="index-Greiner_002c-S_002e-204"></a><a name="index-de-Meer_002c-H_002e-205"></a><a name="index-Trivedi_002c-K_002e-206"></a><a name="index-Lazowska_002c-E_002e-D_002e-207"></a><a name="index-Zahorjan_002c-J_002e-208"></a><a name="index-Graham_002c-G_002e-S_002e-209"></a><a name="index-Sevcik_002c-K_002e-C_002e-210"></a> + <p><a name="index-Bolch_002c-G_002e-192"></a><a name="index-Greiner_002c-S_002e-193"></a><a name="index-de-Meer_002c-H_002e-194"></a><a name="index-Trivedi_002c-K_002e-195"></a><a name="index-Lazowska_002c-E_002e-D_002e-196"></a><a name="index-Zahorjan_002c-J_002e-197"></a><a name="index-Graham_002c-G_002e-S_002e-198"></a><a name="index-Sevcik_002c-K_002e-C_002e-199"></a> <!-- Approximate MVA, with Bard-Schweitzer approximation --> +<a name="doc_002dqnclosedmultimvaapprox"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V</var>)<var><a name="index-qnclosedmultimvaapprox-211"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedmultimvaapprox-212"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m, Z</var>)<var><a name="index-qnclosedmultimvaapprox-213"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m, Z, tol</var>)<var><a name="index-qnclosedmultimvaapprox-214"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m, Z, tol, iter_max</var>)<var><a name="index-qnclosedmultimvaapprox-215"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V</var>)<var><a name="index-qnclosedmultimvaapprox-200"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedmultimvaapprox-201"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m, Z</var>)<var><a name="index-qnclosedmultimvaapprox-202"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m, Z, tol</var>)<var><a name="index-qnclosedmultimvaapprox-203"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m, Z, tol, iter_max</var>)<var><a name="index-qnclosedmultimvaapprox-204"></a></var><br> <blockquote> - <p><a name="index-Mean-Value-Analysys-_0028MVA_0029_002c-approximate-216"></a><a name="index-Approximate-MVA-217"></a><a name="index-Closed-network_002c-multiple-classes-218"></a><a name="index-Closed-network_002c-approximate-analysis-219"></a> + <p><a name="index-Mean-Value-Analysys-_0028MVA_0029_002c-approximate-205"></a><a name="index-Approximate-MVA-206"></a><a name="index-Closed-network_002c-multiple-classes-207"></a><a name="index-Closed-network_002c-approximate-analysis-208"></a> Analyze closed, multiclass queueing networks with K service centers and C customer classes using the approximate Mean Value Analysys (MVA) algorithm. @@ -4148,12 +3879,12 @@ proc. 4th Int. Symp. on Modelling and Performance Evaluation of Computer Systems, feb. 1979, pp. 51–62. - <p><a name="index-Bard_002c-Y_002e-220"></a> + <p><a name="index-Bard_002c-Y_002e-209"></a> P. Schweitzer, <cite>Approximate Analysis of Multiclass Closed Networks of Queues</cite>, Proc. Int. Conf. on Stochastic Control and Optimization, jun 1979, pp. 25–29. - <p><a name="index-Schweitzer_002c-P_002e-221"></a> + <p><a name="index-Schweitzer_002c-P_002e-210"></a> 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</cite>, @@ -4164,15 +3895,17 @@ described above, as it computes the average response times R instead of the residence times. - <p><a name="index-Lazowska_002c-E_002e-D_002e-222"></a><a name="index-Zahorjan_002c-J_002e-223"></a><a name="index-Graham_002c-G_002e-S_002e-224"></a><a name="index-Sevcik_002c-K_002e-C_002e-225"></a> - -<h4 class="subsection">6.3.5 Mixed Networks</h4> + <p><a name="index-Lazowska_002c-E_002e-D_002e-211"></a><a name="index-Zahorjan_002c-J_002e-212"></a><a name="index-Graham_002c-G_002e-S_002e-213"></a><a name="index-Sevcik_002c-K_002e-C_002e-214"></a> + +<h4 class="subsection">5.2.5 Mixed Networks</h4> <!-- MVA for mixed networks --> +<p><a name="doc_002dqnmix"></a> + <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmix</b> (<var>lambda, N, S, V, m</var>)<var><a name="index-qnmix-226"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmix</b> (<var>lambda, N, S, V, m</var>)<var><a name="index-qnmix-215"></a></var><br> <blockquote> - <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-227"></a><a name="index-mixed-network-228"></a> + <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-216"></a><a name="index-mixed-network-217"></a> Solution of mixed queueing networks through MVA. The network consists of K service centers (single-server or delay centers) and C independent customer chains. Both open and closed chains @@ -4251,7 +3984,7 @@ </pre> <strong>See also:</strong> qnclosedmultimva, qnopenmulti. - </blockquote></div> + </blockquote></div> <p class="noindent"><strong>REFERENCES</strong> @@ -4263,33 +3996,35 @@ Note that in this function we compute the mean response time R instead of the mean residence time as in the reference. - <p><a name="index-Lazowska_002c-E_002e-D_002e-229"></a><a name="index-Zahorjan_002c-J_002e-230"></a><a name="index-Graham_002c-G_002e-S_002e-231"></a><a name="index-Sevcik_002c-K_002e-C_002e-232"></a> + <p><a name="index-Lazowska_002c-E_002e-D_002e-218"></a><a name="index-Zahorjan_002c-J_002e-219"></a><a name="index-Graham_002c-G_002e-S_002e-220"></a><a name="index-Sevcik_002c-K_002e-C_002e-221"></a> Herb Schwetman, <cite>Implementing the Mean Value Algorithm for the Solution of Queueing Network Models</cite>, Technical Report CSD-TR-355, Department of Computer Sciences, Purdue University, feb 15, 1982, available at <a href="http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-355.pdf">http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-355.pdf</a> - <p><a name="index-Schwetman_002c-H_002e-233"></a> + <p><a name="index-Schwetman_002c-H_002e-222"></a> <div class="node"> -<a name="Algorithms-for-non-Product-form-QNs"></a> -<a name="Algorithms-for-non-Product_002dform-QNs"></a> +<a name="Algorithms-for-non-Product-Form-QNs"></a> +<a name="Algorithms-for-non-Product_002dForm-QNs"></a> <p><hr> -Next: <a rel="next" accesskey="n" href="#Bounds-on-performance">Bounds on performance</a>, +Next: <a rel="next" accesskey="n" href="#Generic-Algorithms">Generic Algorithms</a>, Previous: <a rel="previous" accesskey="p" href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a>, Up: <a rel="up" accesskey="u" href="#Queueing-Networks">Queueing Networks</a> </div> -<h3 class="section">6.4 Algorithms for non Product-Form QNs</h3> +<h3 class="section">5.3 Algorithms for non Product-Form QNs</h3> <!-- MVABLO algorithm for approximate analysis of closed, single class --> <!-- QN with blocking --> +<p><a name="doc_002dqnmvablo"></a> + <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmvablo</b> (<var>N, S, M, P</var>)<var><a name="index-qnmvablo-234"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmvablo</b> (<var>N, S, M, P</var>)<var><a name="index-qnmvablo-223"></a></var><br> <blockquote> - <p><a name="index-queueing-network-with-blocking-235"></a><a name="index-blocking-queueing-network-236"></a><a name="index-closed-network_002c-finite-capacity-237"></a> + <p><a name="index-queueing-network-with-blocking-224"></a><a name="index-blocking-queueing-network-225"></a><a name="index-closed-network_002c-finite-capacity-226"></a> MVA algorithm for closed queueing networks with blocking. <samp><span class="command">qnmvablo</span></samp> computes approximate utilization, response time and mean queue length for closed, single class queueing networks with blocking. @@ -4336,7 +4071,7 @@ </pre> <strong>See also:</strong> qnopen, qnclosed. - </blockquote></div> + </blockquote></div> <p class="noindent"><strong>REFERENCES</strong> @@ -4344,15 +4079,16 @@ Networks</cite>, IEEE Transactions on Software Engineering, vol. 14, n. 2, april 1988, pp. 418–428. <a href="http://dx.doi.org/10.1109/32.4663">http://dx.doi.org/10.1109/32.4663</a> - <p><a name="index-Akyildiz_002c-I_002e-F_002e-238"></a> + <p><a name="index-Akyildiz_002c-I_002e-F_002e-227"></a> +<a name="doc_002dqnmarkov"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>lambda, S, C, P</var>)<var><a name="index-qnmarkov-239"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>lambda, S, C, P, m</var>)<var><a name="index-qnmarkov-240"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>N, S, C, P</var>)<var><a name="index-qnmarkov-241"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>N, S, C, P, m</var>)<var><a name="index-qnmarkov-242"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>lambda, S, C, P</var>)<var><a name="index-qnmarkov-228"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>lambda, S, C, P, m</var>)<var><a name="index-qnmarkov-229"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>N, S, C, P</var>)<var><a name="index-qnmarkov-230"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>N, S, C, P, m</var>)<var><a name="index-qnmarkov-231"></a></var><br> <blockquote> - <p><a name="index-closed-network_002c-multiple-classes-243"></a><a name="index-closed-network_002c-finite-capacity-244"></a><a name="index-blocking-queueing-network-245"></a><a name="index-RS-blocking-246"></a> + <p><a name="index-closed-network_002c-multiple-classes-232"></a><a name="index-closed-network_002c-finite-capacity-233"></a><a name="index-blocking-queueing-network-234"></a><a name="index-RS-blocking-235"></a> Compute utilization, response time, average queue length and throughput for open or closed queueing networks with finite capacity. Blocking type is Repetitive-Service (RS). This function explicitly @@ -4449,15 +4185,228 @@ </blockquote></div> <div class="node"> +<a name="Generic-Algorithms"></a> +<p><hr> +Next: <a rel="next" accesskey="n" href="#Bounds-on-performance">Bounds on performance</a>, +Previous: <a rel="previous" accesskey="p" href="#Algorithms-for-non-Product_002dForm-QNs">Algorithms for non Product-Form QNs</a>, +Up: <a rel="up" accesskey="u" href="#Queueing-Networks">Queueing Networks</a> + +</div> + +<h3 class="section">5.4 Generic Algorithms</h3> + +<p>The <code>queueing</code> package provides a high-level function +<code>qnsolve</code> for analyzing QN models. <code>qnsolve</code> 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 +described in the previous section. <code>qnsolve</code> supports single or +multiclass models, but at the moment only product-form networks can be +analyzed. For non product-form networks See <a href="#Algorithms-for-non-Product_002dForm-QNs">Algorithms for non Product-Form QNs</a>. + + <p><code>qnsolve</code> accepts two input parameters. The first one is the list +of nodes, encoded as an Octave <em>cell array</em>. The second parameter +is the vector of visit ratios <var>V</var>, which can be either a vector +(for single-class models) or a two-dimensional matrix (for +multiple-class models). + + <p>Individual nodes in the network are structures build using the +<code>qnmknode</code> function. + + <p><a name="doc_002dqnmknode"></a> + +<div class="defun"> +— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"m/m/m-fcfs", S</var>)<var><a name="index-qnmknode-236"></a></var><br> +— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"m/m/m-fcfs", S, m</var>)<var><a name="index-qnmknode-237"></a></var><br> +— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"m/m/1-lcfs-pr", S</var>)<var><a name="index-qnmknode-238"></a></var><br> +— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"-/g/1-ps", S</var>)<var><a name="index-qnmknode-239"></a></var><br> +— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"-/g/1-ps", S, s2</var>)<var><a name="index-qnmknode-240"></a></var><br> +— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"-/g/inf", S</var>)<var><a name="index-qnmknode-241"></a></var><br> +— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"-/g/inf", S, s2</var>)<var><a name="index-qnmknode-242"></a></var><br> +<blockquote> + <p>Creates a node; this function can be used together with +<code>qnsolve</code>. 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. + + <p><strong>INPUTS</strong> + + <dl> +<dt><var>S</var><dd>Average service time. S can be either a scalar, a row vector, +a column vector or a two-dimensional matrix. + + <ul> +<li>If S is a scalar, +it is assumed to be a load-independent, class-independent service time. + + <li>If S is a column vector, then <var>S</var><code>(c)</code> is assumed to +the the load-independent service time for class c customers. + + <li>If S is a row vector, then <var>S</var><code>(n)</code> is assumed to be +the class-independent service time at the node, when there are n +requests. + + <li>Finally, if <var>S</var> is a two-dimensional matrix, then +<var>S</var><code>(c,n)</code> is assumed to be the class c service time +when there are n requests at the node. + + </ul> + + <br><dt><var>m</var><dd>Number of identical servers at the node. Default is <var>m</var><code>=1</code>. + + <br><dt><var>s2</var><dd>Squared coefficient of variation for the service time. Default is 1.0. + + </dl> + + <p>The returned struct <var>Q</var> should be considered opaque to the client. + + <!-- The returned struct @var{Q} has the following fields: --> + <!-- @table @var --> + <!-- @item Q.node --> + <!-- (String) type of the node; valid values are @code{"m/m/m-fcfs"}, --> + <!-- @code{"-/g/1-lcfs-pr"}, @code{"-/g/1-ps"} (Processor-Sharing) --> + <!-- and @code{"-/g/inf"} (Infinite Server, or delay center). --> + <!-- @item Q.S --> + <!-- Average service time. If @code{@var{Q}.S} is a vector, then --> + <!-- @code{@var{Q}.S(i)} is the average service time at that node --> + <!-- if there are @math{i} requests. --> + <!-- @item Q.m --> + <!-- Number of identical servers at a @code{"m/m/m-fcfs"}. Default is 1. --> + <!-- @item Q.c --> + <!-- Number of customer classes. Default is 1. --> + <!-- @end table --> + <pre class="sp"> + + </pre> + <strong>See also:</strong> qnsolve. + + </blockquote></div> + + <p>After the network has been defined, it is possible to solve it using +<code>qnsolve</code>. + + <p><a name="doc_002dqnsolve"></a> + +<div class="defun"> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"closed", N, QQ, V</var>)<var><a name="index-qnsolve-243"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"closed", N, QQ, V, Z</var>)<var><a name="index-qnsolve-244"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"open", lambda, QQ, V</var>)<var><a name="index-qnsolve-245"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"mixed", lambda, N, QQ, V</var>)<var><a name="index-qnsolve-246"></a></var><br> +<blockquote> + <p>General evaluator of QN models. Networks can be open, +closed or mixed; single as well as multiclass networks are supported. + + <ul> +<li>For <strong>closed</strong> networks, the following server types are +supported: M/M/m–FCFS, -/G/\infty, -/G/1–LCFS-PR, +-/G/1–PS and load-dependent variants. + + <li>For <strong>open</strong> networks, the following server types are supported: +M/M/m–FCFS, -/G/\infty and -/G/1–PS. General +load-dependent nodes are <em>not</em> supported. Multiclass open networks +do not support multiple server M/M/m nodes, but only +single server M/M/1–FCFS. + + <li>For <strong>mixed</strong> networks, the following server types are supported: +M/M/1–FCFS, -/G/\infty and -/G/1–PS. General +load-dependent nodes are <em>not</em> supported. + + </ul> + + <p><strong>INPUTS</strong> + + <dl> +<dt><var>N</var><dd>Number of requests in the system for closed networks. For +single-class networks, <var>N</var> must be a scalar. For multiclass +networks, <var>N</var><code>(c)</code> is the population size of closed class +c. + + <br><dt><var>lambda</var><dd>External arrival rate (scalar) for open networks. For single-class +networks, <var>lambda</var> must be a scalar. For multiclass networks, +<var>lambda</var><code>(c)</code> is the class c overall arrival rate. + + <br><dt><var>QQ</var><dd>List of queues in the network. This must be a cell array +with N elements, such that <var>QQ</var><code>{i}</code> is +a struct produced by the <code>qnmknode</code> function. + + <br><dt><var>Z</var><dd>External delay ("think time") for closed networks. Default 0. + + </dl> + + <p><strong>OUTPUTS</strong> + + <dl> +<dt><var>U</var><dd>If i is a FCFS node, then <var>U</var><code>(i)</code> is the utilization +of service center i. If i is an IS node, then +<var>U</var><code>(i)</code> is the <em>traffic intensity</em> defined as +<var>X</var><code>(i)*</code><var>S</var><code>(i)</code>. + + <br><dt><var>R</var><dd><var>R</var><code>(i)</code> is the average response time of service center i. + + <br><dt><var>Q</var><dd><var>Q</var><code>(i)</code> is the average number of customers in service center +i. + + <br><dt><var>X</var><dd><var>X</var><code>(i)</code> is the throughput of service center i. + + </dl> + + <p>Note that for multiclass networks, the computed results are per-class +utilization, response time, number of customers and throughput: +<var>U</var><code>(c,k)</code>, <var>R</var><code>(c,k)</code>, <var>Q</var><code>(c,k)</code>, +<var>X</var><code>(c,k)</code>, + + </blockquote></div> + +<p class="noindent"><strong>EXAMPLE</strong> + + <p>Let us consider a closed, multiclass network with C=2 classes +and K=3 service center. Let the population be M=(2, 1) +(class 1 has 2 requests, and class 2 has 1 request). The nodes are as +follows: + + <ul> +<li>Node 1 is a 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]</code>. Thus, <var>S</var><code>(1,2) = +0.2</code> means that service time for class 1 customers where there are 2 +requests in 0.2. Note that service times are class-independent; + + <li>Node 2 is a -/G/1–PS node, with service times +S_1, 2 = 0.4 for class 1, and S_2, 2 = 0.6 for class 2 +requests; + + <li>Node 3 is a -/G/\infty node (delay center), with service +times S_1, 3=1 and S_2, 3=2 for class 1 and 2 +respectively. + + </ul> + + <p>After defining the per-class visit count <var>V</var> such that +<var>V</var><code>(c,k)</code> is the visit count of class c requests to +service center k. We can define and solve the model as +follows: + +<pre class="example"><pre class="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 ); +</pre> +</pre> + <div class="node"> <a name="Bounds-on-performance"></a> <p><hr> Next: <a rel="next" accesskey="n" href="#Utility-functions">Utility functions</a>, -Previous: <a rel="previous" accesskey="p" href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a>, +Previous: <a rel="previous" accesskey="p" href="#Generic-Algorithms">Generic Algorithms</a>, Up: <a rel="up" accesskey="u" href="#Queueing-Networks">Queueing Networks</a> </div> -<h3 class="section">6.5 Bounds on performance</h3> +<h3 class="section">5.5 Bounds on performance</h3> + +<p><a name="doc_002dqnopenab"></a> <div class="defun"> — Function File: [<var>Xu</var>, <var>Rl</var>] = <b>qnopenab</b> (<var>lambda, D</var>)<var><a name="index-qnopenab-247"></a></var><br> @@ -4492,7 +4441,7 @@ </pre> <strong>See also:</strong> qnopenbsb. - </blockquote></div> + </blockquote></div> <p class="noindent"><strong>REFERENCES</strong> @@ -4503,6 +4452,7 @@ particular, see section 5.2 ("Asymptotic Bounds"). <p><a name="index-Lazowska_002c-E_002e-D_002e-250"></a><a name="index-Zahorjan_002c-J_002e-251"></a><a name="index-Graham_002c-G_002e-S_002e-252"></a><a name="index-Sevcik_002c-K_002e-C_002e-253"></a> +<a name="doc_002dqnclosedab"></a> <div class="defun"> — Function File: [<var>Xl</var>, <var>Xu</var>, <var>Rl</var>, <var>Ru</var>] = <b>qnclosedab</b> (<var>N, D</var>)<var><a name="index-qnclosedab-254"></a></var><br> @@ -4551,6 +4501,8 @@ <p><a name="index-Lazowska_002c-E_002e-D_002e-258"></a><a name="index-Zahorjan_002c-J_002e-259"></a><a name="index-Graham_002c-G_002e-S_002e-260"></a><a name="index-Sevcik_002c-K_002e-C_002e-261"></a> + <p><a name="doc_002dqnopenbsb"></a> + <div class="defun"> — Function File: [<var>Xu</var>, <var>Rl</var>, <var>Ru</var>] = <b>qnopenbsb</b> (<var>lambda, D</var>)<var><a name="index-qnopenbsb-262"></a></var><br> <blockquote> @@ -4595,6 +4547,7 @@ particular, see section 5.4 ("Balanced Systems Bounds"). <p><a name="index-Lazowska_002c-E_002e-D_002e-265"></a><a name="index-Zahorjan_002c-J_002e-266"></a><a name="index-Graham_002c-G_002e-S_002e-267"></a><a name="index-Sevcik_002c-K_002e-C_002e-268"></a> +<a name="doc_002dqnclosedbsb"></a> <div class="defun"> — Function File: [<var>Xl</var>, <var>Xu</var>, <var>Rl</var>, <var>Ru</var>] = <b>qnclosedbsb</b> (<var>N, D</var>)<var><a name="index-qnclosedbsb-269"></a></var><br> @@ -4633,6 +4586,8 @@ </blockquote></div> + <p><a name="doc_002dqnclosedpb"></a> + <div class="defun"> — Function File: [<var>Xl</var>, <var>Xu</var>] = <b>qnclosedpb</b> (<var>N, D </var>)<var><a name="index-qnclosedpb-273"></a></var><br> <blockquote> @@ -4679,6 +4634,7 @@ Transactions on Computers, 57(6):780-794, June 2008. <p><a name="index-Hsieh_002c-C_002e-H-274"></a><a name="index-Lam_002c-S_002e-275"></a><a name="index-Casale_002c-G_002e-276"></a><a name="index-Muntz_002c-R_002e-R_002e-277"></a><a name="index-Serazzi_002c-G_002e-278"></a> +<a name="doc_002dqnclosedgb"></a> <div class="defun"> — Function File: [<var>Xl</var>, <var>Xu</var>, <var>Ql</var>, <var>Qu</var>] = <b>qnclosedgb</b> (<var>N, D, Z</var>)<var><a name="index-qnclosedgb-279"></a></var><br> @@ -4737,9 +4693,11 @@ </div> -<h3 class="section">6.6 Utility functions</h3> - -<h4 class="subsection">6.6.1 Open or closed networks</h4> +<h3 class="section">5.6 Utility functions</h3> + +<h4 class="subsection">5.6.1 Open or closed networks</h4> + +<p><a name="doc_002dqnclosed"></a> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosed</b> (<var>N, S, V, <small class="dots">...</small></var>)<var><a name="index-qnclosed-285"></a></var><br> @@ -4777,7 +4735,7 @@ </pre> <strong>See also:</strong> qnclosedsinglemva, qnclosedsinglemvald, qnclosedmultimva. - </blockquote></div> + </blockquote></div> <p class="noindent"><strong>EXAMPLE</strong> @@ -4810,7 +4768,9 @@ legend("location","southeast"); </pre> </pre> - <div class="defun"> + <p><a name="doc_002dqnopen"></a> + +<div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopen</b> (<var>lambda, S, V, <small class="dots">...</small></var>)<var><a name="index-qnopen-287"></a></var><br> <blockquote> <p><a name="index-open-network-288"></a> @@ -4828,7 +4788,7 @@ </blockquote></div> <!-- Compute the visit counts --> -<h4 class="subsection">6.6.2 Computation of the visit counts</h4> +<h4 class="subsection">5.6.2 Computation of the visit counts</h4> <p>For single-class networks the average number of visits satisfy the following equation: @@ -4863,6 +4823,8 @@ \lambda_s, j is the overall external arrival rate to the whole system, then P_0, s, j = \lambda_s, j / \lambda. + <p><a name="doc_002dqnvisits"></a> + <div class="defun"> — Function File: [<var>V</var> <var>ch</var>] = <b>qnvisits</b> (<var>P</var>)<var><a name="index-qnvisits-289"></a></var><br> — Function File: <var>V</var> = <b>qnvisits</b> (<var>P, lambda</var>)<var><a name="index-qnvisits-290"></a></var><br> @@ -4924,7 +4886,9 @@ [U R Q X] = qnopensingle( sum(lambda), S, V, m ); </pre> </pre> - <h4 class="subsection">6.6.3 Other utility functions</h4> + <h4 class="subsection">5.6.3 Other utility functions</h4> + +<p><a name="doc_002dpopulation_005fmix"></a> <div class="defun"> — Function File: pop_mix = <b>population_mix</b> (<var>k, N</var>)<var><a name="index-population_005fmix-291"></a></var><br> @@ -4974,7 +4938,7 @@ </pre> <strong>See also:</strong> qnmvapop. - </blockquote></div> + </blockquote></div> <p class="noindent"><strong>REFERENCES</strong> @@ -4992,6 +4956,7 @@ <a href="http://arantxa.ii.uam.es/~ssantini/writing/notes/s668_summation.pdf">http://arantxa.ii.uam.es/~ssantini/writing/notes/s668_summation.pdf</a> <p><a name="index-Schwetman_002c-H_002e-294"></a><a name="index-Santini_002c-S_002e-295"></a> +<a name="doc_002dqnmvapop"></a> <div class="defun"> — Function File: <var>H</var> = <b>qnmvapop</b> (<var>N</var>)<var><a name="index-qnmvapop-296"></a></var><br> @@ -5061,7 +5026,7 @@ </div> -<h2 class="chapter">7 References</h2> +<h2 class="chapter">6 References</h2> <dl> <dt>[Aky88]<dd>Ian F. Akyildiz, <cite>Mean Value Analysis for Blocking Queueing @@ -5089,7 +5054,7 @@ Queueing Networks</cite>, IEEE Transactions on Computers, 57(6):780-794, June 2008. DOI <a href="http://doi.ieeecomputersociety.org/10.1109/TC.2008.37">10.1109/TC.2008.37</a> - <br><dt>[GrSn97]<dd>Charles M. Grinstead, J. Laurie Snell, (July 1997). <cite>Introduction + <br><dt><a name="GrSn97"></a>[GrSn97]<dd>Charles M. Grinstead, J. Laurie Snell, (July 1997). <cite>Introduction to Probability</cite>. American Mathematical Society. ISBN 978-0821807491; this excellent textbook is <a href="http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/amsbook.mac.pdf">available in PDF format</a> and can be used under the terms of the <a href="http://www.gnu.org/copyleft/fdl.html">GNU Free Documentation License (FDL)</a> @@ -5865,29 +5830,29 @@ <ul class="index-cp" compact> <li><a href="#index-Absorption-probabilities-23">Absorption probabilities</a>: <a href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a></li> -<li><a href="#index-Approximate-MVA-186">Approximate MVA</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Approximate-MVA-175">Approximate MVA</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-Asymmetric-_0040math_007bM_002fM_002fm_007d-system-86">Asymmetric M/M/m system</a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> -<li><a href="#index-BCMP-network-141">BCMP network</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-BCMP-network-130">BCMP network</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-Birth_002ddeath-process-38">Birth-death process</a>: <a href="#Birth_002ddeath-process-_0028CTMC_0029">Birth-death process (CTMC)</a></li> <li><a href="#index-Birth_002ddeath-process-13">Birth-death process</a>: <a href="#Birth_002ddeath-process-_0028DTMC_0029">Birth-death process (DTMC)</a></li> -<li><a href="#index-blocking-queueing-network-236">blocking queueing network</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> +<li><a href="#index-blocking-queueing-network-225">blocking queueing network</a>: <a href="#Algorithms-for-non-Product_002dForm-QNs">Algorithms for non Product-Form QNs</a></li> <li><a href="#index-bounds_002c-asymptotic-248">bounds, asymptotic</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> <li><a href="#index-bounds_002c-balanced-system-263">bounds, balanced system</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> <li><a href="#index-bounds_002c-geometric-280">bounds, geometric</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> <li><a href="#index-closed-network-286">closed network</a>: <a href="#Utility-functions">Utility functions</a></li> <li><a href="#index-closed-network-257">closed network</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-closed-network-118">closed network</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Closed-network_002c-approximate-analysis-188">Closed network, approximate analysis</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-closed-network_002c-finite-capacity-237">closed network, finite capacity</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> +<li><a href="#index-closed-network-107">closed network</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Closed-network_002c-approximate-analysis-177">Closed network, approximate analysis</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-closed-network_002c-finite-capacity-226">closed network, finite capacity</a>: <a href="#Algorithms-for-non-Product_002dForm-QNs">Algorithms for non Product-Form QNs</a></li> <li><a href="#index-closed-network_002c-multiple-classes-293">closed network, multiple classes</a>: <a href="#Utility-functions">Utility functions</a></li> -<li><a href="#index-closed-network_002c-multiple-classes-243">closed network, multiple classes</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> -<li><a href="#index-Closed-network_002c-multiple-classes-218">Closed network, multiple classes</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-closed-network_002c-multiple-classes-200">closed network, multiple classes</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Closed-network_002c-single-class-187">Closed network, single class</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-closed-network_002c-single-class-157">closed network, single class</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-CMVA-178">CMVA</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-closed-network_002c-multiple-classes-232">closed network, multiple classes</a>: <a href="#Algorithms-for-non-Product_002dForm-QNs">Algorithms for non Product-Form QNs</a></li> +<li><a href="#index-Closed-network_002c-multiple-classes-207">Closed network, multiple classes</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-closed-network_002c-multiple-classes-189">closed network, multiple classes</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Closed-network_002c-single-class-176">Closed network, single class</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-closed-network_002c-single-class-146">closed network, single class</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-CMVA-167">CMVA</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-Continuous-time-Markov-chain-33">Continuous time Markov chain</a>: <a href="#State-occupancy-probabilities-_0028CTMC_0029">State occupancy probabilities (CTMC)</a></li> -<li><a href="#index-convolution-algorithm-120">convolution algorithm</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-convolution-algorithm-109">convolution algorithm</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-copyright-302">copyright</a>: <a href="#Copying">Copying</a></li> <li><a href="#index-Discrete-time-Markov-chain-6">Discrete time Markov chain</a>: <a href="#State-occupancy-probabilities-_0028DTMC_0029">State occupancy probabilities (DTMC)</a></li> <li><a href="#index-Expected-sojourn-time-42">Expected sojourn time</a>: <a href="#Expected-sojourn-times-_0028CTMC_0029">Expected sojourn times (CTMC)</a></li> @@ -5895,8 +5860,8 @@ <li><a href="#index-First-passage-times-56">First passage times</a>: <a href="#First-passage-times-_0028CTMC_0029">First passage times (CTMC)</a></li> <li><a href="#index-First-passage-times-26">First passage times</a>: <a href="#First-passage-times-_0028DTMC_0029">First passage times (DTMC)</a></li> <li><a href="#index-Fundamental-matrix-24">Fundamental matrix</a>: <a href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a></li> -<li><a href="#index-Jackson-network-111">Jackson network</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-load_002ddependent-service-center-130">load-dependent service center</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Jackson-network-100">Jackson network</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-load_002ddependent-service-center-119">load-dependent service center</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-g_t_0040math_007bM_002fG_002f1_007d-system-92">M/G/1 system</a>: <a href="#The-M_002fG_002f1-System">The M/G/1 System</a></li> <li><a href="#index-g_t_0040math_007bM_002fH_005fm_002f1_007d-system-94">M/H_m/1 system</a>: <a href="#The-M_002fHm_002f1-System">The M/Hm/1 System</a></li> <li><a href="#index-g_t_0040math_007bM_002fM_002f1_007d-system-58">M/M/1 system</a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> @@ -5919,18 +5884,18 @@ <li><a href="#index-Mean-recurrence-times-27">Mean recurrence times</a>: <a href="#First-passage-times-_0028DTMC_0029">First passage times (DTMC)</a></li> <li><a href="#index-Mean-time-to-absorption-49">Mean time to absorption</a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> <li><a href="#index-Mean-time-to-absorption-22">Mean time to absorption</a>: <a href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a></li> -<li><a href="#index-Mean-Value-Analysys-_0028MVA_0029-156">Mean Value Analysys (MVA)</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Mean-Value-Analysys-_0028MVA_0029_002c-approximate-185">Mean Value Analysys (MVA), approximate</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-mixed-network-228">mixed network</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-normalization-constant-119">normalization constant</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Mean-Value-Analysys-_0028MVA_0029-145">Mean Value Analysys (MVA)</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Mean-Value-Analysys-_0028MVA_0029_002c-approximate-174">Mean Value Analysys (MVA), approximate</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-mixed-network-217">mixed network</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-normalization-constant-108">normalization constant</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-open-network-288">open network</a>: <a href="#Utility-functions">Utility functions</a></li> <li><a href="#index-open-network-249">open network</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-open-network_002c-multiple-classes-148">open network, multiple classes</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-open-network_002c-single-class-110">open network, single class</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-open-network_002c-multiple-classes-137">open network, multiple classes</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-open-network_002c-single-class-99">open network, single class</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-population-mix-292">population mix</a>: <a href="#Utility-functions">Utility functions</a></li> -<li><a href="#index-queueing-network-with-blocking-235">queueing network with blocking</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> +<li><a href="#index-queueing-network-with-blocking-224">queueing network with blocking</a>: <a href="#Algorithms-for-non-Product_002dForm-QNs">Algorithms for non Product-Form QNs</a></li> <li><a href="#index-queueing-networks-95">queueing networks</a>: <a href="#Queueing-Networks">Queueing Networks</a></li> -<li><a href="#index-RS-blocking-246">RS blocking</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> +<li><a href="#index-RS-blocking-235">RS blocking</a>: <a href="#Algorithms-for-non-Product_002dForm-QNs">Algorithms for non Product-Form QNs</a></li> <li><a href="#index-Stationary-probabilities-35">Stationary probabilities</a>: <a href="#State-occupancy-probabilities-_0028CTMC_0029">State occupancy probabilities (CTMC)</a></li> <li><a href="#index-Stationary-probabilities-8">Stationary probabilities</a>: <a href="#State-occupancy-probabilities-_0028DTMC_0029">State occupancy probabilities (DTMC)</a></li> <li><a href="#index-Time_002dalveraged-sojourn-time-46">Time-alveraged sojourn time</a>: <a href="#Time_002daveraged-expected-sojourn-times-_0028CTMC_0029">Time-averaged expected sojourn times (CTMC)</a></li> @@ -5972,34 +5937,34 @@ <li><a href="#index-qnclosedab-254"><code>qnclosedab</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> <li><a href="#index-qnclosedbsb-269"><code>qnclosedbsb</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> <li><a href="#index-qnclosedgb-279"><code>qnclosedgb</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-qnclosedmultimva-193"><code>qnclosedmultimva</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnclosedmultimvaapprox-211"><code>qnclosedmultimvaapprox</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnclosedmultimva-182"><code>qnclosedmultimva</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnclosedmultimvaapprox-200"><code>qnclosedmultimvaapprox</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-qnclosedpb-273"><code>qnclosedpb</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-qnclosedsinglemva-153"><code>qnclosedsinglemva</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnclosedsinglemvaapprox-180"><code>qnclosedsinglemvaapprox</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnclosedsinglemvald-166"><code>qnclosedsinglemvald</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qncmva-175"><code>qncmva</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnconvolution-116"><code>qnconvolution</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnconvolutionld-126"><code>qnconvolutionld</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnjackson-107"><code>qnjackson</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnmarkov-239"><code>qnmarkov</code></a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> +<li><a href="#index-qnclosedsinglemva-142"><code>qnclosedsinglemva</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnclosedsinglemvaapprox-169"><code>qnclosedsinglemvaapprox</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnclosedsinglemvald-155"><code>qnclosedsinglemvald</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qncmva-164"><code>qncmva</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnconvolution-105"><code>qnconvolution</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnconvolutionld-115"><code>qnconvolutionld</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnjackson-96"><code>qnjackson</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnmarkov-228"><code>qnmarkov</code></a>: <a href="#Algorithms-for-non-Product_002dForm-QNs">Algorithms for non Product-Form QNs</a></li> <li><a href="#index-qnmg1-91"><code>qnmg1</code></a>: <a href="#The-M_002fG_002f1-System">The M/G/1 System</a></li> <li><a href="#index-qnmh1-93"><code>qnmh1</code></a>: <a href="#The-M_002fHm_002f1-System">The M/Hm/1 System</a></li> -<li><a href="#index-qnmix-226"><code>qnmix</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnmknode-96"><code>qnmknode</code></a>: <a href="#Generic-Algorithms">Generic Algorithms</a></li> +<li><a href="#index-qnmix-215"><code>qnmix</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnmknode-236"><code>qnmknode</code></a>: <a href="#Generic-Algorithms">Generic Algorithms</a></li> <li><a href="#index-qnmm1-57"><code>qnmm1</code></a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> <li><a href="#index-qnmm1k-77"><code>qnmm1k</code></a>: <a href="#The-M_002fM_002f1_002fK-System">The M/M/1/K System</a></li> <li><a href="#index-qnmminf-70"><code>qnmminf</code></a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> <li><a href="#index-qnmmm-63"><code>qnmmm</code></a>: <a href="#The-M_002fM_002fm-System">The M/M/m System</a></li> <li><a href="#index-qnmmmk-79"><code>qnmmmk</code></a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> -<li><a href="#index-qnmvablo-234"><code>qnmvablo</code></a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> +<li><a href="#index-qnmvablo-223"><code>qnmvablo</code></a>: <a href="#Algorithms-for-non-Product_002dForm-QNs">Algorithms for non Product-Form QNs</a></li> <li><a href="#index-qnmvapop-296"><code>qnmvapop</code></a>: <a href="#Utility-functions">Utility functions</a></li> <li><a href="#index-qnopen-287"><code>qnopen</code></a>: <a href="#Utility-functions">Utility functions</a></li> <li><a href="#index-qnopenab-247"><code>qnopenab</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> <li><a href="#index-qnopenbsb-262"><code>qnopenbsb</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-qnopenmulti-146"><code>qnopenmulti</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnopensingle-138"><code>qnopensingle</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnsolve-103"><code>qnsolve</code></a>: <a href="#Generic-Algorithms">Generic Algorithms</a></li> +<li><a href="#index-qnopenmulti-135"><code>qnopenmulti</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnopensingle-127"><code>qnopensingle</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnsolve-243"><code>qnsolve</code></a>: <a href="#Generic-Algorithms">Generic Algorithms</a></li> <li><a href="#index-qnvisits-289"><code>qnvisits</code></a>: <a href="#Utility-functions">Utility functions</a></li> </ul><div class="node"> <a name="Author-Index"></a> @@ -6014,19 +5979,19 @@ <ul class="index-au" compact> -<li><a href="#index-Akyildiz_002c-I_002e-F_002e-238">Akyildiz, I. F.</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> -<li><a href="#index-Bard_002c-Y_002e-220">Bard, Y.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Bolch_002c-G_002e-112">Bolch, G.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Akyildiz_002c-I_002e-F_002e-227">Akyildiz, I. F.</a>: <a href="#Algorithms-for-non-Product_002dForm-QNs">Algorithms for non Product-Form QNs</a></li> +<li><a href="#index-Bard_002c-Y_002e-209">Bard, Y.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Bolch_002c-G_002e-101">Bolch, G.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-Bolch_002c-G_002e-87">Bolch, G.</a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> <li><a href="#index-Bolch_002c-G_002e-81">Bolch, G.</a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> <li><a href="#index-Bolch_002c-G_002e-73">Bolch, G.</a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> <li><a href="#index-Bolch_002c-G_002e-66">Bolch, G.</a>: <a href="#The-M_002fM_002fm-System">The M/M/m System</a></li> <li><a href="#index-Bolch_002c-G_002e-59">Bolch, G.</a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> <li><a href="#index-Bolch_002c-G_002e-50">Bolch, G.</a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> -<li><a href="#index-Buzen_002c-J_002e-P_002e-121">Buzen, J. P.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Buzen_002c-J_002e-P_002e-110">Buzen, J. P.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-Casale_002c-G_002e-276">Casale, G.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Casale_002c-G_002e-179">Casale, G.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-de-Meer_002c-H_002e-114">de Meer, H.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Casale_002c-G_002e-168">Casale, G.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-de-Meer_002c-H_002e-103">de Meer, H.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-de-Meer_002c-H_002e-89">de Meer, H.</a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> <li><a href="#index-de-Meer_002c-H_002e-83">de Meer, H.</a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> <li><a href="#index-de-Meer_002c-H_002e-75">de Meer, H.</a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> @@ -6034,8 +5999,8 @@ <li><a href="#index-de-Meer_002c-H_002e-61">de Meer, H.</a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> <li><a href="#index-de-Meer_002c-H_002e-52">de Meer, H.</a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> <li><a href="#index-Graham_002c-G_002e-S_002e-252">Graham, G. S.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Graham_002c-G_002e-S_002e-151">Graham, G. S.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Greiner_002c-S_002e-113">Greiner, S.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Graham_002c-G_002e-S_002e-140">Graham, G. S.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Greiner_002c-S_002e-102">Greiner, S.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-Greiner_002c-S_002e-88">Greiner, S.</a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> <li><a href="#index-Greiner_002c-S_002e-82">Greiner, S.</a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> <li><a href="#index-Greiner_002c-S_002e-74">Greiner, S.</a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> @@ -6043,22 +6008,22 @@ <li><a href="#index-Greiner_002c-S_002e-60">Greiner, S.</a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> <li><a href="#index-Greiner_002c-S_002e-51">Greiner, S.</a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> <li><a href="#index-Hsieh_002c-C_002e-H-274">Hsieh, C. H</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Jain_002c-R_002e-161">Jain, R.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Kobayashi_002c-H_002e-133">Kobayashi, H.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Jain_002c-R_002e-150">Jain, R.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Kobayashi_002c-H_002e-122">Kobayashi, H.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-Lam_002c-S_002e-275">Lam, S.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Lavenberg_002c-S_002e-S_002e-160">Lavenberg, S. S.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Lavenberg_002c-S_002e-S_002e-149">Lavenberg, S. S.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-Lazowska_002c-E_002e-D_002e-250">Lazowska, E. D.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Lazowska_002c-E_002e-D_002e-149">Lazowska, E. D.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Lazowska_002c-E_002e-D_002e-138">Lazowska, E. D.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-Muntz_002c-R_002e-R_002e-277">Muntz, R. R.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Reiser_002c-M_002e-132">Reiser, M.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Reiser_002c-M_002e-121">Reiser, M.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-Santini_002c-S_002e-295">Santini, S.</a>: <a href="#Utility-functions">Utility functions</a></li> -<li><a href="#index-Schweitzer_002c-P_002e-221">Schweitzer, P.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Schweitzer_002c-P_002e-210">Schweitzer, P.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-Schwetman_002c-H_002e-294">Schwetman, H.</a>: <a href="#Utility-functions">Utility functions</a></li> -<li><a href="#index-Schwetman_002c-H_002e-131">Schwetman, H.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Schwetman_002c-H_002e-120">Schwetman, H.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-Serazzi_002c-G_002e-278">Serazzi, G.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> <li><a href="#index-Sevcik_002c-K_002e-C_002e-253">Sevcik, K. C.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Sevcik_002c-K_002e-C_002e-152">Sevcik, K. C.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Trivedi_002c-K_002e-115">Trivedi, K.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Sevcik_002c-K_002e-C_002e-141">Sevcik, K. C.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Trivedi_002c-K_002e-104">Trivedi, K.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> <li><a href="#index-Trivedi_002c-K_002e-90">Trivedi, K.</a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> <li><a href="#index-Trivedi_002c-K_002e-84">Trivedi, K.</a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> <li><a href="#index-Trivedi_002c-K_002e-76">Trivedi, K.</a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> @@ -6068,6 +6033,6 @@ <li><a href="#index-Wong_002c-E_002e-300">Wong, E.</a>: <a href="#Utility-functions">Utility functions</a></li> <li><a href="#index-Zahorjan_002c-J_002e-299">Zahorjan, J.</a>: <a href="#Utility-functions">Utility functions</a></li> <li><a href="#index-Zahorjan_002c-J_002e-251">Zahorjan, J.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Zahorjan_002c-J_002e-150">Zahorjan, J.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Zahorjan_002c-J_002e-139">Zahorjan, J.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> </ul></body></html>
--- a/main/queueing/doc/queueing.texi Sun Apr 08 20:54:02 2012 +0000 +++ b/main/queueing/doc/queueing.texi Mon Apr 09 12:50:58 2012 +0000 @@ -161,7 +161,6 @@ @menu * Summary:: * Installation:: Installation of the queueing toolbox. -* Getting Started:: Getting started with the queueing toolbox. * Markov Chains:: Functions for Markov Chains. * Single Station Queueing Systems:: Functions for single-station queueing systems. * Queueing Networks:: Functions for queueing networks. @@ -176,7 +175,6 @@ @include summary.texi @include installation.texi -@include gettingstarted.texi @include markovchains.texi @include singlestation.texi @include queueingnetworks.texi
--- a/main/queueing/doc/queueingnetworks.txi Sun Apr 08 20:54:02 2012 +0000 +++ b/main/queueing/doc/queueingnetworks.txi Mon Apr 09 12:50:58 2012 +0000 @@ -24,9 +24,9 @@ @menu * Introduction to QNs:: A brief introduction to Queueing Networks. +* Algorithms for Product-Form QNs:: Functions to analyze product-form QNs +* Algorithms for non Product-Form QNs:: Functions to analyze non product-form QNs * Generic Algorithms:: High-level functions for QN analysis -* Algorithms for Product-Form QNs:: Functions to analyze product-form QNs -* Algorithms for non Product-form QNs:: Functions to analyze non product-form QNs * Bounds on performance:: Functions to compute performance bounds * Utility functions:: Utility functions to compute miscellaneous quantities @end menu @@ -40,18 +40,17 @@ @section Introduction to QNs Queueing Networks (QN) are a very simple yet powerful modeling tool -which is used to analyze many kind of systems. In its simplest form, a -QN is made of @math{K} service centers. Each service center @math{i} -has a queue, which is connected to @math{m_i} (generally identical) -@emph{servers}. Customers (or requests) arrive at the service center, -and join the queue if there is a slot available. Then, requests are -served according to a (de)queueing policy. After service completes, -the requests leave the service center. +which can be used to analyze many kind of systems. In its simplest +form, a QN is made of @math{K} service centers. Each center @math{k} +has a queue, which is connected to @math{m_k} (generally identical) +@emph{servers}. Arriving customers (requests) join the queue if there +is a slot available. Then, 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. -The service centers for which @math{m_i = \infty} are called -@emph{delay centers} or @emph{infinite servers}. If a service center -has infinite servers, of course each new request will find one server -available, so there will never be queueing. +Service centers for which @math{m_k = \infty} are called @emph{delay +centers} or @emph{infinite servers}. In this kind of centers, every +request always finds one available server, so queueing never occurs. Requests join the queue according to a @emph{queueing policy}, such as: @@ -67,28 +66,26 @@ Processor Sharing @item IS -Infinite Server, there is an infinite number of identical servers so -that each request always finds a server available, and there is no -queueing +Infinite Server (for which @math{m_k = \infty}). @end table -A population of @emph{requests} or @emph{customers} arrives to the -system system, requesting service to the service centers. The request -population may be @emph{open} or @emph{closed}. In open systems there -is an infinite population of requests. New customers arrive from -outside the system, and eventually leave the system. In closed systems -there is a fixed population of request which continuously interacts -with the system. +Queueing models can be @emph{open} or @emph{closed}. In open models +there is an infinite population of requests; new customers are +generated outside the system, and eventually leave the system. In +closed systems there is a fixed population of request. -There might be a single class of requests, meaning that all requests -behave in the same way (e.g., they spend the same average time on each -particular server), or there might be multiple classes of requests. +Queueing models can have a single request class, meaning that all +requests behave in the same way (e.g., they spend the same average +time on each particular server). In multiclass models there are +multiple request classes, each one with its own +parameters. Furthermore, in multiclass models there can be open and +closed classes of requests within the same system. @subsection Single class models -In single class models, all requests are indistinguishable and belong to -the same class. This means that every request has the same average +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. @@ -96,31 +93,31 @@ @table @math -@item \lambda_i -External arrival rate to service center @math{i}. +@item \lambda_k +External arrival rate to service center @math{k}. @item \lambda Overall external arrival rate to the whole system: @math{\lambda = -\sum_i \lambda_i}. +\sum_k \lambda_k}. -@item S_i -Average service time. @math{S_i} is the average service time on service -center @math{i}. In other words, @math{S_i} is the average time from the +@item S_k +Average service time. @math{S_k} is the average service time on service +center @math{k}. In other words, @math{S_k} is the average time from the instant in which a request is extracted from the queue and starts being service, and the instant at which service finishes and the request moves to another queue (or exits the system). @item P_{i, j} -Routing probability matrix. @math{{\bf P} = P_{i, j}} is a @math{K +Routing probability matrix. @math{{\bf P} = [P_{i, j}]} is a @math{K \times K} matrix such that @math{P_{i, j}} is the probability that a request completing service at server @math{i} will move directly to server @math{j}, The probability that a request leaves the system after service at service center @math{i} is @math{1-\sum_{j=1}^K P_{i, j}}. -@item V_i -Average number of visits. @math{V_i} is the average number of visits to -the service center @math{i}. This quantity will be described shortly. +@item V_k +Average number of visits. @math{V_k} is the average number of visits to +the service center @math{k}. This quantity will be described shortly. @end table @@ -128,24 +125,24 @@ @table @math -@item U_i -Service center utilization. @math{U_i} is the utilization of service -center @math{i}. The utilization is defined as the fraction of time in +@item U_k +Service center utilization. @math{U_k} is the 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). -@item R_i -Average response time. @math{R_i} is the average response time of -service center @math{i}. The average response time is defined as the +@item R_k +Average response time. @math{R_k} is the average response time of +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 Q_i -Average number of customers. @math{Q_i} is the average number of -requests in service center @math{i}. This includes both the requests in +@item Q_k +Average number of customers. @math{Q_k} is the average number of +requests in service center @math{k}. This includes both the requests in the queue, and the request being served. -@item X_i -Throughput. @math{X_i} is the throughput of service center @math{i}. +@item X_k +Throughput. @math{X_k} is the throughput of service center @math{k}. The throughput is defined as the ratio of job completions (i.e., average number of jobs completed over a fixed interval of time). @@ -231,7 +228,7 @@ class @math{c} requests in the system. The transition probability matrix for these kind of networks will be a -@math{C \times K \times C \times K} matrix @math{{\bf P} = P_{r, i, s, j}} +@math{C \times K \times C \times K} matrix @math{{\bf P} = [P_{r, i, s, j}]} such that @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. @@ -243,26 +240,26 @@ @table @math -@item \lambda_{c, i} -External arrival rate of class-@math{c} requests to service center @math{i} +@item \lambda_{c, k} +External arrival rate of class-@math{c} requests to service center @math{k} @item \lambda -Overall external arrival rate to the whole system: @math{\lambda = \sum_c \sum_i \lambda_{c, i}} +Overall external arrival rate to the whole system: @math{\lambda = \sum_c \sum_k \lambda_{c, k}} -@item S_{c, i} -Average service time. @math{S_{c, i}} is the average service time on -service center @math{i} for class @math{c} requests. +@item 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 P_{r, i, s, j} -Routing probability matrix. @math{{\bf P} = P_{r, i, s, j}} is a @math{C +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 V_{c, i} -Average number of visits. @math{V_{c, i}} is the average number of visits -of class @math{c} requests to the service center @math{i}. +@item V_{c, k} +Average number of visits. @math{V_{c, k}} is the average number of visits +of class @math{c} requests to center @math{k}. @end table @@ -270,24 +267,24 @@ @table @math -@item U_{c, i} -Utilization of service center @math{i} by class @math{c} requests. The +@item 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). -@item R_{c, i} +@item R_{c, k} Average response time experienced by class @math{c} requests on service -center @math{i}. The average response time is defined as the average +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 Q_{c, i} +@item Q_{c, k} Average number of class @math{c} requests on service center -@math{i}. This includes both the requests in the queue, and the request +@math{k}. This includes both the requests in the queue, and the request being served. -@item X_{c, i} -Throughput of service center @math{i} for class @math{c} requests. The +@item 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. @@ -297,22 +294,22 @@ @table @math -@item U_i -Utilization of service center @math{i}: +@item U_k +Utilization of service center @math{k}: @iftex @tex -$U_i = \sum_{c=1}^C U_{c, i}$ +$U_k = \sum_{c=1}^C U_{c, k}$ @end tex @end iftex @ifnottex -@code{Ui = sum(U,1);} +@code{Uk = sum(U,k);} @end ifnottex @item R_c System response time for class @math{c} requests: @iftex @tex -$R_c = \sum_{i=1}^K R_{c, i} V_{c, i}$ +$R_c = \sum_{k=1}^K R_{c, k} V_{c, k}$ @end tex @end iftex @ifnottex @@ -323,7 +320,7 @@ Average number of class @math{c} requests in the system: @iftex @tex -$Q_c = \sum_{i=1}^K Q_{c, i}$ +$Q_c = \sum_{k=1}^K Q_{c, k}$ @end tex @end iftex @ifnottex @@ -378,70 +375,197 @@ \sum_s \sum_j \lambda_{s, j}} is the overall external arrival rate to the whole system, then @math{P_{0, s, j} = \lambda_{s, j} / \lambda}. -@c -@c -@c -@node Generic Algorithms -@section Generic Algorithms +@subsection Closed Network Example -The @code{queueing} package provides a couple of high-level functions -for defining and solving QN models. These functions can be used to -define a open or closed QN model (with single or multiple job -classes), with arbitrary configuration and queueing disciplines. At -the moment only product-form networks can be solved, @xref{Algorithms for Product-Form QNs}. +We now give a simple example on how the queueing toolbox can be used +to analyze a closed network. Let us consider a simple closed network +with @math{K=3} @math{M/M/1}--FCFS centers. We denote with @math{S_k} +the average service time at center @math{k}, @math{k=1, 2, 3}. We use +@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}. Specifically, 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: -The network is defined by two parameters. The first one is the list of -nodes, encoded as an Octave @emph{cell array}. The second parameter is -the visit ration @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 -@code{qnmknode} function. +@iftex +@tex +$$ +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 -@GETHELP{qnmknode} +The network above can be analyzed with the @command{qnclosed} function +@pxref{doc-qnclosed}. @command{qnclosed} requires the following +parameters: -After the network has been defined, it is possible to solve it using -the @code{qnsolve} function. Note that this function is somewhat less -efficient than those described in later sections, but -generally easier to use. +@table @var -@GETHELP{qnsolve} +@item N +Number of requests in the network (since we are considering a closed +network, the number of requests is fixed) -@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: +@item S +Array of average service times at the centers: @code{@var{S}(k)} is +the average service time at center @math{k}. -@itemize +@item V +Array of visit ratios: @code{@var{V}(k)} is the average number of +visits to center @math{k}. -@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; +@end table + +We can compute @math{V_k} from the routing probability matrix +@math{P_{i, j}} using the @command{qnvisits} function +@pxref{doc-qnvisits}. We can analyze the network for a given +population size @math{N} (for example, @math{N=10}) as follows: -@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; +@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 = qnvisits(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 -@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. +The output of @command{qnclosed} includes the vector 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 higher +value among the service centers. Tus, center 1 is the @emph{bottleneck +device}. -@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: +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 -@GETDEMO{qnsolve,1} +@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. Here we use @code{"m/m/m-fcfs"} to denote a +@math{M/M/m}--FCFS center. 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 +Of course, we get exactly the same results. Other functions can be used +for closed networks, @pxref{Algorithms for Product-Form QNs}. + +@subsection Open Network Example + +Open networks can be analyzed in a similar way. Let us consider +an open network with @math{K=3} service centers, and routing +probability matrix as follows: + +@iftex +@tex +$$ +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 need to compute the visit +counts @math{V_k} to center @math{k}. Again, we use the +@command{qnvisits} 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 = qnvisits(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 @var{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 @c @c @@ -962,8 +1086,11 @@ @auindex Schwetman, H. +@c +@c +@c -@node Algorithms for non Product-form QNs +@node Algorithms for non Product-Form QNs @section Algorithms for non Product-Form QNs @c @@ -985,6 +1112,72 @@ @c @c @c +@node Generic Algorithms +@section Generic Algorithms + +The @code{queueing} package provides a high-level function +@code{qnsolve} for analyzing QN models. @code{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 +described in the previous section. @code{qnsolve} supports single or +multiclass models, but at the moment only product-form networks can be +analyzed. For non product-form networks @xref{Algorithms for non +Product-Form QNs}. + +@code{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 +@code{qnmknode} function. + +@GETHELP{qnmknode} + +After the network has been defined, it is possible to solve it using +@code{qnsolve}. + +@GETHELP{qnsolve} + +@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 +@GETDEMO{qnsolve,1} +@end example + + +@c +@c +@c @node Bounds on performance @section Bounds on performance
--- a/main/queueing/doc/references.txi Sun Apr 08 20:54:02 2012 +0000 +++ b/main/queueing/doc/references.txi Mon Apr 09 12:50:58 2012 +0000 @@ -55,7 +55,7 @@ Queueing Networks}, IEEE Transactions on Computers, 57(6):780-794, June 2008. DOI @uref{http://doi.ieeecomputersociety.org/10.1109/TC.2008.37, 10.1109/TC.2008.37} -@item [GrSn97] +@item @anchor{GrSn97}[GrSn97] Charles M. Grinstead, J. Laurie Snell, (July 1997). @cite{Introduction to Probability}. American Mathematical Society. ISBN 978-0821807491; this excellent textbook is @uref{http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/amsbook.mac.pdf, available in PDF format}