Rationale Ankunfts- und Bedienprozesse zur Leistungs- und Zuverlässigkeitsanalyse
Final Report Abstract
Zur Analyse der Leistung und Zuverlässigkeit von Systemen werden vielfach stochastische Modelle eingesetzt. In diesen Modellen werden Zeitverbräuche oft durch Zufallsverteilungen beschrieben, so dass die einzelnen Zeiten unabhängig und identisch verteilt sind. In der Praxis lassen sich dagegen häufig Korrelationen beobachten, welche bei Nicht-Berücksichtigung im Modell zu einer signifikanten Verfälschung der Analyseresultate führen. Markovsche und Rationale Ankunftsprozesse (MAPs/RAPs) sind zwei Klassen von Prozessen, welche die Modellierung korrelierter Größen erlauben und sowohl in analytischen als auch simulativen Modellen eingesetzt werden können. Haupthindernis für eine weitere Verbreitung dieser Prozesstypen sind Probleme, eine geeignete Parametrisierung zu finden. In diesem Projekt wurden neue Verfahren zur Parameteranpassung von MAPs und RAPs entwickelt und implementiert. Darüber hinaus wurden theoretische Resultate zur Charakterisierung dieser Prozesse und der Äquivalenz und Minimierung von Darstellungen der Prozesse erzielt. Bei der Parameteranpassung von MAPs lag der Schwerpunkt auf zweistufigen Verfahren, welche zuerst eine Phasenverteilung und dann darauf aufbauend, zur Modellierung der Korrelation, einen MAP anpassen. Implementierungen neu entwickelter und vorhandener Methoden wurden durchgeführt und in einer Toolumgebung, welche als Open-Source-Software frei zugänglich ist, verfügbar gemacht. Die Werkzeuge in der Toolumgebung erlauben neben der automatisierten Parametrisierung von MAPs, den Vergleich und die Bewertung der verschiedenen Methoden zur Parameteranpassung. Durch eine offene Architektur wird die Integration weiterer Verfahren unterstützt. Ein XML-Austauschformat erlaubt die Nutzung der angepassten MAPs in anderen Software-Paketen zur Leistungs- und Zuverlässigkeitsanalyse. Im Rahmen dieses Projektes wurde ein entsprechendes Modul für die freie Simulationsumgebung OMNeT++ erstellt. In der zweiten Projektphase lag der Schwerpunkt auf der Charakterisierung und Parameteranpassung von RAPs. Dieser Prozesstyp ist rein algebraisch definiert. Dies erschwert zwar die Interpretation des Verhaltens, erlaubt aber die Herleitung neuer theoretischer Resultate. So gelang es in Kooperation mit Kollegen der TU Budapest eine minimale Repräsentation für RAPs und MAPs herzuleiten und sogar einen Algorithmus zur Berechnung dieser Darstellung zu entwickeln. Ferner konnte gezeigt werden, dass RAPs, wenn sie in Modelle wie Warteschlangennetze oder stochastische Automatennetze eingebunden werden, zu einer speziellen Variante von stückweise deterministischen Markov-Prozessen führen, die sich numerisch effizient analysieren lässt. Neben den unten aufgeführten Ergebnissen ist im Rahmen des Projekts ein Buch entstanden, das den aktuellen Stand der Forschung zu Phasenverteilungen und MAPs zusammenfasst.
Publications
- A Comparison of Markovian Arrival and ARMA/ARTA Processes for the Modeling of Correlated Input Processes. Proc. of the Winter Simulation Conference (WSC) 2009, IEEE, 2009
F. Bause, P. Buchholz, J. Kriege
- A Heuristic Approach for Fitting MAPs to Moments and Joint Moments. Proc. of the 6th International Conference on Quantitative Evaluation of SysTems (QEST 2009), IEEE Computer Society, 2009
P. Buchholz, J. Kriege
- An Empirical Comparison of MAP Fitting Algorithms. Proc. of the 15th International GI/ITG Conference on Measurement, Modelling and Evaluation of Computing Systems and Dependability and Fault Tolerance (MMB & DFT 2010), Springer, 2010
J. Kriege, P. Buchholz
- Multi Class Markovian Arrival Processes and Their Parameter Fitting. Performance Evaluation, Volume 67, Issue 11, 2010
P. Buchholz, P. Kemper, J. Kriege
- ProFiDo - The Processes Fitting Toolkit Dortmund. Proc. of the 7th International Conference on Quantitative Evaluation of SysTems (QEST 2010), IEEE Computer Society, 2010
F. Bause, P. Buchholz, J. Kriege
- Bounding Reward Measures of Markov Models using Markov Decision Processes. Numerical Linear Algebra with Applications 18 (6), 2011, 919-930
P. Buchholz
- Correlated Phase-type distributed Random Numbers as Input Models for Simulations. Performance Evaluation, Volume 68, Issue 11, 2011
J. Kriege, P. Buchholz
- Numerical Analysis of Rational Processes - Beyond Markov Chains. Performance Evaluation 70 (9) , 2013, 646-662
P. Buchholz
- On Minimal Representations of Rational Arrival Processes. Annals of Operations Research 202 (1), 2013, 35-58
P. Buchholz, M. Telek
- Rational Automata Networks - A Non-Markovian Modeling Approach. INFORMS Journal on Computing 25 (1), 2013, 87- 101
P. Buchholz, M. Telek
- Approximate aggregation of Markovian models using alternating least squares. Performance Evaluation, Volume 73, 2014
P. Buchholz, J. Kriege
(See online at https://doi.org/10.1016/j.peva.2013.09.001) - Input Modeling with Phase-Type Distributions and Markov Models – Theory and Applications, Springer Briefs in Mathematics, 2014
P. Buchholz, J. Kriege, I. Felko
