Using state reduction for computing steady state vectors in Markov chains ofM/G/1 type

This paper presents a state reduction based algorithm for computing the steady state probability vectors of the embedded Markov chains ofM/G/1 type. The algorithm is based on the use of the notion of a state reduction box for streamlining compution. The computational details are linked directly to the theoretical results developed recently by Grassmann and Heyman [6]. Exploiting these connections and a method given in Neuts [18] for finding theG matrix forPH/PH/1 queues, we also propose an hybrid approach for solvingPH/PH/1 queues. Using several numerical examples, we report our computational experiences and present some observations about the relative merits of these approaches.     

Transform-free equations for the stationary waiting time distributions in the queue with poisson arrivals and bulk services

We study a queue with Poisson arrivals and a bulk service rule with two thresholdsN andm on the group sizes. No group of fewer thanN or more thanm customers is served. When the number of available customers is betweenN andm, all customers are served together. The principal results deal with the joint stationary distribution of the waiting time of an arriving customer and of the size of the group in which he is eventually served. After prior computation of the stationary queue length density, the evaluation of the waiting time distribution is reduced to the solution of a system of linear differential equations and a single integral equation. The process describing the waiting time is in general non-Markovian.University of Delaware, Applied Mathematics Institute, Technical Report No. 95 B, May 1984.This research was supported by Grant No. ECS-8205404 of the National Science Foundation and by a Senior U.S. Scientist Award of the Alexander von Humboldt Foundation.     

A simple proof for the matrix-geometric theorem

For block-partitioned matrices of the GI/M/1 type, it has been shown by M. F. Neuts that the stationary probability vector, when it exists, has a matrix-geometric form. We present here a new proof, which we believe to be the simplest available today.     

Some limit theorems for regenerative queues

We consider a single server queue with the interarrival times and the service times forming a regenerative sequence. This traffic class includes the standard models: iid, periodic, Markov modulated (e.g., BMAP model of Lucantoni [18]) and their superpositions. This class also includes the recently proposed traffic models in high speed networks, exhibiting long range dependence. Under minimal conditions we obtain the rates of convergence to stationary distributions, finiteness of stationary moments, various functional limit theorems and the continuity of stationary distributions and moments. We use the continuity results to obtain approximations for stationary distributions and moments of an MMPP/GI/1 queue where the modulating chain has a countable state space. We extend all our results to feed-forward networks where the external arrivals to each queue can be regenerative. In the end we show that the output process of a leaky bucket is regenerative if the input process is and hence our results extend to a queue with arrivals controlled by a leaky bucket. This revised version was published online in June 2006 with corrections to the Cover Date.     

Application of the method of collective marks to someM/G/1 vacation models with exhaustive service

We use the Method of Collective Marks to analyze some time-dependent processes in theM/G/1 queue with single and multiple vacations. With the server state specified at a fixed timet>0, the Laplace transforms with respect tot of mixed transforms for the joint distribution of the number of departures by timet, the queue length, the virtual waiting time, the elapsed and remaining service/vacation times at timet are derived by means of probabilistic interpretations. The Laplace-Stieltjes transform of the virtual waiting time at timet is also given. Some well known results are special cases.This research was supported by the University of Amsterdam.     

On some relations between stationary time and customer state probabilities for qneueing systems G/GI/s/r

By means of a general formula for stochastic processes with imbedded marked point processes (PMP) some necessary and sufficient condition is given for the validity of a relationship, which is well-known in the case of exponentially distributed service times, between stationary time and customer state probabilities for loss systems G/GI/s/O (Theorem 3). A result of Miyazawa for the GI/GI/l/∞ queue is generalized to the case of non-recurrent interarrival times (Theorem 4)-. Furthermore, bounds are derived for the mean increment of the waiting time process at arrival epochs and for the mean actual waiting time in multi-server queues.     

Discrete-time GI/G/1 retrial queues with time-controlled vacation policies

