Stability analysis of parallel server systems under longest queue first

We consider the stability of parallel server systems under the longest queue first (LQF) rule. We show that when the underlying graph of a parallel server system is a tree, the standard nominal traffic condition is sufficient for the stability of that system under LQF when interarrival and service times have general distributions. Then we consider a special parallel server system, which is known as the X-model, whose underlying graph is not a tree. We provide additional “drift” conditions for the stability and transience of these queueing systems with exponential interarrival and service times. Drift conditions depend in general on the stationary distribution of an induced Markov chain that is derived from the underlying queueing system. We illustrate our results with examples and simulation experiments. We also demonstrate that the stability of the LQF depends on the tie-breaking rule used and that it can be unstable even under arbitrary low loads.     

Perturbation analysis of theGI/GI/1 queue

We examine a family ofGI/GI/1 queueing processes generated by a parametric family of service time distributions,F(x,), and we show that under suitable conditions the corresponding customer stationary expectation of the system time is twice continuously differentiable with respect to. Expressions for the derivatives are given which are suitable for single run derivative estimation. These results are extended to parameters of the interarrival time distribution and expressions for the corresponding second derivatives (as well as partial second derivatives involving both interarrivai and service time parameters) are also obtained. Finally, we present perturbation analysis algorithms based on these expressions along with simulation results demonstrating their performance.     

Performance analysis approximation in a queueing system of type M/G/1

In this work, we apply the strong stability method to obtain an estimate for the proximity of the performance measures in the M/G/1 queueing system to the same performance measures in the M/M/1 system under the assumption that the distributions of the service time are close and the arrival flows coincide. In addition to the proof of the stability fact for the perturbed M/M/1 queueing system, we obtain the inequalities of the stability. These results give with precision the error, on the queue size stationary distribution, due to the approximation. For this, we elaborate from the obtained theoretical results, the STR-STAB algorithm which we execute for a determined queueing system: M/Coxian − 2/1. The accuracy of the approach is evaluated by comparison with simulation results.     

The discrete-time single-server queue

In this paper we consider the discrete-time single server queueing model with exceptional first service. For this model we cannot define the steady-state waiting-time distribution simply as the limiting distribution of the waiting times, since this limit does not always exist. Instead, we use the Cesaro limit to define the limiting waiting-time distribution. We give an exact relation between the generating functions of the steady-state waiting-time distribution and of the idle-time distribution in the case of general interarrival-time and service-time distributions. Once we have this relation, we can give more explicit results when the generating function of either the interarrival-time distribution or the service-time distribution is rational. We also derive some results on the asymptotic behaviour of the waiting-time distribution.     

Analysis of finite capacity discrete-time <Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">Geo</Emphasis>/1 queueing system with multiple vacations

This paper investigates a discrete-time single-server finite-buffer queueing system with multiple vacations in which arrivals occur according to a discrete-time renewal process. Service and vacation times are mutually independent and geometrically distributed. We obtain steady-state system length distributions at prearrival, arbitrary and outside observer's observation epochs under the late arrival system with delayed access and early arrival system. The analysis of actual waiting-time for both the systems has also been carried out. The model has potential application in high-speed computer network, digital communication systems and other related areas.     

Product form stationary distributions for queueing networks with blocking and rerouting

In this paper we study Markovian queueing networks in which the service and the routing characteristics have a particular form which leads to a product form stationary distribution for the number of customers in the various queues of the network. We show that if certain transitions are prohibited due to blocking conditions, then the form of the stationary distribution is preserved under a certain rerouting protocol. Several examples are presented which illustrate the wide applicability of the model. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotic Stability of a Stationary Flowing Regime of an Ideal Incompressible Fluid

