Viktad round robin

Weighted round robin ( WRR ) är en nätverksschemaläggare för dataflöden, men används också för att schemalägga processer .

Viktad round robin är en generalisering av round-robin-schemaläggning . Den tjänar en uppsättning köer eller uppgifter. Medan round-robin cyklar över köerna eller uppgifterna och ger en servicemöjlighet per cykel, erbjuder viktad round-robin var och en ett fast antal möjligheter, som specificeras av den konfigurerade vikten som tjänar till att påverka den del av kapaciteten som tas emot av varje kö eller uppgift . I datornätverk är en servicemöjlighet emissionen av ett paket, om den valda kön inte är tom.

Om alla paket har samma storlek är WRR den enklaste approximationen av generaliserad processordelning (GPS). Det finns flera varianter av WRR. De viktigaste är den klassiska WRR och den interfolierade WRR.

Algoritm

Principer

WRR presenteras i det följande som en nätverksschemaläggare . Den kan också användas för att schemalägga uppgifter på liknande sätt.

En viktad round-robin nätverksschemaläggare har $n$ ingångsköer, $q_{1},...,q_{n}$ . Till varje kö $q_{i}$ associerat ${\displaystyle w_{i}} ,$ ett positivt heltal, som kallas vikten . WRR-schemaläggaren har ett cykliskt beteende. har varje kö $q_{i}$ $w_{i}$ utsläppsmöjligheter.

De olika WRR-algoritmerna skiljer sig åt vad gäller fördelningarna av dessa möjligheter i cykeln.

Klassisk WRR

I klassisk WRR cyklar schemaläggaren över köerna. När en kö $q_{i}$ är vald, kommer schemaläggaren att skicka paket, upp till emissionen av ${\displaystyle w_{i}}-$ paketet eller slutet av kön.

 
     Konstant och variabler:  const N // Antal köer konstant vikt[1..N] // vikt av varje kö köer[1..N] // köer i // köindex c // paketräknare  Instruktioner:  while  true  do  för  i  i  1 .. N  do  c := 0  while  (inte kö[i].tom) och (c<vikt[i])  skicka  (kö[i].head()) kö[i].dequeue( ) c:= c+1

Interfolierad WRR

Låt $w_{max}=\max\{w_{i}\}$ vara maxvikten. I IWRR delas varje cykel upp i $w_{max}$ omgångar. En kö med vikt $w_{i}$ kan sända ut ett paket vid round $r$ endast om $r\leq w_{i}$ .

 Konstant och variabler:  const N // Nb av köer const weight[1..N] // vikt av varje kö const w_max queues[1..N] // queues i // queue index r // round counter Instruktioner  :

     
        
             while  sant  gör  för  r  i  1 .. w_max  gör  för  i  i  1 .. N  gör  om  (  inte  kö[i].tom)  och  (vikt[i] >= r)  sedan  skicka(kö[i].head()) queue[i].dequeue()

Exempel

Exempel på schemaläggning för CWRR och IWRR

Betrakta ett system med tre köer $q_{1},q_{2},q_{3}$ och respektive vikter $w_{1}=5,w_{2}=2,w_{3}=3$ . Tänk på en situation där de är 7 paket i den första kön, A,B,C,D,E,F,G , 3 i den andra kön, U,V,W och 2 i den tredje kön X,Y . Antag att det inte finns fler paketankomster.

Med klassisk WRR, i den första cykeln, väljer schemaläggaren först $q_{1}$ och sänder de fem paketen i köhuvudet, A,B,C,D,E ( eftersom ${\ displaystyle w_{1}=5}$ ), sedan väljer den den andra kön, $q_{2}$ , och sänder de två paketen längst upp i kön, U,V (eftersom $w_{2}=2$ ), och sist väljer den den tredje kön, som har en vikt som är lika med 3 men bara två paket, så den sänder X,Y . Omedelbart efter slutet av sändningen av Y startar den andra cykeln och F,G från $q_{1}$ sänds, följt av W från $q_{2}$ .

Med interfolierad WRR delas den första cykeln i 5 omgångar (eftersom $max(w_{1},w_{2},w_{3})= 5$ ). I den första ( r=1 ) skickas ett paket från varje kö ( A,U,X ), i den andra omgången ( r=2 ) skickas även ett annat paket från varje kö ( B,V,Y ) , i den tredje omgången ( r=3 ), får endast köerna ${\displaystyle q_{1},q_{3}} skicka ett paket ($ $w_{1} >=r$ , $w_{2}<r$ och $w_{3}>=r$ ), men eftersom $q_{3}$ är tom, skickas endast C från ${\displaystyle q_{1}} , och i den fjärde och femte omgången$ skickas endast D,E från ${\displaystyle q_{1}} .$ Sedan startar den andra cykeln, där F,W,G skickas.

Uppgiftsschemaläggning

Uppgifts- eller processschemaläggning kan göras i WRR på ett sätt som liknar paketschemaläggning: när man överväger en uppsättning av $n$ aktiva uppgifter, schemaläggs de på ett cykliskt sätt, varje uppgift $\tau _{ i}$ får $w_{i}$ quantum eller bit av processortid .

Egenskaper

Precis som round-robin , är viktad round-robin-schemaläggning enkel, lätt att implementera, arbetsbesparande och svältfri .

Vid schemaläggning av paket, om alla paket har samma storlek, är WRR och IWRR en approximation av generaliserad processordelning : en kö $q_{i}$ kommer att ta emot en långvarig del av bandbredden som är lika med ${\displaystyle {\frac {w_{i}}{\sum _{j=1}^{n}w_{j}}}} ($ om alla köer är aktiva) medan GPS betjänar oändligt små mängder av data från varje icke-tom kö och erbjuda denna del vid valfritt intervall.

Om köerna har paket med variabel längd beror den del av bandbredden som tas emot av varje kö inte bara på vikten utan också på paketstorlekarna.

Om en medelpaketstorlek $s_{i}$ är känd för varje kö $q_{i}$ , kommer varje kö att få en långvarig del av bandbredden lika med ${\frac {s_{i}\times w_{i}}{\sum _{j=1}^{n}s_{j}\times w_{j} }}$ . Om målet är att ge varje kö $q_{i}$ en del $\rho _{i}$ av länkkapaciteten (med $\sum _{i=1}^{n}\rho _{i}=1$ ), kan man sätta $w_{i}={\frac {\rho _{i }}{s_{i}}}$ .

Eftersom IWRR har mindre skurar per klass än WRR, innebär det mindre värsta tänkbara förseningar.

Begränsningar och förbättringar

WRR för schemaläggning av nätverkspaket föreslogs först av Katevenis, Sidiropoulos och Courcoubetis 1991, specifikt för schemaläggning i ATM-nätverk som använder paket med fast storlek (celler). Den primära begränsningen för viktad round-robin-köning är att den ger rätt procentandel av bandbredd till varje tjänsteklass endast om alla paket i alla köer är av samma storlek eller när medelpaketstorleken är känd i förväg. I det mer allmänna fallet med IP-nätverk med paket med variabel storlek, för att uppskatta GPS måste viktfaktorerna justeras baserat på paketstorleken. Det kräver en uppskattning av den genomsnittliga paketstorleken, vilket gör en bra GPS-uppskattning svår att uppnå i praktiken med WRR.

Deficit round robin är en senare variant av WRR som uppnår bättre GPS-approximation utan att veta medelpaketstorleken för varje anslutning i förväg. Effektivare schemaläggningsdiscipliner introducerades också som hanterar de ovan nämnda begränsningarna (t.ex. viktad rättvis köning) .

Se även