Faires Anstehen - Fair queuing

Fair Queuing ist eine Familie von Scheduling-Algorithmen, die in einigen Prozess- und Netzwerk-Schedulern verwendet werden . Der Algorithmus wurde entwickelt, um Fairness zu erreichen, wenn eine begrenzte Ressource gemeinsam genutzt wird, um beispielsweise zu verhindern, dass Flows mit großen Paketen oder Prozessen, die kleine Jobs generieren, mehr Durchsatz oder CPU-Zeit verbrauchen als andere Flows oder Prozesse.

Fair Queuing ist in einigen fortschrittlichen Netzwerk-Switches und Routern implementiert .

Geschichte

Der Begriff Fair Queuing wurde 1985 von John Nagle geprägt, als er eine Round-Robin-Planung im Gateway zwischen einem lokalen Netzwerk und dem Internet vorschlug , um Netzwerkunterbrechungen durch sich schlecht benehmende Hosts zu reduzieren.

Eine bytegewichtete Version wurde 1989 von Alan Demers, Srinivasan Keshav und Scott Shenker vorgeschlagen und basierte auf dem früheren Nagle Fair Queuing Algorithmus. Der bytegewichtete faire Warteschlangen-Algorithmus zielt darauf ab, ein Bit-pro-Bit-Multiplexing nachzuahmen, indem das theoretische Abfahrtsdatum für jedes Paket berechnet wird.

Das Konzept wurde zu einem gewichteten fairen Warteschlangensystem und dem allgemeineren Konzept der Verkehrsgestaltung weiterentwickelt , bei dem die Warteschlangenprioritäten dynamisch gesteuert werden, um die gewünschten Flussqualitätsziele von Diensten zu erreichen oder einige Flüsse zu beschleunigen.

Prinzip

Fair Queuing verwendet eine Warteschlange pro Paketfluss und bedient diese abwechselnd, so dass jeder Fluss „einen gleichen Bruchteil der Ressourcen erhalten“ kann.

Der Vorteil gegenüber herkömmlichen first in first out (FIFO) oder Prioritäts - Warteschlangen besteht darin , dass eine hohe Datenrate fließen, bestehend aus großen Paketen oder viele Datenpakete, kann nicht mehr als seinen fairen Anteil an der Verbindungskapazität nehmen.

Fair Queuing wird in Routern, Switches und statistischen Multiplexern verwendet , die Pakete aus einem Puffer weiterleiten . Der Puffer arbeitet als Warteschlangensystem, in dem die Datenpakete bis zur Übertragung zwischengespeichert werden.

Bei einer Verbindungsdatenrate von R werden zu jedem gegebenen Zeitpunkt die N aktiven Datenflüsse (die mit nicht leeren Warteschlangen) jeweils mit einer durchschnittlichen Datenrate von R/N bedient . In einem kurzen Zeitintervall kann die Datenrate um diesen Wert schwanken, da die Pakete der Reihe nach zugestellt werden.

Gerechtigkeit

Im Kontext der Netzwerkplanung hat Fairness mehrere Definitionen. Nagels Artikel verwendet das Round-Robin-Scheduling von Paketen, was in Bezug auf die Anzahl der Pakete fair ist, aber nicht auf die Bandbreitennutzung, wenn Pakete unterschiedlicher Größe sind. Es wurden mehrere formale Begriffe von Fairness-Maß definiert, darunter Max-Min-Fairness , Worst-Case-Fairness und Fairness-Index .

Verallgemeinerung auf gewichtetes Teilen

Die ursprüngliche Idee gibt jedem Fluss die gleiche Geschwindigkeit. Eine natürliche Erweiterung besteht darin, den Benutzer den jedem Fluss zugeteilten Bandbreitenanteil spezifizieren zu lassen, was zu einer gewichteten fairen Warteschlange und einer generalisierten Prozessorteilung führt .

Ein bytegewichteter fairer Warteschlangen-Algorithmus

Dieser Algorithmus versucht, die Fairness des bitweisen Round-Robin-Sharings von Verbindungsressourcen zwischen konkurrierenden Flüssen zu emulieren. Paketbasierte Flüsse müssen jedoch paketweise und nacheinander übertragen werden. Der Byte-gewichtete faire Warteschlangen-Algorithmus wählt die Übertragungsreihenfolge für die Pakete aus, indem er die Endzeit für jedes Paket so modelliert, als ob sie bitweise Round-Robin übertragen werden könnten. Das Paket mit der frühesten Endzeit gemäß dieser Modellierung wird als nächstes zur Übertragung ausgewählt.

Die Komplexität des Algorithmus ist O(log(n)) , wobei n die Anzahl der Warteschlangen/Flüsse ist.

Algorithmusdetails

Die Modellierung der tatsächlichen Endzeit ist zwar machbar, aber rechenintensiv. Das Modell muss jedes Mal, wenn ein Paket zur Übertragung ausgewählt wird und jedes Mal, wenn ein neues Paket in einer Warteschlange ankommt, im Wesentlichen neu berechnet werden.

