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

W tej samej publikacji co Blue, W. Feng, D. Kandlur, D. Saha i K. Shin zaprezentowali algorytm nazwany Stochastic Fair Blue (SFB), łaczący w sobie cechy RED/Blue oraz SFQ. Głownym zadaniem tego algorytmu (oprócz działania tak jak Blue) jest wyłapywanie połączeń niepoddających się kontroli zaznaczaniem lub odrzucaniem pojedyńczych pakietów. Algorytm, chociaż dość wyszukany, w rzeczywistości jest nieskomplikwoany obliczeniowo i wymagający wyjątkowo mało pamięci roboczej.

Aby wykryć niekontrolowalne połączenie, zmienna $p_m$ oraz ilość danych (długość kolejki) powinna być utrzymywana dla wszystkich połączeń. Jeśli prawdopodobieństwo dla danego połączenia osiąga $1$, oznacza to, że połączenie jest niekontrolowalne i należy je stłumić, odmówić usługi itp. Domyślnie, algorytm SFB odrzuca wtedy tyle pakietów, by prędkość połączenia spadła do określonego poziomu. Określmy to jako ograniczenie pasma (ang. rate limit). Taka tablica danych jednak wymaga dość dużej ilości pamięci a klasyfikacja pakietów do połączeń zbędnej mocy obliczeniowej. Dlatego algorytm używa w tym celu filtra Bloom'a. Jest to probabilistyczna struktura potrafiąca przechowywać informacje o zbiorze danych $X$ zawierających więcej informacji niż ona sama. Składa się ona z wektora danych $B$ oraz wektora funkcji haszujących $H$ z czego każda taka funkcja każdemu elementowi z $X$ przyporządkowuje jakiś element z $B$. Filtr ma sens (jest przydatny), jeśli $|B| < |X|$, a więc nie jest to funkcja różnowartościowa, nie musi to też być suriekcja. Kiedy prosimy o dostęp do elementu $x \in X$, funkcje haszujące zwracają nam wektor elementów z $B$, które wszystkie jednocześnie modyfikujemy, lub odczytujemy. Interpretacja odczytanych danych zależy od tego co chcemy osiagnąć. Możemy pobierać średnią wartość lub najmniejszą/największą. Wynik jest oczywiście niedokładny, gdyż ten sam element z $B$ może być modyfikowany przez różne elementy z $X$.

Schemat działania SFB. Dla pakietu z połączenia $x_1$: $h_0(x_1) = 1, h_1(x_1) = 1 = h_1(x_2), h_{L-1}(x_1) = 0$. Kolizja dla $i=1$ nie powoduje błedu, gdyż brane jest minimalne $p_m$ dla całej ścieżki (rys. wg tej samej publikacji co Blue, s. 16).

SFB wykorzystuje rodzinę $\mathcal{B}$ wektorów $B$, z czego każdemu wektorowi $B$ ($|B| ~ozn.~ N$) przyporządkowana jest jedna funkcja haszująca z $H$ ($|H| = |\mathcal{B}| ~ozn.~ L$) (rys). Jako element z $B_i$ przechowywana jest struktura $b_n$, gdzie $n$ jest numerem połączenia. Jest to struktura dwóch wartości:

• $x_n.q_{len}$ – długość kolejki zajęta przez pakiety połączenia $n$,
• $x_n.p_m$ – prawdopodobieństwo odrzucenia/zaznaczenia pakietu dla tego połączenia.

Funkcje haszujące działają na takich samych zasadach jak przy SFQ. Mogą być liczone po połączeniach, adresach źródła, przeznaczenia lub na parach źródło-przeznaczenie. Tak samo też jak w SFQ, funkcje haszujące powinny być zmieniane co jakiś czas. Z ta różnicą, że filtr Blooma ,,wysyca się'' (z powodu stałego przyrostu nowych połączeń, lub żródeł/przeznaczeń) i należy go co jakiś czas wyzerować. Oczywiście praca algorytmu na dopiero co wyzerowanym filtrze powodowałaby nieprawidłowe działanie. Może tu pomóc podwójne buforowanie zastosowane w linuksowej wersji algorytmu[1]. Utrzymywane są dwa zestawy filtrów uaktualniane równolegle, ale tylko jeden jest używany do wykrywania niekontrolowanych połączeń i odczytywania $p_{min}$. Co jakiś czas algorytm przełącza się na drugi filtr, zerując pierwszy i zmieniając jego funkcje haszujące, by potem przełączyć się na pierwszy, zerując drugi i zmieniając jego funkcje haszujące.

Interesującą cechą SFB w porównaniu do chociażby SFQ, jest zachowanie kolejności FIFO. Kiedy w SFQ zmieni się funkcja haszująca, przez moment pakiety z tego samego połączenia mogą znależć się w różnych kolejkach. Wtedy może się zdarzyć, że kolejny pakiet szybciej zostanie zdjety ze swojej kolejki niż poprzedzający. W algorytmie SFB nie ma wirtualnych kolejek, więc zmiana funkcji haszujących nie może spowodować zamiany kolejności pakietów. Nie jest to jednak znaczący atrybut w sieciach opartych głównie na protokole TCP/IP który jest odporny na przemieszanie kolejności pakietów.

Wspomniana wcześniej implementacja linuksowa autorstwa Juliusza Chroboczka (nie włączona do jądra Linuksa) pozwala zdefiniować maksymalną oraz pożądaną długość wirtualnych kolejek ($q_{len}$) za pomoca parametrów odpowiednio $max$ i $target$. Algorytm funkcjonuje z wykorzystaniem ECN. Pakiety sa zaznaczane jeśli $q_{len} \le max$ a odrzucane jeśli $q_{len} > max$. Dodatkowo wprowadzona została modyfikacja oryginalnego SFB. Mianowicie, pakiety zaczynają być także odrzucane w odróżnieniu od zaznczania, jeśli $p_m > 0.5$. Pakiety są wtedy zaznaczane z prawdopodobieńśtwem $p_m (1.5 - 2 p_m)$ a odrzucane z prawdopodobieństwem $p_m (2 p_m - 0.5)$.

Chociaż SFB nie jest algorytmem kolejowania (działa zgodnie z zasadą FIFO), to można na jego wyjściu podłączyć inny algorytm, np. kolejkujący SFQ.

1. [^] http://www.pps.jussieu.fr/~jch/software/sfb