\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.