Gewichtete faire Warteschlange

Weighted Fair Queuing ( WFQ ) ist ein Netzwerk-Scheduling- Algorithmus. WFQ ist sowohl eine paketbasierte Implementierung der Generalized Processor Sharing (GPS)-Richtlinie als auch eine natürliche Erweiterung von Fair Queuing (FQ). Während FQ die Kapazität der Verbindung in gleiche Teile aufteilt, ermöglicht WFQ den Schedulern, für jeden Datenfluss festzulegen, welcher Anteil der Kapazität zugewiesen wird.

Weighted Fair Queuing wird auch als Packet-by-Packet GPS (PGPS oder P-GPS) bezeichnet, da es die verallgemeinerte Prozessorteilung „bis auf eine Paketübertragungszeit annähert, unabhängig von den Ankunftsmustern“. ^{[ 1 ]}

Parametrisierung und Fairness

Wie bei anderen GPS-ähnlichen Scheduling-Algorithmen obliegt die Wahl der Gewichtungen dem Netzwerkadministrator. Es gibt keine einheitliche Definition von „fair“ (siehe Fair Queuing § Fairness für weitere Informationen).

Durch die dynamische Regulierung der WFQ-Gewichte kann WFQ zur Steuerung der Dienstgüte eingesetzt werden , beispielsweise um eine garantierte Datenrate zu erreichen.

Proportional faires Verhalten lässt sich erreichen, indem die Gewichte auf gesetzt werden , wobei die Kosten pro Datenbit des Datenflusses sind . Beispielsweise können in CDMA- Spreizspektrum-Mobilfunknetzen die Kosten die benötigte Energie (das Interferenzniveau) sein, und in dynamischen Kanalzuweisungssystemen können die Kosten die Anzahl der nahegelegenen Basisstationen sein, die nicht denselben Frequenzkanal nutzen dürfen, um Gleichkanalstörungen zu vermeiden. $w_{i}=1/c_{i}$ $c_{i}$ $i$

Algorithmus

