next up previous contents
Next: Computational complexity of DR, Up: Approximations of dimensionality reduction Previous: Dimensionality reduction with partial   Contents


Dimensionality reduction with complete independence assumption

DR-CI (DR with complete independence assumption) ignores not only the dependency that the length of the sojourn time in levels $\geq\kappa$ has on how the Markov chain enters levels $\geq\kappa$ but also the dependency on how it exits from levels $\geq\kappa$ (to level $\kappa-1$). Specifically, we assume that $D_{i,j}$ is independent of $i$ and $j$. Let $D'' = D_{i,j}$ for all $i$ and $j$, and let $\widetilde B''$ denote the process that is the same as $\widetilde B$ except that $D_{i,j}$ is replaced by $D''$ for all $i$ and $j$. Figure 3.27(b) shows the Markov chain for the high priority jobs (background process) that is obtained via DR-CI in the analysis of an M/PH/2 queue with two priority classes. In DR-CI, the four types of busy periods are represented by a single PH distribution, ignoring the dependency that the duration of the busy period has on the phase of the job in service at the beginning and end of the busy period.

We choose $D''$ such that $\widetilde B''$ has the above two key properties that $\widetilde B'$ has. The difference between $\widetilde B'$ and $\widetilde B''$ lies in the dependencies in the sequence of the sojourn times in levels $\geq\kappa$. Observe that the sequence of the sojourn times in levels $\geq\kappa$ is i.i.d. in $\widetilde B''$, while it has some dependencies in $\widetilde B'$.

More formally, the generator matrix of $\widetilde B''$, $Q_{\widetilde B''}$, is determined as follows. Let $M_r''$ be the $r$-th moment of $D''$ for $r\geq 1$. We determine $M_r''$ so that $\widetilde B''$ and $B$ have the same marginal $r$-th moment of the sojourn time in levels $\geq\kappa$:

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

We approximate $D''$ by a PH distribution, $(\Vec{\tau''},\mathbf{T''})$, matching the first three moments of $D''$, $(M_1'',M_2'',M_3'')$. Let $\Vec{t''} = -\mathbf{T''}\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 ...
...& \Vec{t''}\cdot\Vec{\chi} & \mathbf{T''}
\end{array}\right),
\end{displaymath}

where $\mbox{\boldmath$\tau''$} = \mbox{transpose}(\vec\lambda)\cdot\Vec{\tau''}$, and is a row vector whose $h$-th element is

\begin{displaymath}
(\Vec{\chi})_h = \left(\sum_{i=1}^\xi(\Vec{\pi_{\kappa-1}})_...
...a-1}})_i \cdot(\Vec\lambda)_i \cdot(\mathbf{P})_{i,j} \right).
\end{displaymath}


next up previous contents
Next: Computational complexity of DR, Up: Approximations of dimensionality reduction Previous: Dimensionality reduction with partial   Contents
Takayuki Osogami 2005-07-19