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].     

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.     

Approximations for waiting time in GI/G/1 systems

The Sokolov procedure is described and used to obtain an explicit and easily applied approximation for the waiting time distribution in the FIFO GI/G/1 queue.     

Equivalence relations in the approximations for the M/G/s/s + r queue

This paper investigates some equivalence relations among previously established approximations for the steady-state distribution in an M/G/s queue with finite waiting spaces. The focus is on four approximations developed by Hokstad [1], Tijms and van Hoorn [2], Miyazawa [3] and Kimura [4]. These approximations have been obtained by completely different approaches and they have different expressions. Equivalence theorems show conditions under which some of the approximations coincide.     

Derivation of the N-step interdeparture time distribution in GI/G/1 queueing systems

The departure process of a queueing system has been studied since the 1960s. Due to its inherent complexity, closed form solutions for the distribution of the departure process are nearly intractable. In this paper, we derive a closed form expression for the distribution of interdeparture time in a GI/G/1 queueing model. Without loss of generality, we consider an embedded Markov chain in a general K_M/G/1 queueing system, in which the interarrival time distribution is Coxian and service time distribution is general. Closed form solutions of the equilibrium distribution are derived for this model and the Laplace–Stieltjes transform (LST) of the distribution of interdeparture times is presented. An algorithmic computing procedure is given and numerical examples are provided to illustrate the results. With the analysis presented, we provide a novel analytic tool for studying the departure process in a general queueing model.     

An exact FCFS waiting time analysis for a general class of G/G/s queueing systems

A closed form expression for the waiting time distribution under FCFS is derived for the queueing system MGE_k/MGE_m/s, where MGE_n is the class of mixed generalized Erlang probability density functions (pdfs) of ordern, which is a subset of the Coxian pdfs that have rational Laplace transform. Using the calculus of difference equations and based on previous results of the author, it is proved that the waiting time distribution is of the form 1- , under the assumption that the rootsU _j are distinct, i.e. belongs to the Coxian class of distributions of order . The present approach offers qualitative insight by providing exact and asymptotic expressions, generalizes and unifies the well known theories developed for the G/G/1,G/M/s systems and leads to an algorithm, which is polynomial if only one of the parameterss orm varies, and is exponential if both parameters vary. As an example, numerical results for the waiting time distribution of the MGE₂/MGE₂/s queueing system are presented.     

On reducing time spent in M/G/1 systems

In this paper we define a new ‘truncated shortest processing time’ scheduling discipline and present the first two moments of the time spent in a single server queuing system (M/G/1) with Poisson arrivals and truncated shortest processing time scheduling discipline. Also for quadratic cost functions, the mean cost of time spent in an M/G/1 system under (1) first come first served. (2) shortest processing time. (3) two level shortest processing time, (4) two class non-preemptive priority, and (5) truncated shortest processing time scheduling disciplines are compared.     

On some relations between spinor and orthogonal groups

In this article we consider Clifford algebras over the field of real numbers of finite dimension. We define the operation of Hermitian conjugation for the elements of Clifford algebra. This operation allows us to define the structure of Euclidian space on the Clifford algebra. We consider pseudo-orthogonal group and its subgroups — special pseudo-orthogonal, orthochronous, orthochorous and special orthochronous groups. As we know, spinor groups are double covers of these orthogonal groups.We proved theorem that relates the norm of element of spinor group to the minor of matrix of the corresponding orthogonal group.     

Asymptotics for transient and stationary probabilities for finite and infinite buffer discrete time queues

