Translating stationary probabilities into performance measures

The stationary probabilities obtained above can be used to compute other relevant performance measures. Specifically, we consider a QBD process modeling a MAP/PH/1 queue or other queueing systems where level $\ell$ of the QBD process consists of the states with $\ell$ jobs in the system. We first analyze the moments of the number of jobs in the system. The mean response time follows immediately from the mean number of jobs in the system. We will also discuss how to compute higher moments of response time.

First, the mean number of jobs in the system, $N$, is given by

$$\mbox{{\bf\sf E}}\left[ N \right] = \sum_{\ell=0}^\infty \ell \Vec{\pi_\ell} \Vec{1}$$

$$= \sum_{\ell=0}^{\hat\ell-1} \ell \Vec{\pi_\ell} \Vec{1} + \sum_{i=0}^\infty (\hat\ell+i) \Vec{\pi_{\hat\ell}}(\mathbf{R})^i \Vec{1}$$

$$= \sum_{\ell=0}^{\hat\ell-1} \ell \Vec{\pi_\ell} \Vec{1} + \hat\ell... ... \Vec{1} + \Vec{\pi_{\hat\ell}} (\mathbf{I}-\mathbf{R})^{-2} \mathbf{R} \Vec{1}$$ (3.6)

Similarly, the $r$-th moment of the number of jobs in the system can be computed via

$$\mbox{{\bf\sf E}}\left[ N^r \right] = \sum_{\ell=0}^\infty \ell^r \Vec{\pi_\ell} \Vec{1} \\$$

for $r\geq 2$.

The mean response time, $\mbox{{\bf\sf E}}\left[ T \right]$, is given immediately from $\mbox{{\bf\sf E}}\left[ N \right]$ via Little's law:

$$\mbox{{\bf\sf E}}\left[ T \right] = \frac{\mbox{{\bf\sf E}}\left[ N \right]}{\lambda},$$

where $\lambda$ is the arrival rate.

Computation of higher moments of response time, $T$, depends on particular queueing systems. When jobs are completed in the order of their arrivals (first-in-first-out, FIFO), a generalization of Little's law (distributional Little's law) applies [63,32]. For example, in a MAP/PH/1/FCFS queue, jobs are completed in the FIFO order. If, in addition, the arrival process is Poisson (and some technical assumptions are satisfied [19,202], e.g. in an M/PH/1/FCFS queue), the $r$-th moment of response time, $\mbox{{\bf\sf E}}\left[ T^r \right]$, is given simply as a function of the first $r$ moments of the number of jobs in the system:

$$\mbox{{\bf\sf E}}\left[ T^r \right] = \frac{1}{\lambda^r} \mbox{{\bf\sf E}}\left[ N(N-1)\cdots(N-r+1) \right]$$

for $r\geq 2$. For more general arrival processes, see [19,202]. For some queueing systems including M/PH/$k$ queues ($k\geq 2$), where jobs are served in FCFS order but not necessarily completed in FIFO order, the distributional Little's law does not apply. In these cases, higher moments of response time may be computed via an analysis of passage times in a QBD process. We will elaborate on this method in Section 3.8.