Regularly varying tail of the waiting time distribution in M/G/1 retrial queue

We consider an M/G/1 retrial queue where the service time distribution has a regularly varying tail with index −β, β>1. The waiting time distribution is shown to have a regularly varying tail with index 1−β, and the pre-factor is determined explicitly. The result is obtained by comparing the waiting time in the M/G/1 retrial queue with the waiting time in the ordinary M/G/1 queue with random order service policy.     

批到达M/G/1重试排队的队长的尾渐近

用随机分解法研究成批到达服务时间为次指数分布的重试排队中队长的尾行为,得到了该系统与其相应的标准排队系统队长尾分布的关系;对次指数尾,结果也能用于正则变化尾,进而得到正则变化尾渐近．     

Sojourn time asymptotics in the M/G/1 processor sharing queue

We show for the M/G/1 processor sharing queue that the service time distribution is regularly varying of index -ν, ν non-integer, iff the sojourn time distribution is regularly varying of index -ν. This result is derived from a new expression for the Laplace–Stieltjes transform of the sojourn time distribution. That expression also leads to other new properties for the sojourn time distribution. We show how the moments of the sojourn time can be calculated recursively and prove that the kth moment of the sojourn time is finite iff the kth moment of the service time is finite. In addition, we give a short proof of a heavy traffic theorem for the sojourn time distribution, prove a heavy traffic theorem for the moments of the sojourn time, and study the properties of the heavy traffic limiting sojourn time distribution when the service time distribution is regularly varying. Explicit formulas and multiterm expansions are provided for the case that the service time has a Pareto distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Tail asymptotics for the queue length in an M/G/1 retrial queue

In this paper, we study the tail behavior of the stationary queue length of an M/G/1 retrial queue. We show that the subexponential tail of the stationary queue length of an M/G/1 retrial queue is determined by that of the corresponding M/G/1 queue, and hence the stationary queue length in an M/G/1 retrial queue is subexponential if the stationary queue length in the corresponding M/G/1 queue is subexponential. Our results for subexponential tails also apply to regularly varying tails, and we provide the regularly varying tail asymptotics for the stationary queue length of the M/G/1 retrial queue. AMS subject classifications: 60J25, 60K25     

Second-Order Tail Behavior of the Busy Period Distribution of Certain GI/G/1 Queues

We consider the stable GI/G/1 queue in which the service time distribution has a dominated-varying tail. Under simple assumptions, we obtain the first- and second-order tail behavior of the busy period distribution in this queue.     

Tail asymptotics for the queue size distribution in the MAP/G/1 retrial queue

We consider a MAP/G/1 retrial queue where the service time distribution has a finite exponential moment. We derive matrix differential equations for the vector probability generating functions of the stationary queue size distributions. Using these equations, Perron–Frobenius theory, and the Karamata Tauberian theorem, we obtain the tail asymptotics of the queue size distribution. The main result on light-tailed asymptotics is an extension of the result in Kim et al. (J. Appl. Probab. 44:1111–1118, 2007) on the M/G/1 retrial queue.     

Heavy-traffic analysis for the GI/G/1 queue with heavy-tailed distributions

We consider a GI/G/1 queue in which the service time distribution and/or the interarrival time distribution has a heavy tail, i.e., a tail behaviour like t ^−ν with 1 < ν ⩽ 2 , so that the mean is finite but the variance is infinite. We prove a heavy-traffic limit theorem for the distribution of the stationary actual waiting time W. If the tail of the service time distribution is heavier than that of the interarrival time distribution, and the traffic load a → 1, then W, multiplied by an appropriate ‘coefficient of contraction’ that is a function of a, converges in distribution to the Kovalenko distribution. If the tail of the interarrival time distribution is heavier than that of the service time distribution, and the traffic load a → 1, then W, multiplied by another appropriate ‘coefficient of contraction’ that is a function of a, converges in distribution to the negative exponential distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Queues with Equally Heavy Sojourn Time and Service Requirement Distributions

For the G/G/1 queue with First-Come First-Served, it is well known that the tail of the sojourn time distribution is heavier than the tail of the service requirement distribution when the latter has a regularly varying tail. In contrast, for the M/G/1 queue with Processor Sharing, Zwart and Boxma [26] showed that under the same assumptions on the service requirement distribution, the two tails are equally heavy. By means of a probabilistic analysis we provide a new insightful proof of this result, allowing for the slightly weaker assumption of service requirement distributions with a tail of intermediate regular variation. The new approach allows us to also establish the tail equivalence for two other service disciplines: Foreground–Background Processor Sharing and Shortest Remaining Processing Time. The method can also be applied to more complicated models, for which no explicit formulas exist for (transforms of) the sojourn time distribution. One such model is the M/G/1 Processor Sharing queue with service that is subject to random interruptions. The latter model is of particular interest for the performance analysis of communication networks.     

