1. Epicentrum Przeciążenia: Rola Kolejek

W sercu każdego urządzenia sieciowego, które przekazuje ruch, od prostego domowego routera po ogromny przełącznik klasy operatorskiej, znajduje się fundamentalny komponent: bufor, zorganizowany w jedną lub więcej kolejek. Kolejka to tymczasowy obszar przechowujący pakiety danych. Kolejki są niezbędne, ponieważ urządzenia nie zawsze mogą przekazywać pakiety w dokładnie tym samym momencie, w którym one docierają.

Wyobraźmy sobie router z wieloma portami wejściowymi i jednym portem wyjściowym. Jeśli pakiety napływają z kilku różnych wejść, a wszystkie są przeznaczone na to samo łącze wyjściowe, i łączna szybkość ich napływania przekracza pojemność łącza, tworzy się wąskie gardło. Router nie może w magiczny sposób przesyłać danych szybciej, niż pozwala na to fizyczne łącze. Zamiast tego musi umieścić nadmiarowe pakiety w kolejce powiązanej z tym portem wyjściowym. Bez kolejek każdy pakiet, który nie mógłby zostać natychmiast przesłany, zostałby odrzucony, co prowadziłoby do bardzo nieefektywnej i zawodnej sieci.

Dlatego kolejki są epicentrum, w którym przeciążenie sieci staje się fizyczną rzeczywistością. Zarządzanie kolejkami to zestaw algorytmów i strategii używanych przez urządzenie sieciowe do kontrolowania, które pakiety są przechowywane w tych kolejkach, w jakiej kolejności są przesyłane i które pakiety powinny być odrzucone, gdy kolejka nieuchronnie się zapełni. Jest to jeden z najważniejszych mechanizmów wdrażania Jakości Usługi (QoS).

2. Kolejkowanie FIFO (First-In, First-Out)

FIFO to najprostsza i najbardziej podstawowa dyscyplina kolejkowania. Jest to domyślne zachowanie w sieci typu best-effort, gdzie nie skonfigurowano żadnych jawnych polityk QoS.

Jak Działa FIFO

Koncepcja jest identyczna jak w kolejce do kasy w sklepie spożywczym. Pierwsza osoba, która weszła do kolejki, jest pierwszą obsługiwaną. W terminologii sieciowej, router używający FIFO ma pojedynczą kolejkę dla każdego interfejsu wyjściowego. Pakiety docierające do interfejsu są umieszczane na końcu tej kolejki. Router następnie obsługuje pakiety z początku kolejki w dokładnie takiej kolejności, w jakiej dotarły.

Zalety FIFO

• Prostota: Wymaga minimalnego narzutu obliczeniowego i zarządzania pamięcią, co czyni ją szybką i łatwą do zaimplementowania.
• Zachowanie Kolejności: Dla pojedynczego przepływu danych FIFO gwarantuje, że pakiety zostaną przesłane w tej samej kolejności, w jakiej zostały odebrane, zapobiegając dostarczaniu poza kolejnością przez ten router.

Krytyczna Słabość: Brak Zróżnicowania

Główną wadą FIFO jest to, że traktuje cały ruch absolutnie jednakowo. Nie ma pojęcia priorytetu ani wymagań aplikacji. Prowadzi to do poważnego problemu znanego jako blokowanie czoła kolejki. Jeśli duży, niekrytyczny pakiet (np. fragment pobieranego pliku) dotrze na początek kolejki, zostanie on przesłany jako pierwszy. Wszelkie małe, wrażliwe na opóźnienia pakiety (np. pakiet VoIP lub żądanie DNS), które dotrą tuż za nim, muszą czekać, aż duży pakiet zostanie w pełni przesłany. Ten jeden duży pakiet może wprowadzić znaczne opóźnienie dla całego kolejnego, ważniejszego ruchu, poważnie pogarszając wydajność aplikacji czasu rzeczywistego.

3. Kolejkowanie Priorytetowe (PQ): Ścieżka dla VIP-ów

Kolejkowanie Priorytetowe jest jednym z najwcześniejszych mechanizmów QoS zaprojektowanych w celu przezwyciężenia ograniczeń FIFO. Wprowadza ono koncepcję różnicowania poprzez klasyfikację ruchu na wiele poziomów priorytetu.

Jak Działa Kolejkowanie Priorytetowe

