The versatile Markovian point process was introduced by M. F. Neuts in 1979. This is a rich class of point processes which contains many familiar arrival process as very special cases. Recently, the Batch Markovian Arrival Process, a class of point processes which was subsequently shown to be equivalent to Neuts' point process, has been studied using a more transparent notation.
Recent results in the matrix-analytic approach to queueing theory have substantially reduced the computational complexity of the algorithmic solution of single server queues with a general Markovian arrival process. We generalize these results to the single server queue with the batch arrival process and emphasize the resulting simplifications.
Algorithms for the special cases of the PH/G/1 and MMPP/G/1 queues are highlighted as these models are receiving renewed attention in the literature and the new algorithms proposed here are simpler than existing ones. In particular, the PH/G/I queue has additional structure which further enhances the efficiency of its algorithmic solution. Also, the two-state MMPP/G/1 queue, which has applications in communications modeling, has an extremely simple solution.
The versatile Markovian point process was introduced by M. F. Neuts in . This is a very rich class of point processes which contains many well known arrival processes as special cases. Among them are the phase-type (PH) renewal process, the Markov modulated Poisson process (MMPP), overflows from finite Markovian queues, etc. In each case, arrivals are allowed to occur in batches where different types of arrivals can have different batch size distributions. The price paid for such generality was an elaborate notation required to keep track of the different types of arrivals. Although the notation was complex, the analysis of queues with this point process as the arrival stream proceeded, conceptually, in an analogous fashion to that of queues with simpler arrival streams. Thus it was possible to solve in a unified methodical analysis a whole class of queueing problems, unifying many results in the literature.
This was first accomplished by V. Ramaswami for the single server queue with the versatile Markovian point process as the arrival stream . Since then, the infinite server, c-server (with deterministic service times), and finite queue versions have been solved, see , , and . Although the computational algorithm suggested by Rarnaswami's analysis has been shown to be numerically stable , in practice it has not been feasible to implement it in its full generality. The setup computations alone are a formidable burden on both CPU time and storage. Thus, until now, practical numerical solutions have been limited to particular cases of the general model.
In our analysis of a single server queue with server vacations , we desired the solution to the queue with a PH-renewal arrival process and the one with a correlated arrival stream such as an MMPP. As our focus was not on batch arrivals, we did not proceed with the full generality of the versatile Markovian point process, but constructed a new process which contained both PH-renewal and the MMPP processes yet whose notation was very simple. We called this process the Markovian Arrival Process (MAP). This construction is easily generalized to the Batch Markovian Arrival Process (BMAP) to allow for batch arrivals. Although this new class of processes was originally thought to be more general than the versatile Markovian point process, we later showed that the two processes were in fact equivalent. The only difference is that the BMAP involves much simpler notation.
Special cases of the BMAP/G/I queue have received renewed attention in the communications modeling literature. The interrupted Poisson process has long been used to approximate the overflow traffic of finite trunk systems . More recently, modeling of packetized voice and data traffic has required consideration of more complicated arrival processes than the Poisson process. It is now well known (, ) that the interarrival times in the packet streams are strongly correlated. The MMPP was used in  to approximate the superposition of packetized voice processes and in  for a related process. The MMPP was chosen because it is a tractable, non-renewal stream which could match certain statistical properties of the original traffic. The MMPP/G/l queue approximated the first two moments of delays as well as the tail probabilities with high accuracy. Other algorithms for solving the MMPP/G/l queue are presented in  and . For a case where the MMPP is obtained as the superposition of interrupted Poisson processes see . Other special cases of the BMAP/G/I queue which have appeared in the literature are related to the PH/G/I queue. We refer to the extended, annotated bibliography  for many examples and special cases.
We present here new resnlts for the BMAP/G/I queue. In particular, we show that the matrix G, which arises in the matrix analytic approach to queues of M/G/I type and is the key ingredient to the computational procedures, has an exponential form. This exponential fonn leads to an efficient algorithm for the computation of G as well as the coefficient matrices in the transition probability matrix of the Markov chain embedded at departures. These are needed to compute the queue length distribution at departures and at arbitrary times. This key result generalizes similar results in  ,and . The algorithms presented here allow for a general implementation of canned computer programs for solving the general model. Such a program could be used for comparing vastly different arrival processes entering a single server queue.
A further use of this algorithm is to evaluate the performance of superpositions of renewal processes entering a queue. If the renewal processes are of phase type then the superposition is a special case of the BMAP. Although the size of the matrices involved grows geometrically as the number of streams, for two or three streams the computations are completely feasible. The delay seen by customers in the individual streams can be derived from the results presented earlier. Similar calculations for the MMPP/M/c/c +K queue were presented in . These exact expressions could be used to validate various simple approximations that have been proposed, see e.g.,  and .
The remainder of this paper is organized as follows. In Section 2, we define the BMAP and present some familiar special cases of the process. Section 3 consists of an outline of the traditional matrixanalytic approach to solving the single server queue with a BMAP as the arrival stream emphasizing the framework of the new notation. New results for the BMAP/G/I queue are presented in Section 4. Section 5 summarizes the algorithmic simplifications for the general model, highlighting the substantial savings in both computational complexity and storage which are afforded by the new results. In Section 6 present several special cases which have particularly simple solutions. Conclusions are presented in Section 7.