Gewichtete faire Warteschlangen - Weighted fair queueing

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 gleichen Unterteilen teilt, ermöglicht WFQ den Planern, für jeden Fluss anzugeben, welcher Anteil der Kapazität gegeben wird.

Weighted Fair Queuing ist auch als paketweises GPS (PGPS oder P-GPS) bekannt, da es die allgemeine Prozessorteilung "auf eine Paketübertragungszeit unabhängig von den Ankunftsmustern" annähert.

Parametrierung und Fairness

Wie bei anderen GPS-ähnlichen Planungsalgorithmen wird die Wahl der Gewichte dem Netzwerkadministrator überlassen. Es gibt keine eindeutige Definition dessen, was "fair" ist ( weitere Erläuterungen finden Sie unter Faires Einreihen § Fairness ).

Durch dynamisches Regeln der WFQ-Gewichte kann WFQ zum Steuern der Dienstgüte verwendet werden , um beispielsweise eine garantierte Datenrate zu erreichen.

Ein proportional faires Verhalten kann erreicht werden, indem die Gewichte auf gesetzt werden , wobei die Kosten pro Datenbit des Datenflusses sind . In zellularen CDMA- Spreizspektrumnetzen können die Kosten beispielsweise die erforderliche Energie (der Interferenzpegel) sein, und in dynamischen Kanalzuweisungssystemen können die Kosten die Anzahl nahegelegener Basisstationsstandorte sein, die nicht denselben Frequenzkanal verwenden können, in um Gleichkanalstörungen zu vermeiden.

Algorithmus

In WFQ ist ein Scheduler, der N Flüsse handhabt, mit einer Gewichtung für jeden Fluss konfiguriert . Dann erreicht der Zahlenfluss eine durchschnittliche Datenrate von , wobei die Verbindungsrate ist. Ein WFQ-Scheduler, bei dem alle Gewichtungen gleich sind, ist ein FQ-Scheduler.

Wie bei allen Fair-Queuing-Schedulern ist jeder Fluss vor den anderen geschützt, und es kann nachgewiesen werden, dass bei einem Datenfluss mit Leaky-Bucket- Beschränkung eine End-to-End-Verzögerungsgrenze garantiert werden kann.

Der Algorithmus von WFQ ist dem von FQ sehr ähnlich . Für jedes Paket wird ein virtuelles theoretisches Abfahrtsdatum berechnet, das als Abfahrtsdatum definiert ist, wenn der Scheduler ein perfekter GPS-Scheduler war. Dann wird jedes Mal, wenn die Ausgangsverbindung im Leerlauf ist, das Paket mit dem kleinsten Datum zum Senden ausgewählt.

Der Pseudocode kann einfach aus dem von FQ gewonnen werden, indem die Berechnung der virtuellen Abfahrtszeit durch . ersetzt wird 

packet.virFinish = virStart + packet.size / Ri

mit .

WFQ als GPS-Approximation

WFQ, unter dem Namen PGPS, wurde als "eine ausgezeichnete Annäherung an GPS" entworfen, und es wurde bewiesen, dass es GPS "auf eine Paketübertragungszeit unabhängig von den Ankunftsmustern" annähert.

Da die WFQ-Implementierung dem Fair Queuing ähnlich ist , hat sie die gleiche O(log(n))- Komplexität, wobei n die Anzahl der Flüsse ist. Diese Komplexität ergibt sich aus der Notwendigkeit, jedes Mal, wenn ein Paket gesendet wird, die Warteschlange mit der kleinsten virtuellen Endzeit auszuwählen.

Nach WFQ wurden mehrere andere Implementierungen von GPS definiert.

  • Auch wenn WFQ im Hinblick auf die ideale GPS-Richtlinie höchstens "ein Paket" zu spät ist, kann es beliebig voraus sein. Das Fair Weighted Fair Queuing (WF2Q) im schlimmsten Fall behebt dies, indem es jedem Paket einen virtuellen Dienststart hinzufügt und ein Paket nur dann auswählt, wenn sein virtueller Dienststart nicht kleiner als die aktuelle Zeit ist.
  • Die Auswahl der Warteschlange mit minimaler virtueller Endzeit kann bei Drahtgeschwindigkeit schwer zu implementieren sein. Dann wurden andere Näherungen von GPS mit geringerer Komplexität definiert, wie z . B. Defizit-Round-Robin .

Geschichte

Die Einführung von Parametern zur willkürlichen Aufteilung der Bandbreite wird am Ende als mögliche Erweiterung von FQ erwähnt. Der Begriff gewichtet erscheint zuerst in.

Siehe auch

Verweise