\chapter {Introduction}
\label{ch:int}
\body
The objective of this thesis is to evaluate the performance of several
transient queueing approximations for a network of queues. These
approximations will be tested and characterized for a single M/M/1
and a tandem queue (2 node) network~\cite{JA:1}.
The statistics of queueing systems, such as the mean number in each
queue and the variance, are often computed using steady state assumptions.
In many systems, however, the queue parameters change with time and
steady state assumptions lead to erroneous mean and variance quantities.
It is therefore desirable to solve the transient system. Unfortunately,
solutions to transient queueing systems are difficult to obtain. Although
an analytic solution exists for the single M/M/1 queue, a network of two
such queues remains an open problem. The approximation methods are used reduce
the computational complexity of existing transient solutions and to provide
insight into the behavior of systems for which no analytic solution exists.
It is hoped that this research will serve to improve present methods of
modelling computer networks~\cite{AAJA:1}.
\section{Queueing Theory Background}
Central to interpreting results from any queueing model is the understanding
of the underlying queueing process. If you now refer to Fig.~\ref{fig:pic},
you will see an example of the \LaTeX\ picture environment.
\begin{figure}
\centering
\setlength{\unitlength}{1mm}
\begin{picture}(50,39)
\put(0,7){\makebox(0,0)[bl]{cm}}
\multiput(10,7)(10,0){5}{\makebox(0,0)[b]{\protect\addtocounter{cm}{1}
\arabic{cm}}}
\put(15,20){\circle{6}}
\put(30,20){\circle{6}}
\put(15,20){\circle*{2}}
\put(30,20){\circle*{2}}
\put(10,24){\framebox(25,8){car}}
\put(10,32){\vector(-2,1){10}}
\multiput(1,0)(1,0){49}{\line(0,1){2.5}}
\multiput(5,0)(10,0){5}{\line(0,1){3.5}}
\thicklines
\put(0,0){\line(1,0){50}}
\multiput(0,0)(10,0){6}{\line(0,1){5}}
\end{picture}
\caption{A sample {\bf\tt picture} environment.}
\label{fig:pic}
\end{figure}
Of particular importance are five basic
characteristics~\cite{AB:1}: arrival pattern of customers, service pattern of
servers, queue discipline, system capacity, and the number of service channels.
\section{Network Applications}
The study of a network of queues can be used to provide useful information
for the design and maintenance of computer networks, where several computers
are communicating with each other. On the design side, the modeling of a
network can provide statistics such the average number of packets waiting
to be transmitted at each computer~\cite{MWJCDL:1}.
\section {Solution Methods}
The most common numerical solution to the transient queueing model is found
through the use of the Kolmogorov forward equations~\cite{HC:1}.
This method can handle non-stationary arrival and service rates
and, for reasonable error bounds, provides an exact solution. One equation is
integrated to find the probability of being in a particular state.
\section{Thesis Structure}
Chapter II starts by reviewing some of the fundamentals in queueing theory
upon which the approximations are based. The closure approximations
are presented for the M/M/1 queue and compared to reveal differences
in structure~\cite{ROPC:1}.
In Chapter III the M/M/1 approximations are tested against exact methods for both
stationary and nonstationary arrival patterns. The stationary cases are compared
against exact results from Cantrell~\cite{JS:1,PR:1}, while the
nonstationary cases will be compared to solutions from Kolmogorov forward
equations. Each approximation will
be characterized to show areas of weakness and strength.
In Chapter IV the methods proving to be most
accurate will be tested in a two node feed-forward network, otherwise known
as the tandem queue.
The results are compared against the Kolmogorov forward equation solutions and
results from the previous chapter to see the effect of the first node on the
accuracy of the second node results.
In Chapter V final conclusions are drawn and suggestions for further research
topics are suggested.
An equation using the equation environment
\begin{equation}
\lim_{x\to0}{\sin x\over x}=1,
\end{equation}
and one using the displaymath environment
\begin{displaymath}
\sqrt{1+\sqrt{1+\sqrt{1+x}}}.
\end{displaymath}
are displayed here. Now refer to Fig.~\ref{fig:block} for another example
of what you can do with the \LaTeX\ picture environment.
\begin{figure}
\begin{center}
\setlength{\unitlength}{1in}
\begin{picture}(5,6)
\thicklines
\put(2,4){\framebox(1,0.75){\LaTeX}}
\put(0.5,4){\framebox(1,0.75){User Input}}
\put(3.5,4){\framebox(1.25,0.75){Document Style}}
\put(2,2.25){\framebox(1,0.75){\TeX}}
\put(1.75,0.5){\framebox(1.5,0.75){Printed Document}}
\put(1.5,4.375){\vector(1,0){0.5}}
\put(3.5,4.375){\vector(-1,0){0.5}}
\put(2.5,4){\vector(0,-1){1}}
\put(2.5,2.25){\vector(0,-1){1}}
\end{picture}
\end{center}
\caption{Overall Structure}
\label{fig:block}
\end{figure}