Algorytm Nagle'a

Algorytm Nagle'a jest sposobem na poprawę wydajności sieci TCP/IP poprzez zmniejszenie liczby pakietów, które muszą zostać przesłane przez sieć. Został zdefiniowany przez Johna Nagle'a podczas pracy dla Ford Aerospace . Został opublikowany w 1984 roku jako Prośba o komentarze (RFC) pod tytułem Congestion Control in IP/TCP Internetworks w RFC 896 .

RFC opisuje to, co nazwał „problemem małych pakietów”, w którym aplikacja wielokrotnie emituje dane w małych porcjach, często o rozmiarze tylko 1 bajta . Ponieważ pakiety TCP mają 40-bajtowy nagłówek (20 bajtów dla TCP, 20 bajtów dla IPv4 ), skutkuje to 41-bajtowym pakietem dla 1 bajta użytecznych informacji, co stanowi ogromny narzut. Taka sytuacja często występuje w Telnet , gdzie większość naciśnięć klawiszy generuje pojedynczy bajt danych, który jest natychmiast przesyłany. Co gorsza, w przypadku wolnych łączy wiele takich pakietów może być przesyłanych w tym samym czasie, co potencjalnie prowadzi do załamania się przeciążenia .

Algorytm Nagle'a polega na łączeniu kilku małych wiadomości wychodzących i wysyłaniu ich wszystkich naraz. W szczególności, dopóki istnieje wysłany pakiet, dla którego nadawca nie otrzymał potwierdzenia, nadawca powinien buforować swoje dane wyjściowe, dopóki nie uzyska wartości wyjściowej pełnego pakietu, umożliwiając w ten sposób wysłanie wszystkich danych wyjściowych na raz.

Algorytm

RFC definiuje algorytm jako

wstrzymać wysyłanie nowych segmentów TCP, gdy nadchodzą nowe dane wychodzące od użytkownika, jeśli jakiekolwiek wcześniej przesłane dane w połączeniu pozostają niepotwierdzone.

Gdzie MSS to maksymalny rozmiar segmentu , największy segment, jaki można wysłać tym połączeniem, a rozmiar okna to aktualnie akceptowalne okno niepotwierdzonych danych, można to zapisać w pseudokodzie jako ^{[ potrzebne źródło ]}

    
        
    
 jeśli  są nowe dane do wysłania,  to  jeśli  rozmiar okna ≥ MSS  i  dostępne dane to ≥ MSS , wyślij   teraz  pełny segment MSS,  w przeciwnym razie  , jeśli  w potoku nadal znajdują się niepotwierdzone dane,  następnie  umieść dane w kolejce w buforze, aż do otrzymania potwierdzenia, w  przeciwnym razie  wyślij dane natychmiast  zakończ, jeśli  zakończ, jeśli  zakończ, jeśli

Interakcja z opóźnionym ACK

Algorytm ten źle współdziała z opóźnionymi potwierdzeniami TCP (opóźnionym potwierdzeniem ACK), funkcją wprowadzoną do protokołu TCP mniej więcej w tym samym czasie na początku lat 80., ale przez inną grupę. Przy włączonych obu algorytmach aplikacje, które wykonują dwa kolejne zapisy do połączenia TCP, po których następuje odczyt, który nie zostanie zakończony, dopóki dane z drugiego zapisu nie dotrą do miejsca docelowego, doświadczają stałego opóźnienia do 500 milisekund, „ ACK ”. Zaleca się wyłączenie któregokolwiek z nich, chociaż tradycyjnie łatwiej jest wyłączyć Nagle, ponieważ taki przełącznik już istnieje dla aplikacji czasu rzeczywistego.

Rozwiązaniem zalecanym przez Nagle'a jest unikanie wysyłania przedwczesnych pakietów przez algorytm poprzez buforowanie zapisów aplikacji, a następnie opróżnianie bufora:

Rozwiązaniem na poziomie użytkownika jest uniknięcie sekwencji zapisu-zapisu-odczytu w gniazdach. Pisanie – czytanie – pisanie – czytanie jest w porządku. Pisanie – pisanie – pisanie jest w porządku. Ale pisanie – pisanie – czytanie to zabójca. Więc jeśli możesz, buforuj swoje małe zapisy do TCP i wysyłaj je wszystkie naraz. Używanie standardowego pakietu UNIX I/O i opróżnianie zapisu przed każdym odczytem zwykle działa.

Nagle uważa opóźnione potwierdzenia ACK za „zły pomysł”, ponieważ warstwa aplikacji zwykle nie odpowiada w określonym przedziale czasowym. W typowych przypadkach zaleca wyłączenie „opóźnionego potwierdzenia ACK” zamiast swojego algorytmu, ponieważ „szybkie” potwierdzenia nie powodują tak dużego narzutu, jak wiele małych pakietów.

