Efficient system evaluation using stochastic models

Abstract

Efficient and accurate methods are indispensible in the evaluation of complex systems. Methods of various abstraction levels may be applied, ranging from measurements in test-beds over simulation to analytical approaches. These methods vary in their efficiency and accuracy. In order to obtain realistic results, methods from all abstraction levels should be applied. Furthermore, real-world phenomena must be represented in a suitable way at all abstraction levels. This approach requires the use of stochastic models for the faults that may affect a system. This thesis explores several important issues of system evaluation using stochastic fault models. The first part of the thesis provides a survey of stochastic fault-models for system evaluation. We survey a broad range of existing fault-models and provide a new classification scheme for fault models in service-oriented systems. In the second part of the thesis we address the use of phase-type (PH) distributions as fault models in system evaluation. We study algorithms for random-variate generation and discuss their computational costs. An optimisation method for reducing the cost of random-variate generation by transformation of the representation is presented and an optimality result for the sub-class of acyclic phase-type distributions is derived. We then develop a new algorithm for efficient and user-friendly fitting of PH distributions to data sets using clustering. The algorithm is implemented as part of the HyperStar tool. We additionally illustrate application of HyperStar as a graphical user interface for prototype algorithms using a new algorithm for fitting general PH distributions. The third part illustrates application of the results from the first and second parts. We first study the application of stochastic fault models for IP packet loss in fault-injection and investigate the interaction between fault models and traffic arrival streams and its impact on evaluation results. We then describe a library for random-variate generation from phase-type distributions and show its use in two case-studies.

Die Evaluation komplexer Systeme erfordert effiziente und genaue Untersuchungsmethoden. Abhängig vom Abstraktionsniveau existieren unterschiedliche Verfahren, die Messungen in Testbetten ebenso umfassen wie Simulationen und analytische Ansätze. Die Verfahren unterscheiden sich hinsichlich ihrer Effizienz und der Genauigkeit der erzielbaren Ergebnisse. Für realistische Aussagen sollten in einer Evaluation immer Methoden ̈ aller Abstraktionsebenen kombiniert werden. Überdies sollten auf allen Ebenen Phänomene der echten Welt in die Untersuchung einfließen. Dies erfordert den Einsatz stochastischer Modelle für die Fehler, die das System beeinträchtigen können. In dieser Arbeit werden wichtige Aspekte der Systemevaluation mit stochastischen Fehlermodellen untersucht. ̈ Im ersten Teil der Arbeit wird eine Übersicht uber stochastische Fehlermodelle erarbeitet und ein neues Klassifikationsschema für Fehler in Service-Orientierten Systemen vorgestellt. Der zweite Teil der Arbeit konzentriert sich auf den Einsatz von Phasentypverteilungen als Fehlermodelle. Es werden Algorithmen zur Zufallszahlenerzeugung aus Phasentypverteilungen und ihre Kosten untersucht. Anschließend wird ein Verfahren vorgestellt, das Phasentypverteilungen so umformt, daß die Kosten der Zufallszahlenerzeugung minimiert werden. Für diesen Ansatz wird ein Optimalitätsresultat für die Unterklasse der azyklischen Phasentypverteilungen hergeleitet. Des weiteren wird ein auf Clustering basierender Algorithmus zur effizienten und nutzerfreundlichen Anpassung von Phasentypverteilungen an Datensätze entwickelt. Der Algorithmus wurde im Programm HyperStar implementiert. HyperStar kann überdies als graphische Benutzeroberfläche für dieEntwicklung von Fitting-Algorithmen dienen. Diese Verwendungsweise wird anhand eines neuen Algorithmus’ zur Anpassung allgemeiner Phasentypverteilungen demonstriert. Im dritten Teil werden die Ergebnisse des ersten und zweiten Teils in der Anwendung illustriert. Es wird zunächst die Anwendung stochastischer Fehlermodelle für IP-Paketverluste in der Fehlerinjektion untersucht. Der Schwerpunkt liegt hierbei auf der Wechselwirkung zwischen Fehlermodellen und Verkehrsankunftsströmen und ihrem Einfluß auf die Evaluationsergebnisse. Anschließend wird eine Bibliothek zur effizienten Zufallszahlenerzeugung in Simulationen vorgestellt und in einer Fallstudie evaluiert. Eine zweite Fallstudie demonstriert die mögliche Effizienzsteigerung durch den Einsatz von Phasentypverteilungen in Simulationen.