Algorithmische Aspekte der Packet Routing im Internet

• Antragsteller: Professor Dr. Thomas Ottmann
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2005 bis 2010
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 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-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1126: Algorithmik großer und komplexer Netzwerke