Regularly varying tail of the waiting time distribution in M/G/1 retrial queue

We consider an M/G/1 retrial queue where the service time distribution has a regularly varying tail with index −β, β>1. The waiting time distribution is shown to have a regularly varying tail with index 1−β, and the pre-factor is determined explicitly. The result is obtained by comparing the waiting time in the M/G/1 retrial queue with the waiting time in the ordinary M/G/1 queue with random order service policy.     

An <Emphasis Type="Italic">M</Emphasis><Superscript>[<Emphasis Type="Italic">X</Emphasis>]</Superscript>/<Emphasis Type="Italic">G</Emphasis>/1 retrial queue with server breakdowns and constant rate of repeated attempts

We consider an M ^[X]/G/1 retrial queue subject to breakdowns where the retrial time is exponential and independent of the number of customers applying for service. If a coming batch of customers finds the server idle, one of the arriving customers begins his service immediately and the rest joins a retrial group (called orbit) to repeat his request later; otherwise, if the server is busy or down, all customers of the coming batch enter the orbit. It is assumed that the server has a constant failure rate and arbitrary repair time distribution. We study the ergodicity of the embedded Markov chain, its stationary distribution and the joint distribution of the server state and the orbit size in steady-state. The orbit and system size distributions are obtained as well as some performance measures of the system. The stochastic decomposition property and the asymptotic behavior under high rate of retrials are discussed. We also analyse some reliability problems, the k-busy period and the ordinary busy period of our retrial queue. Besides, we give a recursive scheme to compute the distribution of the number of served customers during the k-busy period and the ordinary busy period. The effects of several parameters on the system are analysed numerically. I. Atencia’s and Moreno’s research is supported by the MEC through the project MTM2005-01248.     

MAP 1, MAP2 /M/c retrial queue with guard channels and its application to cellular networks

In this paper, we investigate the impact of retrial phenomenon on loss probabilities and compare loss probabilities of several channel allocation schemes giving higher priority to hand-off calls in the cellular mobile wireless network. In general, two channel allocation schemes giving higher priority to hand-off calls are known; one is the scheme with the guard channels for hand-off calls and the other is the scheme with the priority queue for hand-off calls. For mathematical unified model for both schemes, we consider theMAP ₁,MAP ₂ /M/c/b, ∞ retrial queue with infinite retrial group, geometric loss, guard channels and finite priority queue for hand-off class. We approximate the joint distribution of two queue lengths by Neuts' method and also obtain waiting time distribution for hand-off calls. From these results, we obtain the loss probabilities, the mean waiting time and the mean queue lengths. We give numerical examples to show the impact of the repeated attempt and to compare loss probabilities of channel allocation schemes.     

Maximum Likelihood Estimates and Confidence Intervals of an M/M/R Queue with Heterogeneous Servers

This paper studies maximum likelihood estimates as well as confidence intervals of an M/M/R queue with heterogeneous servers under steady-state conditions. We derive the maximum likelihood estimates of the mean arrival rate and the three unequal mean service rates for an M/M/3 queue with heterogeneous servers, and then extend the results to an M/M/R queue with heterogeneous servers. We also develop the confidence interval formula for the parameter ρ, the probability of empty system P ₀, and the expected number of customers in the system E[N], of an M/M/R queue with heterogeneous servers     

AnM/M/c queue with impatient customers

This paper considers theM/M/c queue in which a customer leaves when its service has not begun within a fixed interval after its arrival. The loss probability can be expressed in a simple formula involving the waiting time probabilities in the standardM/M/c queue. The purpose of this paper is to give a probabilistic derivation of this formula and to outline a possible use of this general formula in theM/M/c retrial queue with impatient customers. This research was supported by the INTAS 96-0828 research project and was presented at the First International Workshop on Retrial Queues, Universidad Complutense de Madrid, Madrid, September 22–24, 1998.     

On the single server retrial queue with priority customers

We consider anM ₂/G ₂/1 type queueing system which serves two types of calls. In the case of blocking the first type customers can be queued whereas the second type customers must leave the service area but return after some random period of time to try their luck again. This model is a natural generalization of the classicM ₂/G ₂/1 priority queue with the head-of-theline priority discipline and the classicM/G/1 retrial queue. We carry out an extensive analysis of the system, including existence of the stationary regime, embedded Markov chain, stochastic decomposition, limit theorems under high and low rates of retrials and heavy traffic analysis.Visiting from: Department of Probability, Mechanics and Mathematics, Moscow State University, Moscow 119899, Russia.     

Monotonicity properties in various retrial queues and their applications

We consider several multi-server retrial queueing models with exponential retrial times that arise in the literature of retrial queues. The effect of retrial rates on the behavior of the queue length process is investigated via sample path approach. We show that the number of customers in orbit and in the system as a whole are monotonically changed if the retrial rates in one system are bounded by the rates in second one. The monotonicity results are applied to show the convergence of generalized truncated systems that have been widely used for approximating the stationary queue length distribution in retrial queues. AMS subject classifications: Primary 60K25     

