Stability analysis of GI/GI/c/K retrial queue with constant retrial rate

We consider a finite buffer capacity GI/GI/c/K-type retrial queueing system with constant retrial rate. The system consists of a primary queue and an orbit queue. The primary queue has \(c\) identical servers and can accommodate up to \(K\) jobs (including \(c\) jobs under service). If a newly arriving job finds the primary queue to be full, it joins the orbit queue. The original primary jobs arrive to the system according to a renewal process. The jobs have i.i.d. service times. The head of line job in the orbit queue retries to enter the primary queue after an exponentially distributed time independent of the length of the orbit queue. Telephone exchange systems, medium access protocols, optical networks with near-zero buffering and TCP short-file transfers are some telecommunication applications of the proposed queueing system. The model is also applicable in logistics. We establish sufficient stability conditions for this system. In addition to the known cases, the proposed model covers a number of new particular cases with the closed-form stability conditions. The stability conditions that we obtained have clear probabilistic interpretation.     

Validity of heavy-traffic steady-state approximations in many-server queues with abandonment

We consider \(GI/Ph/n+M\) parallel-server systems with a renewal arrival process, a phase-type service time distribution, \(n\) homogenous servers, and an exponential patience time distribution with positive rate. We show that in the Halfin–Whitt regime, the sequence of stationary distributions corresponding to the normalized state processes is tight. As a consequence, we establish an interchange of heavy-traffic and steady-state limits for \(GI/Ph/n+M\) queues.     

Generalized sub-Gaussian fractional Brownian motion queueing model

It is well known that often the one-dimensional distribution of a queue content is not Gaussian but its tails behave like a Gaussian. We propose to consider a general class of processes, namely the class of $\varphi $ -sub-Gaussian random processes, which is more general than the Gaussian one and includes non-Gaussian processes. The class of sub-Gaussian random processes contains Gaussian processes also and therefore is of special interest. In this paper we provide an estimate for the queue content distribution of a fluid queue fed by $N$ independent strictly $\varphi $ -sub-Gaussian generalized fractional Brownian motion input processes. We obtain an upper estimate of buffer overflow probability in a finite buffer system defined on any finite time interval $[a,b]$ or infinite interval $[0,\infty )$ . The derived estimate captures more accurately the performance of the queueing system for a wider-range of input processes.     

Approximating the Mean Waiting Time in the <Emphasis Type="Italic">GI/G/s</Emphasis> Queue

We provide two distribution-dependent approximations for the mean waiting time in a GI/G/s queue. Both approximations are weighted combinations of the exact mean waiting times for the GI/M/s and M/D/s queues each of which has the same mean service time and traffic intensity as in the approximating GI/G/s queue. The weights in the approximations are expressed by the service-time c.d.f. and the first two moments of interarrival and service times. To examine the performance of our approximations, they are numerically compared with exact solutions and previous two-moment approximations for various cases. Extensive numerical comparisons indicate that the relative percentage errors of the approximations are of the order of 5% in moderate traffic and 1% in heavy traffic, except for extreme cases.     

Analysis of Open Discrete Time Queueing Networks: A Refined Decomposition Approach

This paper deals with approximate analysis methods for open queueing networks. External and internal flows from and to the nodes are characterized by renewal processes with discrete time distributions of their interarrival times. Stationary distributions of the waiting time, the queue size and the interdeparture times are obtained using efficient discrete time algorithms for single server (GI/G/1) and multi-server (GI/D/c) nodes with deterministic service. The network analysis is extended to semi-Markovian representations of each flow among the nodes, which include parameters of the autocorrelation function.     

Heavy traffic limit for a tandem queue with identical service times

We consider a two-node tandem queueing network in which the upstream queue is M/G/1 and each job reuses its upstream service requirement when moving to the downstream queue. Both servers employ the first-in-first-out policy. We investigate the amount of work in the second queue at certain embedded arrival time points, namely when the upstream queue has just emptied. We focus on the case of infinite-variance service times and obtain a heavy traffic process limit for the embedded Markov chain.     

Gaussian skewness approximation for dynamic rate multi-server queues with abandonment

