An RG-Factorization Approach for a BMAP/M/1 Generalized Processor-Sharing Queue

ABSTRACT

In this paper, we study a BMAP/M/1 generalized processor-sharing queue. We propose an RG-factorization approach, which can be applied to a wider class of Markovian block-structured processor-sharing queues. We obtain the expressions for both the distribution of the stationary queue length and the Laplace transform of the sojourn time distribution. From these two expressions, we develop an algorithm to compute the mean and variance of the sojourn time approximately.     

Sojourn time in an M/M/1 processor sharing queue with permanent customers

We explicitly compute the sojourn time distribution of an arbitrary customer in an M/M/1 processor sharing (PS) queue with permanent customers. We notably exhibit the orthogonal structure associated with this queuing system and we show how sieved Pollaczek polynomials and their associated orthogonality measure can be used to obtain an explicit representation for the complementary cumulative distribution function of the sojourn time of a customer. This explicit formula subsequently allows us to compute the two first moments of this random variable and to study the asymptotic behavior of its distribution. The most salient result is that the decay rate depends on the load of the system and the number K of permanent customers. When the load is above a certain threshold depending on K, the decay rate is identical to that of a regular M/M/1 PS queue.     

Approximating M/G/1 Waiting Time Tail Probabilities

Abstract

We propose a new approximation formula for the waiting time tail probability of the M/G/1 queue with FIFO discipline and unlimited waiting space. The aim is to address the difficulty of obtaining good estimates when the tail probability has non-exponential asymptotics. We show that the waiting time tail probability can be expressed in terms of the waiting time tail probability of a notional M/G/1 queue with truncated service time distribution plus the tail probability of an extreme order statistic. The Cramér–Lundberg approximation is applied to approximate the tail probability of the notional queue. In essence, our technique extends the applicability of the Cramér–Lundberg approximation to cases where the standard Lundberg condition does not hold. We propose a simple moment-based technique for estimating the parameters of the approximation; numerical results demonstrate that our approximation can yield very good estimates over the whole range of the argument.     

Estimation in M/Er /1 queueing systems

In this paper, the maximum likelihood estimates of the parameters for the M/E_r /1 queueing model are derived when the queue size at each departure point is observed. A numerical example is generated by simulating a finite Markov chain to illustrate the methodology for estimating the parameters with variable Erlang service time distribution. The problem of hypothesis testing and simultaneous Confidence regions of the parameter is also investigated.0     

BMAP/G/1 Queue Under D-Policy: Queue Length Analysis

ABSTRACT

We study the queue length distribution of a queueing system with BMAP arrivals under D-policy. The idle server begins to serve the customers only when the sum of the service times of all waiting customers exceeds some fixed threshold D. We derive the vector generating functions of the queue lengths both at a departure and at an arbitrary point of time. Mean queue lengths are derived and a numerical example is presented.     

Queue Length Analysis of MAP/G/1 Queue Under D-Policy

Abstract

We study the queue length distribution of a queueing system with MAP arrivals under D-policy. The idle server begins to serve the customers only when the sum of the service times of all waiting customers exceeds some fixed threshold D. We derive the vector generating functions of the queue lengths both at a departure and at an arbitrary point of time. Mean queue lengths will be derived from these transform results. A numerical example is provided.     

Commuting Matrices in the Queue Length and Sojourn Time Analysis of MAP/MAP/1 Queues

Queues with Markovian arrival and service processes, i.e., MAP/MAP/1 queues, have been useful in the analysis of computer and communication systems and different representations for their stationary sojourn time and queue length distribution have been derived. More specifically, the class of MAP/MAP/1 queues lies at the intersection of the class of QBD queues and the class of semi-Markovian queues. While QBD queues have a matrix exponential representation for their queue length and sojourn time distribution of order N and N², respectively, where N is the size of the background continuous time Markov chain, the reverse is true for a semi-Markovian queue. As the class of MAP/MAP/1 queues lies at the intersection, both the queue length and sojourn time distribution of a MAP/MAP/1 queue has an order N matrix exponential representation. The aim of this article is to understand why the order N² distributions of the sojourn time of a QBD queue and the queue length of a semi-Markovian queue can be reduced to an order N distribution in the specific case of a MAP/MAP/1 queue. We show that the key observation exists in establishing the commutativity of some fundamental matrices involved in the analysis of the MAP/MAP/1 queue.     

Estimation of Measures in M/M/1 Queue

Maximum likelihood and uniform minimum variance unbiased estimators of steady-state probability distribution of system size, probability of at least ? customers in the system in steady state, and certain steady-state measures of effectiveness in the M/M/1 queue are obtained/derived based on observations on X, the number of customer arrivals during a service time. The estimators are compared using Asympotic Expected Deficiency (AED) criterion leading to recommendation of uniform minimum variance unbiased estimators over maximum likelihood estimators for some measures.     

A new look at Markov processes of G/M/1-type

We present a new method for deriving the stationary distribution of an ergodic Markov process of G/M/1-type in continuous-time, by deriving and making use of a new representation for each element of the rate matrices contained in these distributions. This method can also be modified to derive the Laplace transform of each transition function associated with Markov processes of G/M/1-type.     

Bayesian analysis of Er/M/1 and Er/M/c queues

Bayesian inference and prediction tasks for Er/M/1 and Er/M/c queues are undertaken. Equilibrium probabilities of the queue size and waiting time distributions are estimated using conditional Monte-Carlo simulation methods. We illustrate that some standard queueing measures do not exist when independent priors are used for the arrival and service rates of a G/M/1 queue.     

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.     

Hypothesis Testing and Confidence Regions for the Mean Sojourn Time of an M/M/1 Queueing System

This article discusses testing hypotheses and confidence regions with correct levels for the mean sojourn time of an M/M/1 queueing system. The uniformly most powerful unbiased tests for three usual hypothesis testing problems are obtained and the corresponding p values are provided. Based on the duality between hypothesis tests and confidence sets, the uniformly most accurate confidence bounds are derived. A confidence interval with correct level is proposed.     

Bernstein–von Mises Theorem for M|M|1 Queue

The article deals with Bernstein–von Mises theorem, for the arrival process in a M | M |1 queue.     

The analysis of MX/M/1 queue with two-stage vacations policy

Abstract

In this article, we consider a batch arrival M^X/M/1 queue with two-stage vacations policy that comprises of single working vacation and multiple vacations, denoted by M^X/M/1/SWV?+?MV. Using the matrix analytic method, we derive the probability generating function (PGF) of the stationary system size and investigate the stochastic decomposition structure of stationary system size. Further, we obtain the Laplace–Stieltjes transform (LST) of stationary sojourn time of a customer by the first passage time analysis. At last, we illustrate the effects of various parameters on the performance measures numerically and graphically by some numerical examples.     

Response Time Distribution in a D-MAP/PH/1 Queue with General Customer Impatience

ABSTRACT

This paper presents two methods to calculate the response time distribution of impatient customers in a discrete-time queue with Markovian arrivals and phase-type services, in which the customers’ patience is generally distributed (i.e., the D-MAP/PH/1 queue). The first approach uses a GI/M/1 type Markov chain and may be regarded as a generalization of the procedure presented in Van Houdt ^[14] Van Houdt , B. ; Lenin , R. B. ; Blondia , C. Delay distribution of (im)patient customers in a discrete time D-MAP/PH/1 queue with age dependent service times Queueing Systems and Applications 2003 , 45 1 , 59 – 73 . [CROSSREF]  [Google Scholar] for the D-MAP/PH/1 queue, where every customer has the same amount of patience. The key construction in order to obtain the response time distribution is to set up a Markov chain based on the age of the customer being served, together with the state of the D-MAP process immediately after the arrival of this customer. As a by-product, we can also easily obtain the queue length distribution from the steady state of this Markov chain.

We consider three different situations: (i) customers leave the system due to impatience regardless of whether they are being served or not, possibly wasting some service capacity, (ii) a customer is only allowed to enter the server if he is able to complete his service before reaching his critical age and (iii) customers become patient as soon as they are allowed to enter the server. In the second part of the paper, we reduce the GI/M/1 type Markov chain to a Quasi-Birth-Death (QBD) process. As a result, the time needed, in general, to calculate the response time distribution is reduced significantly, while only a relatively small amount of additional memory is needed in comparison with the GI/M/1 approach. We also include some numerical examples in which we apply the procedures being discussed.     

Transient Analysis of the M/M/k/N/N Queue using a Continuous Time Homogeneous Markov System with Finite State Size Capacity

In this article, the M/M/k/N/N queue is modeled as a continuous-time homogeneous Markov system with finite state size capacity (HMS/c_s). In order to examine the behavior of the queue a continuous-time homogeneous Markov system (HMS) constituted of two states is used. The first state of this HMS corresponds to the source and the second one to the state with the servers. The second state has a finite capacity which corresponds to the number of servers. The members of the system which can not enter the second state, due to its finite capacity, enter the buffer state which represents the system's queue. In order to examine the variability of the state sizes formulae for their factorial and mixed factorial moments are derived in matrix form. As a consequence, the pmf of each state size can be evaluated for any t ∈ ?⁺. The theoretical results are illustrated by a numerical example.     

Large deviations of multiclass M/G/1 queues

Consider a multiclass M/G/1 queue where queued customers are served in their order of arrival at a rate which depends on the customer class. We model this system using a chain with states represented by a tree. Since the service time distribution depends on the customer class, the stationary distribution is not of product form so there is no simple expression for the stationary distribution. Nevertheless, we can find a harmonic function on this chain which provides information about the asymptotics of this stationary distribution. The associated h‐transformation produces a change of measure that increases the arrival rate of customers and decreases the departure rate thus making large deviations common. The Canadian Journal of Statistics 37: 327–346; 2009 © 2009 Statistical Society of Canada