Hierarchical Token Bucket

Hierarchical Token Bucket, HTB – algorytm hierarchicznego podziału łącza. Umożliwia on:

• podział pasma na klasy;
• przyporządkowanie różnego rodzaju pakietów IP do odpowiednich klas według różnych kryteriów, na przykład według adresu odbiorcy, adresu nadawcy, wielkości pakietu, protokołu itp.;
• nałożenie reguł i ograniczeń na przepływność dla poszczególnych klas.

HTB zostało włączone do jądra Linuksa poczynając od wersji 2.4.20. Koncepcję HTB opracował i dokonał pierwszej implementacji Martin Devera.

Zbliżone cechy posiada inny algorytm kolejkowania – CBQ (ang. Class Based Queueing).

Token Bucket

Algorytm Token Bucket ma wiele znaczeń, najlepiej jednak jest go rozumieć w kontekście sterowania natężenia ruchu w sieci lub ograniczania pasma. Algorytm jest wykorzystywany do kontrolowania ilości danych transmitowanych w sieci, pozwalając na szybsze ich wysłanie.

Algorytmy sterowania natężeniem ruchu

Istnieją dwie dominujące metody sterowania ruchem: model „cieknącego wiadra” (ang. leaky bucket) i model „wiadra z żetonami” (ang. token bucket). Często algorytm Leaky Bucket utożsamiany jest niesłusznie z algorytmem Token Bucket. Obydwa modele mają odrębne działanie i są używane do różnych celów. Ich różnica polega głównie na tym, że algorytm Leaky Bucket nakłada duży limit na szybkość transmitowanych danych, podczas gdy algorytm Token Bucket pozwala na dokładne ustalenie ograniczenia prędkości transmisji w odniesieniu do różnorodnej wielkości napływających pakietów danych.

Zasada działania algorytmu Token Bucket

Token Bucket to mechanizm kontrolujący, który dyktuje kiedy pakiety danych mogą być przesłane. Token Bucket posługuje się wzorcem w postaci bufora – kubełka (Bucket), do którego wpadają „żetony” (Tokens) z określonym administracyjnie natężeniem. Wysyłanie określonych porcji danych z kolejki powoduje skasowanie żetonu z kubełka. Przepływ danych może więc opróżnić kubełek z żetonów i na skutek tego zostać chwilowo wstrzymany, ograniczając pasmo. Jego brak czy spowolnienie może wypełnić bufor żetonami (tylko do pojemności bufora), pozostawiając pewną rezerwę na chwilowy wzrost natężenia ruchu.

Sytuacje które występują w algorytmie Token Bucket:

• dane wchodzą do TBF (ang. Token Bucket Filter) z natężeniem przepływu żetonów. Wówczas każda porcja ma swój odpowiadający żeton i przechodzi przez filtr.
• dane wchodzą do TBF z natężeniem przepływu mniejszym niż żetony. Ponieważ tylko część żetonów jest „zabierana” przez wychodzące dane, kubełek wypełnia się niewykorzystanymi żetonami.
• jeżeli natężenie danych jest większe niż ustalone natężenie żetonów to mamy do czynienia z przeciążeniem filtra. Pakiety danych mogą być wysyłane do chwili kiedy nie zostaną zużyte wszystkie żetony, które mogłyby się tam nagromadzić. Jeżeli w kubełku nie ma już żetonów pakiety są kasowane.

Parametry związane z algorytmem

• Limit – liczba bajtów oczekujących na żetony (Tokens)
• Latency – maksymalny czas przebywania pakietu w kolejce TBF
• MPU (ang. minimum packet unit) – najmniejszy pakiet przetwarzany przez TBF
• Rate – limit prędkości
• Burst – liczba bajtów na żeton
• Buffer – wielkość bufora na żetony

Zobacz też

• QoS
• CBQ
• IMQ
• HFSC

Linki zewnętrzne

• Strona Martina Devry o HTB (ang.)
• Strona o IMQ i HTB (pol.)