Mercurial > forge
changeset 9761:a5960d05d2ca octave-forge
new files added
| author | mmarzolla |
|---|---|
| date | Sun, 18 Mar 2012 15:35:02 +0000 |
| parents | 801e6ee8521b |
| children | 1bc4fc356028 |
| files | main/queueing/ChangeLog main/queueing/NEWS main/queueing/doc/Makefile main/queueing/doc/markovchains.txi main/queueing/doc/queueing.html main/queueing/doc/queueing.pdf main/queueing/doc/queueing.texi main/queueing/doc/references.txi main/queueing/inst/ctmc_exps.m main/queueing/inst/ctmc_fpt.m main/queueing/inst/ctmc_mtta.m main/queueing/inst/ctmc_taexps.m main/queueing/inst/dtmc_exps.m main/queueing/inst/dtmc_fpt.m main/queueing/inst/dtmc_mtta.m main/queueing/inst/dtmc_taexps.m |
| diffstat | 16 files changed, 1170 insertions(+), 531 deletions(-) [+] |
line wrap: on
line diff
--- a/main/queueing/ChangeLog Sun Mar 18 15:21:33 2012 +0000 +++ b/main/queueing/ChangeLog Sun Mar 18 15:35:02 2012 +0000 @@ -17,6 +17,8 @@ * dtmc_bd() added * ctmc_check_Q() added * dtmc_mtta() added + * dtmc_exps() added + * dtmc_taexps() added * Miscellaneous fixes/improvements to the documentation 2012-02-04 Moreno Marzolla <marzolla@cs.unibo.it>
--- a/main/queueing/NEWS Sun Mar 18 15:21:33 2012 +0000 +++ b/main/queueing/NEWS Sun Mar 18 15:35:02 2012 +0000 @@ -12,7 +12,7 @@ solution. ** The following new functions have been added: dtmc_bd(), dtmc_mtta(), - ctmc_check_Q() + ctmc_check_Q(), dtmc_exps(), dtmc_taexps() ** The following deprecated functions have been removed: ctmc_bd_solve(), ctmc_solve(), dtmc_solve()
--- a/main/queueing/doc/Makefile Sun Mar 18 15:21:33 2012 +0000 +++ b/main/queueing/doc/Makefile Sun Mar 18 15:35:02 2012 +0000 @@ -1,5 +1,5 @@ DOC=queueing -CHAPTERS=summary.texi installation.texi markovchains.texi singlestation.texi queueingnetworks.texi conf.texi ack.texi contributing.texi gpl.texi gettingstarted.texi +CHAPTERS=summary.texi installation.texi markovchains.texi singlestation.texi queueingnetworks.texi conf.texi ack.texi contributing.texi gpl.texi gettingstarted.texi references.texi DISTFILES=README INSTALL $(DOC).pdf $(DOC).html $(DOC).texi .PHONY: clean
--- a/main/queueing/doc/markovchains.txi Sun Mar 18 15:21:33 2012 +0000 +++ b/main/queueing/doc/markovchains.txi Sun Mar 18 15:35:02 2012 +0000 @@ -68,6 +68,8 @@ @menu * State occupancy probabilities (DTMC):: * Birth-death process (DTMC):: +* Expected number of visits (DTMC):: +* Time-averaged expected sojourn times (DTMC):: * First passage times (DTMC):: * Mean time to absorption (DTMC):: @end menu @@ -124,9 +126,78 @@ @node Birth-death process (DTMC) @subsection Birth-death process -@c @DOCSTRING(dtmc_bd) +@c +@node Expected number of visits (DTMC) +@subsection Expected Number of Visits + +Given a @math{N} state discrete-time Markov chain with transition +matrix @math{\bf P} and an integer @math{n @geq{} 0}, we let +@math{L-I(n)} be the the expected number of visits to state @math{i} +during the first @math{n} transitions. The vector @math{{\bf L}(n) = +(L_1(n), L_2(n), @dots{}, L_N(n))} is defined as: + +@iftex +@tex +$$ {\bf L}(n) = \sum_{i=0}^n {\bf \pi}(i) = \sum_{i=0}^n {\bf \pi}(0) {\bf P}^i $$ +@end tex +@end iftex +@ifnottex +@example +@group + n n + ___ ___ + \ \ i +L(n) = > pi(i) = > pi(0) P + /___ /___ + i=0 i=0 +@end group +@end example +@end ifnottex + +@noindent where @math{{\bf \pi}(i) = {\bf \pi}(0){\bf P}^i} is the state occupancy probability +after @math{i} transitions. + +If @math{\bf P} is absorbing, we can rearrange the states to rewrite +@math{\bf P} as: + +@iftex +@tex +$$ {\bf P} = \pmatrix{ {\bf Q} & {\bf R} \cr + {\bf 0} & {\bf I} }$$ +@end tex +@end iftex +@ifnottex +@example +@group + / Q | R \ +P = |---+---| + \ 0 | I / +@end group +@end example +@end ifnottex + +@noindent where we suppose that the first @math{t} states are transient +and the last @math{r} states are absorbing. + +The matrix @math{{\bf N} = ({\bf I} - {\bf Q})^{-1}} is called the +@emph{fundamental matrix}; @math{N(i,j)} represents the expected +number of times that the process is in the @math{j}-th transient state +if it is started in the @math{i}-th transient state. If we reshape +@math{\bf N} to the size of @math{\bf P} (filling missing entries with +zeros), we have that, for abrosbing chains @math{{\bf L} = {\bf +\pi}(0){\bf N}}. + +@DOCSTRING(dtmc_exps) + +@c +@node Time-averaged expected sojourn times (DTMC) +@subsection Time-averaged expected sojourn times + +@DOCSTRING(dtmc_taexps) + +@c @node First passage times (DTMC) @subsection First Passage Times
--- a/main/queueing/doc/queueing.html Sun Mar 18 15:21:33 2012 +0000 +++ b/main/queueing/doc/queueing.html Sun Mar 18 15:35:02 2012 +0000 @@ -58,8 +58,10 @@ <ul> <li><a href="#State-occupancy-probabilities-_0028DTMC_0029">4.1.1 State occupancy probabilities</a> <li><a href="#Birth_002ddeath-process-_0028DTMC_0029">4.1.2 Birth-death process</a> -<li><a href="#First-passage-times-_0028DTMC_0029">4.1.3 First Passage Times</a> -<li><a href="#Mean-time-to-absorption-_0028DTMC_0029">4.1.4 Mean Time to Absorption</a> +<li><a href="#Expected-number-of-visits-_0028DTMC_0029">4.1.3 Expected Number of Visits</a> +<li><a href="#Time_002daveraged-expected-sojourn-times-_0028DTMC_0029">4.1.4 Time-averaged expected sojourn times</a> +<li><a href="#First-passage-times-_0028DTMC_0029">4.1.5 First Passage Times</a> +<li><a href="#Mean-time-to-absorption-_0028DTMC_0029">4.1.6 Mean Time to Absorption</a> </li></ul> <li><a href="#Continuous_002dTime-Markov-Chains">4.2 Continuous-Time Markov Chains</a> <ul> @@ -107,6 +109,7 @@ <li><a href="#Utility-functions">6.6.3 Other utility functions</a> </li></ul> </li></ul> +<li><a name="toc_References" href="#References">7 References</a> <li><a name="toc_Contributing-Guidelines" href="#Contributing-Guidelines">Appendix A Contributing Guidelines</a> <li><a name="toc_Acknowledgements" href="#Acknowledgements">Appendix B Acknowledgements</a> <li><a name="toc_Copying" href="#Copying">Appendix C GNU GENERAL PUBLIC LICENSE</a> @@ -137,9 +140,10 @@ <li><a accesskey="4" href="#Markov-Chains">Markov Chains</a>: Functions for Markov Chains. <li><a accesskey="5" href="#Single-Station-Queueing-Systems">Single Station Queueing Systems</a>: Functions for single-station queueing systems. <li><a accesskey="6" href="#Queueing-Networks">Queueing Networks</a>: Functions for queueing networks. -<li><a accesskey="7" href="#Contributing-Guidelines">Contributing Guidelines</a>: How to contribute. -<li><a accesskey="8" href="#Acknowledgements">Acknowledgements</a>: People who contributed to the queueing toolbox. -<li><a accesskey="9" href="#Copying">Copying</a>: The GNU General Public License. +<li><a accesskey="7" href="#References">References</a>: References +<li><a accesskey="8" href="#Contributing-Guidelines">Contributing Guidelines</a>: How to contribute. +<li><a accesskey="9" href="#Acknowledgements">Acknowledgements</a>: People who contributed to the queueing toolbox. +<li><a href="#Copying">Copying</a>: The GNU General Public License. <li><a href="#Concept-Index">Concept Index</a>: An item for each concept. <li><a href="#Function-Index">Function Index</a>: An item for each function. <li><a href="#Author-Index">Author Index</a>: An item for each author. @@ -830,8 +834,10 @@ <ul class="menu"> <li><a accesskey="1" href="#State-occupancy-probabilities-_0028DTMC_0029">State occupancy probabilities (DTMC)</a> <li><a accesskey="2" href="#Birth_002ddeath-process-_0028DTMC_0029">Birth-death process (DTMC)</a> -<li><a accesskey="3" href="#First-passage-times-_0028DTMC_0029">First passage times (DTMC)</a> -<li><a accesskey="4" href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a> +<li><a accesskey="3" href="#Expected-number-of-visits-_0028DTMC_0029">Expected number of visits (DTMC)</a> +<li><a accesskey="4" href="#Time_002daveraged-expected-sojourn-times-_0028DTMC_0029">Time-averaged expected sojourn times (DTMC)</a> +<li><a accesskey="5" href="#First-passage-times-_0028DTMC_0029">First passage times (DTMC)</a> +<li><a accesskey="6" href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a> </ul> <div class="node"> @@ -931,7 +937,7 @@ <a name="Birth-death-process-(DTMC)"></a> <a name="Birth_002ddeath-process-_0028DTMC_0029"></a> <p><hr> -Next: <a rel="next" accesskey="n" href="#First-passage-times-_0028DTMC_0029">First passage times (DTMC)</a>, +Next: <a rel="next" accesskey="n" href="#Expected-number-of-visits-_0028DTMC_0029">Expected number of visits (DTMC)</a>, Previous: <a rel="previous" accesskey="p" href="#State-occupancy-probabilities-_0028DTMC_0029">State occupancy probabilities (DTMC)</a>, Up: <a rel="up" accesskey="u" href="#Discrete_002dTime-Markov-Chains">Discrete-Time Markov Chains</a> @@ -969,16 +975,156 @@ </blockquote></div> <div class="node"> +<a name="Expected-number-of-visits-(DTMC)"></a> +<a name="Expected-number-of-visits-_0028DTMC_0029"></a> +<p><hr> +Next: <a rel="next" accesskey="n" href="#Time_002daveraged-expected-sojourn-times-_0028DTMC_0029">Time-averaged expected sojourn times (DTMC)</a>, +Previous: <a rel="previous" accesskey="p" href="#Birth_002ddeath-process-_0028DTMC_0029">Birth-death process (DTMC)</a>, +Up: <a rel="up" accesskey="u" href="#Discrete_002dTime-Markov-Chains">Discrete-Time Markov Chains</a> + +</div> + +<h4 class="subsection">4.1.3 Expected Number of Visits</h4> + +<p>Given a N state discrete-time Markov chain with transition +matrix \bf P and an integer n ≥ 0, we let +L-I(n) be the the expected number of visits to state i +during the first n transitions. The vector \bf L(n) = +(L_1(n), L_2(n), <small class="dots">...</small>, L_N(n)) is defined as: + +<pre class="example"> n n + ___ ___ + \ \ i + L(n) = > pi(i) = > pi(0) P + /___ /___ + i=0 i=0 +</pre> + <p class="noindent">where \bf \pi(i) = \bf \pi(0)\bf P^i is the state occupancy probability +after i transitions. + + <p>If \bf P is absorbing, we can rearrange the states to rewrite +\bf P as: + +<pre class="example"> / Q | R \ + P = |---+---| + \ 0 | I / +</pre> + <p class="noindent">where we suppose that the first t states are transient +and the last r states are absorbing. + + <p>The matrix \bf N = (\bf I - \bf Q)^-1 is called the +<em>fundamental matrix</em>; N(i,j) represents the expected +number of times that the process is in the j-th transient state +if it is started in the i-th transient state. If we reshape +\bf N to the size of \bf P (filling missing entries with +zeros), we have that, for abrosbing chains \bf L = \bf +\pi(0)\bf N. + + <p><a name="doc_002ddtmc_005fexps"></a> + +<div class="defun"> +— Function File: <var>L</var> = <b>dtmc_exps</b> (<var>P, n, p0</var>)<var><a name="index-dtmc_005fexps-14"></a></var><br> +— Function File: <var>L</var> = <b>dtmc_exps</b> (<var>P, p0</var>)<var><a name="index-dtmc_005fexps-15"></a></var><br> +<blockquote> + <p><a name="index-Expected-sojourn-times-16"></a> +Compute the expected number of visits to each state during the first +<var>n</var> transitions, or until abrosption. + + <p><strong>INPUTS</strong> + + <dl> +<dt><var>P</var><dd>N \times N transition probability matrix. + + <br><dt><var>n</var><dd>Number of steps during which the expected number of visits are +computed (<var>n</var> ≥ 0). If <var>n</var><code>=0</code>, simply +returns <var>p0</var>. If <var>n</var><code> > 0</code>, returns the expected number +of visits after exactly <var>n</var> transitions. + + <br><dt><var>p0</var><dd>Initial state occupancy probability + + </dl> + + <p><strong>OUTPUTS</strong> + + <dl> +<dt><var>L</var><dd>When called with two arguments, <var>L</var><code>(i)</code> is the expected +number of visits to transient state i before absorption. When +called with three arguments, <var>L</var><code>(i)</code> is the expected number +of visits to state i during the first <var>n</var> transitions. + + </dl> + + <pre class="sp"> + + </pre> + <strong>See also:</strong> ctmc_exps. + + </blockquote></div> + +<div class="node"> +<a name="Time-averaged-expected-sojourn-times-(DTMC)"></a> +<a name="Time_002daveraged-expected-sojourn-times-_0028DTMC_0029"></a> +<p><hr> +Next: <a rel="next" accesskey="n" href="#First-passage-times-_0028DTMC_0029">First passage times (DTMC)</a>, +Previous: <a rel="previous" accesskey="p" href="#Expected-number-of-visits-_0028DTMC_0029">Expected number of visits (DTMC)</a>, +Up: <a rel="up" accesskey="u" href="#Discrete_002dTime-Markov-Chains">Discrete-Time Markov Chains</a> + +</div> + +<h4 class="subsection">4.1.4 Time-averaged expected sojourn times</h4> + +<p><a name="doc_002ddtmc_005ftaexps"></a> + +<div class="defun"> +— Function File: <var>L</var> = <b>dtmc_exps</b> (<var>P, n, p0</var>)<var><a name="index-dtmc_005fexps-17"></a></var><br> +— Function File: <var>L</var> = <b>dtmc_exps</b> (<var>P, p0</var>)<var><a name="index-dtmc_005fexps-18"></a></var><br> +<blockquote> + <p><a name="index-Time_002dalveraged-sojourn-time-19"></a> +Compute the <em>time-averaged sojourn time</em> <var>M</var><code>(i)</code>, +defined as the fraction of time steps {0, 1, <small class="dots">...</small>, n} (or +until absorption) spent in state i, assuming that the state +occupancy probabilities at time 0 are <var>p0</var>. + + <p><strong>INPUTS</strong> + + <dl> +<dt><var>Q</var><dd>Infinitesimal generator matrix. <var>Q</var><code>(i,j)</code> is the transition +rate from state i to state j, +1 ≤ i \neq j ≤ N. The +matrix <var>Q</var> must also satisfy the condition \sum_j=1^N Q_ij = 0 + + <br><dt><var>t</var><dd>Time. If omitted, the results are computed until absorption. + + <br><dt><var>p</var><dd><var>p</var><code>(i)</code> is the probability that, at time 0, the system was in +state i, for all i = 1, <small class="dots">...</small>, N + + </dl> + + <p><strong>OUTPUTS</strong> + + <dl> +<dt><var>M</var><dd>If this function is called with three arguments, <var>M</var><code>(i)</code> +is the expected fraction of the interval [0,t] spent in state +i assuming that the state occupancy probability at time zero +is <var>p</var>. If this function is called with two arguments, +<var>M</var><code>(i)</code> is the expected fraction of time until absorption +spent in state i. + + </dl> + + </blockquote></div> + +<div class="node"> <a name="First-passage-times-(DTMC)"></a> <a name="First-passage-times-_0028DTMC_0029"></a> <p><hr> Next: <a rel="next" accesskey="n" href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a>, -Previous: <a rel="previous" accesskey="p" href="#Birth_002ddeath-process-_0028DTMC_0029">Birth-death process (DTMC)</a>, +Previous: <a rel="previous" accesskey="p" href="#Time_002daveraged-expected-sojourn-times-_0028DTMC_0029">Time-averaged expected sojourn times (DTMC)</a>, Up: <a rel="up" accesskey="u" href="#Discrete_002dTime-Markov-Chains">Discrete-Time Markov Chains</a> </div> -<h4 class="subsection">4.1.3 First Passage Times</h4> +<h4 class="subsection">4.1.5 First Passage Times</h4> <p>The First Passage Time M_i j is defined as the average number of transitions needed to visit state j for the first @@ -994,14 +1140,11 @@ <p><a name="doc_002ddtmc_005ffpt"></a> <div class="defun"> -— Function File: <var>M</var> = <b>dtmc_fpt</b> (<var>P</var>)<var><a name="index-dtmc_005ffpt-14"></a></var><br> +— Function File: <var>M</var> = <b>dtmc_fpt</b> (<var>P</var>)<var><a name="index-dtmc_005ffpt-20"></a></var><br> <blockquote> - <p><a name="index-First-passage-times-15"></a><a name="index-Mean-recurrence-times-16"></a> -Compute the mean first passage times matrix \bf M, such that -<var>M</var><code>(i,j)</code> is the average number of transitions before state -<var>j</var> is reached, starting from state <var>i</var>, for all 1 \leq -i, j \leq N. Diagonal elements of <var>M</var> are the mean recurrence -times. + <p><a name="index-First-passage-times-21"></a><a name="index-Mean-recurrence-times-22"></a> +Compute mean first passage times and mean recurrence times +for an irreducible discrete-time Markov chain. <p><strong>INPUTS</strong> @@ -1017,14 +1160,19 @@ <p><strong>OUTPUTS</strong> <dl> -<dt><var>M</var><dd><var>M</var><code>(i,j)</code> is the average number of transitions before state -<var>j</var> is reached for the first time, starting from state <var>i</var>. -<var>M</var><code>(i,i)</code> is the <em>mean recurrence time</em> of state -i, and represents the average time needed to return to state -<var>i</var>. +<dt><var>M</var><dd>For all i \neq j, <var>M</var><code>(i,j)</code> is the average number of +transitions before state <var>j</var> is reached for the first time, +starting from state <var>i</var>. <var>M</var><code>(i,i)</code> is the <em>mean +recurrence time</em> of state i, and represents the average time +needed to return to state <var>i</var>. </dl> + <pre class="sp"> + + </pre> + <strong>See also:</strong> ctmc_fpt. + </blockquote></div> <div class="node"> @@ -1036,49 +1184,63 @@ </div> -<h4 class="subsection">4.1.4 Mean Time to Absorption</h4> +<h4 class="subsection">4.1.6 Mean Time to Absorption</h4> <p><a name="doc_002ddtmc_005fmtta"></a> <div class="defun"> -— Function File: [<var>t</var> <var>B</var>] = <b>dtmc_mtta</b> (<var>P</var>)<var><a name="index-dtmc_005fmtta-17"></a></var><br> -— Function File: [<var>t</var> <var>B</var>] = <b>dtmc_mtta</b> (<var>P, p0</var>)<var><a name="index-dtmc_005fmtta-18"></a></var><br> +— Function File: [<var>t</var> <var>N</var> <var>B</var>] = <b>dtmc_mtta</b> (<var>P</var>)<var><a name="index-dtmc_005fmtta-23"></a></var><br> +— Function File: [<var>t</var> <var>N</var> <var>B</var>] = <b>dtmc_mtta</b> (<var>P, p0</var>)<var><a name="index-dtmc_005fmtta-24"></a></var><br> <blockquote> - <p><a name="index-Markov-chain_002c-disctete-time-19"></a><a name="index-Mean-time-to-absorption-20"></a><a name="index-Absorption-probabilities-21"></a> -Compute the expected number of steps before absorption for the -DTMC with N \times N transition probability matrix <var>P</var>. + <p><a name="index-Mean-time-to-absorption-25"></a><a name="index-Absorption-probabilities-26"></a><a name="index-Fundamental-matrix-27"></a> +Compute the expected number of steps before absorption for a +DTMC with N \times N transition probability matrix <var>P</var>; +compute also the fundamental matrix <var>N</var> for <var>P</var>. <p><strong>INPUTS</strong> <dl> -<dt><var>P</var><dd>Transition probability matrix. - - <br><dt><var>p0</var><dd>Initial state occupancy probabilities. +<dt><var>P</var><dd>N \times N transition probability matrix. </dl> <p><strong>OUTPUTS</strong> <dl> -<dt><var>t</var><dd>When called with a single argument, <var>t</var> is a vector such that -<var>t</var><code>(i)</code> is the expected number of steps before being -absorbed, starting from state i. When called with two -arguments, <var>t</var> is a scalar and represents the average number of -steps before absorption, given initial state occupancy probabilities -<var>p0</var>. +<dt><var>t</var><dd>When called with a single argument, <var>t</var> is a vector of size +N such that <var>t</var><code>(i)</code> is the expected number of steps +before being absorbed in any absorbing state, starting from state +i; if i is absorbing, <var>t</var><code>(i) = 0</code>. When +called with two arguments, <var>t</var> is a scalar, and represents the +expected number of steps before absorption, starting from the initial +state occupancy probability <var>p0</var>. + + <br><dt><var>N</var><dd>When called with a single argument, <var>N</var> is the N \times N +fundamental matrix for <var>P</var>. <var>N</var><code>(i,j)</code> is the expected +number of visits to transient state <var>j</var> before absorption, if it +is started in transient state <var>i</var>. The initial state is counted +if i = j. When called with two arguments, <var>N</var> is a vector +of size N such that <var>N</var><code>(j)</code> is the expected number +of visits to transient state <var>j</var> before absorption, given initial +state occupancy probability <var>P0</var>. <br><dt><var>B</var><dd>When called with a single argument, <var>B</var> is a N \times N matrix where <var>B</var><code>(i,j)</code> is the probability of being absorbed in state j, starting from transient state i; if -j is not absorbing, <var>B</var><code>(i,j) = 0</code>; if i is -absorbing, then <var>B</var><code>(i,i) = 1</code>. -When called with two arguments, <var>B</var> is a -vector with N elements where <var>B</var><code>(j)</code> is the -probability of being absorbed in state <var>j</var>, given initial state -occupancy probabilities <var>p0</var>. +j is not absorbing, <var>B</var><code>(i,j) = 0</code>; if i +is absorbing, <var>B</var><code>(i,i) = 1</code> and +<var>B</var><code>(i,j) = 0</code> for all j \neq j. When called with +two arguments, <var>B</var> is a vector of size N where +<var>B</var><code>(j)</code> is the probability of being absorbed in state +<var>j</var>, given initial state occupancy probabilities <var>p0</var>. </dl> + <pre class="sp"> + + </pre> + <strong>See also:</strong> ctmc_mtta. + </blockquote></div> <div class="node"> @@ -1109,9 +1271,9 @@ <p><a name="doc_002dctmc_005fcheck_005fQ"></a> <div class="defun"> -— Function File: [<var>result</var> <var>err</var>] = <b>ctmc_check_Q</b> (<var>Q</var>)<var><a name="index-ctmc_005fcheck_005fQ-22"></a></var><br> +— Function File: [<var>result</var> <var>err</var>] = <b>ctmc_check_Q</b> (<var>Q</var>)<var><a name="index-ctmc_005fcheck_005fQ-28"></a></var><br> <blockquote> - <p><a name="index-Markov-chain_002c-continuous-time-23"></a> + <p><a name="index-Markov-chain_002c-continuous-time-29"></a> If <var>Q</var> is a valid infinitesimal generator matrix, return the size (number of rows or columns) of <var>Q</var>. If <var>Q</var> is not an infinitesimal generator matrix, set <var>result</var> to zero, and @@ -1162,10 +1324,10 @@ <p><a name="doc_002dctmc"></a> <div class="defun"> -— Function File: <var>p</var> = <b>ctmc</b> (<var>Q</var>)<var><a name="index-ctmc-24"></a></var><br> -— Function File: <var>p</var> = <b>ctmc</b> (<var>Q, t. p0</var>)<var><a name="index-ctmc-25"></a></var><br> +— Function File: <var>p</var> = <b>ctmc</b> (<var>Q</var>)<var><a name="index-ctmc-30"></a></var><br> +— Function File: <var>p</var> = <b>ctmc</b> (<var>Q, t. p0</var>)<var><a name="index-ctmc-31"></a></var><br> <blockquote> - <p><a name="index-Markov-chain_002c-continuous-time-26"></a><a name="index-Continuous-time-Markov-chain-27"></a><a name="index-Markov-chain_002c-state-occupancy-probabilities-28"></a><a name="index-Stationary-probabilities-29"></a> + <p><a name="index-Markov-chain_002c-continuous-time-32"></a><a name="index-Continuous-time-Markov-chain-33"></a><a name="index-Markov-chain_002c-state-occupancy-probabilities-34"></a><a name="index-Stationary-probabilities-35"></a> With a single argument, compute the stationary state occupancy probability vector <var>p</var>(1), <small class="dots">...</small>, <var>p</var>(N) for a Continuous-Time Markov Chain with infinitesimal generator matrix @@ -1228,9 +1390,9 @@ <p><a name="doc_002dctmc_005fbd"></a> <div class="defun"> -— Function File: <var>Q</var> = <b>ctmc_bd</b> (<var>birth, death</var>)<var><a name="index-ctmc_005fbd-30"></a></var><br> +— Function File: <var>Q</var> = <b>ctmc_bd</b> (<var>birth, death</var>)<var><a name="index-ctmc_005fbd-36"></a></var><br> <blockquote> - <p><a name="index-Markov-chain_002c-continuous-time-31"></a><a name="index-Birth_002ddeath-process-32"></a> + <p><a name="index-Markov-chain_002c-continuous-time-37"></a><a name="index-Birth_002ddeath-process-38"></a> Returns the N \times N infinitesimal generator matrix Q for a birth-death process with given rates. @@ -1291,10 +1453,10 @@ <p><a name="doc_002dctmc_005fexps"></a> <div class="defun"> -— Function File: <var>L</var> = <b>ctmc_exps</b> (<var>Q, t, p </var>)<var><a name="index-ctmc_005fexps-33"></a></var><br> -— Function File: <var>L</var> = <b>ctmc_exps</b> (<var>Q, p</var>)<var><a name="index-ctmc_005fexps-34"></a></var><br> +— Function File: <var>L</var> = <b>ctmc_exps</b> (<var>Q, t, p </var>)<var><a name="index-ctmc_005fexps-39"></a></var><br> +— Function File: <var>L</var> = <b>ctmc_exps</b> (<var>Q, p</var>)<var><a name="index-ctmc_005fexps-40"></a></var><br> <blockquote> - <p><a name="index-Markov-chain_002c-continuous-time-35"></a><a name="index-Expected-sojourn-time-36"></a> + <p><a name="index-Markov-chain_002c-continuous-time-41"></a><a name="index-Expected-sojourn-time-42"></a> With three arguments, compute the expected times <var>L</var><code>(i)</code> spent in each state i during the time interval [0,t], assuming that the state occupancy probabilities @@ -1374,10 +1536,10 @@ <p><a name="doc_002dctmc_005ftaexps"></a> <div class="defun"> -— Function File: <var>M</var> = <b>ctmc_taexps</b> (<var>Q, t, p</var>)<var><a name="index-ctmc_005ftaexps-37"></a></var><br> -— Function File: <var>M</var> = <b>ctmc_taexps</b> (<var>Q, p</var>)<var><a name="index-ctmc_005ftaexps-38"></a></var><br> +— Function File: <var>M</var> = <b>ctmc_taexps</b> (<var>Q, t, p</var>)<var><a name="index-ctmc_005ftaexps-43"></a></var><br> +— Function File: <var>M</var> = <b>ctmc_taexps</b> (<var>Q, p</var>)<var><a name="index-ctmc_005ftaexps-44"></a></var><br> <blockquote> - <p><a name="index-Markov-chain_002c-continuous-time-39"></a><a name="index-Time_002dalveraged-sojourn-time-40"></a> + <p><a name="index-Markov-chain_002c-continuous-time-45"></a><a name="index-Time_002dalveraged-sojourn-time-46"></a> Compute the <em>time-averaged sojourn time</em> <var>M</var><code>(i)</code>, defined as the fraction of the time interval [0,t] (or until absorption) spent in state i, assuming that the state @@ -1464,9 +1626,9 @@ <p><a name="doc_002dctmc_005fmtta"></a> <div class="defun"> -— Function File: <var>t</var> = <b>ctmc_mtta</b> (<var>Q, p</var>)<var><a name="index-ctmc_005fmtta-41"></a></var><br> +— Function File: <var>t</var> = <b>ctmc_mtta</b> (<var>Q, p</var>)<var><a name="index-ctmc_005fmtta-47"></a></var><br> <blockquote> - <p><a name="index-Markov-chain_002c-continuous-time-42"></a><a name="index-Mean-time-to-absorption-43"></a> + <p><a name="index-Markov-chain_002c-continuous-time-48"></a><a name="index-Mean-time-to-absorption-49"></a> Compute the Mean-Time to Absorption (MTTA) of the CTMC described by the infinitesimal generator matrix <var>Q</var>, starting from initial occupancy probabilities <var>p</var>. If there are no absorbing states, this @@ -1493,6 +1655,11 @@ </dl> + <pre class="sp"> + + </pre> + <strong>See also:</strong> dtmc_mtta. + </blockquote></div> <p class="noindent"><strong>EXAMPLE</strong> @@ -1516,9 +1683,9 @@ <pre class="example"><pre class="verbatim"> mu = 0.01; death = [ 3 4 5 ] * mu; - Q = diag(death,-1); - Q -= diag(sum(Q,2)); - [t L] = ctmc_mtta(Q,[0 0 0 1])</pre> ⇒ t = 78.333 + birth = 0*death; + Q = ctmc_bd(birth,death); + t = ctmc_mtta(Q,[0 0 0 1])</pre> ⇒ t = 78.333 </pre> <p class="noindent"><strong>REFERENCES</strong> @@ -1527,7 +1694,7 @@ Performance Evaluation with Computer Science Applications</cite>, Wiley, 1998. - <p><a name="index-Bolch_002c-G_002e-44"></a><a name="index-Greiner_002c-S_002e-45"></a><a name="index-de-Meer_002c-H_002e-46"></a><a name="index-Trivedi_002c-K_002e-47"></a> + <p><a name="index-Bolch_002c-G_002e-50"></a><a name="index-Greiner_002c-S_002e-51"></a><a name="index-de-Meer_002c-H_002e-52"></a><a name="index-Trivedi_002c-K_002e-53"></a> <div class="node"> <a name="First-passage-times-(CTMC)"></a> <a name="First-passage-times-_0028CTMC_0029"></a> @@ -1542,15 +1709,12 @@ <p><a name="doc_002dctmc_005ffpt"></a> <div class="defun"> -— Function File: <var>M</var> = <b>ctmc_fpt</b> (<var>Q</var>)<var><a name="index-ctmc_005ffpt-48"></a></var><br> -— Function File: <var>m</var> = <b>ctmc_fpt</b> (<var>Q, i, j</var>)<var><a name="index-ctmc_005ffpt-49"></a></var><br> +— Function File: <var>M</var> = <b>ctmc_fpt</b> (<var>Q</var>)<var><a name="index-ctmc_005ffpt-54"></a></var><br> +— Function File: <var>m</var> = <b>ctmc_fpt</b> (<var>Q, i, j</var>)<var><a name="index-ctmc_005ffpt-55"></a></var><br> <blockquote> - <p><a name="index-Markov-chain_002c-continuous-time-50"></a><a name="index-First-passage-times-51"></a> -If called with a single argument, computes the mean first passage -times <var>M</var><code>(i,j)</code>, the average times before state <var>j</var> is -reached, starting from state <var>i</var>, for all 1 \leq i, j \leq -N. If called with three arguments, returns the single value -<var>m</var><code> = </code><var>M</var><code>(i,j)</code>. + <p><a name="index-First-passage-times-56"></a> +Compute mean first passage times for an irreducible continuous-time +Markov chain. <p><strong>INPUTS</strong> @@ -1562,24 +1726,27 @@ <br><dt><var>i</var><dd>Initial state. - <br><dt><var>j</var><dd>Destination state. If <var>j</var> is a vector, returns the mean first passage -time to any state in <var>j</var>. + <br><dt><var>j</var><dd>Destination state. </dl> <p><strong>OUTPUTS</strong> <dl> -<dt><var>M</var><dd>If this function is called with a single argument, the result -<var>M</var><code>(i,j)</code> is the average time before state -<var>j</var> is visited for the first time, starting from state <var>i</var>. - - <br><dt><var>m</var><dd>If this function is called with three arguments, the result -<var>m</var> is the average time before state <var>j</var> is visited for the first +<dt><var>M</var><dd><var>M</var><code>(i,j)</code> is the average time before state +<var>j</var> is visited for the first time, starting from state <var>i</var>. +We set <var>M</var><code>(i,i) = 0</code>. + + <br><dt><var>m</var><dd><var>m</var> is the average time before state <var>j</var> is visited for the first time, starting from state <var>i</var>. </dl> + <pre class="sp"> + + </pre> + <strong>See also:</strong> dtmc_fpt. + </blockquote></div> <!-- DO NOT EDIT! Generated automatically by munge-texi. --> @@ -1651,9 +1818,9 @@ <p><a name="doc_002dqnmm1"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>] = <b>qnmm1</b> (<var>lambda, mu</var>)<var><a name="index-qnmm1-52"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>] = <b>qnmm1</b> (<var>lambda, mu</var>)<var><a name="index-qnmm1-57"></a></var><br> <blockquote> - <p><a name="index-g_t_0040math_007bM_002fM_002f1_007d-system-53"></a> + <p><a name="index-g_t_0040math_007bM_002fM_002f1_007d-system-58"></a> Compute utilization, response time, average number of requests and throughput for a M/M/1 queue. @@ -1698,7 +1865,7 @@ and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications</cite>, Wiley, 1998, Section 6.3. - <p><a name="index-Bolch_002c-G_002e-54"></a><a name="index-Greiner_002c-S_002e-55"></a><a name="index-de-Meer_002c-H_002e-56"></a><a name="index-Trivedi_002c-K_002e-57"></a> + <p><a name="index-Bolch_002c-G_002e-59"></a><a name="index-Greiner_002c-S_002e-60"></a><a name="index-de-Meer_002c-H_002e-61"></a><a name="index-Trivedi_002c-K_002e-62"></a> <!-- M/M/m --> <div class="node"> <a name="The-M%2fM%2fm-System"></a> @@ -1724,10 +1891,10 @@ <p><a name="doc_002dqnmmm"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>, <var>pm</var>] = <b>qnmmm</b> (<var>lambda, mu</var>)<var><a name="index-qnmmm-58"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>, <var>pm</var>] = <b>qnmmm</b> (<var>lambda, mu, m</var>)<var><a name="index-qnmmm-59"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>, <var>pm</var>] = <b>qnmmm</b> (<var>lambda, mu</var>)<var><a name="index-qnmmm-63"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>, <var>pm</var>] = <b>qnmmm</b> (<var>lambda, mu, m</var>)<var><a name="index-qnmmm-64"></a></var><br> <blockquote> - <p><a name="index-g_t_0040math_007bM_002fM_002fm_007d-system-60"></a> + <p><a name="index-g_t_0040math_007bM_002fM_002fm_007d-system-65"></a> Compute utilization, response time, average number of requests in service and throughput for a M/M/m queue, a queueing system with m identical service centers connected to a single queue. @@ -1779,7 +1946,7 @@ and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications</cite>, Wiley, 1998, Section 6.5. - <p><a name="index-Bolch_002c-G_002e-61"></a><a name="index-Greiner_002c-S_002e-62"></a><a name="index-de-Meer_002c-H_002e-63"></a><a name="index-Trivedi_002c-K_002e-64"></a> + <p><a name="index-Bolch_002c-G_002e-66"></a><a name="index-Greiner_002c-S_002e-67"></a><a name="index-de-Meer_002c-H_002e-68"></a><a name="index-Trivedi_002c-K_002e-69"></a> <!-- M/M/inf --> <div class="node"> <a name="The-M%2fM%2finf-System"></a> @@ -1802,7 +1969,7 @@ <p><a name="doc_002dqnmminf"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>] = <b>qnmminf</b> (<var>lambda, mu</var>)<var><a name="index-qnmminf-65"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>] = <b>qnmminf</b> (<var>lambda, mu</var>)<var><a name="index-qnmminf-70"></a></var><br> <blockquote> <p>Compute utilization, response time, average number of requests and throughput for a M/M/\infty queue. This is a system with an @@ -1810,7 +1977,7 @@ system is always stable, regardless the values of the arrival and service rates. - <p><a name="index-g_t_0040math_007bM_002fM_002f_007dinf-system-66"></a> + <p><a name="index-g_t_0040math_007bM_002fM_002f_007dinf-system-71"></a> <p><strong>INPUTS</strong> @@ -1828,7 +1995,7 @@ different from the utilization, which in the case of M/M/\infty centers is always zero. - <p><a name="index-traffic-intensity-67"></a> + <p><a name="index-traffic-intensity-72"></a> <br><dt><var>R</var><dd>Service center response time. <br><dt><var>Q</var><dd>Average number of requests in the system (which is equal to the @@ -1856,7 +2023,7 @@ and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications</cite>, Wiley, 1998, Section 6.4. - <p><a name="index-Bolch_002c-G_002e-68"></a><a name="index-Greiner_002c-S_002e-69"></a><a name="index-de-Meer_002c-H_002e-70"></a><a name="index-Trivedi_002c-K_002e-71"></a> + <p><a name="index-Bolch_002c-G_002e-73"></a><a name="index-Greiner_002c-S_002e-74"></a><a name="index-de-Meer_002c-H_002e-75"></a><a name="index-Trivedi_002c-K_002e-76"></a> <!-- M/M/1/k --> <div class="node"> <a name="The-M%2fM%2f1%2fK-System"></a> @@ -1880,9 +2047,9 @@ <p><a name="doc_002dqnmm1k"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>, <var>pK</var>] = <b>qnmm1k</b> (<var>lambda, mu, K</var>)<var><a name="index-qnmm1k-72"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>, <var>pK</var>] = <b>qnmm1k</b> (<var>lambda, mu, K</var>)<var><a name="index-qnmm1k-77"></a></var><br> <blockquote> - <p><a name="index-g_t_0040math_007bM_002fM_002f1_002fK_007d-system-73"></a> + <p><a name="index-g_t_0040math_007bM_002fM_002f1_002fK_007d-system-78"></a> Compute utilization, response time, average number of requests and throughput for a M/M/1/K finite capacity system. In a M/M/1/K queue there is a single server; the maximum number of @@ -1949,9 +2116,9 @@ <p><a name="doc_002dqnmmmk"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>, <var>pK</var>] = <b>qnmmmk</b> (<var>lambda, mu, m, K</var>)<var><a name="index-qnmmmk-74"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>, <var>pK</var>] = <b>qnmmmk</b> (<var>lambda, mu, m, K</var>)<var><a name="index-qnmmmk-79"></a></var><br> <blockquote> - <p><a name="index-g_t_0040math_007bM_002fM_002fm_002fK_007d-system-75"></a> + <p><a name="index-g_t_0040math_007bM_002fM_002fm_002fK_007d-system-80"></a> Compute utilization, response time, average number of requests and throughput for a M/M/m/K finite capacity system. In a M/M/m/K system there are m \geq 1 identical service @@ -2009,7 +2176,7 @@ and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications</cite>, Wiley, 1998, Section 6.6. - <p><a name="index-Bolch_002c-G_002e-76"></a><a name="index-Greiner_002c-S_002e-77"></a><a name="index-de-Meer_002c-H_002e-78"></a><a name="index-Trivedi_002c-K_002e-79"></a> + <p><a name="index-Bolch_002c-G_002e-81"></a><a name="index-Greiner_002c-S_002e-82"></a><a name="index-de-Meer_002c-H_002e-83"></a><a name="index-Trivedi_002c-K_002e-84"></a> <!-- Approximate M/M/m --> <div class="node"> @@ -2031,9 +2198,9 @@ <p><a name="doc_002dqnammm"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnammm</b> (<var>lambda, mu</var>)<var><a name="index-qnammm-80"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnammm</b> (<var>lambda, mu</var>)<var><a name="index-qnammm-85"></a></var><br> <blockquote> - <p><a name="index-Asymmetric-_0040math_007bM_002fM_002fm_007d-system-81"></a> + <p><a name="index-Asymmetric-_0040math_007bM_002fM_002fm_007d-system-86"></a> Compute <em>approximate</em> utilization, response time, average number of requests in service and throughput for an asymmetric M/M/m queue. In this system there are m different service centers @@ -2080,7 +2247,7 @@ and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications</cite>, Wiley, 1998 - <p><a name="index-Bolch_002c-G_002e-82"></a><a name="index-Greiner_002c-S_002e-83"></a><a name="index-de-Meer_002c-H_002e-84"></a><a name="index-Trivedi_002c-K_002e-85"></a> + <p><a name="index-Bolch_002c-G_002e-87"></a><a name="index-Greiner_002c-S_002e-88"></a><a name="index-de-Meer_002c-H_002e-89"></a><a name="index-Trivedi_002c-K_002e-90"></a> <div class="node"> <a name="The-M%2fG%2f1-System"></a> <a name="The-M_002fG_002f1-System"></a> @@ -2096,9 +2263,9 @@ <p><a name="doc_002dqnmg1"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>] = <b>qnmg1</b> (<var>lambda, xavg, x2nd</var>)<var><a name="index-qnmg1-86"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>] = <b>qnmg1</b> (<var>lambda, xavg, x2nd</var>)<var><a name="index-qnmg1-91"></a></var><br> <blockquote> - <p><a name="index-g_t_0040math_007bM_002fG_002f1_007d-system-87"></a> + <p><a name="index-g_t_0040math_007bM_002fG_002f1_007d-system-92"></a> Compute utilization, response time, average number of requests and throughput for a M/G/1 system. The service time distribution is described by its mean <var>xavg</var>, and by its second moment @@ -2155,9 +2322,9 @@ <p><a name="doc_002dqnmh1"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>] = <b>qnmh1</b> (<var>lambda, mu, alpha</var>)<var><a name="index-qnmh1-88"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>] = <b>qnmh1</b> (<var>lambda, mu, alpha</var>)<var><a name="index-qnmh1-93"></a></var><br> <blockquote> - <p><a name="index-g_t_0040math_007bM_002fH_005fm_002f1_007d-system-89"></a> + <p><a name="index-g_t_0040math_007bM_002fH_005fm_002f1_007d-system-94"></a> Compute utilization, response time, average number of requests and throughput for a M/H_m/1 system. In this system, the customer service times have hyper-exponential distribution: @@ -2222,7 +2389,7 @@ <div class="node"> <a name="Queueing-Networks"></a> <p><hr> -Next: <a rel="next" accesskey="n" href="#Contributing-Guidelines">Contributing Guidelines</a>, +Next: <a rel="next" accesskey="n" href="#References">References</a>, Previous: <a rel="previous" accesskey="p" href="#Single-Station-Queueing-Systems">Single Station Queueing Systems</a>, Up: <a rel="up" accesskey="u" href="#Top">Top</a> @@ -2239,7 +2406,7 @@ <li><a accesskey="6" href="#Utility-functions">Utility functions</a>: Utility functions to compute miscellaneous quantities </ul> -<p><a name="index-queueing-networks-90"></a> +<p><a name="index-queueing-networks-95"></a> <!-- INTRODUCTION --> <div class="node"> <a name="Introduction-to-QNs"></a> @@ -2500,13 +2667,13 @@ <p><a name="doc_002dqnmknode"></a> <div class="defun"> -— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"m/m/m-fcfs", S</var>)<var><a name="index-qnmknode-91"></a></var><br> -— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"m/m/m-fcfs", S, m</var>)<var><a name="index-qnmknode-92"></a></var><br> -— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"m/m/1-lcfs-pr", S</var>)<var><a name="index-qnmknode-93"></a></var><br> -— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"-/g/1-ps", S</var>)<var><a name="index-qnmknode-94"></a></var><br> -— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"-/g/1-ps", S, s2</var>)<var><a name="index-qnmknode-95"></a></var><br> -— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"-/g/inf", S</var>)<var><a name="index-qnmknode-96"></a></var><br> -— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"-/g/inf", S, s2</var>)<var><a name="index-qnmknode-97"></a></var><br> +— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"m/m/m-fcfs", S</var>)<var><a name="index-qnmknode-96"></a></var><br> +— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"m/m/m-fcfs", S, m</var>)<var><a name="index-qnmknode-97"></a></var><br> +— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"m/m/1-lcfs-pr", S</var>)<var><a name="index-qnmknode-98"></a></var><br> +— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"-/g/1-ps", S</var>)<var><a name="index-qnmknode-99"></a></var><br> +— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"-/g/1-ps", S, s2</var>)<var><a name="index-qnmknode-100"></a></var><br> +— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"-/g/inf", S</var>)<var><a name="index-qnmknode-101"></a></var><br> +— Function File: <var>Q</var> = <b>qnmknode</b> (<var>"-/g/inf", S, s2</var>)<var><a name="index-qnmknode-102"></a></var><br> <blockquote> <p>Creates a node; this function can be used together with <code>qnsolve</code>. It is possible to create either single-class nodes @@ -2575,10 +2742,10 @@ <p><a name="doc_002dqnsolve"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"closed", N, QQ, V</var>)<var><a name="index-qnsolve-98"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"closed", N, QQ, V, Z</var>)<var><a name="index-qnsolve-99"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"open", lambda, QQ, V</var>)<var><a name="index-qnsolve-100"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"mixed", lambda, N, QQ, V</var>)<var><a name="index-qnsolve-101"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"closed", N, QQ, V</var>)<var><a name="index-qnsolve-103"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"closed", N, QQ, V, Z</var>)<var><a name="index-qnsolve-104"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"open", lambda, QQ, V</var>)<var><a name="index-qnsolve-105"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"mixed", lambda, N, QQ, V</var>)<var><a name="index-qnsolve-106"></a></var><br> <blockquote> <p>General evaluator of QN models. Networks can be open, closed or mixed; single as well as multiclass networks are supported. @@ -2756,11 +2923,11 @@ <p><a name="doc_002dqnjackson"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnjackson</b> (<var>lambda, S, P </var>)<var><a name="index-qnjackson-102"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnjackson</b> (<var>lambda, S, P, m </var>)<var><a name="index-qnjackson-103"></a></var><br> -— Function File: <var>pr</var> = <b>qnjackson</b> (<var>lambda, S, P, m, k</var>)<var><a name="index-qnjackson-104"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnjackson</b> (<var>lambda, S, P </var>)<var><a name="index-qnjackson-107"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnjackson</b> (<var>lambda, S, P, m </var>)<var><a name="index-qnjackson-108"></a></var><br> +— Function File: <var>pr</var> = <b>qnjackson</b> (<var>lambda, S, P, m, k</var>)<var><a name="index-qnjackson-109"></a></var><br> <blockquote> - <p><a name="index-open-network_002c-single-class-105"></a><a name="index-Jackson-network-106"></a> + <p><a name="index-open-network_002c-single-class-110"></a><a name="index-Jackson-network-111"></a> With three or four input parameters, this function computes the steady-state occupancy probabilities for a Jackson network. With five input parameters, this function computes the steady-state probability @@ -2842,7 +3009,7 @@ Performance Evaluation with Computer Science Applications</cite>, Wiley, 1998, pp. 284–287. - <p><a name="index-Bolch_002c-G_002e-107"></a><a name="index-Greiner_002c-S_002e-108"></a><a name="index-de-Meer_002c-H_002e-109"></a><a name="index-Trivedi_002c-K_002e-110"></a> + <p><a name="index-Bolch_002c-G_002e-112"></a><a name="index-Greiner_002c-S_002e-113"></a><a name="index-de-Meer_002c-H_002e-114"></a><a name="index-Trivedi_002c-K_002e-115"></a> <h4 class="subsection">6.3.2 The Convolution Algorithm</h4> @@ -2876,10 +3043,10 @@ <p><a name="doc_002dqnconvolution"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnconvolution</b> (<var>N, S, V</var>)<var><a name="index-qnconvolution-111"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnconvolution</b> (<var>N, S, V, m</var>)<var><a name="index-qnconvolution-112"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnconvolution</b> (<var>N, S, V</var>)<var><a name="index-qnconvolution-116"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnconvolution</b> (<var>N, S, V, m</var>)<var><a name="index-qnconvolution-117"></a></var><br> <blockquote> - <p><a name="index-closed-network-113"></a><a name="index-normalization-constant-114"></a><a name="index-convolution-algorithm-115"></a> + <p><a name="index-closed-network-118"></a><a name="index-normalization-constant-119"></a><a name="index-convolution-algorithm-120"></a> This function implements the <em>convolution algorithm</em> for computing steady-state performance measures of product-form, single-class closed queueing networks. Load-independent service @@ -2970,20 +3137,20 @@ 16, number 9, september 1973, pp. 527–531. <a href="http://doi.acm.org/10.1145/362342.362345">http://doi.acm.org/10.1145/362342.362345</a> - <p><a name="index-Buzen_002c-J_002e-P_002e-116"></a> + <p><a name="index-Buzen_002c-J_002e-P_002e-121"></a> This implementation is based on G. Bolch, S. Greiner, H. de Meer and K. Trivedi, <cite>Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications</cite>, Wiley, 1998, pp. 313–317. - <p><a name="index-Bolch_002c-G_002e-117"></a><a name="index-Greiner_002c-S_002e-118"></a><a name="index-de-Meer_002c-H_002e-119"></a><a name="index-Trivedi_002c-K_002e-120"></a> + <p><a name="index-Bolch_002c-G_002e-122"></a><a name="index-Greiner_002c-S_002e-123"></a><a name="index-de-Meer_002c-H_002e-124"></a><a name="index-Trivedi_002c-K_002e-125"></a> <!-- Convolution for load-dependent service centers --> <a name="doc_002dqnconvolutionld"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnconvolutionld</b> (<var>N, S, V</var>)<var><a name="index-qnconvolutionld-121"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnconvolutionld</b> (<var>N, S, V</var>)<var><a name="index-qnconvolutionld-126"></a></var><br> <blockquote> - <p><a name="index-closed-network-122"></a><a name="index-normalization-constant-123"></a><a name="index-convolution-algorithm-124"></a><a name="index-load_002ddependent-service-center-125"></a> + <p><a name="index-closed-network-127"></a><a name="index-normalization-constant-128"></a><a name="index-convolution-algorithm-129"></a><a name="index-load_002ddependent-service-center-130"></a> This function implements the <em>convolution algorithm</em> for product-form, single-class closed queueing networks with general load-dependent service centers. @@ -3043,7 +3210,7 @@ Purdue University, feb, 1981 (revised). <a href="http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-354.pdf">http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-354.pdf</a> - <p><a name="index-Schwetman_002c-H_002e-126"></a> + <p><a name="index-Schwetman_002c-H_002e-131"></a> M. Reiser, H. Kobayashi, <cite>On The Convolution Algorithm for Separable Queueing Networks</cite>, In Proceedings of the 1976 ACM SIGMETRICS Conference on Computer Performance Modeling Measurement and @@ -3051,7 +3218,7 @@ 1976). SIGMETRICS '76. ACM, New York, NY, pp. 109–117. <a href="http://doi.acm.org/10.1145/800200.806187">http://doi.acm.org/10.1145/800200.806187</a> - <p><a name="index-Reiser_002c-M_002e-127"></a><a name="index-Kobayashi_002c-H_002e-128"></a> + <p><a name="index-Reiser_002c-M_002e-132"></a><a name="index-Kobayashi_002c-H_002e-133"></a> This implementation is based on G. Bolch, S. Greiner, H. de Meer and K. Trivedi, <cite>Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications</cite>, Wiley, @@ -3063,7 +3230,7 @@ function f_i defined in Schwetman, <code>Some Computational Aspects of Queueing Network Models</code>. - <p><a name="index-Bolch_002c-G_002e-129"></a><a name="index-Greiner_002c-S_002e-130"></a><a name="index-de-Meer_002c-H_002e-131"></a><a name="index-Trivedi_002c-K_002e-132"></a> + <p><a name="index-Bolch_002c-G_002e-134"></a><a name="index-Greiner_002c-S_002e-135"></a><a name="index-de-Meer_002c-H_002e-136"></a><a name="index-Trivedi_002c-K_002e-137"></a> <h4 class="subsection">6.3.3 Open networks</h4> @@ -3071,10 +3238,10 @@ <p><a name="doc_002dqnopensingle"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopensingle</b> (<var>lambda, S, V</var>)<var><a name="index-qnopensingle-133"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopensingle</b> (<var>lambda, S, V, m</var>)<var><a name="index-qnopensingle-134"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopensingle</b> (<var>lambda, S, V</var>)<var><a name="index-qnopensingle-138"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopensingle</b> (<var>lambda, S, V, m</var>)<var><a name="index-qnopensingle-139"></a></var><br> <blockquote> - <p><a name="index-open-network_002c-single-class-135"></a><a name="index-BCMP-network-136"></a> + <p><a name="index-open-network_002c-single-class-140"></a><a name="index-BCMP-network-141"></a> Analyze open, single class BCMP queueing networks. <p>This function works for a subset of BCMP single-class open networks @@ -3167,16 +3334,16 @@ Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications</cite>, Wiley, 1998. - <p><a name="index-Bolch_002c-G_002e-137"></a><a name="index-Greiner_002c-S_002e-138"></a><a name="index-de-Meer_002c-H_002e-139"></a><a name="index-Trivedi_002c-K_002e-140"></a> + <p><a name="index-Bolch_002c-G_002e-142"></a><a name="index-Greiner_002c-S_002e-143"></a><a name="index-de-Meer_002c-H_002e-144"></a><a name="index-Trivedi_002c-K_002e-145"></a> <!-- Open network with multiple classes --> <p><a name="doc_002dqnopenmulti"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopenmulti</b> (<var>lambda, S, V</var>)<var><a name="index-qnopenmulti-141"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopenmulti</b> (<var>lambda, S, V, m</var>)<var><a name="index-qnopenmulti-142"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopenmulti</b> (<var>lambda, S, V</var>)<var><a name="index-qnopenmulti-146"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopenmulti</b> (<var>lambda, S, V, m</var>)<var><a name="index-qnopenmulti-147"></a></var><br> <blockquote> - <p><a name="index-open-network_002c-multiple-classes-143"></a> + <p><a name="index-open-network_002c-multiple-classes-148"></a> Exact analysis of open, multiple-class BCMP networks. The network can be made of <em>single-server</em> queueing centers (FCFS, LCFS-PR or PS) or delay centers (IS). This function assumes a network with @@ -3241,7 +3408,7 @@ 1984. <a href="http://www.cs.washington.edu/homes/lazowska/qsp/">http://www.cs.washington.edu/homes/lazowska/qsp/</a>. In particular, see section 7.4.1 ("Open Model Solution Techniques"). - <p><a name="index-Lazowska_002c-E_002e-D_002e-144"></a><a name="index-Zahorjan_002c-J_002e-145"></a><a name="index-Graham_002c-G_002e-S_002e-146"></a><a name="index-Sevcik_002c-K_002e-C_002e-147"></a> + <p><a name="index-Lazowska_002c-E_002e-D_002e-149"></a><a name="index-Zahorjan_002c-J_002e-150"></a><a name="index-Graham_002c-G_002e-S_002e-151"></a><a name="index-Sevcik_002c-K_002e-C_002e-152"></a> <h4 class="subsection">6.3.4 Closed Networks</h4> @@ -3249,11 +3416,11 @@ <p><a name="doc_002dqnclosedsinglemva"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnclosedsinglemva</b> (<var>N, S, V</var>)<var><a name="index-qnclosedsinglemva-148"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnclosedsinglemva</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedsinglemva-149"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnclosedsinglemva</b> (<var>N, S, V, m, Z</var>)<var><a name="index-qnclosedsinglemva-150"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnclosedsinglemva</b> (<var>N, S, V</var>)<var><a name="index-qnclosedsinglemva-153"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnclosedsinglemva</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedsinglemva-154"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnclosedsinglemva</b> (<var>N, S, V, m, Z</var>)<var><a name="index-qnclosedsinglemva-155"></a></var><br> <blockquote> - <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-151"></a><a name="index-closed-network_002c-single-class-152"></a><a name="index-normalization-constant-153"></a> + <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-156"></a><a name="index-closed-network_002c-single-class-157"></a><a name="index-normalization-constant-158"></a> Analyze closed, single class queueing networks using the exact Mean Value Analysis (MVA) algorithm. The following queueing disciplines are supported: FCFS, LCFS-PR, PS and IS (Infinite Server). This @@ -3354,7 +3521,7 @@ Multichain Queuing Networks</cite>, Journal of the ACM, vol. 27, n. 2, April 1980, pp. 313–322. <a href="http://doi.acm.org/10.1145/322186.322195">http://doi.acm.org/10.1145/322186.322195</a> - <p><a name="index-Reiser_002c-M_002e-154"></a><a name="index-Lavenberg_002c-S_002e-S_002e-155"></a> + <p><a name="index-Reiser_002c-M_002e-159"></a><a name="index-Lavenberg_002c-S_002e-S_002e-160"></a> This implementation is described in R. Jain , <cite>The Art of Computer Systems Performance Analysis</cite>, Wiley, 1991, p. 577. Multi-server nodes <!-- and the computation of @math{G(N)}, --> @@ -3363,15 +3530,15 @@ Performance Evaluation with Computer Science Applications</cite>, Wiley, 1998, Section 8.2.1, "Single Class Queueing Networks". - <p><a name="index-Jain_002c-R_002e-156"></a><a name="index-Bolch_002c-G_002e-157"></a><a name="index-Greiner_002c-S_002e-158"></a><a name="index-de-Meer_002c-H_002e-159"></a><a name="index-Trivedi_002c-K_002e-160"></a> + <p><a name="index-Jain_002c-R_002e-161"></a><a name="index-Bolch_002c-G_002e-162"></a><a name="index-Greiner_002c-S_002e-163"></a><a name="index-de-Meer_002c-H_002e-164"></a><a name="index-Trivedi_002c-K_002e-165"></a> <!-- MVA for single class, closed networks with load dependent servers --> <a name="doc_002dqnclosedsinglemvald"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvald</b> (<var>N, S, V</var>)<var><a name="index-qnclosedsinglemvald-161"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvald</b> (<var>N, S, V, Z</var>)<var><a name="index-qnclosedsinglemvald-162"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvald</b> (<var>N, S, V</var>)<var><a name="index-qnclosedsinglemvald-166"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvald</b> (<var>N, S, V, Z</var>)<var><a name="index-qnclosedsinglemvald-167"></a></var><br> <blockquote> - <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-163"></a><a name="index-closed-network_002c-single-class-164"></a><a name="index-load_002ddependent-service-center-165"></a> + <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-168"></a><a name="index-closed-network_002c-single-class-169"></a><a name="index-load_002ddependent-service-center-170"></a> Exact MVA algorithm for closed, single class queueing networks with load-dependent service centers. This function supports FCFS, LCFS-PR, PS and IS nodes. For networks with only fixed-rate @@ -3429,15 +3596,15 @@ 1998, Section 8.2.4.1, “Networks with Load-Deèpendent Service: Closed Networks”. - <p><a name="index-Bolch_002c-G_002e-166"></a><a name="index-Greiner_002c-S_002e-167"></a><a name="index-de-Meer_002c-H_002e-168"></a><a name="index-Trivedi_002c-K_002e-169"></a> + <p><a name="index-Bolch_002c-G_002e-171"></a><a name="index-Greiner_002c-S_002e-172"></a><a name="index-de-Meer_002c-H_002e-173"></a><a name="index-Trivedi_002c-K_002e-174"></a> <!-- CMVA for single class, closed networks with a single load dependent servers --> <a name="doc_002dqncmva"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qncmva</b> (<var>N, S, Sld, V</var>)<var><a name="index-qncmva-170"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qncmva</b> (<var>N, S, Sld, V, Z</var>)<var><a name="index-qncmva-171"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qncmva</b> (<var>N, S, Sld, V</var>)<var><a name="index-qncmva-175"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qncmva</b> (<var>N, S, Sld, V, Z</var>)<var><a name="index-qncmva-176"></a></var><br> <blockquote> - <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-172"></a><a name="index-CMVA-173"></a> + <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-177"></a><a name="index-CMVA-178"></a> Implementation of the Conditional MVA (CMVA) algorithm, a numerically stable variant of MVA for load-dependent servers. CMVA is described in G. Casale, <cite>A Note on Stable Flow-Equivalent Aggregation in @@ -3491,19 +3658,19 @@ closed networks</cite>. Queueing Syst. Theory Appl., 60:193–202, December 2008. - <p><a name="index-Casale_002c-G_002e-174"></a> + <p><a name="index-Casale_002c-G_002e-179"></a> <!-- Approximate MVA for single class, closed networks --> <p><a name="doc_002dqnclosedsinglemvaapprox"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V</var>)<var><a name="index-qnclosedsinglemvaapprox-175"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedsinglemvaapprox-176"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m, Z</var>)<var><a name="index-qnclosedsinglemvaapprox-177"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m, Z, tol</var>)<var><a name="index-qnclosedsinglemvaapprox-178"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m, Z, tol, iter_max</var>)<var><a name="index-qnclosedsinglemvaapprox-179"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V</var>)<var><a name="index-qnclosedsinglemvaapprox-180"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedsinglemvaapprox-181"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m, Z</var>)<var><a name="index-qnclosedsinglemvaapprox-182"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m, Z, tol</var>)<var><a name="index-qnclosedsinglemvaapprox-183"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m, Z, tol, iter_max</var>)<var><a name="index-qnclosedsinglemvaapprox-184"></a></var><br> <blockquote> - <p><a name="index-Mean-Value-Analysys-_0028MVA_0029_002c-approximate-180"></a><a name="index-Approximate-MVA-181"></a><a name="index-Closed-network_002c-single-class-182"></a><a name="index-Closed-network_002c-approximate-analysis-183"></a> + <p><a name="index-Mean-Value-Analysys-_0028MVA_0029_002c-approximate-185"></a><a name="index-Approximate-MVA-186"></a><a name="index-Closed-network_002c-single-class-187"></a><a name="index-Closed-network_002c-approximate-analysis-188"></a> Analyze closed, single class queueing networks using the Approximate Mean Value Analysis (MVA) algorithm. This function is based on approximating the number of customers seen at center k when a @@ -3582,20 +3749,20 @@ 1984. <a href="http://www.cs.washington.edu/homes/lazowska/qsp/">http://www.cs.washington.edu/homes/lazowska/qsp/</a>. In particular, see section 6.4.2.2 ("Approximate Solution Techniques"). - <p><a name="index-Lazowska_002c-E_002e-D_002e-184"></a><a name="index-Zahorjan_002c-J_002e-185"></a><a name="index-Graham_002c-G_002e-S_002e-186"></a><a name="index-Sevcik_002c-K_002e-C_002e-187"></a> + <p><a name="index-Lazowska_002c-E_002e-D_002e-189"></a><a name="index-Zahorjan_002c-J_002e-190"></a><a name="index-Graham_002c-G_002e-S_002e-191"></a><a name="index-Sevcik_002c-K_002e-C_002e-192"></a> <!-- MVA for multiple class, closed networks --> <p><a name="doc_002dqnclosedmultimva"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S </var>)<var><a name="index-qnclosedmultimva-188"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, V</var>)<var><a name="index-qnclosedmultimva-189"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedmultimva-190"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, V, m, Z</var>)<var><a name="index-qnclosedmultimva-191"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, P</var>)<var><a name="index-qnclosedmultimva-192"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, P, m</var>)<var><a name="index-qnclosedmultimva-193"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S </var>)<var><a name="index-qnclosedmultimva-193"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, V</var>)<var><a name="index-qnclosedmultimva-194"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedmultimva-195"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, V, m, Z</var>)<var><a name="index-qnclosedmultimva-196"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, P</var>)<var><a name="index-qnclosedmultimva-197"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, P, m</var>)<var><a name="index-qnclosedmultimva-198"></a></var><br> <blockquote> - <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-194"></a><a name="index-closed-network_002c-multiple-classes-195"></a> + <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-199"></a><a name="index-closed-network_002c-multiple-classes-200"></a> Analyze closed, multiclass queueing networks with K service centers and C independent customer classes (chains) using the Mean Value Analysys (MVA) algorithm. @@ -3725,7 +3892,7 @@ Multichain Queuing Networks</cite>, Journal of the ACM, vol. 27, n. 2, April 1980, pp. 313–322. <a href="http://doi.acm.org/10.1145/322186.322195">http://doi.acm.org/10.1145/322186.322195</a> - <p><a name="index-Reiser_002c-M_002e-196"></a><a name="index-Lavenberg_002c-S_002e-S_002e-197"></a> + <p><a name="index-Reiser_002c-M_002e-201"></a><a name="index-Lavenberg_002c-S_002e-S_002e-202"></a> This implementation is based on G. Bolch, S. Greiner, H. de Meer and K. Trivedi, <cite>Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications</cite>, Wiley, @@ -3735,18 +3902,18 @@ 1984. <a href="http://www.cs.washington.edu/homes/lazowska/qsp/">http://www.cs.washington.edu/homes/lazowska/qsp/</a>. In particular, see section 7.4.2.1 ("Exact Solution Techniques"). - <p><a name="index-Bolch_002c-G_002e-198"></a><a name="index-Greiner_002c-S_002e-199"></a><a name="index-de-Meer_002c-H_002e-200"></a><a name="index-Trivedi_002c-K_002e-201"></a><a name="index-Lazowska_002c-E_002e-D_002e-202"></a><a name="index-Zahorjan_002c-J_002e-203"></a><a name="index-Graham_002c-G_002e-S_002e-204"></a><a name="index-Sevcik_002c-K_002e-C_002e-205"></a> + <p><a name="index-Bolch_002c-G_002e-203"></a><a name="index-Greiner_002c-S_002e-204"></a><a name="index-de-Meer_002c-H_002e-205"></a><a name="index-Trivedi_002c-K_002e-206"></a><a name="index-Lazowska_002c-E_002e-D_002e-207"></a><a name="index-Zahorjan_002c-J_002e-208"></a><a name="index-Graham_002c-G_002e-S_002e-209"></a><a name="index-Sevcik_002c-K_002e-C_002e-210"></a> <!-- Approximate MVA, with Bard-Schweitzer approximation --> <a name="doc_002dqnclosedmultimvaapprox"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V</var>)<var><a name="index-qnclosedmultimvaapprox-206"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedmultimvaapprox-207"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m, Z</var>)<var><a name="index-qnclosedmultimvaapprox-208"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m, Z, tol</var>)<var><a name="index-qnclosedmultimvaapprox-209"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m, Z, tol, iter_max</var>)<var><a name="index-qnclosedmultimvaapprox-210"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V</var>)<var><a name="index-qnclosedmultimvaapprox-211"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedmultimvaapprox-212"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m, Z</var>)<var><a name="index-qnclosedmultimvaapprox-213"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m, Z, tol</var>)<var><a name="index-qnclosedmultimvaapprox-214"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m, Z, tol, iter_max</var>)<var><a name="index-qnclosedmultimvaapprox-215"></a></var><br> <blockquote> - <p><a name="index-Mean-Value-Analysys-_0028MVA_0029_002c-approximate-211"></a><a name="index-Approximate-MVA-212"></a><a name="index-Closed-network_002c-multiple-classes-213"></a><a name="index-Closed-network_002c-approximate-analysis-214"></a> + <p><a name="index-Mean-Value-Analysys-_0028MVA_0029_002c-approximate-216"></a><a name="index-Approximate-MVA-217"></a><a name="index-Closed-network_002c-multiple-classes-218"></a><a name="index-Closed-network_002c-approximate-analysis-219"></a> Analyze closed, multiclass queueing networks with K service centers and C customer classes using the approximate Mean Value Analysys (MVA) algorithm. @@ -3831,12 +3998,12 @@ proc. 4th Int. Symp. on Modelling and Performance Evaluation of Computer Systems, feb. 1979, pp. 51–62. - <p><a name="index-Bard_002c-Y_002e-215"></a> + <p><a name="index-Bard_002c-Y_002e-220"></a> P. Schweitzer, <cite>Approximate Analysis of Multiclass Closed Networks of Queues</cite>, Proc. Int. Conf. on Stochastic Control and Optimization, jun 1979, pp. 25–29. - <p><a name="index-Schweitzer_002c-P_002e-216"></a> + <p><a name="index-Schweitzer_002c-P_002e-221"></a> This implementation is based on Edward D. Lazowska, John Zahorjan, G. Scott Graham, and Kenneth C. Sevcik, <cite>Quantitative System Performance: Computer System Analysis Using Queueing Network Models</cite>, @@ -3847,7 +4014,7 @@ described above, as it computes the average response times R instead of the residence times. - <p><a name="index-Lazowska_002c-E_002e-D_002e-217"></a><a name="index-Zahorjan_002c-J_002e-218"></a><a name="index-Graham_002c-G_002e-S_002e-219"></a><a name="index-Sevcik_002c-K_002e-C_002e-220"></a> + <p><a name="index-Lazowska_002c-E_002e-D_002e-222"></a><a name="index-Zahorjan_002c-J_002e-223"></a><a name="index-Graham_002c-G_002e-S_002e-224"></a><a name="index-Sevcik_002c-K_002e-C_002e-225"></a> <h4 class="subsection">6.3.5 Mixed Networks</h4> @@ -3855,9 +4022,9 @@ <p><a name="doc_002dqnmix"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmix</b> (<var>lambda, N, S, V, m</var>)<var><a name="index-qnmix-221"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmix</b> (<var>lambda, N, S, V, m</var>)<var><a name="index-qnmix-226"></a></var><br> <blockquote> - <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-222"></a><a name="index-mixed-network-223"></a> + <p><a name="index-Mean-Value-Analysys-_0028MVA_0029-227"></a><a name="index-mixed-network-228"></a> Solution of mixed queueing networks through MVA. The network consists of K service centers (single-server or delay centers) and C independent customer chains. Both open and closed chains @@ -3948,14 +4115,14 @@ Note that in this function we compute the mean response time R instead of the mean residence time as in the reference. - <p><a name="index-Lazowska_002c-E_002e-D_002e-224"></a><a name="index-Zahorjan_002c-J_002e-225"></a><a name="index-Graham_002c-G_002e-S_002e-226"></a><a name="index-Sevcik_002c-K_002e-C_002e-227"></a> + <p><a name="index-Lazowska_002c-E_002e-D_002e-229"></a><a name="index-Zahorjan_002c-J_002e-230"></a><a name="index-Graham_002c-G_002e-S_002e-231"></a><a name="index-Sevcik_002c-K_002e-C_002e-232"></a> Herb Schwetman, <cite>Implementing the Mean Value Algorithm for the Solution of Queueing Network Models</cite>, Technical Report CSD-TR-355, Department of Computer Sciences, Purdue University, feb 15, 1982, available at <a href="http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-355.pdf">http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-355.pdf</a> - <p><a name="index-Schwetman_002c-H_002e-228"></a> + <p><a name="index-Schwetman_002c-H_002e-233"></a> <div class="node"> <a name="Algorithms-for-non-Product-form-QNs"></a> @@ -3974,9 +4141,9 @@ <p><a name="doc_002dqnmvablo"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmvablo</b> (<var>N, S, M, P</var>)<var><a name="index-qnmvablo-229"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmvablo</b> (<var>N, S, M, P</var>)<var><a name="index-qnmvablo-234"></a></var><br> <blockquote> - <p><a name="index-queueing-network-with-blocking-230"></a><a name="index-blocking-queueing-network-231"></a><a name="index-closed-network_002c-finite-capacity-232"></a> + <p><a name="index-queueing-network-with-blocking-235"></a><a name="index-blocking-queueing-network-236"></a><a name="index-closed-network_002c-finite-capacity-237"></a> MVA algorithm for closed queueing networks with blocking. <samp><span class="command">qnmvablo</span></samp> computes approximate utilization, response time and mean queue length for closed, single class queueing networks with blocking. @@ -4031,16 +4198,16 @@ Networks</cite>, IEEE Transactions on Software Engineering, vol. 14, n. 2, april 1988, pp. 418–428. <a href="http://dx.doi.org/10.1109/32.4663">http://dx.doi.org/10.1109/32.4663</a> - <p><a name="index-Akyildiz_002c-I_002e-F_002e-233"></a> + <p><a name="index-Akyildiz_002c-I_002e-F_002e-238"></a> <a name="doc_002dqnmarkov"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>lambda, S, C, P</var>)<var><a name="index-qnmarkov-234"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>lambda, S, C, P, m</var>)<var><a name="index-qnmarkov-235"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>N, S, C, P</var>)<var><a name="index-qnmarkov-236"></a></var><br> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>N, S, C, P, m</var>)<var><a name="index-qnmarkov-237"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>lambda, S, C, P</var>)<var><a name="index-qnmarkov-239"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>lambda, S, C, P, m</var>)<var><a name="index-qnmarkov-240"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>N, S, C, P</var>)<var><a name="index-qnmarkov-241"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>N, S, C, P, m</var>)<var><a name="index-qnmarkov-242"></a></var><br> <blockquote> - <p><a name="index-closed-network_002c-multiple-classes-238"></a><a name="index-closed-network_002c-finite-capacity-239"></a><a name="index-blocking-queueing-network-240"></a><a name="index-RS-blocking-241"></a> + <p><a name="index-closed-network_002c-multiple-classes-243"></a><a name="index-closed-network_002c-finite-capacity-244"></a><a name="index-blocking-queueing-network-245"></a><a name="index-RS-blocking-246"></a> Compute utilization, response time, average queue length and throughput for open or closed queueing networks with finite capacity. Blocking type is Repetitive-Service (RS). This function explicitly @@ -4150,9 +4317,9 @@ <p><a name="doc_002dqnopenab"></a> <div class="defun"> -— Function File: [<var>Xu</var>, <var>Rl</var>] = <b>qnopenab</b> (<var>lambda, D</var>)<var><a name="index-qnopenab-242"></a></var><br> +— Function File: [<var>Xu</var>, <var>Rl</var>] = <b>qnopenab</b> (<var>lambda, D</var>)<var><a name="index-qnopenab-247"></a></var><br> <blockquote> - <p><a name="index-bounds_002c-asymptotic-243"></a><a name="index-open-network-244"></a> + <p><a name="index-bounds_002c-asymptotic-248"></a><a name="index-open-network-249"></a> Compute Asymptotic Bounds for single-class, open Queueing Networks with K service centers. @@ -4192,14 +4359,14 @@ 1984. <a href="http://www.cs.washington.edu/homes/lazowska/qsp/">http://www.cs.washington.edu/homes/lazowska/qsp/</a>. In particular, see section 5.2 ("Asymptotic Bounds"). - <p><a name="index-Lazowska_002c-E_002e-D_002e-245"></a><a name="index-Zahorjan_002c-J_002e-246"></a><a name="index-Graham_002c-G_002e-S_002e-247"></a><a name="index-Sevcik_002c-K_002e-C_002e-248"></a> + <p><a name="index-Lazowska_002c-E_002e-D_002e-250"></a><a name="index-Zahorjan_002c-J_002e-251"></a><a name="index-Graham_002c-G_002e-S_002e-252"></a><a name="index-Sevcik_002c-K_002e-C_002e-253"></a> <a name="doc_002dqnclosedab"></a> <div class="defun"> -— Function File: [<var>Xl</var>, <var>Xu</var>, <var>Rl</var>, <var>Ru</var>] = <b>qnclosedab</b> (<var>N, D</var>)<var><a name="index-qnclosedab-249"></a></var><br> -— Function File: [<var>Xl</var>, <var>Xu</var>, <var>Rl</var>, <var>Ru</var>] = <b>qnclosedab</b> (<var>N, D, Z</var>)<var><a name="index-qnclosedab-250"></a></var><br> +— Function File: [<var>Xl</var>, <var>Xu</var>, <var>Rl</var>, <var>Ru</var>] = <b>qnclosedab</b> (<var>N, D</var>)<var><a name="index-qnclosedab-254"></a></var><br> +— Function File: [<var>Xl</var>, <var>Xu</var>, <var>Rl</var>, <var>Ru</var>] = <b>qnclosedab</b> (<var>N, D, Z</var>)<var><a name="index-qnclosedab-255"></a></var><br> <blockquote> - <p><a name="index-bounds_002c-asymptotic-251"></a><a name="index-closed-network-252"></a> + <p><a name="index-bounds_002c-asymptotic-256"></a><a name="index-closed-network-257"></a> Compute Asymptotic Bounds for single-class, closed Queueing Networks with K service centers. @@ -4240,14 +4407,14 @@ 1984. <a href="http://www.cs.washington.edu/homes/lazowska/qsp/">http://www.cs.washington.edu/homes/lazowska/qsp/</a>. In particular, see section 5.2 ("Asymptotic Bounds"). - <p><a name="index-Lazowska_002c-E_002e-D_002e-253"></a><a name="index-Zahorjan_002c-J_002e-254"></a><a name="index-Graham_002c-G_002e-S_002e-255"></a><a name="index-Sevcik_002c-K_002e-C_002e-256"></a> + <p><a name="index-Lazowska_002c-E_002e-D_002e-258"></a><a name="index-Zahorjan_002c-J_002e-259"></a><a name="index-Graham_002c-G_002e-S_002e-260"></a><a name="index-Sevcik_002c-K_002e-C_002e-261"></a> <p><a name="doc_002dqnopenbsb"></a> <div class="defun"> -— Function File: [<var>Xu</var>, <var>Rl</var>, <var>Ru</var>] = <b>qnopenbsb</b> (<var>lambda, D</var>)<var><a name="index-qnopenbsb-257"></a></var><br> +— Function File: [<var>Xu</var>, <var>Rl</var>, <var>Ru</var>] = <b>qnopenbsb</b> (<var>lambda, D</var>)<var><a name="index-qnopenbsb-262"></a></var><br> <blockquote> - <p><a name="index-bounds_002c-balanced-system-258"></a><a name="index-open-network-259"></a> + <p><a name="index-bounds_002c-balanced-system-263"></a><a name="index-open-network-264"></a> Compute Balanced System Bounds for single-class, open Queueing Networks with K service centers. @@ -4287,14 +4454,14 @@ 1984. <a href="http://www.cs.washington.edu/homes/lazowska/qsp/">http://www.cs.washington.edu/homes/lazowska/qsp/</a>. In particular, see section 5.4 ("Balanced Systems Bounds"). - <p><a name="index-Lazowska_002c-E_002e-D_002e-260"></a><a name="index-Zahorjan_002c-J_002e-261"></a><a name="index-Graham_002c-G_002e-S_002e-262"></a><a name="index-Sevcik_002c-K_002e-C_002e-263"></a> + <p><a name="index-Lazowska_002c-E_002e-D_002e-265"></a><a name="index-Zahorjan_002c-J_002e-266"></a><a name="index-Graham_002c-G_002e-S_002e-267"></a><a name="index-Sevcik_002c-K_002e-C_002e-268"></a> <a name="doc_002dqnclosedbsb"></a> <div class="defun"> -— Function File: [<var>Xl</var>, <var>Xu</var>, <var>Rl</var>, <var>Ru</var>] = <b>qnclosedbsb</b> (<var>N, D</var>)<var><a name="index-qnclosedbsb-264"></a></var><br> -— Function File: [<var>Xl</var>, <var>Xu</var>, <var>Rl</var>, <var>Ru</var>] = <b>qnclosedbsb</b> (<var>N, D, Z</var>)<var><a name="index-qnclosedbsb-265"></a></var><br> +— Function File: [<var>Xl</var>, <var>Xu</var>, <var>Rl</var>, <var>Ru</var>] = <b>qnclosedbsb</b> (<var>N, D</var>)<var><a name="index-qnclosedbsb-269"></a></var><br> +— Function File: [<var>Xl</var>, <var>Xu</var>, <var>Rl</var>, <var>Ru</var>] = <b>qnclosedbsb</b> (<var>N, D, Z</var>)<var><a name="index-qnclosedbsb-270"></a></var><br> <blockquote> - <p><a name="index-bounds_002c-balanced-system-266"></a><a name="index-closed-network-267"></a> + <p><a name="index-bounds_002c-balanced-system-271"></a><a name="index-closed-network-272"></a> Compute Balanced System Bounds for single-class, closed Queueing Networks with K service centers. @@ -4330,7 +4497,7 @@ <p><a name="doc_002dqnclosedpb"></a> <div class="defun"> -— Function File: [<var>Xl</var>, <var>Xu</var>] = <b>qnclosedpb</b> (<var>N, D </var>)<var><a name="index-qnclosedpb-268"></a></var><br> +— Function File: [<var>Xl</var>, <var>Xu</var>] = <b>qnclosedpb</b> (<var>N, D </var>)<var><a name="index-qnclosedpb-273"></a></var><br> <blockquote> <p>Compute PB Bounds (C. H. Hsieh and S. Lam, 1987) for single-class, closed Queueing Networks @@ -4374,13 +4541,13 @@ Non-Iterative Analysis Technique for Closed Queueing Networks</cite>, IEEE Transactions on Computers, 57(6):780-794, June 2008. - <p><a name="index-Hsieh_002c-C_002e-H-269"></a><a name="index-Lam_002c-S_002e-270"></a><a name="index-Casale_002c-G_002e-271"></a><a name="index-Muntz_002c-R_002e-R_002e-272"></a><a name="index-Serazzi_002c-G_002e-273"></a> + <p><a name="index-Hsieh_002c-C_002e-H-274"></a><a name="index-Lam_002c-S_002e-275"></a><a name="index-Casale_002c-G_002e-276"></a><a name="index-Muntz_002c-R_002e-R_002e-277"></a><a name="index-Serazzi_002c-G_002e-278"></a> <a name="doc_002dqnclosedgb"></a> <div class="defun"> -— Function File: [<var>Xl</var>, <var>Xu</var>, <var>Ql</var>, <var>Qu</var>] = <b>qnclosedgb</b> (<var>N, D, Z</var>)<var><a name="index-qnclosedgb-274"></a></var><br> +— Function File: [<var>Xl</var>, <var>Xu</var>, <var>Ql</var>, <var>Qu</var>] = <b>qnclosedgb</b> (<var>N, D, Z</var>)<var><a name="index-qnclosedgb-279"></a></var><br> <blockquote> - <p><a name="index-bounds_002c-geometric-275"></a><a name="index-closed-network-276"></a> + <p><a name="index-bounds_002c-geometric-280"></a><a name="index-closed-network-281"></a> Compute Geometric Bounds (GB) for single-class, closed Queueing Networks. <p><strong>INPUTS</strong> @@ -4421,7 +4588,7 @@ Queueing Networks</cite>, IEEE Transactions on Computers, 57(6):780-794, June 2008. <a href="http://doi.ieeecomputersociety.org/10.1109/TC.2008.37">http://doi.ieeecomputersociety.org/10.1109/TC.2008.37</a> - <p><a name="index-Casale_002c-G_002e-277"></a><a name="index-Muntz_002c-R_002e-R_002e-278"></a><a name="index-Serazzi_002c-G_002e-279"></a> + <p><a name="index-Casale_002c-G_002e-282"></a><a name="index-Muntz_002c-R_002e-R_002e-283"></a><a name="index-Serazzi_002c-G_002e-284"></a> In this implementation we set X^+ and X^- as the upper and lower Asymptotic Bounds as computed by the <code>qnclosedab</code> function, respectively. @@ -4441,9 +4608,9 @@ <p><a name="doc_002dqnclosed"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosed</b> (<var>N, S, V, <small class="dots">...</small></var>)<var><a name="index-qnclosed-280"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosed</b> (<var>N, S, V, <small class="dots">...</small></var>)<var><a name="index-qnclosed-285"></a></var><br> <blockquote> - <p><a name="index-closed-network-281"></a> + <p><a name="index-closed-network-286"></a> This function computes steady-state performance measures of closed queueing networks using the Mean Value Analysis (MVA) algorithm. The qneneing network is allowed to contain fixed-capacity centers, delay @@ -4510,9 +4677,9 @@ <p><a name="doc_002dqnopen"></a> <div class="defun"> -— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopen</b> (<var>lambda, S, V, <small class="dots">...</small></var>)<var><a name="index-qnopen-282"></a></var><br> +— Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopen</b> (<var>lambda, S, V, <small class="dots">...</small></var>)<var><a name="index-qnopen-287"></a></var><br> <blockquote> - <p><a name="index-open-network-283"></a> + <p><a name="index-open-network-288"></a> Compute utilization, response time, average number of requests in the system, and throughput for open queueing networks. If <var>lambda</var> is a scalar, the network is considered a single-class QN and is solved @@ -4565,8 +4732,8 @@ <p><a name="doc_002dqnvisits"></a> <div class="defun"> -— Function File: [<var>V</var> <var>ch</var>] = <b>qnvisits</b> (<var>P</var>)<var><a name="index-qnvisits-284"></a></var><br> -— Function File: <var>V</var> = <b>qnvisits</b> (<var>P, lambda</var>)<var><a name="index-qnvisits-285"></a></var><br> +— Function File: [<var>V</var> <var>ch</var>] = <b>qnvisits</b> (<var>P</var>)<var><a name="index-qnvisits-289"></a></var><br> +— Function File: <var>V</var> = <b>qnvisits</b> (<var>P, lambda</var>)<var><a name="index-qnvisits-290"></a></var><br> <blockquote> <p>Compute the average number of visits to the service centers of a single class, open or closed Queueing Network with N service @@ -4628,9 +4795,9 @@ <p><a name="doc_002dpopulation_005fmix"></a> <div class="defun"> -— Function File: pop_mix = <b>population_mix</b> (<var>k, N</var>)<var><a name="index-population_005fmix-286"></a></var><br> +— Function File: pop_mix = <b>population_mix</b> (<var>k, N</var>)<var><a name="index-population_005fmix-291"></a></var><br> <blockquote> - <p><a name="index-population-mix-287"></a><a name="index-closed-network_002c-multiple-classes-288"></a> + <p><a name="index-population-mix-292"></a><a name="index-closed-network_002c-multiple-classes-293"></a> Return the set of valid population mixes with exactly <var>k</var> customers, for a closed multiclass Queueing Network with population vector <var>N</var>. More specifically, given a multiclass Queueing @@ -4692,13 +4859,13 @@ Indices for a Complex Summation</cite>, unpublished report, available at <a href="http://arantxa.ii.uam.es/~ssantini/writing/notes/s668_summation.pdf">http://arantxa.ii.uam.es/~ssantini/writing/notes/s668_summation.pdf</a> - <p><a name="index-Schwetman_002c-H_002e-289"></a><a name="index-Santini_002c-S_002e-290"></a> + <p><a name="index-Schwetman_002c-H_002e-294"></a><a name="index-Santini_002c-S_002e-295"></a> <a name="doc_002dqnmvapop"></a> <div class="defun"> -— Function File: <var>H</var> = <b>qnmvapop</b> (<var>N</var>)<var><a name="index-qnmvapop-291"></a></var><br> +— Function File: <var>H</var> = <b>qnmvapop</b> (<var>N</var>)<var><a name="index-qnmvapop-296"></a></var><br> <blockquote> - <p><a name="index-population-mix-292"></a><a name="index-closed-network_002c-multiple-classes-293"></a> + <p><a name="index-population-mix-297"></a><a name="index-closed-network_002c-multiple-classes-298"></a> Given a network with C customer classes, this function computes the number of valid population mixes <var>H</var><code>(r,n)</code> that can be constructed by the multiclass MVA algorithm by allocating n @@ -4735,7 +4902,103 @@ Perform. Eval. Rev. 10, 3 (Sep. 1981), 80-85. DOI <a href="http://doi.acm.org/10.1145/1010629.805477">http://doi.acm.org/10.1145/1010629.805477</a> - <p><a name="index-Zahorjan_002c-J_002e-294"></a><a name="index-Wong_002c-E_002e-295"></a> + <p><a name="index-Zahorjan_002c-J_002e-299"></a><a name="index-Wong_002c-E_002e-300"></a> + +<!-- DO NOT EDIT! Generated automatically by munge-texi. --> +<!-- *- texinfo -*- --> +<!-- Copyright (C) 2012 Moreno Marzolla --> +<!-- This file is part of the queueing toolbox, a Queueing Networks --> +<!-- analysis package for GNU Octave. --> +<!-- The queueing toolbox is free software; you can redistribute it --> +<!-- and/or modify it under the terms of the GNU General Public License --> +<!-- as published by the Free Software Foundation; either version 3 of --> +<!-- the License, or (at your option) any later version. --> +<!-- The queueing toolbox is distributed in the hope that it will be --> +<!-- useful, but WITHOUT ANY WARRANTY; without even the implied warranty --> +<!-- of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the --> +<!-- GNU General Public License for more details. --> +<!-- You should have received a copy of the GNU General Public License --> +<!-- along with the queueing toolbox; see the file COPYING. If not, see --> +<!-- <http://www.gnu.org/licenses/>. --> +<div class="node"> +<a name="References"></a> +<p><hr> +Next: <a rel="next" accesskey="n" href="#Contributing-Guidelines">Contributing Guidelines</a>, +Previous: <a rel="previous" accesskey="p" href="#Queueing-Networks">Queueing Networks</a>, +Up: <a rel="up" accesskey="u" href="#Top">Top</a> + +</div> + +<h2 class="chapter">7 References</h2> + + <dl> +<dt>[Aky88]<dd>Ian F. Akyildiz, <cite>Mean Value Analysis for Blocking Queueing +Networks</cite>, IEEE Transactions on Software Engineering, vol. 14, n. 2, +april 1988, pp. 418–428. <a href="http://dx.doi.org/10.1109/32.4663">http://dx.doi.org/10.1109/32.4663</a> + + <br><dt>[Bar79]<dd>Y. Bard, <cite>Some Extensions to Multiclass Queueing Network Analysis</cite>, +proc. 4th Int. Symp. on Modelling and Performance Evaluation of +Computer Systems, feb. 1979, pp. 51–62. + + <br><dt>[RGMT98]<dd>G. Bolch, S. Greiner, H. de Meer and +K. Trivedi, <cite>Queueing Networks and Markov Chains: Modeling and +Performance Evaluation with Computer Science Applications</cite>, Wiley, +1998. + + <br><dt>[Buz73]<dd>Jeffrey P. Buzen, <cite>Computational Algorithms for Closed Queueing +Networks with Exponential Servers</cite>, Communications of the ACM, volume +16, number 9, september 1973, +pp. 527–531. <a href="http://doi.acm.org/10.1145/362342.362345">http://doi.acm.org/10.1145/362342.362345</a> + + <br><dt>[CMS08]<dd>G. Casale, R. R. Muntz, G. Serazzi, +<cite>Geometric Bounds: a Non-Iterative Analysis Technique for Closed +Queueing Networks</cite>, IEEE Transactions on Computers, 57(6):780-794, +June 2008. <a href="http://doi.ieeecomputersociety.org/10.1109/TC.2008.37">http://doi.ieeecomputersociety.org/10.1109/TC.2008.37</a> + + <br><dt>[GrSn97]<dd>Charles M. Grinstead, J. Laurie Snell, (July 1997). Introduction to +Probability. American Mathematical Society. ISBN 978-0821807491 + + <br><dt>[Jai91]<dd>R. Jain , <cite>The Art of Computer Systems Performance Analysis</cite>, +Wiley, 1991, p. 577. + + <br><dt>[HsLa87]<dd>C. H. Hsieh and S. Lam, +<cite>Two classes of performance bounds for closed queueing networks</cite>, +PEVA, vol. 7, n. 1, pp. 3–30, 1987 + + <br><dt>[LZGS84]<dd>Edward D. Lazowska, John Zahorjan, G. Scott Graham, and Kenneth C. +Sevcik, <cite>Quantitative System Performance: Computer System +Analysis Using Queueing Network Models</cite>, Prentice Hall, +1984. <a href="http://www.cs.washington.edu/homes/lazowska/qsp/">http://www.cs.washington.edu/homes/lazowska/qsp/</a>. + + <br><dt>[ReKo76]<dd>M. Reiser, H. Kobayashi, <cite>On The Convolution Algorithm for +Separable Queueing Networks</cite>, In Proceedings of the 1976 ACM +SIGMETRICS Conference on Computer Performance Modeling Measurement and +Evaluation (Cambridge, Massachusetts, United States, March 29–31, +1976). SIGMETRICS '76. ACM, New York, NY, +pp. 109–117. <a href="http://doi.acm.org/10.1145/800200.806187">http://doi.acm.org/10.1145/800200.806187</a> + + <br><dt>[ReLa80]<dd>M. Reiser and S. S. Lavenberg, <cite>Mean-Value Analysis of Closed +Multichain Queuing Networks</cite>, Journal of the ACM, vol. 27, n. 2, April +1980, pp. 313–322. <a href="http://doi.acm.org/10.1145/322186.322195">http://doi.acm.org/10.1145/322186.322195</a> + + <br><dt>[Sch81]<dd>Herb Schwetman, <cite>Some Computational +Aspects of Queueing Network Models</cite>, Technical Report CSD-TR-354, +Department of Computer Sciences, Purdue University, feb, 1981 +(revised). +<a href="http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-354.pdf">http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-354.pdf</a> + + <br><dt>[Sch82]<dd>Herb Schwetman, <cite>Implementing the Mean Value Algorithm for the +Solution of Queueing Network Models</cite>, Technical Report CSD-TR-355, +Department of Computer Sciences, Purdue University, feb 15, 1982, +available at +<a href="http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-355.pdf">http://www.cs.purdue.edu/research/technical_reports/1980/TR%2080-355.pdf</a> + + <br><dt>[ZaWo81]<dd>Zahorjan, J. and Wong, E. <cite>The solution of separable queueing +network models using mean value analysis</cite>. SIGMETRICS +Perform. Eval. Rev. 10, 3 (Sep. 1981), 80-85. DOI +<a href="http://doi.acm.org/10.1145/1010629.805477">http://doi.acm.org/10.1145/1010629.805477</a> + +</dl> <!-- Appendix starts here --> <!-- DO NOT EDIT! Generated automatically by munge-texi. --> @@ -4758,7 +5021,7 @@ <a name="Contributing-Guidelines"></a> <p><hr> Next: <a rel="next" accesskey="n" href="#Acknowledgements">Acknowledgements</a>, -Previous: <a rel="previous" accesskey="p" href="#Queueing-Networks">Queueing Networks</a>, +Previous: <a rel="previous" accesskey="p" href="#References">References</a>, Up: <a rel="up" accesskey="u" href="#Top">Top</a> </div> @@ -4846,7 +5109,7 @@ <h2 class="appendix">Appendix C GNU GENERAL PUBLIC LICENSE</h2> -<p><a name="index-warranty-296"></a><a name="index-copyright-297"></a> +<p><a name="index-warranty-301"></a><a name="index-copyright-302"></a> <div align="center">Version 3, 29 June 2007</div> <pre class="display"> Copyright © 2007 Free Software Foundation, Inc. <a href="http://fsf.org/">http://fsf.org/</a> @@ -5553,79 +5816,80 @@ <h2 class="unnumbered">Concept Index</h2> <ul class="index-cp" compact> -<li><a href="#index-Absorption-probabilities-21">Absorption probabilities</a>: <a href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a></li> -<li><a href="#index-Approximate-MVA-181">Approximate MVA</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Asymmetric-_0040math_007bM_002fM_002fm_007d-system-81">Asymmetric M/M/m system</a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> -<li><a href="#index-BCMP-network-136">BCMP network</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Birth_002ddeath-process-32">Birth-death process</a>: <a href="#Birth_002ddeath-process-_0028CTMC_0029">Birth-death process (CTMC)</a></li> +<li><a href="#index-Absorption-probabilities-26">Absorption probabilities</a>: <a href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a></li> +<li><a href="#index-Approximate-MVA-186">Approximate MVA</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Asymmetric-_0040math_007bM_002fM_002fm_007d-system-86">Asymmetric M/M/m system</a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> +<li><a href="#index-BCMP-network-141">BCMP network</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Birth_002ddeath-process-38">Birth-death process</a>: <a href="#Birth_002ddeath-process-_0028CTMC_0029">Birth-death process (CTMC)</a></li> <li><a href="#index-Birth_002ddeath-process-13">Birth-death process</a>: <a href="#Birth_002ddeath-process-_0028DTMC_0029">Birth-death process (DTMC)</a></li> -<li><a href="#index-blocking-queueing-network-231">blocking queueing network</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> -<li><a href="#index-bounds_002c-asymptotic-243">bounds, asymptotic</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-bounds_002c-balanced-system-258">bounds, balanced system</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-bounds_002c-geometric-275">bounds, geometric</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-closed-network-281">closed network</a>: <a href="#Utility-functions">Utility functions</a></li> -<li><a href="#index-closed-network-252">closed network</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-closed-network-113">closed network</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Closed-network_002c-approximate-analysis-183">Closed network, approximate analysis</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-closed-network_002c-finite-capacity-232">closed network, finite capacity</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> -<li><a href="#index-closed-network_002c-multiple-classes-288">closed network, multiple classes</a>: <a href="#Utility-functions">Utility functions</a></li> -<li><a href="#index-closed-network_002c-multiple-classes-238">closed network, multiple classes</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> -<li><a href="#index-Closed-network_002c-multiple-classes-213">Closed network, multiple classes</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-closed-network_002c-multiple-classes-195">closed network, multiple classes</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Closed-network_002c-single-class-182">Closed network, single class</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-closed-network_002c-single-class-152">closed network, single class</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-CMVA-173">CMVA</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Continuous-time-Markov-chain-27">Continuous time Markov chain</a>: <a href="#State-occupancy-probabilities-_0028CTMC_0029">State occupancy probabilities (CTMC)</a></li> -<li><a href="#index-convolution-algorithm-115">convolution algorithm</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-copyright-297">copyright</a>: <a href="#Copying">Copying</a></li> +<li><a href="#index-blocking-queueing-network-236">blocking queueing network</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> +<li><a href="#index-bounds_002c-asymptotic-248">bounds, asymptotic</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-bounds_002c-balanced-system-263">bounds, balanced system</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-bounds_002c-geometric-280">bounds, geometric</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-closed-network-286">closed network</a>: <a href="#Utility-functions">Utility functions</a></li> +<li><a href="#index-closed-network-257">closed network</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-closed-network-118">closed network</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Closed-network_002c-approximate-analysis-188">Closed network, approximate analysis</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-closed-network_002c-finite-capacity-237">closed network, finite capacity</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> +<li><a href="#index-closed-network_002c-multiple-classes-293">closed network, multiple classes</a>: <a href="#Utility-functions">Utility functions</a></li> +<li><a href="#index-closed-network_002c-multiple-classes-243">closed network, multiple classes</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> +<li><a href="#index-Closed-network_002c-multiple-classes-218">Closed network, multiple classes</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-closed-network_002c-multiple-classes-200">closed network, multiple classes</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Closed-network_002c-single-class-187">Closed network, single class</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-closed-network_002c-single-class-157">closed network, single class</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-CMVA-178">CMVA</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Continuous-time-Markov-chain-33">Continuous time Markov chain</a>: <a href="#State-occupancy-probabilities-_0028CTMC_0029">State occupancy probabilities (CTMC)</a></li> +<li><a href="#index-convolution-algorithm-120">convolution algorithm</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-copyright-302">copyright</a>: <a href="#Copying">Copying</a></li> <li><a href="#index-Discrete-time-Markov-chain-6">Discrete time Markov chain</a>: <a href="#State-occupancy-probabilities-_0028DTMC_0029">State occupancy probabilities (DTMC)</a></li> -<li><a href="#index-Expected-sojourn-time-36">Expected sojourn time</a>: <a href="#Expected-sojourn-times-_0028CTMC_0029">Expected sojourn times (CTMC)</a></li> -<li><a href="#index-First-passage-times-51">First passage times</a>: <a href="#First-passage-times-_0028CTMC_0029">First passage times (CTMC)</a></li> -<li><a href="#index-First-passage-times-15">First passage times</a>: <a href="#First-passage-times-_0028DTMC_0029">First passage times (DTMC)</a></li> -<li><a href="#index-Jackson-network-106">Jackson network</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-load_002ddependent-service-center-125">load-dependent service center</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-g_t_0040math_007bM_002fG_002f1_007d-system-87">M/G/1 system</a>: <a href="#The-M_002fG_002f1-System">The M/G/1 System</a></li> -<li><a href="#index-g_t_0040math_007bM_002fH_005fm_002f1_007d-system-89">M/H_m/1 system</a>: <a href="#The-M_002fHm_002f1-System">The M/Hm/1 System</a></li> -<li><a href="#index-g_t_0040math_007bM_002fM_002f1_007d-system-53">M/M/1 system</a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> -<li><a href="#index-g_t_0040math_007bM_002fM_002f1_002fK_007d-system-73">M/M/1/K system</a>: <a href="#The-M_002fM_002f1_002fK-System">The M/M/1/K System</a></li> -<li><a href="#index-g_t_0040math_007bM_002fM_002f_007dinf-system-66">M/M/inf system</a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> -<li><a href="#index-g_t_0040math_007bM_002fM_002fm_007d-system-60">M/M/m system</a>: <a href="#The-M_002fM_002fm-System">The M/M/m System</a></li> -<li><a href="#index-g_t_0040math_007bM_002fM_002fm_002fK_007d-system-75">M/M/m/K system</a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> -<li><a href="#index-Markov-chain_002c-continuous-time-50">Markov chain, continuous time</a>: <a href="#First-passage-times-_0028CTMC_0029">First passage times (CTMC)</a></li> -<li><a href="#index-Markov-chain_002c-continuous-time-42">Markov chain, continuous time</a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> -<li><a href="#index-Markov-chain_002c-continuous-time-39">Markov chain, continuous time</a>: <a href="#Time_002daveraged-expected-sojourn-times-_0028CTMC_0029">Time-averaged expected sojourn times (CTMC)</a></li> -<li><a href="#index-Markov-chain_002c-continuous-time-35">Markov chain, continuous time</a>: <a href="#Expected-sojourn-times-_0028CTMC_0029">Expected sojourn times (CTMC)</a></li> -<li><a href="#index-Markov-chain_002c-continuous-time-31">Markov chain, continuous time</a>: <a href="#Birth_002ddeath-process-_0028CTMC_0029">Birth-death process (CTMC)</a></li> -<li><a href="#index-Markov-chain_002c-continuous-time-26">Markov chain, continuous time</a>: <a href="#State-occupancy-probabilities-_0028CTMC_0029">State occupancy probabilities (CTMC)</a></li> -<li><a href="#index-Markov-chain_002c-continuous-time-23">Markov chain, continuous time</a>: <a href="#Continuous_002dTime-Markov-Chains">Continuous-Time Markov Chains</a></li> +<li><a href="#index-Expected-sojourn-time-42">Expected sojourn time</a>: <a href="#Expected-sojourn-times-_0028CTMC_0029">Expected sojourn times (CTMC)</a></li> +<li><a href="#index-Expected-sojourn-times-16">Expected sojourn times</a>: <a href="#Expected-number-of-visits-_0028DTMC_0029">Expected number of visits (DTMC)</a></li> +<li><a href="#index-First-passage-times-56">First passage times</a>: <a href="#First-passage-times-_0028CTMC_0029">First passage times (CTMC)</a></li> +<li><a href="#index-First-passage-times-21">First passage times</a>: <a href="#First-passage-times-_0028DTMC_0029">First passage times (DTMC)</a></li> +<li><a href="#index-Fundamental-matrix-27">Fundamental matrix</a>: <a href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a></li> +<li><a href="#index-Jackson-network-111">Jackson network</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-load_002ddependent-service-center-130">load-dependent service center</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-g_t_0040math_007bM_002fG_002f1_007d-system-92">M/G/1 system</a>: <a href="#The-M_002fG_002f1-System">The M/G/1 System</a></li> +<li><a href="#index-g_t_0040math_007bM_002fH_005fm_002f1_007d-system-94">M/H_m/1 system</a>: <a href="#The-M_002fHm_002f1-System">The M/Hm/1 System</a></li> +<li><a href="#index-g_t_0040math_007bM_002fM_002f1_007d-system-58">M/M/1 system</a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> +<li><a href="#index-g_t_0040math_007bM_002fM_002f1_002fK_007d-system-78">M/M/1/K system</a>: <a href="#The-M_002fM_002f1_002fK-System">The M/M/1/K System</a></li> +<li><a href="#index-g_t_0040math_007bM_002fM_002f_007dinf-system-71">M/M/inf system</a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> +<li><a href="#index-g_t_0040math_007bM_002fM_002fm_007d-system-65">M/M/m system</a>: <a href="#The-M_002fM_002fm-System">The M/M/m System</a></li> +<li><a href="#index-g_t_0040math_007bM_002fM_002fm_002fK_007d-system-80">M/M/m/K system</a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> +<li><a href="#index-Markov-chain_002c-continuous-time-48">Markov chain, continuous time</a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> +<li><a href="#index-Markov-chain_002c-continuous-time-45">Markov chain, continuous time</a>: <a href="#Time_002daveraged-expected-sojourn-times-_0028CTMC_0029">Time-averaged expected sojourn times (CTMC)</a></li> +<li><a href="#index-Markov-chain_002c-continuous-time-41">Markov chain, continuous time</a>: <a href="#Expected-sojourn-times-_0028CTMC_0029">Expected sojourn times (CTMC)</a></li> +<li><a href="#index-Markov-chain_002c-continuous-time-37">Markov chain, continuous time</a>: <a href="#Birth_002ddeath-process-_0028CTMC_0029">Birth-death process (CTMC)</a></li> +<li><a href="#index-Markov-chain_002c-continuous-time-32">Markov chain, continuous time</a>: <a href="#State-occupancy-probabilities-_0028CTMC_0029">State occupancy probabilities (CTMC)</a></li> +<li><a href="#index-Markov-chain_002c-continuous-time-29">Markov chain, continuous time</a>: <a href="#Continuous_002dTime-Markov-Chains">Continuous-Time Markov Chains</a></li> <li><a href="#index-Markov-chain_002c-discrete-time-12">Markov chain, discrete time</a>: <a href="#Birth_002ddeath-process-_0028DTMC_0029">Birth-death process (DTMC)</a></li> <li><a href="#index-Markov-chain_002c-discrete-time-5">Markov chain, discrete time</a>: <a href="#State-occupancy-probabilities-_0028DTMC_0029">State occupancy probabilities (DTMC)</a></li> <li><a href="#index-Markov-chain_002c-discrete-time-2">Markov chain, discrete time</a>: <a href="#Discrete_002dTime-Markov-Chains">Discrete-Time Markov Chains</a></li> -<li><a href="#index-Markov-chain_002c-disctete-time-19">Markov chain, disctete time</a>: <a href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a></li> -<li><a href="#index-Markov-chain_002c-state-occupancy-probabilities-28">Markov chain, state occupancy probabilities</a>: <a href="#State-occupancy-probabilities-_0028CTMC_0029">State occupancy probabilities (CTMC)</a></li> +<li><a href="#index-Markov-chain_002c-state-occupancy-probabilities-34">Markov chain, state occupancy probabilities</a>: <a href="#State-occupancy-probabilities-_0028CTMC_0029">State occupancy probabilities (CTMC)</a></li> <li><a href="#index-Markov-chain_002c-stationary-probabilities-7">Markov chain, stationary probabilities</a>: <a href="#State-occupancy-probabilities-_0028DTMC_0029">State occupancy probabilities (DTMC)</a></li> <li><a href="#index-Markov-chain_002c-transient-probabilities-9">Markov chain, transient probabilities</a>: <a href="#State-occupancy-probabilities-_0028DTMC_0029">State occupancy probabilities (DTMC)</a></li> -<li><a href="#index-Mean-recurrence-times-16">Mean recurrence times</a>: <a href="#First-passage-times-_0028DTMC_0029">First passage times (DTMC)</a></li> -<li><a href="#index-Mean-time-to-absorption-43">Mean time to absorption</a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> -<li><a href="#index-Mean-time-to-absorption-20">Mean time to absorption</a>: <a href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a></li> -<li><a href="#index-Mean-Value-Analysys-_0028MVA_0029-151">Mean Value Analysys (MVA)</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Mean-Value-Analysys-_0028MVA_0029_002c-approximate-180">Mean Value Analysys (MVA), approximate</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-mixed-network-223">mixed network</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-normalization-constant-114">normalization constant</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-open-network-283">open network</a>: <a href="#Utility-functions">Utility functions</a></li> -<li><a href="#index-open-network-244">open network</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-open-network_002c-multiple-classes-143">open network, multiple classes</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-open-network_002c-single-class-105">open network, single class</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-population-mix-287">population mix</a>: <a href="#Utility-functions">Utility functions</a></li> -<li><a href="#index-queueing-network-with-blocking-230">queueing network with blocking</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> -<li><a href="#index-queueing-networks-90">queueing networks</a>: <a href="#Queueing-Networks">Queueing Networks</a></li> -<li><a href="#index-RS-blocking-241">RS blocking</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> -<li><a href="#index-Stationary-probabilities-29">Stationary probabilities</a>: <a href="#State-occupancy-probabilities-_0028CTMC_0029">State occupancy probabilities (CTMC)</a></li> +<li><a href="#index-Mean-recurrence-times-22">Mean recurrence times</a>: <a href="#First-passage-times-_0028DTMC_0029">First passage times (DTMC)</a></li> +<li><a href="#index-Mean-time-to-absorption-49">Mean time to absorption</a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> +<li><a href="#index-Mean-time-to-absorption-25">Mean time to absorption</a>: <a href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a></li> +<li><a href="#index-Mean-Value-Analysys-_0028MVA_0029-156">Mean Value Analysys (MVA)</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Mean-Value-Analysys-_0028MVA_0029_002c-approximate-185">Mean Value Analysys (MVA), approximate</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-mixed-network-228">mixed network</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-normalization-constant-119">normalization constant</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-open-network-288">open network</a>: <a href="#Utility-functions">Utility functions</a></li> +<li><a href="#index-open-network-249">open network</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-open-network_002c-multiple-classes-148">open network, multiple classes</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-open-network_002c-single-class-110">open network, single class</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-population-mix-292">population mix</a>: <a href="#Utility-functions">Utility functions</a></li> +<li><a href="#index-queueing-network-with-blocking-235">queueing network with blocking</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> +<li><a href="#index-queueing-networks-95">queueing networks</a>: <a href="#Queueing-Networks">Queueing Networks</a></li> +<li><a href="#index-RS-blocking-246">RS blocking</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> +<li><a href="#index-Stationary-probabilities-35">Stationary probabilities</a>: <a href="#State-occupancy-probabilities-_0028CTMC_0029">State occupancy probabilities (CTMC)</a></li> <li><a href="#index-Stationary-probabilities-8">Stationary probabilities</a>: <a href="#State-occupancy-probabilities-_0028DTMC_0029">State occupancy probabilities (DTMC)</a></li> -<li><a href="#index-Time_002dalveraged-sojourn-time-40">Time-alveraged sojourn time</a>: <a href="#Time_002daveraged-expected-sojourn-times-_0028CTMC_0029">Time-averaged expected sojourn times (CTMC)</a></li> -<li><a href="#index-traffic-intensity-67">traffic intensity</a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> +<li><a href="#index-Time_002dalveraged-sojourn-time-46">Time-alveraged sojourn time</a>: <a href="#Time_002daveraged-expected-sojourn-times-_0028CTMC_0029">Time-averaged expected sojourn times (CTMC)</a></li> +<li><a href="#index-Time_002dalveraged-sojourn-time-19">Time-alveraged sojourn time</a>: <a href="#Time_002daveraged-expected-sojourn-times-_0028DTMC_0029">Time-averaged expected sojourn times (DTMC)</a></li> +<li><a href="#index-traffic-intensity-72">traffic intensity</a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> <li><a href="#index-Transient-probabilities-10">Transient probabilities</a>: <a href="#State-occupancy-probabilities-_0028DTMC_0029">State occupancy probabilities (DTMC)</a></li> -<li><a href="#index-warranty-296">warranty</a>: <a href="#Copying">Copying</a></li> +<li><a href="#index-warranty-301">warranty</a>: <a href="#Copying">Copying</a></li> </ul><div class="node"> <a name="Function-Index"></a> <p><hr> @@ -5640,53 +5904,55 @@ <ul class="index-fn" compact> -<li><a href="#index-ctmc-24"><code>ctmc</code></a>: <a href="#State-occupancy-probabilities-_0028CTMC_0029">State occupancy probabilities (CTMC)</a></li> -<li><a href="#index-ctmc_005fbd-30"><code>ctmc_bd</code></a>: <a href="#Birth_002ddeath-process-_0028CTMC_0029">Birth-death process (CTMC)</a></li> -<li><a href="#index-ctmc_005fcheck_005fQ-22"><code>ctmc_check_Q</code></a>: <a href="#Continuous_002dTime-Markov-Chains">Continuous-Time Markov Chains</a></li> -<li><a href="#index-ctmc_005fexps-33"><code>ctmc_exps</code></a>: <a href="#Expected-sojourn-times-_0028CTMC_0029">Expected sojourn times (CTMC)</a></li> -<li><a href="#index-ctmc_005ffpt-48"><code>ctmc_fpt</code></a>: <a href="#First-passage-times-_0028CTMC_0029">First passage times (CTMC)</a></li> -<li><a href="#index-ctmc_005fmtta-41"><code>ctmc_mtta</code></a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> -<li><a href="#index-ctmc_005ftaexps-37"><code>ctmc_taexps</code></a>: <a href="#Time_002daveraged-expected-sojourn-times-_0028CTMC_0029">Time-averaged expected sojourn times (CTMC)</a></li> +<li><a href="#index-ctmc-30"><code>ctmc</code></a>: <a href="#State-occupancy-probabilities-_0028CTMC_0029">State occupancy probabilities (CTMC)</a></li> +<li><a href="#index-ctmc_005fbd-36"><code>ctmc_bd</code></a>: <a href="#Birth_002ddeath-process-_0028CTMC_0029">Birth-death process (CTMC)</a></li> +<li><a href="#index-ctmc_005fcheck_005fQ-28"><code>ctmc_check_Q</code></a>: <a href="#Continuous_002dTime-Markov-Chains">Continuous-Time Markov Chains</a></li> +<li><a href="#index-ctmc_005fexps-39"><code>ctmc_exps</code></a>: <a href="#Expected-sojourn-times-_0028CTMC_0029">Expected sojourn times (CTMC)</a></li> +<li><a href="#index-ctmc_005ffpt-54"><code>ctmc_fpt</code></a>: <a href="#First-passage-times-_0028CTMC_0029">First passage times (CTMC)</a></li> +<li><a href="#index-ctmc_005fmtta-47"><code>ctmc_mtta</code></a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> +<li><a href="#index-ctmc_005ftaexps-43"><code>ctmc_taexps</code></a>: <a href="#Time_002daveraged-expected-sojourn-times-_0028CTMC_0029">Time-averaged expected sojourn times (CTMC)</a></li> <li><a href="#index-dtmc-3"><code>dtmc</code></a>: <a href="#State-occupancy-probabilities-_0028DTMC_0029">State occupancy probabilities (DTMC)</a></li> <li><a href="#index-dtmc_005fbd-11"><code>dtmc_bd</code></a>: <a href="#Birth_002ddeath-process-_0028DTMC_0029">Birth-death process (DTMC)</a></li> <li><a href="#index-dtmc_005fcheck_005fP-1"><code>dtmc_check_P</code></a>: <a href="#Discrete_002dTime-Markov-Chains">Discrete-Time Markov Chains</a></li> -<li><a href="#index-dtmc_005ffpt-14"><code>dtmc_fpt</code></a>: <a href="#First-passage-times-_0028DTMC_0029">First passage times (DTMC)</a></li> -<li><a href="#index-dtmc_005fmtta-17"><code>dtmc_mtta</code></a>: <a href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a></li> -<li><a href="#index-population_005fmix-286"><code>population_mix</code></a>: <a href="#Utility-functions">Utility functions</a></li> -<li><a href="#index-qnammm-80"><code>qnammm</code></a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> -<li><a href="#index-qnclosed-280"><code>qnclosed</code></a>: <a href="#Utility-functions">Utility functions</a></li> -<li><a href="#index-qnclosedab-249"><code>qnclosedab</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-qnclosedbsb-264"><code>qnclosedbsb</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-qnclosedgb-274"><code>qnclosedgb</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-qnclosedmultimva-188"><code>qnclosedmultimva</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnclosedmultimvaapprox-206"><code>qnclosedmultimvaapprox</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnclosedpb-268"><code>qnclosedpb</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-qnclosedsinglemva-148"><code>qnclosedsinglemva</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnclosedsinglemvaapprox-175"><code>qnclosedsinglemvaapprox</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnclosedsinglemvald-161"><code>qnclosedsinglemvald</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qncmva-170"><code>qncmva</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnconvolution-111"><code>qnconvolution</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnconvolutionld-121"><code>qnconvolutionld</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnjackson-102"><code>qnjackson</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnmarkov-234"><code>qnmarkov</code></a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> -<li><a href="#index-qnmg1-86"><code>qnmg1</code></a>: <a href="#The-M_002fG_002f1-System">The M/G/1 System</a></li> -<li><a href="#index-qnmh1-88"><code>qnmh1</code></a>: <a href="#The-M_002fHm_002f1-System">The M/Hm/1 System</a></li> -<li><a href="#index-qnmix-221"><code>qnmix</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnmknode-91"><code>qnmknode</code></a>: <a href="#Generic-Algorithms">Generic Algorithms</a></li> -<li><a href="#index-qnmm1-52"><code>qnmm1</code></a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> -<li><a href="#index-qnmm1k-72"><code>qnmm1k</code></a>: <a href="#The-M_002fM_002f1_002fK-System">The M/M/1/K System</a></li> -<li><a href="#index-qnmminf-65"><code>qnmminf</code></a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> -<li><a href="#index-qnmmm-58"><code>qnmmm</code></a>: <a href="#The-M_002fM_002fm-System">The M/M/m System</a></li> -<li><a href="#index-qnmmmk-74"><code>qnmmmk</code></a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> -<li><a href="#index-qnmvablo-229"><code>qnmvablo</code></a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> -<li><a href="#index-qnmvapop-291"><code>qnmvapop</code></a>: <a href="#Utility-functions">Utility functions</a></li> -<li><a href="#index-qnopen-282"><code>qnopen</code></a>: <a href="#Utility-functions">Utility functions</a></li> -<li><a href="#index-qnopenab-242"><code>qnopenab</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-qnopenbsb-257"><code>qnopenbsb</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-qnopenmulti-141"><code>qnopenmulti</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnopensingle-133"><code>qnopensingle</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-qnsolve-98"><code>qnsolve</code></a>: <a href="#Generic-Algorithms">Generic Algorithms</a></li> -<li><a href="#index-qnvisits-284"><code>qnvisits</code></a>: <a href="#Utility-functions">Utility functions</a></li> +<li><a href="#index-dtmc_005fexps-17"><code>dtmc_exps</code></a>: <a href="#Time_002daveraged-expected-sojourn-times-_0028DTMC_0029">Time-averaged expected sojourn times (DTMC)</a></li> +<li><a href="#index-dtmc_005fexps-14"><code>dtmc_exps</code></a>: <a href="#Expected-number-of-visits-_0028DTMC_0029">Expected number of visits (DTMC)</a></li> +<li><a href="#index-dtmc_005ffpt-20"><code>dtmc_fpt</code></a>: <a href="#First-passage-times-_0028DTMC_0029">First passage times (DTMC)</a></li> +<li><a href="#index-dtmc_005fmtta-23"><code>dtmc_mtta</code></a>: <a href="#Mean-time-to-absorption-_0028DTMC_0029">Mean time to absorption (DTMC)</a></li> +<li><a href="#index-population_005fmix-291"><code>population_mix</code></a>: <a href="#Utility-functions">Utility functions</a></li> +<li><a href="#index-qnammm-85"><code>qnammm</code></a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> +<li><a href="#index-qnclosed-285"><code>qnclosed</code></a>: <a href="#Utility-functions">Utility functions</a></li> +<li><a href="#index-qnclosedab-254"><code>qnclosedab</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-qnclosedbsb-269"><code>qnclosedbsb</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-qnclosedgb-279"><code>qnclosedgb</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-qnclosedmultimva-193"><code>qnclosedmultimva</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnclosedmultimvaapprox-211"><code>qnclosedmultimvaapprox</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnclosedpb-273"><code>qnclosedpb</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-qnclosedsinglemva-153"><code>qnclosedsinglemva</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnclosedsinglemvaapprox-180"><code>qnclosedsinglemvaapprox</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnclosedsinglemvald-166"><code>qnclosedsinglemvald</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qncmva-175"><code>qncmva</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnconvolution-116"><code>qnconvolution</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnconvolutionld-126"><code>qnconvolutionld</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnjackson-107"><code>qnjackson</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnmarkov-239"><code>qnmarkov</code></a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> +<li><a href="#index-qnmg1-91"><code>qnmg1</code></a>: <a href="#The-M_002fG_002f1-System">The M/G/1 System</a></li> +<li><a href="#index-qnmh1-93"><code>qnmh1</code></a>: <a href="#The-M_002fHm_002f1-System">The M/Hm/1 System</a></li> +<li><a href="#index-qnmix-226"><code>qnmix</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnmknode-96"><code>qnmknode</code></a>: <a href="#Generic-Algorithms">Generic Algorithms</a></li> +<li><a href="#index-qnmm1-57"><code>qnmm1</code></a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> +<li><a href="#index-qnmm1k-77"><code>qnmm1k</code></a>: <a href="#The-M_002fM_002f1_002fK-System">The M/M/1/K System</a></li> +<li><a href="#index-qnmminf-70"><code>qnmminf</code></a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> +<li><a href="#index-qnmmm-63"><code>qnmmm</code></a>: <a href="#The-M_002fM_002fm-System">The M/M/m System</a></li> +<li><a href="#index-qnmmmk-79"><code>qnmmmk</code></a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> +<li><a href="#index-qnmvablo-234"><code>qnmvablo</code></a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> +<li><a href="#index-qnmvapop-296"><code>qnmvapop</code></a>: <a href="#Utility-functions">Utility functions</a></li> +<li><a href="#index-qnopen-287"><code>qnopen</code></a>: <a href="#Utility-functions">Utility functions</a></li> +<li><a href="#index-qnopenab-247"><code>qnopenab</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-qnopenbsb-262"><code>qnopenbsb</code></a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-qnopenmulti-146"><code>qnopenmulti</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnopensingle-138"><code>qnopensingle</code></a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-qnsolve-103"><code>qnsolve</code></a>: <a href="#Generic-Algorithms">Generic Algorithms</a></li> +<li><a href="#index-qnvisits-289"><code>qnvisits</code></a>: <a href="#Utility-functions">Utility functions</a></li> </ul><div class="node"> <a name="Author-Index"></a> <p><hr> @@ -5700,60 +5966,60 @@ <ul class="index-au" compact> -<li><a href="#index-Akyildiz_002c-I_002e-F_002e-233">Akyildiz, I. F.</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> -<li><a href="#index-Bard_002c-Y_002e-215">Bard, Y.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Bolch_002c-G_002e-107">Bolch, G.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Bolch_002c-G_002e-82">Bolch, G.</a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> -<li><a href="#index-Bolch_002c-G_002e-76">Bolch, G.</a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> -<li><a href="#index-Bolch_002c-G_002e-68">Bolch, G.</a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> -<li><a href="#index-Bolch_002c-G_002e-61">Bolch, G.</a>: <a href="#The-M_002fM_002fm-System">The M/M/m System</a></li> -<li><a href="#index-Bolch_002c-G_002e-54">Bolch, G.</a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> -<li><a href="#index-Bolch_002c-G_002e-44">Bolch, G.</a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> -<li><a href="#index-Buzen_002c-J_002e-P_002e-116">Buzen, J. P.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Casale_002c-G_002e-271">Casale, G.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Casale_002c-G_002e-174">Casale, G.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-de-Meer_002c-H_002e-109">de Meer, H.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-de-Meer_002c-H_002e-84">de Meer, H.</a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> -<li><a href="#index-de-Meer_002c-H_002e-78">de Meer, H.</a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> -<li><a href="#index-de-Meer_002c-H_002e-70">de Meer, H.</a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> -<li><a href="#index-de-Meer_002c-H_002e-63">de Meer, H.</a>: <a href="#The-M_002fM_002fm-System">The M/M/m System</a></li> -<li><a href="#index-de-Meer_002c-H_002e-56">de Meer, H.</a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> -<li><a href="#index-de-Meer_002c-H_002e-46">de Meer, H.</a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> -<li><a href="#index-Graham_002c-G_002e-S_002e-247">Graham, G. S.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Graham_002c-G_002e-S_002e-146">Graham, G. S.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Greiner_002c-S_002e-108">Greiner, S.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Greiner_002c-S_002e-83">Greiner, S.</a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> -<li><a href="#index-Greiner_002c-S_002e-77">Greiner, S.</a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> -<li><a href="#index-Greiner_002c-S_002e-69">Greiner, S.</a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> -<li><a href="#index-Greiner_002c-S_002e-62">Greiner, S.</a>: <a href="#The-M_002fM_002fm-System">The M/M/m System</a></li> -<li><a href="#index-Greiner_002c-S_002e-55">Greiner, S.</a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> -<li><a href="#index-Greiner_002c-S_002e-45">Greiner, S.</a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> -<li><a href="#index-Hsieh_002c-C_002e-H-269">Hsieh, C. H</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Jain_002c-R_002e-156">Jain, R.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Kobayashi_002c-H_002e-128">Kobayashi, H.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Lam_002c-S_002e-270">Lam, S.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Lavenberg_002c-S_002e-S_002e-155">Lavenberg, S. S.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Lazowska_002c-E_002e-D_002e-245">Lazowska, E. D.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Lazowska_002c-E_002e-D_002e-144">Lazowska, E. D.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Muntz_002c-R_002e-R_002e-272">Muntz, R. R.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Reiser_002c-M_002e-127">Reiser, M.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Santini_002c-S_002e-290">Santini, S.</a>: <a href="#Utility-functions">Utility functions</a></li> -<li><a href="#index-Schweitzer_002c-P_002e-216">Schweitzer, P.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Schwetman_002c-H_002e-289">Schwetman, H.</a>: <a href="#Utility-functions">Utility functions</a></li> -<li><a href="#index-Schwetman_002c-H_002e-126">Schwetman, H.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Serazzi_002c-G_002e-273">Serazzi, G.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Sevcik_002c-K_002e-C_002e-248">Sevcik, K. C.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Sevcik_002c-K_002e-C_002e-147">Sevcik, K. C.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Trivedi_002c-K_002e-110">Trivedi, K.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> -<li><a href="#index-Trivedi_002c-K_002e-85">Trivedi, K.</a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> -<li><a href="#index-Trivedi_002c-K_002e-79">Trivedi, K.</a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> -<li><a href="#index-Trivedi_002c-K_002e-71">Trivedi, K.</a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> -<li><a href="#index-Trivedi_002c-K_002e-64">Trivedi, K.</a>: <a href="#The-M_002fM_002fm-System">The M/M/m System</a></li> -<li><a href="#index-Trivedi_002c-K_002e-57">Trivedi, K.</a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> -<li><a href="#index-Trivedi_002c-K_002e-47">Trivedi, K.</a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> -<li><a href="#index-Wong_002c-E_002e-295">Wong, E.</a>: <a href="#Utility-functions">Utility functions</a></li> -<li><a href="#index-Zahorjan_002c-J_002e-294">Zahorjan, J.</a>: <a href="#Utility-functions">Utility functions</a></li> -<li><a href="#index-Zahorjan_002c-J_002e-246">Zahorjan, J.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> -<li><a href="#index-Zahorjan_002c-J_002e-145">Zahorjan, J.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Akyildiz_002c-I_002e-F_002e-238">Akyildiz, I. F.</a>: <a href="#Algorithms-for-non-Product_002dform-QNs">Algorithms for non Product-form QNs</a></li> +<li><a href="#index-Bard_002c-Y_002e-220">Bard, Y.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Bolch_002c-G_002e-112">Bolch, G.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Bolch_002c-G_002e-87">Bolch, G.</a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> +<li><a href="#index-Bolch_002c-G_002e-81">Bolch, G.</a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> +<li><a href="#index-Bolch_002c-G_002e-73">Bolch, G.</a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> +<li><a href="#index-Bolch_002c-G_002e-66">Bolch, G.</a>: <a href="#The-M_002fM_002fm-System">The M/M/m System</a></li> +<li><a href="#index-Bolch_002c-G_002e-59">Bolch, G.</a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> +<li><a href="#index-Bolch_002c-G_002e-50">Bolch, G.</a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> +<li><a href="#index-Buzen_002c-J_002e-P_002e-121">Buzen, J. P.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Casale_002c-G_002e-276">Casale, G.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-Casale_002c-G_002e-179">Casale, G.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-de-Meer_002c-H_002e-114">de Meer, H.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-de-Meer_002c-H_002e-89">de Meer, H.</a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> +<li><a href="#index-de-Meer_002c-H_002e-83">de Meer, H.</a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> +<li><a href="#index-de-Meer_002c-H_002e-75">de Meer, H.</a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> +<li><a href="#index-de-Meer_002c-H_002e-68">de Meer, H.</a>: <a href="#The-M_002fM_002fm-System">The M/M/m System</a></li> +<li><a href="#index-de-Meer_002c-H_002e-61">de Meer, H.</a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> +<li><a href="#index-de-Meer_002c-H_002e-52">de Meer, H.</a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> +<li><a href="#index-Graham_002c-G_002e-S_002e-252">Graham, G. S.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-Graham_002c-G_002e-S_002e-151">Graham, G. S.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Greiner_002c-S_002e-113">Greiner, S.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Greiner_002c-S_002e-88">Greiner, S.</a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> +<li><a href="#index-Greiner_002c-S_002e-82">Greiner, S.</a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> +<li><a href="#index-Greiner_002c-S_002e-74">Greiner, S.</a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> +<li><a href="#index-Greiner_002c-S_002e-67">Greiner, S.</a>: <a href="#The-M_002fM_002fm-System">The M/M/m System</a></li> +<li><a href="#index-Greiner_002c-S_002e-60">Greiner, S.</a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> +<li><a href="#index-Greiner_002c-S_002e-51">Greiner, S.</a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> +<li><a href="#index-Hsieh_002c-C_002e-H-274">Hsieh, C. H</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-Jain_002c-R_002e-161">Jain, R.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Kobayashi_002c-H_002e-133">Kobayashi, H.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Lam_002c-S_002e-275">Lam, S.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-Lavenberg_002c-S_002e-S_002e-160">Lavenberg, S. S.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Lazowska_002c-E_002e-D_002e-250">Lazowska, E. D.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-Lazowska_002c-E_002e-D_002e-149">Lazowska, E. D.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Muntz_002c-R_002e-R_002e-277">Muntz, R. R.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-Reiser_002c-M_002e-132">Reiser, M.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Santini_002c-S_002e-295">Santini, S.</a>: <a href="#Utility-functions">Utility functions</a></li> +<li><a href="#index-Schweitzer_002c-P_002e-221">Schweitzer, P.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Schwetman_002c-H_002e-294">Schwetman, H.</a>: <a href="#Utility-functions">Utility functions</a></li> +<li><a href="#index-Schwetman_002c-H_002e-131">Schwetman, H.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Serazzi_002c-G_002e-278">Serazzi, G.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-Sevcik_002c-K_002e-C_002e-253">Sevcik, K. C.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-Sevcik_002c-K_002e-C_002e-152">Sevcik, K. C.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Trivedi_002c-K_002e-115">Trivedi, K.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> +<li><a href="#index-Trivedi_002c-K_002e-90">Trivedi, K.</a>: <a href="#The-Asymmetric-M_002fM_002fm-System">The Asymmetric M/M/m System</a></li> +<li><a href="#index-Trivedi_002c-K_002e-84">Trivedi, K.</a>: <a href="#The-M_002fM_002fm_002fK-System">The M/M/m/K System</a></li> +<li><a href="#index-Trivedi_002c-K_002e-76">Trivedi, K.</a>: <a href="#The-M_002fM_002finf-System">The M/M/inf System</a></li> +<li><a href="#index-Trivedi_002c-K_002e-69">Trivedi, K.</a>: <a href="#The-M_002fM_002fm-System">The M/M/m System</a></li> +<li><a href="#index-Trivedi_002c-K_002e-62">Trivedi, K.</a>: <a href="#The-M_002fM_002f1-System">The M/M/1 System</a></li> +<li><a href="#index-Trivedi_002c-K_002e-53">Trivedi, K.</a>: <a href="#Mean-time-to-absorption-_0028CTMC_0029">Mean time to absorption (CTMC)</a></li> +<li><a href="#index-Wong_002c-E_002e-300">Wong, E.</a>: <a href="#Utility-functions">Utility functions</a></li> +<li><a href="#index-Zahorjan_002c-J_002e-299">Zahorjan, J.</a>: <a href="#Utility-functions">Utility functions</a></li> +<li><a href="#index-Zahorjan_002c-J_002e-251">Zahorjan, J.</a>: <a href="#Bounds-on-performance">Bounds on performance</a></li> +<li><a href="#index-Zahorjan_002c-J_002e-150">Zahorjan, J.</a>: <a href="#Algorithms-for-Product_002dForm-QNs">Algorithms for Product-Form QNs</a></li> </ul></body></html>
--- a/main/queueing/doc/queueing.texi Sun Mar 18 15:21:33 2012 +0000 +++ b/main/queueing/doc/queueing.texi Sun Mar 18 15:35:02 2012 +0000 @@ -157,6 +157,7 @@ * Markov Chains:: Functions for Markov Chains. * Single Station Queueing Systems:: Functions for single-station queueing systems. * Queueing Networks:: Functions for queueing networks. +* References:: References * Contributing Guidelines:: How to contribute. * Acknowledgements:: People who contributed to the queueing toolbox. * Copying:: The GNU General Public License. @@ -173,6 +174,7 @@ @include markovchains.texi @include singlestation.texi @include queueingnetworks.texi +@include references.texi @c @c Appendix starts here
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/queueing/doc/references.txi Sun Mar 18 15:35:02 2012 +0000 @@ -0,0 +1,107 @@ +@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. @url{http://dx.doi.org/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 [RGMT98] +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. @url{http://doi.acm.org/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. @url{http://doi.ieeecomputersociety.org/10.1109/TC.2008.37} + +@item [GrSn97] +Charles M. Grinstead, J. Laurie Snell, (July 1997). Introduction to +Probability. American Mathematical Society. ISBN 978-0821807491 + +@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. @url{http://www.cs.washington.edu/homes/lazowska/qsp/}. + +@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. @url{http://doi.acm.org/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. @url{http://doi.acm.org/10.1145/322186.322195} + +@item [Sch81] +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} + +@item [Sch82] +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} + +@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 +@url{http://doi.acm.org/10.1145/1010629.805477} + +@end table
--- a/main/queueing/inst/ctmc_exps.m Sun Mar 18 15:21:33 2012 +0000 +++ b/main/queueing/inst/ctmc_exps.m Sun Mar 18 15:35:02 2012 +0000 @@ -111,38 +111,22 @@ L = lsode( {ff, fj}, zeros(size(p)), t ); endif else # absorbing case -#{ - ## This code is left for information only - - ## F(t) are the transient state occupancy probabilities at time t. - ## It is known that F(t) = p*expm(Q*t) (see function ctmc()). - ## The expected times spent in each state until absorption can - ## be computed as the integral of F(t) from t=0 to t=inf - F = @(t) (p*expm(Q*t)); ## FIXME: this must be restricted to transient states ONLY!!!! - ## Since function quadv does not support infinite integration - ## limits, we define a new function G(u) = F(tan(pi/2*u)) such that - ## the integral of G(u) on [0,1] is the integral of F(t) on [0, - ## +inf]. - G = @(u) (F(tan(pi/2*u))*pi/2*(1+tan(pi/2*u)**2)); + ## Identify transient states. If all states are transient, then + ## raise an error since we can't deal with non-absorbing chains + ## here. - L = quadv(G,0,1); -#} - ## Find nonzero rows. Nonzero rows correspond to transient states, - ## while zero rows are absorbing states. If there are no zero rows, - ## then the Markov chain does not contain absorbing states and we - ## raise an error N = rows(Q); - nzrows = find( any( abs(Q) > epsilon, 2 ) ); - if ( length( nzrows ) == N ) + tr = find( any( abs(Q) > epsilon, 2 ) ); + if ( length( tr ) == N ) error( "There are no absorbing states" ); endif - QN = Q(nzrows,nzrows); - pN = p(nzrows); + QN = Q(tr,tr); + pN = p(tr); LN = -pN*inv(QN); L = zeros(1,N); - L(nzrows) = LN; + L(tr) = LN; endif endfunction %!test
--- a/main/queueing/inst/ctmc_fpt.m Sun Mar 18 15:21:33 2012 +0000 +++ b/main/queueing/inst/ctmc_fpt.m Sun Mar 18 15:35:02 2012 +0000 @@ -20,14 +20,10 @@ ## @deftypefn {Function File} {@var{M} =} ctmc_fpt (@var{Q}) ## @deftypefnx {Function File} {@var{m} =} ctmc_fpt (@var{Q}, @var{i}, @var{j}) ## -## @cindex Markov chain, continuous time ## @cindex First passage times ## -## If called with a single argument, computes the mean first passage -## times @code{@var{M}(i,j)}, the average times before state @var{j} is -## reached, starting from state @var{i}, for all @math{1 \leq i, j \leq -## N}. If called with three arguments, returns the single value -## @code{@var{m} = @var{M}(i,j)}. +## Compute mean first passage times for an irreducible continuous-time +## Markov chain. ## ## @strong{INPUTS} ## @@ -43,8 +39,7 @@ ## Initial state. ## ## @item j -## Destination state. If @var{j} is a vector, returns the mean first passage -## time to any state in @var{j}. +## Destination state. ## ## @end table ## @@ -53,17 +48,18 @@ ## @table @var ## ## @item M -## If this function is called with a single argument, the result ## @code{@var{M}(i,j)} is the average time before state ## @var{j} is visited for the first time, starting from state @var{i}. +## We set @code{@var{M}(i,i) = 0}. ## ## @item m -## If this function is called with three arguments, the result ## @var{m} is the average time before state @var{j} is visited for the first ## time, starting from state @var{i}. ## ## @end table ## +## @seealso{dtmc_fpt} +## ## @end deftypefn ## Author: Moreno Marzolla <marzolla(at)cs.unibo.it> @@ -80,7 +76,7 @@ [N err] = ctmc_check_Q(Q); (N>0) || \ - usage(err); + error(err); if ( nargin == 1 ) M = zeros(N,N); @@ -109,10 +105,13 @@ %! M = ctmc_fpt(Q) %! m = ctmc_fpt(Q,1,3) -%!xtest -%! Q = unifrnd(0.1,0.9,10,10); +%!test +%! N = 10; +%! Q = reshape(1:N^2,N,N); +%! Q(1:N+1:end) = 0; %! Q -= diag(sum(Q,2)); %! M = ctmc_fpt(Q); +%! assert( all(diag(M) < 10*eps) ); %!xtest %! Q = unifrnd(0.1,0.9,10,10);
--- a/main/queueing/inst/ctmc_mtta.m Sun Mar 18 15:21:33 2012 +0000 +++ b/main/queueing/inst/ctmc_mtta.m Sun Mar 18 15:35:02 2012 +0000 @@ -53,6 +53,8 @@ ## ## @end table ## +## @seealso{dtmc_mtta} +## ## @end deftypefn ## Author: Moreno Marzolla <marzolla(at)cs.unibo.it>
--- a/main/queueing/inst/ctmc_taexps.m Sun Mar 18 15:21:33 2012 +0000 +++ b/main/queueing/inst/ctmc_taexps.m Sun Mar 18 15:35:02 2012 +0000 @@ -74,38 +74,20 @@ print_usage(); endif - [N err] = ctmc_check_Q(Q); - - (N>0) || \ - usage(err); - - if ( nargin == 2 ) - p = varargin{1}; - else - t = varargin{1}; - p = varargin{2}; - endif + L = ctmc_exps(Q,varargin{:}); + M = L ./ sum(L); - ( isvector(p) && length(p) == N && all(p>=0) && abs(sum(p)-1.0)<epsilon ) || \ - usage( "p must be a probability vector" ); +#{ if ( nargin == 3 ) - if ( isscalar(t) ) - (t >= 0) || \ - usage( "t must be >= 0" ); - F = @(x) (p*expm(Q*x)); - M = quadv(F,0,t) / t; - else - ## FIXME: deprecate this? - t = t(:)'; # make t a row vector - p = p(:)'; # make p a row vector - ff = @(x,t) (((x')*(Q-eye(N)/t).+p/t)'); - fj = @(x,t) (Q-eye(N)/t); - M = lsode( {ff, fj}, zeros(size(p)), t ); - endif + (t >= 0) || \ + usage( "t must be >= 0" ); + F = @(x) (p*expm(Q*x)); + M = quadv(F,0,t) / t; else L = ctmc_exps(Q,p); M = L ./ sum(L); endif +#} endfunction %!test %! Q = [ 0 0.1 0 0; \
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/queueing/inst/dtmc_exps.m Sun Mar 18 15:35:02 2012 +0000 @@ -0,0 +1,144 @@ +## Copyright (C) 2012 Moreno Marzolla +## +## This file is part of the queueing toolbox. +## +## The queueing toolbox is free software: you can redistribute it and/or +## modify it under the terms of the GNU General Public License as +## published by the Free Software Foundation, either version 3 of the +## License, or (at your option) any later version. +## +## The queueing toolbox is distributed in the hope that it will be +## useful, but WITHOUT ANY WARRANTY; without even the implied warranty +## of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +## General Public License for more details. +## +## You should have received a copy of the GNU General Public License +## along with the queueing toolbox. If not, see <http://www.gnu.org/licenses/>. + +## -*- texinfo -*- +## +## @deftypefn {Function File} {@var{L} =} dtmc_exps (@var{P}, @var{n}, @var{p0}) +## @deftypefnx {Function File} {@var{L} =} dtmc_exps (@var{P}, @var{p0}) +## +## @cindex Expected sojourn times +## +## Compute the expected number of visits to each state during the first +## @var{n} transitions, or until abrosption. +## +## @strong{INPUTS} +## +## @table @var +## +## @item P +## @math{N \times N} transition probability matrix. +## +## @item n +## Number of steps during which the expected number of visits are +## computed (@math{@var{n} @geq{} 0}). If @code{@var{n}=0}, simply +## returns @var{p0}. If @code{@var{n} > 0}, returns the expected number +## of visits after exactly @var{n} transitions. +## +## @item p0 +## Initial state occupancy probability +## +## @end table +## +## @strong{OUTPUTS} +## +## @table @var +## +## @item L +## When called with two arguments, @code{@var{L}(i)} is the expected +## number of visits to transient state @math{i} before absorption. When +## called with three arguments, @code{@var{L}(i)} is the expected number +## of visits to state @math{i} during the first @var{n} transitions. +## +## @end table +## +## @seealso{ctmc_exps} +## +## @end deftypefn + +## Author: Moreno Marzolla <marzolla(at)cs.unibo.it> +## Web: http://www.moreno.marzolla.name/ + +function L = dtmc_exps ( P, varargin ) + + persistent epsilon = 10*eps; + + if ( nargin < 2 || nargin > 3 ) + print_usage(); + endif + + [K err] = dtmc_check_P(P); + + (K>0) || \ + usage(err); + + if ( nargin == 2 ) + p0 = varargin{1}; + else + n = varargin{1}; + p0 = varargin{2}; + endif + + ( isvector(p0) && length(p0) == K && all(p0>=0) && abs(sum(p0)-1.0)<epsilon ) || \ + usage( "p0 must be a state occupancy probability vector" ); + + p0 = p0(:)'; # make p0 a row vector + + if ( nargin == 3 ) + isscalar(n) && n>=0 || \ + error("n must be >=0"); + n = fix(n); + L = zeros(sizeof(p0)); + + ## It is know that + ## + ## I + P + P^2 + P^3 + ... + P^n = (I-P)^-1 * (I-P^(n+1)) + ## + ## and therefore we could succintly write + ## + ## L = p0*inv(eye(K)-P)*(eye(K)-P^(n+1)); + ## + ## Unfortunatly, the method above is numerically unstable (at least + ## for small values of n), so we use the crude approach below. + + PP = p0; + L = zeros(1,K); + for p=0:n + L += PP; + PP *= P; + endfor + else + ## identify transient states + tr = find(diag(P) < 1); + k = length(tr); # number of transient states + if ( k == K ) + error("There are no absorbing states"); + endif + + N = zeros(size(P)); + + ## Source: Grinstead, Charles M.; Snell, J. Laurie (July 1997). "Ch. + ## 11: Markov Chains". Introduction to Probability. American + ## Mathematical Society. ISBN 978-0821807491. + + ## http://www.cs.virginia.edu/~gfx/Courses/2006/DataDriven/bib/texsyn/Chapter11.pdf + tmpN = inv(eye(k) - P(tr,tr)); # matrix N = (I-Q)^-1 + N(tr,tr) = tmpN; + L = p0*N; + endif +endfunction +%!test +%! P = dtmc_bd([1 1 1 1], [0 0 0 0]); +%! L = dtmc_exps(P,[1 0 0 0 0]); +%! t = dtmc_mtta(P,[1 0 0 0 0]); +%! assert( L, [1 1 1 1 0] ); +%! assert( sum(L), t ); + +%!test +%! P = dtmc_bd(linspace(0.1,0.4,5),linspace(0.4,0.1,5)); +%! p0 = [1 0 0 0 0 0]; +%! L = dtmc_exps(P,0,p0); +%! assert( L, p0 ); \ No newline at end of file
--- a/main/queueing/inst/dtmc_fpt.m Sun Mar 18 15:21:33 2012 +0000 +++ b/main/queueing/inst/dtmc_fpt.m Sun Mar 18 15:35:02 2012 +0000 @@ -22,11 +22,8 @@ ## @cindex First passage times ## @cindex Mean recurrence times ## -## Compute the mean first passage times matrix @math{\bf M}, such that -## @code{@var{M}(i,j)} is the average number of transitions before state -## @var{j} is reached, starting from state @var{i}, for all @math{1 \leq -## i, j \leq N}. Diagonal elements of @var{M} are the mean recurrence -## times. +## Compute mean first passage times and mean recurrence times +## for an irreducible discrete-time Markov chain. ## ## @strong{INPUTS} ## @@ -46,14 +43,16 @@ ## @table @var ## ## @item M -## @code{@var{M}(i,j)} is the average number of transitions before state -## @var{j} is reached for the first time, starting from state @var{i}. -## @code{@var{M}(i,i)} is the @emph{mean recurrence time} of state -## @math{i}, and represents the average time needed to return to state -## @var{i}. +## For all @math{i \neq j}, @code{@var{M}(i,j)} is the average number of +## transitions before state @var{j} is reached for the first time, +## starting from state @var{i}. @code{@var{M}(i,i)} is the @emph{mean +## recurrence time} of state @math{i}, and represents the average time +## needed to return to state @var{i}. ## ## @end table ## +## @seealso{ctmc_fpt} +## ## @end deftypefn ## Author: Moreno Marzolla <marzolla(at)cs.unibo.it> @@ -74,39 +73,16 @@ error("Cannot compute first passage times for absorbing chains"); endif - w = dtmc(P); + ## Source: + ## http://www.cs.virginia.edu/~gfx/Courses/2006/DataDriven/bib/texsyn/Chapter11.pdf + w = dtmc(P); # steady state probability vector W = repmat(w,N,1); + ## Z = (I - P + W)^-1 where W is the matrix where each row is the + ## steady-state probability vector for P Z = inv(eye(N)-P+W); + ## m_ij = (z_jj - z_ij) / w_j result = (repmat(diag(Z)',N,1) - Z) ./ repmat(w,N,1) + diag(1./w); -#{ - if ( nargin == 1 ) - M = zeros(N,N); - ## M(i,j) = 1 + sum_{k \neq j} P(i,k) M(k,j) - b = ones(N,1); - for j=1:N - A = -P; - A(:,j) = 0; - A += eye(N,N); - res = A \ b; - M(:,j) = res'; - endfor - result = M; - else - (isscalar(i) && i>=1 && j<=N) || \ - usage("i must be an integer in the range [1,%d]", N); - (isvector(j) && all(j>=1) && all(j<=N)) || \ - usage("j must be an integer or vector with elements in [1,%d]", N); - j = j(:)'; # make j a row vector - b = ones(N,1); - A = -P; - A(:,j) = 0; - A += eye(N,N); - res = A \ b; - result = res(i); - endif -#} - endfunction %!test %! P = [1 1 1; 1 1 1];
--- a/main/queueing/inst/dtmc_mtta.m Sun Mar 18 15:21:33 2012 +0000 +++ b/main/queueing/inst/dtmc_mtta.m Sun Mar 18 15:35:02 2012 +0000 @@ -17,59 +17,70 @@ ## -*- texinfo -*- ## -## @deftypefn {Function File} {[@var{t} @var{B}] =} dtmc_mtta (@var{P}) -## @deftypefnx {Function File} {[@var{t} @var{B}] =} dtmc_mtta (@var{P}, @var{p0}) +## @deftypefn {Function File} {[@var{t} @var{N} @var{B}] =} dtmc_mtta (@var{P}) +## @deftypefnx {Function File} {[@var{t} @var{N} @var{B}] =} dtmc_mtta (@var{P}, @var{p0}) ## -## @cindex Markov chain, disctete time ## @cindex Mean time to absorption ## @cindex Absorption probabilities +## @cindex Fundamental matrix ## -## Compute the expected number of steps before absorption for the -## DTMC with @math{N \times N} transition probability matrix @var{P}. +## Compute the expected number of steps before absorption for a +## DTMC with @math{N \times N} transition probability matrix @var{P}; +## compute also the fundamental matrix @var{N} for @var{P}. ## ## @strong{INPUTS} ## ## @table @var ## ## @item P -## Transition probability matrix. -## -## @item p0 -## Initial state occupancy probabilities. +## @math{N \times N} transition probability matrix. ## ## @end table ## -## @strong{OUTPUTS} +## @strong{OUTPUTS} ## ## @table @var ## ## @item t -## When called with a single argument, @var{t} is a vector such that -## @code{@var{t}(i)} is the expected number of steps before being -## absorbed, starting from state @math{i}. When called with two -## arguments, @var{t} is a scalar and represents the average number of -## steps before absorption, given initial state occupancy probabilities -## @var{p0}. +## When called with a single argument, @var{t} is a vector of size +## @math{N} such that @code{@var{t}(i)} is the expected number of steps +## before being absorbed in any absorbing state, starting from state +## @math{i}; if @math{i} is absorbing, @code{@var{t}(i) = 0}. When +## called with two arguments, @var{t} is a scalar, and represents the +## expected number of steps before absorption, starting from the initial +## state occupancy probability @var{p0}. +## +## @item N +## When called with a single argument, @var{N} is the @math{N \times N} +## fundamental matrix for @var{P}. @code{@var{N}(i,j)} is the expected +## number of visits to transient state @var{j} before absorption, if it +## is started in transient state @var{i}. The initial state is counted +## if @math{i = j}. When called with two arguments, @var{N} is a vector +## of size @math{N} such that @code{@var{N}(j)} is the expected number +## of visits to transient state @var{j} before absorption, given initial +## state occupancy probability @var{P0}. ## ## @item B ## When called with a single argument, @var{B} is a @math{N \times N} ## matrix where @code{@var{B}(i,j)} is the probability of being absorbed ## in state @math{j}, starting from transient state @math{i}; if -## @math{j} is not absorbing, @code{@var{B}(i,j) = 0}; if @math{i} is -## absorbing, then @code{@var{B}(i,i) = 1}. -## When called with two arguments, @var{B} is a -## vector with @math{N} elements where @code{@var{B}(j)} is the -## probability of being absorbed in state @var{j}, given initial state -## occupancy probabilities @var{p0}. +## @math{j} is not absorbing, @code{@var{B}(i,j) = 0}; if @math{i} +## is absorbing, @code{@var{B}(i,i) = 1} and +## @code{@var{B}(i,j) = 0} for all @math{j \neq j}. When called with +## two arguments, @var{B} is a vector of size @math{N} where +## @code{@var{B}(j)} is the probability of being absorbed in state +## @var{j}, given initial state occupancy probabilities @var{p0}. ## ## @end table ## +## @seealso{ctmc_mtta} +## ## @end deftypefn ## Author: Moreno Marzolla <marzolla(at)cs.unibo.it> ## Web: http://www.moreno.marzolla.name/ -function [t B] = dtmc_mtta( P, p0 ) +function [t N B] = dtmc_mtta( P, p0 ) persistent epsilon = 10*eps; @@ -87,7 +98,6 @@ usage( "p0 must be a state occupancy probability vector" ); endif - ## identify transient states tr = find(diag(P) < 1); ab = find(diag(P) == 1); @@ -96,32 +106,42 @@ error("There are no absorbing states"); endif + N = B = zeros(size(P)); + t = zeros(1,rows(P)); + ## Source: Grinstead, Charles M.; Snell, J. Laurie (July 1997). "Ch. ## 11: Markov Chains". Introduction to Probability. American ## Mathematical Society. ISBN 978-0821807491. ## http://www.cs.virginia.edu/~gfx/Courses/2006/DataDriven/bib/texsyn/Chapter11.pdf - - N = (eye(k) - P(tr,tr)); + tmpN = inv(eye(k) - P(tr,tr)); # matrix N = (I-Q)^-1 + N(tr,tr) = tmpN; R = P(tr,ab); - res = N \ ones(k,1); - t = zeros(1,rows(P)); + res = tmpN * ones(k,1); t(tr) = res; - tmp = N \ R; - B = zeros(size(P)); + tmp = tmpN*R; B(tr,ab) = tmp; - B(ab,ab) = 1; + ## set B(i,i) = 1 for all absorbing states i + dd = diag(B); + dd(ab) = 1; + B(1:K+1:end) = dd; if ( nargin == 2 ) - t = dot(t,p0); + t = dot(p0,t); + N = p0*N; B = p0*B; endif + endfunction %!test +%! fail( "dtmc_mtta(1,2,3)" ); +%! fail( "dtmc_mtta()" ); + +%!test %! P = dtmc_bd([0 .5 .5 .5], [.5 .5 .5 0]); -%! [t B] = dtmc_mtta(P); +%! [t N B] = dtmc_mtta(P); %! assert( t, [0 3 4 3 0], 10*eps ); %! assert( B([2 3 4],[1 5]), [3/4 1/4; 1/2 1/2; 1/4 3/4], 10*eps ); %! assert( B(1,1), 1 ); @@ -129,17 +149,17 @@ %!test %! P = dtmc_bd([0 .5 .5 .5], [.5 .5 .5 0]); -%! [t B] = dtmc_mtta(P, [0 0 1 0 0]); -%! assert( t, 4, 10*eps ); -%! assert( B(1), 0.5, 10*eps ); -%! assert( B(5), 0.5, 10*eps ); +%! [t N B] = dtmc_mtta(P); +%! assert( t(3), 4, 10*eps ); +%! assert( B(3,1), 0.5, 10*eps ); +%! assert( B(3,5), 0.5, 10*eps ); ## Example on p. 422 of ## http://www.cs.virginia.edu/~gfx/Courses/2006/DataDriven/bib/texsyn/Chapter11.pdf %!test %! P = dtmc_bd([0 .5 .5 .5 .5], [.5 .5 .5 .5 0]); -%! [t B] = dtmc_mtta(P); -%! assert( t, [0 4 6 6 4 0], 10*eps ); +%! [t N B] = dtmc_mtta(P); +%! assert( t(2:5), [4 6 6 4], 10*eps ); %! assert( B(2:5,1), [.8 .6 .4 .2]', 10*eps ); %! assert( B(2:5,6), [.2 .4 .6 .8]', 10*eps ); @@ -198,15 +218,15 @@ %! # spy(Pstar); pause %! nsteps = 250; # number of steps %! Pfinish = zeros(1,nsteps); # Pfinish(i) = probability of finishing after step i -%! start = zeros(1,101); start(1) = 1; +%! pstart = zeros(1,101); pstart(1) = 1; pn = pstart; %! for i=1:nsteps -%! pn = dtmc(Pstar,i,start); +%! pn = pn*Pstar; %! Pfinish(i) = pn(101); # state 101 is the ending (absorbing) state %! endfor -%! f = dtmc_mtta(Pstar, start); +%! f = dtmc_mtta(Pstar,pstart); %! printf("Average number of steps to complete the game: %f\n", f ); %! plot(Pfinish,"linewidth",2); %! line([f,f],[0,1]); -%! text(f*1.1,0.2,"Mean Time to Absorption"); +%! text(f*1.1,0.2,["Mean Time to Absorption (" num2str(f) ")"]); %! xlabel("Step number (n)"); %! title("Probability of finishing the game before step n");
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/queueing/inst/dtmc_taexps.m Sun Mar 18 15:35:02 2012 +0000 @@ -0,0 +1,84 @@ +## Copyright (C) 2012 Moreno Marzolla +## +## This file is part of the queueing toolbox. +## +## The queueing toolbox is free software: you can redistribute it and/or +## modify it under the terms of the GNU General Public License as +## published by the Free Software Foundation, either version 3 of the +## License, or (at your option) any later version. +## +## The queueing toolbox is distributed in the hope that it will be +## useful, but WITHOUT ANY WARRANTY; without even the implied warranty +## of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +## General Public License for more details. +## +## You should have received a copy of the GNU General Public License +## along with the queueing toolbox. If not, see <http://www.gnu.org/licenses/>. + +## -*- texinfo -*- +## +## @deftypefn {Function File} {@var{L} =} dtmc_exps (@var{P}, @var{n}, @var{p0}) +## @deftypefnx {Function File} {@var{L} =} dtmc_exps (@var{P}, @var{p0}) +## +## @cindex Time-alveraged sojourn time +## +## Compute the @emph{time-averaged sojourn time} @code{@var{M}(i)}, +## defined as the fraction of time steps @math{@{0, 1, @dots{}, n@}} (or +## until absorption) spent in state @math{i}, assuming that the state +## occupancy probabilities at time 0 are @var{p0}. +## +## @strong{INPUTS} +## +## @table @var +## +## @item Q +## Infinitesimal generator matrix. @code{@var{Q}(i,j)} is the transition +## rate from state @math{i} to state @math{j}, +## @math{1 @leq{} i \neq j @leq{} N}. The +## matrix @var{Q} must also satisfy the condition @math{\sum_{j=1}^N Q_{ij} = 0} +## +## @item t +## Time. If omitted, the results are computed until absorption. +## +## @item p +## @code{@var{p}(i)} is the probability that, at time 0, the system was in +## state @math{i}, for all @math{i = 1, @dots{}, N} +## +## @end table +## +## @strong{OUTPUTS} +## +## @table @var +## +## @item M +## If this function is called with three arguments, @code{@var{M}(i)} +## is the expected fraction of the interval @math{[0,t]} spent in state +## @math{i} assuming that the state occupancy probability at time zero +## is @var{p}. If this function is called with two arguments, +## @code{@var{M}(i)} is the expected fraction of time until absorption +## spent in state @math{i}. +## +## @end table +## +## @end deftypefn + +## Author: Moreno Marzolla <marzolla(at)cs.unibo.it> +## Web: http://www.moreno.marzolla.name/ + +function M = dtmc_taexps( P, varargin ) + + persistent epsilon = 10*eps; + + if ( nargin < 2 || nargin > 3 ) + print_usage(); + endif + + L = dtmc_exps(P,varargin{:}); + M = L ./ sum(L); +endfunction +%!test +%! P = dtmc_bd([1 1 1 1], [0 0 0 0]); +%! p0 = [1 0 0 0 0]; +%! L = dtmc_taexps(P,p0); +%! assert( L, [.25 .25 .25 .25 0], 10*eps ); +