AKKD

1. Dyscypliny, klasy, filtry
2. PRIO
3. CBQ
   1. Teoria
   2. Estymator i Planista
   3. Szczegóły implementacji
   4. Wykorzystanie
4. HTB
   1. Początki
   2. HTB 3
   3. Wykorzystanie
5. H-FSC
   1. Wstęp
   2. Krzywa usługi
   3. Sposób działania HFSC
   4. Deadline i Eligible time
   5. Virtual time
   6. Szczegóły implementacji
   7. Wykorzystanie

HTB – Hierarchical Token Bucket

HTB powstał w 2001 roku za sprawą Martina Devery, pierwotnie jako implementacja CBQ [1], która miała być zarówno prosta, jak i prezycyjna (bez użycia heurystyki). Zmiany obejmowały zrezygnowanie z pojęcia związania (ang. bounding)) klas na rzecz twardego ograniczenia przepustowości (ang. ceil limit), zamiane estymatora na algorytm oparty o wiadro żetonów, oraz nowego podejścia do formalnej zasady współdzielenia.

Autor proponuje tak zwane podejście iteracyjne, które w pełni implementuje formalną zasadę współdzielenia (oryginalne implementacje CBQ tylko aproksymują tą zasadę). Iteracja odnosi się tutaj do kroczenia najpierw po wszystkich liściach, a potem przechodzenia o poziom wyżej – w odróżnieniu od przyjętego w CBQ kroczenia w górę dla każdego liścia z osobna. Przyjmijmy $L$ jako poziom w którym iteracja aktualnie się znajduje. Początkowo $L=1$. Klasa może pozostać nieregulowana jeśli nie ma przekraczających limit przodków na poziomie $L$. Jeśli okaże się, że żaden liść nie spełnia wymagań (nie da się wybrać pakietu do wysłania), zwiększamy $L$ i powtarzamy procedurę dopóki otrzymamy pakiet, lub $L$ przekroczy poziom korzenia. Pierwsza część zasady (klasa może wysyłać nieregulowana jeśli nie przekracza limitu) jest zapewniona na początku, kiedy $L=1$. Druga część zasady mówi, że klasa nad limitem nie wyśle nieregulowanego pakietu jeśli istnieje niespełniona klasa niższego poziomu. Jest to zapewnione przez rozpatrywanie wszystkich klas iteracyjnie od najniższego poziomu. Algorytm można przyśpieszyć, zapamiętując podczas $L=1$ najniższy poziom, z którego przeglądany liść może pożyczyć pasmo do wysłania pakietu, a następnie wybrać liść o najniższym takim poziomie.

Wspomniana wcześniej zmiana estymatora na wiadro żetonów to z pewnością główna przyczyna popularności algorytmu HTB. Wiadro żetonów równie dobrze jak estymator z CBQ może informować o przekroczeniu przez klase limitu, lecz wystarczają do tego dwa parametry – limit prędkości wysyłania, oraz maksymalnyn jednorazowy napływ (wielkość wiadra). Upraszcza to diametralnie konfigurację. Dodatkowo wiadro żetonów nie jest zależne od sprzętu (od ziarnistości zegara systemowego), działa więc tak samo na każdej architekturze sprzętowej. Jedyna modyfikacja wiadra polega na tym, że wiadro oprócz zliczania pakietów mieszcących się w wiadrze (tzw. pakietów pozytywnych), zlicza też pakiety niemieszczące się (negatywne). Jest to wymagane, by klasa będąca nad limitem, mająca dziecko pod limitem i wysyłajace dane, mogła być wciąż zliczana.

Zaadresowany został jeszcze jeden problem związany z CBQ, a konkretnie z zastosowanym w planiscie generalnym deficytowym algorytmie karuzelowym (DDR). W sytuacji kiedy klasa często zmienia swój stan z regulowanej na nieregulowaną, jest często pomijana przez DRR. W CBQ jednak nie było to uciążliwe z powodu dużej bezwładności wynikajacej z zastowoania średniej ruchomej. W momencie kiedy zastosowane zostało wiadro żetonów szybkość wykrywania przekroczenia limitu wzrosła do porównywalnej z czasem obiegu algorytmu karuzelowego, co sprawiło, że problem zaczął być uciążliwy. Prostym rozwiązaniem okazało się utrzymywanie oddzielnych pół deficytowych oraz oddzilenych wskaźników dla każdego poziomu.

Algorytm, okazał się niestety od 2 do 5 razy wolniejszy od CBQ[2]. Jego niekwestionowaną zaletą była jendak precyzja w działaniu, a wymagania sprzętowe nie stanowiły przeszkody dla wydajnych serwerów lub w zastosowaniach domowych gdzie ilość danych nie byłą znaczna. Problem pojawiał się dopiero w urządzeniach osadzonych, które z zastosowaniem innych algorytmów potrafiły przesyłać dane z dużą prędkością, lecz w przypadku HTB moc obliczeniowa nie była wystarczająca.

1. [^] Martin Devera, ,,Hierachical token bucket''
2. [^] Martin Devera, ,,HTB 3 Linux queuing discipline developement''