Modellierung und Analyse von Kommunikationsnetzen und Verteilten Systemen

Vorlesung + Übung, Wintersemester 2007/08

Modulbezeichnung: KTR-MAKV-M

Aktuelle Hinweise

• 14. Januar 2008: Das dritte Übungsblatt(33.9 KB) ist verfügbar.

Organisatorisches

• Termine:  Montag, 14-16 Uhr, F381; Freitag, 10-12 Uhr, F303

• Übung:  Im Schnitt 14-tägig (gemäß Ankündigung in der Vorlesung, je nach Bedarf)
  Die Veranstaltung ist als Einheit aus Vorlesung und Übung anzusehen.
  

• Dozent:  Dr. rer. nat. Werner Sandmann

Voraussetzungen

Interesse an formalen Methoden zur Leistungsbewertung von Computer- und Kommunikationssystemen, mathematische Grundlagenkenntnisse, keine Berührungsängste vor Stochastik.

Inhalt

Thema der Vorlesung ist die Leistungsbewertung von Computer- und Kommunikationssystemen (Rechnernetze, Verteilte Systeme,...), dem Titel entsprechend mittels (formaler, hauptsächlich stochastischer) Modellierung und Analyse.

Die Vorlesung beginnt mit einem einführenden Überblick über die modellgestützte Systemanalyse und der Bereitstellung der notwendigen stochastischen Grundlagen für die Leistungsbewertung. Die weitere Vorlesung gliedert sich in einen "Modellierungsteil" und einen "Analyseteil".

Im Modellierungsteil werden zunächst Warteschlangenmodelle und Petrinetze als wichtige Modellierungsparadigmen auf "hoher Abstraktionsebene" behandelt, gefolgt von Markovketten und deren Zusammenhang mit Warteschlangenmodellen und verallgemeinerten stochastischen Petrinetzen. Anschließend werden Verfahren zur Lastmodellierung erläutert, d.h. die adäquate Modellierung von Verkehrscharakteristika, Serviceanforderungen und leistungsrelevanten Systemeigenschaften.

Im Analyseteil wird zunächst die explizite algebraische Lösung elementarer Warteschlangensysteme behandelt, ggf. gefolgt von Algorithmen zur numerischen Analyse von Warteschlangennetzen. Den Abschluß bildet eine Einführung in die diskrete Simulation mit Schwerpunkt auf Verfahren zur Auswertung von Simulationsergebnissen sowie ggf. Varianzreduktionsverfahren zur Simulationsbeschleunigung  und zur Simulation seltener Ereignisse.

Unterlagen

Vorlesungsfolien werden vorlesungsbegleitend zur Verfügung gestellt.

Vorlesungsfolien bilden nur ein Gerippe. Sie dienen der Vortragsunterstützung und sind nicht als Skript anzusehen. Sie ersetzen insbesondere weder den Besuch der Vorlesung noch das Lesen von Begleitliteratur und sind allein nicht ausreichend für ein gutes Verständnis und die Fähigkeit der Anwendung des Vorlesungsstoffes.

1 Einführung(205.2 KB)
2 Modellierungsparadigmen(691.7 KB)
   2.1 Warteschlangenmodelle
   2.2 Stochastische Petrinetze
3 Stochastische Grundlagen (siehe Tafel und AWR)
   3.1 Wahrscheinlichkeitsräume
   3.2 Zufallsvariablen
   3.3 Verteilungen und Kenngrößen
4 Markovketten(443.4 KB)
   4.1 Grundlagen
   4.2 Diskrete Markovketten
         4.2.1 Grundbegriffe
         4.2.2 Klassifizierungen
         4.2.3 Absorbierende diskrete Markovketten
   4.3 Stetige Markovketten
         4.3.1 Grundbegriffe
         4.3.2 Klassifizierungen
         4.3.3 Stetige Phasenverteilungen
   4.4 Erzeugung von Markovketten
         4.4.1 Vom Warteschlangenmodell zur Markovkette
         4.4.2 Vom Petrinetz zur Markovkette
