Analysis of the GFB process

Figure 3.24: An analysis of the GFB process via DR.

$\Longrightarrow$

DR

Most of the techniques necessary in the analysis of the GFB process are already provided in the analysis of the FB process. In this section, we describe how we can apply these techniques to the GFB process, where we use a particular GFB process shown in Figure 3.25 as an example. Intuitively, a GFB process can be reduced to a 1D Markov chain by reducing the FB portion (rows $\geq\kappa$) of the GFB process to a 1D Markov chain via DR as illustrated in Figure 3.24. The stationary probabilities in the 1D Markov chain will be immediately translated into those in the foreground process. We will need an additional technique in the analysis of the background process, since the background process in the GFB process depends on the foreground process, and hence cannot be analyzed independently as in the FB process.

Figure 3.25: A GFB process: Threshold-based policy for reducing switching costs in cycle stealing, where $N_D^{th}=2$ and $N_B^{th}=3$.

The Markov chain shown in Figure 3.25 models the number of donor and beneficiary jobs, respectively, in the system under the threshold-based policy for reducing switching costs in cycle stealing (recall Figure 3.18(a)), where $N_D^{th}=2$ and $N_B^{th}=3$. To simplify the analysis, we assume that switching times are zero^3.7. In Figure 3.25, the number of donor jobs (background process) is tracked in the vertical direction, and the number of beneficiary jobs (foreground process) is tracked in the horizontal direction. A state labeled $D$ (respectively, $B$) denotes that the donor server is working or staying idle at the donor's queue (respectively, beneficiary's queue) in the state. Since the background process and the foreground process are independent birth-and-death processes when the number of donor jobs $N_D\geq\kappa\equiv N_D^{th}$, the Markov chain is a GFB process. However, since the background process and the foreground process have complex interaction while $N_D<\kappa$, it is not an FB process.

The GFB process can be reduced to a 1D Markov chain by replacing a portion of the background process, as is done in Section 3.5.2. Figure 3.26(a) shows a portion ( $N_D\geq\kappa\equiv N_D^{th}$) of the background process. In general, a background process in a GFB process has a level $\kappa$ such that the background process is a QBD process while it is in levels $\geq\kappa$. By using the techniques that we have introduced in Section 3.5.2, this portion of the background process can be approximated by a Markov chain on a finite state space as in Figure 3.26(b). By replacing levels $\geq\kappa\equiv N_D^{th}$ of the background process (Figure 3.26(a)) by the Markov chain on a finite state space (Figure 3.26(b)), the GFB process is reduced to a 1D Markov chain as shown in Figure 3.26(c).

Figure 3.26: An analysis of the GFB process in Figure 3.25 via DR. (a)-(b) Levels $\geq\kappa$ of the background process. (c) 1D Markov chain reduced from the GFB process.

Number of donor jobs, $N_D$, given $N_D\geq N_D^{th}$

(a) Markov chain on an infinite state space

$\Longrightarrow$

(b) Markov chain on a finite state space

(c)

The 1D Markov chain reduced from a GFB process is a QBD process and its stationary probabilities can be analyzed via matrix analytic methods as in Section 3.2. As in the analysis of the FB process, the stationary probabilities in the 1D Markov chain can be immediately translated into the stationary probabilities in the foreground process, since the state space of the foreground process is not aggregated in the 1D Markov chain.

By contrast, levels $\geq \kappa+1$ of the background process are aggregated in the 1D Markov chain; thus, the analysis of the stationary probabilities in the background process requires an additional technique. Since levels $\leq \kappa$ of the background process are exactly tracked in the 1D Markov chain, the stationary probabilities in this portion is given by the stationary probabilities in the 1D Markov chain. Note, in particular, that the probability that there are $N_D=\kappa\equiv N_D^{th}$ donor jobs, $\pi_\kappa$, is given by the stationary probability in the 1D Markov chain. Since the background process is a birth-and-death process when $N_D\geq\kappa\equiv N_D^{th}$ (Figure 3.26(a)), the probability that there are $\ell$ jobs, $\pi_\ell$, is obtained recursively by

$$\pi_\ell = \rho\pi_{\ell-1},$$

where $\rho=\frac{\lambda_D}{\mu_D}$, for $\ell\geq\kappa+1$.

In general, the stationary probabilities in levels $\leq \kappa$ of the background process are given by the stationary probabilities in the 1D Markov chain reduced from the GFB process. In particular, the stationary probability vector in level $\kappa$, _, is given by analyzing the 1D Markov chain. Then, the stationary probability vector in level $\ell>\kappa$, _, is given recursively by

$$\Vec{\pi_\ell} = \Vec{\pi_{\ell-1}} \mathbf{R}^{(\ell)},$$

for $\ell\geq\kappa+1$, where $\mathbf{R}^{(\ell)}$'s are the R matrices of the background process that can be calculated by the algorithm shown in Figure 3.12.