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     

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.     

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     

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.     

Approximating queue lengths inM(t)/G/1 queue using the maximum entropy principle

Using the discrete time approach a model is developed for obtaining the expected queue length of theM(t)/G/1 queue. This type of queue occurs in different forms in transportation and traffic systems and in communications and manufacturing systems. In order to cut down the very high computational efforts required to evaluate the performance measures in such queues by exact methods, the Maximum Entropy Principle is used to approximate the expected queue length which is one of the most commonly used performance measures. A procedure is then developed for reducing the error encountered when this approximation is adopted. The results from this paper will encourage the practitioners to use the appropriate time-varying queueing models when the need arises instead of resorting to very poor approximations.     

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.     

Finite-source M/M/S retrial queue with search for balking and impatient customers from the orbit

The present paper deals with a generalization of the homogeneous multi-server finite-source retrial queue with search for customers in the orbit. The novelty of the investigation is the introduction of balking and impatience for requests who arrive at the service facility with a limited capacity and FIFO queue. Arriving customers may balk, i.e., they either join the queue or go to the orbit. Moreover, the requests are impatient and abandon the buffer after a random time and enter the orbit, too. In case of an empty buffer, each server searches for a customer in the orbit after finishing service. All random variables involved in the model construction are supposed to be exponentially distributed and independent of each other. The primary aim of this analysis is to show the effect of balking, impatience, and buffer size on the steady-state performance measures. Concentrating on the mean response time, several numerical examples are investigated by the help of the MOSEL-2 tool used for creating the model and calculating the stationary characteristics.     

Periodic discrete-time one-channel GI/G/1 retrial queuing system with FCFS service discipline

A discrete-time one-channel queuing system with general inter-arrival, service, and orbit times periodically dependent on the number of arrival is considered. The service discipline is assumed to be FCFS. The sufficient condition for the ergodicity of an embedded Markov chain is derived.