Quasi-reversible multiclass queues with order independent departure rates

This paper introduces a new class of queues which are quasi-reversible and therefore preserve product form distribution when connected in multinode networks. The essential feature leading to the quasi-reversibility of these queues is the fact that the total departure rate in any queue state is independent of the order of the customers in the queue. We call such queues order independent (OI) queues. The OI class includes a significant part of Kelly's class of symmetric queues, although it does not cover the whole class. A distinguishing feature of the OI class is that, among others, it includes the MSCCC and MSHCC queues but not the LCFS queue. This demonstrates a certain generality of the class of OI queues and shows that the quasi-reversibility of the OI queues derives from causes other than symmetry principles. Finally, we examine OI queues where arrivals to the queue are lost when the number of customers in the queue equals an upper bound. We obtain the stationary distribution for the OI loss queue by normalizing the stationary probabilities of the corresponding OI queue without losses. A teletraffic application for the OI loss queue is presented.     

A mean value formula for the M/G/1 queues controlled by workload

We present a mean value formula for the M/G/1 queues controlled by workload (such as the D-policy queues). We first prove the formula and then demonstrate its application. This formula also works for the conventional vacation systems which are controlled by number of customers (such as the N-policy queues).     

An Arrival Time Approach to M/G/1-type Queues with Generalized Vacations

We propose a simple way, called the arrival time approach, of finding the queue length distributions for M/G/1-type queues with generalized server vacations. The proposed approach serves as a useful alternative to understanding complicated queueing processes such as priority queues with server vacations and MAP/G/1 queues with server vacations.     

Heavily loaded queue coupled to two underloaded queues

We consider a system of three parallel queues with Poisson arrivals and exponentially distributed service requirements. The service rate for the heavily loaded queue depends on which of the two underloaded queues are empty. We derive the lowest-order asymptotic approximation to the joint stationary distribution of the queue lengths, in terms of a small parameter measuring the closeness of the heavily loaded queue to instability. To this order the queue lengths are independent, and the underloaded queues and the heavily loaded queue have geometrically and, after suitable scaling, exponentially distributed lengths, respectively. The expression for the exponential decay rate for the heavily loaded queue involves the solution to an inhomogeneous linear functional equation. Explicit results are obtained for this decay rate when the two underloaded queues have vastly different arrival and service rates.     

Fluid queues with synchronized output

We present a model of parallel Lévy-driven queues that mix their output into a final product; whatever cannot be mixed is sold on the open market for a lower price. The queues incur holding and capacity costs and can choose their processing rates. We solve the ensuing centralized (system optimal) and decentralized (individual station optimal) profit optimization problems. In equilibrium the queues process work faster than desirable from a system point of view. Several model extensions are also discussed.     

Non-product form equilibrium probabilities in a class of two-station closed reentrant queueing networks

While many single station queues possess explicit forms for their equilibrium probabilities, queueing networks are more problematic. Outside of the class of product form networks (e.g., Jackson, Kelly, and BCMP networks), one must resort to bounds, simulation, asymptotic studies or approximations. By focusing on a class of two-station closed reentrant queueing networks under the last buffer first served (LBFS) policy, we show that non-product form equilibrium probabilities can be obtained. When the number of customer classes in the network is five or fewer, explicit solutions can be obtained. Otherwise, we require the roots of a characteristic polynomial and a matrix inversion that depend only on the network topology. The approach relies on two key points. First, under LBFS, the state space can be reduced to four dimensions independent of the number of buffers in the system. Second, there is a sense of spatial causality in the global balance equations that can then be exploited. To our knowledge, these two-station closed reentrant queueing networks under LBFS represent the first class of queueing networks for which explicit non-product form equilibrium probabilities can be constructed (for five customer classes or less), the generic form of the equilibrium probabilities can be deduced and matrix analytic approaches can be applied. As discussed via example, there may be other networks for which related observations can be exploited.     

Interacting queues in heavy traffic

We consider a system of parallel queues with Poisson arrivals and exponentially distributed service requirements. The various queues are coupled through their service rates, causing a complex dynamic interaction. Specifically, the system consists of one primary queue and several secondary queues whose service rates depend on whether the primary queue is empty or not. Conversely, the service rate of the primary queue depends on which of the secondary queues are empty.     

Invariance relations in single server queues with LCFS service discipline

This paper is concerned with single server queues having LCFS service discipline. We give a condition to hold an invariance relation between time and customer average queue length distributions in the queues. The relation is a generalization of that in an ordinary GI/M/1 queue. We compare the queue length distributions for different single server queues with finite waiting space under the same arrival process and service requirement distribution of customer and derive invariance relations among them.This research was supported in part by a grant from the Tokyo Metropolitan Government. The latter part of this paper was written while the author resided at the University of California, Berkeley.     

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.     

Discrete time queues and matrix-analytic methods

This is an expository paper dealing with discrete time analysis of queues using matrix-analytic methods (MAM). Discrete time analysis queues has always been popular with engineers who are very keen on obtaining numerical values out of their analyses for the sake of experimentation and design. As telecommunication systems are based more on digital technology these days than analog the need to use discrete time analysis for queues has become more important. Besides, we find that several queues which are difficult to analyse by the continuous time approach are sometimes easier to analyse using discrete time method. Of course, there are some queueing problems which are easier to analyse using continuous time approach instead of discrete time. We discuss, in this paper, both the advantages and disadvantages of discrete time analysis. The paper focusses on setting up several queueing systems as discrete time quasi-birth-and-death processes and then shows how to use matrix-geometric method (MGM), a class of MAM, to analyse the problems. We point out that there are other methods for analysing such queues but MGM provides a much simpler approach for setting up the problems in order to obtain semi-explicit results for computational tractability. We also point out some of the shortcomings of MGM. The paper mainly focusses on the Geo/Geo/1, PH/PH/1, GI/G/1 and GI/G/1/K systems and some of the related problems, including vacation models with time-limited visits.     

