Retrial queues with collision arising from unslottedCSMA/CD protocol

We consider a retrial queueing model with collision arising from the specific communication protocolCSMAICD. Under the retrial control policy in which the retrial rate is inversely proportional to the number of customers in the retrial group, we derive the generating function of the limiting distribution of the number of customers in the retrial group at the moment when the channel is free. Using the theory of Markov regenerative processes, we also obtain the limiting distribution of the number of customers in the system at arbitrary time points.This paper was supported in part by the Non-Directed Research Fund, Korea Research Foundation, 1990.     

A retrial queue with redundancy and unreliable server

Retrial queues are useful in the stochastic modelling of computer and telecommunication systems amongst others. In this paper we study a version of the retrial queue with variable service. Such a point of view gives another look at the unreliable retrial queueing problem which includes the redundancy model.By using the theory of piecewise Markovian processes, we obtain the analogue of the Pollaczek-Khintchine formula for such retrial queues, which is useful for operations researchers to obtain performance measures of interest.     

Single server retrial queues with two way communication

The main aim of this paper is to study the steady state behavior of an M/G/1-type retrial queue in which there are two flows of arrivals namely ingoing calls made by regular customers and outgoing calls made by the server when it is idle. We carry out an extensive stationary analysis of the system, including stability condition, embedded Markov chain, steady state joint distribution of the server state and the number of customers in the orbit (i.e., the retrial group) and calculation of the first moments. We also obtain light-tailed asymptotic results for the number of customers in the orbit. We further formulate a more complicate but realistic model where the arrivals and the service time distributions are modeled in terms of the Markovian arrival process (MAP) and the phase (PH) type distribution.     

On the single server retrial queue subject to breakdowns

This paper deals with a single server retrial queueing system subject to active and independent breakdowns. The objective is to extend the results given independently by Aissani [1] and Kulkarni and Choi [15]. To this end, we introduce the concept of fundamental server period and an auxiliary queueing system with breakdowns and option for leaving the system. Then, we concentrate our attention on the limiting distribution of the system state. We obtain simplified expressions for the partial generating functions of the server state and the number of customers in the retrial group, a recursive scheme for computing the limiting probabilities and closed-form formulae for the second order partial moments. Some stochastic decomposition results are also investigated. This revised version was published online in June 2006 with corrections to the Cover Date.     

Multiclass batch arrival retrial queues analyzed as branching processes with immigration

TheM/G/1 batch arrival retrial queue is studied by means of branching processes with immigration. We shall investigate this queue when traffic intensity is less than one, tends to one or is greater than one.     

Stationary queues with one autonomous server

Given a stationary stochastic continuous demand of service σ(θ_tω) dt with ∫ σ(ω)P(dω) < 1, we construct real stationary point processes $\text{(T}{}_{\mathrm{n}}\text{, n ∈}\text{Z}\text{)[T}{}_{\mathrm{n}}\text{< T}{}_{\mathrm{n}}\text{+1, lim}{}_{\mathrm{\pm \infty }}\text{T}{}_{\mathrm{n}}\text{= ±∞]}$ such that

