Netzalgorithmen - Interaktive Studienpläne der TU Ilmenau

Grundlegende Kenntnisse zu Netzwerken

• Fachkompetenz: Die Studierenden verstehen die gebräuchlichen Routingverfahren kennen die Notwendigkeit für eine bedarfsgerechte Aufteilung des Verkehrsaufkommens in Netzwerken. Sie können die verschiedenen Zielsetzungen beim Netzwerkentwurf voneinander abgrenzen und gegenüberstellen. Auf der Grundlage der Übung sind die Studierenden in der Lage, formale Beweise über die Korrektheit von Routing-Verfahren zu führen.
• Methodenkompetenz: Die Studierenden können grundlegende Entwurfs- bzw. Optimierungsprobleme als Multi-Commodity-Flow-Probleme formulieren. Sie sind auf der Grundlage der bearbeiteten Übungsaufgaben in der Lage, Multi-Commodity-Flow-Probleme in Standardformen zu überführen und durch Anwendung mathematischer Standardsoftware zu lösen.
  
• Systemkompetenz: Die Studierenden verstehen die Wechselwirkungen verschiedener Optimierungsziele beim Netzwerkentwurf und -betrieb.
  
• Sozialkompetenz: Auf der Grundlage der in der Vorlesung verwendeten metaphorischen Beispiele sind die Studierenden in der Lage, in den Übungen auch gesellschaftliche Sachzwänge (z.B. der fairen Vergabe von Ressourcen) im Kontext von Optimierungsverfahren durch Setzen entsprechender Zielfunktionen zu durchdenken, zwischen einzelnen Priotitätensetzungen (z.B. Gesamtdurchsatz vs. Fairness) abzuwägen und die vorgenommenen Priotitätensetzungen kritisch zu bewerten.

1. Einführung: Kommunikation in datagrammorientierten Netzwerken, Routingalgorithmen inklusive Korrektheitsbeweise, Modellierung von Datenverkehr mittels Poisson-Prozess, MM1 Wartesystem, Grundlegende Entwurfsprobleme in Netzwerken

2. Netzwerkmodellierung: Modellierung von Netzwerk-Design-Aufgaben als Multi-Commodity-Flow Probleme, Pure-Allocation-Problem, Shortest-Path-Routing, Fair Networks, Tunnel-Design in MPLS Netzwerken, Multilevel Netzwerke

3. Optimierungsmethoden:  Grundlagen der Linearen Optimierung, Simplexalgorithmus, Branch-and-Bound, Gomory-Schnitte, Branch-and-Cut

4. Netzwerkentwurf: Zusammenhang von Netzwerkentwurfsproblemen und mathematischer Modellierung in Standardform, kapazitierte Probleme, Pfaddiversität, Limited-Demand-Split, NP-Vollständigkeit von Single-Path-Allocation, Modular Flows, nichtlineare Zielfunktionen und Nebenbedingungen, Lösung von Problemen mit konvexen und konkaven Zielfunktionen bzw. Nebenbedingungen durch lineare Approximation

5. Network Resilience: Zusammenhangsmaße, Biconnected Components, Algorithmen zur Bestimmung der Blockstruktur von Graphen

Praktische Probleme und Protokollfunktionen in Kommunikationsnetzen und ihr algorithmischer Hintergrund.

Folien, Skripte

Michal Pioro, Deepankar Medhi. Routing, Flow, and Capacity Design in Communication and Computer Networks. The Morgan Kaufmann Series in Networking, Elsevier, 2004