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 – Deadline i Eligible time

Jak już zostało wcześniej wspomniane, do obliczania czasów nieprzekraczalnych i kwalifikujących utrzymywane są krzywe odpowiednio $D_i(a_i^k, t)$ oraz $E_i(a_i^k, t)$, a oprócz tego zmienna $c_i$ reprezentującą ilość do tej pory wysłanych danych przez kryterium czasu rzeczywistego. Ogólny proces obliczania czasów nieprzekraczalnego i kwalifikującego jest przedstawiony na rysunku poniżej.

H-FSC: Obliczanie czasu nieprzekraczalnego i kwalifikującego
Według: dz. cyt.

Na początku pierwszej aktywności klasy $i$ krzywa $D_i(a_t^k, t)$ jest inicjowana według przypisanej tej klasie krzywej usługi $S_i(t)$. Za każdym razem kiedy klasa znów staje się aktywna, krzywa $D_i(a_t^k, t)$ inicjowana jest według wzoru: $$ D_i(a_t^k, t) = min(D_i(a_i^{k-1}, t), S_i(t-a_i^k) + c_i(a_i^k)), ~~~ t \ge a_i^k $$ gdzie $c_i(a_i^k)$ oznacza wartość zmiennej $c_i$ w chwili $a_i^k$. Ponieważ $c_i$ nie zmienia się kiedy pakiety wysyłane są w kryterium współdzielenia, to nie trzeba wtedy uaktualniać krzywych. Wystarczy jedynie obliczenie czasu nieprzekraczalnego $d_i$, gdyż mogła się zmienić długość pakietu na szczycie klasy.

