r =
s =
ss =

AKKD

Nowości Historia i teoria : : Algorytmy bezklasowe : : Algorytmy klasowe : : Klasyfikowanie ruchu (filtry) : : Dobre praktyki

Bezklasowe / Wiadra / Leaky bucket - Cieknące wiadro

Leaky bucket - Cieknące wiadro

Koncepcja cieknącego wiadra pojawiła się już w 1986 roku, kiedy Jonathan Turner określał [1] kierunki rozwoju w erze informacji. Obrazowo, przychodzące pakiety wpadają do określonej wielkości wiadra, które przecieka z pewną określoną prędkością. Wyciek pakietu jest równoznaczny z jego wysłaniem. Jeśli pakiety nadchodzą szybciej niż wyciekają, wiadro napełnia się i w końcu przelewa, co jest równoznaczne z odrzucaniem pakietów. Najprostsza implementacja to utrzymywanie licznika, który zwiększa się w momencie zakolejkowania pakietu, a zmniejsza w momencie wysyłania pakietu z określoną prędkością. Jeśli licznik przekroczy pewną wartość, pakiety są odrzucane.

Na porównaniu do cieknącego wiadra Rene Cruz oparł matematyczny model pomiaru przepływności [2] będący podstawą wielu algorytmów kolejkowania, np. H-FSC. Przepływ danych przez urządzenie, można opisać funkcją $R$, określającą tempo ruchu w strumieniu danych (ang. rate of traffic stream). Wartość funkcji $R(t)$ określa tempo ruchu w chwili $t$. Jako jednostkę tej wielkości najczęściej przymuje się bit na sekundę ($bit/s$). Zatem $\int_x^y R(t) dt$ jest ilością bitów wysłanych w okresie czasu od chwili $x$ do chwili $y$. Przesłanie pakietu może nastąpić natychmiastowo, co na wykresie funkcji $R$ byłoby impulsem o wysokości równej wielkości pakietu. Na przykład funkcja $R_1(t)=L \delta(t-a) dt$, gdzie $\delta(t)$ jest deltą Diraca, odpowiada przesłaniu $L$ bitów danych w chwili $a$. Wynika z tego, że $\int_x^y R_1(t) = L$, jeśli $x \le a \le y$, a zero w przeciwnym wypadku. Dla wygody przyjmuje się, że dla $t < 0$ funkcja $R(t) = 0$.

Idea cieknącego wiadra

Jeśli do wiadra wlewa się woda w tempie okreśłonym funkcją $R(t)$, a w każdej sekundzie przecieka $\rho$ jednostek wody, to ilość wody w wiadrze w chwili $t$ wynosi $$ W_\rho(R)(t) = \max_s \left\lbrace \int_s^t ( R(u) - \rho ) du : s \le t \right\rbrace $$ Należy zwrócić uwagę, że jest to maksimum przy zmiennym $s$. Funkcja ta pozwala zdefiniować ograniczenie przepływności postaci $$ W_\rho(R)(t) \le \sigma $$ dla każdego $t$, gdzie $\sigma$ jest nieujemną stałą. Skrótowo, ograniczenie to zapisuje się za pomocą relacji $R \sim (\sigma, \rho)$. Z definicji funkcji $W(R)$ możemy ograniczenie to zapisać jako $$\int_s^t R(u)du \le \sigma + \rho(t-s)$$ dla każdego przedziału czasu $[s, t]$, lub bardziej ogólnie: $$\int_s^t R(u)du \le b(t-s) ~~~ ~~~ ~~~ (1)$$ gdzie $b(t)$ jest nieujemną niemalejącą funkcją. Skrótowy zapis przyjmuje wtedy postać $R \sim b$. Zdefiniujmy dla każdego $\rho \le 0$ wielkość $\sigma_\rho = sup \lbrace b(x) - \rho x : x \ge 0 \rbrace$. Wtedy dla każdego $\rho$ mamy $b(x) \le \sigma_\rho + \rho x$, a zatem z ograniczenia $R \sim b$ wynika $$W_\rho(R)(t) \le \sigma_\rho ~~~ ~~~ ~~~ (2)$$ dla każdego $t$ i $\rho \ge 0$. Co więcej, jeśli $b$ jest wklęsła, to z (2) wynika (1).

Algorytm cieknącego wiadra przede wszystkim ogranicza przesył danych ale także reguluje. W sieciach ATM stosuje się metode podwójnej regulacji zwanej Podwójnym Cieknącym Wiadrem[3] (ang. Dual Leaky Bucket) Można to zobrazować jako dwa wiadra jedno pod drugim. Pierwsze wiadro jest mniejsze (ale o większej dziurze), reguluje więc krótkoterminowe napływy danych, natomiast drugie wiadro jest większe, ale o mniejszej dziurze, więc reguluje długoterminowe fale ruchu.

Przypisy

Content by Michał Pokrywka is licensed under a Creative Commons BY-SA 3.0
Ostatnia znacząca zmiana: 2010-04-28