banner ad
Experts Logo


New Results On The Single Server Queue With a Batch Markovian Arrival Process

By: Dr. David Lucantoni

As Originally Published in Stochastic Models, Vol. 7, No.1, pp. 1-46, 1991

Tel: (732) 493-0587
Email Dr. Lucantoni

View Profile on


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 [1]. 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 [2]. Since then, the infinite server, c-server (with deterministic service times), and finite queue versions have been solved, see [3], [4], and [5]. Although the computational algorithm suggested by Rarnaswami's analysis has been shown to be numerically stable [6], 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 [7], 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 [8]. 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 ([9], [10]) that the interarrival times in the packet streams are strongly correlated. The MMPP was used in [10] to approximate the superposition of packetized voice processes and in [11] 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 [12] and [13]. For a case where the MMPP is obtained as the superposition of interrupted Poisson processes see [14]. 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 [15] 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 [7] ,and [16]. 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 [17]. These exact expressions could be used to validate various simple approximations that have been proposed, see e.g., [18] and [19].

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.


. . .Continue to read rest of article (PDF).

Dr. David Lucantoni, is an internationally renowned Telecommunications Expert with over 27 years experience.

©Copyright - All Rights Reserved


Related articles


5/24/2018· Telecommunication

Analyst Angle: Complementary Spectrum Allocations and Technologies Maximize Coverage and Capacity for All

By: Keith Mallinson

Radio spectrum is the lifeblood of wireless networks. Traditional methods of doling out spectrum have somewhat hindered rather than helped maximize the availability of affordable Internet access, even if this was not the case with voice and text. Instead of seeking to aggrandize auction proceeds by creating scarcity, more flexible allocations including shared as well as traditional licensed and unlicensed assignments are required.


11/13/2010· Telecommunication

Squeezing the Most Out of ATM

By: David Lucantoni, G. L. Choudhury, and Ward Whitt

Much energy is being devoted to studying the promising new asynchronous transfer mode (ATM) technology for supporting multiservice high-speed communication networks-e.g., see Roberts [39]. As indicated in [39], interest in ATM is stimulated by two factors: First, by new technology making it possible to transmit and switch at very high bandwidths; and, second, by the growing demand for more sophisticated and powerful communication services.


9/21/2019· Telecommunication

Telephone Consumer Protection Act (TCPA) Compliance: A Checklist

By: Ray Horak

The Telephone Consumer Protection Act (TCPA) was passed into law in 1991. At the time, consumers were plagued by sales calls which it seemed always came at the most inconvenient times...In an effort to address a growing number of telephone marketing calls and certain other telemarketing practices...

; broker Movie Ad
Unicourt Logo Button

Follow us

linkedin logo youtube logo rss feed logo