- Fair-Queuing
-
Fair-Queuing (engl. "faires Einreihen") ist eine geläufige Technik, um Datenstaus bzw. Überlast in Übertragungskomponenten wie Routern zu vermeiden.
Das primäre Ziel beim Fair-Queuing ist die faire Behandlungen der Quellen einer Übertragungskomponente. Deshalb wird das Verfahren auch »Fair« genannt.
Fair-Queuing funktioniert nach folgendem Prinzip: Auf jeder Ausgangsleitung der Übertragungskomponente wird jedem Datenfluss (und damit jeder Quelle der Übertragungskomponente) eine eigene Warteschlange zugeordnet. 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 einschränkt.
Inhaltsverzeichnis
Nachteile
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-Queueing mit Byte-by-Byte-Round-Robin
Fair-Queueing 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-Queueing für Paket-basierte Netze in Betracht:
Ein Paket n bekommt eine sogenannte Fertigstellungszeit Fn zugewiesen. Diese berechnet sich nach der Formel
- Fn = max(Fn − 1,tn) + ln
wobei tn die Ankunftszeit des Pakets selbst und ln seine Länge ist. Fn − 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 muß die Übertragung des Vorgängers abgewartet werden.
Beispiel
Das Verfahren lässt es demnach also zu, daß 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, daß 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.
Siehe auch
Kategorie:- Rechnernetze
Wikimedia Foundation.
