Next: 2.8.1 Exact aggregation and Up: 2. Background Previous: 2.7.1 Fitting techniques for

2.8 Aggregation techniques

For the analysis of complex Markov chains with large state spaces, decomposition and aggregation techniques are used as tools that reduce the complexity of the solution. The general idea behind decomposition and aggregation is to decompose (divide) the Markov chain in independent subchains which can be solved separately, and then aggregate (combine) the results back together. If a Markov chain can be divided into independent subchains then this Markov chain is completely decomposable. In practice, it is unusual to find completely decomposable Markov chains. However, there are cases where the condition of independent subchains almost holds. These type of Markov chains are called nearly completely decomposable.

A Markov chain is nearly completely decomposable if its state space can be partitioned into subsets such that within the same subset, the states interact strongly with one another, i.e., are strongly connected, while between different subsets the states interact loosely with one another, i.e., are loosely connected. For a CTMC, this means that the cumulative rate between states of the same subset is much higher than the cumulative rate between the states of different subsets [27]. The fundamental formal foundation of decomposition methods for the steady state analysis of queueing systems is due to Simon and Ando [96].

Generally speaking, aggregation and decomposition techniques yield approximate solutions. If they apply to the nearly completely decomposable Markov chains, the relative error can be maintained under a given small constant. If the conditions of nearly decomposable Markov chains do not hold, then the error introduced in the results is considerably large, with the notable exception of product-form queueing networks where the aggregation techniques yield exact solutions. The value of the decomposition and aggregation methodology is two-fold [26]:

• it provides efficient numerical solutions for complex and large Markov chains by dividing the problem into smaller and more tractable subproblems, and
• provides theoretical insights regarding the structure of the process modeled by the Markov chain.

Subsections

Next: 2.8.1 Exact aggregation and Up: 2. Background Previous: 2.7.1 Fitting techniques for
Alma Riska 2003-01-13