A fluid queue driven by a Markovian queue

We consider an infinite buffer fluid queue receiving its input from the output of a Markovian queue with finite or infinite waiting room. The input is characterized by a Markov modulated rate process. We derive a new approach for the computation of the stationary buffer content. This approach leads to a numerically stable algorithm for which the precision of the result can be given in advance. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the optimal design of tandem queueing systems with finite buffers

We consider tandem queueing systems that can be formulated as a continuous-time Markov chain, and investigate how to maximize the throughput when the queue capacities are limited. We consider various constrained optimization problems where the decision variables are of one or more of the following types: (1) expected service times, (2) queue capacities, and (3) the number of servers at the respective stations. After surveying our previous studies of this kind, we open up consideration of three new problems by presenting some numerical results that should give some insight into the general form of the optimal design.     

A Finite Buffer Fluid Queue Driven by a Markovian Queue

We consider a finite buffer fluid queue receiving its input from the output of a Markovian queue with finite or infinite waiting room. The input flow into the fluid queue is thus characterized by a Markov modulated input rate process and we derive, for a wide class of such input processes, a procedure for the computation of the stationary buffer content of the fluid queue and the stationary overflow probability. This approach leads to a numerically stable algorithm for which the precision of the result can be specified in advance.     

A fork-join queueing model: Diffusion approximation,integral representations and asymptotics

We consider two parallel M/M/1 queues which are fed by a single Poisson arrival stream. An arrival splits into two parts, with each part joining a different queue. This is the simplest example of a fork-join model. After the individual parts receive service, they may be joined back together, though we do not consider the join part here. We study this model in the heavy traffic limit, where the service rate in either queue is only slightly larger than the arrival rate. In this limit we obtain asymptotically the joint steady-state queue length distribution. In the symmetric case, where the two servers are identical, this distribution has a very simple form. In the non-symmetric case we derive several integral representations for the distribution. We then evaluate these integrals asymptotically, which leads to simple formulas which show the basic qualitative structure of the joint distribution function.     

Stationary tail asymptotics of a tandem queue with feedback

Motivated by applications in manufacturing systems and computer networks, in this paper, we consider a tandem queue with feedback. In this model, the i.i.d. interarrival times and the i.i.d. service times are both exponential and independent. Upon completion of a service at the second station, the customer either leaves the system with probability p or goes back, together with all customers currently waiting in the second queue, to the first queue with probability 1−p. For any fixed number of customers in one queue (either queue 1 or queue 2), using newly developed methods we study properties of the exactly geometric tail asymptotics as the number of customers in the other queue increases to infinity. We hope that this work can serve as a demonstration of how to deal with a block generating function of GI/M/1 type, and an illustration of how the boundary behaviour can affect the tail decay rate.     

On the optimality of a maintenance queueing system

We consider a finite single-server maintenance queue with multiple types of customers. The difference between customers' types is defined by the offered rewards. We show that the optimal admission control policy for maximizing the long-run average reward per unit time has a trunk reservation structure. Meanwhile, if the equipment is off, there exists a threshold of the queue length, above which the optimal repair speed is increasing in the queue length and below which the optimal repair speed is 0.     

Further second-order properties of certain single-server queueing systems

The Laplace-Stieltjes transform of the variance function V(y) = var (N(0, y]) for the number N(0, y] of departures in a time interval of length y is found for stationary M/G/1 and G1/M/1 queueing systems. It is shown that for G1/M/1 systems V(y) is linear only for M/M/1.     

Analysis of the symmetric join the shortest orbit queue

This work introduces the join the shortest queue policy in the retrial setting. We consider a Markovian single server retrial system with two infinite capacity orbits. An arriving job finding the server busy, it is forwarded to the least loaded orbit. Otherwise, it is forwarded to an orbit randomly. Orbiting jobs of either type retry to access the server independently. We investigate the stability condition, the stationary tail decay rate, and obtain the equilibrium distribution by using the compensation method.     

