s =
ss =
Nowości
Historia i teoria : :
Algorytmy bezklasowe : :
Algorytmy klasowe : :
Klasyfikowanie ruchu (filtry) : :
Dobre praktyki
W wielu sytuacjach, gdzie napływające fale pakietów sa duże, ciężko ustalić parametry RED tak, by jego bezwładność i efektywność odpowiadała potrzebom ruchu. Przedstawiając[1] w 1999 roku algorytm Blue, W. Feng, D. Kandlur, D. Saha i K. Shin mieli na celu stworzyć algorytm funkcjonujący jak RED, ale potrafiący się sam konfigurować. W wyniku tego powstał algorytm zrywający z podstawowymi założeniami jakich trzymały się dotychczasowe pomysły. Przede wszystkim, należało porzucić wykrywanie przeciążenia jedynie na podstawie zajętości bufora. Taka informacja, niezależnie czy mierzona bezpośrednio, czy za pomocą średniej kroczącej, jest niewystarczająca by określić powagę przeciążenia, a w szczególności ilość rywalizujących aktualnie połączeń. Autorzy Blue pokazują, że niedostosowany do sytuacji RED (wynikający nie z nieprawidłowego skonfigurowania algorytmu lecz z chwilowej zmiany sytuacji, np. zwiększona ilość rywalizującyc połączeń) poddaje się globalnej synchronizacji powodując nierównomierny przepływ danych oraz niską utylizację łącza.
Idea działania Blue jest bardzo prosta. Wykrywanie przeciążenia opiera się bezpośrednio na utracie pakietów i stopniu wykorzystania pasma. Algorytm przechowuje pojedyńczą zmienną $p_m$ oznaczającą prawdopodobieństwo odrzucenia/zaznaczenia pakietu w momencie zakolejkowania. Jeśli łącze odrzuca pakiety z powodu przepełenienia bufora, $p_m$ rośnie, natomiast jeśli łącze jest nieaktywne, $p_m$ maleje. Algorytm więc niejako uczy się właściwego prawdopodobieństwa z jakim należy odrzucać pakiety by nie doprowadzić do przeciążenia. Adaptuje się więc do nowej sytuacji w momencie zmiany charakterystyki ruchu. Wzrost $p_m$ można uaktywniać trochę wcześniej, jeśli długość kolejki przekroczy pewną wartość. Dodatkowo wprowadzona jest zmienna $freeze\_time$, określająca minimalny odstęp czasu pomiędzy dwiema modyfikacjami zmiennej $p_m$, filtruje to krótkotrwałe przeciążenia, na które nie trzeba reagować. Możnaby w tym momencie powiedzieć, że jest to w rzeczywistości takie same zachowanie jak w przypadku RED. Uaktywnienie wzrostu $p_m$ odpowiada przekroczeniu w RED wartości $min_{th}$, a $freeze\_time$ to waga $w_q$ odpowiadająca za szybkość reakcji średniej ważonej. Jednak w algorytmie Blue prawdopodobieństwo nie jest określone proporcjonalnie do średniej długości kolejki, co pozwala na zachowanie większej jego stabilności, a wartość $freeze\_time$ można randomizować. Obie te cechy mają bezpośredni wpływ na "rozbicie" ewentualnej zbliżającej się globalnej synchronizacji.
Sposób w jaki prawdopodobieństwo $p_m$ ma rosnąć lub maleć jest dowolny. Najprostrzym rozwiązaniem, ale sprawdzającym się w praktyce jest zdefiniowanie stałych $d_1$ oraz $d_2$. Jeśli $p_m$ ma rosnąć to dodajemy do niego $d_1$, a jeśli ma maleć, to odejmujemy $d_2$. Zmiana $p_m$ oczywiście nie wykonuje się jeśli od poprzedniej zmiany nie upłynął czas $freeze\_time$.
Przypisy
|
Content by Michał Pokrywka
is licensed under a Creative Commons BY-SA 3.0 Ostatnia znacząca zmiana: 2010-04-28 |