Theorie und Anwendung des Restart-Verfahrens in verteilten, konkurrierenden Umgebungen

• Antragstellerin: Professorin Dr. Katinka Wolter
• Fachliche Zuordnung: Rechnerarchitektur, eingebettete und massiv parallele Systeme
• Förderung: Förderung von 2009 bis 2013
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 130260990

• Erstellungsjahr: 2013

Zusammenfassung der Projektergebnisse

Ziel dieses Forschungsprojektes war es, unter Verwendung verschiedener Methoden, herauszufinden, ob der Neustart von Jobs in einem verteilten System mit mehreren Teilnehmern zur Verbesserung der Leistung für jeden einzelnen Teilnehmer führt. Bei genauerer Betrachtung untergliederte sich dieses Problem in eine Vielzahl von Fällen und Möglichkeiten, die zum Teil unter Verwendung von analytischen Modellen, von Simulationen oder Experimenten im Testbett untersucht wurden. Dabei gab es sowohl Fehlschläge, wie auch erwartete und überraschende Erfolge und es wurden mehrere Werkzeuge entwickelt, die über das Projekt hinaus Anwendung finden. Im Laufe des Projektes und durch die Zusammenarbeit mit L. Kloul stellte sich heraus, daß keine Formulierung von PEPA-Modellen gefunden wurde, die nicht den gesamten Zustandsraum beschreibt. Aus Komplexitätsgründen wäre ein PEPA-Modell erforderlich, das nicht kombinatorisch den gesamten Zustandsraum erzeugt. Dies konnte mit den vorhandenen Mitteln nicht erreicht werden. Glücklicherweise stellte sich auch eine positive Fehleinschätzung heraus. In Zusammenarbeit mit J.-M. Fourneau konnte eine Klasse von G-Networks definiert werden, die sich zur Untersuchung von Restart eignet und Aussagen über die Anwendbarkeit von Restart und das optimale Restart-Intervall liefert. Mit der Anwendung des G-Networks-Formalismus konnte gezeigt werden, daß Restart in Warteschlangennetzwerken zu einer Verringerung der Last führen kann. Dieses Ergebnis wurde durch Simulationen bestätigt. Die Simulationen unterstützen, daß eine realistischere Modellierung als mit G-Networks möglich ist. Das Simulationswerkzeug SFERA wurde für das Projekt deutlich erweitert und an die Anforderungen der Fragestellung angepaßt. Mit SFERA können sehr viele verschiedene RestartSzenarien in Simulationen modelliert und untersucht werden. Das Simulationswerkzeug wurde in mehreren Publikationen verwendet. Das vorhandene SOA-Testbett wurde so erweitert, daß es zur Untersuchung von Restart mit mehreren Teilnehmern genutzt werden kann. Es wurden Modelle zur Injektion von Fehlern in das System entwickelt und implementiert. Dazu wurden Experimente in drahtlosen Netzwerken an der FU-Berlin durchgeführt. Die Untersuchung von Restart erfordert realitätsnahe Bedienzeitenverteilungen. Um die Charakteristika echter Bedienzeitenverteilungen, wie sie beispielsweise im Testbett gemessen werden, zu erfassen und in der Analyse und der Simulation wiederzugeben, wurden Phasentypverteilungen verwendet. Im Rahmen des Projektes wurden Methoden und Werkzeuge zur Anpassung von Phasentypverteilungen und zur effizienten Zufallszahlenerzeugung entwickelt. Neben den Aussagen zur Anwendbarkeit von Restart wurden mehrere Software-Werkzeuge zur Anpassung und Zufallszahlenerzeugung von Phasentypverteilungen, sowie zur Simulation komplexer Systeme mit Restart entwickelt. Die erstellten Werkzeuge finden in mehreren Projekten der Antragstellerin Verwendung.

Projektbezogene Publikationen (Auswahl)

• Cluster-based fitting of phasetype distributions to empirical data. Computers & Mathematics with Applications, 64(12):3840–3851, December 2012. Special Issue on Theory and Practice of Stochastic Modeling
  Philipp Reinecke, Tilman Krauß, and Katinka Wolter
  
• Efficient Generation of PH-distributed Random Variates. In Khalid Al-Begain, Dieter Fiems, and Jean-Marc Vincent, editors, 19th International Conference on Analytical and Stochastic Modelling Techniques and Applications (ASMTA’12), volume 7314 of Lecture Notes in Computer Science (LNCS), pages 271–285, Grenoble, France, 4–6 July 2012. Springer
  Gábor Horváth, Philipp Reinecke, Miklós Telek, and Katinka Wolter
  
• SFERA: A Simulation Framework for the Performance Evaluation of Restart Algorithms in Service-Oriented Systems. Electronic Notes in Theoretical Computer Science (2012)
  Danilkina, A., Reinecke, P., and Wolter, K.
  
• Multiple Class G-Networks with Restart. In Proceedings of ICPE 2013, Prague, April 2013. ACM
  Jean-Michel Fourneau, Katinka Wolter, Philipp Reinecke, Tilman Krauss, and Alexandra Danilkina