Next: 2.5.2 GI/M/1-type processes Up: 2.5 Markov chains with Previous: 2.5 Markov chains with

## 2.5.1 Quasi birth-death processes

Consider now a single queue that accepts Poisson arrivals at rate . Jobs require two exponential stages of service: the first at rate and the second at rate . The service time distribution as described is a hypoexponential distribution with phases, i.e., . This is an M/Hypo/1 queue. Each state is defined by , where is the number of jobs in the queue and is the stage of service for the job being served. If we order states lexicographically, then and the infinitesimal generator matrix of the process is

 (2.16)

where . 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).

We define subvectors of the stationary distribution vector of the process as for , and . Accordingly, we define subsets for and of the state space . We call the states on the boundary portion of the process and all other states are called the repeating portion or the repeating states of the process2.5. Throughout this dissertation, it is assumed that the cardinality of the boundary portion of the process is and the cardinality of each repeating level is , where may be different from . This partition of the stationary distribution vector and state space of the process defines the following submatrices of the infinitesimal generator in Eq.(2.16).

 (2.17)

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

 (2.18)

where 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 for . We use '' for matrices related to . 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.

Next: 2.5.2 GI/M/1-type processes Up: 2.5 Markov chains with Previous: 2.5 Markov chains with
Alma Riska 2003-01-13