Head-of-Line-Blocking

Abkürzung: HOL

Was ist Head-of-Line-Blocking?

Head-of-Line-Blocking, abgekürzt HOL-Blocking, beschreibt einen Zustand in Netzwerk-Switches, bei dem ein wartendes Datenpaket am Anfang einer Warteschlange die Weiterleitung aller dahinter stehenden Pakete verhindert. Der Name leitet sich vom Bild einer Schlange ab: Solange der Kopf der Schlange nicht bedient werden kann, müssen alle Nachfolgenden warten, selbst wenn sie ein freies Ziel hätten. Das Phänomen betrifft vor allem Input-gepufferte Switches und führt zu einer drastischen Verschlechterung des maximalen Durchsatzes sowie zu unnötig hohen Latenzen.

Ursache: Input-Queues und das FIFO-Prinzip

In einfachen Switch-Architekturen besitzt jeder Eingangsport eine gemeinsame First-In-First-Out-Warteschlange (FIFO). Eintreffende Pakete werden in der Reihenfolge ihres Eingangs in diese Queue eingereiht. Der Switch verarbeitet sie streng sequenziell. Das Problem entsteht, wenn das vorderste Paket für einen Ausgangsport bestimmt ist, der momentan belegt ist. Das Paket kann nicht vermittelt werden und blockiert die gesamte Queue. Alle nachfolgenden Pakete in derselben Warteschlange müssen warten, obwohl ihre Zielports längst frei sein könnten und sie sofort weitergeleitet werden könnten.

Ein anschauliches Beispiel

Port 1 empfängt nacheinander drei Pakete: Das erste ist für Port 3, das zweite für Port 4 und das dritte für Port 5. Port 3 ist zu diesem Zeitpunkt durch eine große Datenübertragung belegt. Port 4 und Port 5 sind frei. Weil die Eingangs-Queue nach dem FIFO-Prinzip arbeitet, steht das für Port 3 bestimmte Paket ganz vorne und blockiert. Der Switch kann es nicht zustellen, also wartet es. Die dahinter liegenden Pakete für Port 4 und Port 5 müssen ebenfalls warten, obwohl ihre Ziele sofort verfügbar wären. Das Blocking entsteht allein durch die gemeinsame Nutzung einer einzigen Warteschlange pro Eingangsport.

Folgen für den Datendurchsatz

Die Auswirkungen von Head-of-Line-Blocking sind gravierend. Bereits unter moderater Last kann der nutzbare Durchsatz eines Input-gepufferten Switches auf etwa 58 Prozent der theoretischen maximalen Kapazität einbrechen. Dieser Wert wurde in der klassischen Analyse von Karol, Hluchyj und Morgan für gleichverteilten Verkehr ermittelt. Bei asymmetrischen Verkehrsmustern und Hotspots kann der Durchsatz noch weiter sinken. Die vergeudete Kapazität bedeutet verschwendete Bandbreite, höhere Latenzen für unschuldige Pakete und eine ungleichmäßige Dienstgüte über alle Ports hinweg.

Abgrenzung: Output-gepufferte und Shared-Memory-Switches

Head-of-Line-Blocking ist ein spezifisches Problem Input-gepufferter Architekturen. Reine Output-gepufferte Switches kennen dieses Problem nicht, da dort die Warteschlangen direkt am Zielport liegen und ein Eingangsport keinen Einfluss auf die Weiterleitung anderer Pakete hat. Allerdings sind Output-gepufferte Architekturen teurer und benötigen eine interne Übertragungsgeschwindigkeit, die ein Vielfaches der einzelnen Portgeschwindigkeiten beträgt. Shared-Memory-Switches puffern alle eingehenden Pakete in einem gemeinsamen Speicher und können flexibel auslesen, ohne dass ein Port den anderen blockiert. Sie sind jedoch durch die Speicherbandbreite und -größe limitiert.

Lösung: Virtual Output Queuing (VOQ)

Die wirksamste und am weitesten verbreitete Gegenmaßnahme ist Virtual Output Queuing. Anstatt einer einzigen FIFO-Queue pro Eingangsport unterhält der Switch für jeden Ausgangsport eine separate logische Warteschlange am Eingang. Ein eintreffendes Paket wird sofort in die Queue einsortiert, die seinem Zielport entspricht. Der Scheduler des Switches überblickt alle VOQs und entscheidet in jedem Zeitschlitz, welche Pakete an die Ausgangsports weitergeleitet werden können. Ein belegter Zielport blockiert nur noch die ihm zugeordnete virtuelle Queue. Pakete für andere, freie Zielports in anderen Queues bleiben davon unberührt und werden planmäßig zugestellt.

Scheduling und Matching

Der Einsatz von VOQ erfordert einen zentralen Scheduler, der in jedem Übertragungsintervall eine Zuordnung zwischen Eingangs- und Ausgangsports berechnet. Diese Matching-Problemstellung ähnelt dem Finden einer maximalen Paarung in einem bipartiten Graphen. Praktisch eingesetzte Algorithmen sind das Parallel Iterative Matching (PIM) oder das iSLIP-Verfahren. Sie versuchen, in möglichst wenigen Iterationen eine konfliktfreie Zuordnung zu finden, die einen hohen Durchsatz gewährleistet und Fairness zwischen den Ports sicherstellt.

VOQ in modernen Switches

Moderne Hochgeschwindigkeits-Ethernet-Switches und Router setzen praktisch durchgängig auf VOQ-Architekturen, um Head-of-Line-Blocking an den Eingängen zu verhindern. Auch bei der Implementierung von Quality of Service und mehreren Prioritätsstufen wird VOQ ausgebaut, indem pro Zielport und Priorität eine eigene virtuelle Queue existiert. So bleibt sichergestellt, dass ein priorisiertes Sprachpaket nicht hinter einem großen Datenpaket für denselben Zielport warten muss.

Andere Formen von Head-of-Line-Blocking

Der Begriff Head-of-Line-Blocking beschränkt sich nicht nur auf Input-Queues in Switches. Das gleiche Phänomen tritt bei jeder Art von sequenzieller Warteschlange auf, etwa bei HTTP/1.1-Verbindungen, wo Anfragen über eine einzelne TCP-Verbindung der Reihe nach abgearbeitet werden müssen, oder in Festplatten-Controllern mit einfachen Befehlswarteschlangen. In der Netzwerktechnik ist das klassische HOL-Blocking der Switches jedoch das prominenteste und am besten untersuchte Beispiel.

Zusammenfassung und Praxisrelevanz

Head-of-Line-Blocking reduziert die Effizienz von Netzwerk-Switches erheblich und kann im Worst Case mehr als 40 Prozent der theoretischen Kapazität ungenutzt lassen. Durch den Einsatz von Virtual Output Queuing und intelligentem Scheduling lässt sich das Problem architektonisch vollständig lösen. Für Planung und Betrieb von Rechenzentren, Carrier-Netzen und leistungsfähigen Unternehmensnetzen ist das Verständnis von HOL-Blocking eine wichtige Voraussetzung, um die richtige Switch-Architektur auszuwählen und Engpässe zu vermeiden.