next up previous contents
Next: Analysis of the FB Up: Dimensionality reduction Previous: Dimensionality reduction   Contents


Analysis of the birth-and-death FB process

In this section, we analyze a simplest FB process shown in Figure 3.13. Our goal is to reduce the FB process (2D Markov chain) to a QBD process with a finite number of phases (1D Markov chain) which closely approximates the FB process.

Figure 3.23: An analysis of the FB process in Figure 3.13 via DR. (a) The background process in Figure 3.13(a) is approximated by a Markov chain on a finite state space. (c) The FB process in Figure 3.13(c) is approximated by a 1D Markov chain.
\includegraphics[width=\linewidth]{fig/MC/background-DR.eps}
(a) Approximate background process


\includegraphics[width=.85\linewidth]{fig/MC/foreground.eps}
(b) Foreground process when the background process is in level $d$
\includegraphics[width=\linewidth]{fig/MC/RFBQBD-DR.eps}
(c) 1D FB process

Observe that the infinite number of phases in the FB process stems from the infinite number of states in the background process, $B$ (Figure 3.13(a)). This motivates us to approximate $B$ by a Markov chain with a finite number of states, $\widetilde B$ (Figure 3.23(a)). In process $\widetilde B$, all the states in levels $\geq\kappa$ of process $B$ is aggregated into two states labeled $\geq\kappa$. That is, the sojourn time in levels $\geq\kappa$, $T$, is approximated by a two-phase PH distribution (as defined in Section 2.2) with parameters:

\begin{displaymath} \Vec\tau = (1,0) \quad\mbox{and}\quad \mathbf{T} = \left(\b... ...+\beta_{12}) & \beta_{12} \\ 0 & -\beta_2 \end{array}\right). \end{displaymath}

We use the moment matching algorithm developed in Chapter 2 to choose the parameters of the PH distribution so that the first three moments of $T$ are matched. The sojourn time $T$ is exactly the same as the busy period in an M/M/1 queue where the arrival rate is $f_B$ and the service rate is $b_B$. Thus, the first three moments of $T$ are

\begin{displaymath} \mbox{{\bf\sf E}}\left[ T \right] = \frac{1}{1-\rho}\frac{1}... ...ft[ T^3 \right] = \frac{6(1+\rho)}{(1-\rho)^5}\frac{1}{b_B^3}, \end{displaymath}

where $\rho = \frac{f_B}{b_B}$. The following theorem implies that two phases are sufficient to match these three moments by a PH distribution.

Theorem 8   Let $T$ denote the duration of an M/GI/1 busy period where service demand $G$ has an arbitrary distribution with finite third moment and where the job starting the busy period has size $K$ whose distribution is in ${\cal T}^{(n)}$ (recall Definition 7 in Section 2.1). Then, the distribution of $T$ is in  ${\cal T}^{(n)}$.

A proof of Theorem 8 is postponed to Appendix A. Theorem 8 is useful in determining the sufficient number of phases in a PH distribution to well-represent a busy period duration without explicitly computing the moments of the busy period.

By replacing the background process $B$ by $\widetilde B$, the 2D Markov chain (Figure 3.13(c)) is reduced to a 1D Markov chain shown in Figure 3.23(c). More formally, the 1D Markov chain is a QBD process, and its generator matrix, $\mathbf{Q}$, is obtained via the generator matrix of $\widetilde B$, $\mathbf{Q}_{\widetilde B}$, as follows. First, observe that

\begin{displaymath} \mathbf{Q}_{\widetilde B} = \left(\begin{array}{ccccc} -f_B ... ...B\Vec\tau \\ & & & \Vec{t} & \mathbf{T} \end{array}\right), \end{displaymath}

where $\Vec{t}=-\mathbf{T}\Vec{1}$. Generator matrix $\mathbf{Q}$ is then given by

\begin{displaymath} \mathbf{Q} = \left(\begin{array}{cccc} \mathbf{L}^{(0)}& \ma... ... \mathbf{L}& \ddots\\ & &\ddots & \ddots \end{array}\right), \end{displaymath}

where $\mathbf{F}$ and $\mathbf{B}$ are $(\kappa+2)\times(\kappa+2)$ diagonal matrices,

\begin{displaymath} \mathbf{F} = \left(\begin{array}{ccccc} f_{F,0} & & & & \\ ... ... b_{F,\kappa} & \\ & & & & b_{F,\kappa} \end{array}\right), \end{displaymath}

$\mathbf{L}^{(0)} = \mathbf{Q}_{\widetilde B}-\mathbf{F}$, and $\mathbf{L} = \mathbf{Q}_{\widetilde B}-\mathbf{F} -\mathbf{B}$.

In general, the stationary probabilities in the 1D Markov chain can immediately be translated into the stationary probabilities in the foreground process. On the other hand, the stationary probabilities in the background process needs to be analyzed independently, since its state space is aggregated in the 1D Markov chain. Observe, however, that the background process is easy to analyze, since it is simply a birth-and-death process without dependency on the foreground process.

next up previous contents
Next: Analysis of the FB Up: Dimensionality reduction Previous: Dimensionality reduction   Contents
Takayuki Osogami 2005-07-19