Rättvis kö - Fair queuing

Rättvis köning är en familj av schemaläggningsalgoritmer som används i vissa process- och nätverksschemaläggare . Algoritmen är utformad för att uppnå rättvisa när en begränsad resurs delas, till exempel för att förhindra flöden med stora paket eller processer som genererar små jobb från att konsumera mer genomströmning eller CPU-tid än andra flöden eller processer.

Rättvis köning implementeras i vissa avancerade nätverksväxlar och routrar .

Historia

Begreppet rättvis kö skapades av John Nagle 1985 medan han föreslog rundplanering i schemat mellan gatunätet och internet för att minska nätstörningar från dåligt beteende värdar.

En byte-vägd version föreslogs av Alan Demers, Srinivasan Keshav och Scott Shenker 1989 och baserades på den tidigare Nagle-rätta köalgoritmen. Den byte-vägda rättvisa köalgoritmen syftar till att efterlikna en bit-per-bit-multiplexering genom att beräkna teoretiskt avgångsdatum för varje paket.

Konceptet har vidareutvecklats till viktad rättvis kö och det mer generella konceptet med trafikformning , där köprioriteter dynamiskt styrs för att uppnå önskad flödeskvalitet i servicemål eller påskynda vissa flöden.

Princip

Rättvis köning använder en kö per paketflöde och servar dem i rotation, så att varje flöde kan "få en lika stor del av resurserna".

Fördelen jämfört med konventionell först in första ut (FIFO) eller prioritetskö är att ett flöde med hög datahastighet, bestående av stora paket eller många datapaket, inte kan ta mer än sin rättvisa andel av länkkapaciteten.

Rättvis köning används i routrar, switchar och statistiska multiplexorer som vidarebefordrar paket från en buffert . Bufferten fungerar som ett kösystem där datapaketet lagras tillfälligt tills de sänds.

Med en länkdatahastighet på R , vid varje given tidpunkt de N aktiva dataflöden (de med icke-tomma köer) betjänas var och en med en medeldatahastighet på R / N . Under ett kort tidsintervall kan datahastigheten fluktuera runt detta värde eftersom paketen levereras i tur och ordning i tur och ordning.

Rättvisa

I samband med schemaläggning av nätverk har rättvisa flera definitioner. Nagels artikel använder round-robin schemaläggning av paket, vilket är rättvist när det gäller antalet paket, men inte på bandbreddsanvändningen när paket har olika storlek. Flera formella begrepp om mått på rättvisa har definierats inklusive max-min rättvisa , värsta fall rättvisa och rättvisa index .

Generalisering till viktad delning

Den ursprungliga idén ger varje flöde samma hastighet. En naturlig förlängning består i att låta användaren specificera den del av bandbredden som tilldelats varje flöde vilket leder till viktad rättvis kö och generaliserad processordelning .

En byte-vägd rättvis köalgoritm

Denna algoritm försöker efterlikna rättvisa bitvis runddelning av länkresurser mellan konkurrerande flöden. Paketbaserade flöden måste dock överföras paketvis och i följd. Den byte-vägda rättvisa köalgoritmen väljer överföringsordning för paketen genom att modellera sluttiden för varje paket som om de skulle kunna sändas bitvis kringgående. Paketet med den tidigaste sluttiden enligt denna modellering är nästa valda för överföring.

Komplexiteten hos algoritmen är O (log (n)) , där n är antalet köer / flöden.

Algoritmdetaljer

Modellering av den faktiska sluttiden, medan det är möjligt, är beräkningsintensivt. Modellen måste väsentligen beräknas om varje gång ett paket väljs för överföring och varje gång ett nytt paket anländer till valfri kö.

För att minska beräkningsbelastningen introduceras begreppet virtuell tid . Sluttid för varje paket beräknas på denna alternativa monotont ökande virtuella tidsskala. Medan virtuell tid inte exakt modellerar tidspaketen slutför sina överföringar, modellerar den exakt den ordning i vilken överföringarna måste ske för att uppfylla målen för den fullständiga modellen. Med virtuell tid är det onödigt att beräkna sluttiden för paket som tidigare har köats. Även om sluttiden, i absoluta termer, för befintliga paket potentiellt påverkas av nyanlända, är sluttiden på den virtuella tidslinjen oförändrad - den virtuella tidslinjen varpar i förhållande till realtid för att tillgodose eventuell ny överföring.

Den virtuella sluttiden för ett nyligen köat paket ges av summan av den virtuella starttiden plus paketets storlek. Den virtuella starttiden är det maximala mellan den tidigare virtuella sluttiden för samma kö och det aktuella ögonblicket.

Med en virtuell avslutningstid för alla kandidatpaket (dvs. paketen i spetsen för alla icke-tomma flödesköer) beräknas, jämför rättvis köning den virtuella avslutningstiden och väljer den minsta. Paketet med den minsta virtuella efterbehandlingstiden överförs.

Pseudokod

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

Funktionen får () körs varje gång ett paket tas emot, och skicka () körs varje gång ett paket att skicka måste väljas, dvs när länken är ledig och köerna inte är tomma. Den här pseudokoden antar att det finns en funktion nu () som returnerar den aktuella virtuella tiden, och en funktion väljerQueue () som väljer kön där paketet är inkapslat.

Funktionen selectQueue () väljer kön med minimal virtuell sluttid. För läsbarhetens skull gör den pseudokod som presenteras här en linjär sökning. Men att upprätthålla en sorterad lista kan implementeras på logaritmisk tid, vilket leder till en O (log (n)) -komplexitet, men med mer komplex kod.

Se även

Referenser

  1. ^ a b John Nagle: "På paketbrytare med oändlig lagring," RFC 970, IETF , december 1985.
  2. ^ a b c Nagle, JB (1987). "På paketbrytare med oändlig lagring". IEEE-transaktioner vid kommunikation . 35 (4): 435–438. CiteSeerX  10.1.1.649.5380 . doi : 10.1109 / TCOM.1987.1096782 .
  3. ^ Phillip Gross (januari 1986), Proceedings of the 16-17 January 1986 DARPA Gateway Algorithms and Data Structures Task Force (PDF) , IETF , s. 5, 98 , hämtad 2015-03-04 , Nagle presenterade sin "rättvisa kö" schema, där gateways upprätthåller separata köer för varje sändande värd. På detta sätt kan värdar med patologiska implementeringar inte ta mer än deras rättvisa andel av gatewayens resurser. Detta åberopade livlig och intresserad diskussion.
  4. ^ Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1989). "Analys och simulering av en rättvis köalgoritm". ACM SIGCOMM Datorkommunikationsgranskning . 19 (4): 1–12. doi : 10.1145 / 75247.75248 .
  5. ^ Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1990). "Analys och simulering av en rättvis köalgoritm" (PDF) . Internetarbete: Forskning och erfarenhet . 1 : 3–26.
  6. ^ Bennett, JCR; Hui Zhang (1996). "WF / sup 2 / Q: värsta fall rättvis viktad rättvis kö". Förfaranden från IEEE INFOCOM '96. Konferens om datorkommunikation . 1 . sid. 120. doi : 10.1109 / INFCOM.1996.497885 . ISBN 978-0-8186-7293-4.
  7. ^ Ito, Y .; Tasaka, S .; Ishibashi, Y. (2002). "Variabelt viktad rundkökskö för kärnor för IP - routrar". Konferensförfaranden från IEEE International Performance, Computing and Communications Conference (kat. Nr 02CH37326) . sid. 159. doi : 10.1109 / IPCCC.2002.995147 . ISBN 978-0-7803-7371-6.