Leaky Bucket

Leaky bucket – algorytm odpowiedzialny za kształtowanie przepływu ruchu na przykład w celu utrzymania jakości obsługi (QoS) w sieciach^[1][2]. Algorytm ma za zadanie wyrównanie ruchu i ograniczenie impulsywnych wybuchów ruchu (ang. burstiness)^[1][2].

Schemat działania algorytmu

Algorytm

Parametrami algorytmu są: wielkość bufora („wiadra”) oraz liczba danych jakie opuszczają bufor w jednostce czasu podana w bajtach lub bitach na sekundę (wielkość „przecieku”)^[1]. Podstawę działania „cieknącego wiadra” stanowi pojedynczy bufor zorganizowany w formie kolejki FIFO. Kolejka przepuszcza pakiety póki nie osiągnięto limitu przepływu i gromadzi jest w „wiadrze” jeśli limit przepływu został osiągnięty. W wypadku zbyt dużego ruchu „wiadro” się przepełnia i pakiety zostają odrzucone^[2].

W praktyce liczba danych „cieknących” na dole może być regulowana przez zbiór tokenów, który jest uzupełniany z określoną częstotliwością. Jeśli token jest dostępny, to pakiet przechodzi dalej. Jeśli nie ma tokenu, to pakiet jest odkładany w pamięci kolejki. Kolejka przestaje przyjmować pakiety gdy jest pełna (pakiety zostają odrzucone)^[1].

Wady i rozwiązania

Jedna z wad tego algorytmu jest to, że trzeba z góry znać charakterystykę danego, co jest konieczne do ustalenia odpowiednich parametrów „wiadra”^[1]. Istnieją metody oszacowania prawdopodobieństwa utraty pakietów oraz potencjalnych opóźnień.

W wypadku użycia pojedynczego wiadra problemem jest również jednolite traktowanie ruchu, który może mieć różne charakterystyki (dane strumieniowe jak film czy muzyka, kontra dane tekstowe jak kod stron internetowych).

W sieciach ATM rozwiązaniem dla obu problemów może być użycie wielu cieknących wiader (ang. multiple leaky bucket, MLP) z parametrami ustalanymi przez sieci neuronowe^[3].

Zobacz też

• Quality of service
• Asynchronous Transfer Mode
• Hierarchical Token Bucket
• Średnia ruchoma