Zarządzanie Kolejkami

1. Bufory i kolejki w obsłudze przeciążenia

Urządzenia sieciowe przekazujące ruch, od domowego routera po przełącznik operatorski, używają buforów podzielonych na jedną lub więcej kolejek. przechowuje pakiety, gdy tempo ich przyjęcia przewyższa chwilową możliwość transmisji. Bufor oddziela chwilę przyjęcia pakietu od chwili obsługi przez interfejs i pozwala obsłużyć krótkotrwałą konkurencję wielu wejść o to samo wyjście.

Rozważmy router z wieloma portami wejściowymi i jednym portem wyjściowym. Gdy pakiety z kilku wejść są kierowane do tego samego łącza, a ich łączna szybkość napływu przekracza pojemność łącza, powstaje wąskie gardło. Router nie może przesyłać danych szybciej, niż pozwala na to fizyczne łącze. Pakiety oczekujące trafiają do kolejki przypisanej do portu wyjściowego. Pojemność bufora ogranicza liczbę pakietów, które można przechować przed transmisją. Po zapełnieniu bufora urządzenie musi zastosować regułę odrzucania, chyba że mechanizm AQM oznaczy lub odrzuci pakiet wcześniej.

Kolejki pokazują, gdzie przeciążenie wpływa na przekazywanie pakietów. Zarządzanie kolejkami obejmuje wybór pakietów przechowywanych w buforze oraz reguły ich odrzucania lub oznaczania. Planista określa kolejność transmisji i udział pasma poszczególnych klas. Oba mechanizmy wpływają na opóźnienie, zmienność opóźnienia i utratę pakietów, dlatego należą do podstawowych elementów wdrażania Jakości Usługi (QoS). Konfiguracja musi uwzględniać pojemność bufora, przepustowość wyjścia i wymagania aplikacji.

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

FIFO to prosta dyscyplina kolejkowania. W urządzeniu obsługującym ruch typu best-effort może być używana wtedy, gdy nie skonfigurowano jawnej polityki QoS. Nie przypisuje pakietom klas ani wag, więc decyzja planisty opiera się na kolejności przyjęcia. Przy pełnej kolejce nowe pakiety podlegają zwykle odrzuceniu zgodnie z polityką urządzenia.

Jak Działa FIFO

Router używający FIFO ma pojedynczą kolejkę dla danego interfejsu wyjściowego. Pakiety docierające do interfejsu są umieszczane na końcu kolejki, a planista pobiera je z początku w kolejności przyjęcia. Przy wielu przepływach ta sama zasada obejmuje cały ruch kierowany przez interfejs.

Zalety FIFO

Prostota: Wymaga małego narzutu obliczeniowego i prostego zarządzania pamięcią, więc łatwo ją zaimplementować.
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.

Ograniczenie FIFO: brak różnicowania

FIFO traktuje wszystkie pakiety według jednej kolejności i nie uwzględnia priorytetu ani wymagań aplikacji. Może to prowadzić do . Jeśli duży pakiet o niższym priorytecie, na przykład fragment pobieranego pliku, znajdzie się na początku kolejki, zostanie przesłany przed małymi pakietami wrażliwymi na opóźnienie, takimi jak pakiet VoIP lub żądanie DNS. Pakiety te czekają do zakończenia transmisji dużego pakietu, co zwiększa opóźnienie ruchu czasu rzeczywistego i może zwiększyć jego zmienność. Jedna kolejka nie zapewnia także ochrony dla konkretnego typu aplikacji.

3. Kolejkowanie priorytetowe (PQ)

Kolejkowanie priorytetowe (PQ) rozszerza FIFO o klasyfikację ruchu na wiele poziomów priorytetu. Jest to klasyczny mechanizm QoS, w którym administrator określa klasy oraz kolejność ich obsługi.

Jak Działa Kolejkowanie Priorytetowe

W PQ router używa wielu kolejek dla jednego interfejsu wyjściowego. Jedna implementacja może zdefiniować cztery poziomy: 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). następnie stosuje bardzo ścisłą regułę:

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.
Dopiero gdy kolejka Wysoka jest pusta, planista spojrzy na kolejkę Średnią.
Dopiero gdy kolejki Wysoka i Średnia są puste, obsłuży kolejkę Normalną, i tak dalej.

Zalety Kolejkowania Priorytetowego

PQ pozwala obsłużyć niewielką ilość ruchu o wysokim priorytecie i małym opóźnieniu przed pozostałymi klasami. Umieszczenie pakietów VoIP w kolejce o wysokim priorytecie powoduje ich obsługę przed ruchem z kolejek o niższym priorytecie, gdy kolejka wysokiego priorytetu zawiera pakiety. Taka preferencja skraca oczekiwanie tej klasy, gdy planista może obsłużyć ją jako pierwszą. Gwarantowane opóźnienie wymaga analizy obciążenia i konfiguracji.

Ryzyko Głodzenia

PQ może pozbawić niższe klasy obsługi, gdy ruch o wysokim priorytecie stale zajmuje odpowiednią kolejkę. Zjawisko to nazywa się głodzeniem. Pakiety z niższych kolejek mogą czekać przez nieokreślony czas, a przy zapełnieniu bufora zostać odrzucone. PQ stosuje się więc przy ograniczonym i kontrolowanym udziale ruchu o wysokim priorytecie oraz przy znanym profilu tego ruchu.

4. Ważone sprawiedliwe kolejkowanie (WFQ)

