Technische Universität Ilmenau

Netzalgorithmen - Modultafeln der TU Ilmenau

Die Modultafeln sind ein Informationsangebot zu den Studiengängen der TU Ilmenau.

Die rechtsverbindlichen Studienpläne entnehmen Sie bitte den jeweiligen Studien- und Prüfungsordnungen (Anlage Studienplan).

Alle Angaben zu geplanten Lehrveranstaltungen finden Sie im elektronischen Vorlesungsverzeichnis.

Informationen und Handreichungen zur Pflege von Modulbeschreibungen durch die Modulverantwortlichen finden Sie unter Modulpflege.

Hinweise zu fehlenden oder fehlerhaften Modulbeschreibungen senden Sie bitte direkt an modulkatalog@tu-ilmenau.de.

Modulinformationen zu Netzalgorithmen im Studiengang Master Informatik 2021
Modulnummer200029
Prüfungsnummer2200671
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2253 (Telematik/ Rechnernetze)
Modulverantwortliche(r)Prof. Dr. Günter Schäfer
TurnusWintersemester
SpracheDeutsch
Leistungspunkte5
Präsenzstudium (h)34
Selbststudium (h)116
VerpflichtungPflichtmodul
Abschlussmündliche Prüfungsleistung, 20 Minuten
Details zum Abschluss
Alternative Abschlussform aufgrund verordneter Corona-Maßnahmen inkl. technischer Voraussetzungen
Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl
Vorkenntnisse

Grundlegende Kenntnisse zu Netzwerken

Lernergebnisse und erworbene Kompetenzen
  • 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.
Inhalt

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.

Medienformen und technische Anforderungen bei Lehr- und Abschlussleistungen in elektronischer Form

Folien, Skripte

https://moodle2.tu-ilmenau.de/course/view.php?id=2859

Literatur

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

Lehrevaluation