Approaches using matrix analytic methods

As we have seen in Section 3.2, matrix analytic methods allow an efficient evaluation of QBD processes with a finite number of phases (1D Markov chain), but they can also be applied to more general processes including M/G/1 and G/M/1 type processes [111,136]. The M/G/1 (respectively, G/M/1) type process generalizes the QBD process, and it allows transitions from level $\ell$ to any levels $\geq \ell-1$ (respectively, $\leq \ell+1$) for each $\ell$. The M/G/1 and G/M/1 type processes can be analyzed efficiently only when they have a finite number of phases (1D Markov chain). The tree process is a multidimensional Markov chain that can be analyzed efficiently via matrix analytic methods, but the class of tree processes is rather limited; specifically, the RFB and GFB processes do not appear to be modeled as a tree process.

A popular approach in applying matrix analytic methods to multidimensional Markov chains is to simply truncate the state space so that the resulting process becomes a 1D Markov chain (QBD process with a finite number of phases) [61,93,94,112,138,160,185,186]. For example, Green [61] and Stanford and Grassmann [185,186] analyze cycle stealing without switching cost (see Section 3.4) by truncating the state space. Likewise, Kao and Narayanan [94], and Ngo and Lee [138] analyze the preemptive priority queue with two classes (see Section 3.4) by truncating the state space. Kao and Narayanan [93], Kao and Wilson [95], and Leemans [112] analyze the nonpreemptive priority queue (see Section 3.4) by truncating the state space. Finally, Rao and Posner [160] analyze the 2D Markov chain for the coupled processor model^3.4 by truncating the state space. In general, the errors that are introduced by ignoring portions of the state space with an infinite number of states can be significant, especially at higher traffic intensities. Note that each of the above systems analyzed in [61,93,94,112,138,185,186] by truncating the state space can be modeled as RFB or GFB process (see Section 3.4), and hence can be analyzed via DR; the coupled processor model that is analyzed in [160] by truncating the state space does not appear to be modeled as RFB or GFB process.

Since simple truncation of the state space can lead to erroneous conclusions [108], recently various truncation/aggregation approaches have been proposed by Green [60], Heindl and Telek [73], and Heindl, Zhang, and Smirni [74]. All of these works propose approaches to decompose tandem queues by approximating the departure process from a queue, which can in general be modeled exactly as a MAP (as defined in Section 2.2) with an infinite number of phases, by a MAP with a finite number of phases. The truncation/aggregation approaches proposed in [60,73,74] are specialized for tandem queues or networks of queues, and it is not clear how they are applied to RFB/GFB processes; on the other hand, tandem queues do not appear to be modeled as RFB/GFB processes. Hence, DR is complementary to the truncation/aggregation approaches proposed in [60,73,74].