We give sufficient conditions for asymptotic stability of a stationary solution to a flowing problem of a homogeneous incompressible fluid through a given planar domain. We consider a planar problem for the Euler equation and boundary conditions for the curl and the normal component of the velocity; moreover, the latter is given on the whole boundary of the flow domain and the curl is given only on the inlet part of the boundary. We establish asymptotic stability of a stationary flow (in linear approximation), assuming it to have no rest points and to satisfy some smallness condition which means that the perturbations leave the flow domain before they become to affect the main flow. In particular, we prove asymptotic stability for an arbitrary stationary flow in a rectangular canal close to the Couette flow without rest points. Moreover, we show that stability of the main flow in the L ₂-norm under curl perturbations implies its stability in higher-order norms depending, for example, on the derivatives of the curl.     

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.     

On the stability of queueing systems under precedence restrictions for the service of customers

We consider queueing systems under precedence-based queueing disciplines and derive conditions for the stability of the system. The precedence restrictions are posed on customers' service in a way that a service can start only if some previous customers are served completely and some later customers arrived already. The stability depends on the interarrival times only through their means and the stability condition splits into two terms: with respect to a typical customer, one is representing the influences of future arrivals and one is representing the influences of past arrivals.     

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.     

Stability of stationary states of non-local equations with singular interaction potentials

We study the large-time behaviour of a non-local evolution equation for the density of particles or individuals subject to an external and an interaction potential. In particular, we consider interaction potentials which are singular in the sense that their first derivative is discontinuous at the origin.For locally attractive singular interaction potentials we prove under a linear stability condition local non-linear stability of stationary states consisting of a finite sum of Dirac masses. For singular repulsive interaction potentials we show the stability of stationary states of uniformly bounded solutions under a convexity condition.Finally, we present numerical simulations to illustrate our results.     

Stochastic Recursive Equations with Applications to Queues with Dependent Vacations

We focus on a special class of nonlinear multidimensional stochastic recursive equations in which the coefficients are stationary ergodic (not necessarily independent). Under appropriate conditions, an explicit ergodic stationary solution for these equations is obtained and the convergence to this stationary regime is established. We use these results to analyze several queueing models with vacations. We obtain explicit solutions for several performance measures for the case of general non-independent vacation processes. We finally extend some of these results to polling systems with general vacations.     

State-dependent Coupling of Quasireversible Nodes

The seminal paper of Jackson began a chain of research on queueing networks with product-form stationary distributions which continues strongly to this day. Hard on the heels of the early results on queueing networks followed a series of papers which discussed the relationship between product-form stationary distributions and the quasireversibility of network nodes. More recently, the definition of quasireversibility and the coupling mechanism between nodes have been extended so that they apply to some of the later product-form queueing networks incorporating negative customers, signals, and batch movements.In parallel with this research, it has been shown that some special queueing networks can have arrival and service parameters which depend upon the network state, rather than just the node state, and still retain a generalised product-form stationary distribution.In this paper we begin by offering an alternative proof of a product-form result of Chao and Miyazawa and then build on this proof by postulating a state-dependent coupling mechanism for a quasireversible network. Our main theorem is that the resultant network has a generalised product form stationary distribution. We conclude the paper with some examples.     

An Alternative Model for Queueing Systems with Single Arrivals,Batch Services and Customer Coalescence

In this paper we consider a queueing system with single arrivals, batch services and customer coalescence and we use it as a building block for constructing queueing networks that incorporate such characteristics. Chao et al. (1996) considered a similar model and they proved that it possesses a geometric product form stationary distribution, under the assumption that if the number of units present at a service completion epoch is less than the required number of units, then all the units coalesce into an incomplete (defective) batch which leaves the system. We drop this assumption and we study a model without incomplete batches. We prove that the stationary distribution of such a queue has a nearly geometric form. Using quasi-reversibility arguments we construct a network model with such queues which provides relevant bounds and approximations for the behaviour of assembly processes. Several issues about the validity of these bounds and approximations are also discussed.     

On the stationary distribution of queue lengths in a multi-class priority queueing system with customer transfers

