2.5.1 Quasi birth-death processes

Consider now a single queue that accepts Poisson arrivals at rate $\lambda$. Jobs require two exponential stages of service: the first at rate $\mu_1$ and the second at rate $\mu_2$. The service time distribution as described is a hypoexponential distribution with $2$ phases, i.e., $Hypo(2)$. This is an M/Hypo$(2)$/1 queue. Each state is defined by $(i, s)$, where $i$ is the number of jobs in the queue and $s$ is the stage of service for the job being served. If we order states lexicographically, then ${\cal{S}}=\{(0,0), (0,1), (0,2), (1,1), (1,2), (2,1), (2,2),...\}$ and the infinitesimal generator matrix ${\mathbf{Q}}_{M/Hypo(2)/1}$ of the process is

$${\mathbf{Q}}_{M/Hypo(2)/1} = \left[ \begin{array}{c c c c c ... ...s &\vdots &\vdots &\vdots &\vdots &\ddots \end{array}\right] ,$$ (2.16)

where $\alpha_j \stackrel{\rm def}{=}\lambda + \mu_j,~j=1,2$. The state transition diagram of this process is illustrated in Figure 2.2. Note that by grouping the entries of the generator matrix of Eq.(2.16) according to the number of jobs in the system, then the structure of the new block partitioned Eq.(2.16) closely resembles the structure of the generator matrix of an M/M/1 queue, shown in Eq.(2.15).

Figure 2.2: The state transition diagram of a M/Hypo$2$/$1$ queue.

We define subvectors of the stationary distribution vector $\mbox{\boldmath {$\pi$}}$ of the process as $\mbox{\boldmath {$\pi$}}^{(i)} \stackrel{\rm def}{=}(\mbox{\boldmath {$\pi$}}_{(i,1)}, \mbox{\boldmath {$\pi$}}_{(i,2)})$ for $i \geq 1$, and $\mbox{\boldmath {$\pi$}}^{(0)}\stackrel{\rm def}{=}(\mbox{\boldmath {$\pi$}}_{(0,0)}, (\mbox{\boldmath {$\pi$}}_{(0,1)}, \mbox{\boldmath {$\pi$}}_{(0,2)})$. Accordingly, we define subsets ${\cal{S}}^{(i)}$ for $i \geq 1$ and ${\cal{S}}^{(0)}$ of the state space ${\cal {S}}$. We call the states on ${\cal{S}}^{(0)}$ the boundary portion of the process and all other states are called the repeating portion or the repeating states of the process^2.5. Throughout this dissertation, it is assumed that the cardinality of the boundary portion of the process is $m$ and the cardinality of each repeating level is $n$, where $m$ may be different from $n$. This partition of the stationary distribution vector $\mbox{\boldmath {$\pi$}}$ and state space ${\cal {S}}$ of the process defines the following submatrices of the infinitesimal generator in Eq.(2.16).

$$\begin{array}{c c c} {\mathbf{F}}= \left[ \begin{array}{c c}... ...c} 0 & 0 & 0 \\ 0 & \mu_2 & 0 \end{array}\right]. \end{array}$$ (2.17)

Based on the above definitions, we can block partition the infinitesimal generator of Eq.(2.16) as follows

$${\mathbf{Q}}_{QDB} = \left[ \begin{array}{c c c c c c c} \wi... ...vdots & \vdots & \vdots & \vdots & \ddots \end{array}\right] ,$$ (2.18)

where ${\mathbf{0}}$ is a matrix of all zeros of the appropriate dimension. The letters ``L'', ``F'', and ``B'' are used to denote the ``local'', `forward'', and ``backward'' transition rates, respectively, in relation to a set of states ${\cal{S}}^{(j)}$ for $j \geq 1$. We use ``$\widehat{~}$'' for matrices related to ${\cal{S}}^{(0)}$. The similarity of infinitesimal generator in Eq.(2.18) with the infinitesimal generator in Eq.(2.15) gives such processes the name ``quasi birth-death'' (QBD). We discuss the solution methods for QBD processes in Chapter 3.