Ziele

Bei der Modellierung von realen Prozessen auf Basis von Traces gibt es zwei grundsätzliche Herangehensweisen. Es kann der gesamte Trace zur Anpassung verwendet werden oder es können Maßzahlen aus dem Trace extrahiert werden, die dann anschließend durch einen MAP möglichst genau wiedergegeben werden. Bei der Verwendung des vollständigen Traces wird sämtliche verfügbare Information genutzt. Durch die Maximierung der Likelihood-Funktion in EM-Algorithmen sind auch Algorithmen vorhanden, die diese Information nutzen. Praktisch ist ein solcher Ansatz aber nicht durchführbar, da heutige Traces aus Rechnernetzen mehrere Millionen Einträge beinhalten müssen, damit wirklich die relevanten Charakteristika adäquat abgebildet werden. Ein EM-Algorithmus der den gesamten Trace berücksichtigt muss in jeder Iteration den Wert der Likelihood-Funktion über sämtliche Einträge berechnen. Neben numerischen Problemen führt dies zu immensen Laufzeiten schon für eine Iteration. Die Alternative ist die Berechnung einzelner Maßzahlen aus dem Trace. Für die Verteilungsanpassung werden Momente und Werte der Verteilungsfunktion bzw. Quantile benutzt. Für die Darstellung der Korrelation findet im Wesentlichen die Anpassung des Autokorrelationskoeffizienten Anwendung. Bei diesem Vorgehen muss der Trace nur einmal durchlaufen werden, um die Maßzahlen zu berechen, nicht aber um die Parameter anzupassen.

Für die Verteilungsanpassung wurden Aggregierungsmethoden entwickelt, die die Zahl der Elemente in einem Trace deutlich verkleinern, ohne dessen Charakteristika zu verfälschen. Somit steht für die Verteilungsanpassung eine Methodik zur Verfügung, um die erforderliche Information aus einem Trace in kompakter Form darzustellen.

Anders ist die Situation bei der Anpassung von MAPs. Experimente zeigen, dass eine Anpassung der Autokorrelationskoeffizienten niedriger Ordnung nicht ausreicht. Es existieren auch keine Aggregierungsverfahren, bei denen sichergestellt ist, dass die Korrelationscharakteristika erhalten bleiben.

An Hand von vorhandenen Traces soll deshalb empirisch untersucht werden, welche Maßzahlen besonders geeignet sind, die Effekte der Korrelation zu beschreiben. Dazu sollen mit Hilfe Trace-getriebener Simulationen das Verhalten von Modellen untersucht werden, bei denen die realen Prozesse als Eingangsströme dienen. Anschließend werden dieselben Modelle mit MAPs betrieben, die einzelne Charakteristika des Traces anpassen. Es besteht die Hoffnung, dass auf diese Art, ähnlich wie bei der Verteilungsanpassung, relevante Maßzahlen definiert werden können und auch Aggregierungsansätze für Traces entwickelt werden können.

Es existiert inzwischen eine Vielzahl von Methoden zur Anpassung der Parameter eines MAPs an gemessene Daten. Bewährt hat sich die Idee Verteilungs- und Korrelationsanpassung in zwei Schritten durchzuführen: Die Formulierung als allgemeines Optimierungsproblem mit Nebenbedingungen und die sequentielle Anpassung von Verteilungs- und Korrelationsaspekten, sowie die Behandlung des Problems als multikriterielles Optimierungsproblem führten eindeutig zu besseren und effizienter auszuführenden Algorithmen, als bisher vorhanden.

Diese beiden Ansätze zur Anpassung von Verteilungs- und Korrelationseigenschaften für MAPs sollen in einem hybriden Algorithmus vereint werden. So erscheint es sinnvoll, erst in einigen Iterationsschritten beide Matrizen mit Hilfe von evolutionären Algorithmen zu modifizieren, um anschließend für eine Feinjustierung andere Optimierungsverfahren einzusetzen.

MAPs werden bisher primär in analytischen Modellen eingesetzt. Da sie aber das Potenzial haben, Korrelationen sehr gut abzubilden, bietet sich es an, sie auch in Simulationsmodelle zu integrieren. Dem stehen bisher die folgenden Probleme entgegen:

• Die Modellierungsmöglichkeiten der meisten Simulatoren beschränken sich darauf, verschiedene Verteilungen zur Verfügung zu stellen, so dass stochastische Prozesse nicht standardmäßig spezifiziert werden können.

• Die Parametrisierung von MAPs ist komplex und ihre manuelle Spezifikation der Prozesse ist aufwändig.

• Die seit langem bekannten stochastischen Prozesse wie autoregressive Prozesse werden von Spezialisten in der Simulation genutzt. Methoden zur Parameteranpassung solcher Prozesse sind aber selbst in verbreiteten Softwaretools zur Datenmodellierung für Simulationsmodelle wie ExpertFit oder dem Arena Input Analyzer nicht verfügbar. MAPs als neuere Entwicklung fanden bisher keine Beachtung und wurden nach unserem Wissen auch noch nicht mit autoregressiven Modellen vergleichen.

