r =
s =
ss =
Klasowe / CBQ / Szczegóły implementacji

Szczegóły implementacji

Algorytm CBQ stał się szybko bardzo popularny, powstało wiele implementacji w systemach z rodziny BSD, Linux, Solaris oraz w systemach wbudowanych urządzeń sieciowych. Można zwrócić uwagę na ich niektóre wspólne cechy [1], wynikające zapewne z dokładnego opisu i propozycji implementacji przez samych autorów. Ich znajomość może znacznie ułatwić konfigurację CBQ powszechnie uważaną za trudną. Każdą klasę charakteryzują parametry:

  • idle – jest to różnica w czasie pomiędzy obliczonym idealnym czasem między dwoma wysłanymi ostatniego pakietami, a rzeczywistym (wzór $\mathit{diff} = t - f(a,b)$);
  • avgidle – jest to aktualna wartość obliczana z parametru idle za pomocą wykładniczej ważonej średniej ruchomej (wzór $avg \leftarrow (1-w)avg + w \cdot \mathit{diff} $); im mniejsza (ponieżej zera) tym klasa wysyła więcej ponad limitem;
  • maxidle – maksymalna wartość avgidle; ograniczenie to jest potrzebne, by klasa nie mogła uzyskać zbyt dużego 'rozpędu' zanim avgidle spadnie do zera podczas natłoku danych w klasie;
  • offtime – czas, który będąca nad limitem klasa powinna przeczekać by móc wysłać kolejny pakiet;
  • minidle – wartość używana do zapamiętania jak bardzo nad limitem (tzn. avgidle < 0) była ostatnio klasa; czasami parametr ten jest pomijany a avgidle resetowany do zera.

Podawanie parametrów maxidle oraz offtime jest niewygodne, dlatego w niektórych implementacjach CBQ (np. linuksowa[2]), parametry te są obliczane automatycznie po określeniu odpowiednio maksymalnego jednorazowego napływu danych w klasie (opcja maxburst) oraz minimalnego (minburst).

Określmy zmienne:

  • $t$ – czas transmisji ostaatniego pakietu
  • $p$ – ułamek łącza przydzielony klasie
  • $g = 1-w$, gdzie $w$ to waga z jaką obliczana jest średnia avgidle
Oczekiwany czas pomiędzy wysłaniem dwóch pakietów to $t/p$, natomiast rzeczywisty $t$, skąd bezczynność klasy $idle = t(1-1/p)$. Średnią avgidle można przedstawić nastepująco: $$\mathit{avgidle} \leftarrow g \cdot \mathit{avgidle} + (1-g) idle$$ Założmy, że początkowo avgidle = maxidle, to po wysłaniu $n$ pakietów $$\mathit{avgidle} = g^n \mathit{maxidle} + \sum_{i=0}^{n-1} g^n (1-g) \mathit{idle} = g^n \mathit{maxidle} + \mathit{idle}(1-g^n)$$ Wyprowadzenie to korzysta z wzoru $\sum_{i=0}^{m} g^i = \frac{1-g^{m+1}}{1-g}$. Jeśli po wysłaniu tych $n$ pakietów avgidle osiągnie zero, to znaczy, że maksymalny jednorazowy napływ pakietów wynosi właśnie $n$ pakietów (tzn. maxburst = n). Zatem, aby pozwolić na taki napływ, górną granicę avgidle należy ustawić według wzoru $$\mathit{maxidle} = t_1 \frac{1}{p-1} \cdot \frac{1-g^n}{g^n} = \frac{t_1 (1-g^n)}{(p-1)g^n}$$ gdzie $t_1$ jest typowym czasem wysłania pakietu (np. czasem wysłania średniej wielkości pakietu).

Parametr offtime określa jak długo planista powinien czekać z wysłaniem kolejnego pakietu by klasa nie pozostała nad limitem. Niestety jądra większości systemów operacyjnych (w tym uniksowe) nie pozwalają dokładnie zaplanować zdarzenia w czasie krótszym niż 10 ms (wg. man tc-cbq}, więc lepiej poczekać dłużej i wysłać odpowiednio większą ilość pakietów (tzw. steady-state burst size). Tą ilość określa parametr minburst, oznaczmy go przez $n$. Czas czekania można wtedy wyznaczyć wg wzoru $$\mathit{offtime} = \frac{t_1}{p-1} \left( \frac{1-g^{n-1}}{g^{n-1} - g^n} + 1 \right)$$

Przypisy
  1. [^] Por. Sally Floyd, ,,Notes on Class-Based Queueing: Setting Parameters'', Lawrence Berkeley National Laboratory, luty 1996, s. 1
  2. [^] linux/net/sched/sch_cbq.c
Creative Commons License Content by Michał Pokrywka is licensed under a Creative Commons BY-SA 3.0
Ostatnia znacząca zmiana: 2010-04-28