Information theoretic approximations for M/G/1 and G/G/1 queuing systems

Summary This paper presents new results concerning the use of information theoretic inference techniques in system modeling and concerning the widespread applicability of certain simple queuing theory formulas. For the case when an M/G/1 queue provides a reasonable system model but when information about the service time probability density is limited to knowledge of a few moments, entropy maximization and cross-entropy minimization are used to derive information theoretic approximations for various performance distributions such as queue length, waiting time, residence time, busy period, etc. Some of these approximations are shown to reduce to exact M/M/1 results when G = M. For the case when a G/G/1 queue provides a reasonable system model, but when information about the arrival and service distributions is limited to the average arrival and service rates, it is shown that various well known M/M/1 formulas are information theoretic approximations. These results not only provide a new method for approximating the performance distributions, but they help to explain the widespread applicability of the M/M/1 formulas.     

The M/G/1 retrial queue with Bernoulli schedules and general retrial times

This paper is concerned with the analysis of a single-server queue with Bernoulli vacation schedules and general retrial times. We assume that the customers who find the server busy are queued in the orbit in accordance with an FCFS (first-come-first-served) discipline and only the customer at the head of the queue is allowed access to the server. We first present the necessary and sufficient condition for the system to be stable and derive analytical results for the queue length distribution, as well as some performance measures of the system under steady-state condition. We show that the general stochastic decomposition law for M/G/1 vacation models holds for the present system also. Some special cases are also studied.     

Moments of the queue size distribution in the MAP/G/1 retrial queue

We consider an MAP/G/1 retrial queue. A necessary and sufficient condition is obtained for the existence of the moments of the queue size distribution. The condition is expressed in terms of the moment condition for a service time distribution. In addition, we provide recursive formulas for the moments of the queue size distribution. Numerical examples are given to illustrate our results.     

Queue size distribution in a discrete-time D-BMAP/G/1 retrial queue

We consider a discrete-time batch Markovian arrival process (D-BMAP)/G/1 retrial queue. We find the light-tailed asymptotics for the stationary distributions of the number of customers at embedded epochs and at arbitrary time. Using these tail asymptotics we propose a method for calculating the stationary distributions of the number of customers at embedded epochs and at arbitrary time. Numerical examples are presented to illustrate our results.     

M/M/1 retrial queue with working vacations

In this paper we introduce the new M/M/1 retrial queue with working vacations which is motivated by the performance analysis of a Media Access Control function in wireless systems. We give a condition for the stability of the model, which has an important impact on setting the retrial rate for such systems. We derive the closed form solution in equilibrium for the retrial M/M/1 queue with working vacations, and we also show that the conditional stochastic decomposition holds for this model as well.     

Maximum entropy and the G/G/1/N queue

Summary A new hybrid analytic framework, based on the principle of maximum entropy, is used to derive a closed form expression for the queue length distribution of a G/G/1 finite capacity queue. It is shown that Birth-Death homogeneous recursions for a single resource queue are special cases of maximum entropy one-step transitions which can be applied either in an operational or stochastic context. Furthermore, an equivalence relationship is used to analyse two-stage cyclic queueing networks with general service times, and favourable comparisons are made with global balance and approximate results. Numerical examples provide useful information on how critically system behaviour is affected by the distributional form of interarrival and service patterns. Comments on the implication of the work to the performance analysis and aggregation of computer systems are included.Some of the material included in this paper has been presented to the Performance '86 and ACM Sigmetrics 1986 Joint Conference on Computer Modelling, Measurement and Evaluation, May 28–30, 1986, University of North Carolina, USA     

On the number of customers served in the M/G/1 retrial queue: first moments and maximum entropy approach

In this paper we present general results on the number of customers, I, served during the busy period in an M/G/1 retrial system. Its analysis in terms of Laplace transforms has been previously discussed in the literature. However, this solution presents important limitations in practice; in particular, the moments of I cannot be obtained by direct differentiation. We propose a direct method of computation for the second moment of I and also for the probability of k,k⩽4, customers being served in a busy period. Then, the maximum entropy principle approach is used to estimate the true distribution of I according to the available information.Scope and purposeWe consider an M/G/1 queue with retrials. Retrial queueing systems are characterized by the fact that, an arriving customer who finds the server busy is obliged to leave the service area and return later to repeat his request after some random time. We deal with I, the number of customers served during the busy period of a retrial queue, and obtain closed expressions for its main characteristics, which will be employed in order to estimate the true distribution of this random variable.     

The Brownian approximation for rate-control throttles and the G/G/1/C queue

This paper studies approximations to describe the performance of a rate-control throttle based on a token bank, which is closely related to the standard G/G/1/C queue and the two-node cyclic network of ·/G/1/∞ queues. Several different approximations for the throttle are considered, but most attention is given to a Brownian or diffusion approximation. The Brownian approximation is supported by a heavy-traffic limit theorem (as the traffic intensity approaches the upper limit for stability) for which an upper bound on the rate of convergence is established. Means and squared coefficients of variation associated with renewal-process approximations for the overflow processes are also obtained from the Brownian approximation. The accuracy of the Brownian approximation is investigated by making numerical comparisons with exact values. The relatively simple Brownian approximation for the job overflow rate is not very accurate for small overflow rates, but it nevertheless provides important insights into the way the throttle design parameters should depend on the arrival-process characteristics in order to achieve a specified overflow rate. This simple approximation also provides estimates of the sensitivity of the overflow rates to the model parameters.     