Ziel ist die Beseitigung der genannten Hindernisse beim Einsatz von MAPs in der Simulation. Außerdem soll eine Bewertung des Potenzials von MAPs im Vergleich zu anderen Prozessen erfolgen.

Eine der Stärken von MAPs liegt darin, dass die Überlagerung von MAPs und auch der Abgangsprozess von Bedienstationen mit MAP-Ankunftsprozess und MAP-Bedienzeitverteilung wieder ein MAP ist. Leider nimmt aber die Zustandszahl des resultierenden MAPs exponentiell mit der Zahl der betrachteten MAPs zu oder ist, wie im Fall von Bedienstationen mit unbeschränktem Warteraum, unendlich. Dies bedeutet, dass die resultierenden MAPs nicht mehr handhabbar sind. Ziel ist es, eine Methodik zu entwickeln, mit deren Hilfe Zustände eines MAPs so aggregiert werden können, dass der resultierende MAP untere oder obere Schranken für den Abgangsprozess liefert. Mit Hilfe einer speziellen partiellen stochastischen Ordnung für die Zustände eines Markov-Prozesses, kann sicher gestellt werden kann, dass ausgehend von einem stochastisch größerem Zustand alle transienten und stationären Leistungsgrößen mindestens so groß sind, wie die Leistungsgrößen, die ausgehend von einem stochastisch kleinerem Zustand erreicht werden. Wenn eine Menge von Zuständen durch den größten Zustand in der Menge ersetzt werden, so erreicht man ein stochastisch größeres Aggregat, werden alle Zustände durch den kleinsten ersetzt, so erhält man ein stochastisch kleineres Aggregat. Das Konzept wurde bisher für allgemeine interagierende Markov-Prozesse entwickelt und man kann zeigen, dass unter einschränkenden Bedingungen die Ordnung bei Komposition erhalten bleibt.

Bei der Anwendung auf MAPs ergeben sich einige Besonderheiten. So wird das Verhalten eines MAPs nicht durch seine Umgebung beeinflusst. Weiterhin ist man nur am Prozess interessiert, der durch den MAP generiert wird, nicht aber an der Zustandsverteilung des MAPs. Somit lassen sich die relativ restriktiven Bedingungen an die stochastische Ordnung aufweichen, wodurch sich ein größeres Potenzial aggregierbarer Zustände ergibt. Ergebnis einer solchen ordnungserhaltenden Aggregierung ist ein MAP, bei dem sichergestellt ist, dass innerhalb jedes Zeitintervalls mehr/weniger Ankünfte als mit dem Original-MAP erzeugt werden. Dies lässt sich formal dadurch nachweisen, dass der resultierende Abgangsprozess des aggregierten MAPs stochastisch kleiner/größer als der Abgangsprozess des ursprünglichen MAPs ist. Es bleibt dann zu zeigen, dass sich das System, welches den MAP als Eingangsprozess besitzt bei steigender Ankunftszahl monoton bzgl. der relevanten Leistungsgrößen verhält.

Bisher wurden einzelne Prozesse betrachtet, deren Zeitverhalten korreliert war. In manchen praktischen Anwendungen treten aber auch Korrelationen zwischen unterschiedlichen Größen auf. Beispiele sind die Korrelation von Zwischenankunftszeiten und Nachrichtengrößen in Rechnernetzen oder die Korrelation der Auftrittszeit von Fehlern und der Reparaturzeit. Für eine Modellierung solcher Zusammenhänge reichen einfache MAPs nicht aus, vielmehr müssen verschiedene MAPs verbunden werden. So besteht das einfachste Modell zur Berücksichtigung von Korrelationen zwischen Zwischenankunfts- und Bedienzeiten aus einer MAP/PH/1-Station, deren Bedienzeit von der Zwischenankunftszeit abhängt. Dies kann dadurch realisiert werden, dass die Phase des MAPs, aus der die Ankunft erfolgte, die Startverteilung der PH-Verteilung modelliert. Dieses Modell kann als ein System mit n Kundenklassen interpretiert werden, wobei jede Phase des MAPs, aus der eine Ankunft erfolgen kann, eine neue Klasse definiert. Modelle dieser Art sind mit Standardalgorithmen für MAP/PH/1-Modelle nicht analysierbar. Die spezielle Struktur des Modells erlaubt gleichwohl eine numerische Berechnung der Zustandwahrscheinlichkeiten. Der bisherige Analyseansatz lässt aber noch eine Reihe von Fragen offen. So werden algorithmische Aspekte bisher noch gar nicht berücksichtigt und es ist auch nicht klar, für welche Modellklassen sich die Analyse erweitern lässt, da der bisherige Ansatz nur einfache zeitdiskrete Modelle untersucht.

