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

Linuksowe SFQ (Stochastic DRR)

Linuksowa implementacja SFQ to połączenie pomysłów z DDR i oryginalnego SFQ. Jak zostało to zaznaczone w źródłach[1], algorytm jest dzięki temu bardzo szybki i wykorzystuje bardzo mało pamięci. Nie jest jednak do końca sprawiedliwy z powodu stochastyczności, a także może generować większe opóżnienia z powodu obsługi karuzelowej (patrz Twierdzenie o DRR).

Dodatkowe ograniczenia mające na celu przyśpieszenie działania:

• Maksymalna długość kolejki: 128 pakietów
• Maksymalne MTU $2^{15}-1$ ($32767$)
• Ilość kolejek: 1024 (tzn. że przy ilości połączeń powyżej 1024 mamy pewność ze przynajmniej dwa połączenia nie są odróżniane, przy 512 połączeniach)

Zmiana tych parametrów wymaga przekompilowania modułu.

Istnieje wersja sfq zwana e-sfq pozwalająca na większą kontrolę w działaniu algorytmu. Oryginalnym autorem jest Alexander Atanasov, który popełnił pierwsza wersję esfq w 2002 roku. W 2003 roku za sprawą Corey Hickey powstał patch do kernela 2.6.8, który jednak do tej pory nie został włącozny do głównej gałęzi. W 2008 roku Corey postanowił spróbować dołączyć esfq jako patch do oryginalnego sfq, lecz i to się nie udało.

Wykorzystanie

• depth — ilość wirtualnych slotów do których rozdzielane są pakiety po haszowaniu (standardowo 10),
• divisor — określa ilobitowe ma być haszowanie, im więcej bitów tym mniejsze prawdopodobieństwo kolizji połączeń (standardowo 10, max. 14),
• hash — określa na podstawie czego dokonywane ma być haszowanie:
  • classic — sposób oryginalnego sfq, tzn pakiety grupowane są na podstawie źródła, przeznaczenia oraz portu,
  • dst, src, fwmark — haszowanie jedynie po żródle lub przeznaczeniu pakietu, ewentualnie po markerze z iptables,
  • ctorigdst, ctorigsrc, ctrepldst, ctreplsrc — conntrack original/reply source/destination – haszowanie oparte na oryginalnym adresie źródłowym pakietu (sprzed NATowania/maskarady) lub na podstawie adresu do którego trafić ma odpowiedź na ten pakiet (po ,,odNATowaniu''); informacje te odczytywane są z tablicy conntrack, należy więc upewnić się, że załadowany jest moduł kernela nf_conntrack,
  • ctnatchg — jeśli połączenie jest wychodzące haszowanie odbywa się za pomocą ctorigsrc (podział między klientami internetu (z wewnątrz)), a jeśli przychodzące, to za pomocą ctreplsrc (podział między klientami usług (z zewnątrz)) – jest to dobry wybór jeśli na routerze istnieją przekierowane porty (lub strefa zdemilitaryzowana) do których połączenia także chcemy dzielić sprawiedliwie.

Kilka zależności[2]:

• Maksymalny czas jaki pakiet musi czekać na wysłanie (jeśli nie został odrzucony) to $\mathit{time} = \frac {\mathit{limit} \cdot \mathit{MTU}} {\mathit{rate}}$, gdzie rate to prędkość łącza.}
• Dla pojedyńczego połączenia wysyłającego pakiety najsyzbciej jak może, opóźnienie ograniczone jest zależnością $\mathit{opoznienie} \le \frac {rate} {(\mathit{limit} \cdot \mathit{MTU}}$
• Dla połączenia wysyłającego pojedyńczy pakiet: $\mathit{opoznienie} = \frac {\mathit{rate}} {\mathit{flows} \cdot \mathit{MTU}}$, gdzie flows to ilość równocześnie aktywnych połączeń

Przykłady

Przykład z man tc-sfq zakłądający kolejke sfq na interfejs ppp

tc qdisc add dev ppp0 root sfq perturb 10

Założenie kolejki sfq dla klasy 1:c i nadanie jej uchwytu c:

tc qdisc add dev eth0 parent 1:c handle c: sfq perturb 10 quantum 1500

W przypadku jeśli mamy doczynienia z bardzo słabym sprzętem, na którym sfq nie potrafi wysycić łącza, można sprobować zwiększać jednorazową dawkę dla kolejki (np. do 4xMTU = 6000b):

tc qdisc add dev ppp0 root sfq perturb 10 quantum 6000

Można także użyć opcji limit jeśli uważamy, że kolejka jest za długa, np. chcemy tanim kosztem zwiększyć responsywność w obrębie jednego połączenia:

tc qdisc add dev ppp0 root sfq perturb 10 quantum 6000 limit 64

Jeśli mamy na wyjściu do internetu jakiś algorytm klasowy przypisujący np. wszystkie połączenia typu WWW do klasy 1:12, to w obrębie tej klasy nie można już dzielić pomiędzy klientów internetu, gdyż klasa znajduje się po NATowaniu. Można zastosować tu różne techniki jak np IFB, ale dużo prostrzym rozwiązaniem może być skorzystanie z esfq:

tc qdisc add dev eth1 parent 1:12 handle 12: sfq perturb 10 hash ctnatchg

1. [^] linux/net/sched/sch_sfq.c
2. [^] sfq-2.6.24.1/README