Statistical Analysis of Single-server Loss Queueing Systems

In this article statistical bounds for certain output characteristics of the M/GI/1/n and GI/M/1/n loss queueing systems are derived on the basis of large samples of an input characteristic of these systems, such as service time in the M/GI/1/n queueing system or interarrival time in the GI/M/1/n queueing system. The analysis in this article is based on application of Kolmogorov’s statistics for empirical probability distribution functions.     

Continuity theorems for the M/M/1/n queueing system

In this paper continuity theorems are established for the number of losses during a busy period of the M/M/1/n queue. We consider an M/GI/1/n queueing system where the service time probability distribution, slightly different in a certain sense from the exponential distribution, is approximated by that exponential distribution. Continuity theorems are obtained in the form of one or two-sided stochastic inequalities. The paper shows how the bounds of these inequalities are changed if further assumptions, associated with specific properties of the service time distribution (precisely described in the paper), are made. Specifically, some parametric families of service time distributions are discussed, and the paper establishes uniform estimates (given for all possible values of the parameter) and local estimates (where the parameter is fixed and takes only the given value). The analysis of the paper is based on the level crossing approach and some characterization properties of the exponential distribution. Dedicated to Vladimir Mikhailovich Zolotarev, Victor Makarovich Kruglov, and to the memory of Vladimir Vyacheslavovich Kalashnikov.     

Asymptotic Results and a Markovian Approximation for the M(n)/M(n)/s+GI System

In this paper for the M(n)/M(n)/s+GI system, i.e. for a s-server queueing system where the calls in the queue may leave the system due to impatience, we present new asymptotic results for the intensities of calls leaving the system due to impatience and a Markovian system approximation where these results are applied. Furthermore, we present a new proof for the formulae of the conditional density of the virtual waiting time distributions, recently given by Movaghar for the less general M(n)/M/s+GI system. Also we obtain new explicit expressions for refined virtual waiting time characteristics as a byproduct.     

Empirical validation of a queueing approach to uninterrupted traffic flows

In this paper, the use of queueing theory for modeling uninterrupted traffic flows is evaluated. Empirical data on speeds and flows are used to evaluate speeds generated by the different queueing models. Using the Theil inequality coefficient as evaluation criterion, the speeds generated by the queueing models are compared to the empirical speeds. Queueing models that best fit the observed speeds are obtained. It appears that traffic flow on a highway during non-congested hours is best described using a M/G/1 queueing model. During the congested hours however, the state dependent queueing GI/G/z models are more realistic. Because the queueing models describe the empirical data well, they can also be used to evaluate potential improvements in existing traffic conditions. Received: April 2005 / Revised version: June 2005 AMS classification: 60K30, 68M20     

Stationary Distributions of GI/M/c Queue with PH Type Vacations

We study a GI/M/c type queueing system with vacations in which all servers take vacations together when the system becomes empty. These servers keep taking synchronous vacations until they find waiting customers in the system at a vacation completion instant.The vacation time is a phase-type (PH) distributed random variable. Using embedded Markov chain modeling and the matrix geometric solution methods, we obtain explicit expressions for the stationary probability distributions of the queue length at arrivals and the waiting time. To compare the vacation model with the classical GI/M/c queue without vacations, we prove conditional stochastic decomposition properties for the queue length and the waiting time when all servers are busy. Our model is a generalization of several previous studies.     

Performance analysis approximation in a queueing system of type M/G/1

In this work, we apply the strong stability method to obtain an estimate for the proximity of the performance measures in the M/G/1 queueing system to the same performance measures in the M/M/1 system under the assumption that the distributions of the service time are close and the arrival flows coincide. In addition to the proof of the stability fact for the perturbed M/M/1 queueing system, we obtain the inequalities of the stability. These results give with precision the error, on the queue size stationary distribution, due to the approximation. For this, we elaborate from the obtained theoretical results, the STR-STAB algorithm which we execute for a determined queueing system: M/Coxian − 2/1. The accuracy of the approach is evaluated by comparison with simulation results.     

Computing steady-state queueing-time distributions of single-server queues:GI X /M/1

This paper presents a computationally efficient method to find the steady-state distributions of actual queueing times of the first customer, as well as of a randomly selected customer, of an arrival group for the queueing systemGI ^X /M/1, and hence the queueing-time distribution of a customer for the systemGI/E _X /1. The distribution of virtual queueing time is also obtained. Approximate analysis based on one or more roots is also discussed. Though the exact detailed as well as approximate computations for a variety of interarrival-time distributions such as generalized Erlang, mixed generalized Erlang, hyperexponential, generalized hyperexponential, and deterministic have been carried out, only representative results in the form of tables have been appended. The results obtained should prove useful to queueing theorists, practitioners, and others.     

