Network Algorithms - Interactive curriculae of TU Ilmenau

The interactive curriculae provide information on the degree programmes offered by the TU Ilmenau.

Please refer to the respective study and examination rules and regulations for the legally binding curricula (Annex Curriculum).

You can find all details on planned lectures and classes in the course catalogue.

Please note that this page is no longer updated. All modules and study plans from PO version 2021 onwards (Bachelor and Master study programs) are now available on the Campus Portal.

module properties Network Algorithms in degree program Master Ingenieurinformatik 2014
module number	200029
examination number	2200671
department	Department of Computer Science and Automation
ID of group	2253 (Telematics and Computer Networks)
module leader	Prof. Dr. Günter Schäfer
term	winter term only
language	Deutsch
credit points	5
on-campus program (h)	34
self-study (h)	116
obligation	elective module
exam	oral examination performance, 20 minutes
details of the certificate
link to Moodle course	https://moodle.tu-ilmenau.de/course/view.php?id=3672
teacher	Prof. Dr.-Ing. Günter Schäfer, Prof. Dr.-Ing. Thomas Böhme
signup details for alternative examinations
maximum number of participants
previous knowledge and experience	Grundlegende Kenntnisse zu Netzwerken
learning outcome	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.
content	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.
media of instruction and technical requirements for education and examination in case of online participation	Folien, Skripte
literature / references	Michal Pioro, Deepankar Medhi. Routing, Flow, and Capacity Design in Communication and Computer Networks. The Morgan Kaufmann Series in Networking, Elsevier, 2004
evaluation of teaching