Analysis of the asymmetric shortest queue problem

In this paper we study a system consisting of two parallel servers withdifferent service rates. Jobs arrive according to a Poisson stream and generate an exponentially distributed workload. On arrival a job joins the shortest queue and in case both queues have equal lengths, he joins the first queue with probabilityq and the second one with probability 1 −q, whereq is an arbitrary number between 0 and 1. In a previous paper we showed for the symmetric problem, that is for equal service rates andq = 1/2, that the equilibrium distribution of the lengths of the two queues can be exactly represented by an infinite sum of product form solutions by using an elementary compensation procedure. The main purpose of the present paper is to prove a similar product form result for the asymmetric problem by using a generalization of the compensation procedure. Furthermore, it is shown that the product form representation leads to a numerically efficient algorithm. Essentially, the method exploits the convergence properties of the series of product forms. Because of the fast convergence an efficient method is obtained with upper and lower bounds for the exact solution. For states further away from the origin the convergence is faster. This aspect is also exploited in the paper.     

A single server queue with service interruptions

In this paper we characterize the queue-length distribution as well as the waiting time distribution of a single-server queue which is subject to service interruptions. Such queues arise naturally in computer and communication problems in which customers belong to different classes and share a common server under some complicated service discipline. In such queues, the viewpoint of a given class of customers is that the server is not available for providing service some of the time, because it is busy serving customers from a different class. A natural special case of these queues is the class of preemptive priority queues. In this paper, we consider arrivals according the Markovian Arrival Process (MAP) and the server is not available for service at certain times. The service times are assumed to have a general distribution. We provide numerical examples to show that our methods are computationally feasible. This revised version was published online in June 2006 with corrections to the Cover Date.     

Decay rate for a PH/M/2 queue with shortest queue discipline

In this paper, we consider a PH/M/2 queue in which each server has its own queue and arriving customers join the shortest queue. For this model, it has been conjectured that the decay rate of the tail probabilities for the shortest queue length in the steady state is equal to the square of the decay rate for the queue length in the corresponding PH/M/2 model with a single queue. We prove this fact in the sense that the tail probabilities are asymptotically geometric when the difference of the queue sizes and the arrival phase are fixed. Our proof is based on the matrix analytic approach pioneered by Neuts and recent results on the decay rates. AMS subject classifications: 60K25 · 60K20 · 60F10 · 90B22     

Some first passage time problems for the shortest queue model

We consider the symmetric shortest queue (SQ) problem. Here we have a Poisson arrival stream of rate λ feeding two parallel queues, each having an exponential server that works at rate μ. An arrival joins the shorter of the two queues; if both are of equal length the arrival joins either with probability 1/2. We consider the first passage time until one of the queues reaches the value m ₀, and also the time until both reach this level. We give explicit expressions for the first two first passage moments, conditioned on the initial queue lengths, and also the full first passage distribution. We also give some asymptotic results for m ₀→∞ and various values of ρ=λ/μ. H. Yao work was partially supported by PSC-CUNY Research Award 68751-0037. C. Knessl work was supported in part by NSF grants DMS 02-02815 and DMS 05-03745.     

A two-queue,one-server model with priority for the longer queue

The queueing model studied consists of one server and two queues. Each queue has its own Poisson arrival stream and service time distribution. After a service completion, the server proceeds with a customer from the longer queue, if the queues are unequal; if the queues are equal, the server chooses with some probability a customer from one of the queues. The model is of practical interest in performance analysis, but also of theoretical interest because the functional equation to be solved has not yet been studied in the queueing literature. A basic analysis of this functional equation is presented. Some numerical results are given to assess the influence of the present service discipline. Some new properties of L.S. transforms of service time distributions are discussed in the appendix.Dr. T. Katayama has formulated the present problem and brought it to the author's attention during his visit in October/November 1984 to the NTT-Electr. Comm. Lab.'s Musashino, Tokyo 180.     

Large deviation analysis of the single server queue

We establish the large deviation principle (LDP) for the virtual waiting time and queue length processes in the GI/GI/1 queue. The rate functions are found explicitly. As an application, we obtain the logarithmic asymptotics of the probabilities that the virtual waiting time and queue length exceed high levels at large times. Additional new results deal with the LDP for renewal processes and with the derivation of unconditional LDPs for conditional ones. Our approach applies in large deviations ideas and methods of weak convergence theory.This work was supported in part by AT&T Bell Labs.     

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.     

On the incomplete results for the heterogeneous server problem

In this article, we show that the arguments in Rykov [9] on the optimality of a threshold routing policy when there are more than two heterogeneous servers are incomplete. AMS Subject Classifications: 93E20, 60K25, 90B22     

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.     

Analysis of a single server queue with semi-Markovian service interruption

In this paper we analyze a discrete-time single server queue where the service time equals one slot. The numbers of arrivals in each slot are assumed to be independent and identically distributed random variables. The service process is interrupted by a semi-Markov process, namely in certain states the server is available for service while the server is not available in other states. We analyze both the transient and steady-state models. We study the generating function of the joint probability of queue length, the state and the residual sojourn time of the semi-Markov process. We derive a system of Hilbert boundary value problems for the generating functions. The system of Hilbert boundary value problems is converted to a system of Fredholm integral equations. We show that the system of Fredholm integral equations has a unique solution. This revised version was published online in June 2006 with corrections to the Cover Date.     

On normal approximation for maximum likelihood estimation from single server queues

This paper is concerned with the rate of convergence of the distribution of the maximum likelihood estimators of the arrival and the service rates in a GI/G/1 queueing system. This revised version was published online in June 2006 with corrections to the Cover Date.     

