• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Weighted round robin

    Przeczytaj także...
    Pakiet telekomunikacyjny (pot. pakiet) – sformatowana jednostka informacji przesyłana poprzez sieć wykorzystującą komutację pakietów. Sieci, które nie obsługują przesyłania pakietów, takie jak np. tradycyjne połączenia modemowe lub połączenia CSD w sieci komórkowej, transmitują dane jako strumień bitów. Usługa Best effort (BES) transmituje dane w sieci o możliwie najwyższej przepustowości ale za to bez gwarancji poziomu usług QoS. Jest to standardowy sposób postępowania z kolejkami pakietów w Internecie. Pakiety są wysyłane w kolejności napływania i są wysyłane tak szybko jak to tylko możliwe.
    Algorytm szeregowania (ang. scheduler - planista) to algorytm rozwiązujący jedno z najważniejszych zagadnień informatyki - jak rozdzielić czas procesora i dostęp do innych zasobów pomiędzy zadania, które w praktyce zwykle o te zasoby konkurują.

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

    Protokół internetowy (ang. Internet Protocol, skrót IP) – protokół komunikacyjny warstwy sieciowej modelu OSI (warstwy internet w modelu TCP/IP). Protokół internetowy to zbiór ścisłych reguł i kroków postępowania, które są automatycznie wykonywane przez urządzenia w celu nawiązania łączności i wymiany danych. Używany powszechnie w Internecie i sieciach lokalnych.

    Ż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 kod]

  • mechanizmy szeregowania



  • w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.006 sek.