On the M/G/1 retrial queueing system with linear control policy

Summary This paper is concerned with the study of a newM/G/1 retrial queueing system in which the delays between retrials are exponentially distributed random variables with linear intensityg(n)=α+nμ, when there aren≥1 customers in the retrial group. This new retrial discipline will be calledlinear control policy. We carry out an extensive analysis of the model, including existence of stationary regime, stationary distribution of the embedded Markov chain at epochs of service completions, joint distribution of the orbit size and the server state in steady state and busy period. The results agree with known results for special cases.     

On the infinite server shortest queue problem: Non-symmetric case

We consider two parallel M/M/∞ queues. All servers in the first queue work at rate μ₁ and all in the second work at rate μ₂. A new arrival is routed to the system with the lesser number of customers. If both queues have equal occupancy, the arrival joins the first queue with probability ν₁, and the second with probability ν₂ = 1−ν₁. We analyze this model asymptotically. We assume that the arrival rate λ is large compared to the two service rates. We give several different asymptotic formulas, that apply for different ranges of the state space. The numerical accuracy of the asymptotic results is tested. AMS subject classification 60K25 60K30 34E20     

On the steady-state queue size distribution of the discrete-timeGeo/G/1 queue with repeated customers

In this paper, we study the steady-state queue size distribution of the discrete-timeGeo/G/1 retrial queue. We derive analytic formulas for the probability generating function of the number of customers in the system in steady-state. It is shown that the stochastic decomposition law holds for theGeo/G/1 retrial queue. Recursive formulas for the steady-state probabilities are developed. Computations based on these recursive formulas are numerically stable because the recursions involve only nonnegative terms. Since the regularGeo/G/1 queue is a special case of theGeo/G/1 retrial queue, the recursive formulas can also be used to compute the steady-state queue size distribution of the regularGeo/G/1 queue. Furthermore, it is shown that a continuous-timeM/G/1 retrial queue can be approximated by a discrete-timeGeo/G/1 retrial queue by dividing the time into small intervals of equal length and the approximation approaches the exact when the length of the interval tends to zero. This relationship allows us to apply the recursive formulas derived in this paper to compute the approximate steady-state queue size distribution of the continuous-timeM/G/1 retrial queue and the regularM/G/1 queue.Partially supported by the Natural Sciences and Engineering Research Council of Canada through grant OGP0046415.Partially supported by the Natural Sciences and Engineering Research Council of Canada through grant OGP0105828.     

Some results on a generalized M/G/1 feedback queue with negative customers

This paper deals with a generalized M/G/1 feedback queue in which customers are either “positive" or “negative". We assume that the service time distribution of a positive customer who initiates a busy period is G _e (x) and all subsequent positive customers in the same busy period have service time drawn independently from the distribution G _b (x). The server is idle until a random number N of positive customers accumulate in the queue. Following the arrival of the N-th positive customer, the server serves exhaustively the positive customers in the queue and then a new idle period commences. This queueing system is a generalization of the conventional N-policy queue with N a constant number. Explicit expressions for the probability generating function and mean of the system size of positive customers are obtained under steady-state condition. Various vacation models are discussed as special cases. The effects of various parameters on the mean system size and the probability that the system is empty are also analysed numerically. AMS Subject Classification: Primary: 60 K 25 · Secondary: 60 K 20, 90 B 22     

The M/G/1 retrial queue with bernoulli schedule

We consider anM/G/1 retrial queue with infinite waiting space in which arriving customers who find the server busy join either (a) the retrial group with probabilityp in order to seek service again after a random amount of time, or (b) the infinite waiting space with probabilityq(=1–p) where they wait to be served. The joint generating function of the numbers of customers in the two groups is derived by using the supplementary variable method. It is shown that our results are consistent with known results whenp=0 orp=1.     

A queueing system with linear repeated attempts,bernoulli schedule and feedback

We analyse a single-server retrial queueing system with infinite buffer, Poisson arrivals, general distribution of service time and linear retrial policy. If an arriving customer finds the server occupied, he joins with probabilityp a retrial group (called orbit) and with complementary probabilityq a priority queue in order to be served. After the customer is served completely, he will decide either to return to the priority queue for another service with probability ϑ or to leave the system forever with probability =1−ϑ, where 0≤ϑ<1. We study the ergodicity of the embedded Markov chain, its stationary distribution function and the joint generating function of the number of customers in both groups in the steady-state regime. Moreover, we obtain the generating function of system size distribution, which generalizes the well-knownPollaczek-Khinchin formula. Also we obtain a stochastic decomposition law for our queueing system and as an application we study the asymptotic behaviour under high rate of retrials. The results agree with known special cases. Finally, we give numerical examples to illustrate the effect of the parameters on several performance characteristics.     

Multiserver queue with addressed retrials