Consider a discrete time queue with i.i.d. arrivals (see the generalisation below) and a single server with a buffer length m. Let τm be the first time an overflow occurs. We obtain asymptotic rate of growth of moments and distributions of τm as m → ∞. We also show that under general conditions, the overflow epochs converge to a compound Poisson process. Furthermore, we show that the results for the overflow epochs are qualitatively as well as quantitatively different from the excursion process of an infinite buffer queue studied in continuous time in the literature. Asymptotic results for several other characteristics of the loss process are also studied, e.g., exponential decay of the probability of no loss (for a fixed buffer length) in time [0,η], η → ∞, total number of packets lost in [0, η, maximum run of loss states in [0, η]. We also study tails of stationary distributions. All results extend to the multiserver case and most to a Markov modulated arrival process. This revised version was published online in June 2006 with corrections to the Cover Date.     

GI/G/1 Interdeparture time and queue-length distributions via the Laguerre transform

Queue length and interdeparture distributions for GI/G/1 are obtained using the Laguerre function expansion of the waiting time distribution. The expansion of the steady state waiting time distribution is obtained here by solving a small set of linear equations in the Laguerre function expansion coefficients. Examples show the accuracy of the results and illustrate purely numerical techniques for obtaining the necessary expansions of the arrival and service distributions.     

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.     

A heavy-traffic-limit formula for the moments of the stationary distribution in GI/G/1-type Markov chains

This paper studies the heavy-traffic limit of the moments of the stationary distribution in GI/G/1-type Markov chains. For these Markov chains, several researchers have derived heavy-traffic-limit formulas for the stationary distribution itself. However, for its moments, no such formulas have been reported in the literature. This paper presents a heavy-traffic-limit formula for the moments of the stationary distribution and a sufficient condition for the formula to hold, by using a characteristic function approach.     

Conditioned limit theorem for virtual waiting time process of the GI/G/1 queue

We prove that in the queueing system GI/G/1 with traffic intensity one, the virtual waiting time process suitably scaled, normed and conditioned by the event that the length of the first busy period exceeds n converges to the Brownian meander process, as n .     

Combined Elapsed Time and Matrix-Analytic Method for the Discrete Time GI/G/1 and GI X /G/1 Systems

In this paper, we show that the discrete GI/G/1 system can be easily analysed as a QBD process with infinite blocks by using the elapsed time approach in conjunction with the Matrix-geometric approach. The positive recurrence of the resulting Markov chain is more easily established when compared with the remaining time approach. The G-measure associated with this Markov chain has a special structure which is usefully exploited. Most importantly, we show that this approach can be extended to the analysis of the GI ^X /G/1 system. We also obtain the distributions of the queue length, busy period and waiting times under the FIFO rule. Exact results, based on computational approach, are obtained for the cases of input parameters with finite support – these situations are more commonly encountered in practical problems.     

On some functional relations between Mordell-Tornheim double L-functions and Dirichlet L-functions

In the past decade, many relation formulas for the multiple zeta values, further for the multiple L-values at positive integers have been discovered. Recently Matsumoto suggested that it is important to reveal whether those relations are valid only at integer points, or valid also at other values. Indeed the famous Euler formula for ζ(2k) can be regarded as a part of the functional equation of ζ(s). In this paper, we give certain analytic functional relations between the Mordell-Tornheim double L-functions and the Dirichlet L-functions of conductor 3 and 4. These can be regarded as continuous generalizations of the known discrete relations between the Mordell-Tornheim L-values and the Dirichlet L-values of conductor 3 and 4 at positive integers.     

Numerical analysis for bulk-arrival queueing systems: Root-finding and steady-state probabilities inGI r /M/1 queues

Queueing theorists have presented, as solutions to many queueing models, probability generating functions in which state probabilities are expressed as functions of the roots of characteristic equations, evaluation of the roots in particular cases being left to the reader. Many users have complained that such solutions are inadequate. Some queueing theorists, in particular Neuts [6], rather than use Rouché's theorem to count roots and an equation-solver to find them, have developed new algorithms to solve queueing problems numerically, without explicit calculation of roots. Powell [7] has shown that in many bulk service queues arising in transportation models, characteristic equations can be solved and state probabilities can be found without serious difficulty, even when the number of roots to be found is large. We have slightly modified Powell's method, and have extended his work to cover a number of bulk-service queues discussed by Chaudhry et al. [1] and a number of bulk-arrival queues discussed in the present paper.     

On the Relative Waiting Times in the GI/M/s and the GI/M/1 Queueing Systems

The expected steady-state waiting time, Wq(s), in a GI/M/s system with interarrival-time distribution H(·) is compared with the mean waiting time, Wq, in an "equivalent" system comprised of s separate GI/M/1 queues each fed by an interarrival-time distribution G(·) with mean arrival rate equal to 1/s times that of H(·). For H(·) assumed to be Exponential, Gamma or Deterministic three possible relationships between H(·) and G(·) are considered: G(·) can be of the "same type" as H(·); G(·) can be derived from H(·) by assigning new arrivals to the individual channels in a cyclic order; and G(·) may be obtained from H(·) by assigning customers probabilistically to the different queues. The limiting behaviour of the ratio R = Wq/Wq(s) is studied for the extreme values (1 and 0) of the common traffic intensity, ρ. Closed form results, which depend on the forms of H(·) and G(·) and on the relationships between them, are derived. It is shown that Wq is greater than Wq(s) by a factor of at least (s + 1)/2 when ρ approaches one, and that R is at least s(s!) when ρ tends to zero. In the latter case, however, R goes to infinity (!) in most cases treated. The results may be used to evaluate the effect on the waiting times when, for certain (non-queueing) reasons, it is needed to partition a group of s servers into several small groups.     

GI／G／1排队系统的队长和等待时间的瞬时分布

本是[1，2]的继续,在本中利用马氏骨架过程给出了GI／G／1排队系统的队长的瞬时分布的另一新的计算方法和等待时间的计算方法。     

On the Queue Length Distribution for the GI/G/1/K/VM Queue

Abstract

We present a transform-free distribution of the steady-state queue length for the GI/G/1/K queueing system with multiple vacations under exhaustive FIFO service discipline. The method we use is a modified supplementary variable technique and the result we obtain is expressed in terms of conditional expectations of the remaining service time, the remaining interarrival time, and the remaining vacation, conditional on the queue length at the embedded points. The case K → ∞ is also considered.     

Rare event simulation for a slotted time M/G/s model

This paper develops a rare-event simulation algorithm for a discrete-time version of the M/G/s loss system and a related Markov-modulated variant of the same loss model. The algorithm is shown to be efficient in the many-server asymptotic regime in which the number of servers and the arrival rate increase to infinity in fixed proportion. A key idea is to study the system as a measure-valued Markov chain and to steer the system to the rare event through a randomization of the time horizon over which the rare event is induced.