Computer Science Department - Technischen Universität München Chair for Efficient Algorithms

Internet Algorithmics: Routing Methods (SS 07)

• Lecturer:
  Dr. Sven Kosub

• Module: IN2154

• Area:
  4+2 lectures per week in area III (Theoretical Computer Science)
  advanced course, area algorithms

• Time and Place:
  Tuesday, 8:15-9:45, MI 00.04.011 (Hörsaal 2)
  Thursday, 12:15-13:45, MI 00.13.009A (Multimedia-Raum)

• Exercises:
  2 hours per week accompanying the lectures
  Thursday, 8:15-9:45, MI 03.11.018
  Teaching Assistant: Stefan Eckhardt
  

• Audience:
  graduate students of computer science
  students with computer science as minor
  

• ECTS: 8 points

• Prerequisites:
  1st and 2nd year courses
  course Efficient Algorithms and Data Structures I
  course Internet Protocols advantageous but not necessary
  course Internet Algorithmics: Analysis Methods advantageous but not necessary

• Recommended for:
  in-depth knowledge in topic Algorithms
  in-depth knowledge in topic Computer Networks

• Contents:

  Topics covered:

  1. Introduction

  2. Routing algorithms
     1. Complexity measures and models of distributed algorithms
     2. Fundamental distributed algorithms
        1. Leader election in rings
        2. Leader election in trees
        3. Breadth-first search
        4. Minimum spanning trees
     3. Broadcast and unicast routing
        1. Flooding algorithm
        2. Distance-vector algorithm
        3. Link-state algorithm
     4. Multicast routing

  3. Selfish routing
     1. Fundamental game theory
        1. Definitions and examples
        2. Best response
        3. Strategic equivalence
        4. Special games
        5. Mixed strategies
        6. Nash's theorem
     2. Potential games
     3. Congestion games
        1. Definitions
        2. Characterization by potential games
        3. Non-atomic congestion games
        4. Braess's paradox
        5. Coordination ratio

  4. Routing mechanisms
     1. Social choice functions
        1. Definitions
        2. Implementability
        3. Gibbard-Satterthwaite theorem
        4. Vickrey-Clarke-Groves mechanism
     2. Path auctions

• Related and Advanced Courses:
  Efficient Algorithms and Data Structures
  Computer Networks

• Lecture Notes:
  No lecture notes available.

• References:
  The course is based on recent research papers which are not yet contained in a textbook.

  In-depth and background material of certain course aspects can be found 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.

• Office Hours:
  look here