Hierarchical Token Bucket

Ten artykuł od 2020-09 wymaga zweryfikowania podanych informacji.

Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Google Books • Google Scholar • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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.

Zobacz też

• QoS
• CBQ
• IMQ
• HFSC

Linki zewnętrzne

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