Ważone sprawiedliwe kolejkowanie (WFQ) oferuje bardziej zrównoważony podział przepustowości między przepływy lub klasy ruchu niż ścisła kolejka priorytetowa. Wagi określają udział poszczególnych kolejek, a kolejność obsługi może uwzględniać rozmiar pakietu i czas jego wirtualnego zakończenia. Jeżeli jedna kolejka nie ma danych, niewykorzystany udział może zostać przydzielony innym kolejkom zgodnie z implementacją.

Jak Działa Ważone Sprawiedliwe Kolejkowanie

WFQ klasyfikuje ruch na przepływy, często na podstawie adresów IP, portów i interfejsów, a następnie przypisuje im logiczne kolejki. Planista porównuje wirtualne czasy zakończenia pakietów i uwzględnia wagi kolejek. W uproszczonym opisie działanie widać w dwóch aspektach:

Podział przepustowości: Przy równych wagach i 10 aktywnych przepływach, które stale mają dane do wysłania, łącze 10 Mbps daje każdemu przepływowi około 1 Mbps. Ogranicza to udział pojedynczego intensywnego przepływu, na przykład dużego pobierania FTP, w zasobach pozostałych przepływów.
Obsługa małych pakietów:WFQ porządkuje pakiety według wirtualnego "czasu zakończenia", czyli chwili, w której zakończyłyby transmisję przy równoległej obsłudze przepływów bit po bicie. Przy takim modelu mniejsze pakiety otrzymują wcześniejszy czas zakończenia, co może skrócić odpowiedź ruchu interaktywnego.

Ważone Sprawiedliwe Kolejkowanie Oparte na Klasach (CBWFQ)

CBWFQ rozszerza WFQ o jawnie zdefiniowane klasy ruchu. Administrator przypisuje każdą klasę do kolejki oraz określa wagę lub gwarantowaną minimalną przepustowość. Przykładowa polityka może mieć następującą postać, a gwarancja zależy od implementacji i konfiguracji:

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.

W czasie przeciążenia planista przydziela klasom co najmniej skonfigurowane wartości, o ile implementacja i konfiguracja zapewniają takie gwarancje. Dodatkowa przepustowość może być dzielona między klasy.

CBWFQ może działać z jedną kolejką ścisłego priorytetu. Taki układ nazywa się kolejkowaniem niskiego opóźnienia (LLQ). Kolejka ruchu czasu rzeczywistego, na przykład VoIP, jest obsługiwana przed pozostałymi klasami, a reszta przepustowości trafia do CBWFQ. Limit pasma kolejki priorytetowej chroni klasy pozostałe przed głodzeniem.

5. Aktywne zarządzanie kolejkami (AQM)

Wcześniejsze mechanizmy opisują głównie kolejność transmisji z niepustych kolejek. kontroluje długość kolejki lub czas oczekiwania pakietu przez wcześniejsze odrzucanie albo oznaczanie pakietów. Oznaczenie ECN wymaga obsługi przez ścieżkę i nadawcę, więc w pozostałych przypadkach AQM sygnalizuje przeciążenie utratą pakietu.

Odrzucanie z końca kolejki i synchronizacja przepływów TCP

Gdy kolejka osiąga limit, często stosuje się odrzucanie z końca kolejki (tail drop). Router odrzuca wtedy kolejne pakiety. Jeżeli odrzucenia dotyczą wielu przepływów TCP w podobnym czasie, może wystąpić globalna synchronizacja TCP. Przepływy reagują zgodnie z zastosowanym wariantem kontroli przeciążenia. W TCP Reno po trzecim powtórzonym potwierdzeniu próg ssthresh ustala się na wartość nie większą niż max(FlightSize / 2, 2 * SMSS), a po przekroczeniu limitu czasu retransmisji okno przeciążenia ogranicza się do jednego pełnego segmentu. Jednoczesne reakcje mogą obniżyć wykorzystanie łącza, po czym następuje ponowny wzrost ruchu.

Losowe Wczesne Wykrywanie (RED)

Jednym z klasycznych algorytmów AQM jest Losowe Wczesne Wykrywanie (RED). Algorytm rozdziela odrzucenia lub oznaczenia w czasie, aby ograniczyć synchroniczną reakcję przepływów. Średnia głębokość kolejki jest wygładzana, więc krótkie impulsy nie muszą od razu wywołać decyzji.

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}$ , RED nie odrzuca pakietów w podstawowym modelu.
Gdy średnia głębokość kolejki jest między $min_{th}$ a $max_{th}$ , pakiety są odrzucane lub oznaczane z prawdopodobieństwem rosnącym liniowo od 0 do skonfigurowanego maksimum, gdy średnia zbliża się do $max_{th}$ .
Gdy średnia głębokość kolejki przekracza $max_{th}$ , pakiety są odrzucane w warunkach wysokiego przeciążenia.

Rozdzielenie decyzji dla różnych przepływów może skłonić sesje TCP do reakcji w różnych chwilach i ograniczyć globalną synchronizację. Progi RED opisują średnią kolejkę i nie są prostym odpowiednikiem fizycznej pojemności bufora. Ważony RED (WRED) jest wariantem uwzględniającym priorytet pakietu, na przykład wartość DSCP, więc pakiety niższej klasy mogą otrzymywać wyższe prawdopodobieństwo odrzucenia. Parametry progów i prawdopodobieństwa wymagają dostrojenia do obciążenia oraz rodzaju ruchu.