A discrete-time GI/G/1 retrial queue with Bernoulli retrials and time-controlled vacation policies is investigated in this paper. By representing the inter-arrival, service and vacation tlmes using a Markov-based approach, we are able to analyze this model as a level-dependent quasi-birth-and-death （LDQBD） process which makes the model algorithmically tractable. Several performance measures such as the stationary probability distribution and the expected number of customers in the orbit have been discussed with two different policies： deterministic time-controlled system and random time-controlled system. To give a comparison with the known vacation policy in the literature, we present the exhaustive vacation policy as a contrast between these policies under the early arrival system （EAS） and the late arrival system with delayed access （LAS-DA）. Significant difference between EAS and LAS-DA is illustrated by some numerical examples.     

Single server retrial queues with two way communication

The main aim of this paper is to study the steady state behavior of an M/G/1-type retrial queue in which there are two flows of arrivals namely ingoing calls made by regular customers and outgoing calls made by the server when it is idle. We carry out an extensive stationary analysis of the system, including stability condition, embedded Markov chain, steady state joint distribution of the server state and the number of customers in the orbit (i.e., the retrial group) and calculation of the first moments. We also obtain light-tailed asymptotic results for the number of customers in the orbit. We further formulate a more complicate but realistic model where the arrivals and the service time distributions are modeled in terms of the Markovian arrival process (MAP) and the phase (PH) type distribution.     

M/G/1/N vacation model with varying E-limited service discipline

We define and analyze anM/G/1/N vacation model that uses a service discipline that we call theE-limited with limit variation discipline. According to this discipline, the server provides service until either the system is emptied (i.e. exhausted) or a randomly chosen limit ofl customers has been served. The server then goes on a vacation before returning to service the queue again. The queue length distribution and the Laplace-Stieltjes transforms of the waiting time, busy period and cycle time distributions are found. Further, an expression for the mean waiting time is developed. Several previously analyzed service disciplines, including Bernoulli scheduling, nonexhaustive service and limited service, are special cases of the general varying limit discipline that is analyzed in this paper.     

A tandem Jackson network with feedback to the first node

AnN-node tandem queueing network with Bernoulli feedback to the end of the queue of thefirst node is considered. We first revisit the single-nodeM/G/1 queue with Bernoulli feedback, and derive a formula forEL(n), the expected queue length seen by a customer at his nth feedback. We show that, asn becomes large,EL(n) tends to /(l ), being the effective traffic intensity. We then treat the entire queueing network and calculate the mean value ofS, the total sojourn time of a customer in theN-node system. Based on these results we study the problem ofoptimally ordering the nodes so as to minimize ES. We show that this is a special case of a general sequencing problem and derive sufficient conditions for an optimal ordering. A few extensions of the serial queueing model are also analyzed. We conclude with an appendix in which we derive an explicit formula for the correlation coefficient between the number of customers seen by an arbitrary arrival to anM/G/1 queue, and the number of customers he leaves behind him upon departure. For theM/M/1 queue this coefficient simply equals the traffic intensity .     

A first passage time problem for spectrally positive Lévy processes and its application to a dynamic priority queue

We study a first passage time problem for a class of spectrally positive Lévy processes. By considering the special case where the Lévy process is a compound Poisson process with negative drift, we obtain the Laplace–Stieltjes transform of the steady-state waiting time distribution of low-priority customers in a two-class M/GI/1$M/GI/1$ queue operating under a dynamic non-preemptive priority discipline. This allows us to observe how the waiting time of customers is affected as the policy parameter varies.     

On the complete monotonicity of the waiting time density in some GI/G/k systems

In this note the complete monotonicity of the waiting time density in GI/G/k queues is proved under the assumption that the service time density is completely monotone. This is an extension of Keilson's [3] result for M/G/1 queues. We also provide another proof of the result that complete monotonicity is preserved by geometric compounding.     

Ergodic theorems for queuing systems with dependent inter-arrival times

We study a G/GI/1 single-server queuing model with i.i.d. service times that are independent of a stationary process of inter-arrival times. We show that the distribution of the waiting time converges to a stationary law as time tends to infinity provided that inter-arrival times satisfy a Gärtner-Ellis type condition. A convergence rate is given and a law of large numbers established. These results provide tools for the statistical analysis of such systems, transcending the standard case with independent inter-arrival times.     

