TU Berlin

Internet Network ArchitecturesAidan Walton's Publications

Page Content

to Navigation

Aidan Walton's Publications

Fitting mixtures of exponentials to long-tail distributions to analyze network performance models
Citation key FW-FMELDANPM-98
Author Feldmann, Anja and Whitt, Ward
Pages 245–279
Year 1998
ISSN 0166-5316
DOI http://dx.doi.org/10.1016/S0166-5316(97)00003-5
Address Amsterdam, The Netherlands, The Netherlands
Journal Performance Evaluation
Volume 31
Number 3-4
Note Number 3-4; an earlier version appeared as FW-FMELDANPM-97.
Publisher Elsevier Science Publishers B. V.
Abstract Traffic measurements from communication networks have shown that many quantities characterizing network performance have long-tail probability distributions, i.e., with a tail that decays more slowly than exponentially. File lengths, call holding times, scene lengths in MPEG video streams, and intervals between connection requests in Internet traffic all have been found to have long-tail distributions, being well described by distributions such as the Pareto and Weibull. It is known that long-tail distributions can have a dramatic effect upon performance, e.g., long-tail service-time distributions cause long-tail waiting-time distributions in queues, but it is often difficult to describe this effect in detail, because performance models with component long-tail distributions tend to be difficult to analyze. We address this problem by developing an algorithm for approximating a long-tail distribution by a hyperexponential distribution (a finite mixture of exponentials). We first prove that, in principle, it is possible to approximate distributions from a large class, including the Pareto and Weibull distributions, arbitrarily closely by hyperexponential distributions. Then we develop a specific fitting algorithm. Our fitting algorithm is recursive over time scales, starting with the largest time scale. At each stage, an exponential component is fit in the largest remaining time scale and then the fitted exponential component is subtracted from the distribution. Even though a mixture of exponentials has an exponential tail, it can match a long-tail distribution in the regions of primary interest when there are enough exponential components. When a good fit is achieved, the approximating hyperexponential distribution inherits many of the difficulties of the original long-tail distribution; e.g., it is still difficult to obtain reliable estimates from simulation experiments. However, some difficulties are avoided; e.g., it is possible to solve some queuing models which could not be solved before. We give examples showing that the fitting procedure is effective, both for directly matching a long-tail distribution and for predicting the performance in a queueing model with a long-tail service-time distribution.
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe