Tail asymptotics for the queue size distribution in the MAP/G/1 retrial queue

We consider a MAP/G/1 retrial queue where the service time distribution has a finite exponential moment. We derive matrix differential equations for the vector probability generating functions of the stationary queue size distributions. Using these equations, Perron–Frobenius theory, and the Karamata Tauberian theorem, we obtain the tail asymptotics of the queue size distribution. The main result on light-tailed asymptotics is an extension of the result in Kim et al. (J. Appl. Probab. 44:1111–1118, 2007) on the M/G/1 retrial queue.     

Tail asymptotics for the queue size distribution in a discrete-time Geo/G/1 retrial queue

We consider a discrete-time Geo/G/1 retrial queue where the service time distribution has a finite exponential moment. We show that the tail of the queue size distribution is asymptotically geometric. Remarkably, the result is inconsistent with the corresponding result in the continuous-time counterpart, the M/G/1 retrial queue, where the tail of the queue size distribution is asymptotically given by a geometric function multiplied by a power function.     

Unreliable M/G/1 retrial queue: monotonicity and comparability

In this paper we investigate the monotonicity properties of an unreliable M/G/1 retrial queue using the general theory of stochastic ordering. We show the monotonicity of the transition operator of the embedded Markov chain relative to the strong stochastic ordering and increasing convex ordering. We obtain conditions of comparability of two transition operators and we obtain comparability conditions of the number of customers in the system. Inequalities are derived for the mean characteristics of the busy period, number of customers served during a busy period, number of orbit busy periods and waiting times. Inequalities are also obtained for some probabilities of the steady-state distribution of the server state. An illustrative numerical example is presented.     

The idle period of the finite G/M/1 queue with an interpretation in risk theory

We consider a G/M/1 queue with restricted accessibility in the sense that the maximal workload is bounded by 1. If the current workload V _t of the queue plus the service time of an arriving customer exceeds 1, only 1−V _t of the service requirement is accepted. We are interested in the distribution of the idle period, which can be interpreted as the deficit at ruin for a risk reserve process R _t in the compound Poisson risk model. For this risk process a special dividend strategy applies, where the insurance company pays out all the income whenever R _t reaches level 1. In the queueing context we further introduce a set-up time a∈[0,1]. At the end of every idle period, an arriving customer has to wait for a time units until the server is ready to serve it.     

Global and local asymptotics for the busy period of an M/G/1 queue

We consider an M/G/1 queue with subexponential service times. We give a simple derivation of the global and local asymptotics for the busy period. Our analysis relies on the explicit formula for the joint distribution for the number of customers and the length of the busy period of an M/G/1 queue.     

Lowest priority waiting time distribution in an accumulating priority Lévy queue

We derive the waiting time distribution of the lowest class in an accumulating priority (AP) queue with positive Lévy input. The priority of an infinitesimal customer (particle) is a function of their class and waiting time in the system, and the particles with the highest AP are the next to be processed. To this end we introduce a new method that relies on the construction of a workload overtaking process and solving a first-passage problem using an appropriate stopping time.     

Numerical approximations for the steady‐state waiting times in a GI/G/1 queue

This paper focuses on easily computable numerical approximations for the distribution and moments of the steadystate waiting times in a stable GI/G/1 queue. The approximation methodology is based on the theory of Fredholm integral equations and involves solving a linear system of equations. Numerical experimentation for various M/G/1 and GI/M/1 queues reveals that the methodology results in estimates for the mean and variance of waiting times within ±1% of the corresponding exact values. Comparisons with competing approaches establish that our methodology is not only more accurate, but also more amenable to obtaining waiting time approximations from the operational data. Approximations are also obtained for the distributions of steadystate idle times and interdeparture times. The approximations presented in this paper are intended to be useful in roughcut analysis and design of manufacturing, telecommunications, and computer systems as well as in the verification of the accuracies of inequalities, bounds, and approximations.     

Reflected Brownian motion in the quadrant: tail behavior of the stationary distribution

Let Z be a two-dimensional Brownian motion confined to the non-negative quadrant by oblique reflection at the boundary. Such processes arise in applied probability as diffusion approximations for two-station queueing networks. The parameters of Z are a drift vector, a covariance matrix, and a “direction of reflection” for each of the quadrant’s two boundary rays. Necessary and sufficient conditions are known for Z to be a positive recurrent semimartingale, and they are the only restrictions imposed on the process data in our study. Under those assumptions, a large deviations principle (LDP) is conjectured for the stationary distribution of Z, and we recapitulate the cases for which it has been rigorously justified. For sufficiently regular sets B, the LDP says that the stationary probability of xB decays exponentially as x→∞, and the asymptotic decay rate is the minimum value achieved by a certain function I(?) over the set B. Avram, Dai and Hasenbein  (Queueing Syst.: Theory Appl. 37, 259–289, 2001) provided a complete and explicit solution for the large deviations rate function I(?). In this paper we re-express their solution in a simplified form, showing along the way that the computation of I(?) reduces to a relatively simple problem of least-cost travel between a point and a line.     

On Markov?CKrein characterization of the mean waiting time in M/G/K and other queueing systems

We propose a new research direction to reinvigorate research into better understanding of the M/G/K and other queueing systems??via obtaining tight bounds on the mean waiting time as functions of the moments of the service distribution. Analogous to the classical Markov?CKrein theorem, we conjecture that the bounds on the mean waiting time are achieved by service distributions corresponding to the upper/lower principal representations of the moment sequence. We present analytical, numerical, and simulation evidence in support of our conjectures.     

The last departure time from an M t /G/∞ queue with a terminating arrival process

