imported>PerfektesChaos: tk k

2025-06-18T21:36:50Z

tk k

Neue Seite

'''Fair-Queuing''' ({{enS}} für ''faires Einreihen'') ist ein [[Netzwerk-Scheduler|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 (Datenstruktur)|Warteschlange]] zugeordnet wird. Die Pakete der Warteschlangen werden nach dem [[Round Robin (Informatik)|Round-Robin-Verfahren]] entnommen und versendet. Auf diese Weise wird jede Quelle der Übertragungskomponente auf den gleichen Teil der [[Bandbreite|Gesamtbandbreite]] der Ausgangsleitung eingeschränkt.

== Nachteile ==
Ein Problem von Fair-Queuing ist, dass diejenigen [[Absender|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 [[Datenfluss|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 [[Datenfluss|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 mit Byte-by-Byte-Round-Robin ==
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 <math>F_\mathrm{n}</math> zugewiesen. Diese berechnet sich nach der Formel

: <math>F_\mathrm{n} = max(F_\mathrm{n-1}, t_\mathrm{n}) + l_\mathrm{n}</math>

wobei <math>t_\mathrm{n}</math> die Ankunftszeit des Pakets selbst und <math>l_\mathrm{n}</math> seine Länge ist. <math>F_\mathrm{n-1}</math> 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.

== Beispiel ==
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:

# F(Q1,1) = max(0,0) + 50 = 50 (sofort übertragen, ist das 1. Paket in Warteschlange für Q1)
# F(Q2,1) = max(0,0) + 150 = 150 (übertragen sobald Medium frei und virtuelle Zeit bei 1000 angekommen)
# F(Q1,2) = max(10,50) + 50 = 100 (schiebt sich vor 2., siehe unten)
# F(Q2,2) = max(10,150) + 150 = 300
# F(Q1,3) = max(20,100) + 50 = 150 (schiebt sich vor 4., siehe unten)
# 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.

== Siehe auch ==
* [[Scheduling|Queuing-Techniken]]
* [[FIFO|FIFO-Queuing]]
* [[Prioritätsscheduling|Priority-Queuing]]
* [[Weighted-Fair-Queuing]]

[[Kategorie:Rechnernetze]]

Fair-Queuing - Versionsgeschichte

imported>PerfektesChaos: tk k