Mercurial > forge
changeset 9981:bbc1245575b8 octave-forge
Documentation restructuring
| author | mmarzolla |
|---|---|
| date | Fri, 06 Apr 2012 16:04:05 +0000 |
| parents | 1d809eac8cbe |
| children | 4054cabceb89 |
| files | main/queueing/doc/Makefile main/queueing/doc/ack.texi main/queueing/doc/ack.txi main/queueing/doc/contributing.texi main/queueing/doc/contributing.txi main/queueing/doc/gettingstarted.texi main/queueing/doc/gettingstarted.txi main/queueing/doc/gpl.texi main/queueing/doc/gpl.txi main/queueing/doc/grabdemo.m main/queueing/doc/installation.texi main/queueing/doc/installation.txi main/queueing/doc/markovchains.txi main/queueing/doc/queueingnetworks.texi main/queueing/doc/queueingnetworks.txi main/queueing/doc/references.texi main/queueing/doc/references.txi main/queueing/doc/singlestation.txi main/queueing/doc/summary.texi main/queueing/doc/summary.txi |
| diffstat | 20 files changed, 2915 insertions(+), 2914 deletions(-) [+] |
line wrap: on
line diff
--- a/main/queueing/doc/Makefile Fri Apr 06 10:07:57 2012 +0000 +++ b/main/queueing/doc/Makefile Fri Apr 06 16:04:05 2012 +0000 @@ -1,6 +1,6 @@ DOC=queueing -CHAPTERS=$(patsubst %.txi,%.texi,$(wildcard *.txi)) -DISTFILES=README INSTALL $(DOC).pdf $(DOC).html $(DOC).texi $(CHAPTERS) $(wildcard demo_*.texi) +CHAPTERS=$(wildcard *.texi) +DISTFILES=README INSTALL $(DOC).pdf $(DOC).html $(DOC).texi $(CHAPTERS) $(wildcard demos/*.texi) $(wildcard help/*.texi) .PHONY: clean dist @@ -13,33 +13,32 @@ info: $(DOC).info INSTALL: installation.texi - rm -f ../INSTALL -$(MAKEINFO) -D INSTALLONLY \ --no-validate --no-headers --no-split --output INSTALL $< -$(DOC).html: $(DOC).texi $(CHAPTERS) +$(DOC).html: $(DOC).texi $(CHAPTERS) DEMOS HELP -$(MAKEINFO) --html --no-split $(DOC).texi -$(DOC).pdf: $(DOC).texi $(CHAPTERS) - texi2pdf -o $(DOC).pdf $< +$(DOC).pdf: $(DOC).texi $(CHAPTERS) DEMOS HELP + texi2pdf -o $(DOC).pdf $(DOC).texi -$(DOC).info: $(DOC).texi $(CHAPTERS) - -$(MAKEINFO) $< - -%.texi: %.txi DOCSTRINGS DEMOS - ../scripts/munge-texi -d DOCSTRINGS < $< > $@ +$(DOC).info: $(DOC).texi $(CHAPTERS) DEMOS HELP + -$(MAKEINFO) $(DOC).texi DOCSTRINGS: $(wildcard ../inst/*.m) (cd ../scripts; ./mkdoc ../inst) > DOCSTRINGS || \rm -f DOCSTRINGS DEMOS: - octave -q grabdemo.m ../inst/ && touch DEMOS + cd demos && octave -p ../../inst/ -q ../grabdemo.m ../../inst/ && touch ../DEMOS + +HELP: + cd help && octave -p ../../inst/ -q ../grabhelp.m ../../inst/ && touch ../HELP dist: ln $(DISTFILES) ../`cat ../fname`/doc/ clean: - \rm -f *.fns *.pdf *.aux *.log *.dvi *.out *.info *.html *.ky *.tp *.toc *.vr *.cp *.fn *.pg *.op *.au *.aus *.cps x.log *~ DOCSTRINGS DEMOS $(CHAPTERS) ../INSTALL demo_*.texi + \rm -f *.fns *.pdf *.aux *.log *.dvi *.out *.info *.html *.ky *.tp *.toc *.vr *.cp *.fn *.pg *.op *.au *.aus *.cps x.log *~ demos/*.texi help/*.texi DOCSTRINGS DEMOS HELP $(CHAPTERS) INSTALL distclean: clean
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/queueing/doc/ack.texi Fri Apr 06 16:04:05 2012 +0000 @@ -0,0 +1,28 @@ +@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 Acknowledgements +@appendix Acknowledgements + +The following people (listed in alphabetical order) contributed to the +@code{queueing} package, either by providing feedback, reporting bugs +or contributing code: Philip Carinhas, Phil Colbourn, Yves Durand, +Marco Guazzone, Dmitry Kolesnikov.
--- a/main/queueing/doc/ack.txi Fri Apr 06 10:07:57 2012 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,28 +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 Acknowledgements -@appendix Acknowledgements - -The following people (listed in alphabetical order) contributed to the -@code{queueing} package, either by providing feedback, reporting bugs -or contributing code: Philip Carinhas, Phil Colbourn, Yves Durand, -Marco Guazzone, Dmitry Kolesnikov.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/queueing/doc/contributing.texi Fri Apr 06 16:04:05 2012 +0000 @@ -0,0 +1,57 @@ +@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 Contributing Guidelines +@appendix Contributing Guidelines + +Contributions and bug reports are @emph{always} welcome. If you want +to contribute to the @code{queueing} package, here are some +guidelines: + +@itemize + +@item If you are contributing a new function, please embed proper +documentation within the function itself. The documentation must be in +@code{texinfo} format, so that it can be extracted and formatted into +the printable manual. See the existing functions of the +@code{queueing} package for the documentation style. + +@item Make sure that each new function +properly checks the validity of its input parameters. For example, +each function accepting vectors should check whether the dimensions +match. + +@item Provide bibliographic references for each new algorithm you +contribute. If your implementation differs in some way from the +reference you give, please describe how and why your implementation +differs. Add references to the @file{doc/references.txi} file. + +@item Include test and demo blocks with your code. +Test blocks are particularly important, since most algorithms tend to +be quite tricky to implement correctly. If appropriate, test blocks +should also verify that the function fails on incorrect input +parameters. + +@end itemize + +Send your contribution to Moreno Marzolla +(@email{marzolla@@cs.unibo.it}). If you are just a user of this +package and find it useful, let me know by dropping me a line. Thanks.
--- a/main/queueing/doc/contributing.txi Fri Apr 06 10:07:57 2012 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,57 +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 Contributing Guidelines -@appendix Contributing Guidelines - -Contributions and bug reports are @emph{always} welcome. If you want -to contribute to the @code{queueing} package, here are some -guidelines: - -@itemize - -@item If you are contributing a new function, please embed proper -documentation within the function itself. The documentation must be in -@code{texinfo} format, so that it can be extracted and formatted into -the printable manual. See the existing functions of the -@code{queueing} package for the documentation style. - -@item Make sure that each new function -properly checks the validity of its input parameters. For example, -each function accepting vectors should check whether the dimensions -match. - -@item Provide bibliographic references for each new algorithm you -contribute. If your implementation differs in some way from the -reference you give, please describe how and why your implementation -differs. Add references to the @file{doc/references.txi} file. - -@item Include test and demo blocks with your code. -Test blocks are particularly important, since most algorithms tend to -be quite tricky to implement correctly. If appropriate, test blocks -should also verify that the function fails on incorrect input -parameters. - -@end itemize - -Send your contribution to Moreno Marzolla -(@email{marzolla@@cs.unibo.it}). If you are just a user of this -package and find it useful, let me know by dropping me a line. Thanks.
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/queueing/doc/gettingstarted.texi Fri Apr 06 16:04:05 2012 +0000 @@ -0,0 +1,316 @@ +@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/gettingstarted.txi Fri Apr 06 10:07:57 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) -
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/queueing/doc/gpl.texi Fri Apr 06 16:04:05 2012 +0000 @@ -0,0 +1,718 @@ +@node Copying +@appendix GNU GENERAL PUBLIC LICENSE +@cindex warranty +@cindex copyright + +@center Version 3, 29 June 2007 + +@display +Copyright @copyright{} 2007 Free Software Foundation, Inc. @url{http://fsf.org/} + +Everyone is permitted to copy and distribute verbatim copies of this +license document, but changing it is not allowed. +@end display + +@heading Preamble + +The GNU General Public License is a free, copyleft license for +software and other kinds of works. + +The licenses for most software and other practical works are designed +to take away your freedom to share and change the works. By contrast, +the GNU General Public License is intended to guarantee your freedom +to share and change all versions of a program---to make sure it remains +free software for all its users. We, the Free Software Foundation, +use the GNU General Public License for most of our software; it +applies also to any other work released this way by its authors. You +can apply it to your programs, too. + +When we speak of free software, we are referring to freedom, not +price. Our General Public Licenses are designed to make sure that you +have the freedom to distribute copies of free software (and charge for +them if you wish), that you receive source code or can get it if you +want it, that you can change the software or use pieces of it in new +free programs, and that you know you can do these things. + +To protect your rights, we need to prevent others from denying you +these rights or asking you to surrender the rights. Therefore, you +have certain responsibilities if you distribute copies of the +software, or if you modify it: responsibilities to respect the freedom +of others. + +For example, if you distribute copies of such a program, whether +gratis or for a fee, you must pass on to the recipients the same +freedoms that you received. You must make sure that they, too, +receive or can get the source code. And you must show them these +terms so they know their rights. + +Developers that use the GNU GPL protect your rights with two steps: +(1) assert copyright on the software, and (2) offer you this License +giving you legal permission to copy, distribute and/or modify it. + +For the developers' and authors' protection, the GPL clearly explains +that there is no warranty for this free software. For both users' and +authors' sake, the GPL requires that modified versions be marked as +changed, so that their problems will not be attributed erroneously to +authors of previous versions. + +Some devices are designed to deny users access to install or run +modified versions of the software inside them, although the +manufacturer can do so. This is fundamentally incompatible with the +aim of protecting users' freedom to change the software. The +systematic pattern of such abuse occurs in the area of products for +individuals to use, which is precisely where it is most unacceptable. +Therefore, we have designed this version of the GPL to prohibit the +practice for those products. If such problems arise substantially in +other domains, we stand ready to extend this provision to those +domains in future versions of the GPL, as needed to protect the +freedom of users. + +Finally, every program is threatened constantly by software patents. +States should not allow patents to restrict development and use of +software on general-purpose computers, but in those that do, we wish +to avoid the special danger that patents applied to a free program +could make it effectively proprietary. To prevent this, the GPL +assures that patents cannot be used to render the program non-free. + +The precise terms and conditions for copying, distribution and +modification follow. + +@heading TERMS AND CONDITIONS + +@enumerate 0 +@item Definitions. + +``This License'' refers to version 3 of the GNU General Public License. + +``Copyright'' also means copyright-like laws that apply to other kinds +of works, such as semiconductor masks. + +``The Program'' refers to any copyrightable work licensed under this +License. Each licensee is addressed as ``you''. ``Licensees'' and +``recipients'' may be individuals or organizations. + +To ``modify'' a work means to copy from or adapt all or part of the work +in a fashion requiring copyright permission, other than the making of +an exact copy. The resulting work is called a ``modified version'' of +the earlier work or a work ``based on'' the earlier work. + +A ``covered work'' means either the unmodified Program or a work based +on the Program. + +To ``propagate'' a work means to do anything with it that, without +permission, would make you directly or secondarily liable for +infringement under applicable copyright law, except executing it on a +computer or modifying a private copy. Propagation includes copying, +distribution (with or without modification), making available to the +public, and in some countries other activities as well. + +To ``convey'' a work means any kind of propagation that enables other +parties to make or receive copies. Mere interaction with a user +through a computer network, with no transfer of a copy, is not +conveying. + +An interactive user interface displays ``Appropriate Legal Notices'' to +the extent that it includes a convenient and prominently visible +feature that (1) displays an appropriate copyright notice, and (2) +tells the user that there is no warranty for the work (except to the +extent that warranties are provided), that licensees may convey the +work under this License, and how to view a copy of this License. If +the interface presents a list of user commands or options, such as a +menu, a prominent item in the list meets this criterion. + +@item Source Code. + +The ``source code'' for a work means the preferred form of the work for +making modifications to it. ``Object code'' means any non-source form +of a work. + +A ``Standard Interface'' means an interface that either is an official +standard defined by a recognized standards body, or, in the case of +interfaces specified for a particular programming language, one that +is widely used among developers working in that language. + +The ``System Libraries'' of an executable work include anything, other +than the work as a whole, that (a) is included in the normal form of +packaging a Major Component, but which is not part of that Major +Component, and (b) serves only to enable use of the work with that +Major Component, or to implement a Standard Interface for which an +implementation is available to the public in source code form. A +``Major Component'', in this context, means a major essential component +(kernel, window system, and so on) of the specific operating system +(if any) on which the executable work runs, or a compiler used to +produce the work, or an object code interpreter used to run it. + +The ``Corresponding Source'' for a work in object code form means all +the source code needed to generate, install, and (for an executable +work) run the object code and to modify the work, including scripts to +control those activities. However, it does not include the work's +System Libraries, or general-purpose tools or generally available free +programs which are used unmodified in performing those activities but +which are not part of the work. For example, Corresponding Source +includes interface definition files associated with source files for +the work, and the source code for shared libraries and dynamically +linked subprograms that the work is specifically designed to require, +such as by intimate data communication or control flow between those +subprograms and other parts of the work. + +The Corresponding Source need not include anything that users can +regenerate automatically from other parts of the Corresponding Source. + +The Corresponding Source for a work in source code form is that same +work. + +@item Basic Permissions. + +All rights granted under this License are granted for the term of +copyright on the Program, and are irrevocable provided the stated +conditions are met. This License explicitly affirms your unlimited +permission to run the unmodified Program. The output from running a +covered work is covered by this License only if the output, given its +content, constitutes a covered work. This License acknowledges your +rights of fair use or other equivalent, as provided by copyright law. + +You may make, run and propagate covered works that you do not convey, +without conditions so long as your license otherwise remains in force. +You may convey covered works to others for the sole purpose of having +them make modifications exclusively for you, or provide you with +facilities for running those works, provided that you comply with the +terms of this License in conveying all material for which you do not +control copyright. Those thus making or running the covered works for +you must do so exclusively on your behalf, under your direction and +control, on terms that prohibit them from making any copies of your +copyrighted material outside their relationship with you. + +Conveying under any other circumstances is permitted solely under the +conditions stated below. Sublicensing is not allowed; section 10 +makes it unnecessary. + +@item Protecting Users' Legal Rights From Anti-Circumvention Law. + +No covered work shall be deemed part of an effective technological +measure under any applicable law fulfilling obligations under article +11 of the WIPO copyright treaty adopted on 20 December 1996, or +similar laws prohibiting or restricting circumvention of such +measures. + +When you convey a covered work, you waive any legal power to forbid +circumvention of technological measures to the extent such +circumvention is effected by exercising rights under this License with +respect to the covered work, and you disclaim any intention to limit +operation or modification of the work as a means of enforcing, against +the work's users, your or third parties' legal rights to forbid +circumvention of technological measures. + +@item Conveying Verbatim Copies. + +You may convey verbatim copies of the Program's source code as you +receive it, in any medium, provided that you conspicuously and +appropriately publish on each copy an appropriate copyright notice; +keep intact all notices stating that this License and any +non-permissive terms added in accord with section 7 apply to the code; +keep intact all notices of the absence of any warranty; and give all +recipients a copy of this License along with the Program. + +You may charge any price or no price for each copy that you convey, +and you may offer support or warranty protection for a fee. + +@item Conveying Modified Source Versions. + +You may convey a work based on the Program, or the modifications to +produce it from the Program, in the form of source code under the +terms of section 4, provided that you also meet all of these +conditions: + +@enumerate a +@item +The work must carry prominent notices stating that you modified it, +and giving a relevant date. + +@item +The work must carry prominent notices stating that it is released +under this License and any conditions added under section 7. This +requirement modifies the requirement in section 4 to ``keep intact all +notices''. + +@item +You must license the entire work, as a whole, under this License to +anyone who comes into possession of a copy. This License will +therefore apply, along with any applicable section 7 additional terms, +to the whole of the work, and all its parts, regardless of how they +are packaged. This License gives no permission to license the work in +any other way, but it does not invalidate such permission if you have +separately received it. + +@item +If the work has interactive user interfaces, each must display +Appropriate Legal Notices; however, if the Program has interactive +interfaces that do not display Appropriate Legal Notices, your work +need not make them do so. +@end enumerate + +A compilation of a covered work with other separate and independent +works, which are not by their nature extensions of the covered work, +and which are not combined with it such as to form a larger program, +in or on a volume of a storage or distribution medium, is called an +``aggregate'' if the compilation and its resulting copyright are not +used to limit the access or legal rights of the compilation's users +beyond what the individual works permit. Inclusion of a covered work +in an aggregate does not cause this License to apply to the other +parts of the aggregate. + +@item Conveying Non-Source Forms. + +You may convey a covered work in object code form under the terms of +sections 4 and 5, provided that you also convey the machine-readable +Corresponding Source under the terms of this License, in one of these +ways: + +@enumerate a +@item +Convey the object code in, or embodied in, a physical product +(including a physical distribution medium), accompanied by the +Corresponding Source fixed on a durable physical medium customarily +used for software interchange. + +@item +Convey the object code in, or embodied in, a physical product +(including a physical distribution medium), accompanied by a written +offer, valid for at least three years and valid for as long as you +offer spare parts or customer support for that product model, to give +anyone who possesses the object code either (1) a copy of the +Corresponding Source for all the software in the product that is +covered by this License, on a durable physical medium customarily used +for software interchange, for a price no more than your reasonable +cost of physically performing this conveying of source, or (2) access +to copy the Corresponding Source from a network server at no charge. + +@item +Convey individual copies of the object code with a copy of the written +offer to provide the Corresponding Source. This alternative is +allowed only occasionally and noncommercially, and only if you +received the object code with such an offer, in accord with subsection +6b. + +@item +Convey the object code by offering access from a designated place +(gratis or for a charge), and offer equivalent access to the +Corresponding Source in the same way through the same place at no +further charge. You need not require recipients to copy the +Corresponding Source along with the object code. If the place to copy +the object code is a network server, the Corresponding Source may be +on a different server (operated by you or a third party) that supports +equivalent copying facilities, provided you maintain clear directions +next to the object code saying where to find the Corresponding Source. +Regardless of what server hosts the Corresponding Source, you remain +obligated to ensure that it is available for as long as needed to +satisfy these requirements. + +@item +Convey the object code using peer-to-peer transmission, provided you +inform other peers where the object code and Corresponding Source of +the work are being offered to the general public at no charge under +subsection 6d. + +@end enumerate + +A separable portion of the object code, whose source code is excluded +from the Corresponding Source as a System Library, need not be +included in conveying the object code work. + +A ``User Product'' is either (1) a ``consumer product'', which means any +tangible personal property which is normally used for personal, +family, or household purposes, or (2) anything designed or sold for +incorporation into a dwelling. In determining whether a product is a +consumer product, doubtful cases shall be resolved in favor of +coverage. For a particular product received by a particular user, +``normally used'' refers to a typical or common use of that class of +product, regardless of the status of the particular user or of the way +in which the particular user actually uses, or expects or is expected +to use, the product. A product is a consumer product regardless of +whether the product has substantial commercial, industrial or +non-consumer uses, unless such uses represent the only significant +mode of use of the product. + +``Installation Information'' for a User Product means any methods, +procedures, authorization keys, or other information required to +install and execute modified versions of a covered work in that User +Product from a modified version of its Corresponding Source. The +information must suffice to ensure that the continued functioning of +the modified object code is in no case prevented or interfered with +solely because modification has been made. + +If you convey an object code work under this section in, or with, or +specifically for use in, a User Product, and the conveying occurs as +part of a transaction in which the right of possession and use of the +User Product is transferred to the recipient in perpetuity or for a +fixed term (regardless of how the transaction is characterized), the +Corresponding Source conveyed under this section must be accompanied +by the Installation Information. But this requirement does not apply +if neither you nor any third party retains the ability to install +modified object code on the User Product (for example, the work has +been installed in ROM). + +The requirement to provide Installation Information does not include a +requirement to continue to provide support service, warranty, or +updates for a work that has been modified or installed by the +recipient, or for the User Product in which it has been modified or +installed. Access to a network may be denied when the modification +itself materially and adversely affects the operation of the network +or violates the rules and protocols for communication across the +network. + +Corresponding Source conveyed, and Installation Information provided, +in accord with this section must be in a format that is publicly +documented (and with an implementation available to the public in +source code form), and must require no special password or key for +unpacking, reading or copying. + +@item Additional Terms. + +``Additional permissions'' are terms that supplement the terms of this +License by making exceptions from one or more of its conditions. +Additional permissions that are applicable to the entire Program shall +be treated as though they were included in this License, to the extent +that they are valid under applicable law. If additional permissions +apply only to part of the Program, that part may be used separately +under those permissions, but the entire Program remains governed by +this License without regard to the additional permissions. + +When you convey a copy of a covered work, you may at your option +remove any additional permissions from that copy, or from any part of +it. (Additional permissions may be written to require their own +removal in certain cases when you modify the work.) You may place +additional permissions on material, added by you to a covered work, +for which you have or can give appropriate copyright permission. + +Notwithstanding any other provision of this License, for material you +add to a covered work, you may (if authorized by the copyright holders +of that material) supplement the terms of this License with terms: + +@enumerate a +@item +Disclaiming warranty or limiting liability differently from the terms +of sections 15 and 16 of this License; or + +@item +Requiring preservation of specified reasonable legal notices or author +attributions in that material or in the Appropriate Legal Notices +displayed by works containing it; or + +@item +Prohibiting misrepresentation of the origin of that material, or +requiring that modified versions of such material be marked in +reasonable ways as different from the original version; or + +@item +Limiting the use for publicity purposes of names of licensors or +authors of the material; or + +@item +Declining to grant rights under trademark law for use of some trade +names, trademarks, or service marks; or + +@item +Requiring indemnification of licensors and authors of that material by +anyone who conveys the material (or modified versions of it) with +contractual assumptions of liability to the recipient, for any +liability that these contractual assumptions directly impose on those +licensors and authors. +@end enumerate + +All other non-permissive additional terms are considered ``further +restrictions'' within the meaning of section 10. If the Program as you +received it, or any part of it, contains a notice stating that it is +governed by this License along with a term that is a further +restriction, you may remove that term. If a license document contains +a further restriction but permits relicensing or conveying under this +License, you may add to a covered work material governed by the terms +of that license document, provided that the further restriction does +not survive such relicensing or conveying. + +If you add terms to a covered work in accord with this section, you +must place, in the relevant source files, a statement of the +additional terms that apply to those files, or a notice indicating +where to find the applicable terms. + +Additional terms, permissive or non-permissive, may be stated in the +form of a separately written license, or stated as exceptions; the +above requirements apply either way. + +@item Termination. + +You may not propagate or modify a covered work except as expressly +provided under this License. Any attempt otherwise to propagate or +modify it is void, and will automatically terminate your rights under +this License (including any patent licenses granted under the third +paragraph of section 11). + +However, if you cease all violation of this License, then your license +from a particular copyright holder is reinstated (a) provisionally, +unless and until the copyright holder explicitly and finally +terminates your license, and (b) permanently, if the copyright holder +fails to notify you of the violation by some reasonable means prior to +60 days after the cessation. + +Moreover, your license from a particular copyright holder is +reinstated permanently if the copyright holder notifies you of the +violation by some reasonable means, this is the first time you have +received notice of violation of this License (for any work) from that +copyright holder, and you cure the violation prior to 30 days after +your receipt of the notice. + +Termination of your rights under this section does not terminate the +licenses of parties who have received copies or rights from you under +this License. If your rights have been terminated and not permanently +reinstated, you do not qualify to receive new licenses for the same +material under section 10. + +@item Acceptance Not Required for Having Copies. + +You are not required to accept this License in order to receive or run +a copy of the Program. Ancillary propagation of a covered work +occurring solely as a consequence of using peer-to-peer transmission +to receive a copy likewise does not require acceptance. However, +nothing other than this License grants you permission to propagate or +modify any covered work. These actions infringe copyright if you do +not accept this License. Therefore, by modifying or propagating a +covered work, you indicate your acceptance of this License to do so. + +@item Automatic Licensing of Downstream Recipients. + +Each time you convey a covered work, the recipient automatically +receives a license from the original licensors, to run, modify and +propagate that work, subject to this License. You are not responsible +for enforcing compliance by third parties with this License. + +An ``entity transaction'' is a transaction transferring control of an +organization, or substantially all assets of one, or subdividing an +organization, or merging organizations. If propagation of a covered +work results from an entity transaction, each party to that +transaction who receives a copy of the work also receives whatever +licenses to the work the party's predecessor in interest had or could +give under the previous paragraph, plus a right to possession of the +Corresponding Source of the work from the predecessor in interest, if +the predecessor has it or can get it with reasonable efforts. + +You may not impose any further restrictions on the exercise of the +rights granted or affirmed under this License. For example, you may +not impose a license fee, royalty, or other charge for exercise of +rights granted under this License, and you may not initiate litigation +(including a cross-claim or counterclaim in a lawsuit) alleging that +any patent claim is infringed by making, using, selling, offering for +sale, or importing the Program or any portion of it. + +@item Patents. + +A ``contributor'' is a copyright holder who authorizes use under this +License of the Program or a work on which the Program is based. The +work thus licensed is called the contributor's ``contributor version''. + +A contributor's ``essential patent claims'' are all patent claims owned +or controlled by the contributor, whether already acquired or +hereafter acquired, that would be infringed by some manner, permitted +by this License, of making, using, or selling its contributor version, +but do not include claims that would be infringed only as a +consequence of further modification of the contributor version. For +purposes of this definition, ``control'' includes the right to grant +patent sublicenses in a manner consistent with the requirements of +this License. + +Each contributor grants you a non-exclusive, worldwide, royalty-free +patent license under the contributor's essential patent claims, to +make, use, sell, offer for sale, import and otherwise run, modify and +propagate the contents of its contributor version. + +In the following three paragraphs, a ``patent license'' is any express +agreement or commitment, however denominated, not to enforce a patent +(such as an express permission to practice a patent or covenant not to +sue for patent infringement). To ``grant'' such a patent license to a +party means to make such an agreement or commitment not to enforce a +patent against the party. + +If you convey a covered work, knowingly relying on a patent license, +and the Corresponding Source of the work is not available for anyone +to copy, free of charge and under the terms of this License, through a +publicly available network server or other readily accessible means, +then you must either (1) cause the Corresponding Source to be so +available, or (2) arrange to deprive yourself of the benefit of the +patent license for this particular work, or (3) arrange, in a manner +consistent with the requirements of this License, to extend the patent +license to downstream recipients. ``Knowingly relying'' means you have +actual knowledge that, but for the patent license, your conveying the +covered work in a country, or your recipient's use of the covered work +in a country, would infringe one or more identifiable patents in that +country that you have reason to believe are valid. + +If, pursuant to or in connection with a single transaction or +arrangement, you convey, or propagate by procuring conveyance of, a +covered work, and grant a patent license to some of the parties +receiving the covered work authorizing them to use, propagate, modify +or convey a specific copy of the covered work, then the patent license +you grant is automatically extended to all recipients of the covered +work and works based on it. + +A patent license is ``discriminatory'' if it does not include within the +scope of its coverage, prohibits the exercise of, or is conditioned on +the non-exercise of one or more of the rights that are specifically +granted under this License. You may not convey a covered work if you +are a party to an arrangement with a third party that is in the +business of distributing software, under which you make payment to the +third party based on the extent of your activity of conveying the +work, and under which the third party grants, to any of the parties +who would receive the covered work from you, a discriminatory patent +license (a) in connection with copies of the covered work conveyed by +you (or copies made from those copies), or (b) primarily for and in +connection with specific products or compilations that contain the +covered work, unless you entered into that arrangement, or that patent +license was granted, prior to 28 March 2007. + +Nothing in this License shall be construed as excluding or limiting +any implied license or other defenses to infringement that may +otherwise be available to you under applicable patent law. + +@item No Surrender of Others' Freedom. + +If conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot convey +a covered work so as to satisfy simultaneously your obligations under +this License and any other pertinent obligations, then as a +consequence you may not convey it at all. For example, if you agree +to terms that obligate you to collect a royalty for further conveying +from those to whom you convey the Program, the only way you could +satisfy both those terms and this License would be to refrain entirely +from conveying the Program. + +@item Use with the GNU Affero General Public License. + +Notwithstanding any other provision of this License, you have +permission to link or combine any covered work with a work licensed +under version 3 of the GNU Affero General Public License into a single +combined work, and to convey the resulting work. The terms of this +License will continue to apply to the part which is the covered work, +but the special requirements of the GNU Affero General Public License, +section 13, concerning interaction through a network will apply to the +combination as such. + +@item Revised Versions of this License. + +The Free Software Foundation may publish revised and/or new versions +of the GNU General Public License from time to time. Such new +versions will be similar in spirit to the present version, but may +differ in detail to address new problems or concerns. + +Each version is given a distinguishing version number. If the Program +specifies that a certain numbered version of the GNU General Public +License ``or any later version'' applies to it, you have the option of +following the terms and conditions either of that numbered version or +of any later version published by the Free Software Foundation. If +the Program does not specify a version number of the GNU General +Public License, you may choose any version ever published by the Free +Software Foundation. + +If the Program specifies that a proxy can decide which future versions +of the GNU General Public License can be used, that proxy's public +statement of acceptance of a version permanently authorizes you to +choose that version for the Program. + +Later license versions may give you additional or different +permissions. However, no additional obligations are imposed on any +author or copyright holder as a result of your choosing to follow a +later version. + +@item Disclaimer of Warranty. + +THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY +APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT +HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM ``AS IS'' WITHOUT +WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND +PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE PROGRAM PROVE +DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR +CORRECTION. + +@item Limitation of Liability. + +IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING +WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MODIFIES AND/OR +CONVEYS THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, +INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES +ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT +NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR +LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM +TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER +PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. + +@item Interpretation of Sections 15 and 16. + +If the disclaimer of warranty and limitation of liability provided +above cannot be given local legal effect according to their terms, +reviewing courts shall apply local law that most closely approximates +an absolute waiver of all civil liability in connection with the +Program, unless a warranty or assumption of liability accompanies a +copy of the Program in return for a fee. + +@end enumerate + +@heading END OF TERMS AND CONDITIONS + +@heading How to Apply These Terms to Your New Programs + +If you develop a new program, and you want it to be of the greatest +possible use to the public, the best way to achieve this is to make it +free software which everyone can redistribute and change under these +terms. + +To do so, attach the following notices to the program. It is safest +to attach them to the start of each source file to most effectively +state the exclusion of warranty; and each file should have at least +the ``copyright'' line and a pointer to where the full notice is found. + +@smallexample +@var{one line to give the program's name and a brief idea of what it does.} +Copyright (C) @var{year} @var{name of author} + +This program 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. + +This program 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 this program. If not, see @url{http://www.gnu.org/licenses/}. +@end smallexample + +Also add information on how to contact you by electronic and paper mail. + +If the program does terminal interaction, make it output a short +notice like this when it starts in an interactive mode: + +@smallexample +@var{program} Copyright (C) @var{year} @var{name of author} +This program comes with ABSOLUTELY NO WARRANTY; for details type @samp{show w}. +This is free software, and you are welcome to redistribute it +under certain conditions; type @samp{show c} for details. +@end smallexample + +The hypothetical commands @samp{show w} and @samp{show c} should show +the appropriate parts of the General Public License. Of course, your +program's commands might be different; for a GUI interface, you would +use an ``about box''. + +You should also get your employer (if you work as a programmer) or school, +if any, to sign a ``copyright disclaimer'' for the program, if necessary. +For more information on this, and how to apply and follow the GNU GPL, see +@url{http://www.gnu.org/licenses/}. + +The GNU General Public License does not permit incorporating your +program into proprietary programs. If your program is a subroutine +library, you may consider it more useful to permit linking proprietary +applications with the library. If this is what you want to do, use +the GNU Lesser General Public License instead of this License. But +first, please read @url{http://www.gnu.org/philosophy/why-not-lgpl.html}.
--- a/main/queueing/doc/gpl.txi Fri Apr 06 10:07:57 2012 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,718 +0,0 @@ -@node Copying -@appendix GNU GENERAL PUBLIC LICENSE -@cindex warranty -@cindex copyright - -@center Version 3, 29 June 2007 - -@display -Copyright @copyright{} 2007 Free Software Foundation, Inc. @url{http://fsf.org/} - -Everyone is permitted to copy and distribute verbatim copies of this -license document, but changing it is not allowed. -@end display - -@heading Preamble - -The GNU General Public License is a free, copyleft license for -software and other kinds of works. - -The licenses for most software and other practical works are designed -to take away your freedom to share and change the works. By contrast, -the GNU General Public License is intended to guarantee your freedom -to share and change all versions of a program---to make sure it remains -free software for all its users. We, the Free Software Foundation, -use the GNU General Public License for most of our software; it -applies also to any other work released this way by its authors. You -can apply it to your programs, too. - -When we speak of free software, we are referring to freedom, not -price. Our General Public Licenses are designed to make sure that you -have the freedom to distribute copies of free software (and charge for -them if you wish), that you receive source code or can get it if you -want it, that you can change the software or use pieces of it in new -free programs, and that you know you can do these things. - -To protect your rights, we need to prevent others from denying you -these rights or asking you to surrender the rights. Therefore, you -have certain responsibilities if you distribute copies of the -software, or if you modify it: responsibilities to respect the freedom -of others. - -For example, if you distribute copies of such a program, whether -gratis or for a fee, you must pass on to the recipients the same -freedoms that you received. You must make sure that they, too, -receive or can get the source code. And you must show them these -terms so they know their rights. - -Developers that use the GNU GPL protect your rights with two steps: -(1) assert copyright on the software, and (2) offer you this License -giving you legal permission to copy, distribute and/or modify it. - -For the developers' and authors' protection, the GPL clearly explains -that there is no warranty for this free software. For both users' and -authors' sake, the GPL requires that modified versions be marked as -changed, so that their problems will not be attributed erroneously to -authors of previous versions. - -Some devices are designed to deny users access to install or run -modified versions of the software inside them, although the -manufacturer can do so. This is fundamentally incompatible with the -aim of protecting users' freedom to change the software. The -systematic pattern of such abuse occurs in the area of products for -individuals to use, which is precisely where it is most unacceptable. -Therefore, we have designed this version of the GPL to prohibit the -practice for those products. If such problems arise substantially in -other domains, we stand ready to extend this provision to those -domains in future versions of the GPL, as needed to protect the -freedom of users. - -Finally, every program is threatened constantly by software patents. -States should not allow patents to restrict development and use of -software on general-purpose computers, but in those that do, we wish -to avoid the special danger that patents applied to a free program -could make it effectively proprietary. To prevent this, the GPL -assures that patents cannot be used to render the program non-free. - -The precise terms and conditions for copying, distribution and -modification follow. - -@heading TERMS AND CONDITIONS - -@enumerate 0 -@item Definitions. - -``This License'' refers to version 3 of the GNU General Public License. - -``Copyright'' also means copyright-like laws that apply to other kinds -of works, such as semiconductor masks. - -``The Program'' refers to any copyrightable work licensed under this -License. Each licensee is addressed as ``you''. ``Licensees'' and -``recipients'' may be individuals or organizations. - -To ``modify'' a work means to copy from or adapt all or part of the work -in a fashion requiring copyright permission, other than the making of -an exact copy. The resulting work is called a ``modified version'' of -the earlier work or a work ``based on'' the earlier work. - -A ``covered work'' means either the unmodified Program or a work based -on the Program. - -To ``propagate'' a work means to do anything with it that, without -permission, would make you directly or secondarily liable for -infringement under applicable copyright law, except executing it on a -computer or modifying a private copy. Propagation includes copying, -distribution (with or without modification), making available to the -public, and in some countries other activities as well. - -To ``convey'' a work means any kind of propagation that enables other -parties to make or receive copies. Mere interaction with a user -through a computer network, with no transfer of a copy, is not -conveying. - -An interactive user interface displays ``Appropriate Legal Notices'' to -the extent that it includes a convenient and prominently visible -feature that (1) displays an appropriate copyright notice, and (2) -tells the user that there is no warranty for the work (except to the -extent that warranties are provided), that licensees may convey the -work under this License, and how to view a copy of this License. If -the interface presents a list of user commands or options, such as a -menu, a prominent item in the list meets this criterion. - -@item Source Code. - -The ``source code'' for a work means the preferred form of the work for -making modifications to it. ``Object code'' means any non-source form -of a work. - -A ``Standard Interface'' means an interface that either is an official -standard defined by a recognized standards body, or, in the case of -interfaces specified for a particular programming language, one that -is widely used among developers working in that language. - -The ``System Libraries'' of an executable work include anything, other -than the work as a whole, that (a) is included in the normal form of -packaging a Major Component, but which is not part of that Major -Component, and (b) serves only to enable use of the work with that -Major Component, or to implement a Standard Interface for which an -implementation is available to the public in source code form. A -``Major Component'', in this context, means a major essential component -(kernel, window system, and so on) of the specific operating system -(if any) on which the executable work runs, or a compiler used to -produce the work, or an object code interpreter used to run it. - -The ``Corresponding Source'' for a work in object code form means all -the source code needed to generate, install, and (for an executable -work) run the object code and to modify the work, including scripts to -control those activities. However, it does not include the work's -System Libraries, or general-purpose tools or generally available free -programs which are used unmodified in performing those activities but -which are not part of the work. For example, Corresponding Source -includes interface definition files associated with source files for -the work, and the source code for shared libraries and dynamically -linked subprograms that the work is specifically designed to require, -such as by intimate data communication or control flow between those -subprograms and other parts of the work. - -The Corresponding Source need not include anything that users can -regenerate automatically from other parts of the Corresponding Source. - -The Corresponding Source for a work in source code form is that same -work. - -@item Basic Permissions. - -All rights granted under this License are granted for the term of -copyright on the Program, and are irrevocable provided the stated -conditions are met. This License explicitly affirms your unlimited -permission to run the unmodified Program. The output from running a -covered work is covered by this License only if the output, given its -content, constitutes a covered work. This License acknowledges your -rights of fair use or other equivalent, as provided by copyright law. - -You may make, run and propagate covered works that you do not convey, -without conditions so long as your license otherwise remains in force. -You may convey covered works to others for the sole purpose of having -them make modifications exclusively for you, or provide you with -facilities for running those works, provided that you comply with the -terms of this License in conveying all material for which you do not -control copyright. Those thus making or running the covered works for -you must do so exclusively on your behalf, under your direction and -control, on terms that prohibit them from making any copies of your -copyrighted material outside their relationship with you. - -Conveying under any other circumstances is permitted solely under the -conditions stated below. Sublicensing is not allowed; section 10 -makes it unnecessary. - -@item Protecting Users' Legal Rights From Anti-Circumvention Law. - -No covered work shall be deemed part of an effective technological -measure under any applicable law fulfilling obligations under article -11 of the WIPO copyright treaty adopted on 20 December 1996, or -similar laws prohibiting or restricting circumvention of such -measures. - -When you convey a covered work, you waive any legal power to forbid -circumvention of technological measures to the extent such -circumvention is effected by exercising rights under this License with -respect to the covered work, and you disclaim any intention to limit -operation or modification of the work as a means of enforcing, against -the work's users, your or third parties' legal rights to forbid -circumvention of technological measures. - -@item Conveying Verbatim Copies. - -You may convey verbatim copies of the Program's source code as you -receive it, in any medium, provided that you conspicuously and -appropriately publish on each copy an appropriate copyright notice; -keep intact all notices stating that this License and any -non-permissive terms added in accord with section 7 apply to the code; -keep intact all notices of the absence of any warranty; and give all -recipients a copy of this License along with the Program. - -You may charge any price or no price for each copy that you convey, -and you may offer support or warranty protection for a fee. - -@item Conveying Modified Source Versions. - -You may convey a work based on the Program, or the modifications to -produce it from the Program, in the form of source code under the -terms of section 4, provided that you also meet all of these -conditions: - -@enumerate a -@item -The work must carry prominent notices stating that you modified it, -and giving a relevant date. - -@item -The work must carry prominent notices stating that it is released -under this License and any conditions added under section 7. This -requirement modifies the requirement in section 4 to ``keep intact all -notices''. - -@item -You must license the entire work, as a whole, under this License to -anyone who comes into possession of a copy. This License will -therefore apply, along with any applicable section 7 additional terms, -to the whole of the work, and all its parts, regardless of how they -are packaged. This License gives no permission to license the work in -any other way, but it does not invalidate such permission if you have -separately received it. - -@item -If the work has interactive user interfaces, each must display -Appropriate Legal Notices; however, if the Program has interactive -interfaces that do not display Appropriate Legal Notices, your work -need not make them do so. -@end enumerate - -A compilation of a covered work with other separate and independent -works, which are not by their nature extensions of the covered work, -and which are not combined with it such as to form a larger program, -in or on a volume of a storage or distribution medium, is called an -``aggregate'' if the compilation and its resulting copyright are not -used to limit the access or legal rights of the compilation's users -beyond what the individual works permit. Inclusion of a covered work -in an aggregate does not cause this License to apply to the other -parts of the aggregate. - -@item Conveying Non-Source Forms. - -You may convey a covered work in object code form under the terms of -sections 4 and 5, provided that you also convey the machine-readable -Corresponding Source under the terms of this License, in one of these -ways: - -@enumerate a -@item -Convey the object code in, or embodied in, a physical product -(including a physical distribution medium), accompanied by the -Corresponding Source fixed on a durable physical medium customarily -used for software interchange. - -@item -Convey the object code in, or embodied in, a physical product -(including a physical distribution medium), accompanied by a written -offer, valid for at least three years and valid for as long as you -offer spare parts or customer support for that product model, to give -anyone who possesses the object code either (1) a copy of the -Corresponding Source for all the software in the product that is -covered by this License, on a durable physical medium customarily used -for software interchange, for a price no more than your reasonable -cost of physically performing this conveying of source, or (2) access -to copy the Corresponding Source from a network server at no charge. - -@item -Convey individual copies of the object code with a copy of the written -offer to provide the Corresponding Source. This alternative is -allowed only occasionally and noncommercially, and only if you -received the object code with such an offer, in accord with subsection -6b. - -@item -Convey the object code by offering access from a designated place -(gratis or for a charge), and offer equivalent access to the -Corresponding Source in the same way through the same place at no -further charge. You need not require recipients to copy the -Corresponding Source along with the object code. If the place to copy -the object code is a network server, the Corresponding Source may be -on a different server (operated by you or a third party) that supports -equivalent copying facilities, provided you maintain clear directions -next to the object code saying where to find the Corresponding Source. -Regardless of what server hosts the Corresponding Source, you remain -obligated to ensure that it is available for as long as needed to -satisfy these requirements. - -@item -Convey the object code using peer-to-peer transmission, provided you -inform other peers where the object code and Corresponding Source of -the work are being offered to the general public at no charge under -subsection 6d. - -@end enumerate - -A separable portion of the object code, whose source code is excluded -from the Corresponding Source as a System Library, need not be -included in conveying the object code work. - -A ``User Product'' is either (1) a ``consumer product'', which means any -tangible personal property which is normally used for personal, -family, or household purposes, or (2) anything designed or sold for -incorporation into a dwelling. In determining whether a product is a -consumer product, doubtful cases shall be resolved in favor of -coverage. For a particular product received by a particular user, -``normally used'' refers to a typical or common use of that class of -product, regardless of the status of the particular user or of the way -in which the particular user actually uses, or expects or is expected -to use, the product. A product is a consumer product regardless of -whether the product has substantial commercial, industrial or -non-consumer uses, unless such uses represent the only significant -mode of use of the product. - -``Installation Information'' for a User Product means any methods, -procedures, authorization keys, or other information required to -install and execute modified versions of a covered work in that User -Product from a modified version of its Corresponding Source. The -information must suffice to ensure that the continued functioning of -the modified object code is in no case prevented or interfered with -solely because modification has been made. - -If you convey an object code work under this section in, or with, or -specifically for use in, a User Product, and the conveying occurs as -part of a transaction in which the right of possession and use of the -User Product is transferred to the recipient in perpetuity or for a -fixed term (regardless of how the transaction is characterized), the -Corresponding Source conveyed under this section must be accompanied -by the Installation Information. But this requirement does not apply -if neither you nor any third party retains the ability to install -modified object code on the User Product (for example, the work has -been installed in ROM). - -The requirement to provide Installation Information does not include a -requirement to continue to provide support service, warranty, or -updates for a work that has been modified or installed by the -recipient, or for the User Product in which it has been modified or -installed. Access to a network may be denied when the modification -itself materially and adversely affects the operation of the network -or violates the rules and protocols for communication across the -network. - -Corresponding Source conveyed, and Installation Information provided, -in accord with this section must be in a format that is publicly -documented (and with an implementation available to the public in -source code form), and must require no special password or key for -unpacking, reading or copying. - -@item Additional Terms. - -``Additional permissions'' are terms that supplement the terms of this -License by making exceptions from one or more of its conditions. -Additional permissions that are applicable to the entire Program shall -be treated as though they were included in this License, to the extent -that they are valid under applicable law. If additional permissions -apply only to part of the Program, that part may be used separately -under those permissions, but the entire Program remains governed by -this License without regard to the additional permissions. - -When you convey a copy of a covered work, you may at your option -remove any additional permissions from that copy, or from any part of -it. (Additional permissions may be written to require their own -removal in certain cases when you modify the work.) You may place -additional permissions on material, added by you to a covered work, -for which you have or can give appropriate copyright permission. - -Notwithstanding any other provision of this License, for material you -add to a covered work, you may (if authorized by the copyright holders -of that material) supplement the terms of this License with terms: - -@enumerate a -@item -Disclaiming warranty or limiting liability differently from the terms -of sections 15 and 16 of this License; or - -@item -Requiring preservation of specified reasonable legal notices or author -attributions in that material or in the Appropriate Legal Notices -displayed by works containing it; or - -@item -Prohibiting misrepresentation of the origin of that material, or -requiring that modified versions of such material be marked in -reasonable ways as different from the original version; or - -@item -Limiting the use for publicity purposes of names of licensors or -authors of the material; or - -@item -Declining to grant rights under trademark law for use of some trade -names, trademarks, or service marks; or - -@item -Requiring indemnification of licensors and authors of that material by -anyone who conveys the material (or modified versions of it) with -contractual assumptions of liability to the recipient, for any -liability that these contractual assumptions directly impose on those -licensors and authors. -@end enumerate - -All other non-permissive additional terms are considered ``further -restrictions'' within the meaning of section 10. If the Program as you -received it, or any part of it, contains a notice stating that it is -governed by this License along with a term that is a further -restriction, you may remove that term. If a license document contains -a further restriction but permits relicensing or conveying under this -License, you may add to a covered work material governed by the terms -of that license document, provided that the further restriction does -not survive such relicensing or conveying. - -If you add terms to a covered work in accord with this section, you -must place, in the relevant source files, a statement of the -additional terms that apply to those files, or a notice indicating -where to find the applicable terms. - -Additional terms, permissive or non-permissive, may be stated in the -form of a separately written license, or stated as exceptions; the -above requirements apply either way. - -@item Termination. - -You may not propagate or modify a covered work except as expressly -provided under this License. Any attempt otherwise to propagate or -modify it is void, and will automatically terminate your rights under -this License (including any patent licenses granted under the third -paragraph of section 11). - -However, if you cease all violation of this License, then your license -from a particular copyright holder is reinstated (a) provisionally, -unless and until the copyright holder explicitly and finally -terminates your license, and (b) permanently, if the copyright holder -fails to notify you of the violation by some reasonable means prior to -60 days after the cessation. - -Moreover, your license from a particular copyright holder is -reinstated permanently if the copyright holder notifies you of the -violation by some reasonable means, this is the first time you have -received notice of violation of this License (for any work) from that -copyright holder, and you cure the violation prior to 30 days after -your receipt of the notice. - -Termination of your rights under this section does not terminate the -licenses of parties who have received copies or rights from you under -this License. If your rights have been terminated and not permanently -reinstated, you do not qualify to receive new licenses for the same -material under section 10. - -@item Acceptance Not Required for Having Copies. - -You are not required to accept this License in order to receive or run -a copy of the Program. Ancillary propagation of a covered work -occurring solely as a consequence of using peer-to-peer transmission -to receive a copy likewise does not require acceptance. However, -nothing other than this License grants you permission to propagate or -modify any covered work. These actions infringe copyright if you do -not accept this License. Therefore, by modifying or propagating a -covered work, you indicate your acceptance of this License to do so. - -@item Automatic Licensing of Downstream Recipients. - -Each time you convey a covered work, the recipient automatically -receives a license from the original licensors, to run, modify and -propagate that work, subject to this License. You are not responsible -for enforcing compliance by third parties with this License. - -An ``entity transaction'' is a transaction transferring control of an -organization, or substantially all assets of one, or subdividing an -organization, or merging organizations. If propagation of a covered -work results from an entity transaction, each party to that -transaction who receives a copy of the work also receives whatever -licenses to the work the party's predecessor in interest had or could -give under the previous paragraph, plus a right to possession of the -Corresponding Source of the work from the predecessor in interest, if -the predecessor has it or can get it with reasonable efforts. - -You may not impose any further restrictions on the exercise of the -rights granted or affirmed under this License. For example, you may -not impose a license fee, royalty, or other charge for exercise of -rights granted under this License, and you may not initiate litigation -(including a cross-claim or counterclaim in a lawsuit) alleging that -any patent claim is infringed by making, using, selling, offering for -sale, or importing the Program or any portion of it. - -@item Patents. - -A ``contributor'' is a copyright holder who authorizes use under this -License of the Program or a work on which the Program is based. The -work thus licensed is called the contributor's ``contributor version''. - -A contributor's ``essential patent claims'' are all patent claims owned -or controlled by the contributor, whether already acquired or -hereafter acquired, that would be infringed by some manner, permitted -by this License, of making, using, or selling its contributor version, -but do not include claims that would be infringed only as a -consequence of further modification of the contributor version. For -purposes of this definition, ``control'' includes the right to grant -patent sublicenses in a manner consistent with the requirements of -this License. - -Each contributor grants you a non-exclusive, worldwide, royalty-free -patent license under the contributor's essential patent claims, to -make, use, sell, offer for sale, import and otherwise run, modify and -propagate the contents of its contributor version. - -In the following three paragraphs, a ``patent license'' is any express -agreement or commitment, however denominated, not to enforce a patent -(such as an express permission to practice a patent or covenant not to -sue for patent infringement). To ``grant'' such a patent license to a -party means to make such an agreement or commitment not to enforce a -patent against the party. - -If you convey a covered work, knowingly relying on a patent license, -and the Corresponding Source of the work is not available for anyone -to copy, free of charge and under the terms of this License, through a -publicly available network server or other readily accessible means, -then you must either (1) cause the Corresponding Source to be so -available, or (2) arrange to deprive yourself of the benefit of the -patent license for this particular work, or (3) arrange, in a manner -consistent with the requirements of this License, to extend the patent -license to downstream recipients. ``Knowingly relying'' means you have -actual knowledge that, but for the patent license, your conveying the -covered work in a country, or your recipient's use of the covered work -in a country, would infringe one or more identifiable patents in that -country that you have reason to believe are valid. - -If, pursuant to or in connection with a single transaction or -arrangement, you convey, or propagate by procuring conveyance of, a -covered work, and grant a patent license to some of the parties -receiving the covered work authorizing them to use, propagate, modify -or convey a specific copy of the covered work, then the patent license -you grant is automatically extended to all recipients of the covered -work and works based on it. - -A patent license is ``discriminatory'' if it does not include within the -scope of its coverage, prohibits the exercise of, or is conditioned on -the non-exercise of one or more of the rights that are specifically -granted under this License. You may not convey a covered work if you -are a party to an arrangement with a third party that is in the -business of distributing software, under which you make payment to the -third party based on the extent of your activity of conveying the -work, and under which the third party grants, to any of the parties -who would receive the covered work from you, a discriminatory patent -license (a) in connection with copies of the covered work conveyed by -you (or copies made from those copies), or (b) primarily for and in -connection with specific products or compilations that contain the -covered work, unless you entered into that arrangement, or that patent -license was granted, prior to 28 March 2007. - -Nothing in this License shall be construed as excluding or limiting -any implied license or other defenses to infringement that may -otherwise be available to you under applicable patent law. - -@item No Surrender of Others' Freedom. - -If conditions are imposed on you (whether by court order, agreement or -otherwise) that contradict the conditions of this License, they do not -excuse you from the conditions of this License. If you cannot convey -a covered work so as to satisfy simultaneously your obligations under -this License and any other pertinent obligations, then as a -consequence you may not convey it at all. For example, if you agree -to terms that obligate you to collect a royalty for further conveying -from those to whom you convey the Program, the only way you could -satisfy both those terms and this License would be to refrain entirely -from conveying the Program. - -@item Use with the GNU Affero General Public License. - -Notwithstanding any other provision of this License, you have -permission to link or combine any covered work with a work licensed -under version 3 of the GNU Affero General Public License into a single -combined work, and to convey the resulting work. The terms of this -License will continue to apply to the part which is the covered work, -but the special requirements of the GNU Affero General Public License, -section 13, concerning interaction through a network will apply to the -combination as such. - -@item Revised Versions of this License. - -The Free Software Foundation may publish revised and/or new versions -of the GNU General Public License from time to time. Such new -versions will be similar in spirit to the present version, but may -differ in detail to address new problems or concerns. - -Each version is given a distinguishing version number. If the Program -specifies that a certain numbered version of the GNU General Public -License ``or any later version'' applies to it, you have the option of -following the terms and conditions either of that numbered version or -of any later version published by the Free Software Foundation. If -the Program does not specify a version number of the GNU General -Public License, you may choose any version ever published by the Free -Software Foundation. - -If the Program specifies that a proxy can decide which future versions -of the GNU General Public License can be used, that proxy's public -statement of acceptance of a version permanently authorizes you to -choose that version for the Program. - -Later license versions may give you additional or different -permissions. However, no additional obligations are imposed on any -author or copyright holder as a result of your choosing to follow a -later version. - -@item Disclaimer of Warranty. - -THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY -APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT -HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM ``AS IS'' WITHOUT -WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT -LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR -A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND -PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE PROGRAM PROVE -DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR -CORRECTION. - -@item Limitation of Liability. - -IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING -WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MODIFIES AND/OR -CONVEYS THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, -INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES -ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT -NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR -LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM -TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER -PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. - -@item Interpretation of Sections 15 and 16. - -If the disclaimer of warranty and limitation of liability provided -above cannot be given local legal effect according to their terms, -reviewing courts shall apply local law that most closely approximates -an absolute waiver of all civil liability in connection with the -Program, unless a warranty or assumption of liability accompanies a -copy of the Program in return for a fee. - -@end enumerate - -@heading END OF TERMS AND CONDITIONS - -@heading How to Apply These Terms to Your New Programs - -If you develop a new program, and you want it to be of the greatest -possible use to the public, the best way to achieve this is to make it -free software which everyone can redistribute and change under these -terms. - -To do so, attach the following notices to the program. It is safest -to attach them to the start of each source file to most effectively -state the exclusion of warranty; and each file should have at least -the ``copyright'' line and a pointer to where the full notice is found. - -@smallexample -@var{one line to give the program's name and a brief idea of what it does.} -Copyright (C) @var{year} @var{name of author} - -This program 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. - -This program 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 this program. If not, see @url{http://www.gnu.org/licenses/}. -@end smallexample - -Also add information on how to contact you by electronic and paper mail. - -If the program does terminal interaction, make it output a short -notice like this when it starts in an interactive mode: - -@smallexample -@var{program} Copyright (C) @var{year} @var{name of author} -This program comes with ABSOLUTELY NO WARRANTY; for details type @samp{show w}. -This is free software, and you are welcome to redistribute it -under certain conditions; type @samp{show c} for details. -@end smallexample - -The hypothetical commands @samp{show w} and @samp{show c} should show -the appropriate parts of the General Public License. Of course, your -program's commands might be different; for a GUI interface, you would -use an ``about box''. - -You should also get your employer (if you work as a programmer) or school, -if any, to sign a ``copyright disclaimer'' for the program, if necessary. -For more information on this, and how to apply and follow the GNU GPL, see -@url{http://www.gnu.org/licenses/}. - -The GNU General Public License does not permit incorporating your -program into proprietary programs. If your program is a subroutine -library, you may consider it more useful to permit linking proprietary -applications with the library. If this is what you want to do, use -the GNU Lesser General Public License instead of this License. But -first, please read @url{http://www.gnu.org/philosophy/why-not-lgpl.html}.
--- a/main/queueing/doc/grabdemo.m Fri Apr 06 10:07:57 2012 +0000 +++ b/main/queueing/doc/grabdemo.m Fri Apr 06 16:04:05 2012 +0000 @@ -1,7 +1,7 @@ ## Copyright (C) 2005, 2006, 2007 David Bateman ## Modifications Copyright (C) 2009 Moreno Marzolla ## -## This file is part of qnetworks. It is based on the fntests.m +## This file is part of the queueing toolbox. It is based on the fntests.m ## script included in GNU Octave. ## ## Octave is free software; you can redistribute it and/or modify it @@ -52,7 +52,11 @@ for i=2:length(idx) demoname = [ "demo_" num2str(i-1) "_" nn ".texi" ]; fid = fopen( demoname, "wt" ); - fprintf(fid,"%s",code(idx(i-1)+1:idx(i)-1)); + + fprintf(fid,"@c -*- texinfo -*-\n@c\n@c Copyright (C) 2012 Moreno Marzolla\n@c This file is part of the queueing toolbox, a Queueing Networks\n@c analysis package for GNU Octave. The queueing toolbox is distributed\n@c under the terms of the GNU General Public License version 3 or later\n@c\n@c This file is automatically generated from %s\n@c All modifications to this file will be lost\n", + fname); + + fprintf(fid,"@verbatim\n%s\n@end verbatim\n",code(idx(i-1)+1:idx(i)-1)); fclose(fid); endfor endfunction
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/queueing/doc/installation.texi Fri Apr 06 16:04:05 2012 +0000 @@ -0,0 +1,288 @@ +@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/>. + +@ifset INSTALLONLY +@include conf.texi + +This file documents the installation procedure of the Octave +@code{queueing} toolbox. + +@code{queueing} is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License, version 3 +or later, as published by the Free Software Foundation. + +@quotation Note +This file (@file{INSTALL}) is automatically generated from +@file{doc/installation.txi} in the @code{queueing} subversion sources. +Do not modify this document directly, as changes will be lost. Modify +the source @file{doc/installation.txi} instead. +@end quotation + +@end ifset + +@node Installation +@chapter Installing the queueing toolbox + +@menu +* Installation through Octave package management system:: +* Manual installation:: +* Development sources:: +* Using the queueing toolbox:: +@end menu + +@c +@c +@c + +@node Installation through Octave package management system +@section Installation through Octave package management system + +The most recent version of @code{queueing} is @value{VERSION} and can +be downloaded from Octave-Forge + +@url{http://octave.sourceforge.net/queueing/} + +Additional information can be found at + +@url{http://www.moreno.marzolla.name/software/queueing/} + +If you have a recent version of GNU Octave and a network connection, +you can install @code{queueing} directly from Octave command prompt +using this command: + +@example +octave:1> @kbd{pkg install -forge queueing} +@end example + +The command above will automaticall download and install the latest +version of the queueing toolbox from Octave Forge, and install it on +your machine. You can verify that the package is indeed installed: + +@example +octave:1>@kbd{pkg list queueing} +Package Name | Version | Installation directory +--------------+---------+----------------------- + queueing *| @value{VERSION} | /home/moreno/octave/queueing-@value{VERSION} +@end example + +Alternatively, you can first download @code{queueing} from +Octave-Forge; then, to install the package in the system-wide +location issue this command at the Octave prompt: + +@example +octave:1> @kbd{pkg install @emph{queueing-@value{VERSION}.tar.gz}} +@end example + +@noindent (you may need to start Octave as root in order to allow the +installation to copy the files to the target locations). After this, +all functions will be readily available each time Octave starts, +without the need to tweak the search path. + +If you do not have root access, you can do a local install using: + +@example +octave:1> @kbd{pkg install -local queueing-@value{VERSION}.tar.gz} +@end example + +This will install @code{queueing} within your home directory, and the +package will be available to your user only. + +@quotation Note +Octave version 3.2.3 as shipped with Ubuntu 10.04 seems to ignore +@code{-local} and always tries to install the package on the system +directory. +@end quotation + +To remove @code{queueing} simply use + +@example +octave:1> @kbd{pkg uninstall queueing} +@end example + +@c +@c +@c + +@node Manual installation +@section Manual installation + +If you want to manually install @code{queueing} in a custom location, +you can download the tarball and unpack it somewhere: + +@example +@kbd{tar xvfz queueing-@value{VERSION}.tar.gz} +@kbd{cd queueing-@value{VERSION}/queueing/} +@end example + +Copy all @code{.m} files from the @file{inst/} directory to some +target location. Then, start Octave with the @option{-p} option to add +the target location to the search path, so that Octave will find all +@code{queueing} functions automatically: + +@example +@kbd{octave -p @emph{/path/to/queueing}} +@end example + +For example, if all @code{queueing} m-files are in +@file{/usr/local/queueing}, you can start Octave as follows: + +@example +@kbd{octave -p @emph{/usr/local/queueing}} +@end example + +If you want, you can add the following line to @file{~/.octaverc}: + +@example +@kbd{addpath("@emph{/path/to/queueing}");} +@end example + +@noindent so that the path @file{/usr/local/queueing} is automatically +added to the search path each time Octave is started, and you no +longer need to specify the @option{-p} option on the command line. + +@c +@c +@c + +@ifclear INSTALLONLY + +@node Development sources +@section Development sources + +The source code of the @code{queueing} package can be found in the +Subversion repository at the URL: + +@url{http://octave.svn.sourceforge.net/viewvc/octave/trunk/octave-forge/main/queueing/} + +The source distribution contains additional development files which +are not present in the installation tarball. This section briefly +describes the content of the source tree. This is only relevant for +developers who want to modify the code or documentation; normal users +of the @code{queueing} package don't need + +The source distribution contains the following directories: + +@table @file +@item doc/ +Documentation source. Most of the documentation is extracted from the +comment blocks of individual function files from the @file{inst/} +directory. + +@item inst/ +This directory contains the @verb{|m|}-files which implement the +various Queueing Network algorithms provided by @code{queueing}. As a +notational convention, the names of source files containing functions +for Queueing Networks start with the @samp{qn} prefix; the name of +source files containing functions for Continuous-Time Markov Chains +(CTMSs) start with the @samp{ctmc} prefix, and the names of files +containing functions for Discrete-Time Markov Chains (DTMCs) start +with the @samp{dtmc} prefix. + +@item test/ +This directory contains the test functions used to invoke all tests on +all function files. + +@item scripts/ +This directory contains some utility scripts mostly from GNU Octave, +which extract the documentation from the specially-formatted comments +in the @verb{|m|}-files. + +@item examples/ +This directory contains examples which are automatically extracted +from the @samp{demo} blocks of the function files. + +@item devel/ +This directory contains function files which are either not working +properly, or need additional testing before they are moved to the +@file{inst/} directory. + +@end table + +The @code{queueing} package ships with a Makefile which can be used +to produce the documentation (in PDF and HTML format), and +automatically execute all function tests. Specifically, the following +targets are defined: + +@table @code +@item all +Running @samp{make} (or @samp{make all}) on the top-level directory +builds the programs used to extract the documentation from the +comments embedded in the @verb{|m|}-files, and then produce the +documentation in PDF and HTML format (@file{doc/queueing.pdf} and +@file{doc/queueing.html}, respectively). + +@item check +Running @samp{make check} will execute all tests contained in the +@verb{|m|}-files. If you modify the code of any function in the +@file{inst/} directory, you should run the tests to ensure that no +errors have been introduced. You are also encouraged to contribute new +tests, especially for functions which are not adequately validated. + +@item clean +@itemx distclean +@itemx dist +The @samp{make clean}, @samp{make distclean} and @samp{make dist} +commands are used to clean up the source directory and prepare the +distribution archive in compressed tar format. + +@end table + +@end ifclear + +@c +@c +@c + +@node Using the queueing toolbox +@section Using the queueing toolbox + +You can use all functions by simply invoking their name with the +appropriate parameters; the @code{queueing} package should display an +error message in case of missing/wrong parameters. You can display the +help text for any function using the @command{help} command. For +example: + +@example +octave:2> @kbd{help qnmvablo} +@end example + +prints the documentation for the @command{qnmvablo} function. +Additional information can be found in the @code{queueing} manual, +which is available in PDF format in @file{doc/queueing.pdf} and in +HTML format in @file{doc/queueing.html}. + +Within GNU Octave, you can also run the test and demo blocks +associated to the functions, using the @command{test} and +@command{demo} commands respectively. To run all the tests of, say, +the @command{qnmvablo} function: + +@example +octave:3> @kbd{test qnmvablo} +@print{} PASSES 4 out of 4 tests +@end example + +To execute the demos of the @command{qnclosed} function, use the +following: + +@example +octave:4> @kbd{demo qnclosed} +@end example +
--- a/main/queueing/doc/installation.txi Fri Apr 06 10:07:57 2012 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,288 +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/>. - -@ifset INSTALLONLY -@include conf.texi - -This file documents the installation procedure of the Octave -@code{queueing} toolbox. - -@code{queueing} is free software; you can redistribute it and/or -modify it under the terms of the GNU General Public License, version 3 -or later, as published by the Free Software Foundation. - -@quotation Note -This file (@file{INSTALL}) is automatically generated from -@file{doc/installation.txi} in the @code{queueing} subversion sources. -Do not modify this document directly, as changes will be lost. Modify -the source @file{doc/installation.txi} instead. -@end quotation - -@end ifset - -@node Installation -@chapter Installing the queueing toolbox - -@menu -* Installation through Octave package management system:: -* Manual installation:: -* Development sources:: -* Using the queueing toolbox:: -@end menu - -@c -@c -@c - -@node Installation through Octave package management system -@section Installation through Octave package management system - -The most recent version of @code{queueing} is @value{VERSION} and can -be downloaded from Octave-Forge - -@url{http://octave.sourceforge.net/queueing/} - -Additional information can be found at - -@url{http://www.moreno.marzolla.name/software/queueing/} - -If you have a recent version of GNU Octave and a network connection, -you can install @code{queueing} directly from Octave command prompt -using this command: - -@example -octave:1> @kbd{pkg install -forge queueing} -@end example - -The command above will automaticall download and install the latest -version of the queueing toolbox from Octave Forge, and install it on -your machine. You can verify that the package is indeed installed: - -@example -octave:1>@kbd{pkg list queueing} -Package Name | Version | Installation directory ---------------+---------+----------------------- - queueing *| @value{VERSION} | /home/moreno/octave/queueing-@value{VERSION} -@end example - -Alternatively, you can first download @code{queueing} from -Octave-Forge; then, to install the package in the system-wide -location issue this command at the Octave prompt: - -@example -octave:1> @kbd{pkg install @emph{queueing-@value{VERSION}.tar.gz}} -@end example - -@noindent (you may need to start Octave as root in order to allow the -installation to copy the files to the target locations). After this, -all functions will be readily available each time Octave starts, -without the need to tweak the search path. - -If you do not have root access, you can do a local install using: - -@example -octave:1> @kbd{pkg install -local queueing-@value{VERSION}.tar.gz} -@end example - -This will install @code{queueing} within your home directory, and the -package will be available to your user only. - -@quotation Note -Octave version 3.2.3 as shipped with Ubuntu 10.04 seems to ignore -@code{-local} and always tries to install the package on the system -directory. -@end quotation - -To remove @code{queueing} simply use - -@example -octave:1> @kbd{pkg uninstall queueing} -@end example - -@c -@c -@c - -@node Manual installation -@section Manual installation - -If you want to manually install @code{queueing} in a custom location, -you can download the tarball and unpack it somewhere: - -@example -@kbd{tar xvfz queueing-@value{VERSION}.tar.gz} -@kbd{cd queueing-@value{VERSION}/queueing/} -@end example - -Copy all @code{.m} files from the @file{inst/} directory to some -target location. Then, start Octave with the @option{-p} option to add -the target location to the search path, so that Octave will find all -@code{queueing} functions automatically: - -@example -@kbd{octave -p @emph{/path/to/queueing}} -@end example - -For example, if all @code{queueing} m-files are in -@file{/usr/local/queueing}, you can start Octave as follows: - -@example -@kbd{octave -p @emph{/usr/local/queueing}} -@end example - -If you want, you can add the following line to @file{~/.octaverc}: - -@example -@kbd{addpath("@emph{/path/to/queueing}");} -@end example - -@noindent so that the path @file{/usr/local/queueing} is automatically -added to the search path each time Octave is started, and you no -longer need to specify the @option{-p} option on the command line. - -@c -@c -@c - -@ifclear INSTALLONLY - -@node Development sources -@section Development sources - -The source code of the @code{queueing} package can be found in the -Subversion repository at the URL: - -@url{http://octave.svn.sourceforge.net/viewvc/octave/trunk/octave-forge/main/queueing/} - -The source distribution contains additional development files which -are not present in the installation tarball. This section briefly -describes the content of the source tree. This is only relevant for -developers who want to modify the code or documentation; normal users -of the @code{queueing} package don't need - -The source distribution contains the following directories: - -@table @file -@item doc/ -Documentation source. Most of the documentation is extracted from the -comment blocks of individual function files from the @file{inst/} -directory. - -@item inst/ -This directory contains the @verb{|m|}-files which implement the -various Queueing Network algorithms provided by @code{queueing}. As a -notational convention, the names of source files containing functions -for Queueing Networks start with the @samp{qn} prefix; the name of -source files containing functions for Continuous-Time Markov Chains -(CTMSs) start with the @samp{ctmc} prefix, and the names of files -containing functions for Discrete-Time Markov Chains (DTMCs) start -with the @samp{dtmc} prefix. - -@item test/ -This directory contains the test functions used to invoke all tests on -all function files. - -@item scripts/ -This directory contains some utility scripts mostly from GNU Octave, -which extract the documentation from the specially-formatted comments -in the @verb{|m|}-files. - -@item examples/ -This directory contains examples which are automatically extracted -from the @samp{demo} blocks of the function files. - -@item devel/ -This directory contains function files which are either not working -properly, or need additional testing before they are moved to the -@file{inst/} directory. - -@end table - -The @code{queueing} package ships with a Makefile which can be used -to produce the documentation (in PDF and HTML format), and -automatically execute all function tests. Specifically, the following -targets are defined: - -@table @code -@item all -Running @samp{make} (or @samp{make all}) on the top-level directory -builds the programs used to extract the documentation from the -comments embedded in the @verb{|m|}-files, and then produce the -documentation in PDF and HTML format (@file{doc/queueing.pdf} and -@file{doc/queueing.html}, respectively). - -@item check -Running @samp{make check} will execute all tests contained in the -@verb{|m|}-files. If you modify the code of any function in the -@file{inst/} directory, you should run the tests to ensure that no -errors have been introduced. You are also encouraged to contribute new -tests, especially for functions which are not adequately validated. - -@item clean -@itemx distclean -@itemx dist -The @samp{make clean}, @samp{make distclean} and @samp{make dist} -commands are used to clean up the source directory and prepare the -distribution archive in compressed tar format. - -@end table - -@end ifclear - -@c -@c -@c - -@node Using the queueing toolbox -@section Using the queueing toolbox - -You can use all functions by simply invoking their name with the -appropriate parameters; the @code{queueing} package should display an -error message in case of missing/wrong parameters. You can display the -help text for any function using the @command{help} command. For -example: - -@example -octave:2> @kbd{help qnmvablo} -@end example - -prints the documentation for the @command{qnmvablo} function. -Additional information can be found in the @code{queueing} manual, -which is available in PDF format in @file{doc/queueing.pdf} and in -HTML format in @file{doc/queueing.html}. - -Within GNU Octave, you can also run the test and demo blocks -associated to the functions, using the @command{test} and -@command{demo} commands respectively. To run all the tests of, say, -the @command{qnmvablo} function: - -@example -octave:3> @kbd{test qnmvablo} -@print{} PASSES 4 out of 4 tests -@end example - -To execute the demos of the @command{qnclosed} function, use the -following: - -@example -octave:4> @kbd{demo qnclosed} -@end example -
--- a/main/queueing/doc/markovchains.txi Fri Apr 06 10:07:57 2012 +0000 +++ b/main/queueing/doc/markovchains.txi Fri Apr 06 16:04:05 2012 +0000 @@ -64,7 +64,7 @@ @math{i, j}, and (2) @math{\sum_{j=1}^N P_{i,j} = 1} for all @math{i} @c -@DOCSTRING(dtmc_check_P) +@include help/dtmc_check_P.texi @menu * State occupancy probabilities (DTMC):: @@ -135,7 +135,7 @@ the transpose operator. @c -@DOCSTRING(dtmc) +@include help/dtmc.texi @noindent @strong{EXAMPLE} @@ -205,7 +205,7 @@ @example @c @group -@verbatiminclude demo_1_dtmc.texi +@include demos/demo_1_dtmc.texi @c @end group @result{} 0.083333 0.125000 0.083333 0.125000 0.166667 0.125000 0.083333 0.125000 @@ -216,7 +216,7 @@ @node Birth-death process (DTMC) @subsection Birth-death process -@DOCSTRING(dtmc_bd) +@include help/dtmc_bd.texi @c @node Expected number of visits (DTMC) @@ -280,13 +280,13 @@ to the size of @math{\bf P} (filling missing entries with zeros), we have that, for absorbing chains @math{{\bf L} = {\bf \pi}(0){\bf N}}. -@DOCSTRING(dtmc_exps) +@include help/dtmc_exps.texi @c @node Time-averaged expected sojourn times (DTMC) @subsection Time-averaged expected sojourn times -@DOCSTRING(dtmc_taexps) +@include help/dtmc_taexps.texi @c @node Mean time to absorption (DTMC) @@ -329,7 +329,7 @@ @end example @end ifnottex -@DOCSTRING(dtmc_mtta) +@include help/dtmc_mtta.texi @c @node First passage times (DTMC) @@ -414,7 +414,7 @@ @end example @end ifnottex -@DOCSTRING(dtmc_fpt) +@include help/dtmc_fpt.texi @c @c @@ -444,7 +444,7 @@ satisfy the property that, for all @math{i}, @math{\sum_{j=1}^N Q_{i, j} = 0}. -@DOCSTRING(ctmc_check_Q) +@include help/ctmc_check_Q.texi @menu * State occupancy probabilities (CTMC):: @@ -510,7 +510,7 @@ @end example @end ifnottex -@DOCSTRING(ctmc) +@include help/ctmc.texi @noindent @strong{EXAMPLE} @@ -519,7 +519,7 @@ @example @group -@verbatiminclude demo_1_ctmc.texi +@include demos/demo_1_ctmc.texi @result{} q = 0.50000 0.50000 @end group @end example @@ -530,7 +530,7 @@ @node Birth-death process (CTMC) @subsection Birth-Death Process -@DOCSTRING(ctmc_bd) +@include help/ctmc_bd.texi @c @c @@ -583,7 +583,7 @@ the state occupancy probability at time @math{t}; @math{\exp({\bf Q}t)} is the matrix exponential of @math{{\bf Q}t}. -@DOCSTRING(ctmc_exps) +@include help/ctmc_exps.texi @noindent @strong{EXAMPLE} @@ -595,7 +595,7 @@ @example @group -@verbatiminclude demo_1_ctmc_exps.texi +@include demos/demo_1_ctmc_exps.texi @end group @end example @@ -605,13 +605,13 @@ @node Time-averaged expected sojourn times (CTMC) @subsection Time-Averaged Expected Sojourn Times -@DOCSTRING(ctmc_taexps) +@include help/ctmc_taexps.texi @noindent @strong{EXAMPLE} @example @group -@verbatiminclude demo_1_ctmc_taexps.texi +@include demos/demo_1_ctmc_taexps.texi @end group @end example @@ -647,7 +647,7 @@ state occupancy probability at time 0, restricted to states in @math{A}. -@DOCSTRING(ctmc_mtta) +@include help/ctmc_mtta.texi @noindent @strong{EXAMPLE} @@ -670,7 +670,7 @@ @example @group -@verbatiminclude demo_1_ctmc_mtta.texi +@include demos/demo_1_ctmc_mtta.texi @result{} t = 78.333 @end group @end example @@ -693,5 +693,5 @@ @node First passage times (CTMC) @subsection First Passage Times -@DOCSTRING(ctmc_fpt) +@include help/ctmc_fpt.texi
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/queueing/doc/queueingnetworks.texi Fri Apr 06 16:04:05 2012 +0000 @@ -0,0 +1,1217 @@ +@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 Queueing Networks +@chapter Queueing Networks + +@menu +* Introduction to QNs:: A brief introduction to Queueing Networks. +* 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 + +@cindex queueing networks + +@c +@c INTRODUCTION +@c +@node Introduction to QNs +@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. + +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. + +Requests join the queue according to a @emph{queueing policy}, such as: + +@table @strong + +@item FCFS +First-Come-First-Served + +@item LCFS-PR +Last-Come-First-Served, Preemptive Resume + +@item PS +Processor Sharing + +@item IS +Infinite Server, there is an infinite number of identical servers so +that each request always finds a server available, and there is no +queueing + +@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. + +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. + +@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 +service time, and all requests move through the system with the same +routing probabilities. + +@noindent @strong{Model Inputs} + +@table @math + +@item \lambda_i +External arrival rate to service center @math{i}. + +@item \lambda +Overall external arrival rate to the whole system: @math{\lambda = +\sum_i \lambda_i}. + +@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 +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 +\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. + +@end table + +@noindent @strong{Model Outputs} + +@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 +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 +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 +the queue, and the request being served. + +@item X_i +Throughput. @math{X_i} is the throughput of service center @math{i}. +The throughput is defined as the ratio of job completions (i.e., average +number of jobs completed over a fixed interval of time). + +@end table + +@noindent Given these output parameters, additional performance measures can +be computed as follows: + +@table @math + +@item X +System throughput, @math{X = X_1 / V_1} + +@item R +System response time, @math{R = \sum_{k=1}^K R_k V_k} + +@item Q +Average number of requests in the system, @math{Q = N-XZ} + +@end table + +For open, single-class models, the scalar @math{\lambda} denotes the +external arrival rate of requests to the system. The average number of +visits 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 +@group + K + ___ + \ +V_j = P_(0, j) + > V_i P_(i, j) + /___ + i=1 +@end group +@end example +@end ifnottex + +@noindent where @math{P_{0, j}} is the probability that an external +arrival goes to service center @math{j}. If @math{\lambda_j} is the +external arrival rate to service center @math{j}, and @math{\lambda = +\sum_j \lambda_j} is the overall external arrival rate, then +@math{P_{0, j} = \lambda_j / \lambda}. + +For closed models, the visit ratios satisfy the following equation: + +@iftex +@tex +$$\eqalign{V_1 & = 1 \cr + V_j & = \sum_{i=1}^K V_i P_{i, j}} $$ +@end tex +@end iftex +@ifnottex +@example + +V_1 = 1 + + K + ___ + \ +V_j = > V_i P_(i, j) + /___ + i=1 + +@end example +@end ifnottex + +@subsection Multiple class models + +In multiple class QN models, we assume that there exist @math{C} +different classes of requests. Each request from class @math{c} spends +on average time @math{S_{c, k}} in service at service center +@math{k}. For open models, we denote with @math{{\bf \lambda} = +\lambda_{ck}} the arrival rates, where @math{\lambda_{c, k}} is the +external arrival rate of class @math{c} customers at service center +@math{k}. For closed models, we denote with @math{{\bf N} = (N_1, N_2, +\ldots, N_C)} the population vector, where @math{N_c} is the number of +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}} +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. + +Model input and outputs can be adjusted by adding additional indexes +for the customer classes. + +@noindent @strong{Model Inputs} + +@table @math + +@item \lambda_{c, i} +External arrival rate of class-@math{c} requests to service center @math{i} + +@item \lambda +Overall external arrival rate to the whole system: @math{\lambda = \sum_c \sum_i \lambda_{c, i}} + +@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 P_{r, i, s, j} +Routing probability matrix. @math{{\bf P} = P_{r, i, s, j}} is a @math{C +\times K \times C \times K} matrix such that @math{P_{r, i, s, j}} is +the probability that a class @math{r} request which completes service +at server @math{i} will move to server @math{j} as a class @math{s} +request. + +@item 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}. + +@end table + +@noindent @strong{Model Outputs} + +@table @math + +@item U_{c, i} +Utilization of service center @math{i} 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} +Average response time experienced by class @math{c} requests on service +center @math{i}. 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} +Average number of class @math{c} requests on service center +@math{i}. 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 +throughput is defined as the rate of completion of class @math{c} +requests. + +@end table + +@noindent It is possible to define aggregate performance measures as follows: + +@table @math + +@item U_i +Utilization of service center @math{i}: +@iftex +@tex +$U_i = \sum_{c=1}^C U_{c, i}$ +@end tex +@end iftex +@ifnottex +@code{Ui = sum(U,1);} +@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}$ +@end tex +@end iftex +@ifnottex +@code{Rc = sum( V.*R, 1 );} +@end ifnottex + +@item Q_c +Average number of class @math{c} requests in the system: +@iftex +@tex +$Q_c = \sum_{i=1}^K Q_{c, i}$ +@end tex +@end iftex +@ifnottex +@code{Qc = sum( Q, 2 );} +@end ifnottex + +@item X_c +Class @math{c} throughput: +@iftex +@tex +$X_c = X_{c, 1} / V_{c, 1}$ +@end tex +@end iftex +@ifnottex +@code{Xc = X(:,1) ./ V(:,1);} +@end ifnottex + +@end table + +We can define the visit ratios @math{V_{s, j}} for class @math{s} +customers at service center @math{j} as follows: + +@iftex +@tex +$$ \eqalign{ V_{s, j} & = \sum_{r=1}^C \sum_{i=1}^K V_{r, i} P_{r, i, s, j} \cr + V_{s, 1} & = 1} $$ +@end tex +@end iftex +@ifnottex +@group +V_sj = sum_r sum_i V_ri P_risj, for all s,j +@end group +@end ifnottex + +@noindent while for open networks: + +@iftex +@tex +$$V_{s, j} = P_{0, s, j} + \sum_{r=1}^C \sum_{i=1}^K V_{r, i} P_{r, i, s, j}$$ +@end tex +@end iftex +@ifnottex +@group +V_sj = P_0sj + sum_r sum_i V_ri P_risj, for all s,j +@end group +@end ifnottex + +@noindent where @math{P_{0, s, j}} is the probability that an external +arrival goes to service center @math{j} as a class-@math{s} request. +If @math{\lambda_{s, j}} is the external arrival rate of class +@math{s} requests to service center @math{j}, and @math{\lambda = +\sum_s \sum_j \lambda_{s, j}} is the overall external arrival rate to +the whole system, then @math{P_{0, s, j} = \lambda_{s, j} / \lambda}. + +@c +@c +@c +@node Generic Algorithms +@section Generic Algorithms + +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}. + +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. + +@include help/qnmknode.texi + +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. + +@include help/qnsolve.texi + +@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 +@include demos/demo_1_qnsolve.texi +@end example + + +@c +@c +@c +@node Algorithms for Product-Form QNs +@section Algorithms for Product-Form QNs + +Product-form queueing networks fulfill the following assumptions: + +@itemize + +@item The network can consist of open and closed job classes. + +@item The following queueing disciplines are allowed: FCFS, PS, LCFS-PR and IS. + +@item Service times for FCFS nodes must be exponentially distributed and +class-independent. Service centers at PS, LCFS-PR and IS nodes can +have any kind of service time distribution with a rational Laplace +transform. Furthermore, for PS, LCFS-PR and IS nodes, different +classes of customers can have different service times. + +@item The service rate of an FCFS node is only allowed to depend on the +number of jobs at this node; in a PS, LCFS-PR and IS node the service +rate for a particular job class can also depend on the number of jobs +of that class at the node. + +@item In open networks two kinds of arrival processes are allowed: i) the +arrival process is Poisson, with arrival rate @math{\lambda} which can +depend on the number of jobs in the network. ii) the arrival process +consists of @math{U} independent Poisson arrival streams where the +@math{U} job sources are assigned to the @math{U} chains; the arrival +rate can be load dependent. + +@end itemize + +@c +@c Jackson Networks +@c + +@subsection Jackson Networks + +Jackson networks satisfy the following conditions: + +@itemize + +@item +There is only one job class in the network; the overall number of jobs +in the system is unlimited. + +@item +There are @math{N} service centers in the network. Each service center +may have Poisson arrivals from outside the system. A job can leave +the system from any node. + +@item +Arrival rates as well as routing probabilities are independent from +the number of nodes in the network. + +@item +External arrivals and service times at the service centers are +exponentially distributed, and in general can be load-dependent. + +@item +Service discipline at each node is FCFS + +@end itemize + +We define the @emph{joint probability vector} @math{\pi(k_1, k_2, +\ldots, k_N)} as the steady-state probability that there are @math{k_i} +requests at service center @math{i}, for all @math{i=1, 2, \ldots, N}. +Jackson networks have the property that the joint probability is the +product of the marginal probabilities @math{\pi_i}: + +@iftex +@tex +$$ \pi(k_1, k_2, \ldots, k_N) = \prod_{i=1}^N \pi_i(k_i) $$ +@end tex +@end iftex +@ifnottex +@example +@var{joint_prob} = prod( @var{pi} ) +@end example +@end ifnottex + +@noindent where @math{\pi_i(k_i)} is the steady-state probability +that there are @math{k_i} requests at service center @math{i}. + +@include help/qnjackson.texi + +@noindent @strong{REFERENCES} + +This implementation is based on G. Bolch, S. Greiner, H. de Meer and +K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and +Performance Evaluation with Computer Science Applications}, Wiley, +1998, pp. 284--287. + +@auindex Bolch, G. +@auindex Greiner, S. +@auindex de Meer, H. +@auindex Trivedi, K. + +@subsection The Convolution Algorithm + +According to the BCMP theorem, the state probability of a closed +single class queueing network with @math{K} nodes and @math{N} requests +can be expressed as: + +@iftex +@tex +$$ \pi(k_1, k_2, \ldots, k_K) = {1 \over G(N)} \prod_{i=1}^N F_i(k_i) $$ +@end tex +@end iftex +@ifnottex +@example +@group +k = [k1, k2, @dots{} kn]; @r{population vector} +p = 1/G(N+1) \prod F(i,k); +@end group +@end example +@end ifnottex + +Here @math{\pi(k_1, k_2, \ldots, k_K)} is the joint probability of +having @math{k_i} requests at node @math{i}, for all @math{i=1, 2, +\ldots, K}. + +The @emph{convolution algorithms} computes the normalization constants +@math{{\bf G} = \left(G(0), G(1), \ldots, G(N)\right)} for single-class, closed networks +with @math{N} requests. The normalization constants are returned as +vector @code{@var{G}=[@var{G}(1), @var{G}(2), @dots{} @var{G}(N+1)]} where +@code{@var{G}(i+1)} is the value of @math{G(i)} (remember that Octave +uses 1-base vectors). The normalization constant can be used to +compute all performance measures of interest (utilization, average +response time and so on). + +@code{queueing} implements the convolution algorithm, in the function +@code{qnconvolution} and @code{qnconvolutionld}. The first one +supports single-station nodes, multiple-station nodes and IS nodes. +The second one supports networks with general load-dependent service +centers. + +@c +@c The Convolution Algorithm +@c + +@include help/qnconvolution.texi + +@noindent @strong{EXAMPLE} + +The normalization constant @math{G} can be used to compute the +steady-state probabilities for a closed single class product-form +Queueing Network with @math{K} nodes. Let @code{@var{k}=[@math{k_1, +k_2, @dots{}, k_K}]} be a valid population vector. Then, the +steady-state probability @code{@var{p}(i)} to have @code{@var{k}(i)} +requests at service center @math{i} can be computed as: + +@iftex +@tex +$$ +p_i(k_i) = {(V_i S_i)^{k_i} \over G(K)} \left(G(K-k_i) - V_i S_i G(K-k_i-1)\right), \quad i=1, 2, \ldots, K +$$ +@end tex +@end iftex + +@example +@include demos/demo_1_qnconvolution.texi +@print{} k(1)=1 prob=0.17975 +@print{} k(2)=2 prob=0.48404 +@print{} k(3)=0 prob=0.52779 +@end example + +@noindent @strong{NOTE} + +For a network with @math{K} service centers and @math{N} requests, +this implementation of the convolution algorithm has time and space +complexity @math{O(NK)}. + +@noindent @strong{REFERENCES} + +Jeffrey P. Buzen, @cite{Computational Algorithms for Closed Queueing +Networks with Exponential Servers}, Communications of the ACM, volume +16, number 9, september 1973, +pp. 527--531. @url{http://doi.acm.org/10.1145/362342.362345} + +@auindex Buzen, J. P. + +This implementation is based on G. Bolch, S. Greiner, H. de Meer and +K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and +Performance Evaluation with Computer Science Applications}, Wiley, +1998, pp. 313--317. + +@auindex Bolch, G. +@auindex Greiner, S. +@auindex de Meer, H. +@auindex Trivedi, K. + +@c +@c Convolution for load-dependent service centers +@c +@include help/qnconvolutionld.texi + +@noindent @strong{REFERENCES} + +Herb Schwetman, @cite{Some Computational Aspects of Queueing Network +Models}, Technical Report CSD-TR-354, Department of Computer Sciences, +Purdue University, feb, 1981 (revised). +@url{http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-354.pdf} + +@auindex Schwetman, H. + +M. Reiser, H. Kobayashi, @cite{On The Convolution Algorithm for +Separable Queueing Networks}, In Proceedings of the 1976 ACM +SIGMETRICS Conference on Computer Performance Modeling Measurement and +Evaluation (Cambridge, Massachusetts, United States, March 29--31, +1976). SIGMETRICS '76. ACM, New York, NY, +pp. 109--117. @url{http://doi.acm.org/10.1145/800200.806187} + +@auindex Reiser, M. +@auindex Kobayashi, H. + +This implementation is based on G. Bolch, S. Greiner, H. de Meer and +K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and +Performance Evaluation with Computer Science Applications}, Wiley, +1998, pp. 313--317. Function @code{qnconvolutionld} is slightly +different from the version described in Bolch et al. because it +supports general load-dependent centers (while the version in the book +does not). The modification is in the definition of function +@code{F()} in @code{qnconvolutionld} which has been made similar to +function @math{f_i} defined in Schwetman, @code{Some Computational +Aspects of Queueing Network Models}. + +@auindex Bolch, G. +@auindex Greiner, S. +@auindex de Meer, H. +@auindex Trivedi, K. + + +@subsection Open networks + +@c +@c Open networks with single class +@c +@include help/qnopensingle.texi + +From the results computed by this function, it is possible to derive +other quantities of interest as follows: + +@itemize + +@item +@strong{System Response Time}: The overall system response time +can be computed as +@iftex +@tex +$R_s = \sum_{i=1}^K V_i R_i$ +@end tex +@end iftex +@ifnottex +@code{R_s = dot(V,R);} +@end ifnottex + +@item +@strong{Average number of requests}: The average number of requests +in the system can be computed as: +@iftex +@tex +$Q_s = \sum_{i=1}^K Q(i)$ +@end tex +@end iftex +@ifnottex +@code{Q_s = sum(Q)} +@end ifnottex + +@end itemize + +@noindent @strong{EXAMPLE} + +@example +@include demos/demo_1_qnopensingle.texi +@print{} R_s = 1.4062 +@print{} N = 4.2186 +@end example + +@noindent @strong{REFERENCES} + +G. Bolch, S. Greiner, H. de Meer and K. Trivedi, @cite{Queueing +Networks and Markov Chains: Modeling and Performance Evaluation with +Computer Science Applications}, Wiley, 1998. + +@auindex Bolch, G. +@auindex Greiner, S. +@auindex de Meer, H. +@auindex Trivedi, K. + + +@c +@c Open network with multiple classes +@c +@include help/qnopenmulti.texi + +@noindent @strong{REFERENCES} + +Edward D. Lazowska, John Zahorjan, G. Scott Graham, and Kenneth C. +Sevcik, @cite{Quantitative System Performance: Computer System +Analysis Using Queueing Network Models}, Prentice Hall, +1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In +particular, see section 7.4.1 ("Open Model Solution Techniques"). + +@auindex Lazowska, E. D. +@auindex Zahorjan, J. +@auindex Graham, G. S. +@auindex Sevcik, K. C. + + +@subsection Closed Networks + +@c +@c MVA for single class, closed networks +@c + +@include help/qnclosedsinglemva.texi + +From the results provided by this function, it is possible to derive +other quantities of interest as follows: + +@noindent @strong{EXAMPLE} + +@example +@include demos/demo_1_qnclosedsinglemva.texi +@end example + + +@noindent @strong{REFERENCES} + +M. Reiser and S. S. Lavenberg, @cite{Mean-Value Analysis of Closed +Multichain Queuing Networks}, Journal of the ACM, vol. 27, n. 2, April +1980, pp. 313--322. @url{http://doi.acm.org/10.1145/322186.322195} + +@auindex Reiser, M. +@auindex Lavenberg, S. S. + +This implementation is described in R. Jain , @cite{The Art of Computer +Systems Performance Analysis}, Wiley, 1991, p. 577. Multi-server nodes +@c and the computation of @math{G(N)}, +are treated according to G. Bolch, S. Greiner, H. de Meer and +K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and +Performance Evaluation with Computer Science Applications}, Wiley, +1998, Section 8.2.1, "Single Class Queueing Networks". + +@auindex Jain, R. +@auindex Bolch, G. +@auindex Greiner, S. +@auindex de Meer, H. +@auindex Trivedi, K. + +@c +@c MVA for single class, closed networks with load dependent servers +@c +@include help/qnclosedsinglemvald.texi + +@noindent @strong{REFERENCES} + +M. Reiser and S. S. Lavenberg, @cite{Mean-Value Analysis of Closed +Multichain Queuing Networks}, Journal of the ACM, vol. 27, n. 2, +April 1980, pp. 313--322. @url{http://doi.acm.org/10.1145/322186.322195} + +This implementation is described in G. Bolch, S. Greiner, H. de Meer +and K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling +and Performance Evaluation with Computer Science Applications}, Wiley, +1998, Section 8.2.4.1, ``Networks with Load-Deèpendent Service: Closed +Networks''. + +@auindex Bolch, G. +@auindex Greiner, S. +@auindex de Meer, H. +@auindex Trivedi, K. + +@c +@c CMVA for single class, closed networks with a single load dependent servers +@c +@include help/qncmva.texi + +@noindent @strong{REFERENCES} + +G. Casale. @cite{A note on stable flow-equivalent aggregation in +closed networks}. Queueing Syst. Theory Appl., 60:193–202, December +2008. + +@auindex Casale, G. + +@c +@c Approximate MVA for single class, closed networks +@c + +@include help/qnclosedsinglemvaapprox.texi + +@noindent @strong{REFERENCES} + +This implementation is based on Edward D. Lazowska, John Zahorjan, +G. Scott Graham, and Kenneth C. Sevcik, @cite{Quantitative System +Performance: Computer System Analysis Using Queueing Network Models}, +Prentice Hall, +1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In +particular, see section 6.4.2.2 ("Approximate Solution Techniques"). + +@auindex Lazowska, E. D. +@auindex Zahorjan, J. +@auindex Graham, G. S. +@auindex Sevcik, K. C. + + +@c +@c MVA for multiple class, closed networks +@c +@include help/qnclosedmultimva.texi + +@noindent @strong{NOTE} + +Given a network with @math{K} service centers, @math{C} job classes and +population vector @math{{\bf N}=(N_1, N_2, \ldots, N_C)}, the MVA +algorithm requires space @math{O(C \prod_i (N_i + 1))}. The time +complexity is @math{O(CK\prod_i (N_i + 1))}. This implementation is +slightly more space-efficient (see details in the code). While the space +requirement can be mitigated by using some optimizations, the time +complexity can not. If you need to analyze large closed networks you +should consider the @command{qnclosedmultimvaapprox} function, which +implements the approximate MVA algorithm. Note however that +@command{qnclosedmultimvaapprox} will only provide approximate results. + + +@noindent @strong{REFERENCES} + +M. Reiser and S. S. Lavenberg, @cite{Mean-Value Analysis of Closed +Multichain Queuing Networks}, Journal of the ACM, vol. 27, n. 2, April +1980, pp. 313--322. @url{http://doi.acm.org/10.1145/322186.322195} + +@auindex Reiser, M. +@auindex Lavenberg, S. S. + +This implementation is based on G. Bolch, S. Greiner, H. de Meer and +K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and +Performance Evaluation with Computer Science Applications}, Wiley, +1998 and Edward D. Lazowska, John Zahorjan, G. Scott Graham, and +Kenneth C. Sevcik, @cite{Quantitative System Performance: Computer +System Analysis Using Queueing Network Models}, Prentice Hall, +1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In +particular, see section 7.4.2.1 ("Exact Solution Techniques"). + +@auindex Bolch, G. +@auindex Greiner, S. +@auindex de Meer, H. +@auindex Trivedi, K. +@auindex Lazowska, E. D. +@auindex Zahorjan, J. +@auindex Graham, G. S. +@auindex Sevcik, K. C. + +@c +@c Approximate MVA, with Bard-Schweitzer approximation +@c +@include help/qnclosedmultimvaapprox.texi + +@noindent @strong{REFERENCES} + +Y. Bard, @cite{Some Extensions to Multiclass Queueing Network Analysis}, +proc. 4th Int. Symp. on Modelling and Performance Evaluation of +Computer Systems, feb. 1979, pp. 51--62. + +@auindex Bard, Y. + +P. Schweitzer, @cite{Approximate Analysis of Multiclass Closed +Networks of Queues}, Proc. Int. Conf. on Stochastic Control and +Optimization, jun 1979, pp. 25--29. + +@auindex Schweitzer, P. + +This implementation is based on Edward D. Lazowska, John Zahorjan, G. +Scott Graham, and Kenneth C. Sevcik, @cite{Quantitative System +Performance: Computer System Analysis Using Queueing Network Models}, +Prentice Hall, +1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In +particular, see section 7.4.2.2 ("Approximate Solution +Techniques"). This implementation is slightly different from the one +described above, as it computes the average response times @math{R} +instead of the residence times. + +@auindex Lazowska, E. D. +@auindex Zahorjan, J. +@auindex Graham, G. S. +@auindex Sevcik, K. C. + +@subsection Mixed Networks + +@c +@c MVA for mixed networks +@c +@include help/qnmix.texi + +@noindent @strong{REFERENCES} + +Edward D. Lazowska, John Zahorjan, G. Scott Graham, and Kenneth C. +Sevcik, @cite{Quantitative System Performance: Computer System +Analysis Using Queueing Network Models}, Prentice Hall, +1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In +particular, see section 7.4.3 ("Mixed Model Solution Techniques"). +Note that in this function we compute the mean response time @math{R} +instead of the mean residence time as in the reference. + +@auindex Lazowska, E. D. +@auindex Zahorjan, J. +@auindex Graham, G. S. +@auindex Sevcik, K. C. + +Herb Schwetman, @cite{Implementing the Mean Value Algorithm for the +Solution of Queueing Network Models}, Technical Report CSD-TR-355, +Department of Computer Sciences, Purdue University, feb 15, 1982, +available at +@url{http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-355.pdf} + +@auindex Schwetman, H. + + +@node Algorithms for non Product-form QNs +@section Algorithms for non Product-Form QNs + +@c +@c MVABLO algorithm for approximate analysis of closed, single class +@c QN with blocking +@c +@include help/qnmvablo.texi + +@noindent @strong{REFERENCES} + +Ian F. Akyildiz, @cite{Mean Value Analysis for Blocking Queueing +Networks}, IEEE Transactions on Software Engineering, vol. 14, n. 2, +april 1988, pp. 418--428. @url{http://dx.doi.org/10.1109/32.4663} + +@auindex Akyildiz, I. F. + +@include help/qnmarkov.texi + +@c +@c +@c +@node Bounds on performance +@section Bounds on performance + +@c +@include help/qnopenab.texi + +@noindent @strong{REFERENCES} + +Edward D. Lazowska, John Zahorjan, G. Scott Graham, and Kenneth +C. Sevcik, @cite{Quantitative System Performance: Computer System +Analysis Using Queueing Network Models}, Prentice Hall, +1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In +particular, see section 5.2 ("Asymptotic Bounds"). + +@auindex Lazowska, E. D. +@auindex Zahorjan, J. +@auindex Graham, G. S. +@auindex Sevcik, K. C. + +@c +@include help/qnclosedab.texi + +@noindent @strong{REFERENCES} + +@noindent Edward D. Lazowska, John Zahorjan, G. Scott Graham, and Kenneth +C. Sevcik, @cite{Quantitative System Performance: Computer System +Analysis Using Queueing Network Models}, Prentice Hall, +1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In +particular, see section 5.2 ("Asymptotic Bounds"). + +@auindex Lazowska, E. D. +@auindex Zahorjan, J. +@auindex Graham, G. S. +@auindex Sevcik, K. C. + + +@c +@include help/qnopenbsb.texi + +@noindent @strong{REFERENCES} + +Edward D. Lazowska, John Zahorjan, G. Scott Graham, and Kenneth +C. Sevcik, @cite{Quantitative System Performance: Computer System +Analysis Using Queueing Network Models}, Prentice Hall, +1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In +particular, see section 5.4 ("Balanced Systems Bounds"). + +@auindex Lazowska, E. D. +@auindex Zahorjan, J. +@auindex Graham, G. S. +@auindex Sevcik, K. C. + +@c +@include help/qnclosedbsb.texi + +@c +@include help/qnclosedpb.texi + +@noindent @strong{REFERENCES} + +The original paper describing PB Bounds is C. H. Hsieh and S. Lam, +@cite{Two classes of performance bounds for closed queueing networks}, +PEVA, vol. 7, n. 1, pp. 3--30, 1987 + +This function implements the non-iterative variant described in G. +Casale, R. R. Muntz, G. Serazzi, @cite{Geometric Bounds: a +Non-Iterative Analysis Technique for Closed Queueing Networks}, IEEE +Transactions on Computers, 57(6):780-794, June 2008. + +@auindex Hsieh, C. H +@auindex Lam, S. +@auindex Casale, G. +@auindex Muntz, R. R. +@auindex Serazzi, G. + +@c +@include help/qnclosedgb.texi + +@noindent @strong{REFERENCES} + +G. Casale, R. R. Muntz, G. Serazzi, +@cite{Geometric Bounds: a Non-Iterative Analysis Technique for Closed +Queueing Networks}, IEEE Transactions on Computers, 57(6):780-794, +June 2008. @url{http://doi.ieeecomputersociety.org/10.1109/TC.2008.37} + +@auindex Casale, G. +@auindex Muntz, R. R. +@auindex Serazzi, G. + +In this implementation we set @math{X^+} and @math{X^-} as the upper +and lower Asymptotic Bounds as computed by the @code{qnclosedab} +function, respectively. + +@node Utility functions +@section Utility functions + +@subsection Open or closed networks + +@include help/qnclosed.texi + +@noindent @strong{EXAMPLE} + +@example +@include demos/demo_1_qnclosed.texi +@end example + +@include help/qnopen.texi + +@c +@c Compute the visit counts +@c + +@subsection Computation of the visit counts + +For single-class networks the average number of visits 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 == P0 + V*P; +@end example +@end ifnottex + +@noindent where @math{P_{0, j}} is the probability that an external +arrival goes to service center @math{j}. If @math{\lambda_j} is the +external arrival rate to service center @math{j}, and @math{\lambda = +\sum_j \lambda_j} is the overall external arrival rate, then +@math{P_{0, j} = \lambda_j / \lambda}. + +For closed networks, the visit ratios satisfy the following equation: + +@iftex +@tex +$$\eqalign{ V_j & = \sum_{i=1}^K V_i P_{i, j} \cr + V_1 & = 1 }$$ +@end tex +@end iftex +@ifnottex +@example +V(1) == 1 && V == V*P; +@end example +@end ifnottex + +The definitions above can be extended to multiple class networks as +follows. We define the visit ratios @math{V_{s, j}} for class @math{s} +customers at service center @math{j} as follows: + +@iftex +@tex +$$\eqalign{ V_{s, j} & = \sum_{r=1}^C \sum_{i=1}^K V_{r, i} P_{r, i, s, j} \cr + V_{s, 1} & = 1 }$$ +@end tex +@end iftex +@ifnottex +@group +V_sj = sum_r sum_i V_ri P_risj, for all s,j +V_s1 = 1, for all s +@end group +@end ifnottex + +@noindent while for open networks: + +@iftex +@tex +$$V_{s, j} = P_{0, s, j} + \sum_{r=1}^C \sum_{i=1}^K V_{r, i} P_{r, i, s, j}$$ +@end tex +@end iftex +@ifnottex +@group +V_sj = P_0sj + sum_r sum_i V_ri P_risj, for all s,j +@end group +@end ifnottex + +@noindent where @math{P_{0, s, j}} is the probability that an external +arrival goes to service center @math{j} as a class-@math{s} request. +If @math{\lambda_{s, j}} is the external arrival rate of class @math{s} +requests to service center @math{j}, and @math{\lambda = \sum_s \sum_j +\lambda_{s, j}} is the overall external arrival rate to the whole system, +then @math{P_{0, s, j} = \lambda_{s, j} / \lambda}. + +@include help/qnvisits.texi + +@noindent @strong{EXAMPLE} + +@example +@include demos/demo_1_qnvisits.texi +@end example + +@subsection Other utility functions + +@c +@include help/population_mix.texi + +@noindent @strong{REFERENCES} + +Herb Schwetman, @cite{Implementing the Mean Value Algorithm for the +Solution of Queueing Network Models}, Technical Report CSD-TR-355, +Department of Computer Sciences, Purdue University, feb 15, 1982, +available at +@url{http://www.cs.purdue.edu/research/technical_reports/1980/TR +80-355.pdf} + +Note that the slightly different problem of generating all tuples +@math{k_1, k_2, \ldots, k_N} such that @math{\sum_i k_i = k} and +@math{k_i} are nonnegative integers, for some fixed integer @math{k +@geq{} 0} has been described in S. Santini, @cite{Computing the +Indices for a Complex Summation}, unpublished report, available at +@url{http://arantxa.ii.uam.es/~ssantini/writing/notes/s668_summation.pdf} + +@auindex Schwetman, H. +@auindex Santini, S. + +@c +@include help/qnmvapop.texi + +@noindent @strong{REFERENCES} + +Zahorjan, J. and Wong, E. @cite{The solution of separable queueing +network models using mean value analysis}. SIGMETRICS +Perform. Eval. Rev. 10, 3 (Sep. 1981), 80-85. DOI +@url{http://doi.acm.org/10.1145/1010629.805477} + +@auindex Zahorjan, J. +@auindex Wong, E. +
--- a/main/queueing/doc/queueingnetworks.txi Fri Apr 06 10:07:57 2012 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1217 +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 Queueing Networks -@chapter Queueing Networks - -@menu -* Introduction to QNs:: A brief introduction to Queueing Networks. -* 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 - -@cindex queueing networks - -@c -@c INTRODUCTION -@c -@node Introduction to QNs -@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. - -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. - -Requests join the queue according to a @emph{queueing policy}, such as: - -@table @strong - -@item FCFS -First-Come-First-Served - -@item LCFS-PR -Last-Come-First-Served, Preemptive Resume - -@item PS -Processor Sharing - -@item IS -Infinite Server, there is an infinite number of identical servers so -that each request always finds a server available, and there is no -queueing - -@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. - -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. - -@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 -service time, and all requests move through the system with the same -routing probabilities. - -@noindent @strong{Model Inputs} - -@table @math - -@item \lambda_i -External arrival rate to service center @math{i}. - -@item \lambda -Overall external arrival rate to the whole system: @math{\lambda = -\sum_i \lambda_i}. - -@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 -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 -\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. - -@end table - -@noindent @strong{Model Outputs} - -@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 -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 -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 -the queue, and the request being served. - -@item X_i -Throughput. @math{X_i} is the throughput of service center @math{i}. -The throughput is defined as the ratio of job completions (i.e., average -number of jobs completed over a fixed interval of time). - -@end table - -@noindent Given these output parameters, additional performance measures can -be computed as follows: - -@table @math - -@item X -System throughput, @math{X = X_1 / V_1} - -@item R -System response time, @math{R = \sum_{k=1}^K R_k V_k} - -@item Q -Average number of requests in the system, @math{Q = N-XZ} - -@end table - -For open, single-class models, the scalar @math{\lambda} denotes the -external arrival rate of requests to the system. The average number of -visits 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 -@group - K - ___ - \ -V_j = P_(0, j) + > V_i P_(i, j) - /___ - i=1 -@end group -@end example -@end ifnottex - -@noindent where @math{P_{0, j}} is the probability that an external -arrival goes to service center @math{j}. If @math{\lambda_j} is the -external arrival rate to service center @math{j}, and @math{\lambda = -\sum_j \lambda_j} is the overall external arrival rate, then -@math{P_{0, j} = \lambda_j / \lambda}. - -For closed models, the visit ratios satisfy the following equation: - -@iftex -@tex -$$\eqalign{V_1 & = 1 \cr - V_j & = \sum_{i=1}^K V_i P_{i, j}} $$ -@end tex -@end iftex -@ifnottex -@example - -V_1 = 1 - - K - ___ - \ -V_j = > V_i P_(i, j) - /___ - i=1 - -@end example -@end ifnottex - -@subsection Multiple class models - -In multiple class QN models, we assume that there exist @math{C} -different classes of requests. Each request from class @math{c} spends -on average time @math{S_{c, k}} in service at service center -@math{k}. For open models, we denote with @math{{\bf \lambda} = -\lambda_{ck}} the arrival rates, where @math{\lambda_{c, k}} is the -external arrival rate of class @math{c} customers at service center -@math{k}. For closed models, we denote with @math{{\bf N} = (N_1, N_2, -\ldots, N_C)} the population vector, where @math{N_c} is the number of -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}} -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. - -Model input and outputs can be adjusted by adding additional indexes -for the customer classes. - -@noindent @strong{Model Inputs} - -@table @math - -@item \lambda_{c, i} -External arrival rate of class-@math{c} requests to service center @math{i} - -@item \lambda -Overall external arrival rate to the whole system: @math{\lambda = \sum_c \sum_i \lambda_{c, i}} - -@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 P_{r, i, s, j} -Routing probability matrix. @math{{\bf P} = P_{r, i, s, j}} is a @math{C -\times K \times C \times K} matrix such that @math{P_{r, i, s, j}} is -the probability that a class @math{r} request which completes service -at server @math{i} will move to server @math{j} as a class @math{s} -request. - -@item 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}. - -@end table - -@noindent @strong{Model Outputs} - -@table @math - -@item U_{c, i} -Utilization of service center @math{i} 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} -Average response time experienced by class @math{c} requests on service -center @math{i}. 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} -Average number of class @math{c} requests on service center -@math{i}. 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 -throughput is defined as the rate of completion of class @math{c} -requests. - -@end table - -@noindent It is possible to define aggregate performance measures as follows: - -@table @math - -@item U_i -Utilization of service center @math{i}: -@iftex -@tex -$U_i = \sum_{c=1}^C U_{c, i}$ -@end tex -@end iftex -@ifnottex -@code{Ui = sum(U,1);} -@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}$ -@end tex -@end iftex -@ifnottex -@code{Rc = sum( V.*R, 1 );} -@end ifnottex - -@item Q_c -Average number of class @math{c} requests in the system: -@iftex -@tex -$Q_c = \sum_{i=1}^K Q_{c, i}$ -@end tex -@end iftex -@ifnottex -@code{Qc = sum( Q, 2 );} -@end ifnottex - -@item X_c -Class @math{c} throughput: -@iftex -@tex -$X_c = X_{c, 1} / V_{c, 1}$ -@end tex -@end iftex -@ifnottex -@code{Xc = X(:,1) ./ V(:,1);} -@end ifnottex - -@end table - -We can define the visit ratios @math{V_{s, j}} for class @math{s} -customers at service center @math{j} as follows: - -@iftex -@tex -$$ \eqalign{ V_{s, j} & = \sum_{r=1}^C \sum_{i=1}^K V_{r, i} P_{r, i, s, j} \cr - V_{s, 1} & = 1} $$ -@end tex -@end iftex -@ifnottex -@group -V_sj = sum_r sum_i V_ri P_risj, for all s,j -@end group -@end ifnottex - -@noindent while for open networks: - -@iftex -@tex -$$V_{s, j} = P_{0, s, j} + \sum_{r=1}^C \sum_{i=1}^K V_{r, i} P_{r, i, s, j}$$ -@end tex -@end iftex -@ifnottex -@group -V_sj = P_0sj + sum_r sum_i V_ri P_risj, for all s,j -@end group -@end ifnottex - -@noindent where @math{P_{0, s, j}} is the probability that an external -arrival goes to service center @math{j} as a class-@math{s} request. -If @math{\lambda_{s, j}} is the external arrival rate of class -@math{s} requests to service center @math{j}, and @math{\lambda = -\sum_s \sum_j \lambda_{s, j}} is the overall external arrival rate to -the whole system, then @math{P_{0, s, j} = \lambda_{s, j} / \lambda}. - -@c -@c -@c -@node Generic Algorithms -@section Generic Algorithms - -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}. - -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. - -@DOCSTRING(qnmknode) - -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. - -@DOCSTRING(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 -@verbatiminclude demo_1_qnsolve.texi -@end example - - -@c -@c -@c -@node Algorithms for Product-Form QNs -@section Algorithms for Product-Form QNs - -Product-form queueing networks fulfill the following assumptions: - -@itemize - -@item The network can consist of open and closed job classes. - -@item The following queueing disciplines are allowed: FCFS, PS, LCFS-PR and IS. - -@item Service times for FCFS nodes must be exponentially distributed and -class-independent. Service centers at PS, LCFS-PR and IS nodes can -have any kind of service time distribution with a rational Laplace -transform. Furthermore, for PS, LCFS-PR and IS nodes, different -classes of customers can have different service times. - -@item The service rate of an FCFS node is only allowed to depend on the -number of jobs at this node; in a PS, LCFS-PR and IS node the service -rate for a particular job class can also depend on the number of jobs -of that class at the node. - -@item In open networks two kinds of arrival processes are allowed: i) the -arrival process is Poisson, with arrival rate @math{\lambda} which can -depend on the number of jobs in the network. ii) the arrival process -consists of @math{U} independent Poisson arrival streams where the -@math{U} job sources are assigned to the @math{U} chains; the arrival -rate can be load dependent. - -@end itemize - -@c -@c Jackson Networks -@c - -@subsection Jackson Networks - -Jackson networks satisfy the following conditions: - -@itemize - -@item -There is only one job class in the network; the overall number of jobs -in the system is unlimited. - -@item -There are @math{N} service centers in the network. Each service center -may have Poisson arrivals from outside the system. A job can leave -the system from any node. - -@item -Arrival rates as well as routing probabilities are independent from -the number of nodes in the network. - -@item -External arrivals and service times at the service centers are -exponentially distributed, and in general can be load-dependent. - -@item -Service discipline at each node is FCFS - -@end itemize - -We define the @emph{joint probability vector} @math{\pi(k_1, k_2, -\ldots, k_N)} as the steady-state probability that there are @math{k_i} -requests at service center @math{i}, for all @math{i=1, 2, \ldots, N}. -Jackson networks have the property that the joint probability is the -product of the marginal probabilities @math{\pi_i}: - -@iftex -@tex -$$ \pi(k_1, k_2, \ldots, k_N) = \prod_{i=1}^N \pi_i(k_i) $$ -@end tex -@end iftex -@ifnottex -@example -@var{joint_prob} = prod( @var{pi} ) -@end example -@end ifnottex - -@noindent where @math{\pi_i(k_i)} is the steady-state probability -that there are @math{k_i} requests at service center @math{i}. - -@DOCSTRING(qnjackson) - -@noindent @strong{REFERENCES} - -This implementation is based on G. Bolch, S. Greiner, H. de Meer and -K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and -Performance Evaluation with Computer Science Applications}, Wiley, -1998, pp. 284--287. - -@auindex Bolch, G. -@auindex Greiner, S. -@auindex de Meer, H. -@auindex Trivedi, K. - -@subsection The Convolution Algorithm - -According to the BCMP theorem, the state probability of a closed -single class queueing network with @math{K} nodes and @math{N} requests -can be expressed as: - -@iftex -@tex -$$ \pi(k_1, k_2, \ldots, k_K) = {1 \over G(N)} \prod_{i=1}^N F_i(k_i) $$ -@end tex -@end iftex -@ifnottex -@example -@group -k = [k1, k2, @dots{} kn]; @r{population vector} -p = 1/G(N+1) \prod F(i,k); -@end group -@end example -@end ifnottex - -Here @math{\pi(k_1, k_2, \ldots, k_K)} is the joint probability of -having @math{k_i} requests at node @math{i}, for all @math{i=1, 2, -\ldots, K}. - -The @emph{convolution algorithms} computes the normalization constants -@math{{\bf G} = \left(G(0), G(1), \ldots, G(N)\right)} for single-class, closed networks -with @math{N} requests. The normalization constants are returned as -vector @code{@var{G}=[@var{G}(1), @var{G}(2), @dots{} @var{G}(N+1)]} where -@code{@var{G}(i+1)} is the value of @math{G(i)} (remember that Octave -uses 1-base vectors). The normalization constant can be used to -compute all performance measures of interest (utilization, average -response time and so on). - -@code{queueing} implements the convolution algorithm, in the function -@code{qnconvolution} and @code{qnconvolutionld}. The first one -supports single-station nodes, multiple-station nodes and IS nodes. -The second one supports networks with general load-dependent service -centers. - -@c -@c The Convolution Algorithm -@c - -@DOCSTRING(qnconvolution) - -@noindent @strong{EXAMPLE} - -The normalization constant @math{G} can be used to compute the -steady-state probabilities for a closed single class product-form -Queueing Network with @math{K} nodes. Let @code{@var{k}=[@math{k_1, -k_2, @dots{}, k_K}]} be a valid population vector. Then, the -steady-state probability @code{@var{p}(i)} to have @code{@var{k}(i)} -requests at service center @math{i} can be computed as: - -@iftex -@tex -$$ -p_i(k_i) = {(V_i S_i)^{k_i} \over G(K)} \left(G(K-k_i) - V_i S_i G(K-k_i-1)\right), \quad i=1, 2, \ldots, K -$$ -@end tex -@end iftex - -@example -@verbatiminclude demo_1_qnconvolution.texi -@print{} k(1)=1 prob=0.17975 -@print{} k(2)=2 prob=0.48404 -@print{} k(3)=0 prob=0.52779 -@end example - -@noindent @strong{NOTE} - -For a network with @math{K} service centers and @math{N} requests, -this implementation of the convolution algorithm has time and space -complexity @math{O(NK)}. - -@noindent @strong{REFERENCES} - -Jeffrey P. Buzen, @cite{Computational Algorithms for Closed Queueing -Networks with Exponential Servers}, Communications of the ACM, volume -16, number 9, september 1973, -pp. 527--531. @url{http://doi.acm.org/10.1145/362342.362345} - -@auindex Buzen, J. P. - -This implementation is based on G. Bolch, S. Greiner, H. de Meer and -K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and -Performance Evaluation with Computer Science Applications}, Wiley, -1998, pp. 313--317. - -@auindex Bolch, G. -@auindex Greiner, S. -@auindex de Meer, H. -@auindex Trivedi, K. - -@c -@c Convolution for load-dependent service centers -@c -@DOCSTRING(qnconvolutionld) - -@noindent @strong{REFERENCES} - -Herb Schwetman, @cite{Some Computational Aspects of Queueing Network -Models}, Technical Report CSD-TR-354, Department of Computer Sciences, -Purdue University, feb, 1981 (revised). -@url{http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-354.pdf} - -@auindex Schwetman, H. - -M. Reiser, H. Kobayashi, @cite{On The Convolution Algorithm for -Separable Queueing Networks}, In Proceedings of the 1976 ACM -SIGMETRICS Conference on Computer Performance Modeling Measurement and -Evaluation (Cambridge, Massachusetts, United States, March 29--31, -1976). SIGMETRICS '76. ACM, New York, NY, -pp. 109--117. @url{http://doi.acm.org/10.1145/800200.806187} - -@auindex Reiser, M. -@auindex Kobayashi, H. - -This implementation is based on G. Bolch, S. Greiner, H. de Meer and -K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and -Performance Evaluation with Computer Science Applications}, Wiley, -1998, pp. 313--317. Function @code{qnconvolutionld} is slightly -different from the version described in Bolch et al. because it -supports general load-dependent centers (while the version in the book -does not). The modification is in the definition of function -@code{F()} in @code{qnconvolutionld} which has been made similar to -function @math{f_i} defined in Schwetman, @code{Some Computational -Aspects of Queueing Network Models}. - -@auindex Bolch, G. -@auindex Greiner, S. -@auindex de Meer, H. -@auindex Trivedi, K. - - -@subsection Open networks - -@c -@c Open networks with single class -@c -@DOCSTRING(qnopensingle) - -From the results computed by this function, it is possible to derive -other quantities of interest as follows: - -@itemize - -@item -@strong{System Response Time}: The overall system response time -can be computed as -@iftex -@tex -$R_s = \sum_{i=1}^K V_i R_i$ -@end tex -@end iftex -@ifnottex -@code{R_s = dot(V,R);} -@end ifnottex - -@item -@strong{Average number of requests}: The average number of requests -in the system can be computed as: -@iftex -@tex -$Q_s = \sum_{i=1}^K Q(i)$ -@end tex -@end iftex -@ifnottex -@code{Q_s = sum(Q)} -@end ifnottex - -@end itemize - -@noindent @strong{EXAMPLE} - -@example -@verbatiminclude demo_1_qnopensingle.texi -@print{} R_s = 1.4062 -@print{} N = 4.2186 -@end example - -@noindent @strong{REFERENCES} - -G. Bolch, S. Greiner, H. de Meer and K. Trivedi, @cite{Queueing -Networks and Markov Chains: Modeling and Performance Evaluation with -Computer Science Applications}, Wiley, 1998. - -@auindex Bolch, G. -@auindex Greiner, S. -@auindex de Meer, H. -@auindex Trivedi, K. - - -@c -@c Open network with multiple classes -@c -@DOCSTRING(qnopenmulti) - -@noindent @strong{REFERENCES} - -Edward D. Lazowska, John Zahorjan, G. Scott Graham, and Kenneth C. -Sevcik, @cite{Quantitative System Performance: Computer System -Analysis Using Queueing Network Models}, Prentice Hall, -1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In -particular, see section 7.4.1 ("Open Model Solution Techniques"). - -@auindex Lazowska, E. D. -@auindex Zahorjan, J. -@auindex Graham, G. S. -@auindex Sevcik, K. C. - - -@subsection Closed Networks - -@c -@c MVA for single class, closed networks -@c - -@DOCSTRING(qnclosedsinglemva) - -From the results provided by this function, it is possible to derive -other quantities of interest as follows: - -@noindent @strong{EXAMPLE} - -@example -@verbatiminclude demo_1_qnclosedsinglemva.texi -@end example - - -@noindent @strong{REFERENCES} - -M. Reiser and S. S. Lavenberg, @cite{Mean-Value Analysis of Closed -Multichain Queuing Networks}, Journal of the ACM, vol. 27, n. 2, April -1980, pp. 313--322. @url{http://doi.acm.org/10.1145/322186.322195} - -@auindex Reiser, M. -@auindex Lavenberg, S. S. - -This implementation is described in R. Jain , @cite{The Art of Computer -Systems Performance Analysis}, Wiley, 1991, p. 577. Multi-server nodes -@c and the computation of @math{G(N)}, -are treated according to G. Bolch, S. Greiner, H. de Meer and -K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and -Performance Evaluation with Computer Science Applications}, Wiley, -1998, Section 8.2.1, "Single Class Queueing Networks". - -@auindex Jain, R. -@auindex Bolch, G. -@auindex Greiner, S. -@auindex de Meer, H. -@auindex Trivedi, K. - -@c -@c MVA for single class, closed networks with load dependent servers -@c -@DOCSTRING(qnclosedsinglemvald) - -@noindent @strong{REFERENCES} - -M. Reiser and S. S. Lavenberg, @cite{Mean-Value Analysis of Closed -Multichain Queuing Networks}, Journal of the ACM, vol. 27, n. 2, -April 1980, pp. 313--322. @url{http://doi.acm.org/10.1145/322186.322195} - -This implementation is described in G. Bolch, S. Greiner, H. de Meer -and K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling -and Performance Evaluation with Computer Science Applications}, Wiley, -1998, Section 8.2.4.1, ``Networks with Load-Deèpendent Service: Closed -Networks''. - -@auindex Bolch, G. -@auindex Greiner, S. -@auindex de Meer, H. -@auindex Trivedi, K. - -@c -@c CMVA for single class, closed networks with a single load dependent servers -@c -@DOCSTRING(qncmva) - -@noindent @strong{REFERENCES} - -G. Casale. @cite{A note on stable flow-equivalent aggregation in -closed networks}. Queueing Syst. Theory Appl., 60:193–202, December -2008. - -@auindex Casale, G. - -@c -@c Approximate MVA for single class, closed networks -@c - -@DOCSTRING(qnclosedsinglemvaapprox) - -@noindent @strong{REFERENCES} - -This implementation is based on Edward D. Lazowska, John Zahorjan, -G. Scott Graham, and Kenneth C. Sevcik, @cite{Quantitative System -Performance: Computer System Analysis Using Queueing Network Models}, -Prentice Hall, -1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In -particular, see section 6.4.2.2 ("Approximate Solution Techniques"). - -@auindex Lazowska, E. D. -@auindex Zahorjan, J. -@auindex Graham, G. S. -@auindex Sevcik, K. C. - - -@c -@c MVA for multiple class, closed networks -@c -@DOCSTRING(qnclosedmultimva) - -@noindent @strong{NOTE} - -Given a network with @math{K} service centers, @math{C} job classes and -population vector @math{{\bf N}=(N_1, N_2, \ldots, N_C)}, the MVA -algorithm requires space @math{O(C \prod_i (N_i + 1))}. The time -complexity is @math{O(CK\prod_i (N_i + 1))}. This implementation is -slightly more space-efficient (see details in the code). While the space -requirement can be mitigated by using some optimizations, the time -complexity can not. If you need to analyze large closed networks you -should consider the @command{qnclosedmultimvaapprox} function, which -implements the approximate MVA algorithm. Note however that -@command{qnclosedmultimvaapprox} will only provide approximate results. - - -@noindent @strong{REFERENCES} - -M. Reiser and S. S. Lavenberg, @cite{Mean-Value Analysis of Closed -Multichain Queuing Networks}, Journal of the ACM, vol. 27, n. 2, April -1980, pp. 313--322. @url{http://doi.acm.org/10.1145/322186.322195} - -@auindex Reiser, M. -@auindex Lavenberg, S. S. - -This implementation is based on G. Bolch, S. Greiner, H. de Meer and -K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and -Performance Evaluation with Computer Science Applications}, Wiley, -1998 and Edward D. Lazowska, John Zahorjan, G. Scott Graham, and -Kenneth C. Sevcik, @cite{Quantitative System Performance: Computer -System Analysis Using Queueing Network Models}, Prentice Hall, -1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In -particular, see section 7.4.2.1 ("Exact Solution Techniques"). - -@auindex Bolch, G. -@auindex Greiner, S. -@auindex de Meer, H. -@auindex Trivedi, K. -@auindex Lazowska, E. D. -@auindex Zahorjan, J. -@auindex Graham, G. S. -@auindex Sevcik, K. C. - -@c -@c Approximate MVA, with Bard-Schweitzer approximation -@c -@DOCSTRING(qnclosedmultimvaapprox) - -@noindent @strong{REFERENCES} - -Y. Bard, @cite{Some Extensions to Multiclass Queueing Network Analysis}, -proc. 4th Int. Symp. on Modelling and Performance Evaluation of -Computer Systems, feb. 1979, pp. 51--62. - -@auindex Bard, Y. - -P. Schweitzer, @cite{Approximate Analysis of Multiclass Closed -Networks of Queues}, Proc. Int. Conf. on Stochastic Control and -Optimization, jun 1979, pp. 25--29. - -@auindex Schweitzer, P. - -This implementation is based on Edward D. Lazowska, John Zahorjan, G. -Scott Graham, and Kenneth C. Sevcik, @cite{Quantitative System -Performance: Computer System Analysis Using Queueing Network Models}, -Prentice Hall, -1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In -particular, see section 7.4.2.2 ("Approximate Solution -Techniques"). This implementation is slightly different from the one -described above, as it computes the average response times @math{R} -instead of the residence times. - -@auindex Lazowska, E. D. -@auindex Zahorjan, J. -@auindex Graham, G. S. -@auindex Sevcik, K. C. - -@subsection Mixed Networks - -@c -@c MVA for mixed networks -@c -@DOCSTRING(qnmix) - -@noindent @strong{REFERENCES} - -Edward D. Lazowska, John Zahorjan, G. Scott Graham, and Kenneth C. -Sevcik, @cite{Quantitative System Performance: Computer System -Analysis Using Queueing Network Models}, Prentice Hall, -1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In -particular, see section 7.4.3 ("Mixed Model Solution Techniques"). -Note that in this function we compute the mean response time @math{R} -instead of the mean residence time as in the reference. - -@auindex Lazowska, E. D. -@auindex Zahorjan, J. -@auindex Graham, G. S. -@auindex Sevcik, K. C. - -Herb Schwetman, @cite{Implementing the Mean Value Algorithm for the -Solution of Queueing Network Models}, Technical Report CSD-TR-355, -Department of Computer Sciences, Purdue University, feb 15, 1982, -available at -@url{http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-355.pdf} - -@auindex Schwetman, H. - - -@node Algorithms for non Product-form QNs -@section Algorithms for non Product-Form QNs - -@c -@c MVABLO algorithm for approximate analysis of closed, single class -@c QN with blocking -@c -@DOCSTRING(qnmvablo) - -@noindent @strong{REFERENCES} - -Ian F. Akyildiz, @cite{Mean Value Analysis for Blocking Queueing -Networks}, IEEE Transactions on Software Engineering, vol. 14, n. 2, -april 1988, pp. 418--428. @url{http://dx.doi.org/10.1109/32.4663} - -@auindex Akyildiz, I. F. - -@DOCSTRING(qnmarkov) - -@c -@c -@c -@node Bounds on performance -@section Bounds on performance - -@c -@DOCSTRING(qnopenab) - -@noindent @strong{REFERENCES} - -Edward D. Lazowska, John Zahorjan, G. Scott Graham, and Kenneth -C. Sevcik, @cite{Quantitative System Performance: Computer System -Analysis Using Queueing Network Models}, Prentice Hall, -1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In -particular, see section 5.2 ("Asymptotic Bounds"). - -@auindex Lazowska, E. D. -@auindex Zahorjan, J. -@auindex Graham, G. S. -@auindex Sevcik, K. C. - -@c -@DOCSTRING(qnclosedab) - -@noindent @strong{REFERENCES} - -@noindent Edward D. Lazowska, John Zahorjan, G. Scott Graham, and Kenneth -C. Sevcik, @cite{Quantitative System Performance: Computer System -Analysis Using Queueing Network Models}, Prentice Hall, -1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In -particular, see section 5.2 ("Asymptotic Bounds"). - -@auindex Lazowska, E. D. -@auindex Zahorjan, J. -@auindex Graham, G. S. -@auindex Sevcik, K. C. - - -@c -@DOCSTRING(qnopenbsb) - -@noindent @strong{REFERENCES} - -Edward D. Lazowska, John Zahorjan, G. Scott Graham, and Kenneth -C. Sevcik, @cite{Quantitative System Performance: Computer System -Analysis Using Queueing Network Models}, Prentice Hall, -1984. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. In -particular, see section 5.4 ("Balanced Systems Bounds"). - -@auindex Lazowska, E. D. -@auindex Zahorjan, J. -@auindex Graham, G. S. -@auindex Sevcik, K. C. - -@c -@DOCSTRING(qnclosedbsb) - -@c -@DOCSTRING(qnclosedpb) - -@noindent @strong{REFERENCES} - -The original paper describing PB Bounds is C. H. Hsieh and S. Lam, -@cite{Two classes of performance bounds for closed queueing networks}, -PEVA, vol. 7, n. 1, pp. 3--30, 1987 - -This function implements the non-iterative variant described in G. -Casale, R. R. Muntz, G. Serazzi, @cite{Geometric Bounds: a -Non-Iterative Analysis Technique for Closed Queueing Networks}, IEEE -Transactions on Computers, 57(6):780-794, June 2008. - -@auindex Hsieh, C. H -@auindex Lam, S. -@auindex Casale, G. -@auindex Muntz, R. R. -@auindex Serazzi, G. - -@c -@DOCSTRING(qnclosedgb) - -@noindent @strong{REFERENCES} - -G. Casale, R. R. Muntz, G. Serazzi, -@cite{Geometric Bounds: a Non-Iterative Analysis Technique for Closed -Queueing Networks}, IEEE Transactions on Computers, 57(6):780-794, -June 2008. @url{http://doi.ieeecomputersociety.org/10.1109/TC.2008.37} - -@auindex Casale, G. -@auindex Muntz, R. R. -@auindex Serazzi, G. - -In this implementation we set @math{X^+} and @math{X^-} as the upper -and lower Asymptotic Bounds as computed by the @code{qnclosedab} -function, respectively. - -@node Utility functions -@section Utility functions - -@subsection Open or closed networks - -@DOCSTRING(qnclosed) - -@noindent @strong{EXAMPLE} - -@example -@verbatiminclude demo_1_qnclosed.texi -@end example - -@DOCSTRING(qnopen) - -@c -@c Compute the visit counts -@c - -@subsection Computation of the visit counts - -For single-class networks the average number of visits 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 == P0 + V*P; -@end example -@end ifnottex - -@noindent where @math{P_{0, j}} is the probability that an external -arrival goes to service center @math{j}. If @math{\lambda_j} is the -external arrival rate to service center @math{j}, and @math{\lambda = -\sum_j \lambda_j} is the overall external arrival rate, then -@math{P_{0, j} = \lambda_j / \lambda}. - -For closed networks, the visit ratios satisfy the following equation: - -@iftex -@tex -$$\eqalign{ V_j & = \sum_{i=1}^K V_i P_{i, j} \cr - V_1 & = 1 }$$ -@end tex -@end iftex -@ifnottex -@example -V(1) == 1 && V == V*P; -@end example -@end ifnottex - -The definitions above can be extended to multiple class networks as -follows. We define the visit ratios @math{V_{s, j}} for class @math{s} -customers at service center @math{j} as follows: - -@iftex -@tex -$$\eqalign{ V_{s, j} & = \sum_{r=1}^C \sum_{i=1}^K V_{r, i} P_{r, i, s, j} \cr - V_{s, 1} & = 1 }$$ -@end tex -@end iftex -@ifnottex -@group -V_sj = sum_r sum_i V_ri P_risj, for all s,j -V_s1 = 1, for all s -@end group -@end ifnottex - -@noindent while for open networks: - -@iftex -@tex -$$V_{s, j} = P_{0, s, j} + \sum_{r=1}^C \sum_{i=1}^K V_{r, i} P_{r, i, s, j}$$ -@end tex -@end iftex -@ifnottex -@group -V_sj = P_0sj + sum_r sum_i V_ri P_risj, for all s,j -@end group -@end ifnottex - -@noindent where @math{P_{0, s, j}} is the probability that an external -arrival goes to service center @math{j} as a class-@math{s} request. -If @math{\lambda_{s, j}} is the external arrival rate of class @math{s} -requests to service center @math{j}, and @math{\lambda = \sum_s \sum_j -\lambda_{s, j}} is the overall external arrival rate to the whole system, -then @math{P_{0, s, j} = \lambda_{s, j} / \lambda}. - -@DOCSTRING(qnvisits) - -@noindent @strong{EXAMPLE} - -@example -@verbatiminclude demo_1_qnvisits.texi -@end example - -@subsection Other utility functions - -@c -@DOCSTRING(population_mix) - -@noindent @strong{REFERENCES} - -Herb Schwetman, @cite{Implementing the Mean Value Algorithm for the -Solution of Queueing Network Models}, Technical Report CSD-TR-355, -Department of Computer Sciences, Purdue University, feb 15, 1982, -available at -@url{http://www.cs.purdue.edu/research/technical_reports/1980/TR -80-355.pdf} - -Note that the slightly different problem of generating all tuples -@math{k_1, k_2, \ldots, k_N} such that @math{\sum_i k_i = k} and -@math{k_i} are nonnegative integers, for some fixed integer @math{k -@geq{} 0} has been described in S. Santini, @cite{Computing the -Indices for a Complex Summation}, unpublished report, available at -@url{http://arantxa.ii.uam.es/~ssantini/writing/notes/s668_summation.pdf} - -@auindex Schwetman, H. -@auindex Santini, S. - -@c -@DOCSTRING(qnmvapop) - -@noindent @strong{REFERENCES} - -Zahorjan, J. and Wong, E. @cite{The solution of separable queueing -network models using mean value analysis}. SIGMETRICS -Perform. Eval. Rev. 10, 3 (Sep. 1981), 80-85. DOI -@url{http://doi.acm.org/10.1145/1010629.805477} - -@auindex Zahorjan, J. -@auindex Wong, E. -
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/queueing/doc/references.texi Fri Apr 06 16:04:05 2012 +0000 @@ -0,0 +1,122 @@ +@c -*- texinfo -*- + +@c Copyright (C) 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 References +@chapter References + +@table @asis + +@item [Aky88] +Ian F. Akyildiz, @cite{Mean Value Analysis for Blocking Queueing +Networks}, IEEE Transactions on Software Engineering, vol. 14, n. 2, +april 1988, pp. 418--428. DOI @uref{http://dx.doi.org/10.1109/32.4663, 10.1109/32.4663} + +@item [Bar79] +Y. Bard, @cite{Some Extensions to Multiclass Queueing Network Analysis}, +proc. 4th Int. Symp. on Modelling and Performance Evaluation of +Computer Systems, feb. 1979, pp. 51--62. + +@item [BCMP75] +Forest Baskett, K. Mani Chandy, Richard R. Muntz, and Fernando G. Palacios. 1975. @cite{Open, Closed, and Mixed Networks of Queues with Different Classes of Customers}. J. ACM 22, 2 (April 1975), 248—260, DOI @uref{http://doi.acm.org/10.1145/321879.321887, 10.1145/321879.321887} + +@item [BGMT98] +G. Bolch, S. Greiner, H. de Meer and +K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and +Performance Evaluation with Computer Science Applications}, Wiley, +1998. + +@item [Buz73] +Jeffrey P. Buzen, @cite{Computational Algorithms for Closed Queueing +Networks with Exponential Servers}, Communications of the ACM, volume +16, number 9, september 1973, +pp. 527--531. DOI @uref{http://doi.acm.org/10.1145/362342.362345, 10.1145/362342.362345} + +@item [CMS08] +G. Casale, R. R. Muntz, G. Serazzi, +@cite{Geometric Bounds: a Non-Iterative Analysis Technique for Closed +Queueing Networks}, IEEE Transactions on Computers, 57(6):780-794, +June 2008. DOI @uref{http://doi.ieeecomputersociety.org/10.1109/TC.2008.37, 10.1109/TC.2008.37} + +@item [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} +and can be used under the terms of the @uref{http://www.gnu.org/copyleft/fdl.html, GNU Free Documentation License (FDL)} + +@item [Jac04] +James R. Jackson, @cite{Jobshop-Like Queueing Systems}, Vol. 50, No. 12, Ten Most Influential Titles of "Management Science's" First Fifty Years (Dec., 2004), pp. 1796-1802, @uref{http://www.jstor.org/stable/30046149, available online} + +@item [Jai91] +R. Jain, @cite{The Art of Computer Systems Performance Analysis}, +Wiley, 1991, p. 577. + +@item [HsLa87] +C. H. Hsieh and S. Lam, +@cite{Two classes of performance bounds for closed queueing networks}, +PEVA, vol. 7, n. 1, pp. 3--30, 1987 + +@item [LZGS84] +Edward D. Lazowska, John Zahorjan, G. Scott Graham, and Kenneth C. +Sevcik, @cite{Quantitative System Performance: Computer System +Analysis Using Queueing Network Models}, Prentice Hall, +1984. @uref{http://www.cs.washington.edu/homes/lazowska/qsp/, available online}. + +@item [ReKo76] +M. Reiser, H. Kobayashi, @cite{On The Convolution Algorithm for +Separable Queueing Networks}, In Proceedings of the 1976 ACM +SIGMETRICS Conference on Computer Performance Modeling Measurement and +Evaluation (Cambridge, Massachusetts, United States, March 29--31, +1976). SIGMETRICS '76. ACM, New York, NY, +pp. 109--117. DOI @uref{http://doi.acm.org/10.1145/800200.806187, 10.1145/800200.806187} + +@item [ReLa80] +M. Reiser and S. S. Lavenberg, @cite{Mean-Value Analysis of Closed +Multichain Queuing Networks}, Journal of the ACM, vol. 27, n. 2, April +1980, pp. 313--322. DOI @uref{http://doi.acm.org/10.1145/322186.322195, 10.1145/322186.322195} + +@item [Sch79] +P. Schweitzer, @cite{Approximate Analysis of Multiclass Closed Networks of +Queues}, Proc. Int. Conf. on Stochastic Control and Optimization, jun +1979, pp. 25—29 + +@item [Sch81] +Herb Schwetman, @cite{Some Computational +Aspects of Queueing Network Models}, @uref{http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-354.pdf, Technical Report CSD-TR-354}, +Department of Computer Sciences, Purdue University, feb, 1981 +(revised). + +@item [Sch82] +Herb Schwetman, @cite{Implementing the Mean Value Algorithm for the +Solution of Queueing Network Models}, @uref{http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-355.pdf, Technical Report CSD-TR-355}, +Department of Computer Sciences, Purdue University, feb 15, 1982. + +@item [Tij03] +H. C. Tijms, @cite{A first course in stochastic models}, +John Wiley and Sons, 2003, ISBN 0471498807, ISBN 9780471498803, +DOI @uref{http://dx.doi.org/10.1002/047001363X, 10.1002/047001363X} + +@item [ZaWo81] +Zahorjan, J. and Wong, E. @cite{The solution of separable queueing +network models using mean value analysis}. SIGMETRICS +Perform. Eval. Rev. 10, 3 (Sep. 1981), 80-85. DOI +DOI @uref{http://doi.acm.org/10.1145/1010629.805477, 10.1145/1010629.805477} + +@end table
--- a/main/queueing/doc/references.txi Fri Apr 06 10:07:57 2012 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,122 +0,0 @@ -@c -*- texinfo -*- - -@c Copyright (C) 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 References -@chapter References - -@table @asis - -@item [Aky88] -Ian F. Akyildiz, @cite{Mean Value Analysis for Blocking Queueing -Networks}, IEEE Transactions on Software Engineering, vol. 14, n. 2, -april 1988, pp. 418--428. DOI @uref{http://dx.doi.org/10.1109/32.4663, 10.1109/32.4663} - -@item [Bar79] -Y. Bard, @cite{Some Extensions to Multiclass Queueing Network Analysis}, -proc. 4th Int. Symp. on Modelling and Performance Evaluation of -Computer Systems, feb. 1979, pp. 51--62. - -@item [BCMP75] -Forest Baskett, K. Mani Chandy, Richard R. Muntz, and Fernando G. Palacios. 1975. @cite{Open, Closed, and Mixed Networks of Queues with Different Classes of Customers}. J. ACM 22, 2 (April 1975), 248—260, DOI @uref{http://doi.acm.org/10.1145/321879.321887, 10.1145/321879.321887} - -@item [BGMT98] -G. Bolch, S. Greiner, H. de Meer and -K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and -Performance Evaluation with Computer Science Applications}, Wiley, -1998. - -@item [Buz73] -Jeffrey P. Buzen, @cite{Computational Algorithms for Closed Queueing -Networks with Exponential Servers}, Communications of the ACM, volume -16, number 9, september 1973, -pp. 527--531. DOI @uref{http://doi.acm.org/10.1145/362342.362345, 10.1145/362342.362345} - -@item [CMS08] -G. Casale, R. R. Muntz, G. Serazzi, -@cite{Geometric Bounds: a Non-Iterative Analysis Technique for Closed -Queueing Networks}, IEEE Transactions on Computers, 57(6):780-794, -June 2008. DOI @uref{http://doi.ieeecomputersociety.org/10.1109/TC.2008.37, 10.1109/TC.2008.37} - -@item [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} -and can be used under the terms of the @uref{http://www.gnu.org/copyleft/fdl.html, GNU Free Documentation License (FDL)} - -@item [Jac04] -James R. Jackson, @cite{Jobshop-Like Queueing Systems}, Vol. 50, No. 12, Ten Most Influential Titles of "Management Science's" First Fifty Years (Dec., 2004), pp. 1796-1802, @uref{http://www.jstor.org/stable/30046149, available online} - -@item [Jai91] -R. Jain, @cite{The Art of Computer Systems Performance Analysis}, -Wiley, 1991, p. 577. - -@item [HsLa87] -C. H. Hsieh and S. Lam, -@cite{Two classes of performance bounds for closed queueing networks}, -PEVA, vol. 7, n. 1, pp. 3--30, 1987 - -@item [LZGS84] -Edward D. Lazowska, John Zahorjan, G. Scott Graham, and Kenneth C. -Sevcik, @cite{Quantitative System Performance: Computer System -Analysis Using Queueing Network Models}, Prentice Hall, -1984. @uref{http://www.cs.washington.edu/homes/lazowska/qsp/, available online}. - -@item [ReKo76] -M. Reiser, H. Kobayashi, @cite{On The Convolution Algorithm for -Separable Queueing Networks}, In Proceedings of the 1976 ACM -SIGMETRICS Conference on Computer Performance Modeling Measurement and -Evaluation (Cambridge, Massachusetts, United States, March 29--31, -1976). SIGMETRICS '76. ACM, New York, NY, -pp. 109--117. DOI @uref{http://doi.acm.org/10.1145/800200.806187, 10.1145/800200.806187} - -@item [ReLa80] -M. Reiser and S. S. Lavenberg, @cite{Mean-Value Analysis of Closed -Multichain Queuing Networks}, Journal of the ACM, vol. 27, n. 2, April -1980, pp. 313--322. DOI @uref{http://doi.acm.org/10.1145/322186.322195, 10.1145/322186.322195} - -@item [Sch79] -P. Schweitzer, @cite{Approximate Analysis of Multiclass Closed Networks of -Queues}, Proc. Int. Conf. on Stochastic Control and Optimization, jun -1979, pp. 25—29 - -@item [Sch81] -Herb Schwetman, @cite{Some Computational -Aspects of Queueing Network Models}, @uref{http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-354.pdf, Technical Report CSD-TR-354}, -Department of Computer Sciences, Purdue University, feb, 1981 -(revised). - -@item [Sch82] -Herb Schwetman, @cite{Implementing the Mean Value Algorithm for the -Solution of Queueing Network Models}, @uref{http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-355.pdf, Technical Report CSD-TR-355}, -Department of Computer Sciences, Purdue University, feb 15, 1982. - -@item [Tij03] -H. C. Tijms, @cite{A first course in stochastic models}, -John Wiley and Sons, 2003, ISBN 0471498807, ISBN 9780471498803, -DOI @uref{http://dx.doi.org/10.1002/047001363X, 10.1002/047001363X} - -@item [ZaWo81] -Zahorjan, J. and Wong, E. @cite{The solution of separable queueing -network models using mean value analysis}. SIGMETRICS -Perform. Eval. Rev. 10, 3 (Sep. 1981), 80-85. DOI -DOI @uref{http://doi.acm.org/10.1145/1010629.805477, 10.1145/1010629.805477} - -@end table
--- a/main/queueing/doc/singlestation.txi Fri Apr 06 10:07:57 2012 +0000 +++ b/main/queueing/doc/singlestation.txi Fri Apr 06 16:04:05 2012 +0000 @@ -79,7 +79,7 @@ with average service rate @math{\mu}. The system is stable if @math{\lambda < \mu}. -@DOCSTRING(qnmm1) +@include help/qnmm1.texi @noindent @strong{REFERENCES} @@ -109,7 +109,7 @@ @code{mu(n) = min(m,n)*mu} @end example -@DOCSTRING(qnmmm) +@include help/qnmmm.texi @noindent @strong{REFERENCES} @@ -134,7 +134,7 @@ that queueing never occurs. The @math{M/M/\infty} system is always stable. -@DOCSTRING(qnmminf) +@include help/qnmminf.texi @noindent @strong{REFERENCES} @@ -160,7 +160,7 @@ always stable, regardless of the arrival and service rates @math{\lambda} and @math{\mu}. -@DOCSTRING(qnmm1k) +@include help/qnmm1k.texi @c @c M/M/m/k @@ -173,7 +173,7 @@ where @math{1 \leq m \leq K}. The queue is made of @math{K-m} slots. The @math{M/M/m/K} system is always stable. -@DOCSTRING(qnmmmk) +@include help/qnmmmk.texi @noindent @strong{REFERENCES} @@ -186,8 +186,6 @@ @auindex de Meer, H. @auindex Trivedi, K. -@DOCSTRING(qnmmmk_alt) - @c @c Approximate M/M/m @c @@ -198,7 +196,7 @@ to a single queue. Differently from the @math{M/M/m} system, in the asymmetric @math{M/M/m} each server may have a different service time. -@DOCSTRING(qnammm) +@include help/qnammm.texi @noindent @strong{REFERENCES} @@ -217,12 +215,12 @@ @node The M/G/1 System @section The @math{M/G/1} System -@DOCSTRING(qnmg1) +@include help/qnmg1.texi @c @c @c @node The M/Hm/1 System @section The @math{M/H_m/1} System -@DOCSTRING(qnmh1) +@include help/qnmh1.texi
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/queueing/doc/summary.texi Fri Apr 06 16:04:05 2012 +0000 @@ -0,0 +1,124 @@ +@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 Summary +@chapter Summary + +This document describes the @code{queueing} toolbox for GNU Octave +(@code{queueing} in short). The @code{queueing} toolbox, previously +known as @code{qnetworks}, is a collection of functions written in GNU +Octave for analyzing queueing networks and Markov +chains. Specifically, @code{queueing} contains functions for analyzing +Jackson networks, open, closed or mixed product-form BCMP networks, +and computation of performance bounds. The following algorithms have +been implemented + +@itemize + +@item Convolution for closed, single-class product-form networks +with load-dependent service centers; + +@item Exact and approximate Mean Value Analysis (MVA) for single and +multiple class product-form closed networks; + +@item MVA for mixed, multiple class product-form networks +with load-independent service centers; + +@item Approximate MVA for closed, single-class networks with blocking +(MVABLO algorithm by F. Akyildiz); + +@item Asymptotic Bounds, Balanced System Bounds and Geometric Bounds; + +@end itemize + +@noindent @code{queueing} +provides functions for analyzing the following kind of single-station +queueing systems: + +@itemize + +@item @math{M/M/1} +@item @math{M/M/m} +@item @math{M/M/\infty} +@item @math{M/M/1/k} single-server, finite capacity system +@item @math{M/M/m/k} multiple-server, finite capacity system +@item Asymmetric @math{M/M/m} +@item @math{M/G/1} (general service time distribution) +@item @math{M/H_m/1} (Hyperexponential service time distribution) +@end itemize + +Functions for Markov chain analysis are also provided: + +@itemize + +@item Birth-death process; +@item Transient and steady-state occupancy probabilities; +@item Mean times to absorption; +@item Expected sojourn times and time-averaged sojourn times; +@item Mean first passage times; + +@end itemize + +The @code{queueing} toolbox is distributed under the terms of the GNU +General Public License (GPL), version 3 or later +(@pxref{Copying}). You are encouraged to share this software with +others, and make this package more useful by contributing additional +functions and reporting problems. @xref{Contributing Guidelines}. + +If you use the @code{queueing} toolbox in a technical paper, please +cite it as: + +@quotation +Moreno Marzolla, @emph{The qnetworks Toolbox: A Software Package for +Queueing Networks Analysis}. Khalid Al-Begain, Dieter Fiems and +William J. Knottenbelt, Editors, Proceedings 17th International +Conference on Analytical and Stochastic Modeling Techniques and +Applications (ASMTA 2010) Cardiff, UK, June 14--16, 2010, volume 6148 +of Lecture Notes in Computer Science, Springer, pp. 102--116, ISBN +978-3-642-13567-5 +@end quotation + +If you use BibTeX, this is the citation block: + +@verbatim +@inproceedings{queueing, + author = {Moreno Marzolla}, + title = {The qnetworks Toolbox: A Software Package for Queueing + Networks Analysis}, + booktitle = {Analytical and Stochastic Modeling Techniques and + Applications, 17th International Conference, + ASMTA 2010, Cardiff, UK, June 14-16, 2010. Proceedings}, + editor = {Khalid Al-Begain and Dieter Fiems and William J. Knottenbelt}, + year = {2010}, + publisher = {Springer}, + series = {Lecture Notes in Computer Science}, + volume = {6148}, + pages = {102--116}, + ee = {http://dx.doi.org/10.1007/978-3-642-13568-2_8}, + isbn = {978-3-642-13567-5} +} +@end verbatim + +An early draft of the paper above is available as Technical Report +@uref{http://www.informatica.unibo.it/ricerca/ublcs/2010/UBLCS-2010-04, +UBLCS-2010-04}, February 2010, Department of Computer Science, +University of Bologna, Italy. +
--- a/main/queueing/doc/summary.txi Fri Apr 06 10:07:57 2012 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,124 +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 Summary -@chapter Summary - -This document describes the @code{queueing} toolbox for GNU Octave -(@code{queueing} in short). The @code{queueing} toolbox, previously -known as @code{qnetworks}, is a collection of functions written in GNU -Octave for analyzing queueing networks and Markov -chains. Specifically, @code{queueing} contains functions for analyzing -Jackson networks, open, closed or mixed product-form BCMP networks, -and computation of performance bounds. The following algorithms have -been implemented - -@itemize - -@item Convolution for closed, single-class product-form networks -with load-dependent service centers; - -@item Exact and approximate Mean Value Analysis (MVA) for single and -multiple class product-form closed networks; - -@item MVA for mixed, multiple class product-form networks -with load-independent service centers; - -@item Approximate MVA for closed, single-class networks with blocking -(MVABLO algorithm by F. Akyildiz); - -@item Asymptotic Bounds, Balanced System Bounds and Geometric Bounds; - -@end itemize - -@noindent @code{queueing} -provides functions for analyzing the following kind of single-station -queueing systems: - -@itemize - -@item @math{M/M/1} -@item @math{M/M/m} -@item @math{M/M/\infty} -@item @math{M/M/1/k} single-server, finite capacity system -@item @math{M/M/m/k} multiple-server, finite capacity system -@item Asymmetric @math{M/M/m} -@item @math{M/G/1} (general service time distribution) -@item @math{M/H_m/1} (Hyperexponential service time distribution) -@end itemize - -Functions for Markov chain analysis are also provided: - -@itemize - -@item Birth-death process; -@item Transient and steady-state occupancy probabilities; -@item Mean times to absorption; -@item Expected sojourn times and time-averaged sojourn times; -@item Mean first passage times; - -@end itemize - -The @code{queueing} toolbox is distributed under the terms of the GNU -General Public License (GPL), version 3 or later -(@pxref{Copying}). You are encouraged to share this software with -others, and make this package more useful by contributing additional -functions and reporting problems. @xref{Contributing Guidelines}. - -If you use the @code{queueing} toolbox in a technical paper, please -cite it as: - -@quotation -Moreno Marzolla, @emph{The qnetworks Toolbox: A Software Package for -Queueing Networks Analysis}. Khalid Al-Begain, Dieter Fiems and -William J. Knottenbelt, Editors, Proceedings 17th International -Conference on Analytical and Stochastic Modeling Techniques and -Applications (ASMTA 2010) Cardiff, UK, June 14--16, 2010, volume 6148 -of Lecture Notes in Computer Science, Springer, pp. 102--116, ISBN -978-3-642-13567-5 -@end quotation - -If you use BibTeX, this is the citation block: - -@verbatim -@inproceedings{queueing, - author = {Moreno Marzolla}, - title = {The qnetworks Toolbox: A Software Package for Queueing - Networks Analysis}, - booktitle = {Analytical and Stochastic Modeling Techniques and - Applications, 17th International Conference, - ASMTA 2010, Cardiff, UK, June 14-16, 2010. Proceedings}, - editor = {Khalid Al-Begain and Dieter Fiems and William J. Knottenbelt}, - year = {2010}, - publisher = {Springer}, - series = {Lecture Notes in Computer Science}, - volume = {6148}, - pages = {102--116}, - ee = {http://dx.doi.org/10.1007/978-3-642-13568-2_8}, - isbn = {978-3-642-13567-5} -} -@end verbatim - -An early draft of the paper above is available as Technical Report -@uref{http://www.informatica.unibo.it/ricerca/ublcs/2010/UBLCS-2010-04, -UBLCS-2010-04}, February 2010, Department of Computer Science, -University of Bologna, Italy. -