Two competing discrete-time queues with priority

This paper considers a class of two discrete-time queues with infinite buffers that compete for a single server. Tasks requiring a deterministic amount of service time, arrive randomly to the queues and have to be served by the server. One of the queues has priority over the other in the sense that it always attempts to get the server, while the other queue attempts only randomly according to a rule that depends on how long the task at the head of the queue has been waiting in that position. The class considered is characterized by the fact that if both queues compete and attempt to get the server simultaneously, then they both fail and the server remains idle for a deterministic amount of time. For this class we derive the steady-state joint generating function of the state probabilities. The queueing system considered exhibits interesting behavior, as we demonstrate by an example.     

A finite capacity multi-queueing system with priorities and with repeated server vacations

In this paper, we study an M/G/1 multi-queueing system consisting ofM finite capacity queues, at which customers arrive according to independent Poisson processes. The customers require service times according to a queue-dependent general distribution. Each queue has a different priority. The queues are attended by a single server according to their priority and are served in a non-preemptive way. If there are no customers present, the server takes repeated vacations. The length of each vacation is a random variable with a general distribution function. We derive steady state formulas for the queue length distribution and the Laplace transform of the queueing time distribution for each queue.     

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.     

Networks of infinite-server queues with nonstationary Poisson input

In this paper we focus on networks of infinite-server queues with nonhomogeneous Poisson arrival processes. We start by introducing a more general Poisson-arrival-location model (PALM) in which arrivals move independently through a general state space according to a location stochastic process after arriving according to a nonhomogeneous Poisson process. The usual open network of infinite-server queues, which is also known as a linear population process or a linear stochastic compartmental model, arises in the special case of a finite state space. The mathematical foundation is a Poisson-random-measure representation, which can be obtained by stochastic integration. It implies a time-dependent product-form result: For appropriate initial conditions, the queue lengths (numbers of customers in disjoint subsets of the state space) at any time are independent Poisson random variables. Even though there is no dependence among the queue lengths at each time, there is important dependence among the queue lengths at different times. We show that the joint distribution is multivariate Poisson, and calculate the covariances. A unified framework for constructing stochastic processes of interest is provided by stochastically integrating various functionals of the location process with respect to the Poisson arrival process. We use this approach to study the flows in the queueing network; e.g., we show that the aggregate arrival and departure processes at a given queue (to and from other queues as well as outside the network) are generalized Poisson processes (without necessarily having a rate or unit jumps) if and only if no customer can visit that queue more than once. We also characterize the aggregate arrival and departure processes when customers can visit the queues more frequently. In addition to obtaining structural results, we use the stochastic integrals to obtain explicit expressions for time-dependent means and covariances. We do this in two ways. First, we decompose the entire network into a superposition of independent networks with fixed deterministic routes. Second, we make Markov assumptions, initially for the evolution of the routes and finally for the entire location process. For Markov routing among the queues, the aggregate arrival rates are obtained as the solution to a system of input equations, which have a unique solution under appropriate qualifications, but not in general. Linear ordinary differential equations characterize the time-dependent means and covariances in the totally Markovian case.     

Cooperation in Markovian queueing models

In this paper we study some cooperative models in Markovian queues. We stress the case of several agents agreeing to maintain a common server for their populations in which a priority scheme with preemption has been established. In this situation we propose and characterize an allocation rule for the holding costs that provides core allocations.     

Factorization and Stochastic Decomposition Properties in Bulk Queues with Generalized Vacations

This paper considers a class of stationary batch-arrival, bulk-service queues with generalized vacations. The system consists of a single server and a waiting room of infinite capacity. Arrivals of customers follow a batch Markovian arrival process. The server is unavailable for occasional intervals of time called vacations, and when it is available, customers are served in groups of fixed size B. For this class of queues, we show that the vector probability generating function of the stationary queue length distribution is factored into two terms, one of which is the vector probability generating function of the conditional queue length distribution given that the server is on vacation. The special case of batch Poisson arrivals is carefully examined, and a new stochastic decomposition formula is derived for the stationary queue length distribution.AMS subject classification: 60K25, 90B22, 60K37     

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.     

Vacation models in discrete time