Es ist zu untersuchen, inwieweit sich effiziente Algorithmen zur Analyse von MAP/PH/1-Systemen auf Modelle mit korrelierten Zwischenankunfts- und Bedienzeiten übertragen lassen. Weiterhin ist zu untersuchen, für welche Modelle ein analytischer Analyseansatz basierend auf bekannten matrix-analytischen Methoden vorstellbar ist. Insbesondere ist dabei an Mehrbedienersysteme und Systeme mit endlichem Warteraum gedacht.

Überhaupt noch nicht behandelt wurde in der Literatur das Problem der Parametrisierung von korrelierten MAPs oder PH-Verteilungen. Zur Anpassung müssen Datenströme ermittelt werden, die jeweils mindestens zwei Werte pro Datum enthalten. So kann zum Beispiel die Zwischenankunftszeit und die Nachrichtengröße gemessen werden. Ziel der Parametrisierung ist es nun, einen MAP zu generieren, der die Zwischenankunftszeiten gut modelliert. Gleichzeitig muss eine PH-Verteilung (oder ein MAP) gefunden werden, die die Nachrichtengrößen modelliert. Der Zusammenhang zwischen Zwischenankunftszeit und Bedienzeitbedarf wird durch die Abhängigkeit der Startverteilung für die Bedienzeit von der Abgangsphase des Ankunfts-MAPs bestimmt. Auch dieser Zusammenhang ist zu modellieren. Auch wenn das Problem deutlich komplexer als die einfache Anpassung eines MAPs ist, so lassen erste Untersuchungen erahnen, dass die Methoden zur Parameteranpassung von MAPs erweiterbar sein sollten.

Approximation und Schrankenberechnung für Tandem und Fork-Join-Netze mit MAPs

Wenn MAPs als Prozesse in Modellen eingesetzt werden, so ist die Analysierbarkeit der resultierenden Modelle der zentrale Aspekt. Durch die so genannte Zustandsraumexplosion wächst die Größe des Zustandsraums kombinatorisch mit der Dimension der MAPs und PH-Verteilungen. Offene Systeme können nur in Form von einzelnen Stationen analysiert werden. Insofern besteht ein großer Bedarf daran, Warteschlangennetze mit nicht exponentiellen Bedien- und Ankunftszeiten zumindest approximativ zu analysieren. Es gibt zahlreiche Ansätze, die solche Verfahren behandeln. Dabei zeigt sich, dass die meist eingesetzten Dekompositionsverfahren sich insbesondere für Systeme ohne oder mit nur geringer Rückkoppelung eignen. Ein genereller Nachteil ist allerdings ein unbekannter Approximationsfehler.

Bei der Entwicklung neuer und verbesserter Methoden zur approximativen Analyse von Warteschlangennetzen mit MAPs und PH-Verteilungen sollen Tandem und Fork-Join-Netze im Mittelpunkt der Untersuchungen stehen.

In der zweiten Projektphase steht eine Erweiterung der in Phase 1 für MAPs entwickelten Methoden auf Rationale Ankunftsprozesse (RAPs) im Vordergrund. RAPs beschreiben eine Oberklasse der MAPs und lassen sich nicht mehr als Markov-Kette interpretieren. Aufgrund dieser fehlenden Interpretationsmöglichkeit ist es schwierig für Matrizen zu entscheiden, ob sie einen gültigen RAP beschreiben. Daher zielt die zweite Projektphase auf eine Charakterisierung von RAP Matrizen. Für MAPs lassen sich mit Hilfe von Lumpability und stochastischer Bisimulation Äquivalenzrelationen und Minimierungsalgorithmen definieren. Durch Untersuchung der Äquivalenz von MAPs und RAPs sollen ähnliche Relationen und Algorithmen auch für RAPs entwickelt werden. Für die Spezifikation von Markov Prozessen zur Leistungs- und Zuverlässigkeitsanalyse werden unter anderem Stochastische Automaten-Netze (SANs) genutzt. SANs sind ein kompositioneller Ansatz, der eine übersichtliche Beschreibung erlaubt und darauf basiert, dass die Komposition von Markov Prozessen in SANs wieder Markov Prozesse beschreibt. Es soll geprüft werden, inwiefern die Komposition von RAPs wieder in einem RAP resultiert, um so als Verallgemeinerung der SANs Rationale Automatennetze zur Modellierung nutzen zu können.

Um die praktische Einsetzbarkeit von RAPs zu erhöhen, sollen Algorithmen zur Parameteranpassung von RAPs entwickelt und in das existierende Toolkit ProFiDo integriert werden. Zur Analyse von Modellen mit RAPs sollen in diesem Zusammenhang auch Methoden zum Einsatz von RAPs in der Simulation und Algorithmen zur numerischen Analyse von Modellen mit RAPs entwickelt werden.