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

Internet Algorithmics (WS 06/07)

• Lecturer:
  Prof. Dr. Ernst W. Mayr
  Dr. Sven Kosub

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

• Time and Place:
  Wednesday, 16:00-17:30, MI 00.04.011 (Hörsaal 2)
  Friday, 12:15-13:45, MI 00.04.011 (Hörsaal 2)

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

• ECTS: 6 points

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

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

• Contents:
  
  1. Introduction
  1. Internet analysis
  2. Analyzing data
  1. Algorithms on texts
     1. Definitions and notations
     2. A simple algorithm for exact pattern matching
     3. Knuth-Morris-Pratt algorithm
     4. Boyer-Moore algorithm
     5. Galil's extension of the Boyer-Moore algorithm
     6. Aho-Corasick algorithm
  2. Algorithms on data streams
     1. Processing models and complexity measures
     2. One-pass algorithms for hot-list analysis
     3. Hot-list analysis using two passes
     4. Exact algorithms for frequency-moment analysis
     5. Alon-Matias-Szegedy sampling algorithm
  3. Algorithms on monitors
     1. Processing models
     2. Exponential histograms
     3. Waves
  4. Case study: IP packet classification
  1. Longest prefix matching
  2. Unibit tries
  3. Multibit tries
  4. Prefix automata
  3. Analyzing networks
     1. Dimensioning and locating monitor systems
        1. Separators and detectors
        2. A simple analysis for edge connectivity
        3. Kleinberg's technique for edge connectivity
        4. Extensions of Kleinberg's technique
     2. Reconstructing network topologies
        1. Graph realizations of degree sequences
        2. Gale-Ryser theorem
        3. Havel-Hakimi algorithm
        4. Graph realizations of distance matrices
        5. Graphical matrices
        6. Culberson-Rudnicki algorithm
     3. Case study: Inter-domain routing with BGP
     1. An abstract model for BGP
     2. Combinatorial type-of-relationship inference

  Further topics:

  2. Managing the Internet efficiently
  3. Content delivery on the Internet
  4. Information retrieval on the Internet
  5. Internet privacy and security

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

• Lecture Notes:
  Lecture notes will be produced in parallel with the lectures.

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

  A nice survey (and new results) on approaches to IP packet classification can be found in the following thesis:

  • Benjamin Hummel.
    Automata-based IP Packet Classification.
    Diplomarbeit, Fakultät für Informatik, Technische Universität München, 2006.

• Office Hours:
  look here