Die Arbeitsgruppe "Betriebssysteme und Stochastische Modellierung"

Leitung

• Christoph Strelen

Schwerpunkte in Forschung und Lehre

• Betriebssysteme
• Modelle zur Bewertung der Leistung und Zuverlässigkeit von Rechen- und Kommunikationssystemen
• Simulation
• Parallele und verteilte Systeme

Forschungsprojekte 

Vertrauensintervalle bei stochastischer Simulation

Ein neuartiger Ansatz wurde verfolgt, mit dem sogenannte Min-Max-Vertrauensintervalle und, spezieller, Median-Vertrauensintervalle berechnet werden konnten. Sie haben einige Vorteile, verglichen mit klassischen Methoden: Sie sind besonders einfach zu berechnen, sind genauer, d.h. sie nehmen das nominelle Vertrauensniveau besser an, sie existieren bei einer größeren Klasse von Schätzfunktionen, deren Varianz braucht nicht zu existieren, bei Anordnungsstatistiken für Quantile sind sie präzise, unabhängig von der Wahrscheinlichkeitsverteilung.

Lastmodelle

In stochastischen Modellen wurden Einflüsse von außen auf das modellierte Teilsystem mit Lastmodellen erfaßt, die häufig aus stochstischen Prozessen bestehen, im einfachsten Falle Erneuerungsprozesse. Um sie zu identifizieren, werden zu gemessenen Daten passende Wahrscheinlichkeitsverteilungen oder stochstische Prozesse gesucht, und die Parameterwerden angepaßt. Klassisch dafür ist die Maximum-Likelihood-Methode, zu dieser Zeit wurden auch die Expectation-Maximization-Methode (EM) erprobt. In unserer Arbeitsgruppe wurden genetische Algorithmen auf ihre Nützlichkeit dazu untersucht.

Simulation seltener Ereignisse, steife Systeme

Für Modelle, in denen seltene Ereignisse wichtig sind, gab es keine etablierten Simulationsmethoden, die generell effizient sind. Die Arbeitsgruppe arbeitete am Importance Sampling, das seit langem bekannt ist, aber bei vielen Modellen nur mühsam erfolgreich eingesetzt werden konnte. Ein anderer verfolgter Ansatz benutzt unterschiedliche Zeitskalen, Markov-Modelle werden in langsame und schnelle Teilmodelle zerlegt, ähnlich wie bei dem Verfahren von Courtois für fast-vollständig zerlegbare Markovketten.

Universelle stochastische Modelle

Üblich zur Leistungsbewertung von Rechen- und Kommunikationssystemen sind Simulationsmodelle und analytische Modelle, letztere für formelmäßige oder numerische Auswertung, exakt oder näherungsweise. Es gibt Werkzeuge, mit denen Modelle spezieller Problemklassen dargestellt und analysiert werden können, simulativ oder analytisch-numerisch. Ziel dieses Projektes war eine einheitliche Darstellung von stochastischen Modellen für simulative, exakte numerische oder näherungsweise numerische Auswertung. Das Konzept dafür, genannt Übergangsklassen, ist für eine große Klasse von Modellen geeignet, die auf Markov-Ketten basieren. Ein Modell in dieser Darstellung, ein U-Modell, kann unmittelbar simuliert werden. Ist die Zustandsraumgröße im Bereich des Machbaren, kann es automatisch in eine Markov-Kette umgewandelt werden, die dann mit üblichen Methoden zu analysieren ist. Ist der Zustandsraum zu groß, kann es mit der DA-Methode, siehe unten, näherungsweise analysiert werden. Modelle der üblichen Klassen wie z.B. ganz allgemeine Warteschlangenmodelle oder erweiterte stochastische Petrinetze (GSPN) können automatisch in U-Modelle übersetzt werden. Somit stellen diese eine universelle Schnittstelle zwischen den verschiedenen verbreiteten Modell-Paradigma und den Analysemethoden dar.

Aggregationsmethoden für die Analyse von Markov-Modellen

Die vor einigen Jahren entwickelte Disaggregations-Aggregations-(DA-) Methode ist ein Näherungsverfahren für Modelle mit sehr vielen Zuständen. Dabei werden Partitionen des Zustandsraumes betrachtet und statt einzelner Zustandswahrscheinlichkeiten solche für die Teilmengen von Zuständen, sog. Makrowahrscheinlichkeiten. Für die Rechnung werden implizit jedoch auch die einzelnen Zustandswahrscheinlichkeiten benötigt. Bei der verfolgten Vorgehensweise werden sie mit Entropiemaximierung näherungsweise verfügbar gemacht.

Die DA-Methode eignet sich für zahlreiche interessante Markov-Modelle, deren Analyse bekanntermaßen schwierig ist. So konnten beispielsweise Blockiernetze, Fork-Join-Systeme und stochastische Petrinetze für Performability-Modelle damit behandelt werden. Die Methode wird weiterentwickelt, zum Beispiel für steife Systeme, also solche mit seltenen Ereignissen.