Moment matching algorithm

Much of queueing theory revolves around the exponential distribution, since the memoryless nature of the exponential distribution enables an analysis via Markov chains. Unfortunately, real-world workloads such as CPU service requirements, file sizes, durations of FTP transfers, etc. do not have exponential distributions, but rather follow various general distributions. A way for us to deal with workloads with general distributions is to model these general distributions by a combination of exponential distributions, known as a phase type (PH) distribution, first introduced by M. F. Neuts [133,136]. The PH distribution then fits nicely into the Markov chain.

A popular approach in mapping a general probability distribution, , into a phase type (PH) distribution, , is to choose such that some moments of and agree. Matching the first moment of any nonnegative distribution is possible by a single exponential distribution. Matching the first moment is certainly important, but unfortunately it is often not sufficient, as ignoring the higher moments can result in misleading conclusions.

Thus, it is desirable to match more moments of the input distribution by . Matching more moments may be possible if we are allowed to use many exponential distributions (phases). However, the use of many phases in the PH distribution increases the complexity of the Markov chain, and makes its analysis hard. Matching many moments using a small number of phases may be possible if we are allowed to use unbounded computational resources or if we limit the class of input distributions. However, these limitations are not desirable. Achieving all the four desirable properties is the challenge in designing a moment matching algorithm:

- It is desirable that more moments of the input distribution, , and the matching PH distribution, , agree.
- It is desirable that have a small number of phases.
- It is desirable that the algorithm be defined for a broad class of input distributions.
- It is desirable that the algorithm have short running time.

- Overview

- Brief tutorial on phase type distributions
- Examples of PH distributions
- Definition of PH distribution
- Subclasses of PH distribution
- Properties of PH distributions

- State of the art in moment matching algorithms

- Characterizing phase type distributions
- EC distribution

- Simple closed form solution

- Complete closed form solution

- Positive closed form solution

- Concluding remarks