This paper studies the last departure time from a queue with a terminating arrival process. This problem is motivated by a model of two-stage inspection in which finitely many items come to a first stage for screening. Items failing first-stage inspection go to a second stage to be examined further. Assuming that arrivals at the second stage can be regarded as an independent thinning of the departures from the first stage, the arrival process at the second stage is approximately a terminating Poisson process. If the failure probabilities are not constant, then this Poisson process will be nonhomogeneous. The last departure time from an M _t /G/∞ queue with a terminating arrival process serves as a remarkably tractable approximation, which is appropriate when there are ample inspection resources at the second stage. For this model, the last departure time is a Poisson random maximum, so that it is possible to give exact expressions and develop useful approximations based on extreme-value theory.      

Analysis of a retrial queue with two-phase service and server vacations

A queueing system with a single server providing two stages of service in succession is considered. Every customer receives service in the first stage and in the sequel he decides whether to proceed to the second phase of service or to depart and join a retrial box from where he repeats the demand for a special second stage service after a random amount of time and independently of the other customers in the retrial box. When the server becomes idle, he departs for a single vacation of an arbitrarily distributed length. The arrival process is assumed to be Poisson and all service times are arbitrarily distributed. For such a system the stability conditions and the system state probabilities are investigated both in a transient and in a steady state. A stochastic decomposition result is also presented. Numerical results are finally obtained and used to investigate system performance.     

On the stationary distribution of queue lengths in a multi-class priority queueing system with customer transfers

This paper deals with a multi-class priority queueing system with customer transfers that occur only from lower priority queues to higher priority queues. Conditions for the queueing system to be stable/unstable are obtained. An auxiliary queueing system is introduced, for which an explicit product-form solution is found for the stationary distribution of queue lengths. Sample path relationships between the queue lengths in the original queueing system and the auxiliary queueing system are obtained, which lead to bounds on the stationary distribution of the queue lengths in the original queueing system. Using matrix-analytic methods, it is shown that the tail asymptotics of the stationary distribution is exact geometric, if the queue with the highest priority is overloaded.      

Exact tail asymptotics in a priority queue—characterizations of the non-preemptive model

This is a companion paper to Li and Zhao (Queueing Syst. 63:355–381, 2009) recently published in Queueing Systems, in which the classical preemptive priority queueing system was considered. In the current paper we consider the classical non-preemptive priority queueing system with two classes of independent Poisson customers and a single exponential server serving the two classes of customers at possibly different rates. A complete characterization of the regions of system parameters for exact tail asymptotics is obtained through an analysis of generating functions. This is done for the joint stationary distribution of the queue length of the two classes of customers, for the two marginal distributions and also for the distribution of the total number of customers in the system, respectively. This complete characterization is supplemental to the existing literature, which would be useful to researchers.     

Exact tail asymptotics in a priority queue—characterizations of the preemptive model

In this paper, we consider the classical preemptive priority queueing system with two classes of independent Poisson customers and a single exponential server serving the two classes of customers at possibly different rates. For this system, we carry out a detailed analysis on exact tail asymptotics for the joint stationary distribution of the queue length of the two classes of customers, for the two marginal distributions and for the distribution of the total number of customers in the system, respectively. A complete characterization of the regions of system parameters for exact tail asymptotics is obtained through analysis of generating functions. This characterization has never before been completed. It is interesting to note that the exact tail asymptotics along the high-priority queue direction is of a new form that does not fall within the three types of exact tail asymptotics characterized by various methods for this type of two-dimensional system reported in the literature. We expect that the method employed in this paper can also be applied to the exact tail asymptotic analysis for the non-preemptive priority queueing model, among other possibilities.     

Analysis of the M/G/1 queue with exponentially working vacations—a matrix analytic approach

In this paper, an M/G/1 queue with exponentially working vacations is analyzed. This queueing system is modeled as a two-dimensional embedded Markov chain which has an M/G/1-type transition probability matrix. Using the matrix analytic method, we obtain the distribution for the stationary queue length at departure epochs. Then, based on the classical vacation decomposition in the M/G/1 queue, we derive a conditional stochastic decomposition result. The joint distribution for the stationary queue length and service status at the arbitrary epoch is also obtained by analyzing the semi-Markov process. Furthermore, we provide the stationary waiting time and busy period analysis. Finally, several special cases and numerical examples are presented.     

Corrigendum to “The distribution of the number of arrivals in a subinterval of a busy period of a single server queue”

The purpose of this corrigendum is two-fold. First, we acknowledge that two results in our paper (Novak et al. in Queueing Syst. 53:105–114, 2006) can be obtained from earlier results of Prabhu and Bhat. Second, we make corrections to Theorem 2.2, Corollary 2.1 and Theorem 4.2 of Novak et al. (Queueing Syst. 53:105–114, 2006).      

Queues where customers of one queue act as servers of the other queue

We consider a system comprised of two connected M/M/?/? type queues, where customers of one queue act as servers for the other queue. One queue, Q ₁, operates as a limited-buffer M/M/1/N?1 system. The other queue, Q ₂, has an unlimited-buffer and receives service from the customers of Q ₁. Such analytic models may represent applications like SETI@home, where idle computers of users are used to process data collected by space radio telescopes. Let L ₁ denote the number of customers in Q ₁. Then, two models are studied, distinguished by their service discipline in Q ₂: In Model 1, Q ₂ operates as an unlimited-buffer, single-server M/M/1/∞ queue with Poisson arrival rate λ ₂ and dynamically changing service rate μ ₂ L ₁. In Model 2, Q ₂ operates as a multi-server M/M/L ₁/∞ queue with varying number of servers, L ₁, each serving at a Poisson rate of μ ₂. We analyze both models and derive the Probability Generating Functions of the system’s steady-state probabilities. We then calculate the mean total number of customers present in each queue. Extreme cases are indicated.