Underskott round robin

"DWRR" omdirigerar här. För radiostationen i Filippinerna, se DWRR-FM .

Deficit Round Robin ( DRR ), även Deficit Weighted Round Robin ( DWRR ), är en schemaläggningsalgoritm för nätverksschemaläggaren . DRR är, liksom viktad rättvis kö (WFQ), en paketbaserad implementering av den idealiska policyn för Generalized Processor Sharing (GPS). Det föreslogs av M. Shreedhar och G. Varghese 1995 som en effektiv (med O(1) komplexitet) och rättvis algoritm.

Detaljer

I DRR är en schemaläggare som hanterar N flöden konfigurerad med ett kvant $Q_{i}$ för varje flöde. Denna globala idé är att, vid varje omgång, kan flödet $i$ sända högst $Q_{i}$ bytes, och de återstående, om några, rapporteras till nästa omgång. På detta sätt är den lägsta hastighet som flöde $i$ kommer att uppnå på lång sikt ${\frac {Q_{i} }{(Q_{1}+Q_{2}+...+Q_{N})}}R$ ; där $R$ är länkhastigheten.

Algoritm

DRR skannar alla icke-tomma köer i sekvens. När en icke-tom kö $i$ väljs, ökas dess underskottsräknare med dess kvantvärde. Då är värdet på underskottsräknaren ett maximalt antal byte som kan skickas vid denna tur: om underskottsräknaren är större än paketets storlek i spetsen av kön (HoQ), kan detta paket skickas, och räknarens värde minskas med paketstorleken. Sedan jämförs storleken på nästa paket med räknarens värde, etc. När kön är tom eller värdet på räknaren är otillräckligt, kommer schemaläggaren att hoppa till nästa kö. Om kön är tom återställs värdet på underskottsräknaren till 0.

 Variabler och konstanter  konstant heltal N // Nb av köer const heltal Q[1..N] // Per kö kvantheltal DC[1..N] // Per kö underskottsräknare kökö[1..N] // Den köer 

    
         
            
        
    
 Schemaläggning Loop  while  true  gör  för  i i 1..N  gör  om  inte queue[i].empty()  så  DC[i]:= DC[i] + Q[i]  while  ( inte queue[i].empty( )  och  DC[i] ≥ kö[i].head().size() )  gör  DC[i] := DC[i] − kö[i].head().size() send( kö[i] .head() ) queue[i].dequeue()  end while  if  queue[i].empty()  then  DC[i] := 0  end if  end if  end för  end while 

Prestationer: rättvisa, komplexitet och latens

Precis som andra GPS-liknande schemaläggningsalgoritmer överlåts valet av vikter till nätverksadministratören.

Liksom WFQ erbjuder DRR en minimal hastighet för varje flöde oavsett storleken på paketen. Vid viktad round robin-schemaläggning beror andelen bandbredd som används på paketets storlekar.

Jämfört med WFQ-schemaläggare som har komplexiteten O(log(n)) ( n är antalet aktiva flöden/köer ), är komplexiteten för DRR O(1) , om kvant $Q_{i}$ är större än den maximala paketstorleken för detta flöde. Ändå har denna effektivitet en kostnad: latensen, dvs avståndet till den ideala GPS:en, är större i DRR än i WFQ. Mer om de värsta latenserna finns här.

Genomföranden

En implementering av deficit round robin-algoritmen skrevs av Patrick McHardy för Linux-kärnan och publicerades under GNU General Public License .

I Cisco- och Juniper-routrar är modifierade versioner av DRR implementerade: eftersom latensen för DRR kan vara större för vissa trafikklasser, ger dessa modifierade versioner högre prioritet till vissa köer, medan de andra serveras med standard DRR-algoritmen.

Se även

• Schemaläggningsalgoritm
• Rättvis köande
• Generaliserad processordelning
• Viktad rättvis köning
• Viktad round robin
• Rättvisemått

externa länkar

• UC Berkeley EE122-föreläsning: Effektiv mässkö med deficit round robin