Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Hauptseminar im SS 2002
Theoretische Grundlagen des Internets

Themen & Literatur

1. Kommunikation

• Tornado-Codes
  In vielen Netzwerken treten Informationsverluste durch Übertragungsfehler auf. Mit Kodierungen wird versucht, auftretende Fehler erkennbar und korrigierbar zu machen. In den folgenden Arbeiten werden Tornado-Codes eingeführt, die dies für informationsdichte und zeitkritische Szenarien auf extrem schnelle Weise realisieren, und deshalb z.B. beim Video-Streaming verwendet werden.
  
  1. M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, D. A. Spielman: Efficient Erasure Correcting Codes, IEEE Transactions on Information Theory, 47(2), 569-584, 2001.
  2. N. Alon, M. G. Luby: A Linear Time Erasure-Resilient Code With Nearly Optimal Recovery, IEEE Transactions on Information Theory, 42(6), 1732-1736, 1996.
• Virtual Private Networks
  Ein Virtual Private Network (VPN) ist ein Teilnetz eines größeren Netzes, in dem Daten verschlüsselt übertragen werden, und das insofern abgeschlossen gegenüber dem restlichen Netz ist. Die folgende Arbeit untersucht die optimale Bereitstellung von Leitungskapazitäten angesichts gegebener Kommunikationsanforderungen.
  
  1. A. Gupta, J. M. Kleinberg, A. Kumar, R. Rastogi, B. Yener: Provisioning a Virtual Private Network: A Network Design Problem for Multicommodity Flow, Proceedings 33rd ACM Symposium on Theory of Computing (STOC 2001), 389-398, 2001.
• Erkennung von Netzwerkfehlern
  Durch die Zerstörung einzelner Verbindungen zwischen Netzwerkknoten können ganze Regionen eines Netzwerkes voneinander abgeschnitten sein. Die folgende Arbeit studiert, wie das mittels weniger Kontrollpunkte (Agenten) erkannt werden kann.
  
  1. J. M. Kleinberg: Detecting a Network Failure, Proceedings 41st IEEE Symposium on Foundations of Computer Science (FOCS 2000), 231-239, 2000.
• Fraktales Netzverhalten
  Für Entwurf und Kontrolle von Netzwerken ist es wichtig, Vorhersagen über das Netzverhalten in den unterschiedlichen Schichten (z.B. Transport- oder Anwendungsschicht) treffen zu können. Die folgenden Arbeiten beschäftigen sich mit dem dabei im Internet (und Internet-artigen Netzwerken) auftretenden Phänomen der Selbstähnlichkeit des Netzverhalten.
  
  1. A. Feldmann, A. C. Gilbert, W. Willinger, T. G. Kurtz: The Changing Nature of Network Traffic: Scaling Phenomena, ACM SIGCOMM Computer Communication Review, 28(2), 1998.
  2. V. Paxson, S. Floyd: Wide Area Traffic: The Failure of Poisson Modeling, IEEE/ACM Transactions on Networking, 3(3), 226-244, 1995.
  3. W. E. Leland, M. S. Taqqu, W. Willinger, D .V. Wilson: On the Self-Similar Nature of Ethernet Traffic, IEEE/ACM Transactions on Networking, 2(1), 1-15, 1994.

• Verzögerte Bestätigung im TCP
  Im TCP-Protokoll muss die Ankunft von angekommenen Paketen bestätigt werden. Es ist jedoch möglich, mehrere Pakete der selben Quelle durch eine gemeinsame Nachricht zu bestätigen. Dabei soll die Verzögerung, die sich durch Warten auf weitere Pakete ergibt, sowie die Kosten durch mehrfache Bestätigungsnachrichten an die selbe Quelle vernünftig balanciert werden. Es ahndelt sich um eine typisches Online-Problem, da normalerweise nicht bekannt ist, wann ein Paket von der selben Quelle ankommen wird. Die beiden folgenden Arbeiten untersuchen dieses Problem aus algorithmischer Sicht.
  
  1. D. R. Dooly, S. A. Goldmann, S. D. Scott: On-Line Analysis of the TCP Acknowledgment Delay Problem, Journal of the ACM, 48(2), 243-273, 2001.
  2. A. R. Karlin, C. Kenyon, D. Randall: Dynamic TCP Acknowledgment and Other Stories about e/(e-1), Proceedings 33rd ACM Symposium on Theory of Computing (STOC 2001) , 502-509, 2001.
• Nachschlagen von IP-Adressen
  IP-Adressen sind hierarchisch organisiert. Um zu einer gegebenen Adresse den zuständigen Rechner zu finden, muss in einer Tabelle der längste vorhandene passende Adressenpräfix gefunden werden. Diese Operation muss extrem effizient ausgeführt werden.
  
  1. P. Crescenzi, L. Dardini, R. Grossi: IP Address Loopup Made Fast and Simple, Proceedings 7th Annual European Symposium on Algorithms (ESA 1999), Lecture Notes in Computer Science, 1643, 65-76, 1999, Springer-Verlag.
  2. G. Cheung, S. McCanne: Optimal Routing Table Design for IP Address Lookup Under Memory Constraints, Proceedings 18th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 1999), 3, 1437-1444, 1999.

