next up previous contents
Next: Dimensionality reduction with complete Up: Approximations of dimensionality reduction Previous: Approximations of dimensionality reduction   Contents


Dimensionality reduction with partial independence assumption

DR-PI (DR with partial independence assumption) ignores the dependency that the sojourn time in levels $\geq\kappa$ has on how the Markov chain enters levels $\geq\kappa$ (from level $\kappa-1$). Specifically, we assume that $D_{i,j}$ is independent of $i$. Let $D_j' = D_{i,j}$ for all $i$ for each $j$, and let $\widetilde B'$ denote the process that is the same as $\widetilde B$ except that $D_{i,j}$ is replaced by $D_j'$ for all $i$ for each $j$. Figure 3.27(a) shows the Markov chain for the high priority jobs (background process) that we obtain via DR-PI in the analysis of an M/PH/2 queue with two priority classes. (Recall the Markov chain that we obtain via DR, Figure 3.5 in Section 3.1, where the four types of busy periods are approximated by four PH distributions, respectively.) In DR-PI, the four types of busy periods are represented by two PH distributions, ignoring the dependency that the duration of the busy period has on the phase of the job in service at the beginning of the busy period.

Figure 3.27: Background processes on a finite state space, obtained via (a) DR-PI and (b) DR-CI. Labels on the transitions in the busy periods are omitted for clarity.
\includegraphics[width=.8\linewidth]{fig/MC/PrioPHH-PI.eps}
(a)
\includegraphics[width=.8\linewidth]{fig/MC/PrioPHH-CI.eps}
(b)

In general, we require that process $\widetilde B'$ has the following two key properties:

Hence, $\widetilde B'$ and $B$ would have stochastically the same total sojourn time in levels $\geq\kappa$ in the long run if the second property did not involve the approximation (i.e., if the marginal distribution is fitted exactly). However, $\widetilde B'$ and $B$ have different autocorrelation in the sequence of the sojourn times in levels $\geq\kappa$.

More formally, the generator matrix of $\widetilde B'$, $\mathbf{Q}_{\widetilde B'}$, is determined as follows. Let $(\Vec{M_r'})_j$ be the $r$-th moment of $D_j'$ for $1\leq j\leq \xi$ for each $r\geq 1$. We determine $(\Vec{M_r'})_j$ so that $\widetilde B$ and $\widetilde B'$ have the same marginal $r$-th moment of the sojourn time in levels $\geq\kappa$:

\begin{displaymath} (\Vec{M_r'})_j = \left(\sum_{i=1}^\xi(\Vec{\pi_{\kappa-1}})_... ...appa-1}})_i\cdot(\vec\lambda)_i\cdot(\mathbf{P})_{i,j}\right), \end{displaymath}

where $\Vec{\pi_{\kappa-1}}$ denotes the stationary probability vector that $\widetilde B$ is in level $\kappa-1$, which can be calculated via matrix analytic methods as in Section 3.2. We approximate $D_j'$ by a PH distribution, $(\Vec{\tau_j'},\mathbf{T'}_j)$, matching the first three moments of $D_j'$, $((\Vec{M_1'})_j,(\Vec{M_2'})_j,(\Vec{M_3'})_j)$. Let $\Vec{t_j} = -\mathbf{T'}_j\cdot\vec{1}$ as before. Generator matrix $\mathbf{Q}_{\widetilde B'}$ is then defined by

\begin{displaymath} \mathbf{Q}_{\widetilde B'} = \left(\begin{array}{cccl\vert c... ...\ \hline & & & \mathbf{t'} & \mathbf{T'} \end{array}\right), \end{displaymath}

where $\mathbf{L}_b^{(h)}$, $\mathbf{F}_b^{(h)}$, and $\mathbf{B}_b^{(h)}$ are submatrices of $\mathbf{Q}_b$ as defined in Section 3.5.2,

\begin{eqnarray*} \mathbf{T'} & = & \left(\begin{array}{lll} \mathbf{T'}_1& & \... ...(\mathbf{P})_{\xi,\xi}\cdot\Vec{\tau_\xi'} \end{array}\right). \end{eqnarray*}

Observe that the number of PH distributions used to approximate the sojourn time distributions in levels $\geq\kappa$ is reduced from $\xi^2$, in $\widetilde B$, to $\xi$, in $\widetilde B'$. The next approximation, DR-CI, uses only one PH distribution.

next up previous contents
Next: Dimensionality reduction with complete Up: Approximations of dimensionality reduction Previous: Approximations of dimensionality reduction   Contents
Takayuki Osogami 2005-07-19