AKKD

1. FIFO / FCFS
2. Round-robin - algorytm karuzelowy
3. Fair Queuing
4. Oryginalne SFQ - Stochastic Fair Queuing
5. Deficit Round-Robin
6. Linuksowe SFQ (Stochastic DRR)
7. RED - Losowe Wczesne Wykrywanie
8. Blue
9. SFB - Stochastyczny Sprawiedliwy RED
10. Wiadra
    1. Leaky bucket - Cieknące wiadro
    2. Token bucket - Wiadro żetonów

Algorytm karuzelowy (round-robin)

Algorytm karuzelowy (Round-robin) mówi, że można stworzyć tyle kolejek ile jest strmunieni oraz zdejmować pakiety po jednym z każdego pasma w stałym porządku. Jeśli dane pasmo nie ma nic do wysłania, przechodzi się do kolejnego bez tracenia czasu. W ten sposób, jeśli połączenie zaczyna wysylać dane, ma pewność, że pierwszy pakiet zostanie wysłany nie poźniej niż po czasie jednego okresu.

Idea alg. karuzelowego pojawiła się już w 1986 roku – Ellen Hahne przedstawiła [1]wyniki rozważań teoretycznych nad użyciem algorytmu karuzelowego do pracy w urządzeniach przesyłających dane. Wersja zaprezentowanego tam algorytmu opierała swe działanie nie tylko na tym czy połączenie wystawiło pakiet do wysłania czy nie. Mianowicie, brana pod uwagę była także ilość punktów przekazujących (hopów) jaką pakiet już przebył, oraz czy w następnym punkcie jest dozwolona ilość miejsca dla danego połączenia. W protokole IP niestety nie ma dostępnej informacji o zajętości bufora przez następne urządzenie na ścieżce przesyłu. Ważnymi wioskami płynącymi z tej pracy było natomiast zauważenie, że dla połączeń wymagających najwiekszych przepustowości algorytm zbliżał się niemal idealnie do równego podziału, wraz ze zmniejszaniem długości pakietu. Jest to efekt działający przeciwnie do znanego problemu kiedy zbyt duża fragmentacja powoduje, że narzut zwiazany z obsługą danych jest wiekszy niż same obsługiwane dane. Opracowanie to stanowiło podłoże do wielu późniejszych prac na ten temat i miało wpływ na algorytmy wykrozystywane dzisiaj (np. (W)FQ, SFQ).

Istnieje też ważona wersja tego algorytmu (Weighted Round Robin) pozwalająca przypisać wagę każdemu połączeniu, lub (stosowane w praktyce) połączeniom do/z konkretnego adresu IP lub podsieci. Wagi te są normalizowane (tak by najmniejsza waga była jak najbliżej jedynki, a równocześnie inne wagi pozostały całkowite), po czym służa za wyznacznik ile pakietów z danej kolejki może być zdjętych na raz podczas jednego okresu.

Pierwszy pakiet z połączenia zostanie wysłany nie później niż po czasie jednego okresu, jednak w sieciach w których pakiet ma zmienną długość, zmienny jest czas jego wysłania, a zatem zmienia się czas jednego okresu. To sprawia, że o ile algorytm karuzelowy bazujący na pakietach sprawdza się doskonale w dzieleniu pasma dla połączeń podobnego typu, to w momencie kiedy do czynienia mamy z mieszanką choćby sesji FTP (przesyłanie plików – duże pakiety) i SSH (zdalny interaktywny dostęp – małe pakiety), ta druga może doświadczać poważnych opóźnień. Wyobraźmy sobie sytuacje kiedy na interfejsie dwa połączenia kolejkują dane z taką samą prędkością (w bitach na sekundę), jednak drugie połączenie kolejkuje pakiety ponad dwa razy większe (rys RR). Algorytm karuzelowy obsługiwać będzie po jednym pakiecie z każdego połączenia, więc w każdym okresie drugie połączenie wyśle ponad dwa razy więcej bitów. Jest to typowy problem algorytmu dzielącego pasmo pakietowo.

1. [^] Ellen Louise Hahne ,,Round robin scheduling for fair flow control in data communication networks'', rozprawa doktorska, MIT 1986