Universität Bonn
Institut für Informatik IV
Prof. Strelen

Arbeitsgruppe "Betriebssysteme und Stochastische Modellierung"


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 wird verfolgt, mit dem sogenannte Min-Max-Vertrauensintervalle und, spezieller, Median-Vertrauensintervalle berechnet werden können. 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 werden 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, neuerdings erprobt man auch die Expectation-Maximization-Methode (EM). In unserer Arbeitsgruppe werden genetische Algorithmen auf ihre Nützlichkeit dazu untersucht.

Simulation seltener Ereignisse, steife Systeme

Für Modelle, in denen seltene Ereignisse wichtig sind, gibt es keine etablierten Simulationsmethoden, die generell effizient sind. Die Arbeitsgruppe arbeitet am Importance Sampling, das seit langem bekannt ist, aber bei vielen Modellen nur mühsam erfolgreich eingesetzt werden kann, wenn überhaupt. 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 ist 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 weden. 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 in den letzten 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.


6.7.2004 - strelen@informatik.uni-bonn.de/15.01.01 feldt@informatik.uni-bonn.de