Approximations for the conditional waiting times in the GI/G/c queue

This note presents a two-moment approximation for the conditional average waiting time in the standard multi-server queue and an approximation for the tail probabilities of the conditional waiting time distribution in the standard single-server queue. These approximations have been tested by extensive numerical experiments.     

AnM/M/c queue with impatient customers

This paper considers theM/M/c queue in which a customer leaves when its service has not begun within a fixed interval after its arrival. The loss probability can be expressed in a simple formula involving the waiting time probabilities in the standardM/M/c queue. The purpose of this paper is to give a probabilistic derivation of this formula and to outline a possible use of this general formula in theM/M/c retrial queue with impatient customers. This research was supported by the INTAS 96-0828 research project and was presented at the First International Workshop on Retrial Queues, Universidad Complutense de Madrid, Madrid, September 22–24, 1998.     

The M/G/c queue in light traffic

Under light traffic, we investigate the quality of a well‐known approximation for first‐moment performance measures for an M/G/c queue, and, in particular, conditions under which the approximation is either an upper or a lower bound. The approach is to combine known relationships between quantities such as average delay and time‐average work in system with direct sample‐path comparisons of system operation under two modes of operation: conventional FIFO and a version of preemptive LIFO. We then use light traffic limit theorems to show an inequality between time‐average work of the M/G/c queue and that of the approximation. In the process, we obtain new and improved approximations. This revised version was published online in June 2006 with corrections to the Cover Date.     

On stationary queue length distributions for G/M/s/r queues

Consider aG/M/s/r queue, where the sequence{A _n } _n=– of nonnegative interarrival times is stationary and ergodic, and the service timesS _n are i.i.d. exponentially distributed. (SinceA _n =0 is possible for somen, batch arrivals are included.) In caser < , a uniquely determined stationary process of the number of customers in the system is constructed. This extends corresponding results by Loynes [12] and Brandt [4] forr= (with=ES₀/EA₀<s) and Franken et al. [9], Borovkov [2] forr=0 ors=. Furthermore, we give a proof of the relation min(i, s)¯p(i)=p(i–1), 1ir + s, between the time- and arrival-stationary probabilities¯p(i) andp(i), respectively. This extends earlier results of Franken [7], Franken et al. [9].     

The PH/PH/1 queue at epochs of queue size change

The PH/PH/1 queue is considered at embedded epochs which form the union of arrival and departure instants. This provides us with a new, compact representation as a quasi-birth-and-death process, where the order of the blocks is the sum of the number of phases in the arrival and service time distributions. It is quite easy to recover, from this new embedded process, the usual distributions at epochs of arrival, or epochs of departure, or at arbitrary instants. The quasi-birth-and-death structure allows for efficient algorithmic procedures. This revised version was published online in June 2006 with corrections to the Cover Date.     

On inference concerning time-dependent queue performance: The M/G/1 example

This paper proposes easily-computed approximations to the finite-time expected waiting time for anM/G/1 system starting from an empty state. Both unsaturated (ρ<1) and saturated (ρ>1) conditions are considered. Numerical evidence is presented to indicate that the quality of the approximations is usefully good, especially when ease of computation is an issue. Further, the methodology is adapted to assess expected waiting time when inference must be made from a random sample of service times, and the decision is made to do so nonparametrically, i.e., without fitting a specific function. The results appear reasonable and potentially useful, and are not burdensome to obtain. The methodology investigated can also be applied to the variety of queueing models that are close siblings ofM/G/1: priority and breakdowns and “vacations” being examples. Of course other approximating and inferential options remain to be investigated.     

A Markov-modulated M/G/1 queue I: Stationary distribution

We consider an M/G/1 queueing system in which the arrival rate and service time density are functions of a two-state stochastic process. We describe the system by the total unfinished work present and allow the arrival and service rate processes to depend on the current value of the unfinished work. We employ singular perturbation methods to compute asymptotic approximations to the stationary distribution of unfinished work and in particular, compute the stationary probability of an empty queue.This research was supported in part by NSF Grants DMS-84-06110, DMS-85-01535 and DMS-86-20267, and grants from the U.S. Israel Binational Science Foundation and the Israel Academy of Sciences.     

A markov-modulated M/M/1 queue with group arrivals

