Development of Procedures to Analyze Queueing Models with Heavy-Tailed Interarrival and Service Times

George Mason University, Fairfax VA

Investigators

Abstract

This study is concerned with developing procedures for modeling queues with heavy-tailed distributions for interarrival and/or service times. These type of probability distributions decay much slower than exponential. Distributions of this type render queueing analyses very difficult, in that the Laplace-Stieltjes transforms (LSTs) of interarrival and/or service times, which play such a crucial role in analytical queueing theory, often do not have closed form. Previous researchers, to get around this, have approximated these heavy-tailed distributions by families of exponentials. The approaches proposed herein avoid the problems and pitfalls of finding approximating distributions by using the actual heavy-tailed distributions themselves. One method approximates the LSTs needed to produce the output measures (waiting-time and system-size distributions) of interest by directly approximating the LSTs using a discretized version of the heavy tailed distribution itself (transform approximation method [TAM]). Another method avoids using the LST directly by solving an integral equation involving the complementary cdf of the heavy-tailed distribution (level crossing method [LC]). While discrete-event simulation is an alternative to analytical queueing analyses, this also has its limitations in that it usually can only produce mean measures of output performance. It also has difficulty simulating certain of the heavy-tailed distributions, especially with large coefficients of variation (standard deviation divided by mean). New procedures for discrete-event simulation involving quantile estimators are also proposed. The usual assumptions that made queueing analyses so productive (Poisson arrivals and exponential-type holding times) clearly do not hold when arrivals and holding times are heavy-tailed. These distributions are important, however, in modeling some important situations. The impact of this research can benefit a variety of areas where heavy-tailed distributions come into play, such as the analysis of extreme events in insurance claims and risk models and some Internet traffic situations. Developing analytic/numeric queueing theoretic procedures and better ways of simulating traffic congestion for general distributions (heavy-tailed as well as any other type) can provide very effective additional tools in the queueing modeler's arsenal.