The multi-server queue with non-homogeneous Poisson arrivals and customer abandonment is a fundamental dynamic rate queueing model for large scale service systems such as call centers and hospitals. Scaling the arrival rates and number of servers arises naturally when a manager updates a staffing schedule in response to a forecast of increased customer demand. Mathematically, this type of scaling ultimately gives us the fluid and diffusion limits as found in Mandelbaum et al., Queueing Syst 30:149–201 (1998) for Markovian service networks. The asymptotics used here reduce to the Halfin and Whitt, Oper Res 29:567–588 (1981) scaling for multi-server queues. The diffusion limit suggests a Gaussian approximation to the stochastic behavior of this queueing process. The mean and variance are easily computed from a two-dimensional dynamical system for the fluid and diffusion limiting processes. Recent work by Ko and Gautam, INFORMS J Comput, to appear (2012) found that a modified version of these differential equations yield better Gaussian estimates of the original queueing system distribution. In this paper, we introduce a new three-dimensional dynamical system that is based on estimating the mean, variance, and third cumulant moment. This improves on the previous approaches by fitting the distribution from a quadratic function of a Gaussian random variable.     

Steady-state asymptotics for tandem,split-match and other feedforward queues with heavy tailed service

Consider a stable FIFO GI/GI/1 → /GI/1 tandem queue in which the equilibrium distribution of service time at the second node S(2) is subexponential. It is shown that when the service time at the first node has a lighter tail, the tail of steady-state delay at the second node, D(2), has the same asymptotics as if it were a GI/GI/1 queue: $$x \to \infty $$ where S _e(2) has equilibrium (integrated tail) density P(S(2) > $x$ )/E[S(2)], and ρ₂ = λE[S(2)] (λ is the arrival rate of customers). The same result holds for tandem queues with more than two stations. For split-match (fork-join) queues with subexponential service times, we derive the asymptotics for both the sojourn time and the queue length. Finally, more generally, we consider feedforward generalized Jackson networks and obtain similar results.     

The Dirichlet problem for Einstein metrics on cohomogeneity one manifolds

Let \(G{/}H\) be a compact homogeneous space, and let \(\hat{g}_0\) and \(\hat{g}_1\) be G-invariant Riemannian metrics on \(G/H\). We consider the problem of finding a G-invariant Einstein metric g on the manifold \(G/H\times [0,1]\) subject to the constraint that g restricted to \(G{/}H\times \{0\}\) and \(G/H\times \{1\}\) coincides with \(\hat{g}_0\) and \(\hat{g}_1\), respectively. By assuming that the isotropy representation of \(G/H\) consists of pairwise inequivalent irreducible summands, we show that we can always find such an Einstein metric.     

Analyzing the Steady-State Queue <Emphasis Type="Italic">GI</Emphasis><Superscript><Emphasis Type="Italic">X</Emphasis></Superscript><Emphasis Type="Italic">/G/</Emphasis>1

It is proved in this note that the delay in the queue GI ^X /G/1 can be expressed as the sum of two independent components, such that known results of the queue GI/G/1 (e.g. approximations) can be readily applied. Based on this result, closed-form expressions are also derived for other performance measures of interest.     

Multiclass multiserver queueing system in the Halfin–Whitt heavy traffic regime: asymptotics of the stationary distribution

We consider a heterogeneous queueing system consisting of one large pool of O(r) identical servers, where r→∞ is the scaling parameter. The arriving customers belong to one of several classes which determines the service times in the distributional sense. The system is heavily loaded in the Halfin–Whitt sense, namely the nominal utilization is $1-a/\sqrt{r}$ where a>0 is the spare capacity parameter. Our goal is to obtain bounds on the steady state performance metrics such as the number of customers waiting in the queue Q ^r (∞). While there is a rich literature on deriving process level (transient) scaling limits for such systems, the results for steady state are primarily limited to the single class case. This paper is the first one to address the case of heterogeneity in the steady state regime. Moreover, our results hold for any service policy which does not admit server idling when there are customers waiting in the queue. We assume that the interarrival and service times have exponential distribution, and that customers of each class may abandon while waiting in the queue at a certain rate (which may be zero). We obtain upper bounds of the form $O(\sqrt{r})$ on both Q ^r (∞) and the number of idle servers. The bounds are uniform w.r.t. parameter r and the service policy. In particular, we show that $\limsup_{r} \mathbb {E}\exp(\theta r^{-{1\over2}}Q^{r}(\infty))<\infty$ . Therefore, the sequence $r^{-{1\over2}}Q^{r}(\infty)$ is tight and has a uniform exponential tail bound. We further consider the system with strictly positive abandonment rates, and show that in this case every weak limit $\hat{Q}(\infty)$ of $r^{-{1\over2}}Q^{r}(\infty)$ has a sub-Gaussian tail. Namely, $\mathbb {E}[\exp(\theta(\hat{Q}(\infty ))^{2})]<\infty$ , for some θ>0.     

