Next: Analysis of the RFB Up: Dimensionality reduction Previous: Analysis of the birth-and-death   Contents

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 .
Observe that if the second property did not involve the approximation, then the foreground process that depends on background process and the foreground process that depends on background process would be stochastically equivalent. This is because the sequence of the sojourn times between changing levels (0, 1, ..., , and ) in and that in would be stochastically equivalent.

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

Next: Analysis of the RFB Up: Dimensionality reduction Previous: Analysis of the birth-and-death   Contents
Takayuki Osogami 2005-07-19