r =
s =
ss =
Bezklasowe / RED - Losowe Wczesne Wykrywanie: Teoria

RED

Dotychczas opisane algorytmy kolejkowania (oprócz FIFO oczywiście) wymagają wstępnego sklasyfikowania pakietu do danego strumienia. Czasami moze to być niemożliwe, lub zbyt pracochłonne dla urządzenia, szczególnie w sieciach wysokich predkości, które generują ruch rzędu setek tysięcy pakietów na sekundę. Pakiety te pochodzą z dużej ilości źródeł, mogą kumulować się w niektórych momentach, powodując przepełnienie bufora urządzenia, a w wyniku tego masywną globalną synchronizację. Sprawiedliwość podziału pasma między strumieniami schodzi tutaj na drugi plan. Unikanie globalnej synchronizacji od początku sieci komputerowych było ważnym i często dyskutowanym problemem. Jednym z przełomowych pomysłów jest Losowe Wczesne Wykrywanie (ang. Random Early Detection – RED) zaproponowane[1] w 1993 roku przez S. Floyda i V. Jacobsona.

Algorytm RED śledzi średnią kroczącą aktualnej długości kolejki ($avg$), będącą filtrem dolnoprzepustowym chwilowych krótkich przypływów danych. Średnia ta jest porównywana z dwiema wartościami progowymi - minimalną ($min_{th}$) oraz maksymalną ($max_{th}$). Jeśli $avg$ jest mniejsza od $min_{th}$ to algorytm nie ingeruje w kolejke. Jeśli $avg$ jest większa od $max_{th}$ to algorytm odrzuca (lub oznacza za pomocą ECN) każdy przychodzący pakiet. Jeśli $avg$ jest pomiędzy dwiema wartościami granicznymi, przychodzący pakiet jest odrzucany z prawdopodobieństwem $p_a$ określonym funkcją zależną od $avg$. Naturalną konsekwencją jest, że największe prawdopodobieństwo odrzucenia ma połączenie wysyłające najwięcej pakietów, a więc to które najprawdopodobniej może doprowadzić do przeciążenia.

Algorytm dla każdego przychodzącego pakietu wykonuje następujące kroki:

  1. Oblicz średnią długość kolejki $avg$
  2. Jesli $min_{th} \le avg < max_{th}$:
    1. Zwieksz $count$ (ilość pakietów od ostatniego odrzucenia/oznaczenia)
    2. Oblicz $p_a$
    3. Z prawdopodobienstwem $p_a$ oznacz/odrzuc pakiet i wyzeruj $count$
  3. W przeciwnym wypadku, jeśli $max_{th} \le avg$
    1. Oznacz/odrzuc pakiet
    2. Wyzeruj $count$
  4. W przeciwnym wypadku $count \leftarrow -1$

Srednią ważoną oblicza się inaczej w zależności od tego czy w kolejce znajdują się pakiety. Jesli kolejka jest niepusta (1): $$avg \leftarrow (1 - w_q) avg + w_q q$$ W przeciwnym wypadku: $$ \begin{array}{cc} m \leftarrow f(t - t_q) \\ avg \leftarrow (1 - w_q)^m avg \end{array} $$ gdzie $a$ to aktualna długość kolejki, $w_q$ to waga określająca szybkość reakcji średniej kroczącej, $t$ jest momentem aktualnym, $t_q$ momentem kiedy kolejka ostatnio stała się pusta, a $f(t)$ jest funkcją liniową na czasie. Drugi przypadek (kiedy kolejka jest pusta) mozna interpretować jako symulację przyjścia $m$ małych pakietów (ilość sterowana funkcją $f(t)$ określającą niejako szybkość łącza).

Prawdopodobieństwo zależne od średniej oraz jej wartości granicznych ($p_b$) poddaje się dodatkowo zależności od tego jak dawno został odrzucony/oznaczony ostatni pakiet otrzymując prawdopodobieństwo docelowe ($p_a$) (2): $$ \begin{array}{c} p_b \leftarrow max_p \frac {avg - min_{th}} {max_{th} - min_{th}} \\ \\ p_a \leftarrow \frac{p_b}{1 - count \cdot p_b} \end{array} $$ Można tutaj wprowadzić także zależność na wielkość pakietu, modyfikując dodatkowo $p_b$: $$p_b \leftarrow p_b \frac{wielkosc\_pakietu}{maksymalna\_wielkosc\_pakietu}$$ W tym wypadku duży pakiet sesji FTP ma większe prawdopodobieństwo niż mały pakiet interaktywnej sesji SSH.

