Characterizing the BMAP/MAP/1 Departure Process via the ETAQA Truncation

Abstract

We propose a family of finite approximations for the departure process of a BMAP/MAP/1 queue. The departure process approximations are derived via an exact aggregate solution technique (called ETAQA) applied to M/G/1-type Markov processes. The proposed approximations are indexed by a parameter n(n > 1), which determines the size of the output model as n + 1 block levels of the M/G/1-type process. This output approximation preserves exactly the marginal distribution of the true departure process and the lag correlations of the interdeparture times up to lag n ? 2. Experimental results support the applicability of the proposed approximation in traffic-based decomposition of queueing networks.     

Tail Probability of Low-Priority Queue Length in a Discrete-Time Priority BMAP/PH/1 Queue

ABSTRACT

We investigate the tail probability of the queue length of low-priority class for a discrete-time priority BMAP/PH/1 queue that consists of two priority classes, with BMAP (Batch Markovian Arrival Process) arrivals of high-priority class and MAP (Markovian Arrival Process) arrivals of low-priority class. A sufficient condition under which this tail probability has the asymptotically geometric property is derived. A method is designed to compute the asymptotic decay rate if the asymptotically geometric property holds. For the case when the BMAP for high-priority class is the superposition of a number of MAP's, though the parameter matrices representing the BMAP is huge in dimension, the sufficient condition is numerically easy to verify and the asymptotic decay rate can be computed efficiently.     

Stationary analysis of a BMAP/R/1 queue with R-type multiple working vacations

We consider an infinite-buffer single server queue with batch Markovian arrival process (BMAP) and exhaustive service discipline under multiple working vacation policy. The service time during a working vacation is generally distributed random variable which is independent of the service times during a normal busy period as well as the arrival process. Duration of service times during a normal busy period and duration of working vacation times follow the class of distributions whose Laplace-Stieltjes transforms are rational functions (R-type distributions). The service time during a normal busy period, working vacation time, and the service time during a working vacation are independent of each other as well as of the arrival process. If a working vacation terminates while service is going on for a customer at head of the queue in vacation mode then, the server switches to normal mode and the customer at head of the queue is entitled to receive a full service time in the normal busy period irrespective of the amount of service received by the customer at head of the queue during the previous working vacation period. We obtain system-length distributions at various epoch, such as post-departure, pre-arrival, arbitrary, and pre-service. The proposed analysis is based on the use of matrix-analytic procedure to obtain system-length distribution at post-departure epoch. Later, we use supplementary variable technique and simple algebraic manipulations to obtain system-length distribution at arbitrary epoch using the system-length distribution at post-departure epoch. Some important performance measures, such as mean system lengths and mean waiting time have been obtained. Finally, some numerical results have been presented in the form of tables and graphs to show the applicability of the results obtained in this article. The model has potential application in areas of computer and communication networks, such as ethernet passive optical network (EPON).     

Workload Process,Waiting Times,and Sojourn Times in a Discrete Time MMAP[K]/SM[K]/1/FCFS Queue

Abstract

In this paper, we study the total workload process and waiting times in a queueing system with multiple types of customers and a first-come-first-served service discipline. An M/G/1 type Markov chain, which is closely related to the total workload in the queueing system, is constructed. A method is developed for computing the steady state distribution of that Markov chain. Using that steady state distribution, the distributions of total workload, batch waiting times, and waiting times of individual types of customers are obtained. Compared to the GI/M/1 and QBD approaches for waiting times and sojourn times in discrete time queues, the dimension of the matrix blocks involved in the M/G/1 approach can be significantly smaller.     

Estimation of Traffic Intensity Based on Queue Length in a Single M/M/1 Queue

In this article, maximum likelihood estimator (MLE) as well as Bayes estimator of traffic intensity (ρ) in an M/M/1/∞ queueing model in equilibrium based on number of customers present in the queue at successive departure epochs have been worked out. Estimates of some functions of ρ which provide measures of effectiveness of the queue have also been derived. A comprehensive simulation study starting with the transition probability matrix has been carried out in the last section.     

Bayesian Inference and Prediction in an M/G/1 with Optional Second Service

In this article, we exploit the Bayesian inference and prediction for an M/G/1 queuing model with optional second re-service. In this model, a service unit attends customers arriving following a Poisson process and demanding service according to a general distribution and some of customers need to re-service with probability “p”. First, we introduce a mixture of truncated Normal distributions on interval (? ∞, 0) to approximate the service and re-service time densities. Then, given observations of the system, we propose a Bayesian procedure based on birth-death MCMC methodology to estimate some performance measures. Finally, we apply the theories in practice by providing a numerical example based on real data which have been obtained from a hospital.     

A computational algorithm for the loss probability in the M/G/1+PH queue

This article develops a computational algorithm for the loss probability in the stationary M/G/1 queue with impatient customers whose impatience times follow a phase-type distribution (M/G/1+PH). The algorithm outputs the loss probability, along with an upper-bound of its numerical error due to truncation, and it is readily applicable to the M/D/1+PH, M/PH/1+PH, and M/Pareto/1+PH queues.     

Computing the conditional stationary distribution in Markov chains of level-dependent M/G/1-type

This paper considers the computation of the conditional stationary distribution in Markov chains of level-dependent M/G/1-type, given that the level is not greater than a predefined threshold. This problem has been studied recently and a computational algorithm is proposed under the assumption that matrices representing downward jumps are nonsingular. We first show that this assumption can be eliminated in a general setting of Markov chains of level-dependent G/G/1-type. Next we develop a computational algorithm for the conditional stationary distribution in Markov chains of level-dependent M/G/1-type, by modifying the above-mentioned algorithm slightly. In principle, our algorithm is applicable to any Markov chain of level-dependent M/G/1-type, if the Markov chain is irreducible and positive-recurrent. Furthermore, as an input to the algorithm, we can set an error bound for the computed conditional distribution, which is a notable feature of our algorithm. Some numerical examples are also provided.     

Relative efficiency of a parameter for a M/G/1 queueing system based on reduced and full likelihood functions

The present paper derives the relative efficiency of a parameter for the M/G/1 queueing system based on reduced and full likelihood functions. Monte Carlo simulations were carried out to study the finite sample properties for estimating the parameters of a M/G/1 queueing system. The simulation runs were conducted using various traftic intensities with increaseing sample sizes. The simulation results indicate that the loss in efficiency is quite small due to the use of a reduced likelihood function approach for estimating the parameter instead of the full likelihood, even for a moderate sample size of 50     

The rate of convergence to stationarity for M/G/1 models with admission controls via coupling

We study the workload processes of two M/G/1 queueing systems with restricted capacity: in Model 1 any service requirement that would exceed a certain capacity threshold is truncated; in Model 2 new arrivals do not enter the system if they have to wait more than a fixed threshold time in line. For Model 1 we obtain several results concerning the rate of convergence to equilibrium. In particular, we derive uniform bounds for geometric ergodicity with respect to certain subclasses. For Model 2 geometric ergodicity follows from the finiteness of the moment-generating function of the service time distribution. We derive bounds for the convergence rates in special cases. The proofs use the coupling method.