A functional approximation for the M/G/1/N queue

This paper presents a new approach to the functional approximation of the M/G/1/N built on a Taylor series approach. Specifically, we establish an approximative expression for the remainder term of the Taylor series that can be computed in an efficient manner. As we will illustrate with numerical examples, the resulting Taylor series approximation turns out to be of practical value.     

Perturbation analysis of waiting times in the G/G/1 queue

This paper is devoted to perturbation analysis of the stationary distribution of waiting times in the G/G/1 queue with a parameter-dependent service time distribution. We provide sufficient conditions under which the stationary distribution is Lipschitz continuous and we explicitly compute the Lipschitz constant. Thereby, we provide bounds on the effect of a (finite) perturbation of the service time distribution on the stationary waiting time. The case of infinitesimal perturbations (read, derivatives) is treated as well.     

The M/G/1 processor-sharing queue with disasters

n this paper, the M/G/1 processor-sharing queue with disasters is given a detailed analysis by means of extending the supplementary variable method. The transient and steady-state distributions of the queue length are expressed as a simple and computable form, the Laplace-Stieltjes transform of the sojourn time is derived, and the Laplace transform of the busy period and its mean are obtained. Also, the approach developed in this paper is shown to be able to study more complicated M/G/1 processor-sharing models.     

An improved truncation technique to analyze a Geo/PH/1 retrial queue with impatient customers

This paper considers a discrete-time retrial queue with impatient customers. We establish the global balance equations of the Markov chain describing the system evolution and prove that this queueing system is stable as long as the customers are strict impatient and the mean retrial time is finite. Direct truncation with matrix decomposition is used to approximate the steady-state distribution of the system state and hence derive a set of performance measures. The proposed matrix decomposition scheme is presented in a general form which is applicable to any finite Markov chain of the GI/M/1-type. It represents a generalization of the Gaver–Jacobs–Latouche's algorithm that deals with QBD process. Different sets of numerical results are presented to test the efficiency of this technique compared to the generalized truncation one. Moreover, an emphasis is put on the effect of impatience on the main performance measures.     

A maximum entropy priority approximation for a stableG/G/1 queue

Summary The principle of maximum entropy is used under two different sets of mean value constraints to analyse a stableG/G/1 queue withR priority classes under preemptive-resume (PR) and non-preemptive head-of-line (HOL) scheduling disciplines. New one-step recursions for the maximum entropy state probabilities are established and closed form approximations for the marginal queue length distribution per priority class are derived. To expedite the utility of the maximum entropy solutions exact analysis, based on the generalised exponential (GE) distribution, is used to approximate the marginal mean queue length and idle state probability class constraints for both the PR and HOLG/G/1 priority queues. Moreover, these results are used as building blocks in order to provide new approximate formulae for the mean and coefficient of variation of the effective priority service-time and suggest a maximum entropy algorithm for general open queueing networks with priorities in the context of the reduced occupancy approximation (ROA) method. Numerical examples illustrate the accuracy of the proposed maximum entropy approximations in relation to simulations involving different interarrival-time and service-time distributions per class. Comments on the extension of the work to more complex types of queueing systems are included.This work is sponsored in part by the Science and Engineering Research Council (SERC), UK, under grant GR/D/12422 and in part by the Ministry of Higher Education of the Algerian Government     

An M/PH/k retrial queue with finite number of sources

We study retrial queues with a finite source of customers and identical multiple servers in parallel. Service time requirements in such systems are not of exponential type, yet most of the models assume this service distribution. In this paper, we allow the service times to assume phase type distribution and present two different types of Markov chains based on state space arrangements, for modelling the system. We discuss the special features of the two formulations, show how to obtain some key performance measures and present numerical examples.     

The departure process of an N/G/1 queue

The departure process of an N/G/1 queue is investigated. The arrival process called an N process is a versatile point process and includes, for example, a Markov-modulated Poisson process, which is comprised of models of packetized voice and video traffic arrival processes. The first passage analysis yields LSTs of distributions of the interdeparture times. Emphasis is on the interdeparture times of an N/D/1 queue. Numerical examples show that correlation of interarrival times is likely to be preserved in interdeparture times, and that the departure of a voice packet multiplexer can be expected to be smoothed for a normal load. The result in this paper enables evaluation of the smoothing effect of burst traffic through nodes in Asynchronous Transfer Mode networks.     

A note on mixed exponential approximations for Gi/G/1 waiting times

A method is offered for the effective estimation of the stationary waiting-time distribution of the GI/G/1 queue by a (possibly nonconvex) mixed exponential CDF. The approach relies on obtaining a generalized exponential mixture as an approximation for the distribution of the service times. This is done by the adaptation of a nonlinear optimization algorithm previously developed for the maximum-likelihood estimation of parameters from mixed Weibull distributions. The approach is particularly well-suited for obtaining the delay distribution beginning from raw interarrivai and service-time data.