A class of single server vacation queues which have single arrivals and non-batch service is considered in discrete time. It is shown that provided the interarrival, service, vacation, and server operational times can be cast with Markov-based representation then this class of vacation model can be studied as a matrix–geometric or a matrix-product problem – both in the matrix–analytic family – thereby allowing us to use well established results from Neuts (1981). Most importantly it is shown that using discrete time approach to study some vacation models is more appropriate and makes the models much more algorithmically tractable. An example is a vacation model in which the server visits the queue for a limited duration. The paper focuses mainly on single arrival and single unit service systems which result in quasi-birth-and-death processes. The results presented in this paper are applicable to all this class of vacation queues provided the interarrival, service, vacation, and operational times can be represented by a finite state Markov chain.An erratum to this article can be found at     

Stability of a two-queue cyclic polling system with BMAPs under gated service and state-dependent time-limited service disciplines

The stability of a cyclic polling system, with a single server and two infinite-buffer queues, is considered. Customers arrive at the two queues according to independent batch Markovian arrival processes. The first queue is served according to the gated service discipline, and the second queue is served according to a state-dependent time-limited service discipline with the preemptive repeat-different property. The state dependence is that, during each cycle, the predetermined limited time of the server’s visit to the second queue depends on the queue length of the first queue at the instant when the server last departed from the first queue. The mean of the predetermined limited time for the second queue either decreases or remains the same as the queue length of the first queue increases. Due to the two service disciplines, the customers in the first queue have higher service priority than the ones in the second queue, and the service fairness of the customers with different service priority levels is also considered. In addition, the switchover times for the server traveling between the two queues are considered, and their means are both positive as well as finite. First, based on two embedded Markov chains at the cycle beginning instants, the sufficient and necessary condition for the stability of the cyclic polling system is obtained. Then, the calculation methods for the variables related to the stability condition are given. Finally, the influence of some parameters on the stability condition of the cyclic polling system is analyzed. The results are useful for engineers not only checking whether the given cyclic polling system is stable, but also adjusting some parameters to make the system satisfy some requirements under the condition that the system is stable.     

Towards minimum loss job routing to parallel heterogeneous multiserver queues via index policies

This paper considers a Markovian model for the optimal dynamic routing of homogeneous traffic to parallel heterogeneous queues, each having its own finite input buffer and server pool, where buffer and server-pool sizes, as well as service rates, may differ across queues. The main goal is to identify a heuristic index-based routing policy with low complexity that consistently attains a nearly minimum average loss rate (or, equivalently, maximum throughput rate). A second goal is to compare alternative policies, with respect to computational demands and empirical performance. A novel routing policy that can be efficiently computed is developed based on a second-order extension to Whittle’s restless bandit (RB) index, since the latter is constant for this model. New results are also given for the more computationally demanding index policy obtained via policy improvement (PI), including that it reduces to shortest queue routing under symmetric buffer and server-pool sizes. A numerical study shows that the proposed RB index policy is nearly optimal across the instances considered, and substantially outperforms several previously proposed index policies.     

Markovian queues with Poisson control

We investigate Markovian queues that are examined by a controller at random times determined by a Poisson process. Upon examination, the controller sets the service speed to be equal to the minimum of the current number of customers in the queue and a certain maximum service speed; this service speed prevails until the next examination time. We study the resulting two-dimensional Markov process of queue length and server speed, in particular two regimes with time scale separation, specifically for infinitely frequent and infinitely long examination times. In the intermediate regime the analysis proves to be extremely challenging. To gain further insight into the model dynamics we then analyse two variants of the model in which the controller is just an observer and does not change the speed of the server.     

The MMCPP/GE/c Queue

We obtain the queue length probability distribution at equilibrium for a multi-server, single queue with generalised exponential (GE) service time distribution and a Markov modulated compound Poisson arrival process (MMCPP) – i.e., a Poisson point process with bulk arrivals having geometrically distributed batch size whose parameters are modulated by a Markovian arrival phase process. This arrival process has been considered appropriate in ATM networks and the GE service times provide greater flexibility than the more conventionally assumed exponential distribution. The result is exact and is derived, for both infinite and finite capacity queues, using the method of spectral expansion applied to the two dimensional (queue length by phase of the arrival process) Markov process that describes the dynamics of the system. The Laplace transform of the interdeparture time probability density function is then obtained. The analysis therefore could provide the basis of a building block for modelling networks of switching nodes in terms of their internal arrival processes, which may be both correlated and bursty.     

A note on the stability of the many-queue head-of-the-line processor-sharing system with permanent customers