W PQ router używa wielu kolejek dla jednego interfejsu wyjściowego, zazwyczaj czterech: Wysoki, Średni, Normalny i Niski. Klasyfikator na wejściu przypisuje każdy nadchodzący pakiet do jednej z tych kolejek na podstawie predefiniowanej polityki (np. na podstawie protokołu, numeru portu lub oznaczenia DSCP). Planista następnie stosuje bardzo ścisłą regułę:

1. Zawsze najpierw sprawdza kolejkę o Wysokim priorytecie. Jeśli w kolejce Wysokiej są jakiekolwiek pakiety, będzie je przesyłać, aż ta kolejka będzie całkowicie pusta.
2. Dopiero gdy kolejka Wysoka jest pusta, planista spojrzy na kolejkę Średnią.
3. Dopiero gdy kolejki Wysoka i Średnia są puste, obsłuży kolejkę Normalną, i tak dalej.

Zalety Kolejkowania Priorytetowego

PQ jest niezwykle skutecznym narzędziem do ochrony niewielkiej ilości krytycznego ruchu o niskim opóźnieniu. Umieszczając na przykład pakiety VoIP w kolejce o Wysokim priorytecie, administrator sieci może zapewnić, że ten ruch doświadczy absolutnie minimalnego możliwego opóźnienia, ponieważ zawsze będzie wysyłany przed jakimkolwiek innym ruchem.

Ryzyko Głodzenia

Absolutny charakter PQ jest również jego największą słabością. Jeśli ilość ruchu o wysokim priorytecie jest wystarczająco duża, aby stale utrzymywać zajętą kolejkę Wysoką, planista nigdy nie będzie miał szansy obsłużyć kolejek o niższych priorytetach. Zjawisko to nazywa się głodzeniem. Pakiety w kolejkach o niższym priorytecie mogą być opóźniane w nieskończoność lub ostatecznie odrzucone z powodu wieku bufora, nigdy nie zostając przesłane. Z tego powodu PQ jest generalnie zalecane tylko wtedy, gdy ilość ruchu o wysokim priorytecie jest dobrze znana i gwarantuje się, że stanowi niewielki procent całkowitej przepustowości łącza.

4. Ważone Sprawiedliwe Kolejkowanie (WFQ): Model Sprawiedliwego Podziału

Ważone Sprawiedliwe Kolejkowanie (WFQ) oferuje bardziej zrównoważone i zaawansowane podejście niż Kolejkowanie Priorytetowe. Zamiast dawać absolutne pierwszeństwo jednemu rodzajowi ruchu, WFQ ma na celu zapewnienie "sprawiedliwego" przydziału przepustowości różnym przepływom lub klasom ruchu, jednocześnie inteligentnie dając preferencyjne traktowanie ruchowi o niskim opóźnieniu.

Jak Działa Ważone Sprawiedliwe Kolejkowanie

WFQ automatycznie klasyfikuje ruch na różne "przepływy" (często na podstawie adresów IP źródłowych/docelowych i portów) i przypisuje każdy przepływ do jego własnej logicznej kolejki. Planista następnie obsługuje te kolejki w trybie karuzelowym (round-robin). "Sprawiedliwość" i "ważenie" wchodzą w grę na dwa sposoby:

• Sprawiedliwy Podział Przepustowości: Planista stara się zapewnić, że każdy przepływ otrzymuje równy udział w przepustowości wyjściowej. Jeśli na łączu 10 Mbps jest 10 aktywnych przepływów, każdy z nich otrzyma około 1 Mbps. Zapobiega to sytuacji, w której jeden, agresywny przepływ (jak duży download FTP) głodzi inne, mniej agresywne przepływy (jak interaktywna sesja Telnet).
• Priorytetyzacja Małych Pakietów: WFQ nie jest czysto karuzelowy. Został zaprojektowany tak, aby priorytetyzować pakiety o niższym "czasie zakończenia", czyli czasie, w którym zakończyłyby transmisję, gdyby wszystkie przepływy były obsługiwane jednocześnie w doskonały, bit po bicie sposób. Ponieważ mniejsze pakiety mają wcześniejszy czas zakończenia, mechanizm ten naturalnie daje wyższy priorytet ruchowi interaktywnemu z małymi pakietami, co radykalnie poprawia czasy odpowiedzi.

Ważone Sprawiedliwe Kolejkowanie Oparte na Klasach (CBWFQ)