Szybkość reakcji średniej kroczącej określana przez parametr $w_q$ pozwala ustalać jak wielki jednorazowy napływ danych może być przesłany bez rozpoczęcia losowego odrzucania lub oznaczania pakietów. Im większe $w_q$, tym wolniej zmieniać będzie się średnia, a więc tym większy napływ danych może umknąć bez wykrywania przeciążenia. Obliczenie górnej granicy $w_q$ jest więc kluczowym zagadnieniem podczas stosowania RED. Załóżmy, że kolejka jest pusta. Po przyjściu $L$ pakietów, jej wielkość wzrasta o $L$ (tzn. żaden pakiet nie wychodzi z kolejki). Średnia wielkość kolejki z wzoru (1) wynosi więc: $$\begin{array}{rl} avg_L & =~ \sum_{i=1}^L i~w_q (1 - w_q) ^{L-i} \\ & =~ w_q (1 - w_q)^L \sum_{i=1}^L i~(\frac{1}{1 - w_q})^i \\ \\ & =~ L + 1 \frac {(1 - w_q)^{L+1}- 1} {w_q} \end{array}$$ Ostatni krok wykorzystuje przekształcenie[2]$$\sum_{i=1}^L ix^i = \frac {x + (Lx - L - 1) x^{L+1}} {(1 - x)^2}$$ Jeśli chcemy, aby nagły przypływ $L$ pakietów nie powodował jeszcze odrzucania, $avg_L$ musi być mniejsze od $min_{th}$. Korzystając z wyprowadzonego właśnie wzoru, możemy określić, że dla $min_{th} = 5$, a $L = 50$, musimy wybrać $w_q \le 0.0042$.

Implementacja

Autorzy RED poza opisem algorytmu przedstawili szereg optymalizacji jakim można poddać implementacje. Jeśli wzór na średnią ważoną (1) przekształcimy do postaci $$avg \leftarrow avg + w_q(q - avg)$$ a za $w_q$ będziemy podstawiać (ujemne) potęgi dwójki, to zamiast mnożenia można wykonywać znacznie szybszą operację przesunięcia. I rzeczywiście, w linuksowej implementacji[3] Alexey'a Kuznietsova jako parametr nie podaje się $w_q$ lecz $W_{log}$ z którego obliczane jest $w_q = 2^{(-W_{log})}$.

Podobna sytuacja zachodzi w obliczaniu prawdopodobieństwa. Wzór na $p_b$ (2) można przekształcić do $$\begin{array}{c} C_1 = \frac {max_p} {max_{th} - min_{th}} ~~~ ~~~ C_2 = \frac {max_p n_{ht}} {max_{th} - min_{th}} \\ \\ p_b \leftarrow C_1 avg - C_2 \end{array}$$ $C_1$ i $C_2$ są stałe, więc obliczone zostają tylko raz. Jeśli dodatkowo $max_p$ dobierze się tak, by $C_1$ było potęgą dwójki, to $p_b$ będzie wymagało tylko operacji przesunięcia oraz odejmowania. We wspomnianej implementacji linuksowej podaje się parametr $P_{log}$ z którego obliczyć można $max_p = \frac {max_{th} - min_{th}} {2^{P_{log}}}$.

Istnieje dużo wersji algorytmu RED dostosowywanych do różnych sytuacji głównie ze względu na nierównomierność ruchu oraz sprawiedliwość podziału pasma.

ARED

Adaptacyjny RED (Adaptive RED / Active RED)[4] próbuje dostrajać automatycznie RED w trakcie działania. Określa się pożądaną wartość $avg$ nazwaną $target$. Jeśli $avg > target$ to prawdopodobieństwo maksymalne $max_p$ rośnie addytywnie, a jeśli $avg < target$, to $max_p$ maleje multiplikatywnie. Modyfikowanie $max_p$ wpływa bezpośrednio na $avg$ powodując, że $avg$ oscyluje blisko $target$. Algorytm w zamyśle autorów nie miał być optymalny, a jedynie sprawdzający się w niektórych sytuacjach.

Wykorzystanie

Według man tc-red: 

tc qdisc ... red limit *bytes* min *bytes* max *bytes* avpkt *bytes* burst *packets* [ ecn ] [ bandwidth *rate* ] probability *chance*
gdzie:

Przykład z parametrami proponowanymi przez pewne opracowanie (nie pamietam jakie) dla zwykłego połączenia 100 Mbit: 

tc qdisc add dev eth0 root red min 75000 max 225000 probability 0.02 limit 675000 avpkt 1000 burst 120 bandwidth 100000

C.D.N.

Przypisy
  1. [^] Sally Floyd, Van Jacobson, ,,Random Early Detection Gateways for Congestion Avoidance'', IEEE/ACM Transactions on Networking, sierpień 1993
  2. [^] Eldon Hansen, ,,Table of Series and Products'', Prentice Hall, 1975, s. 65
  3. [^] linux/net/sched/sch_red.c
  4. [^] Sally Floyd, Ramakrishna Gummadi, Scott Shenker, ,,Adaptive RED: An Algorithm for Increasing the Robustness of RED's Active Queue Management'', ICSI Networking Group, sierpień 2001
Creative Commons License Content by Michał Pokrywka is licensed under a Creative Commons BY-SA 3.0
Ostatnia znacząca zmiana: 2010-04-28