Weighted round robin

Principi

Di seguito, il WRR è presentato come scheduler di rete. Può essere utilizzato in modo analogo anche per lo scheduling dei task.

Uno scheduler di rete WRR ha ${\displaystyle n}$ code di ingresso, ${\displaystyle q_{1},...,q_{n}}$. A ogni coda ${\displaystyle q_{i}}$ è associato ${\displaystyle w_{i}}$, un intero positivo detto peso. Lo scheduler WRR ha un comportamento ciclico: in ogni ciclo, ciascuna coda ${\displaystyle q_{i}}$ dispone di ${\displaystyle w_{i}}$ opportunità di emissione.

I diversi algoritmi WRR differiscono per il modo in cui queste opportunità sono distribuite all'interno del ciclo.

WRR classico

Nel WRR classico lo scheduler scorre ciclicamente le code. Quando una coda ${\displaystyle q_{i}}$ viene selezionata, lo scheduler invia pacchetti fino all'emissione del ${\displaystyle w_{i}}$-esimo pacchetto o fino allo svuotamento della coda.

Costanti e variabili: 
    const N             // numero di code
    const weight[1..N]  // peso di ciascuna coda
    queues[1..N]        // code
    i                   // indice della coda
    c                   // contatore dei pacchetti
    
Istruzioni:
while true do 
    for i in 1 .. N do
        c := 0
        while (not queue[i].empty) and (c<weight[i]) do
            send(queue[i].head())
            queue[i].dequeue()
            c:= c+1

WRR interlacciato

Sia ${\displaystyle w_{max}=\max\{w_{i}\}}$ il peso massimo. Nell'IWRR (interleaved WRR), ogni ciclo è suddiviso in ${\displaystyle w_{max}}$ turni. Una coda con peso ${\displaystyle w_{i}}$ può emettere un pacchetto al turno ${\displaystyle r}$ solo se ${\displaystyle r\leq w_{i}}$.

Costanti e variabili: 
    const N             // numero di code
    const weight[1..N]  // peso di ciascuna coda
    const w_max
    queues[1..N]        // code
    i                   // indice della coda
    r                   // contatore dei turni
    
Istruzioni:

while true do
    for r in 1 .. w_max do 
        for i in 1 .. N do
            if (not queue[i].empty) and (weight[i] >= r) then
                send(queue[i].head())
                queue[i].dequeue()

Esempio

Si consideri un sistema con tre code ${\displaystyle q_{1},q_{2},q_{3}}$ e rispettivi pesi ${\displaystyle w_{1}=5,w_{2}=2,w_{3}=3}$. Si supponga che nella prima coda vi siano 7 pacchetti, A,B,C,D,E,F,G, 3 nella seconda, U,V,W, e 2 nella terza, X,Y. Si assuma che non arrivino altri pacchetti.

Con il WRR classico, nel primo ciclo lo scheduler seleziona dapprima ${\displaystyle q_{1}}$ e trasmette i cinque pacchetti in testa alla coda, A,B,C,D,E (poiché ${\displaystyle w_{1}=5}$); poi seleziona la seconda coda, ${\displaystyle q_{2}}$, e trasmette i due pacchetti in testa, U,V (poiché ${\displaystyle w_{2}=2}$); infine seleziona la terza coda, che ha peso 3 ma contiene solo due pacchetti, e trasmette quindi X,Y. Subito dopo la fine della trasmissione di Y inizia il secondo ciclo, nel quale vengono trasmessi F,G da ${\displaystyle q_{1}}$, seguiti da W da ${\displaystyle q_{2}}$.

Con il WRR interlacciato, il primo ciclo è suddiviso in 5 turni (poiché ${\displaystyle max(w_{1},w_{2},w_{3})=5}$). Nel primo turno (r=1) viene inviato un pacchetto da ciascuna coda (A,U,X); nel secondo (r=2) viene inviato un altro pacchetto da ciascuna coda (B,V,Y); nel terzo (r=3) solo le code ${\displaystyle q_{1},q_{3}}$ possono inviare un pacchetto (${\displaystyle w_{1}>=r}$, ${\displaystyle w_{2}<r}$ e ${\displaystyle w_{3}>=r}$), ma poiché ${\displaystyle q_{3}}$ è vuota viene inviato solo C da ${\displaystyle q_{1}}$; nel quarto e nel quinto turno vengono inviati solo D,E da ${\displaystyle q_{1}}$. Inizia poi il secondo ciclo, nel quale vengono inviati F,W,G.