Weighted round robin

Z Wikipedii

Weighted round robin (WRR) to algorytm szeregowania używany przy obsłudze połączeń typu Best Effort. Jest najprostszą emulacją algorytmu generalized processor sharing (GPS). Podczas gdy GPS obsługuje w każdym kroku nieskończenie małą porcję danych z każdego niepustego połączenia, algorytm WRR obsługuje pewną liczbę pakietów (liczba = znormalizowany(waga / średnia długość pakietu)).

Żeby otrzymać zbiór znormalizowanych wag, średnia wielkość pakietu musi być znana. Tylko wtedy algorytm WRR skutecznie emuluje GPS. Zatem najlepiej tę wielkość znać a priori. Z tym, że jest to warunek niewykonalny w prawdziwych sieciach IP. Średnią wielkość pakietu trzeba więc szacować, co w praktyce może być trudne. Innym problemem jest to, iż w skali jednej rundy algorytm WRR nie gwarantuje tzw. uczciwego podziału łącza (ang. fair link sharing).

Mechanizm WRR (pseudokod):

//calculate number of packets to be served each round by connections

for (each connection)
   connection[i].normalized_weight = connection[i].weight / connection[i].mean_packet_size;

min = findSmallestNormalizedWeight();

for (each connection)
   connection[i].packets_to_be_served = connection[i].normalized_weight / min;

// main loop

while (true)
{
   for (each non-empty connection)
      for (j=0; j< min(connection[i].packets_to_be_served, connection[i].packets_waiting); j++)
         servePacket (connection[i].getPacket());
}

Istnieje zmodyfikowana wersja algorytmu WRR zwana deficit round robin (DRR), która potrafi właściwie obsługiwać pakiety o różnych długościach, bez potrzeby znajomości a priori ich średniej długości.

Mimo wszystko są bardziej efektywne algorytmy szeregowania, które radzą sobie z obu wspomnianymi problemami, np. weighted fair queuing (WFQ).

[edytuj] Zobacz też

• mechanizmy szeregowania