Weighted round robin

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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).

Zobacz też[edytuj | edytuj kod]