DFG-Projekt
"Effiziente Algorithmen für die Ressourcenverwaltung in großen Netzwerken"
innerhalb des DFG-Schwerpunkts Nr. 1126
"Algorithmik großer und komplexer Netzwerke"
Zusammenfassung
1. Förderperiode
Der immense Erfolg, den große Netzwerke wie das Internet zu verzeichnen haben, basiert in erheblichem Maße darauf, dass große Datenmengen über weite Distanzen schnell und zuverlässig übertragen werden können. Eine solche Datenübertragung erfordert zum einen effiziente Netzwerkprotokolle und zum anderen, eng damit verknüpft, eine effektive Verwaltung der beteiligten Netzwerkkomponenten wie z.B. Netzwerkverbindungen, Router, Switches oder lokale Caches. Dabei entstehen zahlreiche neue algorithmische Probleme, deren Untersuchung Gegenstand dieses Projekts ist. Ziel dieses Forschungsvorhabens ist die gründliche Bearbeitung wichtiger algorithmischer Probleme, die im Zusammenhang mit Netzwerkprotokollen bzw. bei der Verwaltung von Netzwerkkomponenten auftreten. Es entstehen die folgenden Arbeitspunkte: (1) Identifikation und präzise Modellierung der Probleme, (2) Analyse bestehender Lösungen, (3) Entwicklung von verbesserten Algorithmen mit einem beweisbar guten Verhalten und (4) Durchführung von Experimenten.
2. Förderperiode
Gegenstand dieses Forschungsprojekts ist die algorithmische Untersuchung zentraler Probleme, die bei der Ressourcenverwaltung in großen Netzwerken entstehen. Aufbauend auf unseren Arbeiten aus der ersten Förderungsperiode dieses Projekts werden wir sowohl hardware- als auch protokollorientierte Probleme untersuchen. Auf Hardwareebene hängt die Performanz essentiell von Routern und Switches ab, die Datenpakete zu ihrer korrekten Zieladresse leiten. Hier werden wir an verschiedenen fundamentalen Paketpufferungsstrategien arbeiten, die den Paketverlust minimieren. Auf Protokollebene möchten wir an der Entwicklung von Broadcast-Strategien arbeiten, die unter verschiedenen Zielfunktionen einen garantierten Quality-of-Service erreichen. Durch die wachsende zur Verfügung stehende Bandbreite in Netzwerken werden Datenübertragungen oftmals nicht mehr durch Punkt-zu-Punkt-Transfers sondern Broadcasts realisiert. Generelles Ziel dieses Forschungsvorhabens ist die Entwicklung von Algorithmen, die einfach genug sind, dass sie in der Praxis eingesetzt werden können, und gleichzeitig ein beweisbar gutes Verhalten aufweisen. Unsere theoretischen Ergebnisse sollen durch Experimente auf realen Datentraces ergänzt werden.
Mitarbeiter
- Susanne Albers
- Markus Schmidt
- Sylva Scholz
Publikationen
- S. Albers and M. Schmidt. On the performance of greedy algorithms in packet buffering. In Proc. 36th ACM Symposium on Theory of Computing (STOC04), 35-44, 2004.
- S. Albers. New results on web caching with request reordering. In Proc. 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA04), 84-92, 2004.
- M. Schmidt. Packet buffering: Randomization beats deterministic algorithms. In Proc. of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS05), Springer LNCS 3403, 2004.