Analysis of the FB process

In this section, we extend the analysis in
Section 3.5.1 to the general FB process. As in
Section 3.5.1, once the background process is approximated
by a Markov chain on a finite state space, it is straightforward to
reduce the FB process to a 1D Markov chain.
Hence, in this section, we limit our focus on approximating
the background process by a Markov chain on a finite state space;
for completeness, we formally describe the construction of the 1D Markov chain
using the approximated background process in Appendix 3.5.5.
We will see that, in general, a
*collection* of PH distributions is needed in the
approximate background process, , (e.g. recall Section 3.1.2) to capture
the dependency in the sequence of sojourn times in levels that has.
This is in contrast to the case when the background process is a
birth-and-death process, which required only a *single* PH distribution
in the approximate background process,
since the sojourn times in levels are i.i.d. in this case.
Below, we use to denote the generator matrix of
, and use
,
,
and
to denote the submatrices of ,
following the convention introduced in Section 3.4

We start by specifying the properties that should have. Let be the event that the first state that we visit in level is in phase given that we transitioned from phase in level to any state in level . (Notice that in the analysis of the M/PH/2 queue with two priority classes in Section 3.1, each event corresponds to the event that the phase of the job in service immediately before a busy period starts is and the phase of the job in service immediately after the busy period is .) We require that has the following key properties:

- The probability of event in is the same as that in for each and .
- The distribution of the sojourn time in levels
*given event*in well-represents that in (i.e. the first three moments of the two distributions agree) for each and .

To construct , we first analyze the probability of event and (the moments of) the distribution of the sojourn time in levels given event (we denote this distribution as ) for each and . (Notice that in the analysis of the M/PH/2 queue with two priority classes in Section 3.1, corresponds to the distribution of the busy period duration given that the phase of the job in service immediately before a busy period starts is and the phase of the job in service immediately after the busy period is .) Let be the number of phases in level of (and ). Then, there are types of events .

The probability of event is relatively easy to analyze.
Let be a matrix of order whose element is
the probability of event .
Let be the event that
transitions to state given that
the transition is from state to any state in level .
Also, let be the event that
state is the first state that hits in level given that
starts in state .
Then,

Thus, all that remains is to derive and . The first quantity is derived via as follows:

where is defined as 0. Let be a matrix whose element is . Then, matrix is obtained by the algorithm in Figure 3.12 (see Section 3.7 for an alternative algorithm and intuition). More formally, let Let be a matrix whose element is . Then, matrix is given by

Next, we analyze the moments of .
Let be a
matrix of order whose element is the -th moment
of for .
Note that is a mixture of distributions of various conditional passage times
from level to level .
Specifically, let
be the time to go
from state to state .
Then, the distribution function of is given by

Now, let be a matrix whose element is the -th moment of given event , i.e.

for . Then,

More formally, let be a matrix whose element is

Then,

Thus, all that remains is to derive . We can calculate by a trivial extension of Neuts' algorithm [134] for any ; we postpone this extension to Section 3.7.

We are now ready to construct . We use the moment matching algorithm developed in Chapter 2 to approximate by a PH distribution, , matching the first three moments of , , for all and . Let , where is a column vector with all elements 1 and has order equal to the number of columns in .

Using and
defined above,
the generator matrix of is defined as

where ,

for . Here, is a column vector with all elements 1 and has order equal to the number of columns in , and denotes a zero matrix of order . Recall that is the number of phases in level of (and ).