Fair-Queuing

Fair-Queuing (englisch für faires Einreihen) ist ein Netzwerk-Scheduling-Algorithmus. Das primäre Ziel beim Fair-Queuing ist die faire Behandlung der Quellen einer Übertragungskomponente, was dadurch erreicht werden kann, dass auf jeder Ausgangsleitung der Übertragungskomponente jedem Datenfluss (und damit jeder Quelle der Übertragungskomponente) eine eigene Warteschlange zugeordnet wird. Die Pakete der Warteschlangen werden nach dem Round-Robin-Verfahren entnommen und versendet. Auf diese Weise wird jede Quelle der Übertragungskomponente auf den gleichen Teil der Gesamtbandbreite der Ausgangsleitung eingeschränkt.

Ein Problem von Fair-Queuing ist, dass diejenigen Sender bevorzugt werden, welche lange Pakete senden, da das Versenden größerer Pakete mehr Zeit in Anspruch nimmt. Gelöst werden kann dieses Problem durch eine Erweiterung des Fair-Queuings: Fair-Queuing mit Byte-by-Byte-Round-Robin.

Ein zweites Problem ist, dass Fair-Queuing nicht die Priorität von Datenflüssen (von jeder Quelle gibt es einen Datenfluss) berücksichtigt. Manche Quellen haben nämlich eine höhere Priorität als andere bzw. manche Datenflüsse benötigen eine höhere Bandbreite als andere. Eine Lösung für dieses Problem ist die Erweiterung des Fair-Queuings zum Weighted-Fair-Queuing.

Fair-Queuing ist prinzipiell identisch zu Round-Robin, nur dass pro Quelle eine eigene Warteschlange gebildet wird.

Um die Fairness in Paket-basierten Netzen noch zu erhöhen (und dem Sender mit den größeren Paketen nicht mehr Bandbreite zuzuteilen), kommt folgendes Fair-Queuing für Paket-basierte Netze in Betracht:

Ein Paket n bekommt eine sogenannte Fertigstellungszeit F n {\displaystyle F_{\mathrm {n} }} zugewiesen. Diese berechnet sich nach der Formel

F n = m a x ( F n − 1 , t n ) + l n {\displaystyle F_{\mathrm {n} }=max(F_{\mathrm {n-1} },t_{\mathrm {n} })+l_{\mathrm {n} }}

wobei t n {\displaystyle t_{\mathrm {n} }} die Ankunftszeit des Pakets selbst und l n {\displaystyle l_{\mathrm {n} }} seine Länge ist. F n − 1 {\displaystyle F_{\mathrm {n-1} }} ist der Fertigstellungszeitpunkt des Vorgängers (derselben Quelle). Ist die Warteschlangen leer, kann mit der Übertragung des jeweiligen Pakets natürlich sofort begonnen werden. Ansonsten muss die Übertragung des Vorgängers abgewartet werden.

Das Verfahren lässt es demnach also zu, dass sich kürzere Pakete vor längere schieben können, denn z. B. ist Quelle Q1 mit 50 Byte großen Paketen im Abstand von 10 ms und Quelle Q2 mit 150 Byte großen Paketen in 10 ms folgendermaßen behandelt:

1. F(Q1,1) = max(0,0) + 50 = 50 (sofort übertragen, ist das 1. Paket in Warteschlange für Q1)
2. F(Q2,1) = max(0,0) + 150 = 150 (übertragen sobald Medium frei und virtuelle Zeit bei 1000 angekommen)
3. F(Q1,2) = max(10,50) + 50 = 100 (schiebt sich vor 2., siehe unten)
4. F(Q2,2) = max(10,150) + 150 = 300
5. F(Q1,3) = max(20,100) + 50 = 150 (schiebt sich vor 4., siehe unten)
6. F(Q2,3) = max(20,300) + 150 = 450

Übertragen würde dann in der Reihenfolge: 1. 3. 2. 5. 4. 6.

2. 5., da wir von First-Come-First-Served ausgehen

Zur Vereinfachung gehen wir davon aus, dass keine Daten übertragen wurden, sondern lediglich die Sendereihenfolge beachtet werden soll. Die Daten stauen sich quasi auf. Ansonsten könnte sich eine andere Paketreihenfolge (je nach Bandbreite) ergeben.

• Queuing-Techniken
• FIFO-Queuing
• Priority-Queuing
• Weighted-Fair-Queuing