Equilibrium and optimal behavior of customers in Markovian queues with multiple working vacations

This paper studies the customers’ equilibrium and socially optimal joining–balking behavior in single-server Markovian queues with multiple working vacations. Different from the classical vacation policies, the server does not completely stop service but maintains a low service rate in vacation state in case there are customer arrivals. Based on different precision levels of the system information, we discuss the observable queues, the partially observable queues, and the unobservable queues, respectively. For each type of queues, we get both the customers’ equilibrium and socially optimal joining–balking strategies and make numerical comparisons between them. We numerically observe that their equilibrium strategy is unique, and especially, the customers’ equilibrium joining probability in vacation state is not necessarily smaller than that in busy state in the partially observable queues. Moreover, we also find that the customers’ individual behavior always deviates from the social expectation and makes the system more congested.     

Rate Conservation Laws for Multidimensional Processes of Bounded Variation with Applications to Priority Queueing Systems

In this paper we derive a multidimensional version of the rate conservation law (RCL) for càdlàg processes of bounded variation. These results are then used to analyze queueing models which have a natural multidimensional characterization, such as priority queues. In particular the RCL is used to establish certain conservation laws between the idle probabilities for such queues. We use the relations to provide a detailed analysis of preemptive resume priority queues with M/G inputs. Special attention is paid to the validity of the so-called reduced service rate approximation.     

Batch service systems with heterogeneous servers

Bulk-service multi-server queues with heterogeneous server capacity and thresholds are commonly seen in several situations such as passenger transport or package delivery services. In this paper, we develop a novel decomposition-based solution approach for such queues using arguments from renewal theory. We then obtain the distribution of the waiting time measure for multi-type server systems. We also obtain other useful performance measures such as utilization, expected throughput time, and expected queue lengths.

     

Waiting times in queueing networks with a single shared server

We study a queueing network with a single shared server that serves the queues in a cyclic order. External customers arrive at the queues according to independent Poisson processes. After completing service, a customer either leaves the system or is routed to another queue. This model is very generic and finds many applications in computer systems, communication networks, manufacturing systems, and robotics. Special cases of the introduced network include well-known polling models, tandem queues, systems with a waiting room, multi-stage models with parallel queues, and many others. A complicating factor of this model is that the internally rerouted customers do not arrive at the various queues according to a Poisson process, causing standard techniques to find waiting-time distributions to fail. In this paper, we develop a new method to obtain exact expressions for the Laplace–Stieltjes transforms of the steady-state waiting-time distributions. This method can be applied to a wide variety of models which lacked an analysis of the waiting-time distribution until now.     

Stability of multi-class queueing networks with infinite virtual queues

We generalize the standard multi-class queueing network model by allowing both standard queues and infinite virtual queues which have an infinite supply of work. We pose the general problem of finding policies which allow some of the nodes of the network to work with full utilization, and yet keep all the standard queues in the system stable. Toward this end we show that re-entrant lines, systems of two re-entrant lines through two service stations, and rings of service stations can be stabilized with priority policies under certain parameter restrictions. The analysis throughout the paper depends on model and policy and illustrates the difficulty in solving the general problem.     

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.     

On open problems in polling systems

In the present paper we address two open problems concerning polling systems, viz., queueing systems consisting of multiple queues attended by a single server that visits the queues one at a time. The first open problem deals with a system consisting of two queues, one of which has gated service, while the other receives 1-limited service. The second open problem concerns polling systems with general (renewal) arrivals and deterministic switch-over times that become infinitely large. We discuss related, known results for both problems, and the difficulties encountered when trying to solve them.     

Order independent loss queues

This paper presents an analysis of generalized Order Independent (OI) loss queues serving customers belonging to different types (classes) where limits are placed on the number of customers of each type that may be present in the system. We prove that such queues satisfy partial balance and we present their stationary distribution. OI loss queues can be used to model blocking systems with simultaneous resource possession with the option of queueing blocked customers. The OI loss queue thus extends previous loss models where customers are rejected when processing resources are not available.This work was supported by grants from the Foundation for Research Development.     

Heavy Traffic Analysis of Two Coupled Processors

We consider two parallel queues. When both are non-empty, they behave as two independent M/M/1 queues. If one queue is empty the server in the other works at a different rate. We consider the heavy traffic limit, where the system is close to instability. We derive and analyze the heavy traffic diffusion approximation for this model. In particular, we obtain simple integral representations for the joint steady state density of the (scaled) queue lengths. Asymptotic and numerical properties of the solution are studied.     

Stochastic scheduling of parallel queues with set-up costs

We consider the problem of allocating a single server to a system of queues with Poisson arrivals. Each queue represents a class of jobs and possesses a holding cost rate, general service distribution, and a set-up cost. The objective is to minimize the expected cost due to the waiting of jobs and the switching of the server. A set-up cost is required to effect an instantaneous switch from one queue to another. We partially characterize an optimal policy and provide a simple heuristic scheduling policy. The heuristic's performance is evaluated in the cases of two and three queues by comparison with a numerically obtained optimal policy. Simulation results are provided to demonstrate the effectiveness of our heuristic over a wide range of problem instances with four queues.