Wyłączenie Nagle lub opóźnionego ACK

Implementacje TCP zazwyczaj dostarczają aplikacjom interfejs do wyłączania algorytmu Nagle. Nazywa się to zwykle TCP_NODELAY . W systemie Microsoft Windows TcpNoDelay decyduje o wartości domyślnej. TCP_NODELAY jest obecny od stosu TCP/IP w 4.2BSD z 1983 roku, stosu z wieloma potomkami.

Interfejs do wyłączania opóźnionego potwierdzenia ACK nie jest spójny między systemami. Flaga TCP_QUICKACK jest dostępna w systemie Linux od 2001 r. (2.4.4) i potencjalnie w systemie Windows, gdzie oficjalnym interfejsem jest SIO_TCP_SET_ACK_FREQUENCY . Ustawienie TcpAckFrequency na 1 w rejestrze systemu Windows domyślnie wyłącza opóźnione potwierdzenie ACK.

Negatywny wpływ na większe zapisy

Algorytm Nagle stosuje się do zapisów danych o dowolnym rozmiarze. Jeśli dane w pojedynczym zapisie obejmują 2 n pakietów, gdzie jest 2 n -1 pełnowymiarowych segmentów TCP, po których następuje częściowy segment TCP, oryginalny algorytm Nagle'a wstrzymałby ostatni pakiet, czekając na wysłanie większej ilości danych (do wypełnić pakiet) lub ACK dla poprzedniego pakietu (wskazując, że wszystkie poprzednie pakiety opuściły sieć).

W każdym protokołach aplikacji stop-and-wait typu stop-and-wait typu „zatrzymaj się i czekaj” w odpowiedzi na żądanie, w których dane żądania mogą być większe niż pakiet, może to sztucznie narzucić kilkaset milisekund opóźnienia między żądającym a odpowiadającym. Pierwotnie nie uważano tego za problem, ponieważ żaden protokół stop-and-wait bez potoku prawdopodobnie nie jest zaprojektowany do osiągania wysokiej wydajności, więc dodatkowe kilkaset milisekund opóźnienia nie powinno mieć większego znaczenia. Późniejsze udoskonalenie algorytmu Nagle'a, zwane Modyfikacją Minshalla, rozwiązało ten problem za pomocą protokołów stop-and-wait, które wysyłają jedną krótką wiadomość, a następnie czekają na potwierdzenie przed wysłaniem następnej, usuwając motywację do wyłączania algorytmu Nagle'a (chociaż takie protokoły nadal będą ograniczone przez ich projekt do jednej wymiany komunikatów na czas podróży w obie strony w sieci).

Ogólnie rzecz biorąc, ponieważ algorytm Nagle'a jest tylko obroną przed nieostrożnymi aplikacjami, wyłączenie algorytmu Nagle'a nie przyniesie korzyści najbardziej starannie napisanym aplikacjom, które odpowiednio dbają o buforowanie. Wyłączenie algorytmu Nagle'a umożliwi aplikacji przesyłanie wielu małych pakietów w sieci jednocześnie, zamiast mniejszej liczby dużych pakietów, co może zwiększyć obciążenie sieci i może, ale nie musi, poprawić wydajność aplikacji.

Interakcje z systemami czasu rzeczywistego

Aplikacje, które oczekują odpowiedzi w czasie rzeczywistym i małych opóźnień , mogą słabo reagować z algorytmem Nagle'a. Aplikacje, takie jak sieciowe gry wideo dla wielu graczy lub ruch myszy w zdalnie sterowanym systemie operacyjnym, oczekują, że akcje zostaną wysłane natychmiast, podczas gdy algorytm celowo opóźnia transmisję, zwiększając wydajność przepustowości kosztem opóźnienia . Z tego powodu aplikacje z wrażliwymi na czas transmisjami o niskiej przepustowości zwykle używają protokołu TCP_NODELAY do ominięcia opóźnienia ACK opóźnionego nagle.

Inną opcją jest zamiast tego użycie UDP .

Implementacja systemów operacyjnych

Większość nowoczesnych systemów operacyjnych implementuje algorytmy Nagle'a. W systemach AIX, Linux i Windows jest on domyślnie włączony i można go wyłączyć dla poszczególnych gniazd za pomocą TCP_NODELAY .

Larry'ego L. Petersona ; Bruce S. Davie (2007). Sieci komputerowe: podejście systemowe (wyd. 4). Morgana Kaufmanna. P. 402–403. ISBN 978-0-12-374013-7 .

Linki zewnętrzne