This paper presents a multiserver retrial queueing system with servers kept apart, thereby rendering it impossible for one to know the status (idle/busy) of the others. Customers proceeding to one channel will have to go to orbit if the server in it is busy and retry after some time to some channel, not necessarily the one already tried. Each orbital customer, independently of others, chooses the server randomly according to some specified probability distribution. Further this distribution is identical for all customers. We assume that the same ‘orbit’ is used by all retrial customers, between repeated attempts, to access the servers. We derive the system state probability distribution under Poisson arrival process of external customers, exponentially distributed service times and linear retrial rates to access the servers. Several system state characteristics are obtained and numerical illustrations provided. AMS subject classification: Primary 60K25 60K20     

Analysis of multiserver retrial queueing system: A martingale approach and an algorithm of solution

The paper studies a multiserver retrial queueing system withm servers. Arrival process is a point process with strictly stationary and ergodic increments. A customer arriving to the system occupies one of the free servers. If upon arrival all servers are busy, then the customer goes to the secondary queue, orbit, and after some random time retries more and more to occupy a server. A service time of each customer is exponentially distributed random variable with parameter μ₁. A time between retrials is exponentially distributed with parameter μ₂ for each customer. Using a martingale approach the paper provides an analysis of this system. The paper establishes the stability condition and studies a behavior of the limiting queue-length distributions as μ₂ increases to infinity. As μ₂→∞, the paper also proves the convergence of appropriate queue-length distributions to those of the associated “usual” multiserver queueing system without retrials. An algorithm for numerical solution of the equations, associated with the limiting queue-length distribution of retrial systems, is provided. AMS 2000 Subject classifications: 60K25 60H30.     

Tail asymptotics for the queue length in an M/G/1 retrial queue

In this paper, we study the tail behavior of the stationary queue length of an M/G/1 retrial queue. We show that the subexponential tail of the stationary queue length of an M/G/1 retrial queue is determined by that of the corresponding M/G/1 queue, and hence the stationary queue length in an M/G/1 retrial queue is subexponential if the stationary queue length in the corresponding M/G/1 queue is subexponential. Our results for subexponential tails also apply to regularly varying tails, and we provide the regularly varying tail asymptotics for the stationary queue length of the M/G/1 retrial queue. AMS subject classifications: 60J25, 60K25     

A numerically stable algorithm for two server queue models

In this paper, we consider a queueing system in which there are two exponential servers, each having his own queue, and arriving customers will join the shorter queue. Based on the results given in Flatto and McKean, we rewrite the formula for the probability that there are exactlyk customers in each queue, wherek = 0, 1,…. This enables us to present an algorithm for computing these probabilities and then to find the joint distribution of the queue lengths in the system. A program and numerical examples are given.     

The queue length in an <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/1 batch arrival retrial queue

An M/G/1 retrial queue with batch arrivals is studied. The queue length K _μ is decomposed into the sum of two independent random variables. One corresponds to the queue length K _∞ of a standard M/G/1 batch arrival queue, and another is compound-Poisson distributed. In the case of the distribution of the batch size being light-tailed, the tail asymptotics of K _μ are investigated through the relation between K _∞ and its service times.     

The <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1 retrial queue with retrials due to server failures

Sherman and Kharoufeh (Oper. Res. Lett. 34:697–705, [2006]) considered an M/M/1 type queueing system with unreliable server and retrials. In this model it is assumed that if the server fails during service of a customer, the customer leaves the server, joins a retrial group and in random intervals repeats attempts to get service. We suggest an alternative method for analysis of the Markov process, which describes the functioning of the system, and find the joint distribution of the server state, the number of customers in the queue and the number of customers in the retrial group in steady state.      

A multiserver retrial queue: regenerative stability analysis

We consider a multiserver retrial GI/G/m queue with renewal input of primary customers, interarrival time τ with rate , service time S, and exponential retrial times of customers blocked in the orbit. In the model, an arriving primary customer enters the system and gets a service immediately if there is an empty server, otherwise (if all m servers are busy) he joins the orbit and attempts to enter the system after an exponentially distributed time. Exploiting the regenerative structure of the (non-Markovian) stochastic process representing the total number of customers in the system (in service and in orbit), we determine stability conditions of the system and some of its variations. More precisely, we consider a discrete-time process embedded at the input instants and prove that if and , then the regeneration period is aperiodic with a finite mean. Consequently, this queue has a stationary distribution under the same conditions as a standard multiserver queue GI/G/m with infinite buffer. To establish this result, we apply a renewal technique and a characterization of the limiting behavior of the forward renewal time in the (renewal) process of regenerations. The key step in the proof is to show that the service discipline is asymptotically work-conserving as the orbit size increases. Included are extensions of this stability analysis to continuous-time processes, a retrial system with impatient customers, a system with a general retrial rate, and a system with finite buffer for waiting primary customers. We also consider the regenerative structure of a multi-dimensional Markov process describing the system. This work is supported by Russian Foundation for Basic Research under grants 04-07-90115 and 07-07-00088.