Um die Rechenlast zu reduzieren, wird das Konzept der virtuellen Zeit eingeführt. Die Endzeit für jedes Paket wird auf dieser alternativen monoton ansteigenden virtuellen Zeitskala berechnet. Während die virtuelle Zeit die Zeitpakete, die ihre Übertragungen abschließen, nicht genau modelliert, modelliert sie genau die Reihenfolge, in der die Übertragungen erfolgen müssen, um die Ziele des Modells mit vollem Funktionsumfang zu erfüllen. Bei Verwendung der virtuellen Zeit ist es nicht erforderlich, die Endzeit für zuvor in die Warteschlange gestellte Pakete neu zu berechnen. Obwohl die Endzeit, absolut ausgedrückt, für existierende Pakete potentiell durch Neuankünfte beeinflusst wird, bleibt die Endzeit auf der virtuellen Zeitlinie unverändert – die virtuelle Zeitlinie verzieht sich in Bezug auf die Echtzeit, um jede neue Übertragung aufzunehmen.

Die virtuelle Endzeit für ein neu in die Warteschlange gestelltes Paket ergibt sich aus der Summe der virtuellen Startzeit plus der Paketgröße. Die virtuelle Startzeit ist das Maximum zwischen der vorherigen virtuellen Endzeit derselben Warteschlange und dem aktuellen Zeitpunkt.

Mit einer berechneten virtuellen Endzeit aller Kandidatenpakete (dh der Pakete am Kopf aller nicht-leeren Flusswarteschlangen) vergleicht die faire Warteschlangenbildung die virtuelle Endzeit und wählt die minimale aus. Das Paket mit der minimalen virtuellen Endzeit wird übertragen.

Pseudocode

Shared variables
    const N             // Nb of queues 
    queues[1..N]        // queues
    lastVirFinish[1..N] // last virtual finish instant

receive(packet)
     queueNum := chooseQueue(packet)
     queues[queueNum].enqueue(packet)
     updateTime(packet, queueNum)

updateTime(packet, queueNum)
    // virStart is the virtual start of service
    virStart := max(now(), lastVirFinish[queueNum])
    packet.virFinish := packet.size + virStart
    lastVirFinish[queueNum] := packet.virFinish

send()
     queueNum := selectQueue()
     packet := queues[queueNum].dequeue()
     return packet

selectQueue()
     it := 1
     minVirFinish = 
     while it ≤ N do
         queue := queues[it]
         if not queue.empty and queue.head.virFinish < minVirFinish then
             minVirFinish = queue.head.virFinish
             queueNum := it 
         it := it + 1
     return queueNum

Die Funktion receive () wird jedes Mal ausgeführt, wenn ein Paket empfangen wird, und send () wird jedes Mal ausgeführt, wenn ein zu sendendes Paket ausgewählt werden muss, dh wenn die Verbindung im Leerlauf ist und die Warteschlangen nicht leer sind. Dieser Pseudocode geht davon aus, dass es eine Funktion now () gibt, die die aktuelle virtuelle Zeit zurückgibt, und eine Funktion chooseQueue (), die die Warteschlange auswählt, in die das Paket eingereiht wird.

Die Funktion selectQueue () wählt die Warteschlange mit der minimalen virtuellen Endzeit aus . Aus Gründen der Lesbarkeit führt der hier vorgestellte Pseudocode eine lineare Suche durch. Die Aufrechterhaltung einer sortierten Liste kann jedoch in logarithmischer Zeit implementiert werden, was zu einer Komplexität von O(log(n)) führt , jedoch mit komplexerem Code.

Siehe auch

Verweise

  1. ^ a b John Nagle: "On Packet Switches with infinite storage", RFC 970, IETF , Dezember 1985.
  2. ^ a b c Nagle, JB (1987). „Auf Paket-Switches mit unendlichem Speicher“. IEEE-Transaktionen zur Kommunikation . 35 (4): 435–438. CiteSeerX  10.1.1.649.5380 . doi : 10.1109/TCOM.1987.1096782 .
  3. ^ Phillip Gross (Januar 1986), Proceedings of the 16-17 January 1986 DARPA Gateway Algorithms and Data Structures Task Force (PDF) , IETF , S. 5, 98 , abgerufen 2015-03-04 , Nagle präsentierte seine "faire Warteschlange" Schema, bei dem Gateways separate Warteschlangen für jeden sendenden Host unterhalten. Auf diese Weise können Hosts mit pathologischen Implementierungen nicht mehr als ihren gerechten Anteil an den Ressourcen des Gateways an sich reißen. Dies führte zu einer lebhaften und interessierten Diskussion.
  4. ^ Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1989). "Analyse und Simulation eines fairen Warteschlangen-Algorithmus". ACM SIGCOMM Überprüfung der Computerkommunikation . 19 (4): 1–12. doi : 10.1145/75247.75248 .
  5. ^ Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1990). "Analyse und Simulation eines Fair Queuing-Algorithmus" (PDF) . Internetworking: Forschung und Erfahrung . 1 : 3–26.
  6. ^ Bennett, JCR; Hui Zhang (1996). "WF/sup 2/Q: Fair Weighted Fair Queueing im schlimmsten Fall". Proceedings of IEEE INFOCOM '96. Konferenz über Computerkommunikation . 1 . s. 120. doi : 10.1109/INFCOM.1996.497885 . ISBN 978-0-8186-7293-4.
  7. ^ Ito, Y.; Tasaka, S.; Ishibashi, Y. (2002). „Variable gewichtetes Round-Robin-Queuing für Core-IP-Router“. Konferenzberichte der IEEE International Performance, Computing, and Communications Conference (Kat.-Nr. 02CH37326) . s. 159. doi : 10.1109/IPCCC.2002.995147 . ISBN 978-0-7803-7371-6.