banner ad
Experts Logo


The BMAP/G/l QUEUE: A Tutorial

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

View Profile on


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

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

©Copyright - All Rights Reserved


Related articles


4/10/2018· Telecommunication

Where is 5G Communications Technology IP Coming From?

By: Keith Mallinson

As I explained in IP Finance last week, following President Trump's blocking of Broadcom's hostile bid to acquire Qualcomm, by remaining independent the cellular technology leader will be able to maintain its long-term commitment to high levels of R&D investment (at 23 percent of sales recently), most significantly including that in 5G communications standard-essential IP.


8/24/2018· Telecommunication

Better Late Than Never to Do the Right Thing for SEP Owners

By: Keith Mallinson

At last, American authorities are also beginning to do the right thing for owners of standard-essential patents. Under the previous administration of President Barack Obama, America's agencies did the wrong thing by seriously undermining standard-essential patents in various ways. For example, this existentially threatened the independence of Qualcomm, which relies substantially on its patent-licensing business to fund long-term R&D including that in upcoming 5G mobile communications. Thankfully, President Donald Trump's administration has recognised the important need to support, not undermine, the nation's technology innovators, and uphold their patent rights, as enshrined in the US Constitution.


10/10/2011· Telecommunication

A Markov Modulated Characterization of Packetized Voice and Data Traffic and Related Statistical Multiplexer Performance

By: Dr. David Lucantoni

We study the performance of a statistical multiplexer whose inputs consist of a superposition of packetized voice sources and data. The performance analysis predicts voice packet delay distributions, which usually have a stringent requirement, as well as data packet delay distributions.

; broker Movie Ad
Unicourt Logo Button

Follow us

linkedin logo youtube logo rss feed logo