Dynamic rate Erlang-A queues

The multi-server queue with non-homogeneous Poisson arrivals and customer abandonment is a fundamental dynamic rate queueing model for large-scale service systems such as call centers and hospitals. Scaling the arrival rates and number of servers arises naturally when a manager updates a staffing schedule in response to a forecast of increased customer demand. Mathematically, this type of scaling ultimately gives us the fluid and diffusion limits as found in Mandelbaum et al. (Queueing Syst 30(1):149–201, 1998) for Markovian service networks. These asymptotics were inspired by the Halfin and Whitt (Oper Res 29(3):567–588, 1981) scaling for multi-server queues. In this paper, we provide a review and an in-depth analysis of the Erlang-A queueing model. We prove new results about cumulant moments of the Erlang-A queue, the transient behavior of the Erlang-A limit cycle, new fluid limits for the delay time of a virtual customer, and optimal static staffing policies for healthcare systems. We combine tools from queueing theory, ordinary differential equations, complex analysis, cumulant moments, orthogonal polynomials, and dynamic optimization to obtain new insights about this fundamental queueing model.     

Large deviation analysis of the single server queue

We establish the large deviation principle (LDP) for the virtual waiting time and queue length processes in the GI/GI/1 queue. The rate functions are found explicitly. As an application, we obtain the logarithmic asymptotics of the probabilities that the virtual waiting time and queue length exceed high levels at large times. Additional new results deal with the LDP for renewal processes and with the derivation of unconditional LDPs for conditional ones. Our approach applies in large deviations ideas and methods of weak convergence theory.This work was supported in part by AT&T Bell Labs.     

Equilibrium properties of the M/G/1 queue

Summary Various aspects of the equilibrium M/G/1 queue at large values are studied subject to a condition on the service time distribution closely related to the tail to decrease exponentially fast. A simple case considered is the supplementary variables (age and residual life of the current service period), the distribution of which conditioned upon queue length n is shown to have a limit as n. Similar results hold when conditioning upon large virtual waiting times. More generally, a number of results are given which describe the input and output streams prior to large values e.g. in the sense of weak convergence of the associated point processes and incremental processes. Typically, the behaviour is shown to be that of a different transient M/G/1 queueing model with a certain stochastically larger service time distribution and a larger arrival intensity. The basis of the asymptotic results is a geometrical approximation for the tail of the equilibrium queue length distribution, pointed out here for the GI/G/1 queue as well.     

A single-server queue with batch arrivals and semi-Markov services

We investigate the transient and stationary queue length distributions of a class of service systems with correlated service times. The classical \(M^X/G/1\) queue with semi-Markov service times is the most prominent example in this class and serves as a vehicle to display our results. The sequence of service times is governed by a modulating process J(t). The state of \(J(\cdot )\) at a service initiation time determines the joint distribution of the subsequent service duration and the state of \(J(\cdot )\) at the next service initiation. Several earlier works have imposed technical conditions, on the zeros of a matrix determinant arising in the analysis, that are required in the computation of the stationary queue length probabilities. The imposed conditions in several of these articles are difficult or impossible to verify. Without such assumptions, we determine both the transient and the steady-state joint distribution of the number of customers immediately after a departure and the state of the process J(t) at the start of the next service. We numerically investigate how the mean queue length is affected by variability in the number of customers that arrive during a single service time. Our main observations here are that increasing variability may reduce the mean queue length, and that the Markovian dependence of service times can lead to large queue lengths, even if the system is not in heavy traffic.     

