Rättvis köande

Fair queuing ä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 att flöden med stora paket eller processer som genererar små jobb förbrukar mer genomströmning eller CPU-tid än andra flöden eller processer.

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

Historia

Termen rättvis kö myntades av John Nagle 1985 samtidigt som han föreslog round-robin-schemaläggning i porten mellan ett lokalt nätverk och internet för att minska nätverksstörningar från dåligt uppträdande värdar.

En byte-viktad version föreslogs av Alan Demers, Srinivasan Keshav och Scott Shenker 1989, och baserades på den tidigare Nagle-mässköalgoritmen. Den bytevä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öning , och det mer generella konceptet trafikformning , där köprioriteringar styrs dynamiskt för att uppnå önskad flödeskvalitet på tjänstemål eller accelerera vissa flöden.

Princip

Fair queuing använder en kö per paketflöde och servar dem i rotation, så att varje flöde kan "erhålla en lika stor del av resurserna".

Fördelen jämfört med konventionell först in först 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 beskärda del av länkkapaciteten.

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

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

Rättvisa

I samband med nätverksschemaläggning 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 paketen har varierande storlek. Flera formella begrepp om rättvisa mått har definierats inklusive max-min rättvisa , värsta tänkbara 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 allokeras till varje flöde som leder till viktad rättvis köbildning och generaliserad processordelning .

En bytevägd rättvis köalgoritm

Denna algoritm försöker efterlikna rättvisan i bitvis round-robin-delning av länkresurser mellan konkurrerande flöden. Paketbaserade flöden måste emellertid överföras paketvis och i sekvens. Den bytevä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 round robin. Paketet med den tidigaste sluttiden enligt denna modellering är nästa utvalda för överföring.

Algoritmens komplexitet är O(log(n)) , där n är antalet köer/flöden.

Algoritmdetaljer

Modellering av faktisk sluttid är, även om det är genomförbart, 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 kommer in i någon kö.

introduceras konceptet virtuell tid . Sluttiden för varje paket beräknas på denna alternativa monotont ökande virtuella tidsskala. Även om virtuell tid inte exakt modellerar tidspaketen som slutför sina sändningar, modellerar den noggrant den ordning i vilken sändningarna måste ske för att uppfylla målen för den fullfjädrade modellen. Med virtuell tid är det onödigt att beräkna sluttiden för tidigare köade paket. Även om sluttiden, i absoluta termer, för befintliga paket potentiellt påverkas av nya ankomster, är sluttiden på den virtuella tidslinjen oförändrad - den virtuella tidslinjen förvrängs med avseende på realtid för att tillgodose varje 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 den maximala tiden mellan den föregående virtuella sluttiden för samma kö och det aktuella ögonblicket.

Med en virtuell sluttid för alla kandidatpaket (dvs. paketen i spetsen för alla icke-tomma flödesköer) beräknad, jämför rättvis köning den virtuella sluttiden och väljer den minsta. Paketet med minsta virtuella sluttid sänds.

Pseudokod

 Delade variabler  const N // Antal köer queues[1..N] // queues lastVirFinish[1..N] // sista virtuella avslutande ögonblicket

 motta  (paket) queueNum := väljQueue(paket) queues[queueNum].enqueue(paket) updateTime(paket, queueNum)

 updateTime  (paket, queueNum) // virStart är den virtuella starten av tjänsten virStart := max(now(), lastVirFinish[queueNum]) packet.virFinish := packet.size + virStart lastVirFinish[queueNum] := packet.virFinish

 send()  queueNum := selectQueue()-paket := queues[queueNum].dequeue(  )  returpaket

       selectQueue()  it := 1 minVirFinish =  $\infty$  medan  det ≤ N  gör  kö := köar[it]  om  inte  queue.empty  och  queue.head.virFinish < minVirFinish  sedan  minVirFinish = queue.head.Numnish := it it := it +  1  returköNum

Funktionen motta () exekveras varje gång ett paket tas emot, och skicka () exekveras 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 förutsätter att det finns en funktion nu () som returnerar den aktuella virtuella tiden, och en funktion selectQueue () som väljer den kö där paketet är i kö.

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

Se även

^ ^a ^b John Nagle: "På paketväxlar med oändlig lagring," RFC 970, IETF , december 1985.
^ ^a ^b ^c Nagle, JB (1987). "På paketväxlar med oändlig lagring". IEEE-transaktioner på kommunikation . 35 (4): 435–438. CiteSeerX 10.1.1.649.5380 . doi : 10.1109/TCOM.1987.1096782 .
^ 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 "fair" 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 tillskansa sig mer än sin beskärda del av gatewayens resurser. Detta väckte livlig och intresserad diskussion.
^ Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1989). "Analys och simulering av en rättvis köalgoritm". ACM SIGCOMM Computer Communication Review . 19 (4): 1–12. doi : 10.1145/75247.75248 .
^ Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1990). "Analys och simulering av en rättvis köalgoritm" (PDF) . Internetarbete: forskning och erfarenhet . 1 :3–26.
^ Bennett JCR; Hui Zhang (1996). "WF/sup 2/Q: Worst-case rättvis vägd rättvis köbildning". IEEE INFOCOM '96. Konferens om datorkommunikation . Vol. 1. sid. 120. doi : 10.1109/INFCOM.1996.497885 . ISBN 978-0-8186-7293-4 .
^ Ito, Y.; Tasaka, S.; Ishibashi, Y. (2002). "Variabelt viktad round robin-kö för kärn-IP-routrar". Konferenshandlingar 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 .

[RFC970-1] John Nagle: "På paketväxlar med oändlig lagring," RFC 970, IETF , december 1985.

[Nagle87-2] Nagle, JB (1987). "På paketväxlar med oändlig lagring". IEEE-transaktioner på 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 "fair" 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 tillskansa sig mer än sin beskärda del av gatewayens resurser. Detta väckte livlig och intresserad diskussion.

[4] Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1989). "Analys och simulering av en rättvis köalgoritm". ACM SIGCOMM Computer Communication Review . 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: Worst-case rättvis vägd rättvis köbildning". IEEE INFOCOM '96. Konferens om datorkommunikation . Vol. 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 round robin-kö för kärn-IP-routrar". Konferenshandlingar 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 .