5 Lastmodelle(680.9 KB, 102 Seiten)
   5.1 Ankunftsprozesse
         5.1.1 Poissonprozesse
         5.1.2 Bernoulliprozesse
         5.1.3 Erneuerungsprozesse
   5.2 Auswahl einer Verteilungsfamilie
         5.2.1 Kenngrößen und Statistische Maßzahlen
         5.2.2 Graphische Darstellungen
   5.3 Parameterschätzung
         5.3.1 Grundbegriffe der Schätztheorie
         5.3.2 Maximum-Likelihood-Schätzer
         5.3.3 Momentenmethode
         5.3.4 Kleinste-Quadrate-Schätzer
   5.4 Anpassungstests
         5.4.1 Heuristische Methoden
         5.4.2 Grundbegriffe der Testtheorie
         5.4.3 Chi-Quadrat-Anpassungstest
         5.4.4 Kolmogorov-Smirnov-Test
   5.5 Ausblick auf Netzlastmodelle
         5.5.1 Netzverkehrscharakteristika
         5.5.2 Endlastige Verteilungen
         5.5.3 Schätzung von Extremwertindizes
6 Analyse elementarer Markovscher Modelle(276.8 KB)
   6.1 Geburts-/Todesprozesse
   6.2 Grundmodelle M/M/*
         6.2.1 M/M/1-Modell
         6.2.2 M/M/c-Modell
         6.2.3 M/M/infty-Modell
   6.3 Endliche Warteräume - Verlustsysteme
         6.3.1 M/M/1/K-Modell
         6.3.2 M/M/c/c-Modell
   6.4 Endliche Populationen
         6.4.1 M/M/c//m - Engset-Wartemodell
         6.4.2 M/M/c/c/m - Engset-Verlustmodell
7 Analyse elementarer nicht-Markovscher Modelle(136.4 KB)
   7.1 M/G/1-Modell
         7.1.1 Eingebettete Markovkette
         7.1.2 Stationäre Zustandswahrscheinlichkeitsverteilung
         7.1.3 Pollaczek-Khintchine-Formeln
   7.2 G/M/1-Modell und G/G/1-Modell

Übungsaufgaben

Blatt 1(25.2 KB) (Ausgabe: 02.11.07; Besprechung: 09.11.07)
Blatt 2(59.3 KB) (Ausgabe: 03.12.07; Besprechung: 10.12.07)
Blatt 3(33.9 KB) (Ausgabe: 14.01.08; Besprechung: 21.01.08)

Literatur

Die Vorlesung richtet sich nicht nach einem speziellen Buch. Aus der Vielzahl von Büchern zum Thema sind die folgenden als vorlesungsbegleitende und weiterführende Literatur besonders geeignet. Ausführliche Empfehlungen und Kommentare zur genannten Literatur werden in der Vorlesung gegeben.

Besonders empfohlene Bücher

• A. O. Allen: Probability, Statistics, and Queueing Theory with Computer Science Applications. Wiley, 1990.
• G. Bolch, S. Greiner, H. de Meer, K. S. Trivedi: Queueing Networks and Markov Chains. Wiley, 2nd edition, 2006
• A. M. Law, W. D. Kelton: Simulation Modeling and Analysis. McGraw-Hill, 3rd edition, 2000.
• R. Nelson: Probability, Stochastic Processes, and Queueing Theory. Springer, 1995.

Weitere empfehlenswerte Bücher

• S. Asmussen, P. W. Glynn: Stochastic Simulation. Springer, 2007.
• J. Banks, J. S. Carson, B. L. Nelson, D. M. Nicol: Discrete-Event System Simulation. Prentice Hall, 4th edition, 2005.
• G. Bolch: Leistungsbewertung von Rechensystemen. Teubner, 1989.
• R. B. Cooper: Introduction to Queueing Theory. North Holland, 1981. [ Buch in PDF ]
• B. R. Haverkort: Performance of Computer Communication Systems - A Model-Based Approach. Wiley, 1998.
  [ Vorversion  in PDF ]
• G. Kesidis: An Introduction to Communication Network Analysis. Wiley, 2007.
• P. J. B. King: Computer and Communication Systems Performance Modelling. Prentice Hall, 1990.
• L. Kleinrock: Queueing Theory, Volume I: Theory. Wiley, 1975.
• L. Kleinrock: Queueing Theory, Volume II: Computer Applications. Wiley, 1976.
• V. G. Kulkarni: Modeling and Analysis of Stochastic Systems. Chapman and Hall, 1995.
• H. C. Tijms: A First Course in Stochastic Models. Wiley, 2003.