Asymptotic Analysis of the GI/M/ 1 /n Loss System as n Increases to Infinity

This paper provides the asymptotic analysis of the loss probability in the GI/M/1/n queueing system as n increases to infinity. The approach of this paper is alternative to that of the recent papers of Choi and Kim (2000) and Choi et al. (2000) and based on application of modern Tauberian theorems with remainder. This enables us to simplify the proofs of the results on asymptotic behavior of the loss probability of the abovementioned paper of Choi and Kim (2000) as well as to obtain some new results.     

Two fluid approximations for multi-server queues with abandonments

Insight is provided into a previously developed M/M/s/r+M(n) approximation for the M/GI/s/r+GI queueing model by establishing fluid and diffusion limits for the approximating model. Fluid approximations for the two models are compared in the many-server efficiency-driven (overloaded) regime. The two fluid approximations do not coincide, but they are close.     

Two new heuristics for the <Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/<Emphasis Type="Italic">n</Emphasis>/0 queueing loss system with examples based on the two-phase Coxian distribution

In this paper, we introduce a new heuristic approach for the numerical analysis of queueing systems. In particular, we study the general, multi-server queueing loss system, the GI/G/n/0 queue, with an emphasis on the calculation of steady-state loss probabilities. Two new heuristics are developed, called the GM Heuristic and the MG Heuristic, both of which make use of an exact analysis of the corresponding single-server GI/G/1/0 queue. The GM Heuristic also uses an exact analysis of the GI/M/n/0 queue, while the MG Heuristic uses an exact analysis of the M/G/n/0 queue. Experimental results are based on the use of two-phase Coxian distributions for both the inter-arrival time and the service time; these include an error analysis for each heuristic and the derivation of experimental probability bounds for the loss probability. For the class of problems studied, it is concluded that there are likely to be many situations where the accuracy of the GM Heuristic is adequate for practical purposes. Methods are also developed for combining the GM and MG Heuristics. In some cases, this leads to approximations that are significantly more accurate than those obtained by the individual heuristics.     

Additive functionals with application to sojourn times in infinite-server and processor sharing systems

We deal with additive functionals of stationary processes. It is shown that under some assumptions a stationary model of the time-changed process exists. Further, bounds for the expectation of functions of additive functionals are derived. As an application we analyze virtual sojourn times in an infinite-server system where the service speed is governed by a stationary process. It turns out that the sojourn time of some kind of virtual requests equals in distribution an additive functional of a stationary time-changed process, which provides bounds for the expectation of functions of virtual sojourn times, in particular bounds for fractional moments and the distribution function. Interpreting the GI(n)/GI(n)/∞ system or equivalently the GI(n)/GI system under state-dependent processor sharing as an infinite-server system where the service speed is governed by the number n of requests in the system provides results for sojourn times of virtual requests. In the case of M(n)/GI(n)/∞, the sojourn times of arriving and added requests equal in distribution sojourn times of virtual requests in modified systems, which yields several results for the sojourn times of arriving and added requests. In case of positive integer moments, the bounds generalize earlier results for M/GI(n)/∞. In particular, the mean sojourn times of arriving and added requests in M(n)/GI(n)/∞ are proportional to the required service time, generalizing Cohen’s famous result for M/GI(n)/∞.     

Delay analysis of extended rtPS for VoIP service in IEEE 802.16e by matrix analytic method

Extended real time polling service (ErtPS) is added to IEEE 802.16e-2005 standards in order for VoIP service to use uplink resources efficiently by considering on/off characteristic of voice source. Recently average queueing delay of ErtPS algorithm for VoIP service was investigated, and it was shown that ErtPS allows to admit more users than UGS algorithm. But we need the probability distribution of queueing delay rather than average queueing delay in order to provide a necessary information for QoS. In this paper we obtain the probability distribution of queueing delay of ErtPS for VoIP service by using the matrix analytic method for the GI/M/1 type and the M/G/1 type matrices in cases of the service time being exponential and deterministic respectively. By applying the results on deterministic service time we find the maximum allowable number of VoIP users with the required constraint on queueing delay. This research was supported by the MIC (Ministry of Information and Communication), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Assessment).     

The Discrete-Time GI/Geo/1 Queue with Multiple Vacations

We study a discrete-time GI/Geo/1 queue with server vacations. In this queueing system, the server takes vacations when the system does not have any waiting customers at a service completion instant or a vacation completion instant. This type of discrete-time queueing model has potential applications in computer or telecommunication network systems. Using matrix-geometric method, we obtain the explicit expressions for the stationary distributions of queue length and waiting time and demonstrate the conditional stochastic decomposition property of the queue length and waiting time in this system.     

Small work-load mode in a queueing system with random nonstationary intensity

