Bilkent University
Department of Computer Engineering


Input Modeling with Markov Models


Peter Buchholz
Informatik IV
TU Dortmund, Germany

A key aspect in modeling many real world systems like computer or communication networks, manufacturing plants or dependable infrastructure is an adequate description of the system parameters and input processes which is often denoted as input modeling. Traditionally statistical distributions with a small number of parameters and simple stochastic processes are used for this purpose. For these models parameters can be easily determined from available data but the flexibility is usually limited such that many observed behaviors can only roughly be approximated. A further disadvantage is that the resulting models can only be analyzed with simulation, more efficient numerical analysis techniques are not usable in combination with general distributions or stochastic processes.

An alternative to the use of standard statistical distributions like Weibull or log-normal is the modeling of input processes by means of Markov chains with marked transitions. Markov processes with marked transitions are a versatile class of stochastic processes which allows one to approximate many real world behaviors arbitrarily close. Furthermore, Markov models are amenable for numerical solution techniques as an alternative to simulation. The major problem of Markov chain based input models is the complexity of the parametrization which is often denoted as parameter fitting and results normally in a constrained non-linear optimization problem. In the recent decade several new approaches for the parameter fitting of Markov models have been developed such that nowadays in many situations Markov models are a good alternative to other distributions or stochastic processes.

The talk introduces common Markov models for input modeling, like Phase Type Distributions and Markovian Arrival Processes, it describes the problem of parameter fitting and presents some algorithms. Furthermore, some examples are given where the approaches have been applied to real data and open research questions are outlined.


DATE: 25 August, 2014, Monday @ 13:40