Vorlesungstermine
| Wochentag |
Uhrzeit |
Hörsaal |
| Montag |
16:15-17:45 Uhr |
HG1-HS3 |
| Donnerstag |
14:15-15:45 Uhr |
HG1-HS3 |
Zum Inhalt der Vorlesung
Thema der Vorlesung sind Algorithmen für
Kommunikationsnetzwerke,
insbesondere beschäftigen wir uns mit Routingverfahren und
Datenmanagement. Im weiteren Sinne, geht es um die Frage, wie man
Möglichst effizient Daten durch ein Netzwerk transportieren kann.
Beim Routing geht es darum durch geschickte Wegewahl und geeignete
Schedulingentscheidungen Staus im Netzwerk zu
vermeiden, um Datenpakete möglichst schnell an ihr jeweiliges Ziel
zu bringen. Wir analysieren drei unterschiedliche Szenarien.
Zunächst untersuchen wir, wie man Routingpläne berechnet,
wenn man globales Wissen über das Kommunikationsnetzwerk und den
Kommunikationsbedarf hat. Danach gehen wir zu Modellen über in
denen kein globales Wissen über den Kommuikationsbedarf vorliegt,
so dass die Knoten im Netzwerk lokale Entscheidungen treffen
müssen. Zuletzt beschäftigen wir uns mit spieltheoretischen
Modellen, in denen einzelne Pakete oder auch Datenströme durch
egoistische Agenten geleitet werden, die nur danach streben, ihren
eigenen Nutzen zu maximieren. Beim Datenmanagement geht es darum Daten
so zu platzieren, dass benötigte Informationen schnell
verfügbar sind. Wir untersuchen verschiedene Aspekte, wie etwa die
bedarfsangepasste Allokation und Migration von Daten in
Parallelrechnern aber auch verteilte Datenstrukturen in Form von
sogenannten Overlaynetzwerke, die zur effizienten Such von Daten in
Peer-to-Peer-Netzwerken eingesetzt werden.
Der erste Teil der Vorlesung beschäftigt sich eher mit stark
strukturierten Netzwerken wie sie typischerweise in Parallelrechnern
vorzufinden sind. Wir folgen einem Skript von Friedhelm Meyer
auf der Heide, Universität Paderborn.
Skript Kommunikation in
parallelen Rechenmodellen (Teil
1) (Teil 2)
Wir werden uns vier von acht Kapiteln aus diesem Skript näher
anschauen.
Wir behandeln
- Kapitel 2: Permutationsrouting auf (n,d)-Gittern
- Kapitel 6: Oblivious Routing
- Kapitel 7: Das Multibutterfly-Netzwerk
- Kapitel 5: Simulation von Netzwerken
Diese Kapitel sind so schön geschrieben, dass ich sie nicht
neu
schreiben möchte.
Im zweiten Teil der Vorlesung wenden wir uns Themen zu, die eher
weniger strukturierte Netzwerke wie z.B. das Internet adressieren. Zur
Erläuterung der verwendeten Prinzipien und Konzepte werden wir in
einigen Fällen dennoch Bezug auf wohl-strukturierte Netzwerke
nehmen. Wir studieren die folgenden Themen.
Mission-Statement
Die Vorlesung hat den Anspruch nicht nur Lösungen
für
spezielle Probleme zu vermitteln, sondern elegante, mathematische
Techniken und Konzepte wie z.B. Hypergraphen, Expander, Delaysequenzen,
das Local-Lemma
oder Nash-Gleichgewichte vorzustellen, die von allgemeinerer Bedeutung
sind und auch in
vielen anderen Zusammenhängen angewendet werden können.
Die meisten der betrachteten Probleme sind praktisch motiviert,
wenngleich
nicht jeder Algorithmus, den wir vorstellen eins zu eins in die Praxis
umgesetzt werden kann, sondern die eine oder andere Adaption an die
praktischen Gegebenheiten erfordert. Unser Ziel ist nicht der
ingeneurmäßige
Entwurf von Algorithmen, Protokollen oder Netzwerken, sondern das
Verstehen
von fundamentalen Zusammenhängen in großen und komplexen
Netzwerken, dass
dann wiederum beim Entwurf von Algorithmen, Protokollen oder Netzwerken
sehr hilfreich sein kann.
Fachprüfungen und Leistungsnachweiss
DPO 96: Diese Veranstaltungen kann als 4-SWS-Vorlesung mit
einer anderen
2-SWS-Vorlesung in der Vertiefungsprüfung verwendet werden.
Alternativ
kann der Stoff der ersten Semesterhäfte als 2-SWS-Vorlesung mit
einer
anderen 4-SWS-Vorlesung kombiniert werden.
DPO 01: Über diese Veranstaltung kann im Schwerpunktgebiet
eine mündliche
Fachprüfung abgelegt werden. Ohne Einbeziehung der Übung in
den Prüfungsstoff erhält man 6 Leistungspunkte, mit
Einbeziehung der Übung 9 Punkte. Alternativ kann man einen
Leistungsnachweis über 6 bzw. 9 Punkte durch ein Fachgespräch
am Ende der Vorlesung erwerben.