summaryrefslogtreecommitdiff
path: root/obsolete/macros/latex209/contrib/tamueethesis/ch2.tex
diff options
context:
space:
mode:
Diffstat (limited to 'obsolete/macros/latex209/contrib/tamueethesis/ch2.tex')
-rw-r--r--obsolete/macros/latex209/contrib/tamueethesis/ch2.tex309
1 files changed, 309 insertions, 0 deletions
diff --git a/obsolete/macros/latex209/contrib/tamueethesis/ch2.tex b/obsolete/macros/latex209/contrib/tamueethesis/ch2.tex
new file mode 100644
index 0000000000..2c97fccc79
--- /dev/null
+++ b/obsolete/macros/latex209/contrib/tamueethesis/ch2.tex
@@ -0,0 +1,309 @@
+\chapter{Closure Approximations in the Tandem Queue}
+\label{ch:clo}
+The purpose of this chapter is to extend the results from the M/M/1 queue to
+a two queue system consisting of a M/M/1 queue whose output is directed
+to a second Markovian queue. This small network is known as a tandem queue
+and is depicted in Fig.~\ref{fig:tan}.
+\begin{figure}
+\centering
+\begin{picture}(360,180)
+\multiput(72,45)(0,18){4}{\framebox(18,18){0}}
+\multiput(90,45)(0,18){4}{\framebox(18,18){0}}
+\multiput(108,45)(0,18){3}{\framebox(18,18){1}}
+\multiput(126,45)(0,18){4}{\framebox(18,18){1}}
+\put(108,99){\framebox(18,18){0}}
+\multiput(234,45)(18,0){4}{\framebox(18,18){0}}
+\multiput(234,63)(18,0){4}{\framebox(18,18){0}}
+\multiput(234,81)(18,0){2}{\framebox(18,18){0}}
+\multiput(270,81)(18,0){2}{\framebox(18,18){1}}
+\multiput(234,99)(18,0){3}{\framebox(18,18){0}}
+\put(288,99){\framebox(18,18){1}}
+\put(126,72){\oval(32,15)[t]}
+\put(126,54){\oval(32,15)[b]}
+\multiput(110,54)(32,0){2}{\line(0,1){18}}
+\multiput(126,90)(162,0){2}{\oval(32,15)}
+\multiput(135,99)(162,0){2}{\oval(15,32)}
+\multiput(55,49)(162,0){2}{10}
+\multiput(55,67)(162,0){2}{11}
+\multiput(55,85)(162,0){2}{01}
+\multiput(55,103)(162,0){2}{00}
+\multiput(75,124)(162,0){2}{00}
+\multiput(93,124)(162,0){2}{01}
+\multiput(111,124)(162,0){2}{11}
+\multiput(129,124)(162,0){2}{10}
+\multiput(72,117)(162,0){2}{\thicklines \line(-1,1){28}}
+\multiput(54,137)(162,0){2}{CD}
+\multiput(35,125)(162,0){2}{AB}
+\end{picture}
+\caption{The two node tandem queue.}
+\label{fig:tan}
+\end{figure}
+The size of this network makes possible a solution by near-exact methods so
+that the closure methods can be evaluated for the dependencies of the mean and
+variance of the second queue on the state of the first queue. Since the first
+queue of the tandem is simply M/M/1, this chapter will concentrate on the
+results from the second queue. The two most accurate closure assumptions, Clark
+and Chang/Wang, will be compared against the Kolmogorov solution~\cite{AA:1}.
+
+\section{The Kolmogorov Solution}
+The state space for the tandem queue is a two-dimensional lattice
+of states indexed by the number in each queue. For example, $P_{1,2}(t)$ is
+the probability that there is one in the first queue and two in the second.
+The size of the state space depends on the maximum number in each queue. If
+each queue can hold 49 items, including server, than the number of possible
+states is $50^2$ or 2500~\cite{PKGT:1}.
+
+The Kolmogorov solution for the tandem queue was obtained using a stochastic
+balance between various states of the birth-death process. Fig.\ \ref{fig:sto}
+shows the stochastic balance used to obtain (\ref{eq:kolt4}).
+\begin{figure}
+\centering
+\begin{picture}(224,180)
+\put(36,50){\thicklines \framebox(60,80)[t]{\&}}
+\put(14,70){\line(1,0){22}}
+\put(0,110){\line(1,0){36}}
+\put(0,115){$x$}
+\put(14,70){\line(0,-1){40}}
+\put(14,30){\line(1,0){30}}
+\put(49,26){$c$}
+\put(96,90){\line(1,0){38}}
+\put(134,40){\thicklines \framebox(60,100){ }}
+\put(139,85){D}
+\put(194,110){\line(1,0){18}}
+\put(194,70){\line(1,0){18}}
+\put(204,75){$\overline{Q}$}
+\put(204,115){$Q$}
+\put(24,10){\thicklines \dashbox(200,150){ }}
+\end{picture}
+\caption{Stochastic balance for tandem queue without feedback.}
+\label{fig:sto}
+\end{figure}
+The Kolmogorov equation set for the tandem queue was found to be
+\begin{eqnarray}
+\frac{dP_{0,0}}{dt} & = & -\left( \gamma _1 + \gamma _2\right) P_{0,0} +
+\mu _2 P_{0,1} \label{eq:kolt1}\\
+\frac{dP_{0,i}}{dt} & = & -\left( \gamma _1 + \gamma _2+ \mu_2\right) P_{0,i} +
+\mu _2 P_{0,i+1} \nonumber \\
+& & \mbox{}+\qquad\gamma _2P_{0,i-1}+\mu _1 P_{1,i-1}
+\hspace{.993in}\qquad i=1,2,3... \label {eq:kolt2}\\
+\frac{dP_{j,0}}{dt} & = & -\left( \gamma _1 + \gamma _2+ \mu _1\right) P_{j,0}
++ \gamma _1P_{j-1,0} + \mu _2P_{j,1} \qquad j=1,2,3... \label{eq:kolt3} \\
+\frac{dP_{j,i}}{dt} & = & -\left( \gamma _1 + \gamma _2+ \mu _1
++\mu _2\right) P_{j,i} +\gamma _1P_{j-1,i}+
+\mu _2 P_{j,i+1} \nonumber \\
+& & \mbox{}+\qquad\gamma_2P_{j,i-1}+\mu _1 P_{j+1,i-1} \qquad \hspace{0.77in}
+j,i=1,2,3... \label{eq:kolt4}
+\end{eqnarray}
+
+The mean and variance statistics for the second queue are obtained by the
+following equations:
+\[ M_2 = \sum_{i=1}^{\infty}i\cdot\sum_{j=0}^{\infty}P_{j,i} \]
+\noindent { and}
+\[ V_2 = \sum_{i=1}^{\infty}i^2\cdot\sum_{j=0}^{\infty}P_{j,i} - M_2^2.\]
+Calculation of the mean and variance requires the truncation of the M/M/1$/\infty$
+to some maximum number of states. Stated differently, the M/M/1/$\infty$ queue
+model is approximated by an M/M/1/k queue. While it is impossible to
+evaluate the error in this approximation, an indication
+of the truncation error can be obtained by summing all the probability states
+up to state $k$ and subtracting this total from one. This yields the probability
+of being in a state greater than $k$. If this value is very small then
+its product with $i$ and $i^2$ will also be small.
+
+It is easy to see how large and complicated the Kolmogorov equation set can become
+for just a small network, and the usefulness of an accurate, state-reducing
+approximation~\cite{RL:1}.
+\section{Approximations for the Tandem Queue}
+\subsection{Independent Queue Assumption}
+Jackson \cite{EG:1} showed that a network of queues can be analyzed as
+a group of independent M/M/1 queues when the network is operating
+under steady-state conditions. One method to approximate the tandem queue
+state space is to assume that the independence holds under transient conditions
+as well. By assuming the two queues are independent, the joint probability
+$P_{j,i}$ simply becomes the product of the marginal probabilities, $P_j$ and
+$P_i$. Thus, the number of states needed to model the tandem M/M/1/50 queue by
+the Kolmogorov equations decreases from 2500 to 100.
+
+Since the primary motivation behind the approximation methods is to
+obtain accurate mean and variance statistics for the queues, it is
+of interest to investigate errors induced by assuming the queues
+to be independent. The mean and variance statistics for the first
+and second queues are defined as
+
+\begin{eqnarray}
+ M_1&=&\sum_{j=1}^{\infty}j\cdot P_j\nonumber\\
+ V_1&=&\sum_{j=1}^{\infty}j^2\cdot P_j - M_{1}^2,\nonumber
+\end{eqnarray}
+\noindent{and}
+\begin{eqnarray}
+ M_2&=&\sum_{i=1}^{\infty}i\cdot P_i\label{eq:m2}\\
+ V_2&=&\sum_{i=1}^{\infty}i^2\cdot P_i - M_{2}^2\label{eq:v2}.
+\end{eqnarray}
+
+The accuracy of $P_j$ for $j>0$ will determine the effectiveness of the
+independence assumption. By definition, $P_j=\sum_{i=0}^{\infty}P_{j,i}$.
+By summing (\ref{eq:kolt3}) and (\ref{eq:kolt4}), we obtain
+\begin{eqnarray*}
+\frac{dP_j}{dt} & = & -\left(\gamma_1 +\gamma_2 +\mu_1\right)\sum_{i=0}^{\infty}P_{j,i}
+-\mu_2\sum_{i=1}^{\infty}P_{j,i}+\gamma_1\sum_{i=0}^{\infty}P_{j-1,i} \\
+& & \mbox{}+\mu_1\sum_{i=1}^{\infty}P_{j+1,i-1}+\mu_2\sum_{i=0}^{\infty}
+P_{j,i+1}.
+\end{eqnarray*}
+By gathering similar terms and summing, the above equation simplifies to
+\begin{eqnarray*}
+\frac{dP_j}{dt} & = & -\left(\gamma_1 +\mu_1\right)P_j
++\gamma_1P_{j-1}+\mu_1P_{j+1},\hspace{1.25in}j=1,2,3...
+\end{eqnarray*}
+which is identical to (\ref{eq:kolt4}) developed for the single M/M/1 queue.
+This is true because the addition of
+the second queue does not effect the first in any manner. If, however,
+there was feedback from the second queue to the first then this result
+would no longer hold.
+
+The equation for $dP_i/dt$ for the second queue will now be derived
+to show how the joint probability state must be decoupled to
+obtain the independent queue probability equations.
+
+\subsection{Closure Approximations for the Tandem Queue}
+The approximations by Clark and Chang/Wang were shown in the previous
+chapter to be most accurate for the M/M/1 queue. In this section, we will
+investigate the extension of these approximations for the tandem queue.
+The resulting equation for $dM_2/dt$ is
+\begin{equation}
+\frac{dM_2}{dt}=\gamma_2+\mu_1\left(1-P0_1\right) - \mu_2\left(1-P0_2\right).
+\label{eq:dm2}
+\end{equation}
+
+To derive $dV_2/dt$, we differentiate (\ref{eq:v2}) to obtain
+\begin{equation}
+\frac{dV_2}{dt}=\sum_{i=1}^{\infty}i^2\cdot \frac{dP_i}{dt} -
+2M_2\cdot \frac{dM_2}{dt}.
+\label{eq:dv2a}
+\end{equation}
+
+\section{Implementation and Results}
+Clearly, there are two issues concerning the accuracy of the closure
+approximations in a tandem queue. The first is the accuracy of the assumption
+of independent queues. When is the assumption that $P0_2$ is independent on the
+state of the first queue a good one? Also, what error results from the
+approximation for $V_2(t)$ via (\ref{eq:dv2a})? The second concern is how well
+the closure approximations model the independent tandem queue. Since the
+independence assumption makes the tandem queue a network of two M/M/1 queues,
+the second issue was largely answered in the previous chapter. Therefore this
+chapter will be dedicated to investigating the performance of
+the independent queue assumption~\cite{JS:2}.
+
+\subsection{Test Conditions}
+Three approximations were compared against the truncated Kolmogorov solution
+for the tandem queue: the independent Kolmogorov solution, Chang/Wang's
+approximation, and Clark's approximation. The test cases were the same as
+those discussed in Chapter~\ref{ch:int}, except that cases with $\rho$ close to
+or greater than one could not be included. This is because the truncated
+Kolmogorov equation set models the tandem queue as two dependent M/M/1/k
+queues, requiring the integration of $k^2$ equations. If $\rho$ becomes too
+large then the probability of being in a state
+with greater than $k$ in a queue can no longer be neglected, resulting in
+mean and variance inaccuracies. We used $ k= 50 $ which limited $\rho \le 0.8$.
+
+\subsection{Results}
+The approximations all performed well for most of the conditions presented.
+The most accurate of the three was the Kolmogorov independent solution by
+a very small margin over Clark. Chang/Wang's method also was accurate, but
+it encountered difficulty with the high $M_0$, low utilization cases. See
+Table~\ref{tab:nsta} for the full comparison.
+\begin{table}[p]
+\caption{Results for Nonstationary M/M/1 Queue}
+\label{tab:nsta}
+\vspace{0.125in}
+\begin{center}
+\begin{tabular}[b]{|r|r|r|r|r|r|r|r|r|r|r|}
+\hline
+\multicolumn{3}{|l|}{Test case }&\multicolumn{8}{c|}{Average Percent Error,
+$e_{ave}$, in \%}\\ \cline{4-11}
+\multicolumn{3}{|l|}{parameters} &
+\multicolumn{1}{c|}{John.} &
+\multicolumn{1}{c|}{Rider} &
+\multicolumn{2}{c|}{Rothkopf} &
+\multicolumn{2}{c|}{Chang} &
+\multicolumn{2}{c|}{Clark} \\ \hline
+\multicolumn{1}{|c|}{$\frac{\lambda}{\mu}$} &
+\multicolumn{1}{c|}{$a$} &
+\multicolumn{1}{c|}{$T$} &
+\multicolumn{1}{c|}{$M(t)$} &
+\multicolumn{1}{c|}{$M(t)$} &
+\multicolumn{1}{c|}{$M(t)$} &
+\multicolumn{1}{c|}{$V(t)$} &
+\multicolumn{1}{c|}{$M(t)$} &
+\multicolumn{1}{c|}{$V(t)$} &
+\multicolumn{1}{c|}{$M(t)$} &
+\multicolumn{1}{c|}{$V(t)$} \\ \hline \hline
+0.5&1.0&10 &28.96 &9.77 &1.98 &11.27 &3.39 &5.00 &0.05 &0.47 \\
+0.5&1.0&20 &28.35 &11.75 &4.28 &21.06 &6.21 &9.37 &0.17 &0.65 \\
+0.5&1.0&40 &25.76 &14.24 &7.32 &32.02 &10.60 &16.07 &0.64 &1.96 \\
+0.5&1.0&60 &24.25 &16.48 &8.65 &33.88 &9.97 &19.25 &1.03 &2.47 \\
+0.5&1.0&80 &22.17 &17.04 &8.99 &32.19 &15.68 &17.41 &1.24 &2.70 \\
+0.5&1.0&100 &19.60 &14.92 &8.18 &20.33 &14.77 &18.63 &1.17 &2.75 \\
+0.5&1.0&120 &17.45 &13.03 &4.51 &11.37 &6.60 &21.80 &0.86 &2.19 \\
+\hline \hline
+0.9&0.25&10 &12.26 &4.82 &2.52 &9.26 &1.27 &4.50 &0.19 &0.67 \\
+0.9&0.25&20 &7.59 &3.71 &2.37 &11.26 &1.08 &4.39 &0.17 &0.76 \\
+0.9&0.25&40 &6.44 &3.81 &1.72 &13.10 &1.50 &5.65 &0.47 &1.20 \\
+0.9&0.25&60 &7.08 &4.13 &2.12 &14.26 &2.05 &7.72 &0.85 &1.71 \\
+0.9&0.25&80 &7.88 &4.37 &2.74 &15.13 &2.64 &10.26 &1.23 &2.20 \\
+0.9&0.25&100 &8.47 &4.65 &3.41 &15.79 &3.22 &13.22 &1.58 &2.73 \\
+0.9&0.25&120 &8.89 &5.09 &3.96 &16.25 &3.89 &16.52 &1.88 &3.27 \\
+\hline
+\end{tabular}
+\end{center}
+\end{table}
+The comparable performance of the approximations is shown in
+Fig.~\ref{fig:avet1}.
+\begin{figure}
+\vspace{8.0in}
+\caption{$e_{ave}$ for stationary tandem queue, $M_0=0$.}
+\label{fig:avet1}
+\end{figure}
+The Appendix also contains plots
+for the worst case percent error and the mean-square error.
+
+As can be seen from Table~\ref{tab:cpu}, Chang's method is much faster than the
+rest of the approximations.
+\begin{table}
+\begin{center}
+\caption{CPU Times for Stationary Tandem Queue}
+\label{tab:cpu}
+\vspace{0.125in}
+\begin{tabular}[b]{|r|r|r|r|r|r|}
+\hline
+\multicolumn{2}{|l|}{Test case }&\multicolumn{4}{c|}{CPU time for VAX 8650
+, in secs.}\\ \cline{3-6}
+\multicolumn{2}{|l|}{parameters} &
+\multicolumn{1}{c|}{Exact} &
+\multicolumn{1}{c|}{Independent} &
+\multicolumn{1}{c|}{ } &
+\multicolumn{1}{c|}{ } \\ \cline{1-2}
+\multicolumn{1}{|c|}{$\frac{\lambda}{\mu}$} &
+\multicolumn{1}{c|}{$T_{final}$} &
+\multicolumn{1}{c|}{Kolmogorov} &
+\multicolumn{1}{c|}{Kolmogorov} &
+\multicolumn{1}{c|}{Chang} &
+\multicolumn{1}{c|}{Clark} \\ \hline \hline
+0.1 &39 &20.76 &0.51 &0.08 &0.16 \\
+0.3 &56 &24.21 &0.48 &0.07 &0.27 \\
+0.6 &120 &44.96 &0.84 &0.04 &0.43 \\
+0.8 &300 &119.89 &2.27 &0.05 &1.44 \\
+\hline
+\end{tabular}
+\end{center}
+\end{table}
+Clark's method also provides significant
+computational savings over both the dependent and the independent
+Kolmogorov methods. As is usually the case, increased accuracy and information
+accompanies increased computation.
+
+This concludes the study of the tandem queue. To summarize, both Clark's and
+Chang/Wang's performed strongly for all tests when $\rho > 0.3$. For low utilization
+cases, the approximations incurred larger errors with respect to $e_{ave}$
+and $e_{wor}$. This however was due to numerical accuracy problems
+for small values of the mean coupled with large values (close to one) of $P0$
+in both queues. The $e_{wor}$ criterion in the Appendix did not show any model
+weakness for the low utilization cases.