• Bewertung von Web-Seiten für Suchmaschinen
  Für Suchmaschinen ist es wichtig, dass sie nicht nur einen großen Teil der relevanten Seiten als Ergebnis liefern, sondern auch die wichtigsten Seiten zuerst anbieten. Natürlich hängt die Wichtigkeit einer Seite von den Anforderung der anfragenden Personen ab und lässt sich deshalb nicht allgemein quantifizieren. Viele Suchmaschinen versuchen jedoch nicht nur das Vorkommen der Suchbegriffe in einer Seite (möglichst weit oben, möglichst nahe beieinander) zu bewerten, sondern auch noch ihre Autorität einfließen zu lassen. Die folgenden Arbeiten befassen sich mit dieser Fragestellung.
  
  1. J. M. Kleinberg: Authoritative Sources in a Hyperlinked Environment, Journal of the ACM, 46(5), 604-632, 1999.
  2. J. Dean, M. R. Henzinger: Finding Related Pages in the World Wide Web, Proceedings 8th International World Wide Web Conference (WWW8) , Computer Networks, 31(11-16), 1467-1479, 1999.
• Graphstrukur des Web
  Die folgenden Arbeiten beschäftigen sich mit der Link-Struktur des World Wide Web aus graphentheoretischer Sicht.
  
  1. J. M. Kleinberg: The Small-World Phenomenon: An Algorithmic Perspective, Proceedings 32nd ACM Symposium on Theory of Computing (STOC 2000) , 163-170, 2000.
  2. R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. S. Tomkins, E. Upfal: The Web as a Graph, Proceedings 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2000), 1-10, 2000.
• Web-Berechenbarkeit
  In der klassischen Berechenbarkeitstheorie wird davon ausgegangen, dass die Eingabe für eine Berechnung im Prinzip vollständig verfügbar ist, z.B. gegeben durch eine Zeichenkette. Berechnungen im Web beziehen jedoch die Link-Struktur der Web-Seiten ein und am Anfang einer Berechnung sind oft noch nicht alle benötigten Seiten bekannt. Die beiden folgenden Arbeiten betrachten die prinzipiellen Auswirkungen, die dieser Umstand auf die berechenbaren Funktionen hat.
  
  1. S. Abiteboul, V. Vianu: Queries and Computation on the Web, Theoretical Computer Science, 239, 231-255, 2000.
  2. A. O. Mendelzon, T. Milo: Formal Models of Web Queries, Information Systems, 23(8), 615-637, 1998.
• Verteilte Auswertung von Web-Queries
  Die folgende Arbeit definiert einen Rahmen zur Untersuchung der verteilten Auswertung von Anfragen an Web-Datenbanken, bei denen sich die Verteilung der Daten auf Web-Knoten erst durch die Auswertung der Anfrage ergibt.
  
  1. T. Jim, D. Suciu: Dynamically Distributed Query Evaluation, Proceedings 20th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS 2001), 28-39, 2001

• Automatische Datengenerierung aus HTML-Dokumenten
  Ein Großteil der Informationen im Web ist nicht inhaltlich strukturiert (z.B. als XML-Dokumente) sondern lediglich als HTML-Dokumente vorhanden. Die regelmäße Extraktion solcher Informationen aus Web-Seiten kann von so genannten Wrappern automatisch durchgeführt werden. Die Erstellung von Wrappern kann jedoch recht mühsam sein. Die folgenden Arbeiten beschäftigen sich mit der automatischen und halbautomatischen Erzeugung von Wrappern.
  
  1. N. Kushmerick: Wrapper Induction: Efficiency and Expressiveness, Artificial Intelligence, 118, 15-68, 2000.
  2. I. Muslea, S. Minton, C. A. Knoblock: Hierarchical Wrapper Induction for Semistructured Information Sources, Autonomous Agents and Multi-Agent Systems, 4, 93-114, 2001.
• Transformation von XML-Dokumenten
  In der folgenden Arbeit wird ein Automaten-Modell definiert und untersucht, mit dessen Hilfe sich Transformationen von XML-Dokumenten beschreiben lassen. Dieses Modell erfasst viele der Transformation, die mit gängigen XML-Sprachen wie etwa XML-QL und XSLT ausgedrückt werden können. Weiterhin wird das Modell in der Arbeit genutzt, um das Type-Checking-Problem für XML-Transformationen zu untersuchen.
  
  1. T. Milo, D. Suciu, V. Vianu: Typechecking for XML Transformers, Proceedings 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2000), 11-22, 2000.

Viele der Themen und Aufbereitungen entstammen der Ankündigung des gleichnamigen Seminars "Theoretische Grundlagen des Internets", das von Prof. Dr. Thomas Schwentick im WS 2001/2002 an der Philipps-Universität Marburg durchgeführt wurde, und dessen Unterlagen er dankenswerterweise zur Verfügung gestellt hat.