A semidefinite optimization approach to the steady-state analysis of queueing systems

Obtaining (tail) probabilities from a transform function is an important topic in queueing theory. To obtain these probabilities in discrete-time queueing systems, we have to invert probability generating functions, since most important distributions in discrete-time queueing systems can be determined in the form of probability generating functions. In this paper, we calculate the tail probabilities of two particular random variables in discrete-time priority queueing systems, by means of the dominant singularity approximation. We show that obtaining these tail probabilities can be a complex task, and that the obtained tail probabilities are not necessarily exponential (as in most ‘traditional’ queueing systems). Further, we show the impact and significance of the various system parameters on the type of tail behavior. Finally, we compare our approximation results with simulations.     

Response time in a tandem queue with blocking, Markovian arrivals and phase-type services

A novel approach for obtaining the response time in a discrete-time tandem-queue with blocking is presented. The approach constructs a Markov chain based on the age of the leading customer in the first queue. We also provide a stability condition and carry out several numerical examples.     

On a class of approximations for closed queueing networks

This paper presents some analytical results concerning an approximation procedure for closed queueing networks. The procedure is well-known and has been found useful for product-form networks where large numbers of queues, jobs or job classes prohibit an exact analysis, as well as for networks which do not possess product-form. The procedure represents the mean sojourn time at a queue as a function of the throughput of the queue, and derives a set of fixed point equations for the throughputs of the various job classes. We begin by showing that under a mild regularity condition the fixed point equations have a unique solution. Then we show that derivatives of performance measures can be readily calculated, and that their simple form provides an interesting insight into capacity allocation in closed queueing networks.This work was supported in part by the Nuffield Foundation     

On queueing with customer impatience until the beginning of service

We study queueing systems where customers have strict deadlines until the beginning of their service. An analytic method is given for the analysis of a class of such queues, namely, models. These are queues with state-dependent Poisson arrival process, exponential service times, multiple servers, FCFS service discipline, and general customer impatience. The state of the system is viewed to be the number of customers in the system. The principal measure of performance is the probability measure induced by the offered waiting time. Other measures of interest are the probability of missing deadline and the probability of blocking. Closed-form solutions are derived for the steady-state probabilities of the state process and some important modeling variables and parameters. The efficacy of our method is illustrated through a numerical example. This revised version was published online in June 2006 with corrections to the Cover Date.     

Queueing systems fed by many exponential on-off sources: an infinite-intersection approach

In queueing theory, an important class of events can be written as ‘infinite intersections’. For instance, in a queue with constant service rate c, busy periods starting at 0 and exceeding L > 0 are determined by the intersection of the events , i.e., queue Q _t is empty at 0 and for all t∊ [0, L] the amount of traffic A _t arriving in [0,t) exceeds the server capacity. Also the event of exceeding some predefined threshold in a tandem queue, or a priority queue, can be written in terms of this kind of infinite intersections. This paper studies the probability of such infinite intersections in queueing systems fed by a large number n of i.i.d. traffic sources (the so-called ‘many-sources regime’). If the sources are of the exponential on-off type, and the queueing resources are scaled proportional to n, the probabilities under consideration decay exponentially; we explicitly characterize the corresponding decay rate. The techniques used stem from large deviations theory (particularly sample-path large deviations). M. Mandjes is also with Korteweg-de Vries Institute, University of Amsterdam, Amsterdam, the Netherlands, and EURANDOM, Eindhoven, the Netherlands. Work done while P. Mannersalo was on leave at CWI. MSC 2000: 60F10 (Large deviations), 60K25 (Queueing theory)     

The asymptotic behavior of queueing systems: Large deviations theory and dominant pole approximation

This paper presents the exact asymptotics of the steady state behavior of a broad class of single-node queueing systems. First we show that the asymptotic probability functions derived using large deviations theory are consistent (in a certain sense) with the result using dominant pole approximations. Then we present an exact asymptotic formula for the cumulative probability function of the queue occupancy and relate it to the cell loss ratio, an important performance measure for service systems such as ATM networks. The analysis relies on a new generalization of the Taylor coefficients of a complex function which we call characteristic coefficients. Finally we apply our framework to obtain new results for the M/D/1 system and for a more intricate multiclass M/D/n system.     