We consider a single server system consisting of n queues with different types of customers and k permanent customers. The permanent customers and those at the head of the queues are served in processor-sharing by the service facility (head-of-the-line processor-sharing). By means of Loynes’ monotonicity method a stationary work load process is constructed and using sample path analysis general stability conditions are derived. They allow to decide which queues are stable and, moreover, to compute the fraction of processor capacity devoted to the permanent customers. In case of a stable system the constructed stationary state process is the only one and for any initial state the system converges pathwise to the steady state. This revised version was published online in June 2006 with corrections to the Cover Date.     

Conditional and unconditional distributions forM/G/1 type queues with server vacations

M/G/1 queues with server vacations have been studied extensively over the last two decades. Recent surveys by Boxma [3], Doshi [5] and Teghem [14] provide extensive summary of literature on this subject. More recently, Shanthikumar [11] has generalized some of the results toM/G/1 type queues in which the arrival pattern during the vacations may be different from that during the time the server is actually working. In particular, the queue length at the departure epoch is shown to decompose into two independent random variables, one of which is the queue length at the departure epoch (arrival epoch, steady state) in the correspondingM/G/1 queue without vacations. Such generalizations are important in the analysis of situations involving reneging, balking and finite buffer cyclic server queues. In this paper we consider models similar to the one in Shanthikumar [11] but use the work in the system as the starting point of our investigation. We analyze the busy and idle periods separately and get conditional distributions of work in the system, queue length and, in some cases, waiting time. We then remove the conditioning to get the steady state distributions. Besides deriving the new steady state results and conditional waiting time and queue length distributions, we demonstrate that the results of Boxma and Groenendijk [2] follow as special cases. We also provide an alternative approach to deriving Shanthikumar's [11] results for queue length at departure epochs.     

Analysis of a Discrete-Time Queueing System with a Single Server and Heterogeneous Markovian Arrivals

We consider a discrete-time queueing system with a single deterministic server, heterogeneous Markovian arrivals and finite capacity. Most existing techniques model the queueing system using a direct bivariate Markov chain which requires a state space that grows rapidly as the number of customer types increases. In this paper, we define renewal cycles in terms of the input process and model the system occupancy level on each renewal cycle using a one-dimensional Markov chain. We derive the exact joint steady-state probability distribution of both states of input and system occupancy with a considerably reduced state space, which leads to the efficient calculation of overall/individual performance measures such as loss probability and average delay.     

Moderate deviations for queues in critical loading

We establish logarithmic asymptotics of moderate deviations for queue-length and waiting-time processes in single server queues and open queueing networks in critical loading. Our results complement earlier diffusion approximation results. This revised version was published online in June 2006 with corrections to the Cover Date.     

A two-queue model with Bernoulli service schedule and switching times

In this paper, we present a detailed analysis of a cyclic-service queueing system consisting of two parallel queues, and a single server. The server serves the two queues with a Bernoulli service schedule described as follows. At the beginning of each visit to a queue, the server always serves a customer. At each epoch of service completion in the ith queue at which the queue is not empty, the server makes a random decision: with probability p_i, it serves the next customer; with probability 1-p_i, it switches to the other queue. The server takes switching times in its transition from one queue to the other. We derive the generating functions of the joint stationary queue-length distribution at service completion instants, by using the approach of the boundary value problem for complex variables. We also determine the Laplace-Stieltjes transforms of waiting time distributions for both queues, and obtain their mean waiting times. This revised version was published online in June 2006 with corrections to the Cover Date.     

Approximation of throughput in tandem queues with multiple servers and blocking

In this paper, we develop an approximation method for throughput in tandem queues with multiple independent reliable servers at each stage and finite buffers between service stations. We consider the blocking after service (BAS) blocking protocol of each service stage. The service time distribution of each server is exponential. The approximation is based on the decomposition of the system into a set of coupled subsystems which are modeled by two-stage tandem queue with two buffers and are analyzed by using the level dependent quasi-birth-and-death (LDQBD) process.     

Matrix analytic methods for a multi-server retrial queue with buffer

We present numerical methods for obtaining the stationary distribution of states for multi-server retrial queues with Markovian arrival process, phase type service time distribution with two states and finite buffer; and moments of the waiting time. The methods are direct extensions of the ones for the single server retrial queues earlier developed by the authors. The queue is modelled as a level dependent Markov process and the generator for the process is approximated with one which is spacially homogeneous above some levelN. The levelN is chosen such that the probability associated with the homogeneous part of the approximated system is bounded by a small tolerance and the generator is eventually truncated above that level. Solutions are obtained by efficient application of block Gaussian elimination.     

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.