Czas kwalifikujący jest używany do rozpoznawania czy należy użyć kryterium czasu rzeczywistego. Niech $E(t)$ bedzie najmniejszą ilościa usługi jaką otrzymać powinna każda aktywna klasa do chwili $t$ tak, by niezależnie od nadchodzących danych, zbiorczy czas usługi wymagany przez wszystkie klasy przez jakikolwiek przyszły przedział czasu $(t,t')$ nie mogł przekroczyć $R \cdot (t'-t)$, gdzie $R$ to przepustowość łącza. Jeśli aktywne sesje nie otrzymaja ilości usług przewidywanej przez $E(t)$ to istnieje scenariusz w którym jakaś klasa nie otrzyma wystarczającej ilości usługi by spełnić swoją krzywą $S_i(t)$. Najgorszy z możliwych scenariuszy to sytuacja kiedy wszystkie klasy od momentu $t$ zaczynają być stale aktywne. Jeśli aktywność ta pozostaje do chwili $t'$ to mamy: $$ E(t) = \sum_{i \in \mathcal{A}(t)} D_i(a_i; t) + \left[ \max_{t'>t} \left( \sum_{i \in \mathcal{A}(t)} \left(D_i(a_i;t') - D_i(a_i;t)\right) + \sum_{i \in \mathcal{P}(t)} \left(D_i(t;t')-D_i(t;t)\right) - R \cdot (t' - t) \right) \right]^{+} $$ gdzie:

• $a_i$ – czas kiedy ostatnio klasa $i$ rozpoczęła swoją aktywność,
• $\mathcal{A}(t)$ – zbiór aktywnych klas w chwili $t$,
• $\mathcal{P}(t)$ – zbiór pasywnych klas w chwili $t$,
• $[x]^{+} \equiv \max(x,0)$.

Powyższe równanie można wytłumaczyć następująco: W najgoryszm przypadku wszystkie aktywne klasy pozostają aktywne do chwili $t'$, a wszystkie pasywne klasy stają się aktywne w chwili $t$ i pozostają aktywne do chwili $t'$. Aktywne sesje potrzebują więc $\sum_{i \in \mathcal{A}(t)} \left(D_i(a_i t') - D_i(a_i;t)\right)$ usługi, a pasywne $\sum_{i \in \mathcal{P}(t)} \left(D_i(t;t')-D_i(t;t)\right)$. Wszystkie sesje razem mogą otrzymać maksymalnie $R \cdot (t' - t)$ usługi, a otrzymały juz $\sum_{i \in \mathcal{A}(t)} D_i(a_i; t)$ usługi. Można więc stworzyć algorytm, który rozdziela w kryterium czasu rzeczywistego $E(t)$ usługi, a nadmiar w kryterium współdzielenia. Niestety ten sposób jest mało efektywny, gdyż powyższe równanie wymaga obliczania krzywej $D_i(a_i; t)$ dla wszystkich klas, także pasywnych. Krzywe te zależą także od czasów rozpoczęcia ostatniej aktywności (wcześniejszy wzór na $D_i(a_t^k, t)$) co jeszcze bardziej komplikuje obliczenia. Dodatkowo, dodawanie do siebie dużej ilości krzywych, które najczęściej są dwuelementowymi krzywymi liniowymi, powoduje powstanie dla $E(t)$ wieloelementowej krzywej trudnej do implementacji.

Krzywa $E(t)$ jest więc w H-FSC aproksymowana od ,,bezpiecznej'' strony (z punktu widzenia gwarantowania krzywych usług). Zauważmy, że dla każdego $t$ prawdziwe są zależności: $$ D_i(t; t') - D_i(t;t) \le S_i(t-t'), ~~~ t' \ge t $$ $$ \sum_{i} S_i(t) \le R \cdot t $$ Wykorzystując je, możemy wyprowadzić dużo prostsze równanie na $E(t)$: $$ \begin{array}{rl} \displaystyle E(t) & = \sum_{i \in \mathcal{A}~(t)} D_i(a_i; t) + \left[ \max_{t'>t} \left( \sum_{i \in \mathcal{A}~(t)} \left(D_i(a_i t') - D_i(a_i;t)\right) + \sum_{i \in \mathcal{P}~(t)} \left(D_i(t;t')-D_i(t;t)\right) - R \cdot (t' - t) \right) \right]^{+} \\ & \le \sum_{i \in \mathcal{A}~(t)} D_i(a_i; t) + \left[ \max_{t'>t} \left( \sum_{i \in \mathcal{A}~(t)} \left(D_i(a_i t') - D_i(a_i;t)\right) + \sum_{i \in \mathcal{P}~(t)} \left( S_i(t-t') \right) - R \cdot (t' - t) \right) \right]^{+} \\ & \le \sum_{i \in \mathcal{A}~(t)} D_i(a_i; t) + \left[ \max_{t'>t} \left( \sum_{i \in \mathcal{A}~(t)} \left(D_i(a_i t') - D_i(a_i;t)\right) + \sum_{i \in \mathcal{P}~(t)} \left( S_i(t-t') \right) - \sum_{i \in \mathcal{A}~(t) \cup \mathcal{P}~(t)} \left( S_i(t-t') \right) \right) \right]^{+} \\ & = \sum_{i \in \mathcal{A}~(t)} D_i(a_i; t) + \left[ \max_{t'>t} \left( \sum_{i \in \mathcal{A}~(t)} \left(D_i(a_i t') - D_i(a_i;t) - S_i(t-t')\right)\right)\right]^{+} \\ & \le \sum_{i \in \mathcal{A}~(t)} \left( D_i(a_i; t) + \left[ \max_{t'>t} \left(D_i(a_i t') - D_i(a_i;t) - S_i(t-t')\right)\right]^{+}\right) \end{array} $$

Po tym przekształceniu łatwo określić krzywą kwalifikującą dla pojedyńczej klasy: $$ E_i(a_i;t) = D_i(a_i; t) + \left[ \max_{t'>t} \left(D_i(a_i t') - D_i(a_i;t) - S_i(t-t')\right)\right]^{+}, ~~~ t \ge a_i $$ Równanie to określa maksymalną ilość usługi jaka otrzymać powinna klasa $i$ w kryterium czasu rzeczywistego do chwili $t$. Krzywa ta jest obliczana za każdym razem gdy klasa $i$ staje się aktywna. Istnieją dwa przypadki szczególne kiedy wyznaczanie $E_i(a_i,t)$ jest jeszcze prostsze. Jeśli krzywa usługi jest wklęsła, to $E_i(a_i,t) = D_i(a_i;t)$. Wklęsłość krzywej usługi oznacza, że zapotrzebowanie nie będzie rosło, więc nie trzeba go przewidywać. Natomiast jeśli krzywa usługi jest dwuelementowa, wypukła, o nachyleniu pierwszego elementu $\beta$, to $E_i(a_i,t)$ mozna przybliżyć za pomocą prostej o nachyleniu $\beta$. Na takich dwóch rodzajach krzywych usług skupia się implementacja H-FSC. Wystarcza to by zachować najważniejsze właściwości krzywych usług, czyli określanie minimalnego opóźnienia niezależnie od docelowej przepustowości.