Dimensionality reduction of Markov chains (Chapter 3)

Instead of analyzing individual multiserver systems separately, we will define a broad class of multidimensional Markov chains that allow us to model many multiserver systems with resource sharing or job prioritization, and show an (approximate) analysis of these Markov chains. We will refer to these multidimensional Markov chains as RFB/GFB (recursive foreground-background or generalized foreground-background) processes. Also, we will refer to our new analytical method for analyzing the RFB/GFB process as dimensionality reduction (DR). Our analysis of the RFB/GFB process via DR will enable one to analyze the performance of many multiserver systems by simply modeling them as RFB/GFB processes. We will provide many examples of such multiserver systems.

The key idea in the analysis of the RFB/GFB process via DR is the dimensionality reduction of a multidimensional Markov chain: DR reduces (approximates) a multidimensional Markov chain, which is hard to analyze, into a 1D Markov chain, which is easy to analyze. Figure 1.6 illustrates the idea of DR for a simple 2D Markov chain. The 1D Markov chain will be carefully constructed such that the 1D Markov chain well approximates the multidimensional Markov chain.

Figure 1.6: The key idea in DR: dimensionality reduction (2D $\rightarrow$ 1D).

$\Longrightarrow$ DR

Since the analysis of the RFB/GFB process via DR involves approximations, we will extensively validate the accuracy of DR via simulation. We will find that the error in DR is typically within 5% (and often within 1%) with respect to first order metrics (such as mean response time and mean queue length), and within 10% with respect to second order metrics (such as the variance of the queue length).