Fakultät für Informatik - Technischen Universität München Lehrstuhl für Effiziente Algorithmen

Internet-Algorithmik: Routing-Methoden (SS 07)

• Dozent:
  Dr. Sven Kosub

• Modul: IN2154

• Bereich:
  4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
  Vertiefende Vorlesung im Bereich Algorithmen

• Zeit und Ort:
  Dienstag, 8:15-9:45, MI 00.04.011 (Hörsaal 2)
  Donnerstag, 12:15-13:45, MI 00.13.009A (Multimedia-Raum)

• Übung:
  2 SWS Übung zur Vorlesung
  Donnerstag, 8:30-10:00, MI 03.11.018
  Übungsleitung: Stefan Eckhardt
  

• Hörerkreis:
  Studierende im Hauptstudium der Informatik
  Studierende mit Nebenfach Informatik
  

• ECTS: 8 Punkte

• Voraussetzungen:
  Stoff des Informatik-Grundstudiums
  Vorlesung Effiziente Algorithmen und Datenstrukturen I
  Vorlesung Internetprotokolle vorteilhaft, aber nicht notwendig
  Vorlesung Internet-Algorithmik: Methoden der Analytik vorteilhaft, aber nicht notwendig

• Empfehlenswert für:
  Erweiterte Kenntnisse im Bereich Algorithmen
  Erweiterte Kenntnisse im Bereich Rechnernetze

• Inhalt:

  Behandelte Themen:

  1. Einleitung

  2. Routing-Algorithmen
     1. Komplexitätsmaße und Modelle verteilter Algorithmen
     2. Grundlegende verteilte Algorithmen
        1. Wahl des Anführers in Ringen
        2. Wahl des Anführers in Bäumen
        3. Breitensuche
        4. Minimale Spannbäume
     3. Broadcast und Unicast Routing
        1. Der Flooding-Algorithmus
        2. Der Distanzvektor-Algorithmus
        3. Der Link-State-Algorithmus
     4. Multicast Routing

  3. Nicht-kooperatives Routing
     1. Spieltheoretische Grundlagen
        1. Definitionen und Beispiele
        2. Die Beste-Antwort-Abbildung
        3. Strategische Äquivalenzen
        4. Spieltypen
        5. Gemischte Strategien
        6. Der Satz von Nash
     2. Potenzialspiele
     3. Auslastungsspiele
        1. Definitionen
        2. Charakterisierung durch Potenzialspiele
        3. Nichtatomare Auslastungsmodelle in Kostenform
        4. Das Paradoxon von Braess
        5. Das Koordinierungsverhältnis

  4. Routing-Mechanismen
     1. Soziale Entscheidungsfunktionen
        1. Definitionen
        2. Implementierbarkeit
        3. Der Satz von Gibbard und Satterthwaite
        4. Der Mechanismus von Vickrey, Clarke und Groves
     2. Pfadauktionen

• Weiterführende bzw. verwandte Vorlesungen:
  Effiziente Algorithmen und Datenstrukturen
  Internet-Algorithmik: Methoden der Analytik

• Skript:
  Kein Skriptum verfügbar.

• Literatur:
  Die Vorlesung verwendet viele aktuelle Forschungsarbeiten, die noch nicht in Buchform zusammengefasst sind.
  Vertiefendes und Hintergrundmaterial zu einzelnen Aspekten der Vorlesung findet sich in:
  • Michael T. Goodrich, Roberto Tamassia.
    Algorithm Design: Foundations, Analysis, and Internet Examples.
    John Wiley & Sons, Inc., Hoboken, NJ, 2002.

  • James F. Kurose, Keith W. Ross.
    Computernetze: Ein Top-Down-Ansatz mit Schwerpunkt Internet.
    Pearson Education, München, 2002.

  • Nancy A. Lynch
    Distributed Algorithms.
    Morgan Kaufmann, San Francisco, CA, 1996.

  • Martin J. Osborne, Ariel Rubinstein.
    A Course in Game Theory.
    The MIT Press, Cambridge, MA, 1994.

  • Walter Schlee.
    Einführung in die Spieltheorie. Mit Beispielen und Aufgaben.
    Vieweg, Braunschweig-Wiesbaden, 2004.

  • Andreu Mas-Collel, Michael D. Whinston, Jerry R. Green.
    Microeconomic Theory.
    Oxford University Press, Oxford, 1995.

• Sprechstunde:
  nach Vereinbarung