diff options
Diffstat (limited to 'obsolete/macros/latex209/contrib/tamueethesis/ch2.tex')
-rw-r--r-- | obsolete/macros/latex209/contrib/tamueethesis/ch2.tex | 309 |
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. |