We study anM/M/1 group arrival queue in which the arrival rate, service time distributions and the size of each group arrival depend on the state of an underlying finite-state Markov chain. Using Laplace transforms and matrix analysis, we derive the results for the queue length process, its limit distribution and the departure process. In some special cases, explicit results are obtained which are analogous to known classic results.     

Representing workloads in GI/G/1 queues through the preemptive-resume LIFO queue discipline

We give in this paper a detailed sample-average analysis of GI/G/1 queues with the preemptive-resume LIFO (last-in-first-out) queue discipline: we study the long-run state behavior of the system by averaging over arrival epochs, departure epochs, as well as time, and obtain relations that express the resulting averages in terms of basic characteristics within busy cycles. These relations, together with the fact that the preemptive-resume LIFO queue discipline is work-conserving, imply new representations for both actual and virtual delays in standard GI/G/1 queues with the FIFO (first-in-first-out) queue discipline. The arguments by which our results are obtained unveil the underlying structural explanations for many classical and somewhat mysterious results relating to queue lengths and/or delays in standard GI/G/1 queues, including the well-known Bene's formula for the delay distribution in M/G/l. We also discuss how to extend our results to settings more general than GI/G/1.     

Stationary distribution of queue length in G / M / 1 queue with two-stage service policy

We consider a G / M / 1 queue with two-stage service policy. The server starts to serve with rate of μ₁ customers per unit time until the number of customers in the system reaches λ. At this moment, the service rate is changed to that of μ₂ customers per unit time and this rate continues until the system is empty. We obtain the stationary distribution of the number of customers in the system.     

Delay moments for FIFO GI/GI/s queues

For stable FIFO GI/GI/s queues, s ≥ 2, we show that finite (k+1)st moment of service time, S, is not in general necessary for finite kth moment of steady-state customer delay, D, thus weakening some classical conditions of Kiefer and Wolfowitz (1956). Further, we demonstrate that the conditions required for E[D ^k]<∞ are closely related to the magnitude of traffic intensity ρ (defined to be the ratio of the expected service time to the expected interarrival time). In particular, if ρ is less than the integer part of s/2, then E[D] < ∞ if E[S^3/2]<∞, and E[D^k]<∞ if E[S^k]<∞, ^k≥ 2. On the other hand, if s-1 < ρ < s, then E[D^k]<∞ if and only if E[S^k+1]<∞, k ≥ 1. Our method of proof involves three key elements: a novel recursion for delay which reduces the problem to that of a reflected random walk with dependent increments, a new theorem for proving the existence of finite moments of the steady-state distribution of reflected random walks with stationary increments, and use of the classic Kiefer and Wolfowitz conditions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Simple analysis of a fluid queue driven by an M/M/1 queue

In this note we consider the fluid queue driven by anM/M/1 queue as analysed by Virtamo and Norros [Queueing Systems 16 (1994) 373–386]. We show that the stationary buffer content in this model can be easily analysed by looking at embedded time points. This approach gives the stationary buffer content distribution in terms of the modified Bessel function of the first kind of order one. By using a suitable integral representation for this Bessel function we show that our results coincide with the ones of Virtamo and Norros.     

The serial correlation coefficients for waiting times in the stationary GI/M/m queue

Serial correlation coefficients are useful measures of the interdependence of successive waiting times. Potential applications include the development of linear predictors and determining simulation run lengths. This paper presents the algorithm for calculating such correlations in the multiserver exponential service queue, and relates it to known results for single server queues.     

A Markov-modulated M/G/1 queue II: Busy period and time for buffer overflow

We consider an M/G/1 queue where the arrival and service processes are modulated by a two state Markov chain. We assume that the arrival rate, service time density and the rates at which the Markov chain switches its state, are functions of the total unfinished work (buffer content) in the queue. We compute asymptotic approximations to performance measures such as the mean residual busy period, mean length of a busy period, and the mean time to reach capacity.This research was supported in part by NSF Grants DMS-84-06110, DMS-85-01535 and DMS-86-20267, and grants from the U.S. Israel Binational Science Foundation and the Israel Academy of Sciences.     

Asymptotic analysis of the M/G/1 queue with a time‐dependent arrival rate