Tail asymptotics of the waiting time and the busy period for the {{\varvec{M/G/1/K}}} queues with subexponential service times

We study the asymptotic behavior of the tail probabilities of the waiting time and the busy period for the $M/G/1/K$ queues with subexponential service times under three different service disciplines: FCFS, LCFS, and ROS. Under the FCFS discipline, the result on the waiting time is proved for the more general $GI/G/1/K$ queue with subexponential service times and lighter interarrival times. Using the well-known Laplace–Stieltjes transform (LST) expressions for the probability distribution of the busy period of the $M/G/1/K$ queue, we decompose the busy period into a sum of a random number of independent random variables. The result is used to obtain the tail asymptotics for the waiting time distributions under the LCFS and ROS disciplines.     

Sojourn time tails in the single server queue with heavy-tailed service times

We consider the GI/GI/1 queue with regularly varying service requirement distribution of index −α. It is well known that, in the M/G/1 FCFS queue, the sojourn time distribution is also regularly varying, of index 1−α, whereas in the case of LCFS or Processor Sharing, the sojourn time distribution is regularly varying of index −α. That raises the question whether there exist service disciplines that give rise to a regularly varying sojourn time distribution with any index −γ∈[−α,1−α]. In this paper that question is answered affirmatively.     

Asymptotic expansions for the conditional sojourn time distribution in the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1-PS queue

We consider the M/M/1 queue with processor sharing. We study the conditional sojourn time distribution, conditioned on the customer’s service requirement, in various asymptotic limits. These include large time and/or large service request, and heavy traffic, where the arrival rate is only slightly less than the service rate. The asymptotic formulas relate to, and extend, some results of Morrison (SIAM J. Appl. Math. 45:152–167, [1985]) and Flatto (Ann. Appl. Probab. 7:382–409, [1997]). This work was partly supported by NSF grant DMS 05-03745.     

Asymptotic behaviour of the tandem queueing system with identical service times at both queues

Consider a tandem queue consisting of two single-server queues in series, with a Poisson arrival process at the first queue and arbitrarily distributed service times, which for any customer are identical in both queues. For this tandem queue, we relate the tail behaviour of the sojourn time distribution and the workload distribution at the second queue to that of the (residual) service time distribution. As a by-result, we prove that both the sojourn time distribution and the workload distribution at the second queue are regularly varying at infinity of index 1−ν, if the service time distribution is regularly varying at infinity of index −ν (ν>1). Furthermore, in the latter case we derive a heavy-traffic limit theorem for the sojourn time S ⁽²⁾ at the second queue when the traffic load ρ↑ 1. It states that, for a particular contraction factor Δ (ρ), the contracted sojourn time Δ (ρ) S ⁽²⁾ converges in distribution to the limit distribution H(·) as ρ↑ 1 where .     

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 new approach to an N/G/1 queue

We propose a new approach that gives a one-step computational algorithm to directly obtain the queue length distribution of an N/G/1 queueing system. The new approach is based on the supplementary variable method and the matrix–analytic method. We shall show that this approach enables us to derive the joint distribution of the queue length and the elapsed service time. This revised version was published online in June 2006 with corrections to the Cover Date.     

The Maximum Queue Length for Heavy-Tailed Service Times in the M/G/1 FB Queue

This paper treats the maximum queue length M, in terms of the number of customers present, in a busy cycle in the M/G/1 queue. The distribution of M depends both on the service time distribution and on the service discipline. Assume that the service times have a logconvex density and the discipline is Foreground Background (FB). The FB service discipline gives service to the customer(s) that have received the least amount of service so far. It is shown that under these assumptions the tail of M is bounded by an exponential tail. This bound is used to calculate the time to overflow of a buffer, both in stable and unstable queues.     

Waiting Time Asymptotics in the Single Server Queue with Service in Random Order

We consider the single server queue with service in random order. For a large class of heavy-tailed service time distributions, we determine the asymptotic behavior of the waiting time distribution. For the special case of Poisson arrivals and regularly varying service time distribution with index ?ν, it is shown that the waiting time distribution is also regularly varying, with index 1?ν, and the pre-factor is determined explicitly. Another contribution of the paper is the heavy-traffic analysis of the waiting time distribution in the M/G/1 case. We consider not only the case of finite service time variance, but also the case of regularly varying service time distribution with infinite variance.     

