Algorithmische Aspekte der Packet Routing im Internet

• Applicant: Professor Dr. Thomas Ottmann
• Subject Area: Theoretical Computer Science
• Term: from 2005 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 16236596

Effiziente Lösungen des IP-Lookup- und Paket-Klassifikations-Problems bilden eine kritische Komponente der Paketvermittlung im Internet. In diesem Projekt sollen neue Lösungen für diese Probleme gefunden werden. Dabei kommt es uns nicht nur auf die Verbesserung der asymptotischen Komplexität an, sondern auch darauf, einfache, leicht implementierbare Lösungen zu entwerfen, die sich für realistische Daten bewähren. Klassische Datenstrukturen, wie balancierte Bereichs-suchbäume, Segmentbäume und andere Strukturen, und Entwurfsmethoden, wie das Hinzufugen oder das Persistentmachen von Strukturen, sollen auf ihre Eignung zur Lösung der Probleme untersucht werden. Besonderes interessieren wir uns dafür, ob die gegebenenfalls auszuführenden Umstrukturierungs-Operationen für die benutzten Datenstrukturen von den Lookup-Operationen entkoppelt werden können und so eine Verbesserung der Klassifikationsleistung erreicht werden kann, ohne dass man mit zwei Strukturen, einer Haupt- und Schattenstruktur, arbeiten muss. In diesem Zusammenhang soll auch die Frage untersucht werden, wie man mit Bulk-Updates umgeht. Wir untersuchen das IP-Lookup und Paket-Klassifikations-Problem also aus Datenstruktursicht und betrachten es als zwei besonders wichtige Beispiele für Netzwerkprobleme, die mit Hilfe geeignet modifizierter Algorithmen und Datenstrukturen effizient gelöst werden können. Weitere Probleme dieser Art sind das sichere Multicast-Management von Schlüsseln, und das Routing in Ad-hoc-Netzen.

• DFG Programme: Priority Programmes
• Subproject of: SPP 1126: Algorithmics of Large and Complex Networks