ABSTRACT

We present an overview of recent results related to the single server queue with general independent and identically distributed service times and a batch Markovian arrival process (BMAP). The BMAP encompasses a wide range of arrival processes and yet, mathematically, the BMAP/G/I model is a relatively simple matrix generalization of the M/G/l queue. Stationary and transient distributions for the queue length and waiting time distributions are presented. We discuss numerical algorithms for computing these quantities, which exploit both matrix analytic results and numerical transform inversion. Two-dimensional transform inversion is used for the transient results.

1. Introduction

It is well known that the basic M/G/I and GI/M/l queueing models can be analyzed via embedded Markov chains. As shown in Neuts [1] [2], a large class of interesting queueing models can be analyzed via matrix generalizations of these embedded Markov chains. These are called M/G/I-type and GI/M/ltype Markov chains, respectively.

Within the class of models that can be analyzed by M/G/l-type Markov chains is the BMAP/G/l queue; it is the generalization of the M/G/I model in which the Poisson arrival process is replaced by a batch Markovian arrival process (BMAP). Not only is the embedded Markov chain at departure epochs in a BMAP/G/l queue an M/G/l-type Markov chain, but the entire model tends to be a matrix generalization of the M/G/l queue (or, more exactly, its batch arrival generalization).

This paper is a tutorial on the BMAP and the BMAP/G/l queue. The BMAP was first introduced with alternative notation as the versatile Markovian point process in Neuts [3], and the BMAP/G/l queue was first analyzed (under the name N / G /1) by Ramaswami [4]. A major focus here is on exact and efficient numerical algorithms for both the steady-state and transient distributions for the BMAP/G/l queue. This paper is largely based on the author's (mostly joint) work [5]-[12] but we give a general history in §4.

The idea of a BMAP is to keep the tractability of the Poisson arrival process but significantly generalize it in ways that allow the inclusion of dependent interarrival times, non-exponential interarrival-time distributions, and correlated batch sizes. The BMAP includes as special cases both phase type renewal processes (which include the Erlang, Ek, and hyperexponential, Hie, renewal processes) and non-renewal processes such as the Markov modulated Poisson process (MMPP) and many other processes in the applied probability literature. These are reviewed in §3. The class also allows correlated batch size distributions and is closed under superpositions, thinning, etc.

Matrix analytic solutions to the BMAP/G/I queue have been available for some time now (see Ramaswami [4]) but the expressions were not in a form that allowed feasible numerical implementation in their full generality. Recent results (reviewed in §4) have resulted in much more transparent solutions that show that this model is indeed a simple generalization of the ordinary M/G/l queue. In fact, many expressions for the performance measures of interest are natural matrix analogues of the corresponding expressions for the M/G/l queue. The purpose of this review is to demonstrate the simplicity of the results which may occasionally have been obscured by the technicalities governing their derivations.

This is accomplished by displaying the relevant results next to the corresponding M/G/I formulas. There are no proofs in this paper; we refer the reader to referenced papers for proofs.

The rest of the paper is organized as follows. In §2 we define the BMAP, and in §3 we describe a number of special cases. A brief history of the BMAP and BMAP/G/I queue is presented in §4. This section may serve as an annotated bibliography of recent work related to this model. Expressions for the transforms of the stationary and transient queue length and waiting time distributions are presented in §5. Actual algorithmic procedures for obtaining numerical results for the performance measures of interest are discussed in §6. In particular, we discuss some of the standard matrix analytic algorithms as well as new transform inversion algorithms. Several examples are discussed in §7. A small list of current and future extensions to this model is discussed in §8.

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