We consider the M/G/1 queue with an arrival rate λ that depends weakly upon time, as λ = λ(εt) where ε is a small parameter. In the asymptotic limit ε → 0, we construct approximations to the probability p _n(t)that η customers are present at time t. We show that the asymptotics are different for several ranges of the (slow) time scale Τ= εt. We employ singular perturbation techniques and relate the various time scales by asymptotic matching. This revised version was published online in June 2006 with corrections to the Cover Date.     

Age-based Markovian approximation of the G/M/1 queue

We extend the approach of Koole et al. (2012) [15] and Legros et al. (2018) [20] for the G/M/1 queue. The idea is to provide a Markovian approximation where a state represents the oldest customer's wait. This modeling is made possible by creating states with negative wait, representing an estimate of the time at which a new customer would arrive when the system is empty. We apply this method for performance evaluation and routing optimization. Finally, we further extend the model to the G/M/1+G queue.     

Asymptotics for M/G/1 low-priority waiting-time tail probabilities

We consider the classical M/G/1 queue with two priority classes and the nonpreemptive and preemptive-resume disciplines. We show that the low-priority steady-state waiting-time can be expressed as a geometric random sum of i.i.d. random variables, just like the M/G/1 FIFO waiting-time distribution. We exploit this structures to determine the asymptotic behavior of the tail probabilities. Unlike the FIFO case, there is routinely a region of the parameters such that the tail probabilities have non-exponential asymptotics. This phenomenon even occurs when both service-time distributions are exponential. When non-exponential asymptotics holds, the asymptotic form tends to be determined by the non-exponential asymptotics for the high-priority busy-period distribution. We obtain asymptotic expansions for the low-priority waiting-time distribution by obtaining an asymptotic expansion for the busy-period transform from Kendall's functional equation. We identify the boundary between the exponential and non-exponential asymptotic regions. For the special cases of an exponential high-priority service-time distribution and of common general service-time distributions, we obtain convenient explicit forms for the low-priority waiting-time transform. We also establish asymptotic results for cases with long-tail service-time distributions. As with FIFO, the exponential asymptotics tend to provide excellent approximations, while the non-exponential asymptotics do not, but the asymptotic relations indicate the general form. In all cases, exact results can be obtained by numerically inverting the waiting-time transform. This revised version was published online in June 2006 with corrections to the Cover Date.     

Performance analysis of discrete-time queue GI/G/1 with negative arrivals

In this paper, we consider a discrete-time GI/G/1 queueing model with negative arrivals. By deriving the probability generating function of actual service time of ordinary customers, we reduced the analysis to an equivalent discrete-time GI/G/1 queueing model without negative arrival, and obtained the probability generating function of buffer contents and random customer delay.     

Asymptotic behavior of the loss probability for an M/G/1/N queue with vacations

In this paper, asymptotic properties of the loss probability are considered for an M/G/1/N queue with server vacations and exhaustive service discipline, denoted by an M/G/1/N-(V, E)-queue. Exact asymptotic rates of the loss probability are obtained for the cases in which the traffic intensity is smaller than, equal to and greater than one, respectively. When the vacation time is zero, the model considered degenerates to the standard M/G/1/N queue. For this standard queueing model, our analysis provides new or extended asymptotic results for the loss probability. In terms of the duality relationship between the M/G/1/N and GI/M/1/N queues, we also provide asymptotic properties for the standard GI/M/1/N model.     

Some results on a generalized M/G/1 feedback queue with negative customers

This paper deals with a generalized M/G/1 feedback queue in which customers are either “positive" or “negative". We assume that the service time distribution of a positive customer who initiates a busy period is G _e (x) and all subsequent positive customers in the same busy period have service time drawn independently from the distribution G _b (x). The server is idle until a random number N of positive customers accumulate in the queue. Following the arrival of the N-th positive customer, the server serves exhaustively the positive customers in the queue and then a new idle period commences. This queueing system is a generalization of the conventional N-policy queue with N a constant number. Explicit expressions for the probability generating function and mean of the system size of positive customers are obtained under steady-state condition. Various vacation models are discussed as special cases. The effects of various parameters on the mean system size and the probability that the system is empty are also analysed numerically. AMS Subject Classification: Primary: 60 K 25 · Secondary: 60 K 20, 90 B 22