next up previous contents
Następny: Moduł sch_ep Nadrzędny: Wykonawca Poprzedni: Opis ogólny   Spis rzeczy


Kolejkowanie ruchu w systemie Linux

Komputery w sieci lokalnej żądają najczęściej - co jest jednym z powodów tej pracy - większych przepustowości niż udostępniane przez jej łącza wyjściowe. Oznacza to, że przez większość czasu komputer je obsługujący przechowuje pewną liczbę pakietów w buforze związanym z interfejsem wyjściowym i wybiera jeden z nich za każdym razem, gdy dostanie od karty sieciowej informację o zakończeniu transmisji poprzedniego.

Od wersji 2.2.x w jądrze systemu Linux bufory te (nazywane dalej kolejkami) nadzoruje pakiet iproute2, pozwalający na zdefiniowanie algorytmu obsługi kolejki (a dokładniej dwóch, wejściowej i wyjściowej) dla każdego interfejsu sieciowego. Algorytm ten budowany jest z bloków, z których każdy obsługuje dwa podstawowe polecenia: wstawienia pakietu do kolejki oraz wskazania pakietu do wysłania. Bloki te różnią się złożonością i sposobem działania, od prostych kolejek FIFO (np. domyślnie używany moduł pfifo_fast), poprzez kształtujące wielkość wykorzystywanego pasma (np. tbf), do złożonych, dzielących pakiety na klasy, z których każda może być obsługiwana przez inny algorytm wyboru pakietu (jak to się dzieje w przypadku priq, czy najczęściej wspominanego cbq). W ostatnim przypadku możliwe jest stworzenie drzewa klas, w którego korzeniu znajduje się blok odpowiedzialny za obsługę wszystkich pakietów, który wybiera jeden z podwęzłów do realizacji żądań wstawienia lub wyboru pakietu do wysłania. Dodatkową elastyczność zapewnia możliwość zdefiniowania dla każdej z klas listy filtrów, które na podstawie zawartości pakietu czy informacji o nim (np. pól struktury sk_buff, stosowanej przez jądro do opisu pojedynczego pakietu) mogą zdecydować o jego odrzuceniu lub przekierowaniu do innej klasy.

Przykładowa hierarchia wykorzystująca kilka różnych bloków mogłaby wyglądać jak na rysunku 3.3 (przykład z [15]).

Rysunek 3.3: Schemat hierarchii klas wraz z przypisanymi algorytmami kolejkowania
\includegraphics[width=10cm]{./pictures/Mgr_rys4_last_gimp.ps}

Pary numerów oddzielonych dwukropkiem są identyfikatorami klas; oznaczenie 1:0 wskazuje zawsze korzeń drzewa. Prio jest algorytmem, który rozdziela ruch przychodzący do kilku klas na podstawie zawartości pola TOS pakietu (domyślnie ruch ,,ciężki'' trafi do gałęzi 1:3, a ruch interaktywny do 1:1 i 1:2. Gałęzie te są obsługiwane przez niezależne algorytmy: sfqtbf. Kiedy system zażąda od węzła 1:0 wyboru pakietu do wysłania, ten -- zgodnie z regułami algorytmu prio -- będzie przekazywał żądanie kolejno do klas 1:1, 1:2 oraz 1:3 i wyśle pierwszy otrzymany od nich pakiet.

Do budowy algorytmów służy program tc; hierarchię z rys. 3.3 stworzono poleceniami:


\begin{Code}
tc qdisc add dev eth0 root handle 1: prio
tc qdisc add dev eth0 par...
...uffer 1600 limit 3000
tc qdisc add dev eth0 parent 1:3 handle 30: sfq
\end{Code}

Pierwsze z nich przydziela algorytm prio do obsługi klasy 1:0, co powoduje automatyczne utworzenie gałęzi 1:1, 1:2 i 1:3, a kolejne trzy przypisują do nich algorytmy sfqtbf.

Od strony technicznej każdy z algorytmów obsługi kolejki jest opisywany przez strukturę Qdisc_ops zawierającą wskaźniki do udostępnianych przez niego funkcji. Ważniejsze z nich to:

Dodatkowo w strukturze Qdisc_ops znajduje się pole cls_ops, będące wskaźnikiem do struktury Qdisc_class_ops zawierającej funkcje:

Ważnym szczegółem jest to, że żądania enqueue i dequeue, nawet w przypadku wielopoziomowego drzewa klas, wysyłane są przez system tylko do jego korzenia, więc do klasy z identyfikatorem 1:0. Jej algorytm ma całkowitą swobodę jeśli chodzi o ich obsługę, w szczególności może je odrzucić lub skierować do dowolnej innej klasy. Najczęściej oba żądania przekazywane są w dół drzewa wg reguł algorytmów napotykanych po drodze, co oznacza że podczas enqueue pakiet przekazywany jest w stronę liści, a podczas dequeue - w stronę korzenia (wraca wzdłuż ścieżki wywołań funkcji dequeue kolejnych klas jako jej wynik). Wynika z tego, że jeśli algorytm przyjmie pakiet i dostanie potwierdzenie o jego przyjęciu od którejś ze swoich podklas, to (o ile do hierarchii nie zostaną dodane filtry mogące m.in. przekierowywać pakiety do dowolnych klas) będzie też kontrolował jego wybór.


next up previous contents
Następny: Moduł sch_ep Nadrzędny: Wykonawca Poprzedni: Opis ogólny   Spis rzeczy
Marcin Kaszyński, Krzysztof Lorek