\documentclass[12pt,a4paper]{article} % you HAVE TO use the article class % you HAVE to use the options 12pt and a4paper \usepackage{mmb} % you HAVE TO use the mmb.sty style % download this style from % http://pnpm2001.informatik.rwth-aachen.de/docs/mmb01.html \pagestyle{empty} % make sure not to print page numbers % here you can put your own packages: \usepackage{graphicx} % you can define local macros: \newcommand{\mat}[1]{\ensuremath{{\bf #1}}} % boldface font for matrices \newcommand{\vt}[1]{\ensuremath{{\underline{#1}}}} % underline for vectors \begin{document} \title{\bf Characterising Traffic Streams in Networks of MAP$|$MAP$|$1 Queues} % make sure to keep the title in boldface % use the normal author field: \author{Ramin Sadre, Boudewijn Haverkort\\ Laboratory for Performance Evaluation and Distributed Systems\\ Department of Computer Science, RWTH-Aachen, D-52056 Aachen\\ {\tt \{ramin$|$haverkort\}@lvs.informatik.rwth.aachen.de} } \date{} % keep the date field empty \maketitle \thispagestyle{empty} % surpress page number on first page % use the normal abstract environment % use \noindent to start with \begin{abstract} \noindent In this paper we present an approach to characterise, in an approximate but very accurate fashion, the output process of a MAP$|$MAP$|$1 queue as a MAP. In our approximations, the interdeparture time distribution is correctly represented; the correlation structure is approximated to any required degree of accuracy. We derive our approximations directly from the queueing process itself. Various case studies show the feasability and accuracy of our approach. By combining our results with the exact results that are available to merge and split MAPs, we have established all ingredients for a decomposition procedure for open networks of MAP$|$MAP$|$1 queues. In a separate paper we will report on the details of such a procedure. \end{abstract} % here is where the main body of the paper starts \section{Introduction} Efficient and exact algorithms for the evaluation of open queueing network models only exist when the considered models are of a very simple class. Best-known in this context are Jackson queueing networks \cite{jack57}, in which the service and interarrival time distributions are negative exponential, and in which the routing is fixed and Markovian. A decomposition via the solution of the (first-order) traffic equations then naturally leads to the study of single queues at a time. However, to model modern network systems, more realistic packet (``job'') arrival streams have to be coped with, as well as non-exponential service times. In such cases, the decomposition using the traffic equations becomes more complex and, in fact, only possible in an approximate way. Early work in this area, that is, for the approximate analysis of open networks of G$|$G$|$1 queues, has been reported by K\"uhn \cite{kueh79a} and Whitt \cite{whit83a,whit83b}. An extension ot this approach has been developed by Haverkort {\em et al.} \cite{have98a,sadre99a} in which the service and interarrival time distributions are of phase-type and in which the individual queues are analysed using matrix-gemeotric methods. This is possible due to the quasi-birth-death structure of the resulting per-queue underlying Markov chains. Note that in the latter approach, also finite-buffer queues can be handled. In this paper, we take the previous analyses a step further. In particular, we attempt to study networks of MAP$|$MAP$|$1 queues, that is, networks of queues in which both the service and arrival processes are non-renewal and described as Markovian arrival processes (MAPs; see Section~\ref{s:map}). The motivation for this choice is the fact that complex arrival patterns, for instance those appearing in the Internet, can best be described using MAPs. Furthermore, also complex services that may depend upon one another can also be described using MAPs. Attempts to approximate the non-renewal service and arrival processes with renewal processes often lead to inaccurate analysis results. In order to still study networks of such queues, we have to characterise the output process of MAP$|$MAP$|$1 queues, in order to use these as input processes for queues further downstream in the queueing network. Unfortunately, the output process of a MAP$|$MAP$|$1 queue is not a finite MAP. Hence, the aim of this paper is to construct approximate representations of the output process of MAP$|$MAP$|$1 queues that are still finite MAPs. If we succeed in this, we can develop a decomposition approach as has been done in \cite{have98a,sadre99a}, but now in an more general, non-renewal context. The problem we are addressing in this paper is not new and has been recognised by authors as well. Recently, Green {\em et al.} \cite{Green2000} analysed the output process of MAP$|$PH$|$1 queues; also in their case, the output process is not a finite MAP. Heindl recently proposed to approximate the output process of an MMPP$|$G$|$1$[|K]$ queueing systems using a semi-Markov process \cite{MMPPHeindl}, to be used for the analysis of tandem queueing networks. In this paper we extend the approach of Green {\em et al.} in that we consider MAPs as service processes, and in that we allow for more freedom in the process of making the infinite MAP finite. We compare our results with the approach based on renewal processes (as advocated in \cite{have98a,sadre99a}), as well as with discrete-event simulations. Early results of our implementation are promising. The paper is further organised as follows. In Section~\ref{s:map} we introduce MAPs and discuss the most important properties of such processes. Section~\ref{s:queue} then presents the analysis of the MAP$|$MAP$|$1 queue, thereby focussing on the exact departure process, as well as on the families of departure process approximations. In Section~\ref{s:eval} we then present evaluation results and comparisons to discrete-event simulations. Section~\ref{s:concl} concludes the paper. \section{The Markovian arrival process} \label{s:map} We first consider MAPs in Section~\ref{s:map-def}. Then, we discuss their interarrival time characteristic in Section~\ref{s:map-char} and their joining and splitting in Section~\ref{s:map-joinsplit}. \subsection{Definition} \label{s:map-def} MAPs are stochastic processes where the interarrival times are controlled by a continuous-time Markov chain with marked transitions. Such a CTMC has an infinitesimal generator matrix \mat{Q} which is splitted into two matrices \mat{Q_0} and \mat{Q_1} as follows: $$ \mat{Q_0} = \left(\begin{array}{cccc} -q_1 & q_{12} & \ldots & q_{1m}\\ q_{21} & -q_2 & \ldots & q_{2m}\\ \vdots & \vdots & \ddots & \vdots\\ q_{m1} & q_{m2} & \ldots & -q_{m} \end{array}\right),\quad \mat{Q_1} = \left(\begin{array}{cccc} 0 & a_{12} & \ldots & a_{1m}\\ a_{21} & 0 & \ldots & a_{2m}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m1} & a_{m2} & \ldots & 0 \end{array}\right), $$ with $\mat{Q}=\mat{Q_0} + \mat{Q_1}$ and $q_i=\sum^m_{j=1, j\neq i} (q_{ij}+a_{ij})$. The elements of the matrix \mat{Q_1} give the transition rates of the marked transitions: passing through such a marked transition triggers an arrival event. Some general results of the Markov-modulated Poisson process (MMPP) \cite{MMPPCookbook} can be easily adapted to the MAP. In the following we will state the most important ones. \subsection{Interarrival time characteristics} \label{s:map-char} In order to compute the behaviour of a MAP $(\mat{Q_0},\mat{Q_1})$ we first need to choose the initial probability vector \vt{p} of the MAP. In analogy to phase-type distributions we start the MAP at an ``arbitrary'' arrival epoch by choosing $$\vt{p} = \frac{1}{\vt{\pi} \mat{Q_1} \vt{e}} \vt{\pi} \mat{Q_1},$$ where $\vt{\pi}$ is the steady state probability vector of the MAP, i.e., $\vt{\pi} (\mat{Q_0}+\mat{Q_1}) =\vt{0}$. The thus-obtained process is said to be \emph{interval-stationary} \cite{MMPPCookbook}. The interarrival time distribution function of the interval-stationary process is given by $$ F(t)=1-\vt{p} \exp(\mat{Q_0} t) \vt{e}, $$ which leads to the following expression for the $k$th moment of the interarrival time \cite{MMPPCookbook}: $$ E[T^k] = k! \vt{p} (\mat{-Q_0})^{-(k+1)} \mat{Q_1} \vt{e}. $$ Let $T_i$ be the time between the $i$th and the $(i+1)$st arrivals in a MAP. Then, the autocovariance function $R(k)$ for $T_1$ and $T_{k+1}$ with $k\geq 1$ is given by \begin{eqnarray*} R(k) & = & E\left[(T_1-E[T_1])(T_{k+1}-E[T_{k+1}])\right]\\ & = & \vt{p} (-\mat{Q_0})^{-2} \mat{Q_1} \left\{\left[(-\mat{Q_0})^{-1}\mat{Q_1}\right]^{k-1}-\vt{e}\vt{p}\right\} (-\mat{Q_0})^{-2}\mat{Q_1} \vt{e}. %R(k) & = & E\left\{T_1 T_{k+1}\right\}\\ % & = & \vt{p} (-\mat{Q_0})^{-2} \mat{Q_1} \left[(-\mat{Q_0})^{-1}\mat{Q_1}\right]^{k-1}(-\mat{Q_0})^{-2}\mat{Q_1} \vt{e} \end{eqnarray*} %For $R(0)$, we have %$$ R(0) = E\left\{T_1^2\right\} = 2 \vt{p}(-\mat{Q_0})^{-3} \mat{Q_1} \vt{e} $$ \noindent The limiting index of dispersion $I$ of a MAP is given by \cite{MMPPHeindl} $$ I = \lim_{t\to \infty} {\mbox{Var}[N(t)]\over E[N(t)]} = 1+2\left(\vt{\pi} \mat{Q_1}\vt{e}-\frac{1}{\vt{\pi}\mat{Q_1}\vt{e}}\pi \mat{Q_1} (\mat{Q}+\vt{e}\vt{\pi})^{-1}\mat{Q_1}\vt{e}\right), $$ where $N(t)$ is the counting process of the MAP. \subsection{Joining and splitting} \label{s:map-joinsplit} The class of MAPs is closed under joining and probabilistic splitting. The superposition of two MAPs $(\mat{A_0},\mat{A_1})$ and $(\mat{B_0},\mat{B_1})$ is a new MAP $(\mat{C_0},\mat{C_1})$ with $$ \mat{C_0} = \mat{A_0} \oplus \mat{B_0}, \quad \mat{C_1}= \mat{A_1} \oplus \mat{B_1},$$ where $\mat{L}\oplus \mat{M} = \mat{L}\otimes \mat{I} + \mat{I}\otimes \mat{M}$, and $\otimes$ is the tensor product operator. The probabilistic splitting of a MAP $(\mat{A_0},\mat{A_1})$ with probability $r$ gives two MAPs $(\mat{B_0},\mat{B_1})$ and $(\mat{C_0},\mat{C_1})$ with \begin{eqnarray*} (\mat{B_0},\mat{B_1}) & = & ( \mat{A_0}+(1-r)\mat{A_1}, r\mat{A_1} ),\\ (\mat{C_0},\mat{C_1}) & = & ( \mat{A_0}+r\mat{A_1}, (1-r)\mat{A_1} ). \end{eqnarray*} \section{The MAP$|$MAP$|$1 queue} \label{s:queue} We first present the CTMC underlying a MAP$|$MAP$|$1 queue in Section~\ref{s:queue-ctmc}, after which we discuss the departure process of such a queue in detail in Section~\ref{s:queue-dept}. \subsection{The underlying Markov chain} \label{s:queue-ctmc} In a MAP$|$MAP$|$1 queue both the arrival process and the service process are MAPs. The underlying infinite Markov chain of such a queue can be considered as a special case of a quasi-birth-and-death process (QBD) \cite{NeutsMatrixGeom} where each \emph{level} of the QBD state space corresponds to a specific number of customers in the queueing system. Let $(\mat{\Lambda_0},\mat{\Lambda_1})$ be the arrival MAP with $l$ states and $(\mat{S_0},\mat{S_1})$ the service MAP with $m$ states. Then the underlying QBD has the following generator matrix \begin{equation} \mat{Q} = \left( \begin{array}{ccc} \mat{B_0} & \mat{A_0} \\ \mat{B_1} & \mat{A_1} & \mat{A_0}\\ \mat{0} & \mat{A_2} & \mat{A_1}\\ & \ddots & \ddots \end{array} \right), \label{e:Q} \end{equation} with \begin{eqnarray*} \mat{B_0} & = & \mat{\Lambda_0} \otimes \mat{I},\\ \mat{B_1} & = & \mat{I} \otimes \mat{S_1},\\ \mat{A_0} & = & \mat{\Lambda_1} \otimes \mat{I},\\ \mat{A_1} & = & \mat{\Lambda_0} \oplus \mat{S_0},\\ \mat{A_2} & = & \mat{I} \otimes \mat{S_1}. \end{eqnarray*} The steady-state probability vector \vt{\pi} has the following structure $$ \vt{\pi} = \left(\begin{array}{ccc} \vt{v_0} & \vt{v_1} & \ldots \end{array}\right), $$ where each \vt{v_i} is a vector of size $l\cdot m$ and contains the steady-state probabilities for the states of level $i$ in the QBD. In the following, we assume that matrix-geometric solution methods, like the LR-approach \cite{LRQBD}, are used to compute \vt{\pi}. Matrix-geometric solution methods are based on the fact that the vectors \vt{v_i} have the so-called matrix-geometric form $$ \vt{v_i} = \vt{v_0} \mat{R}^i, \quad \mat{R} \in R^{lm\times lm},\quad i=0,1,\ldots, $$ where \mat{R} is the entry-wise smallest non-negative solution of the matrix-quadratic equation $$ \mat{A_0}+\mat{R} \mat{A_1}+\mat{R}^2 \mat{A_2} = \mat{0}. $$ Having obtained \vt{\pi}, many performance measures of the queue can be computed easily, e.g., the moments of the queue length distribution: $$ E[N^k] = \sum_{i=0}^\infty i^k \vt{v_i} \vt{e} = \sum_{i=0}^\infty i^k \vt{v_0} \mat{R}^i \vt{e}, $$ which yields, in case $k=1$: $$ E[N] = \vt{v_0} \mat{R} (\mat{I}-\mat{R})^{-2} \vt{e}. $$ \subsection{The departure process and its approximations} \label{s:queue-dept} We present the exact departure process in Section~\ref{s:dept-exact} and present a simple and a more complex approximation in Section~\ref{s:dept-simple} and \ref{s:dept-complex}, respectively. \subsubsection{The infinite departure process} \label{s:dept-exact} When analysing the departure process of a queue one generally is interested in a description that is of the same class as the description of the arrival process, since then one is able to analyse networks of queues by simply feeding the output of a queue as input for the subsequent queue after the splitting and joining of traffic streams has been handeld. However, in general, queues with infinite buffer produce departure processes with an infinite structure. In the case of MAP$|$MAP$|$1 queues, the output process is an infinite MAP $(\mat{D_0},\mat{D_1})$ which can easily be obtained by modifying the underlying Markov chain of the queue: since each service completion corresponds to an ``arrival'' in the departure process we obtain \mat{D_0} and \mat{D_1} directly from the generator (\ref{e:Q}) by marking the transitions of the sub-matrices \mat{B_1} and \mat{A_2} as ``arrival'' transitions, as follows: $$ \mat{D_0} = \left( \begin{array}{ccc} \mat{B_0} & \mat{A_0} \\ \mat{0} & \mat{A_1} & \mat{A_0}\\ & \mat{0} & \mat{A_1}\\ & \ddots & \ddots \end{array} \right),\quad \mat{D_1} = \left( \begin{array}{ccc} \mat{0} & \\ \mat{B_1} & \mat{0}\\ & \mat{A_2} & \mat{0}\\ & \ddots & \ddots \end{array} \right). $$ This representation of the departure process is exact but ---due to its infinite size--- not practical for further use, e.g., as arrival MAP for a subsequent MAP$|$MAP$|$1 queue. Hence, our primary goal is to find a finite approximation of the departure MAP which is as small as possible but well matches the characteristics, i.e., the interarrival time distribution and the correlation structure, of the original MAP. \subsubsection{Simple finite approximation of the departure process} \label{s:dept-simple} In \cite{Green1998}, Green presented an approach to approximate the departure process of MAP$|$PH$|$1 queues by a finite MAPs. This approach can be easily extented\footnote{Actually, we developed our approach while not being aware of \cite{Green1998}.} to MAP$|$MAP$|$1 queues. The thus obtained MAP will have two important characteristics: \begin{enumerate} \item It {\em exactly} describes the inter-departure time distribution of the original departure process. \item It is able to describe the correlation structure of the original departure process {\em at arbitrary precision} albeit at the cost of an arbitrary large state space. \end{enumerate} The second characteristic implies that, depending on the required quality of the approximation, the obtained MAP may become so large that other reduction methods must be applied afterwards. The approximation is based on the structural equality of the infinite departure MAP and the underlying CTMC of the QBD: each level in the QBD has its corresponding entries in the matrices of the departure MAP. However, it often is not required to represent all levels of the QBD in the departure process. Since the probability $\vt{v_i} \vt{e}$ to be in level $i$ decreases with increasing $i$, there is an integer $s$ where $\vt{v_s} \vt{e}$ becomes so small that one may decide not to represent the levels $s$ and higher in full detail in the departure process. In the following we assume $s>1$, i.e., level $s$ is not adjacent to the border level $0$. We transform the infinite (exact) departure process into a finite (approximated) departure process by replacing the levels $s$ and higher by only \emph{one} level, the s-called called {\em clipping level} $\widehat{s}$. The transition rates leaving and entering level $\widehat{s}$ are computed as follows: \begin{itemize} \item Changing to level $\widehat{s}$ from level $s-1$ corresponds to changing to level $s$ from $s-1$ in the original departure process. \item Staying in level $\widehat{s}$ without an arrival in the departure process corresponds to staying in level $s'$ or changing from level $s'$ to $s'+1$ (for all $s'\geq s$) in the original departure process. \item Finally, an arrival in the original departure process from a state $i$ in the level $s' \in \{s,\dots\}$ may either lead to: \begin{itemize} \item[(i)] level $s'-1=s-1$: this corresponds to an arrival that leads from level $\widehat{s}$ to $s-1$, which happens with probability $$\frac{1}{|v_{s,i}|+|v_{+,i}|} v_{s,i},$$ \item[(ii)] level $s'-1 \neq s-1$: this corresponds to an arrival that leads from level $\widehat{s}$ to $\widehat{s}$, which happens with probability $$\frac{1}{|v_{s,i}|+|v_{+,i}|} v_{+,i},$$ \end{itemize} where \vt{v_{+}} is the steady-state probability to be in a level higher than $s$ in the original QBD, that is: \begin{eqnarray*} \vt{v_{+}} & = & \sum_{i>s} \vt{v_i} = \sum_{i=s+1}^\infty \vt{v_0}\mat{R}^i\\ & = & \vt{v_0} \mat{R}^{s+1} (\mat{I}-\mat{R})^{-1}. \end{eqnarray*} \end{itemize} \noindent These considerations yield the finite appromixation MAP of the departure process: \begin{eqnarray*} \mat{D_0} & = & \left( \begin{array}{ccccc} \mat{B_0} & \mat{A_0} \\ \mat{0} & \mat{A_1} & \mat{A_0}\\ & \mat{0} & \mat{A_1}\\ & \ddots & \ddots & \ddots\\ & & & \mat{A_0}\\ & & & \mat{A_0} + \mat{A_1} \end{array} \right), \mbox{ and}\\ \mat{D_1} & = & \left( \begin{array}{ccccc} \mat{0} \\ \mat{B_1} & \mat{0}\\ & \mat{A_2} & 0\\ & & \ddots & \ddots\\ & & & \mat{0}\\ & & & \mat{A_{2,down}} & \mat{A_{2,stay}} \end{array} \right), \end{eqnarray*} with \begin{eqnarray*} (\mat{A_{2,down}})_{ij} & = & \frac{1}{v_{s,i}+v_{+,i}} v_{s,i} A_{2,ij},\\ (\mat{A_{2,stay}})_{ij} & = & \frac{1}{v_{s,i}+v_{+,i}} v_{+,i} A_{2,ij}. \end{eqnarray*} \subsubsection{Extended approximation method} \label{s:dept-complex} In the previous section we explained how the set $\{s,s+1,\ldots\}$ of levels for given $s$ can be merged into one level. Certainly, this merging operation can be applied to any finite set $\{s,s+1,\ldots,t\}$ of levels, too. All we need to know are the probabilities to be in one of the border levels $s$ or $t$ of the set and the probability to be in the set $\{s,s+1,\ldots,t\}$ which are given by subvectors of $\vt{\pi}$. We define $ \vt{v_{seq}}=\sum_{i=s}^{t} \vt{v_i}$. Replacing the levels $s$ through $t$ in the original departure process by one level results in the following MAP: \begin{eqnarray*} \mat{D_0} & = & \left( \begin{array}{ccccccc} \mat{B_0} & \mat{A_0}\\ \mat{0} & \mat{A1}\\ & 0 & \ddots\\ & & & \mat{A_0}\\ & & & \mat{A_1}+\mat{A_{0,stay}} & \mat{A_{0,up}}\\ & & & 0 & \mat{A_1}\\ & & & & 0 & \ddots \end{array} \right), \\ \mat{D1} & = & \left( \begin{array}{ccccccc} 0\\ \mat{B_1} & 0\\ & \mat{A_2} & \ddots\\ & & & 0\\ & & & \mat{A_{2,down}} & \mat{A_{2,stay}}\\ & & & & \mat{A_2} & \ddots \end{array} \right), \end{eqnarray*} with \begin{eqnarray*} (\mat{A_{0,up}})_{ij} & = & \frac{1}{v_{seq,i}} v_{t,i} A_{0,ij},\\ (\mat{A_{0,stay}})_{ij} & = & \frac{1}{v_{seq,i}} (v_{seq,i}-v_{t,i}) A_{0,ij},\\ (\mat{A_{2,stay}})_{ij} & = & \frac{1}{v_{seq,i}} (v_{seq,i}-v_{s,i}) A_{2,ij},\\ (\mat{A_{2,down}})_{ij} & = & \frac{1}{v_{seq,i}} v_{s,i} A_{2,ij}. \end{eqnarray*} \noindent Combined with the method of the previous section we are able to create finite approximations of the departure process whose quality and size can be controlled in many ways by choosing the number and the position of the here described compacting operations. It should be noted that this approach, as well as the approach presented in the previous section, always yields a MAP with exactly the same interarrival distribution as the original departure process. \section{Evaluation of the approximation methods} \label{s:eval} In Section~\ref{s:eval-case1} we evaluate our approach when used with renewal external arrivals, whereas we apply non-renewal arrival processes in Section~\ref{s:eval-case2}. We study effects of queue utilisation in Section~\ref{s:eval-case3}. \subsection{Case 1: renewal input processes} \label{s:eval-case1} \subsubsection*{The queueing system studied} We start our evaluation with the analysis of a simple MAP$|$MAP$|$1 queue using an Erlang-2 service process with service rate $1.9$. The queue is fed by a hyper-exponential renewal process with MAP representation $$\left(\left(\begin{array}{cc} -3.39 & 0 \\ 0 & -0.21 \end{array}\right), \left(\begin{array}{cc} 3.19 & 0.2\\ 0.2 & 0.01 \end{array}\right)\right).$$ The arrival rate and coefficient of variation are $1.8$, respectively $8.0$. When analysing this queue we can see that the high load of nearly $95\%$ and the high variance of the input process lead to a high mean queue length of $73.11$ with the corresponding slowly decaying queue length distribution function (Figure~\ref{n_prob}). \begin{figure} \begin{center} \includegraphics[scale=1.0]{n_prob.ps} \end{center} \caption{Complementary distribution function (cF) of the queue length (Case 1)} \label{n_prob} \end{figure} \subsubsection*{Characteristics of the approximated departure process} First, we investigate the departure process approximated by the simple approximation method presented in Section~\ref{s:dept-simple}. How does the quality of the approximation depend on the choice of the clipping level? In view of the remarks made about the queue length distribution it is clear that a high clipping level is required to preserve the characteristics of the original departure process. To illustrate this, we have computed the approximated departure process for four different clipping levels, namely 17, 33, 49 and 65. For these cases, the autocovariance functions $R(k)$, as defined in Section~\ref{s:map-char}, are shown in Figure~\ref{simplecovar}. Choosing 33 as clipping level seems to result in a good approximation to the autocovariance function of the exact departure process (which has not been shown here because it nearly is equal to the 65-approximation). \begin{figure} \begin{center} \includegraphics[scale=1.0]{simplecovar.ps} \end{center} \caption{Autocovariance function $R(k)$ of the approximate departure MAP for clipping levels 17, 33, 49 and 65 (Case 1)} \label{simplecovar} \end{figure} These results show that even MAPs with low clipping level can give a good approximation of the correlation structure at small time lags $k$. For the approximation of correlation at large time lags, MAPs must be choosen which respect the structure of the higher levels of the queue QBD. Figure~\ref{simplecovar} shows that the autocovariance function of MAPs with low clipping level quickly drops to 0 (i.e., to the behaviour of uncorrelated renewal processes) with increasing time lag. However, the figure additionally shows that clipping levels which are considerably smaller than the mean queue length yield good approximations to the exact departure process. This may be surprising since clipping levels like 65 only catch 55\% of the queue length distribution probability (Figure~\ref{n_prob}). But we should note that many important characteristics of queue processes, like the busy period, are mainly represented by the lower levels. In fact, Green proved for MAP$|$PH$|$1 queues in~\cite{Green2000} that the $k$-level approximation captures the first $k-1$ correlation coefficients of the departure process exactly. As next step, we use the fact that high clipping levels lead to increased correlation for large time lags by introducing the approximation method presented in Section~\ref{s:dept-complex}. To evaluate its impact, we choose the 33-level MAP as reference. It is of moderate size (134 states; which can be easily handled computationally) and is a good approximation to the exact solution. We now compare the 33-level MAP with a MAP \emph{of the same size} but constructed as follows: (i) levels 0 and 1 are modelled without approximation, (ii) levels 2 through 63 are merged two by two, and (iii) the levels beyond 63 are merged into one level. This MAP (called 2-64-level MAP) is compared with the 33-level and the 65-level MAP in Figure~\ref{twotwocovar}. For $k \geq110$ this MAP better approximates the exact solution as the 33-level MAP. However for $k \leq110$ its autocovariance is apparently lower than the 33-level solution: since the 2-64-level MAP approximates the levels from 2 through 63 two by two it gives a worse description of correlation between subsequent queue departure. Even slightly better approximations can be obtained by using more complex level schemes, e.g., a 4-40-84-level MAP with the following structure: (i) levels 0 through 3 are modelled exactly, (ii) levels 4 through 39 are merged two by two and (iii) levels 40 through 83 are merged four by four (clipping level is 84). Figure~\ref{fourfourcovar} shows this MAP in comparision with the other approximations. \begin{figure} \begin{center} \includegraphics[scale=1.0]{twotwocovar.ps} \end{center} \caption{Autocovariance function $R(k)$ of the 2-64-level MAP (Case 1)} \label{twotwocovar} \end{figure} \begin{figure} \begin{center} \includegraphics[scale=1.0]{fourfourcovar.ps} \end{center} \caption{Autocovariance function $R(k)$ of the 4-40-84-level MAP (case 1)} \label{fourfourcovar} \end{figure} \subsubsection*{Analysis results of MAP$|$MAP$|$1 tandem queues} In the previous section we have presented and compared different approximations to the output process of an MAP$|$MAP$|$1 queue. These approximations have the same interarrival time distribution but differ in higher order statistics as the autocovariance. It is well known that the presence of autocorrelation in arrival processes heavily impacts the performance measures of queueing systems \cite{Livny93}. Hence, in this section, we will examine how the different approximations affect the performance of a subsequent second queue which takes the (approximated) departure process of the first queue as arrival process. As for the first queue, we choose for this queue as service process an Erlang-2 process with service rate $1.9$. Table~\ref{en_results} shows the mean value of its queue length as a function of the chosen approximated departure process. The first row also presents the 95\% confidence interval produced by simulation. The second row states the results computed by the queueing analysis tool {FiFiQueues} \cite{sadre99a} which approximates queue departure processes by renewal processes. The remaining rows show the results obtained with the new method and compares them with the simulation. The relative error (RE) stated in the table is defined as $$ \frac{\mbox{simulation} - \mbox{approximation}}{\mbox{simulation}} \cdot 100\%. $$ \begin{table} \begin{center} \begin{tabular}{r|rr} \hline & $E[N]$ & RE\\ \hline Simulation & 22.2 $\pm$ 1.4\\ FiFiQueues & 16.3 & 26.6\%\\ \hline 33 & 19.8 & 10.8\%\\ 2-64 & 20.8 & 6.4\%\\ 4-40-84 & 21.0 & 5.4\%\\ 46 & 21.0 & 5.4\%\\ \hline \end{tabular} \end{center} \caption{Mean queue length for different approximations (Case 1)} \label{en_results} \end{table} \noindent As reported in other publications, these cases shows that increased correlation leads to higher mean queue lengths. This can be explained in a quite intuitive manner by looking at the power spectrum (see also Appendix~\ref{app}) of the discrete function $f(k)=T_k$ where $T_k$ is the interarrival time as defined in Section~\ref{s:map-char}. In Figure~\ref{f:fft}, we show the power spectrum for clipping levels 2, 6 and 11; we see that low-frequency energy, i.e., around $\omega = 0$, increases with the clipping level. This is an important fact, since San-qi Li has shown in~\cite{SanQiLi} that input power in the low-frequency band has a dominent impact on queueing performance. Low frequencies produce long periods of increased workload entering the queue~\cite{Livny93}. \begin{figure} \begin{center} \includegraphics[scale=1.0]{lowcovar_fft.ps} \end{center} \caption{The power spectrum of MAPs for three different clipping levels} \label{f:fft} \end{figure} This example also shows that better approximations do not necessarily require more states, as becomes clear from the last row: a 4-40-84-level MAP with \emph{134} states produces the same mean queue length as a 46-level MAP with \emph{186} states. This is an significant improvement since the complexity of MAP$|$MAP$|$1 queue analysis cubically depends on the number of states in the MAP describing the arrival process. It seems that the good modelling of correlation for large time lags, as provided by the 4-40-84-level MAP, is more important than for small time lags. This observation confirms the results of studies made in the area of self-similar traffic which report that correlation over many time scales may noticeably affect the performance of queueing systems~\cite{Grossglauser1999}. \subsection{Case 2: true Markovian arrival processes} \label{s:eval-case2} In this second case, we show that comparably good results (as before) are obtained with true Markovian arrival processes. The queueing system under study remains unchanged (two queues with Erlang-2 service and service rate 1.9). For the sake of compactness we present only the results of the tandem system analysis; the results for the departure process per se are as good as before. Table~\ref{en_results_poisson} shows the mean queue length at the second queue, obtained by feeding a Poisson process with arrival rate $1.86$ into the first queue. The mean queue length of the first queue is $35.1$. Again, our results are rather good. \begin{table} \begin{center} \begin{tabular}{r|rr} \hline & $E[N]$ & RE\\ \hline Simulation & 27.7 $\pm$ 2.3\\ FiFiQueues & 24.1 & 13.0\%\\ 33 & 26.4 & 4.7\%\\ 4-40-84 & 27.4 & 1.1\%\\ \hline \end{tabular} \end{center} \caption{Mean queue length for different approximations (Case 2; Poisson arrivals)} \label{en_results_poisson} \end{table} Our next arrival process is the superposition of an hyper-exponential renewal process with arrival rate $1.4$ and squared coefficient of variation $8.0$ with an Erlang-2 process with arrival rate $0.4$. The thus-obtained process has the following characteristics: \begin{center} \begin{tabular}{rcr} arrival rate & = & 1.8,\\ $c^2$ & = & 2.2. \end{tabular} \end{center} Since this process is not a renewal process, its limiting index of dispersion for counts considerably differs from its squared coefficient of variation: $I = 6.3$. The mean queue length of the first queue is $58.2$. The results for the mean queue length of the second queue are shown in Table~\ref{en_results_nonrenewal}. The confidence interval for the simulation result is $\pm 2$ with $95\%$ confidence level. Although slightly worse as before, the results are still acceptable. \begin{table} \begin{center} \begin{tabular}{r|rr} \hline & $E[N]$ & RE\\ \hline Simulation & 20.2 $\pm$ 2.0\\ 33 & 18.9 & 6.4\%\\ 2-64 & 19.2 & 4.9\%\\ 4-40-84 & 19.4 & 4.0\%\\ \hline \end{tabular} \end{center} \caption{Mean queue length for different approximations (Case 2; non-renewal arrivals)} \label{en_results_nonrenewal} \end{table} \subsection{Case 3: different load scenarios} \label{s:eval-case3} Finally, we present a scenario for which the more complex departure process approximation does not improve the simple clipping-level approximation. We take the same tandem queueing system as in Case 1, but lower the arrival intensity to $1.6$. This results in a mean queue length of $19.3$ for the first queue. The mean queue length of the second queue is shown in Table~\ref{en_results3}, in case the service rate $\mu=1.9$ (middle column) or 1.7 (right column). \begin{table} \begin{center} \begin{tabular}{r|r|r} \hline & [$\mu=1.9$] & [$\mu=1.7$]\\ & $E[N]$ & $E[N]$\\ \hline Simulation & 7.4 & 45.0\\ \hline %(50 states)& & \\ %11 & 6.7 & 32.6\\ %2-22 & 6.8 & 34.5\\\hline %(90 states) & & \\ 22 & 7.16 & 38.6\\ 2-42 & 7.09 & 39.2\\ \hline \end{tabular} \end{center} \caption{Mean queue length for different arrival processes (Case 3)}\label{en_results3} \end{table} Here, we can find an interesting fact: the last two rows in the middle column (Case $\mu=1.9$) show that the 2-42-level approximation provides worse results than the 22-level approximation. Apperantly, this effect is not present for $\mu=1.7$ (right column). This may be explained by the fact that for $\mu=1.9$ the queue runs with a substantially lower load than in all other experiments presented in this paper. This seems to lead to a lower sensitivity to long-time correlation and the 2-42-level MAP loses its advantage against the 22-level approximation. However, more investigations are needed here, to make this more firm. \section{Conclusion} \label{s:concl} In this paper we have presented an approach to characterise, in an approximate but very accurate fashion, the output process of a MAP$|$MAP$|$1 queue as a MAP. In any case, the interarrival time distribution is correctly represented; the correlation structure is approximated to any required degree of accuracy. By combining this result with the exact results that are available to merge and split MAPs, we have established all ingredients for a decomposition procedure for open networks of MAP$|$MAP$|$1 queues. In a separate paper we will report on that; most probably we will incorporate the new technique in the FiFiQueues tool \cite{sadre99a}. It should be noted at this point, that the MAP respresentations of the traffic streams may become rather large, especially in case we allow for feedback loops in the queueing network. We will then have to use algorithms to reduce the size of the MAPs. We are currently investigating the use of Markovian bisimulation algorithms \cite{hermanns1999,hermanns2000} to perform such reductions; early results are promising. % we use bibtex with style 'plain'. you do not need to % use bibtex, but make sure that your bibliography looks % like if you did!! \bibliographystyle{plain} \bibliography{bibfile,/home/haverkort/bibtex/haverkort} % here is where appendices start \begin{appendix} \section{The power spectrum of a MAP} \label{app} The power spectrum of the discrete process $T_1,T_2,\ldots$ is the Fourier transform of the non-centralized autocovariance function $V(k) = E[X_1X_{k+1}]$. In the spcial case of a MAP $(\mat{Q_0}, \mat{Q_1})$, we have: \begin{eqnarray*} V(k) & = & E\left\{X_1 X_{k+1}\right\}\\ & = & \vt{p} (-\mat{Q_0})^{-2} \mat{Q_1} \left[(-\mat{Q_0})^{-1}\mat{Q_1}\right]^{k-1}(-\mat{Q_0})^{-2}\mat{Q_1}\vt{e} \end{eqnarray*} For $V(0)$ we find: $$ V(0) = E[X_1^2] = 2 \vt{p}(-\mat{Q_0})^{-3} \mat{Q_1} \vt{e}. $$ The Fourier transform $\Phi(\omega)$ is given by: $$ \Phi(\omega) = \sum_{k=-\infty}^{\infty}V(k)e^{-i\omega k}. $$ Since the process is weakly stationary, we have $V(-k)=V(k)$, which leads to \begin{eqnarray} \Phi(\omega) & = & V(0)+\sum_{k=1}^{\infty} V(k)(e^{i\omega k}+e^{-i\omega k})\nonumber\\ & = & V(0) + 2 \vt{C_1}\cdot\sum_{k=1}^{\infty} \left[(\mat{-Q_0})^{-1}\mat{Q_1}\right]^{k-1} \cos(\omega k)\cdot \vt{C_2}, \label{eqn:power} \end{eqnarray} where $\vt{C_1}=\vt{p} (-\mat{Q_0})^{-2} \mat{Q_1}$ and $\vt{C_2}=(-\mat{Q_0})^{-2} \mat{Q_1} \vt{e}$. Using the eigenvectors and eigenvalues of the matrix $(-\mat{Q_0}^{-1}\mat{Q_1}$, a closed-form solution for $\Phi(\omega)$ can be obtained. \end{appendix} % and here is where appendices end \end{document}