Potężnym rozszerzeniem WFQ jest CBWFQ. W tym modelu administrator sieci jawnie definiuje klasy ruchu na podstawie różnych kryteriów i przypisuje każdą klasę do określonej kolejki. Administrator może następnie przypisać wagę lub gwarantowaną minimalną przepustowość każdej klasie. Na przykład, polityka może stanowić:

• Klasa "Głos" ma zagwarantowane 2 Mbps.
• Klasa "Baza Danych" ma zagwarantowane 3 Mbps.
• Klasa "Web" ma zagwarantowane 4 Mbps.
• Cały pozostały ruch trafia do klasy domyślnej.

Planista obsługuje kolejki na podstawie tych wag, zapewniając, że każda klasa otrzyma co najmniej swoją gwarantowaną przepustowość w czasie przeciążenia. Jeśli dostępna jest dodatkowa przepustowość, może ona być dzielona między klasy.

Aby połączyć najlepsze cechy obu światów, CBWFQ jest często używane w połączeniu z jedną kolejką o ścisłym priorytecie. Jest to znane jako Kolejkowanie Niskiego Opóźnienia (LLQ). Mechanizm LLQ tworzy jedną kolejkę o ścisłym priorytecie dla ruchu czasu rzeczywistego (jak VoIP), która jest zawsze obsługiwana jako pierwsza (jak w PQ), a pozostała przepustowość jest sprawiedliwie przydzielana między pozostałe klasy ruchu za pomocą CBWFQ. Zapewnia to minimalne opóźnienie dla głosu, jednocześnie zapobiegając głodzeniu wszystkich innych danych.

5. Aktywne Zarządzanie Kolejkami (AQM)

Poprzednio omówione mechanizmy są "pasywne", ponieważ zajmują się głównie kolejnością transmisji pakietów z niepustych kolejek. Aktywne Zarządzanie Kolejkami (AQM) przyjmuje bardziej proaktywne podejście, mając na celu zapobieganie poważnym przeciążeniom poprzez sygnalizowanie nadawcom, aby zwolnili przed całkowitym zapełnieniem kolejek.

Problem: Odrzucanie z Końca Kolejki i Globalna Synchronizacja

Domyślnym zachowaniem, gdy kolejka jest pełna, jest odrzucanie z końca kolejki (tail drop). Router po prostu odrzuca wszystkie nowo przybywające pakiety. Ma to szkodliwy efekt uboczny zwany globalną synchronizacją TCP. Gdy kolejka się zapełni, pakiety z wielu różnych przepływów TCP są odrzucane jednocześnie. Wszystkie te przepływy TCP wykrywają stratę mniej więcej w tym samym czasie, wszystkie wchodzą w fazę unikania przeciążeń (obcinając swoje okna o połowę), a następnie wszystkie próbują ponownie przyspieszyć w tym samym czasie. Prowadzi to do nieefektywnych cykli niedostatecznego wykorzystania sieci, po których następują fale przeciążeń.

Losowe Wczesne Wykrywanie (RED)

Najbardziej znanym algorytmem AQM jest Losowe Wczesne Wykrywanie (RED). Unika ono globalnej synchronizacji poprzez proaktywne i losowe odrzucanie pakietów.

• RED monitoruje średnią głębokość kolejki, co wygładza krótkotrwałe impulsy.
• Używa dwóch progów: progu minimalnego $(min_{th})$ i progu maksymalnego $(max_{th})$.
• Gdy średnia głębokość kolejki jest poniżej $min_{th}$, żadne pakiety nie są odrzucane.
• Gdy średnia głębokość kolejki jest między $min_{th}$ a $max_{th}$, przychodzące pakiety są odrzucane z prawdopodobieństwem, które rośnie liniowo od 0 do prekonfigurowanego maksimum, w miarę jak średnia kolejka zbliża się do $max_{th}$.
• Gdy średnia głębokość kolejki przekracza $max_{th}$, wszystkie przychodzące pakiety są odrzucane.

Losowo odrzucając pakiety z różnych przepływów w różnym czasie, RED powoduje, że różne sesje TCP zwalniają asynchronicznie, unikając globalnej synchronizacji i utrzymując średnią głębokość kolejki niższą i bardziej stabilną. Ważony RED (WRED) jest popularnym wariantem, który używa priorytetów pakietów (takich jak wartości DSCP), aby odrzucać pakiety o niskim priorytecie z większym prawdopodobieństwem niż pakiety o wysokim priorytecie po wykryciu przeciążenia.