TheM/G/1 retrial queue with the server subject to starting failures

In this paper, we study a retrial queueing model with the server subject to starting failures. We first present the necessary and sufficient condition for the system to be stable and derive analytical results for the queue length distribution as well as some performance measures of the system in steady state. We show that the general stochastic decomposition law forM/G/1 vacation models also holds for the present system. Finally, we demonstrate that a few well known queueing models are special cases of the present model and discuss various interpretations of the stochastic decomposition law when applied to each of these special cases.Partially supported by the Natural Sciences and Engineering Research Council of Canada, grant OGP0046415.Partially supported by internal research grant of Mount Saint Vincent University.     

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.     

A Discrete-Time Geo/G/1 retrial queue with the server subject to starting failures

This paper studies a discrete-time Geo/G/1 retrial queue where the server is subject to starting failures. We analyse the Markov chain underlying the regarded queueing system and present some performance measures of the system in steady-state. Then, we give two stochastic decomposition laws and find a measure of the proximity between the system size distributions of our model and the corresponding model without retrials. We also develop a procedure for calculating the distributions of the orbit and system size as well as the marginal distributions of the orbit size when the server is idle, busy or down. Besides, we prove that the M/G/1 retrial queue with starting failures can be approximated by its discrete-time counterpart. Finally, some numerical examples show the influence of the parameters on several performance characteristics. This work is supported by the DGINV through the project BFM2002-02189.     

A two-stage tandem queue attended by a moving server with holding and switching costs

We consider a two-stage tandem queue attended by a moving server, with homogeneous Poisson arrivals and general service times. Two different holding costs for stages 1 and 2 and different switching costs from one stage to the other are considered. We show that the optimal policy in the second stage is greedy; and if the holding cost rate in the second stage is greater or equal to the rate in the first stage, then the optimal policy in the second stage is also exhaustive. Then, the optimality condition for sequential service policy in systems with zero switchover times is introduced. Considering some properties of the optimal policy, we then define a Triple-Threshold (TT) policy to approximate the optimal policy in the first stage. Finally, a model is introduced to find the optimal TT policy, and using numerical results, it is shown that the TT policy accurately approximates the optimal policy. This revised version was published online in June 2006 with corrections to the Cover Date.     

A single server queue with random arrivals and balking: Confidence interval estimation

This paper investigates a queueing system, which consists of Poisson input of customers, some of whom are lost to balking, and a single server working a shift of lengthL and providing a service whose duration can vary from customer to customer. If a service is in progress at the end of a shift, the server works overtime to complete the service. This process was motivated by the behavior of fishermen interviewed in the NY Great Lakes Creel Survey.We derive the distributions of the number of services (X), overtime and total server idle time (T), both unconditionally (for Poisson arrivals) and conditionally on the number (n) of arrivals per shift, assuming that the arrival times are not recorded in the data. These distributions provide the basis for estimation of the parameters from asingle realization of the queueing process during [0,L]. The conditional distributions also can be used to estimate common service time,w, when (n, X) or (n, T) are observed. Confidence intervals based onT are of shorter length, for all confidence coefficients, than the corresponding intervals based onX.This paper is Technical Report #BU-1019-M in the Biometrics Unit Series. The authors are grateful to N.U. Prabhu for suggestions on streamlining the distributional derivations and to D.R. Cox and C.E. McCulloch for helpful comments.     

On the transient behavior of the processor sharing queue

We analyze the transient behavior of the single server queue under the processor sharing discipline. Under fairly general assumptions, we give the rate of growth of the number of customers in the queue as well as the asymptotic behavior of the residual service times described in terms of a renormalized point process.     

On a problem with nonperiodic frequent alternation of boundary conditions imposed on fast oscillating sets

A singularly perturbed eigenvalue problem for the Laplacian in a cylinder is considered. The problem is characterized by frequent nonperiodic alternation of boundary conditions imposed on narrow strips lying on the cylinder’s lateral surface. The width of the strips is an arbitrary function of a small parameter and can oscillate rapidly, with the nature of the oscillations being arbitrary. Sharp estimates are derived for the convergence rate of the eigenvalues and eigenfunctions in the problem.     

An approximate analysis of a cyclic server queue with limited service and reservations

In this paper, we examine a queueing problem motivated by the pipeline polling protocol in satellite communications. The model is an extension of the cyclic queueing system withM-limited service. In this service mechanism, each queue, after receiving service on cyclej, makes a reservation for its service requirement in cyclej + 1. The main contribution to queueing theory is that we propose an approximation for the queue length and sojourn-time distributions for this discipline. Most approximate studies on cyclic queues, which have been considered before, examine the means only. Our method is an iterative one, which we prove to be convergent by using stochastic dominance arguments. We examine the performance of our algorithm by comparing it to simulations and show that the results are very good.     

Activity periods of an infinite server queue and performance of certain heavy tailed fluid queues

A fluid queue with ON periods arriving according to a Poisson process and having a long-tailed distribution has long range dependence. As a result, its performance deteriorates. The extent of this performance deterioration depends on a quantity determined by the average values of the system parameters. In the case when the the performance deterioration is the most extreme, we quantify it by studying the time until the amount of work in the system causes an overflow of a large buffer. This turns out to be strongly related to the tail behavior of the increase in the buffer content during a busy period of the M/G/∞ queue feeding the buffer. A large deviation approach provides a powerful method of studying such tail behavior. This revised version was published online in June 2006 with corrections to the Cover Date.