Maximum likelihood estimation for single server queues from waiting time data

Maximum likelihood estimators for the parameters of a GI/G/1 queue are derived based on the information on waiting times {W _t },t=1,...,n, ofn successive customers. The consistency and asymptotic normality of the estimators are established. A simulation study of the M/M/1 and M/E _k /1 queues is presented.     

The stationary workload of the <Emphasis Type="Italic">G</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1 queue with impatient customers

We consider a G/M/1 queue in which the patience time of the customers is constant. The stationary distribution of the workload of the server, or the virtual waiting time, is derived by the level crossing argument. To this end, we obtain the expected downcrossings of a level in the workload process during a busy cycle and then the expected length of a busy cycle. For both the expectations, we use the dual property between the M/G/1 and G/M/1 queue.     

Second moment relationships for waiting times in queueing systems with poisson input

For theM/G/1 queue there are well-known and simple relationships among the second moments of waiting time under the first-in-first-out, last-in-first-out, and random-order-of-service disciplines. This paper points out that these relationships hold in considerably more general settings. In particular, it is shown that these relationships hold forM/G/1 queues with exceptional first service,M/G/1 queues with server vacations, andM/G/1 queues with static priorities.     

Heavy-traffic limits for nearly deterministic queues: stationary distributions

We establish heavy-traffic limits for stationary waiting times and other performance measures in G _n /G _n /1 queues, where G _n indicates that an original point process is modified by cyclic thinning of order n, i.e., the thinned process contains every nth point from the original point process. The classical example is the Erlang E _n /E _n /1 queue, where cyclic thinning of order n is applied to both the interarrival times and the service times, starting from a “base” M/M/1 model. The models G _n /D/1 and D/G _n /1 are special cases of G _n /G _n /1. Since waiting times before starting service in the G/D/n queue are equivalent to waiting times in an associated G _n /D/1 model, where the interarrival times are the sum of n consecutive interarrival times in the original model, the G/D/n model is a special case as well. As n→∞, the G _n /G _n /1 models approach the deterministic D/D/1 model. We obtain revealing limits by letting ρ _n ↑1 as n→∞, where ρ _n is the traffic intensity in model n.     

A unified algorithm for computing the stationary queue length distributions inM(k)/G/1/N and GI/M(k)/1/N queues

An iterative algorithm is developed for computing numerically the stationary queue length distributions in M/G/1/N queues with arbitrary state-dependent arrivals, or simply M(k)/G/1/N queues. The only input requirement is the Laplace-Stieltjes transform of the service time distribution.In addition, the algorithm can also be used to obtain the stationary queue length distributions in GI/M/1/N queues with state-dependent services, orGI/M(k)/1/N, after establishing a relationship between the stationary queue length distributions inGI/M(k)/1/N and M(k)/G/1/N+1 queues.Finally, we elaborate on some of the well studied special cases, such asM/G/1/N queues,M/G/1/N queues with distinct arrival rates (which includes the machine interference problems), andGI/M/C/N queues. The discussions lead to a simplified algorithm for each of the three cases.     

Priority queues with semi-exhaustive service

This paper studies a new type of multi-class priority queues with semi-exhaustive service and server vacations, which operates as follows: A single server continues serving messages in queuen until the number of messages decreases toone less than that found upon the server's last arrival at queuen, where 1nN. In succession, messages of the highest class present in the system, if any, will be served according to this semi-exhaustive service. Applying the delay cycle analysis and introducing a super-message composed of messages served in a busy period, we derive explicitly the Laplace-Stieltjes transforms (LSTs) and the first two moments of the message waiting time distributions for each class in the M/G/1-type priority queues with multiple and single vacations. We also derive a conversion relationship between the LSTs for waiting times in the multiple and single vacation models.     

Asymptotic expansions for waiting time probabilities in an M/G/1 queue with long-tailed service time

We consider anM/G/1 queue with FCFS queue discipline. We present asymptotic expansions for tail probabilities of the stationary waiting time when the service time distribution is longtailed and we discuss an extension of our methods to theM ^[x]/G/1 queue with batch arrivals.