Mercurial > forge
changeset 9983:d5ff0e54d7e7 octave-forge
documentation restructuring
| author | mmarzolla |
|---|---|
| date | Fri, 06 Apr 2012 16:12:18 +0000 |
| parents | 4054cabceb89 |
| children | f1ba108476f9 |
| files | main/queueing/doc/Makefile main/queueing/doc/markovchains.texi main/queueing/doc/markovchains.txi main/queueing/doc/queueing.html main/queueing/doc/queueing.pdf main/queueing/doc/singlestation.texi main/queueing/doc/singlestation.txi |
| diffstat | 7 files changed, 1409 insertions(+), 1069 deletions(-) [+] |
line wrap: on
line diff
--- a/main/queueing/doc/Makefile Fri Apr 06 16:06:56 2012 +0000 +++ b/main/queueing/doc/Makefile Fri Apr 06 16:12:18 2012 +0000 @@ -38,7 +38,7 @@ ln $(DISTFILES) ../`cat ../fname`/doc/ clean: - \rm -f *.fns *.pdf *.aux *.log *.dvi *.out *.info *.html *.ky *.tp *.toc *.vr *.cp *.fn *.pg *.op *.au *.aus *.cps x.log *~ demos/*.texi help/*.texi DOCSTRINGS DEMOS HELP $(CHAPTERS) INSTALL + \rm -f *.fns *.pdf *.aux *.log *.dvi *.out *.info *.html *.ky *.tp *.toc *.vr *.cp *.fn *.pg *.op *.au *.aus *.cps x.log *~ demos/*.texi help/*.texi DOCSTRINGS DEMOS HELP INSTALL distclean: clean
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/queueing/doc/markovchains.texi Fri Apr 06 16:12:18 2012 +0000 @@ -0,0 +1,697 @@ +@c -*- texinfo -*- + +@c Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla +@c +@c This file is part of the queueing toolbox, a Queueing Networks +@c analysis package for GNU Octave. +@c +@c The queueing toolbox is free software; you can redistribute it +@c and/or modify it under the terms of the GNU General Public License +@c as published by the Free Software Foundation; either version 3 of +@c the License, or (at your option) any later version. +@c +@c The queueing toolbox is distributed in the hope that it will be +@c useful, but WITHOUT ANY WARRANTY; without even the implied warranty +@c of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +@c GNU General Public License for more details. +@c +@c You should have received a copy of the GNU General Public License +@c along with the queueing toolbox; see the file COPYING. If not, see +@c <http://www.gnu.org/licenses/>. + +@node Markov Chains +@chapter Markov Chains + +@menu +* Discrete-Time Markov Chains:: +* Continuous-Time Markov Chains:: +@end menu + +@node Discrete-Time Markov Chains +@section Discrete-Time Markov Chains + +Let @math{X_0, X_1, @dots{}, X_n, @dots{} } be a sequence of random +variables defined over a discete state space @math{0, 1, 2, +@dots{}}. The sequence @math{X_0, X_1, @dots{}, X_n, @dots{}} is a +@emph{stochastic process} with discrete time @math{0, 1, 2, +@dots{}}. A @emph{Markov chain} is a stochastic process @math{@{X_n, +n=0, 1, 2, @dots{}@}} which satisfies the following Markov property: + +@iftex +@tex +$$\eqalign{P\left(X_{n+1} = x_{n+1}\ |\ X_n = x_n, X_{n-1} = x_{n-1}, \ldots, X_0 = x_0 \right) \cr +& = P\left(X_{n+1} = x_{n+1}\ |\ X_n = x_n\right)}$$ +@end tex +@end iftex +@ifnottex +@math{P(X_{n+1} = x_{n+1} | X_n = x_n, X_{n-1} = x_{n-1}, ..., X_0 = x_0) = P(X_{n+1} = x_{n+1} | X_n = x_n)} +@end ifnottex + +@noindent which basically means that the probability that the system is in +a particular state at time @math{n+1} only depends on the state the +system was at time @math{n}. + +The evolution of a Markov chain with finite state space @math{@{1, 2, +@dots{}, N@}} can be fully described by a stochastic matrix @math{{\bf +P}(n) = [ P_{i,j}(n) ]} such that @math{P_{i, j}(n) = P( X_{n+1} = j\ +|\ X_n = i )}. If the Markov chain is homogeneous (that is, the +transition probability matrix @math{{\bf P}(n)} is time-independent), +we can write @math{{\bf P} = [P_{i, j}]}, where @math{P_{i, j} = P( +X_{n+1} = j\ |\ X_n = i )} for all @math{n=0, 1, @dots{}}. + +The transition probability matrix @math{\bf P} must satisfy the +following two properties: (1) @math{P_{i, j} @geq{} 0} for all +@math{i, j}, and (2) @math{\sum_{j=1}^N P_{i,j} = 1} for all @math{i} + +@c +@include help/dtmc_check_P.texi + +@menu +* State occupancy probabilities (DTMC):: +* Birth-death process (DTMC):: +* Expected number of visits (DTMC):: +* Time-averaged expected sojourn times (DTMC):: +* Mean time to absorption (DTMC):: +* First passage times (DTMC):: +@end menu + +@c +@c +@c +@node State occupancy probabilities (DTMC) +@subsection State occupancy probabilities + +We denote with @math{{\bf \pi}(n) = \left(\pi_1(n), \pi_2(n), @dots{}, +\pi_N(n) \right)} the @emph{state occupancy probability vector} at +step @math{n}. @math{\pi_i(n)} denotes the probability that the system +is in state @math{i} after @math{n} transitions. + +Given the transition probability matrix @math{\bf P} and the initial +state occupancy probability vector @math{{\bf \pi}(0) = +\left(\pi_1(0), \pi_2(0), @dots{}, \pi_N(0)\right)}, @math{{\bf +\pi}(n)} can be computed as: + +@iftex +@tex +$${\bf \pi}(n) = {\bf \pi}(0) {\bf P}^n$$ +@end tex +@end iftex +@ifnottex +@example +@group +\pi(n) = \pi(0) P^n +@end group +@end example +@end ifnottex + +Under certain conditions, there exists a @emph{stationary state +occupancy probability} @math{{\bf \pi} = \lim_{n \rightarrow +\infty} +{\bf \pi}(n)}, which is independent from @math{{\bf \pi}(0)}. The +stationary vector @math{\bf \pi} is the solution of the following +linear system: + +@iftex +@tex +$$ +\left\{ \eqalign{ +{\bf \pi P} & = {\bf \pi} \cr +{\bf \pi 1}^T & = 1 +} \right. +$$ +@end tex +@end iftex +@ifnottex +@example +@group +/ +| \pi P = \pi +| \pi 1^T = 1 +\ +@end group +@end example +@end ifnottex + +@noindent where @math{\bf 1} is the row vector of ones, and @math{( \cdot )^T} +the transpose operator. + +@c +@include help/dtmc.texi + +@noindent @strong{EXAMPLE} + +This example is from [GrSn97]. Let us consider a maze with nine rooms, +as shown in the following figure + +@example +@group ++-----+-----+-----+ +| | | | +| 1 2 3 | +| | | | ++- -+- -+- -+ +| | | | +| 4 5 6 | +| | | | ++- -+- -+- -+ +| | | | +| 7 8 9 | +| | | | ++-----+-----+-----+ +@end group +@end example + +A mouse is placed in one of the rooms and can wander around. At each +step, the mouse moves from the current room to a neighboring one with +equal probability: if it is in room 1, it can move to room 2 and 4 +with probability 1/2, respectively. If the mouse is in room 8, it can +move to either 7, 5 or 9 with probability 1/3. + +The transition probability @math{\bf P} from room @math{i} to room +@math{j} is the following: + +@iftex +@tex +$$ {\bf P} = +\pmatrix{ 0 & 1/2 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 \cr + 1/3 & 0 & 1/3 & 0 & 1/3 & 0 & 0 & 0 & 0 \cr + 0 & 1/2 & 0 & 0 & 0 & 1/2 & 0 & 0 & 0 \cr + 1/3 & 0 & 0 & 0 & 1/3 & 0 & 1/3 & 0 & 0 \cr + 0 & 1/4 & 0 & 1/4 & 0 & 1/4 & 0 & 1/4 & 0 \cr + 0 & 0 & 1/3 & 0 & 1/3 & 0 & 0 & 0 & 1/3 \cr + 0 & 0 & 0 & 1/2 & 0 & 0 & 0 & 1/2 & 0 \cr + 0 & 0 & 0 & 0 & 1/3 & 0 & 1/3 & 0 & 1/3 \cr + 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0 } +$$ +@end tex +@end iftex +@ifnottex +@example +@group + / 0 1/2 0 1/2 0 0 0 0 0 \ + | 1/3 0 1/3 0 1/3 0 0 0 0 | + | 0 1/2 0 0 0 1/2 0 0 0 | + | 1/3 0 0 0 1/3 0 1/3 0 0 | + P = | 0 1/4 0 1/4 0 1/4 0 1/4 0 | + | 0 0 1/3 0 1/3 0 0 0 1/3 | + | 0 0 0 1/2 0 0 0 1/2 0 | + | 0 0 0 0 1/3 0 1/3 0 1/3 | + \ 0 0 0 0 0 1/2 0 1/2 0 / +@end group +@end example +@end ifnottex + +The stationary state occupancy probability vector can be computed +using the following code: + +@example +@c @group +@include demos/demo_1_dtmc.texi +@c @end group + @result{} 0.083333 0.125000 0.083333 0.125000 + 0.166667 0.125000 0.083333 0.125000 + 0.083333 +@end example + +@c +@node Birth-death process (DTMC) +@subsection Birth-death process + +@include help/dtmc_bd.texi + +@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, i.e., the stochastic process eventually +reaches a state with no outgoing transitions with probability 1, then +we can compute the expected number of visits until absorption +@math{\bf L}. To do so, we first rearrange the states to rewrite +matrix @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 the first @math{t} states are transient +and the last @math{r} states are absorbing (@math{t+r = N}). The +matrix @math{{\bf N} = ({\bf I} - {\bf Q})^{-1}} is called the +@emph{fundamental matrix}; @math{N_{i,j}} is the expected number of +times that the process is in the @math{j}-th transient state if it +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 absorbing chains @math{{\bf L} = {\bf \pi}(0){\bf N}}. + +@include help/dtmc_exps.texi + +@c +@node Time-averaged expected sojourn times (DTMC) +@subsection Time-averaged expected sojourn times + +@include help/dtmc_taexps.texi + +@c +@node Mean time to absorption (DTMC) +@subsection Mean Time to Absorption + +The @emph{mean time to absorption} is defined as the average number of +transitions which are required to reach an absorbing state, starting +from a transient state (or given an initial state occupancy +probability vector @math{{\bf \pi}(0)}). + +Let @math{{\bf t}_i} be the expected number of transitions before +being absorbed in any absorbing state, starting from state @math{i}. +Vector @math{\bf t} can be computed from the fundamental matrix +@math{\bf N} (@pxref{Expected number of visits (DTMC)}) as + +@iftex +@tex +$$ {\bf t} = {\bf 1 N} $$ +@end tex +@end iftex +@ifnottex +@example +t = 1 N +@end example +@end ifnottex + +Let @math{{\bf B} = [ B_{i, j} ]} be a matrix where @math{B_{i, j}} is +the probability of being absorbed in state @math{j}, starting from +transient state @math{i}. Again, using matrices @math{\bf N} and +@math{\bf R} (@pxref{Expected number of visits (DTMC)}) we can write + +@iftex +@tex +$$ {\bf B} = {\bf N R} $$ +@end tex +@end iftex +@ifnottex +@example +B = N R +@end example +@end ifnottex + +@include help/dtmc_mtta.texi + +@c +@node First passage times (DTMC) +@subsection First Passage Times + +The First Passage Time @math{M_{i, j}} is the average number of +transitions needed to visit state @math{j} for the first time, +starting from state @math{i}. Matrix @math{\bf M} satisfies the +property that + +@iftex +@tex +$$ M_{i, j} = 1 + \sum_{k \neq j} P_{i, k} M_{k, j}$$ +@end tex +@end iftex +@ifnottex +@example +@group + ___ + \ +M_ij = 1 + > P_ij * M_kj + /___ + k!=j +@end group +@end example +@end ifnottex + +To compute @math{{\bf M} = [ M_{i, j}]} a different formulation is +used. Let @math{\bf W} be the @math{N \times N} matrix having each +row equal to the steady-state probability vector @math{\bf \pi} for +@math{\bf P}; let @math{\bf I} be the @math{N \times N} identity +matrix. Define @math{\bf Z} as follows: + +@iftex +@tex +$$ {\bf Z} = \left( {\bf I} - {\bf P} + {\bf W} \right)^{-1} $$ +@end tex +@end iftex +@ifnottex +@example +@group + -1 +Z = (I - P + W) +@end group +@end example +@end ifnottex + +@noindent Then, we have that + +@iftex +@tex +$$ M_{i, j} = {Z_{j, j} - Z_{i, j} \over \pi_j} $$ +@end tex +@end iftex +@ifnottex +@example +@group + Z_jj - Z_ij +M_ij = ----------- + \pi_j +@end group +@end example +@end ifnottex + +According to the definition above, @math{M_{i,i} = 0}. We arbitrarily +let @math{M_{i,i}} to be the @emph{mean recurrence time} @math{r_i} +for state @math{i}, that is the average number of transitions needed +to return to state @math{i} starting from it. @math{r_i} is: + +@iftex +@tex +$$ r_i = {1 \over \pi_i} $$ +@end tex +@end iftex +@ifnottex +@example +@group + 1 +r_i = ----- + \pi_i +@end group +@end example +@end ifnottex + +@include help/dtmc_fpt.texi + +@c +@c +@c +@node Continuous-Time Markov Chains +@section Continuous-Time Markov Chains + +A stochastic process @math{@{X(t), t @geq{} 0@}} is a continuous-time +Markov chain if, for all integers @math{n}, and for any sequence +@math{t_0, t_1 , \ldots, t_n, t_{n+1}} such that @math{t_0 < t_1 < +\ldots < t_n < t_{n+1}}, we have + +@iftex +@tex +$$\eqalign{P(X(t_{n+1}) = x_{n+1}\ |\ X(t_n) = x_n, X(t_{n-1}) = x_{n-1}, \ldots, X(t_0) = x_0) \cr +&= P(X(t_{n+1}) = x_{n+1}\ |\ X(t_n) = x_n)}$$ +@end tex +@end iftex +@ifnottex +@math{P(X_{n+1} = x_{n+1} | X_n = x_n, X_{n-1} = x_{n-1}, ..., X_0 = x_0) = P(X_{n+1} = x_{n+1} | X_n = x_n)} +@end ifnottex + +A continuous-time Markov chain is defined according to an +@emph{infinitesimal generator matrix} @math{{\bf Q} = [Q_{i,j}]}, +where for each @math{i \neq j}, @math{Q_{i, j}} is the transition rate +from state @math{i} to state @math{j}. The matrix @math{\bf Q} must +satisfy the property that, for all @math{i}, @math{\sum_{j=1}^N Q_{i, +j} = 0}. + +@include help/ctmc_check_Q.texi + +@menu +* State occupancy probabilities (CTMC):: +* Birth-death process (CTMC):: +* Expected sojourn times (CTMC):: +* Time-averaged expected sojourn times (CTMC):: +* Mean time to absorption (CTMC):: +* First passage times (CTMC):: +@end menu + +@node State occupancy probabilities (CTMC) +@subsection State occupancy probabilities + +Similarly to the discrete case, we denote with @math{{\bf \pi}(t) = +(\pi_1(t), \pi_2(t), @dots{}, \pi_N(t) )} the @emph{state occupancy +probability vector} at time @math{t}. @math{\pi_i(t)} is the +probability that the system is in state @math{i} at time @math{t +@geq{} 0}. + +Given the infinitesimal generator matrix @math{\bf Q} and the initial +state occupancy probabilities @math{{\bf \pi}(0) = (\pi_1(0), +\pi_2(0), @dots{}, \pi_N(0))}, the state occupancy probabilities +@math{{\bf \pi}(t)} at time @math{t} can be computed as: + +@iftex +@tex +$${\bf \pi}(t) = {\bf \pi}(0) \exp( {\bf Q} t )$$ +@end tex +@end iftex +@ifnottex +@example +@group +\pi(t) = \pi(0) exp(Qt) +@end group +@end example +@end ifnottex + +@noindent where @math{\exp( {\bf Q} t )} is the matrix exponential +of @math{{\bf Q} t}. Under certain conditions, there exists a +@emph{stationary state occupancy probability} @math{{\bf \pi} = +\lim_{t \rightarrow +\infty} {\bf \pi}(t)}, which is independent from +@math{{\bf \pi}(0)}. @math{\bf \pi} is the solution of the following +linear system: + +@iftex +@tex +$$ +\left\{ \eqalign{ +{\bf \pi Q} & = {\bf 0} \cr +{\bf \pi 1}^T & = 1 +} \right. +$$ +@end tex +@end iftex +@ifnottex +@example +@group +/ +| \pi Q = 0 +| \pi 1^T = 1 +\ +@end group +@end example +@end ifnottex + +@include help/ctmc.texi + +@noindent @strong{EXAMPLE} + +Consider a two-state CTMC such that transition rates between states +are equal to 1. This can be solved as follows: + +@example +@group +@include demos/demo_1_ctmc.texi + @result{} q = 0.50000 0.50000 +@end group +@end example + +@c +@c +@c +@node Birth-death process (CTMC) +@subsection Birth-Death Process + +@include help/ctmc_bd.texi + +@c +@c +@c +@node Expected sojourn times (CTMC) +@subsection Expected Sojourn Times + +Given a @math{N} state continuous-time Markov Chain with infinitesimal +generator matrix @math{\bf Q}, we define the vector @math{{\bf L}(t) = +(L_1(t), L_2(t), \ldots, L_N(t))} such that @math{L_i(t)} is the +expected sojourn time in state @math{i} during the interval +@math{[0,t)}, assuming that the initial occupancy probability at time +0 was @math{{\bf \pi}(0)}. @math{{\bf L}(t)} can be expressed as the +solution of the following differential equation: + +@iftex +@tex +$$ { d{\bf L}(t) \over dt} = {\bf L}(t){\bf Q} + {\bf \pi}(0), \qquad {\bf L}(0) = {\bf 0} $$ +@end tex +@end iftex +@ifnottex +@example +@group + dL + --(t) = L(t) Q + pi(0), L(0) = 0 + dt +@end group +@end example +@end ifnottex + +Alternatively, @math{{\bf L}(t)} can also be expressed in integral +form as: + +@iftex +@tex +$$ {\bf L}(t) = \int_0^t {\bf \pi}(u) du$$ +@end tex +@end iftex +@ifnottex +@example +@group + / t +L(t) = | pi(u) du + / 0 +@end group +@end example +@end ifnottex + +@noindent where @math{{\bf \pi}(t) = {\bf \pi}(0) \exp({\bf Q}t)} is +the state occupancy probability at time @math{t}; @math{\exp({\bf Q}t)} +is the matrix exponential of @math{{\bf Q}t}. + +@include help/ctmc_exps.texi + +@noindent @strong{EXAMPLE} + +Let us consider a pure-birth, 4-states CTMC such that the transition +rate from state @math{i} to state @math{i+1} is @math{\lambda_i = i +\lambda} (@math{i=1, 2, 3}), with @math{\lambda = 0.5}. The following +code computes the expected sojourn time in state @math{i}, +given the initial occupancy probability @math{{\bf \pi}_0=(1,0,0,0)}. + +@example +@group +@include demos/demo_1_ctmc_exps.texi +@end group +@end example + +@c +@c +@c +@node Time-averaged expected sojourn times (CTMC) +@subsection Time-Averaged Expected Sojourn Times + +@include help/ctmc_taexps.texi + +@noindent @strong{EXAMPLE} + +@example +@group +@include demos/demo_1_ctmc_taexps.texi +@end group +@end example + +@c +@c +@c +@node Mean time to absorption (CTMC) +@subsection Mean Time to Absorption + +If we consider a Markov Chain with absorbing states, it is possible to +define the @emph{expected time to absorption} as the expected time +until the system goes into an absorbing state. More specifically, let +us suppose that @math{A} is the set of transient (i.e., non-absorbing) +states of a CTMC with @math{N} states and infinitesimal generator +matrix @math{\bf Q}. The expected time to absorption @math{{\bf +L}_A(\infty)} is defined as the solution of the following equation: + +@iftex +@tex +$$ {\bf L}_A(\infty){\bf Q}_A = -{\bf \pi}_A(0) $$ +@end tex +@end iftex +@ifnottex +@example +@group +L_A( inf ) Q_A = -pi_A(0) +@end group +@end example +@end ifnottex + +@noindent where @math{{\bf Q}_A} is the restriction of matrix @math{\bf Q} to +only states in @math{A}, and @math{{\bf \pi}_A(0)} is the initial +state occupancy probability at time 0, restricted to states in +@math{A}. + +@include help/ctmc_mtta.texi + +@noindent @strong{EXAMPLE} + +Let us consider a simple model of a redundant disk array. We assume +that the array is made of 5 independent disks, such that the array can +tolerate up to 2 disk failures without losing data. If three or more +disks break, the array is dead and unrecoverable. We want to estimate +the Mean-Time-To-Failure (MTTF) of the disk array. + +We model this system as a 4 states Markov chain with state space +@math{\{ 2, 3, 4, 5 \}}. State @math{i} denotes the fact that exactly +@math{i} disks are active; state @math{2} is absorbing. Let @math{\mu} +be the failure rate of a single disk. The system starts in state +@math{5} (all disks are operational). We use a pure death process, +with death rate from state @math{i} to state @math{i-1} is @math{\mu +i}, for @math{i = 3, 4, 5}). + +The MTTF of the disk array is the MTTA of the Markov Chain, and can be +computed with the following expression: + +@example +@group +@include demos/demo_1_ctmc_mtta.texi + @result{} t = 78.333 +@end group +@end example + +@noindent @strong{REFERENCES} + +G. Bolch, S. Greiner, H. de Meer and +K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and +Performance Evaluation with Computer Science Applications}, Wiley, +1998. + +@auindex Bolch, G. +@auindex Greiner, S. +@auindex de Meer, H. +@auindex Trivedi, K. + +@c +@c +@c +@node First passage times (CTMC) +@subsection First Passage Times + +@include help/ctmc_fpt.texi +
--- a/main/queueing/doc/markovchains.txi Fri Apr 06 16:06:56 2012 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,697 +0,0 @@ -@c -*- texinfo -*- - -@c Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla -@c -@c This file is part of the queueing toolbox, a Queueing Networks -@c analysis package for GNU Octave. -@c -@c The queueing toolbox is free software; you can redistribute it -@c and/or modify it under the terms of the GNU General Public License -@c as published by the Free Software Foundation; either version 3 of -@c the License, or (at your option) any later version. -@c -@c The queueing toolbox is distributed in the hope that it will be -@c useful, but WITHOUT ANY WARRANTY; without even the implied warranty -@c of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -@c GNU General Public License for more details. -@c -@c You should have received a copy of the GNU General Public License -@c along with the queueing toolbox; see the file COPYING. If not, see -@c <http://www.gnu.org/licenses/>. - -@node Markov Chains -@chapter Markov Chains - -@menu -* Discrete-Time Markov Chains:: -* Continuous-Time Markov Chains:: -@end menu - -@node Discrete-Time Markov Chains -@section Discrete-Time Markov Chains - -Let @math{X_0, X_1, @dots{}, X_n, @dots{} } be a sequence of random -variables defined over a discete state space @math{0, 1, 2, -@dots{}}. The sequence @math{X_0, X_1, @dots{}, X_n, @dots{}} is a -@emph{stochastic process} with discrete time @math{0, 1, 2, -@dots{}}. A @emph{Markov chain} is a stochastic process @math{@{X_n, -n=0, 1, 2, @dots{}@}} which satisfies the following Markov property: - -@iftex -@tex -$$\eqalign{P\left(X_{n+1} = x_{n+1}\ |\ X_n = x_n, X_{n-1} = x_{n-1}, \ldots, X_0 = x_0 \right) \cr -& = P\left(X_{n+1} = x_{n+1}\ |\ X_n = x_n\right)}$$ -@end tex -@end iftex -@ifnottex -@math{P(X_{n+1} = x_{n+1} | X_n = x_n, X_{n-1} = x_{n-1}, ..., X_0 = x_0) = P(X_{n+1} = x_{n+1} | X_n = x_n)} -@end ifnottex - -@noindent which basically means that the probability that the system is in -a particular state at time @math{n+1} only depends on the state the -system was at time @math{n}. - -The evolution of a Markov chain with finite state space @math{@{1, 2, -@dots{}, N@}} can be fully described by a stochastic matrix @math{{\bf -P}(n) = [ P_{i,j}(n) ]} such that @math{P_{i, j}(n) = P( X_{n+1} = j\ -|\ X_n = i )}. If the Markov chain is homogeneous (that is, the -transition probability matrix @math{{\bf P}(n)} is time-independent), -we can write @math{{\bf P} = [P_{i, j}]}, where @math{P_{i, j} = P( -X_{n+1} = j\ |\ X_n = i )} for all @math{n=0, 1, @dots{}}. - -The transition probability matrix @math{\bf P} must satisfy the -following two properties: (1) @math{P_{i, j} @geq{} 0} for all -@math{i, j}, and (2) @math{\sum_{j=1}^N P_{i,j} = 1} for all @math{i} - -@c -@include help/dtmc_check_P.texi - -@menu -* State occupancy probabilities (DTMC):: -* Birth-death process (DTMC):: -* Expected number of visits (DTMC):: -* Time-averaged expected sojourn times (DTMC):: -* Mean time to absorption (DTMC):: -* First passage times (DTMC):: -@end menu - -@c -@c -@c -@node State occupancy probabilities (DTMC) -@subsection State occupancy probabilities - -We denote with @math{{\bf \pi}(n) = \left(\pi_1(n), \pi_2(n), @dots{}, -\pi_N(n) \right)} the @emph{state occupancy probability vector} at -step @math{n}. @math{\pi_i(n)} denotes the probability that the system -is in state @math{i} after @math{n} transitions. - -Given the transition probability matrix @math{\bf P} and the initial -state occupancy probability vector @math{{\bf \pi}(0) = -\left(\pi_1(0), \pi_2(0), @dots{}, \pi_N(0)\right)}, @math{{\bf -\pi}(n)} can be computed as: - -@iftex -@tex -$${\bf \pi}(n) = {\bf \pi}(0) {\bf P}^n$$ -@end tex -@end iftex -@ifnottex -@example -@group -\pi(n) = \pi(0) P^n -@end group -@end example -@end ifnottex - -Under certain conditions, there exists a @emph{stationary state -occupancy probability} @math{{\bf \pi} = \lim_{n \rightarrow +\infty} -{\bf \pi}(n)}, which is independent from @math{{\bf \pi}(0)}. The -stationary vector @math{\bf \pi} is the solution of the following -linear system: - -@iftex -@tex -$$ -\left\{ \eqalign{ -{\bf \pi P} & = {\bf \pi} \cr -{\bf \pi 1}^T & = 1 -} \right. -$$ -@end tex -@end iftex -@ifnottex -@example -@group -/ -| \pi P = \pi -| \pi 1^T = 1 -\ -@end group -@end example -@end ifnottex - -@noindent where @math{\bf 1} is the row vector of ones, and @math{( \cdot )^T} -the transpose operator. - -@c -@include help/dtmc.texi - -@noindent @strong{EXAMPLE} - -This example is from [GrSn97]. Let us consider a maze with nine rooms, -as shown in the following figure - -@example -@group -+-----+-----+-----+ -| | | | -| 1 2 3 | -| | | | -+- -+- -+- -+ -| | | | -| 4 5 6 | -| | | | -+- -+- -+- -+ -| | | | -| 7 8 9 | -| | | | -+-----+-----+-----+ -@end group -@end example - -A mouse is placed in one of the rooms and can wander around. At each -step, the mouse moves from the current room to a neighboring one with -equal probability: if it is in room 1, it can move to room 2 and 4 -with probability 1/2, respectively. If the mouse is in room 8, it can -move to either 7, 5 or 9 with probability 1/3. - -The transition probability @math{\bf P} from room @math{i} to room -@math{j} is the following: - -@iftex -@tex -$$ {\bf P} = -\pmatrix{ 0 & 1/2 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 \cr - 1/3 & 0 & 1/3 & 0 & 1/3 & 0 & 0 & 0 & 0 \cr - 0 & 1/2 & 0 & 0 & 0 & 1/2 & 0 & 0 & 0 \cr - 1/3 & 0 & 0 & 0 & 1/3 & 0 & 1/3 & 0 & 0 \cr - 0 & 1/4 & 0 & 1/4 & 0 & 1/4 & 0 & 1/4 & 0 \cr - 0 & 0 & 1/3 & 0 & 1/3 & 0 & 0 & 0 & 1/3 \cr - 0 & 0 & 0 & 1/2 & 0 & 0 & 0 & 1/2 & 0 \cr - 0 & 0 & 0 & 0 & 1/3 & 0 & 1/3 & 0 & 1/3 \cr - 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0 } -$$ -@end tex -@end iftex -@ifnottex -@example -@group - / 0 1/2 0 1/2 0 0 0 0 0 \ - | 1/3 0 1/3 0 1/3 0 0 0 0 | - | 0 1/2 0 0 0 1/2 0 0 0 | - | 1/3 0 0 0 1/3 0 1/3 0 0 | - P = | 0 1/4 0 1/4 0 1/4 0 1/4 0 | - | 0 0 1/3 0 1/3 0 0 0 1/3 | - | 0 0 0 1/2 0 0 0 1/2 0 | - | 0 0 0 0 1/3 0 1/3 0 1/3 | - \ 0 0 0 0 0 1/2 0 1/2 0 / -@end group -@end example -@end ifnottex - -The stationary state occupancy probability vector can be computed -using the following code: - -@example -@c @group -@include demos/demo_1_dtmc.texi -@c @end group - @result{} 0.083333 0.125000 0.083333 0.125000 - 0.166667 0.125000 0.083333 0.125000 - 0.083333 -@end example - -@c -@node Birth-death process (DTMC) -@subsection Birth-death process - -@include help/dtmc_bd.texi - -@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, i.e., the stochastic process eventually -reaches a state with no outgoing transitions with probability 1, then -we can compute the expected number of visits until absorption -@math{\bf L}. To do so, we first rearrange the states to rewrite -matrix @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 the first @math{t} states are transient -and the last @math{r} states are absorbing (@math{t+r = N}). The -matrix @math{{\bf N} = ({\bf I} - {\bf Q})^{-1}} is called the -@emph{fundamental matrix}; @math{N_{i,j}} is the expected number of -times that the process is in the @math{j}-th transient state if it -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 absorbing chains @math{{\bf L} = {\bf \pi}(0){\bf N}}. - -@include help/dtmc_exps.texi - -@c -@node Time-averaged expected sojourn times (DTMC) -@subsection Time-averaged expected sojourn times - -@include help/dtmc_taexps.texi - -@c -@node Mean time to absorption (DTMC) -@subsection Mean Time to Absorption - -The @emph{mean time to absorption} is defined as the average number of -transitions which are required to reach an absorbing state, starting -from a transient state (or given an initial state occupancy -probability vector @math{{\bf \pi}(0)}). - -Let @math{{\bf t}_i} be the expected number of transitions before -being absorbed in any absorbing state, starting from state @math{i}. -Vector @math{\bf t} can be computed from the fundamental matrix -@math{\bf N} (@pxref{Expected number of visits (DTMC)}) as - -@iftex -@tex -$$ {\bf t} = {\bf 1 N} $$ -@end tex -@end iftex -@ifnottex -@example -t = 1 N -@end example -@end ifnottex - -Let @math{{\bf B} = [ B_{i, j} ]} be a matrix where @math{B_{i, j}} is -the probability of being absorbed in state @math{j}, starting from -transient state @math{i}. Again, using matrices @math{\bf N} and -@math{\bf R} (@pxref{Expected number of visits (DTMC)}) we can write - -@iftex -@tex -$$ {\bf B} = {\bf N R} $$ -@end tex -@end iftex -@ifnottex -@example -B = N R -@end example -@end ifnottex - -@include help/dtmc_mtta.texi - -@c -@node First passage times (DTMC) -@subsection First Passage Times - -The First Passage Time @math{M_{i, j}} is the average number of -transitions needed to visit state @math{j} for the first time, -starting from state @math{i}. Matrix @math{\bf M} satisfies the -property that - -@iftex -@tex -$$ M_{i, j} = 1 + \sum_{k \neq j} P_{i, k} M_{k, j}$$ -@end tex -@end iftex -@ifnottex -@example -@group - ___ - \ -M_ij = 1 + > P_ij * M_kj - /___ - k!=j -@end group -@end example -@end ifnottex - -To compute @math{{\bf M} = [ M_{i, j}]} a different formulation is -used. Let @math{\bf W} be the @math{N \times N} matrix having each -row equal to the steady-state probability vector @math{\bf \pi} for -@math{\bf P}; let @math{\bf I} be the @math{N \times N} identity -matrix. Define @math{\bf Z} as follows: - -@iftex -@tex -$$ {\bf Z} = \left( {\bf I} - {\bf P} + {\bf W} \right)^{-1} $$ -@end tex -@end iftex -@ifnottex -@example -@group - -1 -Z = (I - P + W) -@end group -@end example -@end ifnottex - -@noindent Then, we have that - -@iftex -@tex -$$ M_{i, j} = {Z_{j, j} - Z_{i, j} \over \pi_j} $$ -@end tex -@end iftex -@ifnottex -@example -@group - Z_jj - Z_ij -M_ij = ----------- - \pi_j -@end group -@end example -@end ifnottex - -According to the definition above, @math{M_{i,i} = 0}. We arbitrarily -let @math{M_{i,i}} to be the @emph{mean recurrence time} @math{r_i} -for state @math{i}, that is the average number of transitions needed -to return to state @math{i} starting from it. @math{r_i} is: - -@iftex -@tex -$$ r_i = {1 \over \pi_i} $$ -@end tex -@end iftex -@ifnottex -@example -@group - 1 -r_i = ----- - \pi_i -@end group -@end example -@end ifnottex - -@include help/dtmc_fpt.texi - -@c -@c -@c -@node Continuous-Time Markov Chains -@section Continuous-Time Markov Chains - -A stochastic process @math{@{X(t), t @geq{} 0@}} is a continuous-time -Markov chain if, for all integers @math{n}, and for any sequence -@math{t_0, t_1 , \ldots, t_n, t_{n+1}} such that @math{t_0 < t_1 < -\ldots < t_n < t_{n+1}}, we have - -@iftex -@tex -$$\eqalign{P(X(t_{n+1}) = x_{n+1}\ |\ X(t_n) = x_n, X(t_{n-1}) = x_{n-1}, \ldots, X(t_0) = x_0) \cr -&= P(X(t_{n+1}) = x_{n+1}\ |\ X(t_n) = x_n)}$$ -@end tex -@end iftex -@ifnottex -@math{P(X_{n+1} = x_{n+1} | X_n = x_n, X_{n-1} = x_{n-1}, ..., X_0 = x_0) = P(X_{n+1} = x_{n+1} | X_n = x_n)} -@end ifnottex - -A continuous-time Markov chain is defined according to an -@emph{infinitesimal generator matrix} @math{{\bf Q} = [Q_{i,j}]}, -where for each @math{i \neq j}, @math{Q_{i, j}} is the transition rate -from state @math{i} to state @math{j}. The matrix @math{\bf Q} must -satisfy the property that, for all @math{i}, @math{\sum_{j=1}^N Q_{i, -j} = 0}. - -@include help/ctmc_check_Q.texi - -@menu -* State occupancy probabilities (CTMC):: -* Birth-death process (CTMC):: -* Expected sojourn times (CTMC):: -* Time-averaged expected sojourn times (CTMC):: -* Mean time to absorption (CTMC):: -* First passage times (CTMC):: -@end menu - -@node State occupancy probabilities (CTMC) -@subsection State occupancy probabilities - -Similarly to the discrete case, we denote with @math{{\bf \pi}(t) = -(\pi_1(t), \pi_2(t), @dots{}, \pi_N(t) )} the @emph{state occupancy -probability vector} at time @math{t}. @math{\pi_i(t)} is the -probability that the system is in state @math{i} at time @math{t -@geq{} 0}. - -Given the infinitesimal generator matrix @math{\bf Q} and the initial -state occupancy probabilities @math{{\bf \pi}(0) = (\pi_1(0), -\pi_2(0), @dots{}, \pi_N(0))}, the state occupancy probabilities -@math{{\bf \pi}(t)} at time @math{t} can be computed as: - -@iftex -@tex -$${\bf \pi}(t) = {\bf \pi}(0) \exp( {\bf Q} t )$$ -@end tex -@end iftex -@ifnottex -@example -@group -\pi(t) = \pi(0) exp(Qt) -@end group -@end example -@end ifnottex - -@noindent where @math{\exp( {\bf Q} t )} is the matrix exponential -of @math{{\bf Q} t}. Under certain conditions, there exists a -@emph{stationary state occupancy probability} @math{{\bf \pi} = -\lim_{t \rightarrow +\infty} {\bf \pi}(t)}, which is independent from -@math{{\bf \pi}(0)}. @math{\bf \pi} is the solution of the following -linear system: - -@iftex -@tex -$$ -\left\{ \eqalign{ -{\bf \pi Q} & = {\bf 0} \cr -{\bf \pi 1}^T & = 1 -} \right. -$$ -@end tex -@end iftex -@ifnottex -@example -@group -/ -| \pi Q = 0 -| \pi 1^T = 1 -\ -@end group -@end example -@end ifnottex - -@include help/ctmc.texi - -@noindent @strong{EXAMPLE} - -Consider a two-state CTMC such that transition rates between states -are equal to 1. This can be solved as follows: - -@example -@group -@include demos/demo_1_ctmc.texi - @result{} q = 0.50000 0.50000 -@end group -@end example - -@c -@c -@c -@node Birth-death process (CTMC) -@subsection Birth-Death Process - -@include help/ctmc_bd.texi - -@c -@c -@c -@node Expected sojourn times (CTMC) -@subsection Expected Sojourn Times - -Given a @math{N} state continuous-time Markov Chain with infinitesimal -generator matrix @math{\bf Q}, we define the vector @math{{\bf L}(t) = -(L_1(t), L_2(t), \ldots, L_N(t))} such that @math{L_i(t)} is the -expected sojourn time in state @math{i} during the interval -@math{[0,t)}, assuming that the initial occupancy probability at time -0 was @math{{\bf \pi}(0)}. @math{{\bf L}(t)} can be expressed as the -solution of the following differential equation: - -@iftex -@tex -$$ { d{\bf L}(t) \over dt} = {\bf L}(t){\bf Q} + {\bf \pi}(0), \qquad {\bf L}(0) = {\bf 0} $$ -@end tex -@end iftex -@ifnottex -@example -@group - dL - --(t) = L(t) Q + pi(0), L(0) = 0 - dt -@end group -@end example -@end ifnottex - -Alternatively, @math{{\bf L}(t)} can also be expressed in integral -form as: - -@iftex -@tex -$$ {\bf L}(t) = \int_0^t {\bf \pi}(u) du$$ -@end tex -@end iftex -@ifnottex -@example -@group - / t -L(t) = | pi(u) du - / 0 -@end group -@end example -@end ifnottex - -@noindent where @math{{\bf \pi}(t) = {\bf \pi}(0) \exp({\bf Q}t)} is -the state occupancy probability at time @math{t}; @math{\exp({\bf Q}t)} -is the matrix exponential of @math{{\bf Q}t}. - -@include help/ctmc_exps.texi - -@noindent @strong{EXAMPLE} - -Let us consider a pure-birth, 4-states CTMC such that the transition -rate from state @math{i} to state @math{i+1} is @math{\lambda_i = i -\lambda} (@math{i=1, 2, 3}), with @math{\lambda = 0.5}. The following -code computes the expected sojourn time in state @math{i}, -given the initial occupancy probability @math{{\bf \pi}_0=(1,0,0,0)}. - -@example -@group -@include demos/demo_1_ctmc_exps.texi -@end group -@end example - -@c -@c -@c -@node Time-averaged expected sojourn times (CTMC) -@subsection Time-Averaged Expected Sojourn Times - -@include help/ctmc_taexps.texi - -@noindent @strong{EXAMPLE} - -@example -@group -@include demos/demo_1_ctmc_taexps.texi -@end group -@end example - -@c -@c -@c -@node Mean time to absorption (CTMC) -@subsection Mean Time to Absorption - -If we consider a Markov Chain with absorbing states, it is possible to -define the @emph{expected time to absorption} as the expected time -until the system goes into an absorbing state. More specifically, let -us suppose that @math{A} is the set of transient (i.e., non-absorbing) -states of a CTMC with @math{N} states and infinitesimal generator -matrix @math{\bf Q}. The expected time to absorption @math{{\bf -L}_A(\infty)} is defined as the solution of the following equation: - -@iftex -@tex -$$ {\bf L}_A(\infty){\bf Q}_A = -{\bf \pi}_A(0) $$ -@end tex -@end iftex -@ifnottex -@example -@group -L_A( inf ) Q_A = -pi_A(0) -@end group -@end example -@end ifnottex - -@noindent where @math{{\bf Q}_A} is the restriction of matrix @math{\bf Q} to -only states in @math{A}, and @math{{\bf \pi}_A(0)} is the initial -state occupancy probability at time 0, restricted to states in -@math{A}. - -@include help/ctmc_mtta.texi - -@noindent @strong{EXAMPLE} - -Let us consider a simple model of a redundant disk array. We assume -that the array is made of 5 independent disks, such that the array can -tolerate up to 2 disk failures without losing data. If three or more -disks break, the array is dead and unrecoverable. We want to estimate -the Mean-Time-To-Failure (MTTF) of the disk array. - -We model this system as a 4 states Markov chain with state space -@math{\{ 2, 3, 4, 5 \}}. State @math{i} denotes the fact that exactly -@math{i} disks are active; state @math{2} is absorbing. Let @math{\mu} -be the failure rate of a single disk. The system starts in state -@math{5} (all disks are operational). We use a pure death process, -with death rate from state @math{i} to state @math{i-1} is @math{\mu -i}, for @math{i = 3, 4, 5}). - -The MTTF of the disk array is the MTTA of the Markov Chain, and can be -computed with the following expression: - -@example -@group -@include demos/demo_1_ctmc_mtta.texi - @result{} t = 78.333 -@end group -@end example - -@noindent @strong{REFERENCES} - -G. Bolch, S. Greiner, H. de Meer and -K. Trivedi, @cite{Queueing Networks and Markov Chains: Modeling and -Performance Evaluation with Computer Science Applications}, Wiley, -1998. - -@auindex Bolch, G. -@auindex Greiner, S. -@auindex de Meer, H. -@auindex Trivedi, K. - -@c -@c -@c -@node First passage times (CTMC) -@subsection First Passage Times - -@include help/ctmc_fpt.texi -
--- a/main/queueing/doc/queueing.html Fri Apr 06 16:06:56 2012 +0000 +++ b/main/queueing/doc/queueing.html Fri Apr 06 16:12:18 2012 +0000 @@ -150,7 +150,6 @@ </ul> <!-- --> -<!-- DO NOT EDIT! Generated automatically by munge-texi. --> <!-- *- texinfo -*- --> <!-- Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla --> <!-- This file is part of the queueing toolbox, a Queueing Networks --> @@ -272,7 +271,6 @@ <a href="http://www.informatica.unibo.it/ricerca/ublcs/2010/UBLCS-2010-04">UBLCS-2010-04</a>, February 2010, Department of Computer Science, University of Bologna, Italy. -<!-- DO NOT EDIT! Generated automatically by munge-texi. --> <!-- *- texinfo -*- --> <!-- Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla --> <!-- This file is part of the queueing toolbox, a Queueing Networks --> @@ -519,8 +517,7 @@ <pre class="example"> octave:4> <kbd>demo qnclosed</kbd> </pre> - <!-- DO NOT EDIT! Generated automatically by munge-texi. --> -<!-- *- texinfo -*- --> + <!-- *- texinfo -*- --> <!-- Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla --> <!-- This file is part of the queueing toolbox, a Queueing Networks --> <!-- analysis package for GNU Octave. --> @@ -757,7 +754,6 @@ <!-- (TODO) --> <!-- @subsection Continuous-Time Markov Chains --> <!-- (TODO) --> -<!-- DO NOT EDIT! Generated automatically by munge-texi. --> <!-- *- texinfo -*- --> <!-- Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla --> <!-- This file is part of the queueing toolbox, a Queueing Networks --> @@ -825,8 +821,13 @@ following two properties: (1) P_i, j ≥ 0 for all i, j, and (2) \sum_j=1^N P_i,j = 1 for all i - <p><a name="doc_002ddtmc_005fcheck_005fP"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from dtmc_check_P.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>r</var> <var>err</var>] = <b>dtmc_check_P</b> (<var>P</var>)<var><a name="index-dtmc_005fcheck_005fP-1"></a></var><br> <blockquote> @@ -884,8 +885,13 @@ <p class="noindent">where \bf 1 is the row vector of ones, and ( \cdot )^T the transpose operator. - <p><a name="doc_002ddtmc"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from dtmc.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: <var>p</var> = <b>dtmc</b> (<var>P</var>)<var><a name="index-dtmc-3"></a></var><br> — Function File: <var>p</var> = <b>dtmc</b> (<var>P, n, p0</var>)<var><a name="index-dtmc-4"></a></var><br> @@ -972,6 +978,13 @@ using the following code: <pre class="example"> <!-- @group --> + <!-- *- 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 distributed --> + <!-- under the terms of the GNU General Public License version 3 or later --> + <!-- This file is automatically generated from dtmc.m --> + <!-- All modifications to this file will be lost --> <pre class="verbatim"> P = zeros(9,9); P(1,[2 4] ) = 1/2; P(2,[1 5 3] ) = 1/3; @@ -983,7 +996,9 @@ P(8,[7 5 9] ) = 1/3; P(9,[6 8] ) = 1/2; p = dtmc(P); - disp(p)</pre><!-- @end group --> + disp(p) +</pre> + <!-- @end group --> ⇒ 0.083333 0.125000 0.083333 0.125000 0.166667 0.125000 0.083333 0.125000 0.083333 @@ -1000,8 +1015,13 @@ <h4 class="subsection">4.1.2 Birth-death process</h4> -<p><a name="doc_002ddtmc_005fbd"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from dtmc_bd.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: <var>P</var> = <b>dtmc_bd</b> (<var>b, d</var>)<var><a name="index-dtmc_005fbd-11"></a></var><br> <blockquote> @@ -1075,8 +1095,13 @@ to the size of \bf P (filling missing entries with zeros), we have that, for absorbing chains \bf L = \bf \pi(0)\bf N. - <p><a name="doc_002ddtmc_005fexps"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from dtmc_exps.m --> +<!-- All modifications to this file will be lost --> <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> @@ -1129,8 +1154,13 @@ <h4 class="subsection">4.1.4 Time-averaged expected sojourn times</h4> -<p><a name="doc_002ddtmc_005ftaexps"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from dtmc_taexps.m --> +<!-- All modifications to this file will be lost --> <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> @@ -1168,7 +1198,7 @@ </dl> - </blockquote></div> + </blockquote></div> <div class="node"> <a name="Mean-time-to-absorption-(DTMC)"></a> @@ -1201,8 +1231,13 @@ <pre class="example"> B = N R </pre> - <p><a name="doc_002ddtmc_005fmtta"></a> - + <!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from dtmc_mtta.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>t</var> <var>N</var> <var>B</var>] = <b>dtmc_mtta</b> (<var>P</var>)<var><a name="index-dtmc_005fmtta-20"></a></var><br> — Function File: [<var>t</var> <var>N</var> <var>B</var>] = <b>dtmc_mtta</b> (<var>P, p0</var>)<var><a name="index-dtmc_005fmtta-21"></a></var><br> @@ -1304,8 +1339,13 @@ r_i = ----- \pi_i </pre> - <p><a name="doc_002ddtmc_005ffpt"></a> - + <!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from dtmc_fpt.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: <var>M</var> = <b>dtmc_fpt</b> (<var>P</var>)<var><a name="index-dtmc_005ffpt-25"></a></var><br> <blockquote> @@ -1367,8 +1407,13 @@ satisfy the property that, for all i, \sum_j=1^N Q_i, j = 0. - <p><a name="doc_002dctmc_005fcheck_005fQ"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from ctmc_check_Q.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>result</var> <var>err</var>] = <b>ctmc_check_Q</b> (<var>Q</var>)<var><a name="index-ctmc_005fcheck_005fQ-28"></a></var><br> <blockquote> @@ -1425,8 +1470,13 @@ | \pi 1^T = 1 \ </pre> - <p><a name="doc_002dctmc"></a> - + <!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from ctmc.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: <var>p</var> = <b>ctmc</b> (<var>Q</var>)<var><a name="index-ctmc-30"></a></var><br> — Function File: <var>p</var> = <b>ctmc</b> (<var>Q, t. p0</var>)<var><a name="index-ctmc-31"></a></var><br> @@ -1478,9 +1528,18 @@ <p>Consider a two-state CTMC such that transition rates between states are equal to 1. This can be solved as follows: -<pre class="example"><pre class="verbatim"> Q = [ -1 1; \ +<pre class="example"> <!-- *- 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 distributed --> + <!-- under the terms of the GNU General Public License version 3 or later --> + <!-- This file is automatically generated from ctmc.m --> + <!-- All modifications to this file will be lost --> +<pre class="verbatim"> Q = [ -1 1; \ 1 -1 ]; - q = ctmc(Q)</pre> ⇒ q = 0.50000 0.50000 + q = ctmc(Q) +</pre> + ⇒ q = 0.50000 0.50000 </pre> <div class="node"> <a name="Birth-death-process-(CTMC)"></a> @@ -1494,8 +1553,13 @@ <h4 class="subsection">4.2.2 Birth-Death Process</h4> -<p><a name="doc_002dctmc_005fbd"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from ctmc_bd.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: <var>Q</var> = <b>ctmc_bd</b> (<var>b, d</var>)<var><a name="index-ctmc_005fbd-36"></a></var><br> <blockquote> @@ -1556,8 +1620,13 @@ the state occupancy probability at time t; \exp(\bf Qt) is the matrix exponential of \bf Qt. - <p><a name="doc_002dctmc_005fexps"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from ctmc_exps.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: <var>L</var> = <b>ctmc_exps</b> (<var>Q, t, p </var>)<var><a name="index-ctmc_005fexps-39"></a></var><br> — Function File: <var>L</var> = <b>ctmc_exps</b> (<var>Q, p</var>)<var><a name="index-ctmc_005fexps-40"></a></var><br> @@ -1607,7 +1676,14 @@ code computes the expected sojourn time in state i, given the initial occupancy probability \bf \pi_0=(1,0,0,0). -<pre class="example"><pre class="verbatim"> lambda = 0.5; +<pre class="example"> <!-- *- 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 distributed --> + <!-- under the terms of the GNU General Public License version 3 or later --> + <!-- This file is automatically generated from ctmc_exps.m --> + <!-- All modifications to this file will be lost --> +<pre class="verbatim"> lambda = 0.5; N = 4; b = lambda*[1:N-1]; d = zeros(size(b)); @@ -1624,7 +1700,8 @@ t, L(:,4), ";State 4;", "linewidth", 2 ); legend("location","northwest"); xlabel("Time"); - ylabel("Expected sojourn time");</pre> + ylabel("Expected sojourn time"); +</pre> </pre> <div class="node"> <a name="Time-averaged-expected-sojourn-times-(CTMC)"></a> @@ -1638,8 +1715,13 @@ <h4 class="subsection">4.2.4 Time-Averaged Expected Sojourn Times</h4> -<p><a name="doc_002dctmc_005ftaexps"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from ctmc_taexps.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: <var>M</var> = <b>ctmc_taexps</b> (<var>Q, t, p</var>)<var><a name="index-ctmc_005ftaexps-43"></a></var><br> — Function File: <var>M</var> = <b>ctmc_taexps</b> (<var>Q, p</var>)<var><a name="index-ctmc_005ftaexps-44"></a></var><br> @@ -1677,11 +1759,18 @@ </dl> - </blockquote></div> + </blockquote></div> <p class="noindent"><strong>EXAMPLE</strong> -<pre class="example"><pre class="verbatim"> lambda = 0.5; +<pre class="example"> <!-- *- 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 distributed --> + <!-- under the terms of the GNU General Public License version 3 or later --> + <!-- This file is automatically generated from ctmc_taexps.m --> + <!-- All modifications to this file will be lost --> +<pre class="verbatim"> lambda = 0.5; N = 4; birth = lambda*linspace(1,N-1,N-1); death = zeros(1,N-1); @@ -1700,7 +1789,8 @@ t, M(:,4), ";State 4 (absorbing);", "linewidth", 2 ); legend("location","east"); xlabel("Time"); - ylabel("Time-averaged Expected sojourn time");</pre> + ylabel("Time-averaged Expected sojourn time"); +</pre> </pre> <div class="node"> <a name="Mean-time-to-absorption-(CTMC)"></a> @@ -1729,8 +1819,13 @@ state occupancy probability at time 0, restricted to states in A. - <p><a name="doc_002dctmc_005fmtta"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from ctmc_mtta.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: <var>t</var> = <b>ctmc_mtta</b> (<var>Q, p</var>)<var><a name="index-ctmc_005fmtta-47"></a></var><br> <blockquote> @@ -1787,11 +1882,20 @@ <p>The MTTF of the disk array is the MTTA of the Markov Chain, and can be computed with the following expression: -<pre class="example"><pre class="verbatim"> mu = 0.01; +<pre class="example"> <!-- *- 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 distributed --> + <!-- under the terms of the GNU General Public License version 3 or later --> + <!-- This file is automatically generated from ctmc_mtta.m --> + <!-- All modifications to this file will be lost --> +<pre class="verbatim"> mu = 0.01; death = [ 3 4 5 ] * mu; birth = 0*death; Q = ctmc_bd(birth,death); - t = ctmc_mtta(Q,[0 0 0 1])</pre> ⇒ t = 78.333 + t = ctmc_mtta(Q,[0 0 0 1]) +</pre> + ⇒ t = 78.333 </pre> <p class="noindent"><strong>REFERENCES</strong> @@ -1812,8 +1916,13 @@ <h4 class="subsection">4.2.6 First Passage Times</h4> -<p><a name="doc_002dctmc_005ffpt"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from ctmc_fpt.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: <var>M</var> = <b>ctmc_fpt</b> (<var>Q</var>)<var><a name="index-ctmc_005ffpt-54"></a></var><br> — Function File: <var>m</var> = <b>ctmc_fpt</b> (<var>Q, i, j</var>)<var><a name="index-ctmc_005ffpt-55"></a></var><br> @@ -1853,9 +1962,8 @@ </pre> <strong>See also:</strong> dtmc_fpt. - </blockquote></div> - -<!-- DO NOT EDIT! Generated automatically by munge-texi. --> + </blockquote></div> + <!-- *- texinfo -*- --> <!-- Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla --> <!-- This file is part of the queueing toolbox, a Queueing Networks --> @@ -1921,8 +2029,13 @@ with average service rate \mu. The system is stable if \lambda < \mu. - <p><a name="doc_002dqnmm1"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnmm1.m --> +<!-- All modifications to this file will be lost --> <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-57"></a></var><br> <blockquote> @@ -1994,8 +2107,13 @@ <pre class="example"> <code>mu(n) = min(m,n)*mu</code> </pre> - <p><a name="doc_002dqnmmm"></a> - + <!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnmmm.m --> +<!-- All modifications to this file will be lost --> <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-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> @@ -2072,8 +2190,13 @@ that queueing never occurs. The M/M/\infty system is always stable. - <p><a name="doc_002dqnmminf"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnmminf.m --> +<!-- All modifications to this file will be lost --> <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-70"></a></var><br> <blockquote> @@ -2150,8 +2273,13 @@ always stable, regardless of the arrival and service rates \lambda and \mu. - <p><a name="doc_002dqnmm1k"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnmm1k.m --> +<!-- All modifications to this file will be lost --> <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-77"></a></var><br> <blockquote> @@ -2219,8 +2347,13 @@ where 1 \leq m \leq K. The queue is made of K-m slots. The M/M/m/K system is always stable. - <p><a name="doc_002dqnmmmk"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnmmmk.m --> +<!-- All modifications to this file will be lost --> <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-79"></a></var><br> <blockquote> @@ -2283,7 +2416,6 @@ Science Applications</cite>, Wiley, 1998, Section 6.6. <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"> <a name="The-Asymmetric-M%2fM%2fm-System"></a> @@ -2301,8 +2433,13 @@ to a single queue. Differently from the M/M/m system, in the asymmetric M/M/m each server may have a different service time. - <p><a name="doc_002dqnammm"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnammm.m --> +<!-- All modifications to this file will be lost --> <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-85"></a></var><br> <blockquote> @@ -2366,8 +2503,13 @@ <h3 class="section">5.7 The M/G/1 System</h3> -<p><a name="doc_002dqnmg1"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnmg1.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>] = <b>qnmg1</b> (<var>lambda, xavg, x2nd</var>)<var><a name="index-qnmg1-91"></a></var><br> <blockquote> @@ -2412,7 +2554,7 @@ </pre> <strong>See also:</strong> qnmh1. - </blockquote></div> + </blockquote></div> <div class="node"> <a name="The-M%2fHm%2f1-System"></a> @@ -2425,8 +2567,13 @@ <h3 class="section">5.8 The M/H_m/1 System</h3> -<p><a name="doc_002dqnmh1"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnmh1.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>p0</var>] = <b>qnmh1</b> (<var>lambda, mu, alpha</var>)<var><a name="index-qnmh1-93"></a></var><br> <blockquote> @@ -2474,9 +2621,8 @@ </dl> <!-- @seealso{qnmhr1} --> - </blockquote></div> - -<!-- DO NOT EDIT! Generated automatically by munge-texi. --> + </blockquote></div> + <!-- *- texinfo -*- --> <!-- Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla --> <!-- This file is part of the queueing toolbox, a Queueing Networks --> @@ -2785,8 +2931,13 @@ <p>Individual nodes in the network are structures build using the <code>qnmknode</code> function. - <p><a name="doc_002dqnmknode"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnmknode.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: <var>Q</var> = <b>qnmknode</b> (<var>"m/m/m-fcfs", S</var>)<var><a name="index-qnmknode-96"></a></var><br> — Function File: <var>Q</var> = <b>qnmknode</b> (<var>"m/m/m-fcfs", S, m</var>)<var><a name="index-qnmknode-97"></a></var><br> @@ -2860,8 +3011,13 @@ efficient than those described in later sections, but generally easier to use. - <p><a name="doc_002dqnsolve"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnsolve.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"closed", N, QQ, V</var>)<var><a name="index-qnsolve-103"></a></var><br> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnsolve</b> (<var>"closed", N, QQ, V, Z</var>)<var><a name="index-qnsolve-104"></a></var><br> @@ -2961,13 +3117,22 @@ service center k. We can define and solve the model as follows: -<pre class="example"><pre class="verbatim"> QQ = { qnmknode( "m/m/m-fcfs", [0.2 0.1 0.1; 0.2 0.1 0.1] ), \ +<pre class="example"> <!-- *- 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 distributed --> + <!-- under the terms of the GNU General Public License version 3 or later --> + <!-- This file is automatically generated from qnsolve.m --> + <!-- All modifications to this file will be lost --> +<pre class="verbatim"> QQ = { qnmknode( "m/m/m-fcfs", [0.2 0.1 0.1; 0.2 0.1 0.1] ), \ qnmknode( "-/g/1-ps", [0.4; 0.6] ), \ qnmknode( "-/g/inf", [1; 2] ) }; V = [ 1 0.6 0.4; \ 1 0.3 0.7 ]; N = [ 2 1 ]; - [U R Q X] = qnsolve( "closed", N, QQ, V );</pre></pre> + [U R Q X] = qnsolve( "closed", N, QQ, V ); +</pre> +</pre> <div class="node"> <a name="Algorithms-for-Product-Form-QNs"></a> <a name="Algorithms-for-Product_002dForm-QNs"></a> @@ -3041,8 +3206,13 @@ <p class="noindent">where \pi_i(k_i) is the steady-state probability that there are k_i requests at service center i. - <p><a name="doc_002dqnjackson"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnjackson.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnjackson</b> (<var>lambda, S, P </var>)<var><a name="index-qnjackson-107"></a></var><br> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnjackson</b> (<var>lambda, S, P, m </var>)<var><a name="index-qnjackson-108"></a></var><br> @@ -3161,8 +3331,13 @@ centers. <!-- The Convolution Algorithm --> - <p><a name="doc_002dqnconvolution"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnconvolution.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnconvolution</b> (<var>N, S, V</var>)<var><a name="index-qnconvolution-116"></a></var><br> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnconvolution</b> (<var>N, S, V, m</var>)<var><a name="index-qnconvolution-117"></a></var><br> @@ -3229,7 +3404,14 @@ steady-state probability <var>p</var><code>(i)</code> to have <var>k</var><code>(i)</code> requests at service center i can be computed as: -<pre class="example"><pre class="verbatim"> k = [1 2 0]; +<pre class="example"> <!-- *- 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 distributed --> + <!-- under the terms of the GNU General Public License version 3 or later --> + <!-- This file is automatically generated from qnconvolution.m --> + <!-- All modifications to this file will be lost --> +<pre class="verbatim"> k = [1 2 0]; K = sum(k); # Total population size S = [ 1/0.8 1/0.6 1/0.4 ]; m = [ 2 3 1 ]; @@ -3241,7 +3423,9 @@ p(i) = (V(i)*S(i))^k(i) / G(K+1) * \ (G(K-k(i)+1) - V(i)*S(i)*G(K-k(i)) ); printf("k(%d)=%d prob=%f\n", i, k(i), p(i) ); - endfor</pre>-| k(1)=1 prob=0.17975 + endfor +</pre> + -| k(1)=1 prob=0.17975 -| k(2)=2 prob=0.48404 -| k(3)=0 prob=0.52779 </pre> @@ -3266,8 +3450,14 @@ <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> - + +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnconvolutionld.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnconvolutionld</b> (<var>N, S, V</var>)<var><a name="index-qnconvolutionld-126"></a></var><br> <blockquote> @@ -3356,8 +3546,13 @@ <h4 class="subsection">6.3.3 Open networks</h4> <!-- Open networks with single class --> -<p><a name="doc_002dqnopensingle"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnopensingle.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopensingle</b> (<var>lambda, S, V</var>)<var><a name="index-qnopensingle-138"></a></var><br> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopensingle</b> (<var>lambda, S, V, m</var>)<var><a name="index-qnopensingle-139"></a></var><br> @@ -3423,7 +3618,7 @@ </pre> <strong>See also:</strong> qnopen,qnclosed,qnvisits. - </blockquote></div> + </blockquote></div> <p>From the results computed by this function, it is possible to derive other quantities of interest as follows: @@ -3441,12 +3636,21 @@ <p class="noindent"><strong>EXAMPLE</strong> -<pre class="example"><pre class="verbatim"> lambda = 3; +<pre class="example"> <!-- *- 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 distributed --> + <!-- under the terms of the GNU General Public License version 3 or later --> + <!-- This file is automatically generated from qnopensingle.m --> + <!-- All modifications to this file will be lost --> +<pre class="verbatim"> lambda = 3; V = [16 7 8]; S = [0.01 0.02 0.03]; [U R Q X] = qnopensingle( lambda, S, V ); R_s = dot(R,V) # System response time - N = sum(Q) # Average number in system</pre>-| R_s = 1.4062 + N = sum(Q) # Average number in system +</pre> + -| R_s = 1.4062 -| N = 4.2186 </pre> <p class="noindent"><strong>REFERENCES</strong> @@ -3458,8 +3662,13 @@ <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> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnopenmulti.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopenmulti</b> (<var>lambda, S, V</var>)<var><a name="index-qnopenmulti-146"></a></var><br> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopenmulti</b> (<var>lambda, S, V, m</var>)<var><a name="index-qnopenmulti-147"></a></var><br> @@ -3534,8 +3743,13 @@ <h4 class="subsection">6.3.4 Closed Networks</h4> <!-- MVA for single class, closed networks --> -<p><a name="doc_002dqnclosedsinglemva"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnclosedsinglemva.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnclosedsinglemva</b> (<var>N, S, V</var>)<var><a name="index-qnclosedsinglemva-153"></a></var><br> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>, <var>G</var>] = <b>qnclosedsinglemva</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedsinglemva-154"></a></var><br> @@ -3615,14 +3829,21 @@ </pre> <strong>See also:</strong> qnclosedsinglemvald. - </blockquote></div> + </blockquote></div> <p>From the results provided by this function, it is possible to derive other quantities of interest as follows: <p class="noindent"><strong>EXAMPLE</strong> -<pre class="example"><pre class="verbatim"> S = [ 0.125 0.3 0.2 ]; +<pre class="example"> <!-- *- 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 distributed --> + <!-- under the terms of the GNU General Public License version 3 or later --> + <!-- This file is automatically generated from qnclosedsinglemva.m --> + <!-- All modifications to this file will be lost --> +<pre class="verbatim"> S = [ 0.125 0.3 0.2 ]; V = [ 16 10 5 ]; N = 20; m = ones(1,3); @@ -3635,7 +3856,9 @@ for k=1:length(S) printf("Dev%d\t%8.4f %8.4f %8.4f %8.4f\n", k, U(k), Q(k), R(k), X(k) ); endfor - printf("\nSystem\t %8.4f %8.4f %8.4f\n\n", N-X_s*Z, R_s, X_s );</pre></pre> + printf("\nSystem\t %8.4f %8.4f %8.4f\n\n", N-X_s*Z, R_s, X_s ); +</pre> +</pre> <p class="noindent"><strong>REFERENCES</strong> <p>M. Reiser and S. S. Lavenberg, <cite>Mean-Value Analysis of Closed @@ -3653,8 +3876,14 @@ <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> - + +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnclosedsinglemvald.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvald</b> (<var>N, S, V</var>)<var><a name="index-qnclosedsinglemvald-166"></a></var><br> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvald</b> (<var>N, S, V, Z</var>)<var><a name="index-qnclosedsinglemvald-167"></a></var><br> @@ -3719,8 +3948,14 @@ <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> - + +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qncmva.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qncmva</b> (<var>N, S, Sld, V</var>)<var><a name="index-qncmva-175"></a></var><br> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qncmva</b> (<var>N, S, Sld, V, Z</var>)<var><a name="index-qncmva-176"></a></var><br> @@ -3782,8 +4017,13 @@ <p><a name="index-Casale_002c-G_002e-179"></a> <!-- Approximate MVA for single class, closed networks --> - <p><a name="doc_002dqnclosedsinglemvaapprox"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnclosedsinglemvaapprox.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V</var>)<var><a name="index-qnclosedsinglemvaapprox-180"></a></var><br> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedsinglemvaapprox</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedsinglemvaapprox-181"></a></var><br> @@ -3873,8 +4113,13 @@ <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> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnclosedmultimva.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S </var>)<var><a name="index-qnclosedmultimva-193"></a></var><br> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimva</b> (<var>N, S, V</var>)<var><a name="index-qnclosedmultimva-194"></a></var><br> @@ -4025,8 +4270,14 @@ <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> - + +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnclosedmultimvaapprox.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V</var>)<var><a name="index-qnclosedmultimvaapprox-211"></a></var><br> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosedmultimvaapprox</b> (<var>N, S, V, m</var>)<var><a name="index-qnclosedmultimvaapprox-212"></a></var><br> @@ -4140,8 +4391,13 @@ <h4 class="subsection">6.3.5 Mixed Networks</h4> <!-- MVA for mixed networks --> -<p><a name="doc_002dqnmix"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnmix.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmix</b> (<var>lambda, N, S, V, m</var>)<var><a name="index-qnmix-226"></a></var><br> <blockquote> @@ -4224,7 +4480,7 @@ </pre> <strong>See also:</strong> qnclosedmultimva, qnopenmulti. - </blockquote></div> + </blockquote></div> <p class="noindent"><strong>REFERENCES</strong> @@ -4259,8 +4515,13 @@ <!-- MVABLO algorithm for approximate analysis of closed, single class --> <!-- QN with blocking --> -<p><a name="doc_002dqnmvablo"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnmvablo.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmvablo</b> (<var>N, S, M, P</var>)<var><a name="index-qnmvablo-234"></a></var><br> <blockquote> @@ -4311,7 +4572,7 @@ </pre> <strong>See also:</strong> qnopen, qnclosed. - </blockquote></div> + </blockquote></div> <p class="noindent"><strong>REFERENCES</strong> @@ -4320,8 +4581,14 @@ april 1988, pp. 418–428. <a href="http://dx.doi.org/10.1109/32.4663">http://dx.doi.org/10.1109/32.4663</a> <p><a name="index-Akyildiz_002c-I_002e-F_002e-238"></a> -<a name="doc_002dqnmarkov"></a> - + +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnmarkov.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>lambda, S, C, P</var>)<var><a name="index-qnmarkov-239"></a></var><br> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnmarkov</b> (<var>lambda, S, C, P, m</var>)<var><a name="index-qnmarkov-240"></a></var><br> @@ -4435,8 +4702,13 @@ <h3 class="section">6.5 Bounds on performance</h3> -<p><a name="doc_002dqnopenab"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnopenab.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>Xu</var>, <var>Rl</var>] = <b>qnopenab</b> (<var>lambda, D</var>)<var><a name="index-qnopenab-247"></a></var><br> <blockquote> @@ -4470,7 +4742,7 @@ </pre> <strong>See also:</strong> qnopenbsb. - </blockquote></div> + </blockquote></div> <p class="noindent"><strong>REFERENCES</strong> @@ -4481,8 +4753,14 @@ particular, see section 5.2 ("Asymptotic Bounds"). <p><a name="index-Lazowska_002c-E_002e-D_002e-250"></a><a name="index-Zahorjan_002c-J_002e-251"></a><a name="index-Graham_002c-G_002e-S_002e-252"></a><a name="index-Sevcik_002c-K_002e-C_002e-253"></a> -<a name="doc_002dqnclosedab"></a> - + +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnclosedab.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>Xl</var>, <var>Xu</var>, <var>Rl</var>, <var>Ru</var>] = <b>qnclosedab</b> (<var>N, D</var>)<var><a name="index-qnclosedab-254"></a></var><br> — 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> @@ -4530,8 +4808,13 @@ <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> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnopenbsb.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>Xu</var>, <var>Rl</var>, <var>Ru</var>] = <b>qnopenbsb</b> (<var>lambda, D</var>)<var><a name="index-qnopenbsb-262"></a></var><br> <blockquote> @@ -4576,8 +4859,14 @@ particular, see section 5.4 ("Balanced Systems Bounds"). <p><a name="index-Lazowska_002c-E_002e-D_002e-265"></a><a name="index-Zahorjan_002c-J_002e-266"></a><a name="index-Graham_002c-G_002e-S_002e-267"></a><a name="index-Sevcik_002c-K_002e-C_002e-268"></a> -<a name="doc_002dqnclosedbsb"></a> - + +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnclosedbsb.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>Xl</var>, <var>Xu</var>, <var>Rl</var>, <var>Ru</var>] = <b>qnclosedbsb</b> (<var>N, D</var>)<var><a name="index-qnclosedbsb-269"></a></var><br> — 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> @@ -4615,8 +4904,13 @@ </blockquote></div> - <p><a name="doc_002dqnclosedpb"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnclosedpb.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>Xl</var>, <var>Xu</var>] = <b>qnclosedpb</b> (<var>N, D </var>)<var><a name="index-qnclosedpb-273"></a></var><br> <blockquote> @@ -4663,8 +4957,14 @@ Transactions on Computers, 57(6):780-794, June 2008. <p><a name="index-Hsieh_002c-C_002e-H-274"></a><a name="index-Lam_002c-S_002e-275"></a><a name="index-Casale_002c-G_002e-276"></a><a name="index-Muntz_002c-R_002e-R_002e-277"></a><a name="index-Serazzi_002c-G_002e-278"></a> -<a name="doc_002dqnclosedgb"></a> - + +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnclosedgb.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>Xl</var>, <var>Xu</var>, <var>Ql</var>, <var>Qu</var>] = <b>qnclosedgb</b> (<var>N, D, Z</var>)<var><a name="index-qnclosedgb-279"></a></var><br> <blockquote> @@ -4726,8 +5026,13 @@ <h4 class="subsection">6.6.1 Open or closed networks</h4> -<p><a name="doc_002dqnclosed"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnclosed.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnclosed</b> (<var>N, S, V, <small class="dots">...</small></var>)<var><a name="index-qnclosed-285"></a></var><br> <blockquote> @@ -4764,11 +5069,18 @@ </pre> <strong>See also:</strong> qnclosedsinglemva, qnclosedsinglemvald, qnclosedmultimva. - </blockquote></div> + </blockquote></div> <p class="noindent"><strong>EXAMPLE</strong> -<pre class="example"><pre class="verbatim"> P = [0 0.3 0.7; 1 0 0; 1 0 0]; # Transition probability matrix +<pre class="example"> <!-- *- 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 distributed --> + <!-- under the terms of the GNU General Public License version 3 or later --> + <!-- This file is automatically generated from qnclosed.m --> + <!-- All modifications to this file will be lost --> +<pre class="verbatim"> P = [0 0.3 0.7; 1 0 0; 1 0 0]; # Transition probability matrix S = [1 0.6 0.2]; # Average service times m = ones(1,3); # All centers are single-server Z = 2; # External delay @@ -4794,9 +5106,16 @@ axis([1,N,0,1]); xlabel("Number of Requests n"); ylabel("System Throughput X(n)"); - legend("location","southeast");</pre></pre> - <p><a name="doc_002dqnopen"></a> - + legend("location","southeast"); +</pre> +</pre> + <!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnopen.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>U</var>, <var>R</var>, <var>Q</var>, <var>X</var>] = <b>qnopen</b> (<var>lambda, S, V, <small class="dots">...</small></var>)<var><a name="index-qnopen-287"></a></var><br> <blockquote> @@ -4850,8 +5169,13 @@ \lambda_s, j is the overall external arrival rate to the whole system, then P_0, s, j = \lambda_s, j / \lambda. - <p><a name="doc_002dqnvisits"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnvisits.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: [<var>V</var> <var>ch</var>] = <b>qnvisits</b> (<var>P</var>)<var><a name="index-qnvisits-289"></a></var><br> — Function File: <var>V</var> = <b>qnvisits</b> (<var>P, lambda</var>)<var><a name="index-qnvisits-290"></a></var><br> @@ -4902,7 +5226,14 @@ <p class="noindent"><strong>EXAMPLE</strong> -<pre class="example"><pre class="verbatim"> P = [ 0 0.4 0.6 0; \ +<pre class="example"> <!-- *- 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 distributed --> + <!-- under the terms of the GNU General Public License version 3 or later --> + <!-- This file is automatically generated from qnvisits.m --> + <!-- All modifications to this file will be lost --> +<pre class="verbatim"> P = [ 0 0.4 0.6 0; \ 0.2 0 0.2 0.6; \ 0 0 0 1; \ 0 0 0 0 ]; @@ -4910,11 +5241,18 @@ V = qnvisits(P,lambda); S = [2 1 2 1.8]; m = [3 1 1 2]; - [U R Q X] = qnopensingle( sum(lambda), S, V, m );</pre></pre> + [U R Q X] = qnopensingle( sum(lambda), S, V, m ); +</pre> +</pre> <h4 class="subsection">6.6.3 Other utility functions</h4> -<p><a name="doc_002dpopulation_005fmix"></a> - +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from population_mix.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: pop_mix = <b>population_mix</b> (<var>k, N</var>)<var><a name="index-population_005fmix-291"></a></var><br> <blockquote> @@ -4963,7 +5301,7 @@ </pre> <strong>See also:</strong> qnmvapop. - </blockquote></div> + </blockquote></div> <p class="noindent"><strong>REFERENCES</strong> @@ -4981,8 +5319,14 @@ <a href="http://arantxa.ii.uam.es/~ssantini/writing/notes/s668_summation.pdf">http://arantxa.ii.uam.es/~ssantini/writing/notes/s668_summation.pdf</a> <p><a name="index-Schwetman_002c-H_002e-294"></a><a name="index-Santini_002c-S_002e-295"></a> -<a name="doc_002dqnmvapop"></a> - + +<!-- *- 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 distributed --> +<!-- under the terms of the GNU General Public License version 3 or later --> +<!-- This file is automatically generated from qnmvapop.m --> +<!-- All modifications to this file will be lost --> <div class="defun"> — Function File: <var>H</var> = <b>qnmvapop</b> (<var>N</var>)<var><a name="index-qnmvapop-296"></a></var><br> <blockquote> @@ -5025,7 +5369,6 @@ <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 --> @@ -5133,7 +5476,6 @@ </dl> <!-- Appendix starts here --> -<!-- DO NOT EDIT! Generated automatically by munge-texi. --> <!-- *- texinfo -*- --> <!-- Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla --> <!-- This file is part of the queueing toolbox, a Queueing Networks --> @@ -5193,7 +5535,6 @@ (<a href="mailto:marzolla@cs.unibo.it">marzolla@cs.unibo.it</a>). If you are just a user of this package and find it useful, let me know by dropping me a line. Thanks. -<!-- DO NOT EDIT! Generated automatically by munge-texi. --> <!-- *- texinfo -*- --> <!-- Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla --> <!-- This file is part of the queueing toolbox, a Queueing Networks --> @@ -5225,7 +5566,6 @@ or contributing code: Philip Carinhas, Phil Colbourn, Yves Durand, Marco Guazzone, Dmitry Kolesnikov. -<!-- DO NOT EDIT! Generated automatically by munge-texi. --> <div class="node"> <a name="Copying"></a> <p><hr>
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main/queueing/doc/singlestation.texi Fri Apr 06 16:12:18 2012 +0000 @@ -0,0 +1,226 @@ +@c -*- texinfo -*- + +@c Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla +@c +@c This file is part of the queueing toolbox, a Queueing Networks +@c analysis package for GNU Octave. +@c +@c The queueing toolbox is free software; you can redistribute it +@c and/or modify it under the terms of the GNU General Public License +@c as published by the Free Software Foundation; either version 3 of +@c the License, or (at your option) any later version. +@c +@c The queueing toolbox is distributed in the hope that it will be +@c useful, but WITHOUT ANY WARRANTY; without even the implied warranty +@c of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +@c GNU General Public License for more details. +@c +@c You should have received a copy of the GNU General Public License +@c along with the queueing toolbox; see the file COPYING. If not, see +@c <http://www.gnu.org/licenses/>. + +@node Single Station Queueing Systems +@chapter Single Station Queueing Systems + +Single Station Queueing Systems contain a single station, and are thus +quite easy to analyze. The @code{queueing} package contains functions +for handling the following types of queues: + +@ifnottex +@menu +* The M/M/1 System:: Single-server queueing station. +* The M/M/m System:: Multiple-server queueing station. +* The M/M/inf System:: Infinite-server (delay center) station. +* The M/M/1/K System:: Single-server, finite-capacity queueing station. +* The M/M/m/K System:: Multiple-server, finite-capacity queueing station. +* The Asymmetric M/M/m System:: Asymmetric multiple-server queueing station. +* The M/G/1 System:: Single-server with general service time distribution. +* The M/Hm/1 System:: Single-server with hyperexponential service time distribution. +@end menu +@end ifnottex +@iftex +@itemize + +@item @math{M/M/1} single-server queueing station; + +@item @math{M/M/m} multiple-server queueing station; + +@item Asymmetric @math{M/M/m}; + +@item @math{M/M/\infty} infinite-server station (delay center); + +@item @math{M/M/1/K} single-server, finite-capacity queueing station; + +@item @math{M/M/m/K} multiple-server, finite-capacity queueing station; + +@item @math{M/G/1} single-server with general service time distribution; + +@item @math{M/H_m/1} single-server with hyperexponential service time distribution. + +@end itemize + +@end iftex + +The functions which analyze the queues above can be used as building +blocks for analyzing Queueing Networks. For example, Jackson networks +can be solved by computing the aggregate arrival rates to each node, +and then solving each node in isolation as if it were a single station +queueing system. + +@c +@c M/M/1 +@c +@node The M/M/1 System +@section The @math{M/M/1} System + +The @math{M/M/1} system is made of a single server connected to an +unlimited FCFS queue. The mean arrival rate is Poisson with arrival +rate @math{\lambda}; the service time is exponentially distributed +with average service rate @math{\mu}. The system is stable if +@math{\lambda < \mu}. + +@include help/qnmm1.texi + +@noindent @strong{REFERENCES} + +@noindent G. Bolch, S. Greiner, H. de Meer and K. Trivedi, @cite{Queueing Networks +and Markov Chains: Modeling and Performance Evaluation with Computer +Science Applications}, Wiley, 1998, Section 6.3. + +@auindex Bolch, G. +@auindex Greiner, S. +@auindex de Meer, H. +@auindex Trivedi, K. + +@c +@c M/M/m +@c +@node The M/M/m System +@section The @math{M/M/m} System + +The @math{M/M/m} system is similar to the @math{M/M/1} system, except +that there are @math{m \geq 1} identical servers connected to a single +queue. Thus, at most @math{m} requests can be served at the same +time. The @math{M/M/m} system can be seen as a single server with +load-dependent service rate @math{\mu(n)}, which is a function of the +number @math{n} of nodes in the center: + +@example +@code{mu(n) = min(m,n)*mu} +@end example + +@include help/qnmmm.texi + +@noindent @strong{REFERENCES} + +@noindent G. Bolch, S. Greiner, H. de Meer and K. Trivedi, @cite{Queueing Networks +and Markov Chains: Modeling and Performance Evaluation with Computer +Science Applications}, Wiley, 1998, Section 6.5. + +@auindex Bolch, G. +@auindex Greiner, S. +@auindex de Meer, H. +@auindex Trivedi, K. + +@c +@c M/M/inf +@c +@node The M/M/inf System +@section The @math{M/M/}inf System + +The @math{M/M/\infty} system is similar to the @math{M/M/m} system, +except that there are infinitely many identical servers (that is, +@math{m = \infty}). Each new request is assigned to a new server, so +that queueing never occurs. The @math{M/M/\infty} system is always +stable. + +@include help/qnmminf.texi + +@noindent @strong{REFERENCES} + +@noindent G. Bolch, S. Greiner, H. de Meer and K. Trivedi, @cite{Queueing Networks +and Markov Chains: Modeling and Performance Evaluation with Computer +Science Applications}, Wiley, 1998, Section 6.4. + +@auindex Bolch, G. +@auindex Greiner, S. +@auindex de Meer, H. +@auindex Trivedi, K. + +@c +@c M/M/1/k +@c +@node The M/M/1/K System +@section The @math{M/M/1/K} System + +In a @math{M/M/1/K} finite capacity system there can be at most +@math{k} jobs at any time. If a new request tries to join the system +when there are already @math{K} other requests, the arriving request +is lost. The queue has @math{K-1} slots. The @math{M/M/1/K} system is +always stable, regardless of the arrival and service rates +@math{\lambda} and @math{\mu}. + +@include help/qnmm1k.texi + +@c +@c M/M/m/k +@c +@node The M/M/m/K System +@section The @math{M/M/m/K} System + +The @math{M/M/m/K} finite capacity system is similar to the +@math{M/M/1/k} system except that the number of servers is @math{m}, +where @math{1 \leq m \leq K}. The queue is made of @math{K-m} +slots. The @math{M/M/m/K} system is always stable. + +@include help/qnmmmk.texi + +@noindent @strong{REFERENCES} + +@noindent G. Bolch, S. Greiner, H. de Meer and K. Trivedi, @cite{Queueing Networks +and Markov Chains: Modeling and Performance Evaluation with Computer +Science Applications}, Wiley, 1998, Section 6.6. + +@auindex Bolch, G. +@auindex Greiner, S. +@auindex de Meer, H. +@auindex Trivedi, K. + +@c +@c Approximate M/M/m +@c +@node The Asymmetric M/M/m System +@section The Asymmetric @math{M/M/m} System + +The Asymmetric @math{M/M/m} system contains @math{m} servers connected +to a single queue. Differently from the @math{M/M/m} system, in the +asymmetric @math{M/M/m} each server may have a different service time. + +@include help/qnammm.texi + +@noindent @strong{REFERENCES} + +@noindent G. Bolch, S. Greiner, H. de Meer and K. Trivedi, @cite{Queueing Networks +and Markov Chains: Modeling and Performance Evaluation with Computer +Science Applications}, Wiley, 1998 + +@auindex Bolch, G. +@auindex Greiner, S. +@auindex de Meer, H. +@auindex Trivedi, K. + +@c +@c +@c +@node The M/G/1 System +@section The @math{M/G/1} System + +@include help/qnmg1.texi + +@c +@c +@c +@node The M/Hm/1 System +@section The @math{M/H_m/1} System +@include help/qnmh1.texi +
--- a/main/queueing/doc/singlestation.txi Fri Apr 06 16:06:56 2012 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,226 +0,0 @@ -@c -*- texinfo -*- - -@c Copyright (C) 2008, 2009, 2010, 2011, 2012 Moreno Marzolla -@c -@c This file is part of the queueing toolbox, a Queueing Networks -@c analysis package for GNU Octave. -@c -@c The queueing toolbox is free software; you can redistribute it -@c and/or modify it under the terms of the GNU General Public License -@c as published by the Free Software Foundation; either version 3 of -@c the License, or (at your option) any later version. -@c -@c The queueing toolbox is distributed in the hope that it will be -@c useful, but WITHOUT ANY WARRANTY; without even the implied warranty -@c of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -@c GNU General Public License for more details. -@c -@c You should have received a copy of the GNU General Public License -@c along with the queueing toolbox; see the file COPYING. If not, see -@c <http://www.gnu.org/licenses/>. - -@node Single Station Queueing Systems -@chapter Single Station Queueing Systems - -Single Station Queueing Systems contain a single station, and are thus -quite easy to analyze. The @code{queueing} package contains functions -for handling the following types of queues: - -@ifnottex -@menu -* The M/M/1 System:: Single-server queueing station. -* The M/M/m System:: Multiple-server queueing station. -* The M/M/inf System:: Infinite-server (delay center) station. -* The M/M/1/K System:: Single-server, finite-capacity queueing station. -* The M/M/m/K System:: Multiple-server, finite-capacity queueing station. -* The Asymmetric M/M/m System:: Asymmetric multiple-server queueing station. -* The M/G/1 System:: Single-server with general service time distribution. -* The M/Hm/1 System:: Single-server with hyperexponential service time distribution. -@end menu -@end ifnottex -@iftex -@itemize - -@item @math{M/M/1} single-server queueing station; - -@item @math{M/M/m} multiple-server queueing station; - -@item Asymmetric @math{M/M/m}; - -@item @math{M/M/\infty} infinite-server station (delay center); - -@item @math{M/M/1/K} single-server, finite-capacity queueing station; - -@item @math{M/M/m/K} multiple-server, finite-capacity queueing station; - -@item @math{M/G/1} single-server with general service time distribution; - -@item @math{M/H_m/1} single-server with hyperexponential service time distribution. - -@end itemize - -@end iftex - -The functions which analyze the queues above can be used as building -blocks for analyzing Queueing Networks. For example, Jackson networks -can be solved by computing the aggregate arrival rates to each node, -and then solving each node in isolation as if it were a single station -queueing system. - -@c -@c M/M/1 -@c -@node The M/M/1 System -@section The @math{M/M/1} System - -The @math{M/M/1} system is made of a single server connected to an -unlimited FCFS queue. The mean arrival rate is Poisson with arrival -rate @math{\lambda}; the service time is exponentially distributed -with average service rate @math{\mu}. The system is stable if -@math{\lambda < \mu}. - -@include help/qnmm1.texi - -@noindent @strong{REFERENCES} - -@noindent G. Bolch, S. Greiner, H. de Meer and K. Trivedi, @cite{Queueing Networks -and Markov Chains: Modeling and Performance Evaluation with Computer -Science Applications}, Wiley, 1998, Section 6.3. - -@auindex Bolch, G. -@auindex Greiner, S. -@auindex de Meer, H. -@auindex Trivedi, K. - -@c -@c M/M/m -@c -@node The M/M/m System -@section The @math{M/M/m} System - -The @math{M/M/m} system is similar to the @math{M/M/1} system, except -that there are @math{m \geq 1} identical servers connected to a single -queue. Thus, at most @math{m} requests can be served at the same -time. The @math{M/M/m} system can be seen as a single server with -load-dependent service rate @math{\mu(n)}, which is a function of the -number @math{n} of nodes in the center: - -@example -@code{mu(n) = min(m,n)*mu} -@end example - -@include help/qnmmm.texi - -@noindent @strong{REFERENCES} - -@noindent G. Bolch, S. Greiner, H. de Meer and K. Trivedi, @cite{Queueing Networks -and Markov Chains: Modeling and Performance Evaluation with Computer -Science Applications}, Wiley, 1998, Section 6.5. - -@auindex Bolch, G. -@auindex Greiner, S. -@auindex de Meer, H. -@auindex Trivedi, K. - -@c -@c M/M/inf -@c -@node The M/M/inf System -@section The @math{M/M/}inf System - -The @math{M/M/\infty} system is similar to the @math{M/M/m} system, -except that there are infinitely many identical servers (that is, -@math{m = \infty}). Each new request is assigned to a new server, so -that queueing never occurs. The @math{M/M/\infty} system is always -stable. - -@include help/qnmminf.texi - -@noindent @strong{REFERENCES} - -@noindent G. Bolch, S. Greiner, H. de Meer and K. Trivedi, @cite{Queueing Networks -and Markov Chains: Modeling and Performance Evaluation with Computer -Science Applications}, Wiley, 1998, Section 6.4. - -@auindex Bolch, G. -@auindex Greiner, S. -@auindex de Meer, H. -@auindex Trivedi, K. - -@c -@c M/M/1/k -@c -@node The M/M/1/K System -@section The @math{M/M/1/K} System - -In a @math{M/M/1/K} finite capacity system there can be at most -@math{k} jobs at any time. If a new request tries to join the system -when there are already @math{K} other requests, the arriving request -is lost. The queue has @math{K-1} slots. The @math{M/M/1/K} system is -always stable, regardless of the arrival and service rates -@math{\lambda} and @math{\mu}. - -@include help/qnmm1k.texi - -@c -@c M/M/m/k -@c -@node The M/M/m/K System -@section The @math{M/M/m/K} System - -The @math{M/M/m/K} finite capacity system is similar to the -@math{M/M/1/k} system except that the number of servers is @math{m}, -where @math{1 \leq m \leq K}. The queue is made of @math{K-m} -slots. The @math{M/M/m/K} system is always stable. - -@include help/qnmmmk.texi - -@noindent @strong{REFERENCES} - -@noindent G. Bolch, S. Greiner, H. de Meer and K. Trivedi, @cite{Queueing Networks -and Markov Chains: Modeling and Performance Evaluation with Computer -Science Applications}, Wiley, 1998, Section 6.6. - -@auindex Bolch, G. -@auindex Greiner, S. -@auindex de Meer, H. -@auindex Trivedi, K. - -@c -@c Approximate M/M/m -@c -@node The Asymmetric M/M/m System -@section The Asymmetric @math{M/M/m} System - -The Asymmetric @math{M/M/m} system contains @math{m} servers connected -to a single queue. Differently from the @math{M/M/m} system, in the -asymmetric @math{M/M/m} each server may have a different service time. - -@include help/qnammm.texi - -@noindent @strong{REFERENCES} - -@noindent G. Bolch, S. Greiner, H. de Meer and K. Trivedi, @cite{Queueing Networks -and Markov Chains: Modeling and Performance Evaluation with Computer -Science Applications}, Wiley, 1998 - -@auindex Bolch, G. -@auindex Greiner, S. -@auindex de Meer, H. -@auindex Trivedi, K. - -@c -@c -@c -@node The M/G/1 System -@section The @math{M/G/1} System - -@include help/qnmg1.texi - -@c -@c -@c -@node The M/Hm/1 System -@section The @math{M/H_m/1} System -@include help/qnmh1.texi -