Algorithmic approximations for the busy period distribution of the M/M/c retrial queue

In this paper we deal with the main multiserver retrial queue of M/M/c type with exponential repeated attempts. This model is known to be analytically intractable due to the spatial heterogeneity of the underlying Markov chain, caused by the retrial feature. For this reason several models have been proposed for approximating its stationary distribution, that lead to satisfactory numerical implementations. This paper extends these studies by developing efficient algorithmic procedures for calculating the busy period distribution of the main approximation models of Wilkinson [Wilkinson, R.I., 1956. Theories for toll traffic engineering in the USA, The Bell System Technical Journal 35, 421–514], Falin [Falin, G.I., 1983. Calculations of probability characteristics of a multiline system with repeated calls, Moscow University Computational Mathematics and Cybernetics 1, 43–49] and Neuts and Rao [Neuts, M.F., Rao, B.M., 1990. Numerical investigation of a multiserver retrial model, Queueing Systems 7, 169–190]. Moreover, we develop stable recursive schemes for the computation of the busy period moments. The corresponding distributions for the total number of customers served during a busy period are also studied. Several numerical results illustrate the efficiency of the methods and reveal interesting facts concerning the behavior of the M/M/c retrial queue.     

A G/M/1 retrial queue with constant retrial rate

In this paper, we are concerned with the analytical treatment of an GI/M/1 retrial queue with constant retrial rate. Constant retrial rate is typical for some real world systems where the intensity of individual retrials is inversely proportional to the number of customers in the orbit or only one customer from the orbit is allowed to make the retrials. In our model, a customer who finds the server busy joins the queue in the orbit in accordance with the FCFS (first-come-first-out) discipline and only the oldest customer in the queue is allowed to make the repeated attempts to reach the server. A distinguishing feature of the considered system is an arbitrary distribution of inter-arrival times, while the overwhelming majority of the papers is devoted to the retrial systems with the stationary Poisson arrival process. We carry out an extensive analytical analysis of the queue in steady state using the well-known matrix analytic technique. The ergodicity condition and simple expressions for the stationary distributions of the system states at pre-arrival, post-arrival and arbitrary times are derived. The important and difficult problem of finding the stationary distribution of the sojourn time is solved in terms of the Laplace–Stieltjes transform. Little’s formula is proved. Numerical illustrations are presented.     

Algorithmic analysis of the Geo/Geo/c retrial queue

In this paper, we consider a discrete-time queue of Geo/Geo/c type with geometric repeated attempts. It is known that its continuous counterpart, namely the M/M/c queue with exponential retrials, is analytically intractable due to the spatial heterogeneity of the underlying Markov chain, caused from the retrial feature. In discrete-time, the occurrence of multiple events at each slot increases the complexity of the model and raises further computational difficulties. We propose several algorithmic procedures for the efficient computation of the main performance measures of this system. More specifically, we investigate the stationary distribution of the system state, the busy period and the waiting time. Several numerical examples illustrate the analysis.     

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     

Numerical Calculation of the Stationary Distribution of the Main Multiserver Retrial Queue

We are concerned with the main multiserver retrial queue of M/M/c type with exponential repeated attempts. It is known that an analytical solution of this queueing model is difficult and does not lead to numerical implementation. Based on appropriate understanding of the physical behavior, an efficient and numerically stable algorithm for computing the stationary distribution of the system state is developed. Numerical calculations are done to compare our approach with the existing approximations.     

Approximation of M/M/s/K retrial queue with nonpersistent customers

We consider the M/M/s/K retrial queues in which a customer who is blocked to enter the service facility may leave the system with a probability that depends on the number of attempts of the customer to enter the service facility. Approximation formulae for the distributions of the number of customers in service facility, waiting time in the system and the number of retrials made by a customer during its waiting time are derived. Approximation results are compared with the simulation.     

Steady state analysis of an M/G/1 queue with linear retrial policy and two phase service under Bernoulli vacation schedule

We consider a single server queueing system with two phases of heterogeneous service and Bernoulli vacation schedule which operate under the so called linear retrial policy. This model extends both the classical M/G/1 retrial queue with linear retrial policy as well as the M/G/1 queue with two phases of service and Bernoulli vacation model. We carry out an extensive analysis of the model.     

A Discrete-Time Geo /G/1 Retrial Queue with General Retrial Times

We consider a discrete-time Geo/G/1 retrial queue in which the retrial time has a general distribution and the server, after each service completion, begins a process of search in order to find the following customer to be served. We study the Markov chain underlying the considered queueing system and its ergodicity condition. We find the generating function of the number of customers in the orbit and in the system. We derive the stochastic decomposition law and as an application we give bounds for the proximity between the steady-state distributions for our queueing system and its corresponding standard system. Also, we develop recursive formulae for calculating the steady-state distribution of the orbit and system sizes. Besides, we prove that the M/G/1 retrial queue with general retrial times can be approximated by our corresponding discrete-time system. Finally, we give numerical examples to illustrate the effect of the parameters on several performance characteristics.     

A matrix continued fraction approach to multiserver retrial queues

We consider basic M/M/c/c (c≥1) retrial queues where the number of busy servers and that of customers in the orbit form a level-dependent quasi-birth-and-death (QBD) process with a special structure. Based on this structure and a matrix continued fraction approach, we develop an efficient algorithm to compute the joint stationary distribution of the numbers of busy servers and retrial customers. Through numerical experiments, we demonstrate that our algorithm works well even for M/M/c/c retrial queues with large value of c.     