A fluid model for a relay node in an ad hoc network: the case of heavy-tailed input

Relay nodes in an ad hoc network can be modelled as fluid queues, in which the available service capacity is shared by the input and output. In this paper such a relay node is considered; jobs arrive according to a Poisson process and bring along a random amount of work. The total transmission capacity is fairly shared, meaning that, when n jobs are present, each job transmits traffic into the queue at rate 1/(n + 1) while the queue is drained at the same rate of 1/(n + 1). Where previous studies mainly concentrated on the case of exponentially distributed job sizes, the present paper addresses regularly varying jobs. The focus lies on the tail asymptotics of the sojourn time S. Using sample-path arguments, it is proven that ${\mathbb{P}\left\{ S > x \right\}}${\mathbb{P}\left\{ S > x \right\}} behaves roughly as the residual job size, i.e., if the job sizes are regularly varying of index  − ν, the tail of S is regularly varying of index 1 − ν In addition, we address the tail asymptotics of other performance metrics, such as the workload in the queue, the flow transfer time and the queueing delay.     

Analysis of a finite MAP/G/1 queue with group services

The finite capacity queues, GI/PH/1/N and PH/G/1/N, in which customers are served in groups of varying sizes were recently introduced and studied in detail by the author. In this paper we consider a finite capacity queue in which arrivals are governed by a particular Markov renewal process, called a Markovian arrival process (MAP). With general service times and with the same type of service rule, we study this finite capacity queueing model in detail by obtaining explicit expressions for (a) the steady-state queue length densities at arrivals, at departures and at arbitrary time points, (b) the probability distributions of the busy period and the idle period of the server and (c) the Laplace-Stieltjes transform of the stationary waiting time distribution of an admitted customer at points of arrivals. Efficient algorithmic procedures for computing the steady-state queue length densities and other system performance measures when services are of phase type are discussed. An illustrative numerical example is presented.     

Fluid heuristics, Lyapunov bounds and efficient importance sampling for a heavy-tailed G/G/1 queue

We develop a strongly efficient rare-event simulation algorithm for computing the tail of the steady-state waiting time in a single server queue with regularly varying service times. Our algorithm is based on a state-dependent importance sampling strategy that is constructed so as to be straightforward to implement. The construction of the algorithm and its asymptotic optimality rely on a Lyapunov-type inequality that is used to bound the second moment of the estimator. The solution to the Lyapunov inequality is constructed using fluid heuristics. Our approach takes advantage of the regenerative ratio formula for the steady-state distribution—and does not use the first passage time representation that is particular to the delay in the G/G/1 queue. Hence, the strategy has the potential to be applied in more general queueing models.      

Impact of Bursty Traffic on Queues

The impact of bursty traffic on queues is investigated in this paper. We consider a discrete-time single server queue with an infinite storage room, that releases customers at the constant rate of c customers/slot. The queue is fed by an M/G/∞ process. The M/G/∞ process can be seen as a process resulting from the superposition of infinitely many ‘sessions’: sessions become active according to a Poisson process; a station stays active for a random time, with probability distribution G, after which it becomes inactive. The number of customers entering the queue in the time-interval [t, t + 1) is then defined as the number of active sessions at time t (t = 0,1, ...) or, equivalently, as the number of busy servers at time t in an M/G/∞ queue, thereby explaining the terminology. The M/G/∞ process enjoys several attractive features: First, it can display various forms of dependencies, the extent of which being governed by the service time distribution G. The heavier the tail of G, the more bursty the M/G/∞ process. Second, this process arises naturally in teletraffic as the limiting case for the aggregation of on/off sources [27]. Third, it has been shown to be a good model for various types of network traffic, including telnet/ftp connections [37] and variable-bit-rate (VBR) video traffic [24]. Last but not least, it is amenable to queueing analysis due to its very strong structural properties. In this paper, we compute an asymptotic lower bound for the tail distribution of the queue length. This bound suggests that the queueing delays will dramatically increase as the burstiness of the M/G/∞ input process increases. More specifically, if the tail of G is heavy, implying a bursty input process, then the tail of the queue length will also be heavy. This result is in sharp contrast with the exponential decay rate of the tail distribution of the queue length in presence of ‘non-bursty’ traffic (e.g. Poisson-like traffic). This revised version was published online in August 2006 with corrections to the Cover Date.