Internet traffic flows have often been characterized as having power-tailed (long-tailed, fat-tailed, heavy-tailed) packet interarrival times or service requirements. In this work, we focus on the development of complete and computationally efficient steady-state solutions of queues with power-tailed interarrival times when the service times are assumed exponential. The classical method for obtaining the steady-state probabilities and delay-time distributions for the G/M/1 (G/M/c) queue requires solving a root-finding problem involving the Laplace-Stieltjes transform of the interarrival-time distribution function. Then the exponential service assumption is combined with the derived geometric arrival-point probabilities to get both the limiting general-time state and delay distributions. However, in situations where there is a power tail, the interarrival transform is typically quite complicated and never analytically tractable. In addition, it is possible that there is only a degenerate steady-state system-size probability distribution. Thus, an alternative approach to obtaining a steady-state solution is typically needed when power-tailed interarrivals are present. We exploit the exponentiality of the steady-state delay distributions for the G/M/1 and G/M/c queues, using level-crossings and a transform approximation method, to develop an alternative root-finding problem when there are power-tailed interarrival times. Extensive computational results are given.

We propose two related methods for deriving probability distribution estimates using approximate rational Laplace transform representations. Whatever method is used, the result is a Coxian estimate for an arbitrary distribution form or plain sample data, with the algebra of the Coxian often simplifying to a generalized hyperexponential or phase-type. The transform (or, alternatively, the moment-generating function) is used to facilitate the computations and leads to an attractive algorithm. For method one, the first 2N − 1 derivatives of the transform are matched with those of an approximate rational function; for the second method, a like number of values of the transform are matched with those of the approximation. The numerical process in both cases begins with an empirical Laplace transform or truncation of the actual transform, and then requires only the solution of a relatively small system of linear equations, followed by root finding for a low-degree polynomial. Besides the computationally attractive features of the overall procedure, it addresses the question of the number of terms, or the order, involved in a generalized hyperexponential, phase-type, or Coxian distribution, a problem not adequately treated by existing methods. Coxian distributions are commonly used in the modeling of single-stage and network queueing problems, inventory theory, and reliability analyses. They are particularly handy in the development of large-scale model approximations.

There has been frequent controversy over the years regarding the use of numerical rootfinding for the solution of queueing problems. It has been said that such problems quite often present computational difficulties. However, it turns out that rootfinding in queueing is so well structured that problems rarely occur. There are fundamental properties possessed by the well-known queueing models that eliminate classical rootfinding problems. Most importantly, we show that distinctness of roots is common within simply determined regions in the complex plane and provide conditions under which the characteristic equations for the G/EK/1 and EK/G/1 models have easily found, distinct roots. Furthermore, we show that the characteristic equation for the more general G/GEK/1 model has a collection of real and complex roots which are effectively distinct and located in clearly defined regions of the complex domain. Extensive computational results are given to support our contentions. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

This note provides some extensions of recent work by Delbrouck, which dealt with a queuing model of a feedback system with queue-dependent service times.The emphasis of this present work is upon necessary and sufficient conditions for ergodicity, the relationship of the imbedded and general-time queuing processes, and the relaxation of the extent of state dependence for the service times.