M/G/1 retrial queueing systems with two types of calls and finite capacity

We consider anM/G/1 priority retrial queueing system with two types of calls which models a telephone switching system and a cellular mobile communication system. In the case that arriving calls are blocked due to the server being busy, type I calls are queued in a priority queue of finite capacityK whereas type II calls enter the retrial group in order to try service again after a random amount of time. In this paper we find the joint generating function of the numbers of calls in the priority queue and the retrial group in closed form. When ₁=0, it is shown that our results are consistent with the known results for a classical retrial queueing system.     

Queue Length Distribution in a FIFO Single-Server Queue with Multiple Arrival Streams Having Different Service Time Distributions

This paper considers the queue length distribution in a class of FIFO single-server queues with (possibly correlated) multiple arrival streams, where the service time distribution of customers may be different for different streams. It is widely recognized that the queue length distribution in a FIFO queue with multiple non-Poissonian arrival streams having different service time distributions is very hard to analyze, since we have to keep track of the complete order of customers in the queue to describe the queue length dynamics. In this paper, we provide an alternative way to solve the problem for a class of such queues, where arrival streams are governed by a finite-state Markov chain. We characterize the joint probability generating function of the stationary queue length distribution, by considering the joint distribution of the number of customers arriving from each stream during the stationary attained waiting time. Further we provide recursion formulas to compute the stationary joint queue length distribution and the stationary distribution representing from which stream each customer in the queue arrived.     

Stability of a class of networked control systems with Markovian characterization

This paper studies the stability problem for a class of networked control systems (NCSs) with the plant being a Markovian jump system. The random delays from the sensor to the controller and from the controller to the actuator are modeled as two Markov chains. The necessary and sufficient conditions for the stochastic stability are established. The state-feedback controller gain that depends on not only the delay modes but also the system mode is obtained through the iterative linear matrix inequality approach. An illustrative example is presented to demonstrate the effectiveness of the proposed method.     

Analysis of a single-server queue interacting with a fluid reservoir

We consider a single-server queueing system with Poisson arrivals in which the speed of the server depends on whether an associated fluid reservoir is empty or not. Conversely, the rate of change of the content of the reservoir is determined by the state of the queueing system, since the reservoir fills during idle periods and depletes during busy periods of the server. Our interest focuses on the stationary joint distribution of the number of customers in the system and the content of the fluid reservoir, from which various performance measures such as the steady-state sojourn time distribution of a customer may be obtained. We study two variants of the system. For the first, in which the fluid reservoir is infinitely large, we present an exact analysis. The variant in which the fluid reservoir is finite is analysed approximatively through a discretization technique. The system may serve as a mathematical model for a traffic regulation mechanism - a two-level traffic shaper - at the edge of an ATM network, regulating a very bursty source. We present some numerical results showing the effect of the mechanism. This revised version was published online in June 2006 with corrections to the Cover Date.     

Transient solution of a non-empty chemical queueing system

In this paper, we illustrate that a power series technique can be used to derive explicit expressions for the transient state distribution of a queueing problem having “chemical” rules with an arbitrary number of customers present initially in the system. Based on generating function and Laplace techniques Conolly et al. (in Math Sci 22:83–91, 1997) have obtained the distributions for a non-empty chemical queue. Their solution enables us only to recover the idle probability of the system in explicit form. Here, we extend not only the model of Conolly et al. but also get a new and simple solution for this model. The derived formula for the transient state is free of Bessel function or any integral forms. The transient solution of the standard M/M/1/∞ queue with λ = μ is a special case of our result. Furthermore, the probability density function of the virtual waiting time in a chemical queue is studied. Finally, the theory is underpinned by numerical results.