Informatik-Logo
Fakultät für Informatik - Technische Universität München

Lehrstuhl für Effiziente Algorithmen

TUM-Logo

Hauptseminar im SS 2005:
Internet-Algorithmik

Donnerstag, 14 - 16 Uhr
im Seminarraum MI 03.11.018


[Themen & Literatur] [Vorträge] [Zusammenfassung] [Hinweise]

Nächster Vortrag am 07.07.2005 um 14:00 Uhr


Zusammenfassung

Für einen stabilen Internetbetrieb ist es wichtig, dass bestimmte systemkritische Aktivitäten besonders effizient und Ressourcen sparend durchgeführt werden. Dazu werden wir uns in diesem Hauptseminar speziell mit Routingaufgaben und verwandten Problemstellungen beschäftigen. Aus Sicht der Theoretischen Informatik werden u.a. Netzwerkalgorithmen (Broadcast, Unicast, Multicast Routing, QoS Routing etc.), Netzwerkmechanismen (Kürzeste-Wege-Auktionen, Effizienzverlust durch unkoordiniertes Verhalten etc.), Paketklassifikation und -filterung sowie Paketverfolgung behandelt und beurteilt.

Voraussetzung für die Teilnahme am Hauptseminar sind neben mathematischem Verständnis auch Englischkenntnisse, die zumindest ausreichend für die Bearbeitung der ausschließlich englischsprachigen Literatur sind.


Vorträge


Routingalgorithmen

9. Juni 2005 (um 14:00 Uhr) Raphael Geissler
Thema: Netzwerkalgorithmen: Broadcast, Unicast und Multicast Routing
Vorbesprechung: bis 13. Mai 2005
9. Juni 2005 (um 15:00 Uhr) Özcan Güzelarslan
Thema: QoS Routing: Konzepte, Optimalität und Komplexität
Vorbesprechung: bis 13. Mai 2005
16. Juni 2005 (um 14:00 Uhr) Alexander Klettner
Thema: Strategien zur Aufteilung von Multicast-Kosten
Vorbesprechung: bis 20. Mai 2005

Routingmechanismen

16. Juni 2005 (um 15:00 Uhr) Johannes Tiefenthaler
Thema: Algorithmische Implementierungstheorie
Vorbesprechung: bis 20. Mai 2005
06. Juli 2005 (um 15:00 Uhr) Guo Xinyi
Thema: Effizienzverlust durch unkoordiniertes Routing
Vorbesprechung: bis 17. Juni 2005

Paketmanagement

23. Juni 2005 (um 14:00 Uhr)
Roland Domagalski
Thema: Paketklassifikation
Vorbesprechung: bis 27. Mai 2005
30. Juni 2005 (um 14:00 Uhr)
Dimo Velev
Thema: Paketfilterung: Konzepte und Probleme
Vorbesprechung: bis 3. Juni 2005
30. Juni 2005 (um 15:00 Uhr)
Johannes Wust
Thema: Paketfilterung: Komprimierung von Routing-Tabellen
Vorbesprechung: bis 3. Juni 2005
6. Juli 2005 (um 14:00 Uhr) Sebastian Gaisbauer
Thema: Paketverfolgung
Vorbesprechung: bis 10. Juni 2005

Hinweise

Ein Schein für die erfolgreiche Teilnahme am Hauptseminar wird vergeben, wenn folgende Leistungen erbracht worden sind (die Gesamtnote setzt sich aus gewichteten Einzelnoten zusammen):

Probevortrag (ohne Bewertung) Der Probevortrag erfolgt spätestens zum angegebenen Termin beim Betreuer. Vorzulegen sind dabei die fertig ausgearbeiteten Folien oder ähnliche Präsentationshilfsmittel und die Erstfassung der Seminarbeit.
Vereinbaren Sie für den Probevortrag rechtzeitig einen Termin beim Betreuer (spätestens eine Woche vor dem anvisierten Termin).
Seminarvortrag (in mindestens zufriedenstellender Qualität) Der Seminarvortrag ist zum festgelegten Termin zu halten und dauert 45 (+/-5) Minuten. Tafelvorträge werden nicht akzeptiert. Nach dem Vortrag muss auf Fragen aus dem Publikum eingegangen werden.
Seminararbeit (in mindestens zufriedenstellender Qualität) Die Endfassung der Seminarbeit muss zum Zeitpunkt des Vortrags als TeX-Datei und Postscript-Datei abgegeben worden sein. Der Umfang der Seminararbeit beträgt 8 (+/- 1) Seiten (ohne Literaturverzeichnis) im LNCS-Style (Springer-Verlag) unter LaTeX (Hinweise siehe unten).

Ablauf der Vorbereitung

Der Vortrag und die Ausarbeitung müssen mit dem Betreuer abgesprochen werden. Hierzu sind nachfolgende Terminvorgaben bindend (soweit nicht anders mit dem Betreuer abgestimmt). Werden die Termine nicht eingehalten, führt dies zur Streichung des Vortrags und zum Nichtbestehen des Seminars:

bis 4 Wochen vor dem Vortragerstes Treffen mit dem Betreuer (vor dem Treffen ist die Literatur bereits zu lesen); die genauen Vortragstermine werden noch bekannt gegeben;
bis 2 Wochen vor dem VortragGliederung des Vortrags und der Ausarbeitung mit dem Betreuer besprechen;
bis 1 Woche vor dem VortragProbevortrag vor den Betreuer; fertige Folien und vollständige erste Version der Ausarbeitung mit dem Betreuer abstimmen;
bis 15. Juli 2005Abgabe der endgültigen Version der Ausarbeitung beim Betreuer.

Hinweise zur Anfertigung einer Seminararbeit

* Die Seminararbeiten werden nach der letzten Seminarveranstaltung gemeinsam in einem Seminarband zur Verfügung gestellt. Damit eine einheitliche Form erzielt wird, müssen alle Ausarbeitungen mit dem Textsatzsystem LaTeX erstellt werden. Hierzu sind folgende Richtlinien zu beachten:
  • Es ist der LNCS-Style (die Datei llncs.cls) des Springer-Verlages zu verwenden.
  • Der folgende Rahmen ist zu verwenden (seminararbeit.tex). Dabei dürfen die Seitengröße und der Font nicht verändert werden.
  • Ein Beispiel kann in der Datei example.tex gefunden werden (das Bild example.eps wird eingebunden)
  • Die Ausarbeitung soll auf die verwendete Literatur verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib).
* Bei Fragen zu LaTeX sei einerseits auf die folgenden Links hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden:
* Eine weitere Anleitung zur Erstellung von Ausarbeitungen finden sie hier.
* Informationen zur Installation von LaTeX unter Windows finden Sie hier.

Hinweise zur Gestaltung der Seminarvorträge

* Merkblatt zur Gestaltung eines Seminarvortrags. (Die Tipps auf diesem Merkblatt sind keine offiziellen Anforderungen oder Bewertungskriterien der TU München, sondern aus der Praxis eines Seminarleiters heraus entstandene Ratschläge.)
* Tipps zur Erstellung von Folien mit LaTeX (einschließlich Rahmen-Datei als Vorlage)


Weitere Auskünfte bei Sven Kosub.
Sven Kosub, February/11/2005.