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

H-FSC – Virtual time

Pojęcie czasu wirtualnego wykorzystane było już przez Johna Nagle'a w 1987 roku (patrz Fair Queuing), oraz kontynuowane przez większość algorytmów ,,sprawiedliwego kolejkowania''. Każdy z tych algorytmów oblicza systemowy czas wirtualny $v^s(t)$ oznaczający znormalizowaną ilość usługi jaka każda klasa powinna otrzymać do chwili $t$ oraz dla każdej klasy $i$ wirtualny czas $v_i(t)$ oznaczający znormalizowaną ilość usługi jaką klasa otrzymała do czasu $t$. Dodatkowo obliczany jest też czas zakończenia wysyłania kolejnego pakietu $f_i(t) = s_i(t) + p$, gdzie $p$ to znormalizowana wielkość pakietu. Zadaniem algorytmu jest wysyłanie pakietów w takiej kolejności by rozbieżności pomiędzy klasami w czasach $v_i(t)$ były jak najmniejsze (Jest to algorytm typu SSF (Smallest Start First); inna możliwość to np. SFF (Smallest Finish First)), w której pilnowane są rozbieżności pomiędzy $f_i(t)$}. Kryterium współdzielenia działa w H-FSC na tej samej zasadzie. Czasy wirtualne wewnątrz hierarchii (tzn. dla klas nie będących liśćmi) obliczane są według wzoru $$ v_i(t) = \frac{v_{i,min} + v_{i,max}}{2} $$ gdzie $v_{i,min}$ oraz $v_{i,max}$ są odpowiednio najmniejszym i największym czasem wirtualnym spośród wszystkich aktywnych dzieci klasy $i$. Czas wirtualny obliczany jest dla klasy iteracyjnie używając poprzedniego czasu oraz krzywej usługi w momencie rozpoczęcia wysyłania pakietu lub w momencie kiedy klasa staje się aktywna. Czasy w hierarchii obliczają się rekursywnie, to znaczy, że obliczenie czasu wirtualnego dla korzenia wymaga obliczenia czasów dla wszystkich klas. Ze względów implementacyjnych zamiast bezpośrednio $v_i$, oblicza się krzywą $V_i(a_i^k,v)$ będącą odwrotnością krzywej wyznaczonej z kolejnych czasów $v_i$.

H-FSC: Obliczanie czasu wirtualnego
Według: dz. cyt.

Krzywa $V_i(a_i^k,v)$ jest obliczana podobnie jak dwie pozostałe: podczas pierwszej aktywności klasy inicjowana jest krzywą usługi $S_i(t)$, a w momencie rozpoczęcia przez klase każdego kolejnego aktywnego okresu obliczana z wzoru: $$ V_i(a_i^k;v) = min(V_i(a_i^{k-1}; v), S_i(v - v_{p(i)}^s(a_i^k)) + w_i(a_i^k)), ~~~ v \ge v_{p(i)}^s(a_i^k) $$ gdzie $w_i(a_i^k)$ to ilość usługi otrzymana przez klasę $i$ do chwili $a_i^k$, a $v_{p(i)}^s(a_i^k)$ – systemowy czas wirtualny rodzica klasy $i$.