A batch arrival retrial queue with two phases of service and Bernoulli vacation schedule

We consider an M X /G/1 queueing system with two phases of heterogeneous service and Bernoulli vacation schedule which operate under a linear retrial policy. In addition, each individual customer is subject to a control admission policy upon the arrival. This model generalizes both the classical M/G/1 retrial queue with arrivals in batches and a two phase batch arrival queue with a single vacation under Bernoulli vacation schedule. We will carry out an extensive stationary analysis of the system , including existence of the stationary regime, embedded Markov chain, steady state distribution of the server state and number of customer in the retrial group, stochastic decomposition and calculation of the first moment.     

A survey on retrial queues

Queueing systems in which arriving customers who find all servers and waiting positions (if any) occupied may retry for service after a period of time are called retrial queues or queues with repeated orders. Retrial queues have been widely used to model many problems in telephone switching systems, telecommunication networks, computer networks and computer systems. In this paper, we discuss some important retrial queueing models and present their major analytic results and the techniques used. Our concentration is mainly on single-server queueing models. Multi-server queueing models are briefly discussed, and interested readers are referred to the original papers for details. We also discuss the stochastic decomposition property which commonly holds in retrial queues and the relationship between the retrial queue and the queue with server vacations.     

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.     

Optimizing buffer size for the retrial queue: two state space collapse results in heavy traffic

We study a single server queueing model with admission control and retrials. In the heavy traffic limit, the main queue and retrial queue lengths jointly converge to a degenerate two-dimensional diffusion process. When this model is considered with holding and rejection costs, formal limits lead to a free boundary curve that determines a threshold on the main queue length as a function of the retrial queue length, above which arrivals must be rejected. However, it is known to be a notoriously difficult problem to characterize this curve. We aim instead at optimizing the threshold on the main queue length independently of the retrial queue length. Our main result shows that in the small and large retrial rate limits, this problem is governed by the Harrison–Taksar free boundary problem, which is a Bellman equation in which the free boundary consists of a single point. We derive the asymptotically optimal buffer size in these two extreme cases, as the scaling parameter and the retrial rate approach their limits.     

M/M/c Retrial Queue with Multiclass of Customers

We consider the M/M/c retrial queues with multiclass of customers. We show that the stationary joint distribution for the number of customers in service facility and orbit converges to those of the ordinary M/M/c with discriminatory random order service (DROS) policy as retrial rate tends to infinity. Approximation formulae for the distributions of the number of customers in service facility, the mean number of customers in orbit and the sojourn time distribution of a customer are presented. The approximations are compared with exact and simulation results.     

An algorithmic approach to the Markov chain with transition probability matrix of upper block-Hessenberg form

We present an algorithm to find an approximation for the stationary distribution for the general ergodic spatially-inhomogeneous block-partitioned upper Hessenberg form. Our approximation makes use of an associated upper block-Hessenberg matrix which is spatially homogeneous except for a finite number of blocks. We treat theMAP/G/1 retrial queue and the retrial queue with two types of customer as specific instances and give some numerical examples. The numerical results suggest that our method is superior to the ordinary finite-truncation method.     

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.      

Exact tail asymptotics for the Israeli queue with retrials and non-persistent customers

In this paper, we consider the Israeli queue which consists of a main queue with at most N groups and an infinite capacity retrial orbit. The retrial customers may become non-persistent before receiving service. This model was considered before and the decay rate function of the stationary distribution was obtained. To strengthen the result, we characterize the exact tail asymptotics by calculating the coefficient before the decay rate function.     

A discrete-time Geo[X]/G/1 retrial queue with control of admission

This paper analyses a discrete-time Geo/G/1 retrial queue with batch arrivals in which individual arriving customers have a control of admission. We study the underlying Markov chain at the epochs immediately after the slot boundaries making emphasis on the computation of its steady-state distribution. To this end we employ numerical inversion and maximum entropy techniques. We also establish a stochastic decomposition property and prove that the continuous-time M/G/1 retrial queue with batch arrivals and control of admission can be approximated by our discrete-time system. The outcomes agree with known results for special cases.     

Geo/Geo/1 retrial queue with non-persistent customers and working vacations

In this paper, we consider a Geo/Geo/1 retrial queue with non-persistent customers and working vacations. The server works at a lower service rate in a working vacation period. Assume that the customers waiting in the orbit request for service with a constant retrial rate, if the arriving retrial customer finds the server busy, the customer will go back to the orbit with probability q (0≤q≤1), or depart from the system immediately with probability $\bar{q}=1-q$ . Based on the necessary and sufficient condition for the system to be stable, we develop the recursive formulae for the stationary distribution by using matrix-geometric solution method. Furthermore, some performance measures of the system are calculated and an average cost function is also given. We finally illustrate the effect of the parameters on the performance measures by some numerical examples.     

On the distribution of the successful and blocked events in the retrial queue: A computational approach

This paper deals with the main retrial queue of M/M/c-type with exponential repeated attempts. We refer to a busy period and present a detailed computational analysis of four new performance measures: (i) the successful retrials, (ii) the blocked retrials, (iii) the successful primary arrivals, and (iv) the blocked primary arrivals.