Paket-Scheduling in Switches
Üblicherweise werden in bestehenden Netzwerk-Switches alle Pakete gleich behandelt. Um beispielsweise mehrere Quality-of-Service-Level zu ermöglichen, ist es aber notwendig Paketen verschiedene Prioritäten zuweisen zu können. Da in Netzwerken das angefragte Übertragungsvolumen die vorhandenen Kapazitäten überschreiten kann, werden Paket-Schedulingstrategien für Switches benötigt, die die Prioritäten der Pakete berücksichtigen.
Eine erste Modellierung dieses Szenarios ist das folgende Online-Problem: In jedem Zeitschritt kann eine beliebige Anzahl von Paketen am Switch eintreffen, aber nur ein Paket kann gesendet werden. Ein FIFO-Puffer kann eine begrenzte Anzahl von Paketen zwischenspeichern. Wegen der FIFO-Eigenschaft des Puffers, ist die Sequenz der gesendeten Pakete eine Teilsequenz der empfangenen Pakete. Eine Schedulingstrategie kann Pakete aus dem Puffer löschen, um einen Überlauf des Puffers zu vermeiden. Dabei ist es das Ziel, die Summe der Prioritäten der weitergeleiteten Pakete zu maximieren.
Diese Problemstellung soll in der Diplomarbeit untersucht werden. Einerseits kann ein Schwerpunkt auf der Entwicklung und theoretischen Analyse von effizienten Schedulingstrategien liegen. Andererseits kann auch ein Schwerpunkt im Bereich Algorithm Engineering liegen. Dieses Thema kann auch im Rahmen eines Hiwi-Jobs bearbeitet werden.
Kontakt: Matthias Westermann