<Emphasis Type="Italic">M</Emphasis><Superscript><Emphasis Type="Italic">X</Emphasis></Superscript>/<Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">c</Emphasis> Queue with catastrophes and state-dependent control at idle time

We consider an M ^X /M/c queue with catastrophes and state-dependent control at idle time. Properties of the queues which terminate when the servers become idle are first studied. Recurrence, equilibrium distribution, and equilibrium queue-size structure are studied for the case of resurrection and no catastrophes. All of these properties and the first effective catastrophe occurrence time are then investigated for the case of resurrection and catastrophes. In particular, we obtain the Laplace transform of the transition probability for the absorbing M ^X /M/c queue.     

Further delay moment results for FIFO multiserver queues

Using a new family of service disciplines, we provide weaker sufficient conditions for finite stationary delay moments in FIFO multiserver queues. This extends the work in Sigman and Scheller-Wolf [6] to GI/GI/s queues with = E[S]/E[T] s-1 are the familiar Kiefer and Wolfowitz conditions actually known to be necessary. For the case when < 1, we provide sufficient conditions for finite mean stationary delay, expressed as a function of the number of servers in the system. The limit of these conditions as s is the requirement that E[S] < , which is the condition for finite mean stationary delay in a FIFO GI/GI/ queue. Both of these results highlight the interplay between traffic intensity and service time distribution in determining the behavior of delay moments in multiserver queues.     

Refining Cosmetatos' Approximation for the Mean Waiting Time in the M/D/s Queue

This paper deals with refining Cosmetatos's approximation for the mean waiting time in an M/D/s queue. Although his approximation performs quite well in heavy traffic, it overestimates the true value when the number of servers is large or the traffic is light. We first focus on a normalized quantity that is a ratio of the mean waiting times for the M/D/s and M/M/s queues. Using some asymptotic properties of the quantity, we modify Cosmetatos's approximation to obtain better accuracy both for large s and in light traffic. To see the quality of our approximation, we compare it with the exact value and some previous approximations. Extensive numerical tests indicate that the relative percentage error is less than 1% for almost all cases with s ≤ 20 and at most 5% for other cases.     

Diffusion approximations for open Jackson networks with reneging

We consider generalized Jackson networks with reneging in which the customer patience times follow a general distribution that unifies the patience time without scaling adopted by Ward and Glynn (Queueing Syst 50:371–400, 2005) and the patience time with hazard rate scaling and unbounded support adopted by Reed and Ward (Math Oper Res 33:606–644, 2008). The diffusion approximations for both the queue length process and the abandonment-count process are established under the conventional heavy traffic limit regime. In light of the recent work by Dai and He (Math Oper Res 35:347–362, 2010), the diffusion approximations are obtained by the following four steps: first, establishing the stochastic boundedness for the queue length process and the virtual waiting time process; second, obtaining the $C$ -tightness and fluid limits for the queue length process and the abandonment-count process; then third, building an asymptotic relationship between the abandonment-count process and the queue length process in terms of the customer patience time. Finally, the fourth step is to get the diffusion approximations by invoking the continuous mapping theorem.     

Analyzing <Emphasis Type="Italic">M/M/</Emphasis>1 Queues with Perturbations in the Arrival Process

This paper investigates when the M/M/1 model can be used to predict accurately the operating characteristics of queues with arrival processes that are slightly different from the Poisson process assumed in the model. The arrival processes considered here are perturbed Poisson processes. The perturbations are deviations from the exponential distribution of the inter-arrival times or from the assumption of independence between successive inter-arrival times. An estimate is derived for the difference between the expected numbers in perturbed and M/M/1 queueing systems with the same traffic intensity. The results, for example, indicate that the M/M/1 model can predict the performance of the queue when the arrival process is perturbed by inserting a few short inter-arrival times, an occasional batch arrival or small dependencies between successive inter-arrival times. In contrast, the M/M/1 is not a good model when the arrival process is perturbed by inserting a few long inter-arrival times.