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

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: sfq i tbf. 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:

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 sfq i tbf.

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:

• enqueue - dodaje pakiet do kolejki
  warto tu zwrócić uwagę, że algorytm nie ma obowiązku takiego pakietu przyjąć - może go odrzucić lub nawet usunąć, co dzieje się między innymi w sytuacjach przepełnienia buforów użytych w implementacjach algorytmów;

• dequeue - wybiera jeden pakiet z kolejki do wysłania
  funkcja ta odpowiada prośbie systemu o wyznaczenie pakietu do wysłania. Wiele algorytmów, w tym algorytmy kształtujące ruch, potrafi odmówić wybrania pakietu, nawet jeśli w danej chwili obsługiwane przez nie kolejki nie są puste;

• requeue - wstawia pakiet z powrotem do kolejki (odwrotność dequeue);

• init - inicjuje nowy algorytm obsługi kolejki;

• destroy - usuwa algorytm i wykorzystywane przez niego dane;

• reset - zeruje informacje o stanie algorytmu, przywracając go do stanu pierwotnego;

• change - zmienia parametry algorytmu.

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

• zmiany kolejek wykorzystywanych przez udostępniany przez niego algorytm (graft, leaf, get, put, change, delete i walk),

• operacji na dołączonych do tych klas filtrach (tcf_chain, bind_tcf, unbind_tcf),

• odpowiedzi na pytanie o aktualną konfigurację klasy (dump).

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.