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 – Sposób działania

Idealny model wcielający współdzielenie łącza w hierarchii klas oraz krzywe usług nie może być (zgodnie z poprzednim rozdziałem) osiągnięty. H-FSC balansuje zatem między idealną gwarancją krzywych a efektywnym rozdzielaniem nadmiaru pasma, dążąc możliwie najbliżej obu.

Kolejkowanie w H-FSC dokonuje się według dwóch kryteriów:

• kryterium czasu rzeczywistego (ang. real-time criterion), gwarantującego zgodność z krzywymi usług liści, oraz 
• kryterium współdzielenia (ang. link-sharing criterion), zajmującego się krzywymi klas wewnętrznych oraz rozdzielaniem nadmiaru pasma.

Za każdym razem, gdy istnieje podejrzenie, że krzywa usługi dla jakiegoś liścia zostanie w przyszłości naruszona, wybierane jest kryterium czasu rzeczywistego. W przeciwnym wypadku używane jest kryterium współdzielenia (rys. poniżej).

HFSC: Algorytm główny – postępowanie w momencie odebrania od systemu pakietu przeznaczonego do wysłania, oraz w momencie gotowości urządzenia do wysłania kolejnego pakietu; Prostokąty z podwójnymi bokami odwołują się do kolejnych rysunków;
Według: dz. cyt.

Każdej klasie $i$ będącej liściem przypisana jest trójka $(e_i, d_i, v_i)$, a klasie wewnętrznej tylko $v_i$. Parametry te to:

• $d_i$ – czas nieprzekraczalny związany z pakietem ze szczytu klasy (tzn. zakolejkowanym jako następny do wysłania), czas ten jest używany w kryterium czasu rzeczywistego,
• $v_i$ – czas wirtualny, używany do sprawiedliwego rozdzielania nadmiaru pasma (w kryterium współdzielenia) – czas ten posortowany rosąco ustala kolejność wysyłania pakietów,
• $e_i$ – czas kwalifikujący (ang. eligible), wyznaczający granice między jednym a drugim kryterium.

Czas nieprzekraczalny obliczany jest tak, by zgodność z tymi czasami gwarantowała zgodność z krzywą usługi. Czas kwalifikujący ustawiany jest tak, by pozostało wystarczająco dużo zapasu, jeśli zajdzie sytuacja opisana na rysunku z hierarchią z poprzedniego rozdziału. Pakiet ze szczytu klasy $i$ zostaje zakwalifikowany jako zagrożony (niespełnieniem czasu nieprzekraczalnego) jeśli $e_i > t$ ($t$ - czas aktualny). Jeśli istnieje pakiet zagrożony, to znaczy, że w przypadku użycia kryterium współdzielenia prawdopodobieństwo naruszenia czasu nieprzekraczalnego jest niezerowe. Jeśli nie ma zagrożonych pakietów, kryterium współdzielenia używane jest rekursywnie od korzenia do liścia wybierając kolejne najmniejsze czasy wirtualne pośród rodzeństwa. Czasy te reprezentują pośród rodzeństwa znormalizowaną (po uwzględnieniu wag) ilość usługi jaką każda klasa otrzymała. W idealnie sprawiedliwym środowisku, czasy te powinny być więc zawsze równe. Celem kryterium współdzielenia jest zatem minimalizowanie różnic w czasie wirtualnym pomiędzy klasami o tym samym rodzicu. Z reguły lepiej używać tego kryterium, nawet jeśli łącze jest wysycone, gdyż za każdym razem gdy pakiet wysylany jest wedlug kryterium czasu rzeczywistego, istnieje prawdopodobienstwo, że nie jest to pakiet o najmniejszym czasie wirtualnym. Powoduje to zwiększenie względnej różnicy pomiędzy czasami wirtualnymi a więc oddalenie się od idelnego procesu współdzielenia. Dlatego używanie kryterium czasu rzeczywistego ogranicza się do minimum – tylko jeśli istnieje zagrożenie.

Dla uproszczenia dalszego opisu zdefiniujmy klasę-liścia jako aktywną jeśli ma ona zaległości, oraz klasę wewnętrzną jako aktywną jeśli któryś z jej potomków będących liściem jest aktywny. W przeciwnym wypadku klasa jest pasywna. Do obliczania czasów kwalifikującego, nieprzekraczalnego oraz wirtualnego utrzymywane są dla każdej klasy krzywe odpowiednio $(E_i, D_i, V_i)$. Krzywe te na potrzeby algorytmu przyjmują dwa parametry, na przykład dla czasu kwalifikującego $E_i(a_i^k, t)$, gdzie $a_i^k$ to początek $k$-tego aktywnego okresu klasy $i$. Aktywny okres to taki, w którym klasa była aktywna. Sposób obliczania krzywych $(E_i, D_i, V_i)$ opisany został w kolejnych podrozdziałach.

Organizacja hierarchii klas przedstawiona powyżej niesie za sobą pewne konsekwencje, o których należy pamiętać podczas korzystania z tego algorytmu. Czas nieprzekraczalny wyznaczany jest tylko dla klas będących liśćmi. Oznacza to, że tylko takie klasy mają gwarancję wysłania pakietu nieprzekraczającego określonego opóźnienia oraz z minimalną określoną przepustowością. Należy więc zawsze zadbać o to, by klasyfikacja pakietu, przebiegająca poprzez hierarchię klas, przydzieliła ostatecznie pakiet do liścia.

Warto zaznaczyć dodatkowo, że podczas gdy czas nieprzekraczalny oraz kwalifikujący wyznaczany jest w rzeczywistym czasie wyrażanym w sekundach od pewnej chwili, to czas wirtualny nie jest przypisany do żadnego konkretnego momentu w czasie rzeczywistym gdyż ważne są jedynie różnice pomiędzy klasami.