Menu
▾
▴
[Octave-cvsupdate] SF.net SVN: octave:[10177] trunk/octave-forge/main/queueing/doc
|
From: <mma...@us...> - 2012-04-09 12:51:08
|
Revision: 10177
http://octave.svn.sourceforge.net/octave/?rev=10177&view=rev
Author: mmarzolla
Date: 2012-04-09 12:50:58 +0000 (Mon, 09 Apr 2012)
Log Message:
-----------
improved documentation
Modified Paths:
--------------
trunk/octave-forge/main/queueing/doc/markovchains.txi
trunk/octave-forge/main/queueing/doc/munge-texi.m
trunk/octave-forge/main/queueing/doc/queueing.html
trunk/octave-forge/main/queueing/doc/queueing.pdf
trunk/octave-forge/main/queueing/doc/queueing.texi
trunk/octave-forge/main/queueing/doc/queueingnetworks.txi
trunk/octave-forge/main/queueing/doc/references.txi
Removed Paths:
-------------
trunk/octave-forge/main/queueing/doc/gettingstarted.txi
Deleted: trunk/octave-forge/main/queueing/doc/gettingstarted.txi
===================================================================
--- trunk/octave-forge/main/queueing/doc/gettingstarted.txi 2012-04-08 20:54:02 UTC (rev 10176)
+++ trunk/octave-forge/main/queueing/doc/gettingstarted.txi 2012-04-09 12:50:58 UTC (rev 10177)
@@ -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)
-
Modified: trunk/octave-forge/main/queueing/doc/markovchains.txi
===================================================================
--- trunk/octave-forge/main/queueing/doc/markovchains.txi 2012-04-08 20:54:02 UTC (rev 10176)
+++ trunk/octave-forge/main/queueing/doc/markovchains.txi 2012-04-09 12:50:58 UTC (rev 10177)
@@ -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
Modified: trunk/octave-forge/main/queueing/doc/munge-texi.m
===================================================================
--- trunk/octave-forge/main/queueing/doc/munge-texi.m 2012-04-08 20:54:02 UTC (rev 10176)
+++ trunk/octave-forge/main/queueing/doc/munge-texi.m 2012-04-09 12:50:58 UTC (rev 10177)
@@ -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
##############################################################################
Modified: trunk/octave-forge/main/queueing/doc/queueing.html
===================================================================
--- trunk/octave-forge/main/queueing/doc/queueing.html 2012-04-08 20:54:02 UTC (rev 10176)
+++ trunk/octave-forge/main/queueing/doc/queueing.html 2012-04-09 12:50:58 UTC (rev 10177)
@@ -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>
+<li><a href="#Discrete_002dTime-Markov-Chains">3.1 Discrete-Time Markov Chains</a>
<ul>
-<li><a href="#Discrete_002dTime-Markov-Chains">4.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,7 +593,7 @@
<pre class="example"> octave:4> <kbd>demo qnclosed</kbd>
</pre>
- <!-- This file has been automatically generated from gettingstarted.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 -->
@@ -615,254 +611,15 @@
<!-- 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 -->
-<!-- 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="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,8 +835,10 @@
</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>
<blockquote>
@@ -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,8 +964,10 @@
</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>
— Function File: <var>L</var> = <b>dtmc_exps</b> (<var>P, p0</var>)<var><a name="index-dtmc_005fexps-18"></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,8 +1331,10 @@
</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>
<blockquote>
@@ -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,8 +1476,10 @@
</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>
— Function File: <var>M</var> = <b>ctmc_taexps</b> (<var>Q, p</var>)<var><a name="index-ctmc_005ftaexps-44"></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,8 +1653,10 @@
</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>
— Function File: <var>m</var> = <b>ctmc_fpt</b> (<var>Q, i, j</var>)<var><a name="index-ctmc_005ffpt-55"></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.
+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>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.
+ <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>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>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.
+ <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">6.1.1 Single class models</h4>
+<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
+<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.
+\sum_k \lambda_k.
- <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
+ <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
+<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_i \lambda_c, i
+ <br><dt>\lambda<dd>Overall external arrival rate to the whole system: \lambda = \sum_c \sum_k \lambda_c, k
- <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>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
+ <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>
+<h4 class="subsection">5.1.3 Closed Network Example</h4>
-</div>
+<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:
-<h3 class="section">6.2 Generic Algorithms</h3>
+<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:
-<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>.
+ <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)
- <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)....
[truncated message content] |
