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

CBQ – Estymator i Planista

Implementacja estymatora

Przykładowa implementacja estymatora może używać wykładniczej ważonej średniej ruchomej (jak w RED). Niech $s$ będzie wielkością ostatnio wysłanego pakietu w bajtach, $b$ pasmem przydzielonym klasie w ramach współdzielenia łącza, a $t$ czasem pomiędzy końcem wysyłania ostatniego pakietu a poprzedzającego go. Idealny czas pomiędzy końcami wysłania tych pakietów oznaczmy jako: $$f(s,b) = s/b$$ a różnice między czasem idealnym a rzeczywistym jako $$\mathit{diff} = t - f(a,b)$$ Można zauważyć, że klasa przekracza swój udział jeśli $\mathit{diff} < 0$. Zmiany tej różnicy można więc śledzić by wykrywać, kiedy klasa jest nad limitem. Zatem ze wzoru na średnią ruchomą mamy: $$avg \leftarrow (1-w)avg + w \cdot \mathit{diff} $$ Optymalizację co do parametrów można przeprowadzić taką samą jak dla RED, tzn. tak, by między innymi waga $w$ była ujemną potęgą dwójki, co pozwala uproscić mnożenie do przesunięcia. Waga ta jest parametrem estymatora i mówi, że po wysłaniu $\frac{1}{ln(1-w)}$ pakietów, $avg$ przemieści się o $64\%$ odległości między poprzednią wartością $\mathit{diff}$ a nową. Biorąc pod uwagę przydział danej klasy, odpowiada to czasowi $\frac{-s}{b \cdot ln(1-w)}$ sekund. Wartość $avg$ określa kiedy można wysłać kolejny pakiet. Jeśli $avg \ge 0$, czas kolejnego wysłania ustawiany jest na zero, co oznacza, że klasa jest pod limitem. Jeśli $avg < 0$, czas kolejnego wysłania ustawiany jest o $x$ sekund w przód od czasu aktualnego, gdzie $$\begin{array}{cl} x = -avg \frac{1-w}{w} + f(s,b) &~~~ \textrm{dla klas nieregulowanych} \\ \\ x = f(s,b) &~~~ \textrm{dla klas regulowanych} \end{array}$$ W przypadku klasy nieregulowanej, planista czekając $x$ czasu przed wyslaniem pakietu z tej klasy, będzie miał pewność, że klasa nie pozostanie nad limitem. W przypadku klasy regulowanej, czas wysłania niezależy od średniej ważonej, a więc wcześniejsze wykorzystanie nadmiaru pasma nie umniejsza minimalnego udziału tej klasy w momencie przeciążenia.

Implementacja planistów

Mając ustalone przez estymator czasy kolejnych wysłań, zaimplementowanie planistów jest już prostym zadaniem. Jak już wspomniano podział na planiste generalnego i współdzielącego jest tylko formalny i nie musi mieć odzwierciedlenia w implementacji. Przykładowy algorytm może działać jako planista generalny posługujący się planistą współdzielonym tylko w odpowiednim momencie. Pakiety wysyłane są najpierw z klas o najwyższym priorytecie. Między klasami o jednakowym priorytecie stosuje się algorytm karuzelowy ważony według przydzielonych klasom udziałów. Aby poradzić sobie z klasami o różnych charakterystykach ze względu na wielkości pakietu idealne wydaje się tu zastosowanie wersji deficytowej tego algorytmu.

Zanim jednak planista wyśle pakiet, sprawdza jaki czas wysłania ustawił klasie estymator. Możliwe są 3 przypadki:

• Czas jest zerowy, co oznacza, że klasa nie przekracza swojego limitu – pakiet może być wysłany.
• Czas jest niezerowy, ale mniejszy od bieżącego, co oznacza, że klasa była nad limitem, ale odczekała czas $x$ po którym zeszła pod limit – pakiet może być wysłany.
• Czas jest niezerowy oraz większy od bieżącego, co oznacza, że klasa jest nad limitem. Stosowana jest tutaj zasada współdzielenia określająca czy klasa ma być regulowana czy nie. Jeśli pozostaje nieregulowana – pakiet może być wysłany, jeśli musi być regulowana wywoływana jest procedura planisty współdzielącego.

Planistę współdzielącego można zaimplementować na dwa sposoby. Pierwszy to modyfikacja czasu wysłania na $f(s,b) = s/b$ sekund od bieżacego momentu – wtedy przy kolejnej rundzie planisty generalnego może okazać się, że klasa nie jest już nad limitem i pakiet zostanie wysłany przez planiste generalnego. Drugi sposób to całkowite wyłączenie klasy z listy algorytmu karuzelowego na czas $f(s,b)$. Nie bieże to jednak pod uwagę możliwości wcześniejszego wysłania pakietu po pozytywnym rozpatrzeniu zasady współdzielenia.