Bei WFQ wird ein Scheduler, der $N$ Datenflüsse verarbeitet, so konfiguriert, dass jeder Datenfluss ein Gewicht hat . Der Datenfluss mit der Nummer N erreicht dann eine durchschnittliche Datenrate von , wobei die Verbindungsrate ist. Ein WFQ-Scheduler, bei dem alle Gewichte gleich sind, ist ein FQ-Scheduler. $w_{i}$ $i$ ${\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$ $R$

Wie bei allen Fair-Queuing-Schedulern ist jeder Datenfluss vor den anderen geschützt, und es lässt sich beweisen, dass bei einem durch Leaky Buckets beschränkten Datenfluss eine End-to-End-Verzögerungsgrenze garantiert werden kann. ^{[ 2 ]}

Der WFQ-Algorithmus ähnelt stark dem von FQ . Für jedes Paket wird ein virtuelles, theoretisches Abflugdatum berechnet, das dem Abflugdatum entspricht, wenn der Scheduler ein perfekter GPS-Scheduler wäre. Immer wenn die Ausgabeverbindung frei ist, wird das Paket mit dem frühesten Datum zur Übertragung ausgewählt.

Der Pseudocode kann einfach aus dem von FQ abgeleitet werden , indem die Berechnung der virtuellen Abflugzeit durch folgende ersetzt wird:

packet.virFinish = virStart + packet.size / Ri

mit . $R_{i}={\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R$

WFQ als GPS-Näherung

WFQ, unter dem Namen PGPS, wurde als „eine hervorragende Annäherung an GPS“ konzipiert, und es wurde bewiesen, dass es GPS „auf eine Paketübertragungszeit genau annähert, unabhängig von den Ankunftsmustern“. ^{[ 1 ]}

Da die WFQ-Implementierung der Fair-Queuing-Methode ähnelt , weist sie dieselbe Komplexität O(log(n)) auf, wobei n die Anzahl der Datenflüsse ist. Diese Komplexität ergibt sich aus der Notwendigkeit, bei jedem Senden eines Pakets die Warteschlange mit der kürzesten virtuellen Endzeit auszuwählen.

Nach WFQ wurden mehrere weitere Implementierungen von GPS definiert.

Selbst wenn WFQ im Vergleich zur idealen GPS-Strategie höchstens um ein Paket verzögert ist, kann es beliebig weit voraus sein. Worst-case Fair Weighted Fair Queueing (WF2Q) behebt dieses Problem, indem jedem Paket ein virtueller Dienstbeginn hinzugefügt wird und ein Paket nur dann ausgewählt wird, wenn sein virtueller Dienstbeginn nicht kleiner als die aktuelle Zeit ist. ^{[ 3 ]}
Die Auswahl der Warteschlange mit der minimalen virtuellen Bearbeitungszeit kann bei Leitungsgeschwindigkeit schwierig umzusetzen sein. Daher wurden andere, weniger komplexe Näherungen an GPS definiert, wie beispielsweise Defizit-Round-Robin .

Geschichte

Die Einführung von Parametern zur beliebigen Aufteilung der Bandbreite wird am Ende von ^{[ 4 ]} als mögliche Erweiterung von FQ erwähnt. Der Begriff „gewichtet“ taucht erstmals in ^{[ 1 ] auf.}

Siehe auch

Referenzen

^ ^a ^b ^c Parekh, AK; Gallager, RG (1993). „Ein verallgemeinerter Ansatz zur gemeinsamen Nutzung von Prozessoren für die Flusssteuerung in integrierten Dienstnetzwerken: Der Einzelknotenfall“ (PDF) . IEEE/ACM Transactions on Networking . 1 (3): 344. doi : 10.1109/90.234856 . S2CID 52808341 .
^ Stiliadis, D.; Varma, A. (1998). „Latenzratenserver: Ein allgemeines Modell zur Analyse von Verkehrsplanungsalgorithmen“ (PDF) . IEEE/ACM Transactions on Networking . 6 (5): 611. doi : 10.1109/90.731196 . Archiviert vom Original (PDF) am 4. März 2016. Abgerufen am 29. August 2015 .
Bennett , JCR; Hui Zhang (1996). „WF/sup 2/Q: Worst-case fair weighted fair queueing“. Proceedings of IEEE INFOCOM '96. Conference on Computer Communications . Vol. 1. S. 120. doi : 10.1109/INFCOM.1996.497885 . ISBN 978-0-8186-7293-4. S2CID 17558577 .
^ Demers, A.; Keshav, S.; Shenker, S. (1989). „Analyse und Simulation eines fairen Warteschlangenalgorithmus“ . ACM SIGCOMM Computer Communication Review . 19 (4): 1. doi : 10.1145/75247.75248 .

[GPS-1] Parekh, AK; Gallager, RG (1993). „Ein verallgemeinerter Ansatz zur gemeinsamen Nutzung von Prozessoren für die Flusssteuerung in integrierten Dienstnetzwerken: Der Einzelknotenfall“ (PDF) . IEEE/ACM Transactions on Networking . 1 (3): 344. doi : 10.1109/90.234856 . S2CID 52808341 .

[2] Stiliadis, D.; Varma, A. (1998). „Latenzratenserver: Ein allgemeines Modell zur Analyse von Verkehrsplanungsalgorithmen“ (PDF) . IEEE/ACM Transactions on Networking . 6 (5): 611. doi : 10.1109/90.731196 . Archiviert vom Original (PDF) am 4. März 2016. Abgerufen am 29. August 2015 .

[WF2Q-3] Bennett , JCR; Hui Zhang (1996). „WF/sup 2/Q: Worst-case fair weighted fair queueing“. Proceedings of IEEE INFOCOM '96. Conference on Computer Communications . Vol. 1. S. 120. doi : 10.1109/INFCOM.1996.497885 . ISBN 978-0-8186-7293-4. S2CID 17558577 .

[FQ-4] Demers, A.; Keshav, S.; Shenker, S. (1989). „Analyse und Simulation eines fairen Warteschlangenalgorithmus“ . ACM SIGCOMM Computer Communication Review . 19 (4): 1. doi : 10.1145/75247.75248 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]