We consider a queueing system of M _t R|GI|1|∞ type with doubly stochastic Poisson arrival stream. The case of a small work load in such a system is studied. We derive an asymptotic expansion in the work-load smallness parameter of the distribution function of the virtual waiting time.     

Large-time asymptotics for the Gt/Mt/st+GIt many-server fluid queue with abandonment

We previously introduced and analyzed the G _t /M _t /s _t +GI _t many-server fluid queue with time-varying parameters, intended as an approximation for the corresponding stochastic queueing model when there are many servers and the system experiences periods of overload. In this paper, we establish an asymptotic loss of memory (ALOM) property for that fluid model, i.e., we show that there is asymptotic independence from the initial conditions as time t evolves, under regularity conditions. We show that the difference in the performance functions dissipates over time exponentially fast, again under the regularity conditions. We apply ALOM to show that the stationary G/M/s+GI fluid queue converges to steady state and the periodic G _t /M _t /s _t +GI _t fluid queue converges to a periodic steady state as time evolves, for all finite initial conditions.     

An investigation of phase-distribution moment-matching algorithms for use in queueing models

Algorithms for matching moments to phase-type distributions are evaluated on the basis of their performance in their intended application, queueing models. The moment-matching algorithms under consideration match two moments to a hyperexponential distribution with balanced means and three moments to a mixture of two Erlang distributions of common order. These algorithms are used to approximate an interarrival-time distribution for a queueing model, and the accuracy of associated performance-measure approximations is then used to evaluate the moment-matching algorithms. Three performance measures are considered, and attention is focussed on the steady-state mean queue length (number in system) of theGI/M/1 queue. Performance-measure approximations are compared to three-moment bounds and performance-measure values arising from hypothetical approximated distributions.     

On the Stationary Distribution of the GI X /M Y /1 Queueing System

For the GI ^X /M/1 queue, it has been recently proved that there exist geometric distributions that are stochastic lower and upper bounds for the stationary distribution of the embedded Markov chain at arrival epochs. In this note we observe that this is also true for the GI ^X /M ^Y /1 queue. Moreover, we prove that the stationary distribution of its embedded Markov chain is asymptotically geometric. It is noteworthy that the asymptotic geometric parameter is the same as the geometric parameter of the upper bound. This fact justifies previous numerical findings about the quality of the bounds.     

Age Process, Workload Process, Sojourn Times, and Waiting Times in a Discrete Time SM[K]/PH[K]/1/FCFS Queue

In this paper, we study a discrete time queueing system with multiple types of customers and a first-come-first-served (FCFS) service discipline. Customers arrive according to a semi-Markov arrival process and the service times of individual customers have PH-distributions. A GI/M/1 type Markov chain for a generalized age process of batches of customers is introduced. The steady state distribution of the GI/M/1 type Markov chain is found explicitly and, consequently, the steady state distributions of the age of the batch in service, the total workload in the system, waiting times, and sojourn times of different batches and different types of customers are obtained. We show that the generalized age process and a generalized total workload process have the same steady state distribution. We prove that the waiting times and sojourn times have PH-distributions and find matrix representations of those PH-distributions. When the arrival process is a Markov arrival process with marked transitions, we construct a QBD process for the age process and the total workload process. The steady state distributions of the waiting times and the sojourn times, both at the batch level and the customer level, are obtained from the steady state distribution of the QBD process. A number of numerical examples are presented to gain insight into the waiting processes of different types of customers.AMS subject classification: 60K25, 60J10This revised version was published online in June 2005 with corrected coverdate     

The Recursive Solution for Geom/G/1（E,SV） queue with Feedback and Single Server Vacation

Using recursive method,this paper studies the queue size properties at any epoch n + in Geom/G/1(E,SV) queueing model with feedback under LASDA (late arrival system with delayed access) setup.Some new results about the recursive expressions of queue size distribution at different epoch (n+,n,n-) are obtained.Furthermore the important relations between stationary queue size distribution at different epochs are discovered.The results are different from the relations given in M/G/1 queueing system.The model discussed in this paper can be widely applied in many kinds of communications and computer network.     

Bonferroni-type inequalities; Chebyshev-type inequalities for the distributions on [0, n]

An elementary majorant-minorant method to construct the most stringent Bonferroni-type inequalities is presented. These are essentially Chebyshev-type inequalities for discrete probability distributions on the set {0, 1,..., n}, where n is the number of concerned events, and polynomials with specific properties on the set lead to the inequalities. All the known results are proved easily by this method. Further, the inequalities in terms of all the lower moments are completely solved by the method. As examples, the most stringent new inequalities of degrees three and four are obtained. Simpler expressions of Mrgritescu's inequality (1987, Stud. Cerc. Mat., 39, 246–251), improving Galambos' inequality, are given.