for a given constant D \2>0. These point processes correspond to a service discipline for which a single server services during the time intervals [T_n, T_n+1[ the demand of service accumulated during the proceding intervals [T_n?1, T_n[ and take a rest of fixed duration D.     

Double-sided matching queues: Priority and impatient customers

We analyze a double-sided queue with priority that serves patient customers and customers with zero patience (i.e., impatient customers). In a two-sided market, high and low priority customers arrive to one side and match with queued customers on the opposite side. Impatient customers match with queued patient customers; when there is no queue, they leave the system unmatched. All arrivals follow independent Poisson processes. We derive exact formulae for the stationary queue length distribution and several steady-state performance measures.     

An M|G|1 Retrial Queue with Nonpersistent Customers and Orbital Search

Abstract

The M|G|1 retrial queue with nonpersistent customers and orbital search is considered. If the server is busy at the time of arrival of a primary customer, then with probability 1 ? H ₁ it leaves the system without service, and with probability H ₁ > 0, it enters into an orbit. Similarly, if the server is occupied at the time of arrival of an orbital customer, with probability 1 ? H ₂, it leaves the system without service, and with probability H ₂ > 0, it goes back to the orbit. Immediately after the completion of each service, the server searches for customers in the orbit with probability p > 0, and remains idle with probability 1 ? p. Search time is assumed to be negligible. In the case H ₂ = 1, the model is analyzed in full detail using the supplementary variable method. The joint distribution of the server state and the orbit length in steady state is studied. The structure of the busy period and its analysis in terms of Laplace transform is discussed. We also provide a direct method of calculation for the first and second moment of the busy period. In the case H ₂ < 1, closed form solution is obtained for exponentially distributed service time, in terms of hypergeometric series.     

Insensitivity in discrete time queues with a moving server

Queues in which customers request service consisting of an integral number of segments and in which the server moves from service station to service station are of considerable interest to practitioners working on digital communications networks. In this paper, we present insensitivity theorems and thereby equilibrium distributions for two discrete time queueing models in which the server may change from one customer to another after completion of each segment of service. In the first model, exactly one segment of service is provided at each time point whether or not an arrival occurs, while in the second model, at most one arrival or service occurs at each time point. In each model, customers of typet request a service time which consists ofl segments in succession with probabilityb _t(l). Examples are given which illustrate the application of the theorems to round robin queues, to queues with a persistent server, and to queues in which server transition probabilities do not depend on the server's previous position. In addition, for models in which the probability that the server moves from one position to another depends only on the distance between the positions, an amalgamation procedure is proposed which gives an insensitive model on a coarse state space even though a queue may not be insensitive on the original state space. A model of Daduna and Schassberger is discussed in this context.This work was supported by the Australian Research Council.     

Traffic processes in a class of finite Markovian queues

This paper exposes the stochastic structure of traffic processes in a class of finite state queueing systems which are modeled in continuous time as Markov processes. The theory is presented for theM/E _k /φ/L class under a wide range of queue disciplines. Particular traffic processes of interest include the arrival, input, output, departure and overflow processes. Several examples are given which demonstrate that the theory unifies many earlier works, as well as providing some new results. Several extensions to the model are discussed.     

Optimal server assignment in a two-stage tandem queueing system

We study Markovian queueing systems consisting of two stations in tandem. There is a dedicated server in each station and an additional server that can be assigned to any station. Assuming that linear holding costs are incurred by jobs in the system and two servers can collaborate to work on the same job, we determine structural properties of optimal server assignment policies under the discounted and the average cost criteria.     

Two queues with alternating service and server breakdown

We consider a queueing system with two stations served by a single server in a cyclic manner. We assume that at most one customer can be served at a station when the server arrives at the station. The system is subject to service interuption that arises from server breakdown. When a server breakdown occurs, the server must be repaired before service can resume. We obtain the approximate mean delay of customers in the system.     

Transient analysis of an M/G/1 retrial queue subject to disasters and server failures

An M/G/1 retrial queueing system with disasters and unreliable server is investigated in this paper. Primary customers arrive in the system according to a Poisson process, and they receive service immediately if the server is available upon their arrivals. Otherwise, they will enter a retrial orbit and try their luck after a random time interval. We assume the catastrophes occur following a Poisson stream, and if a catastrophe occurs, all customers in the system are deleted immediately and it also causes the server’s breakdown. Besides, the server has an exponential lifetime in addition to the catastrophe process. Whenever the server breaks down, it is sent for repair immediately. It is assumed that the service time and two kinds of repair time of the server are all arbitrarily distributed. By applying the supplementary variables method, we obtain the Laplace transforms of the transient solutions and also the steady-state solutions for both queueing measures and reliability quantities of interest. Finally, numerical inversion of Laplace transforms is carried out for the blocking probability of the system, and the effects of several system parameters on the blocking probability are illustrated by numerical inversion results.     

On computing average cost optimal policies with application to routing to parallel queues

The Approximating Sequence Method for computation of average cost optimal stationary policies in denumerahle state Markov decision chains, introduced in Sennott (1994), is reviewed. New methods for verifying the assumptions are given. These are useful for models with multidimensional state spaces that satisfy certain mild structural properties. The results are applied to four problems in the optimal routing of packets to parallel queues. Numerical results are given for one of the models.     

A BMAP/G/1 Retrial Queue with a Server Subject to Breakdowns and Repairs

In this paper, we consider a BMAP/G/1 retrial queue with a server subject to breakdowns and repairs, where the life time of the server is exponential and the repair time is general. We use the supplementary variable method, which combines with the matrix-analytic method and the censoring technique, to study the system. We apply the RG-factorization of a level-dependent continuous-time Markov chain of M/G/1 type to provide the stationary performance measures of the system, for example, the stationary availability, failure frequency and queue length. Furthermore, we use the RG-factorization of a level-dependent Markov renewal process of M/G/1 type to express the Laplace transform of the distribution of a first passage time such as the reliability function and the busy period.     

Simple bounds and monotonicity results for finite multi-server exponential tandem queues

Simple and computationally attractive lower and upper bounds are presented for the call congestion such as those representing multi-server loss or delay stations. Numerical computations indicate a potential usefulness of the bounds for quick engineering purposes. The bounds correspond to product-form modifications and are intuitively appealing. A formal proof of the bounds and related monotonicity results will be presented. The technique of this proof, which is based on Markov reward theory, is of interest in itself and seems promising for further application. The extension to the non-exponential case is discussed. For multiserver loss stations the bounds are argued to be insensitive.     

An M/G/1 retrial G-queue with preemptive resume priority and collisions subject to the server breakdowns and delayed repairs

We consider an M/G/1 retrial G-queue with preemptive resume priority and collisions under linear retrial policy subject to the server breakdowns and delayed repairs. A breakdown at the busy server is represented by the arrival of a negative customer which causes the customer being in service to be lost. The stability condition of the system is derived. Using generating function technique, the steady-state distributions of the server state and the number of customers in the orbit are obtained along with some interesting and important performance measures. The stochastic decomposition property is investigated. Further, some special cases of interest are discussed. Finally, numerical illustrations are provided.     

Analyzing priority queues with 3 classes using tree-like processes

In this paper we demonstrate how tree-like processes can be used to analyze a general class of priority queues with three service classes, creating a new methodology to study priority queues. The key result is that the operation of a 3-class priority queue can be mimicked by means of an alternate system that is composed of a single stack and queue. The evolution of this alternate system is reduced to a tree-like Markov process, the solution of which is realized through matrix analytic methods. The main performance measures, i.e., the queue length distributions and loss rates, are obtained from the steady state of the tree-like process through a censoring argument. The strength of our approach is demonstrated via a series of numerical examples. AMS Subject Classifications Primary—60K25; Secondary—60M20, 90B22