This paper deals with a multi-class priority queueing system with customer transfers that occur only from lower priority queues to higher priority queues. Conditions for the queueing system to be stable/unstable are obtained. An auxiliary queueing system is introduced, for which an explicit product-form solution is found for the stationary distribution of queue lengths. Sample path relationships between the queue lengths in the original queueing system and the auxiliary queueing system are obtained, which lead to bounds on the stationary distribution of the queue lengths in the original queueing system. Using matrix-analytic methods, it is shown that the tail asymptotics of the stationary distribution is exact geometric, if the queue with the highest priority is overloaded.      

Queueing models,block hessenberg matrices and the method of neuts

We introduce a numerical method to compute the stationary probability vector of queueing models whose infinitesimal generator is of block Hessenberg form. It is shown that the stationary probability vector is equal to the first column of the inverse of the coefficient matrix. Furthermore, it is shown that the first column of the inverse of an upper (or lower) Hessenberg matrix may be obtained in a relatively small number of operations. Together, these results allow us to define a powerful algorithm for solving certain queueing models. The efficiency of this algorithm is discussed and a comparison with the method of Neuts is undertaken. A relationship with the method of Gaussian elimination is established and used to develop some stability results.This work was supported in part by NSF Grant MCS-83-00438.     

Stock optimization for service differentiated demands with fill rate and waiting time requirements

We develop a computationally efficient optimization procedure to optimize stock and rationing levels for a model consisting of a single product with two priority–demand classes, given by mutually independent, stationary, Poisson demand processes. Each priority class has its own service levels requirements, defined by the class-specific fill rate and expected waiting-time levels. Order lead times are independent and identically distributed random variables. This is the first study in this setting to consider both waiting-time constraints along with fill rate requirements.     

Analyzing a multiserver bulk-service finite-buffer queue

This paper analyzes a finite-buffer multiserver bulk-service queueing system in which the interarrival and service times are, respectively, arbitrarily and exponentially distributed. Using the supplementary variable and the imbedded Markov chain techniques, we obtain the queue-length distributions at prearrival and arbitrary epochs. We also present Laplace–Stiltjes transform of the actual waiting-time distribution in the queue. Finally, several performance measures and a variety of numerical results in the form of tables and graphs are discussed.     

On Lévy-driven vacation models with correlated busy periods and service interruptions

This paper considers queues with server vacations, but departs from the traditional setting in two ways: (i) the queueing model is driven by Lévy processes rather than just compound Poisson processes; (ii) the vacation lengths depend on the length of the server’s preceding busy period. Regarding the former point: the Lévy process active during the busy period is assumed to have no negative jumps, whereas the Lévy process active during the vacation is a subordinator. Regarding the latter point: where in a previous study (Boxma et al. in Probab. Eng. Inf. Sci. 22:537–555, 2008) the durations of the vacations were positively correlated with the length of the preceding busy period, we now introduce a dependence structure that may give rise to both positive and negative correlations. We analyze the steady-state workload of the resulting queueing (or: storage) system, by first considering the queue at embedded epochs (viz. the beginnings of busy periods). We show that this embedded process does not always have a proper stationary distribution, due to the fact that there may occur an infinite number of busy-vacation cycles in a finite time interval; we specify conditions under which the embedded process is recurrent. Fortunately, irrespective of whether the embedded process has a stationary distribution, the steady-state workload of the continuous-time storage process can be determined. In addition, a number of ramifications are presented. The theory is illustrated by several examples.     

Waiting time approximation in single-class queueing systems with multiple types of interruptions: modeling congestion at waterways entrances

We consider a single-server queue subject to multiple types of operation-independent interruptions motivated by operations and vessel queueing at entrances of waterways. A case in point is the Strait of Istanbul. We are using waiting-time arguments and service completion time analysis to obtain the expected waiting time of a customer (vessel) in the aforementioned queue with single-class of customers and k non-simultaneous and possibly simultaneous service interruptions. In the analysis, we have used arguments and assumptions from the Strait of Istanbul that are also valid for narrow waterways at large.