Blokowanie na czele linii
Blokowanie na początku linii ( blokowanie HOL ) w sieciach komputerowych to zjawisko ograniczające wydajność, które występuje, gdy linia pakietów jest zatrzymywana w kolejce przez pierwszy pakiet. Przykłady obejmują przełączniki sieciowe z buforem wejściowym , dostarczanie poza kolejnością i wiele żądań w potoku HTTP .
Przełączniki sieciowe
Przełącznik może składać się z buforowanych portów wejściowych, struktury przełącznika i buforowanych portów wyjściowych. Jeśli typu „pierwsze weszło, pierwsze wyszło ” (FIFO), do przekazania dostępny jest tylko najstarszy pakiet. Nowsze nadejścia nie mogą być przekazane, jeśli najstarszy pakiet nie może zostać przekazany, ponieważ jego wyjście docelowe jest zajęte. Wyjście może być zajęte, jeśli występuje rywalizacja o wyjście .
Bez blokowania HOL nowo przybyli mogliby potencjalnie zostać przekierowani wokół zablokowanego najstarszego pakietu do odpowiednich miejsc docelowych. Blokowanie HOL może powodować obniżenie wydajności w systemach z buforem wejściowym.
Zjawisko to ogranicza przepustowość przełączników. W przypadku buforów wejściowych FIFO prosty model komórek o stałym rozmiarze do równomiernie rozmieszczonych miejsc docelowych powoduje ograniczenie przepustowości do 58,6% całości, gdy liczba łączy staje się duża.
Jednym ze sposobów przezwyciężenia tego ograniczenia jest użycie wirtualnych kolejek wyjściowych .
Blokowanie HOL może dotyczyć tylko przełączników z buforowaniem wejściowym. Przy wystarczającej przepustowości wewnętrznej buforowanie danych wejściowych jest niepotrzebne; całe buforowanie jest obsługiwane na wyjściach i unika się blokowania HOL. Ta architektura bez buforowania danych wejściowych jest powszechna w małych i średnich przełącznikach ethernetowych .
Dostawa poza zamówieniem
Dostarczanie poza kolejnością ma miejsce, gdy pakiety zsekwencjonowane docierają poza kolejnością. Może się to zdarzyć z powodu różnych ścieżek pokonywanych przez pakiety lub z powodu odrzucania i ponownego wysyłania pakietów. Blokowanie HOL może znacznie zwiększyć zmianę kolejności pakietów.
Niezawodne rozgłaszanie wiadomości w stratnej sieci wśród dużej liczby równorzędnych jest trudnym problemem. Chociaż atomowe algorytmy emisji rozwiązują problem pojedynczego punktu awarii scentralizowanych serwerów, algorytmy te wprowadzają problem blokowania na początku linii. Algorytm Bimodal Multicast, losowy algorytm korzystający z protokołu plotek , pozwala uniknąć blokowania na początku linii, umożliwiając odbieranie niektórych wiadomości poza kolejnością.
W protokole HTTP
Jedną z form blokowania HOL w HTTP/1.1 jest wyczerpanie liczby dozwolonych żądań równoległych w przeglądarce, a kolejne żądania muszą czekać na zakończenie poprzednich. HTTP/2 rozwiązuje ten problem poprzez multipleksowanie żądań, które eliminuje blokowanie HOL w warstwie aplikacji, ale HOL nadal istnieje w warstwie transportowej (TCP).
W niezawodnych strumieniach bajtów
Blokowanie początku linii może wystąpić w niezawodnych strumieniach bajtów : jeśli pakiety zostaną ponownie uporządkowane lub utracone i muszą zostać ponownie przesłane (a tym samym dotrą poza kolejnością), dane z kolejnych części strumienia mogą zostać odebrane przed sekwencyjnie wcześniejszymi częściami strumienia; jednak późniejszych danych zazwyczaj nie można użyć, dopóki nie zostaną odebrane wcześniejsze dane, co wiąże się z opóźnieniem sieci . Jeśli wiele niezależnych komunikatów wyższego poziomu jest enkapsulowanych i multipleksowanych na pojedynczy niezawodny strumień bajtów, wówczas blokowanie początku linii może spowodować, że w pełni odebrany komunikat, który został wysłany później, będzie czekał na dostarczenie komunikatu wysłanego wcześniej. Dotyczy to na przykład protokołu HTTP/2 , który umieszcza wiele par żądanie-odpowiedź w jednym strumieniu; Protokół HTTP/3 , który ma konstrukcję ramek w warstwie aplikacji i wykorzystuje datagram zamiast transportu strumieniowego, pozwala uniknąć tego problemu. Degradacja opóźnienia wynikająca z blokowania na początku linii zależy od podstawowego wskaźnika utraty pakietów i czasu podróży w obie strony , przy czym większe straty powodują gorsze opóźnienie. Bez zmiany abstrakcji strumienia zmniejszenie utraty pakietów może zmniejszyć szkody spowodowane blokowaniem na początku linii; alternatywą jest zaimplementowanie niezawodnego strumienia bajtów z wykorzystaniem korekcji błędów w przód w celu wysyłania nadmiarowych danych, tak aby można było tolerować pewną ilość strat bez ponoszenia retransmisji.
Zobacz też
Bibliografia
- Briscoe, Bob; Brunstrom, Anna; Petlund, Andreas; Hayes, Dawid; Ros, Dawid; Tsang, Ing-Jyh; Gjessing, Stein; Fairhurst, Gorry; Griwodz, Carsten; Welzl, Michael (2016). „Zmniejszanie opóźnień w Internecie: przegląd technik i ich zalet” . Ankiety i samouczki dotyczące komunikacji IEEE . 18 (3): 2149–2196. doi : 10.1109/COMST.2014.2375213 . hdl : 2164/8018 . S2CID 206576469 .
- Heijligers, Jaap (2021). Tor przez QUIC (praca).
- Langley, Adam; Riddoch, Alistair; Wilk, Alyssa; Vincente, Antonio; Krasić, Karol; Zhang, Dan; Yang, wentylator; Kuranow, Fedor; Swett, Ian; Iyengar, Janardhan; Bailey, Jeff; Dorfman, Jeremy; Roskind, Jim; Kulik, Joanna; Westin, Patryk; Tenneti, Raman; Cień, Robbie; Hamilton, Ryan; Wasiliew, Wiktor; Chang, Wan-Teh; Shi, Zhongyi (2017). „Protokół transportowy QUIC”. Obrady Konferencji Grupy Specjalnego Zainteresowania ACM ds. Komunikacji Danych . s. 183–196. doi : 10.1145/3098822.3098842 . ISBN 9781450346535 . S2CID 2768765 .
- Marks, Robin; Wijnants, Maarten; Quax, Piotr; Wróżki, Axel; Lamotte, Wim (2018). „Charakterystyka wydajności sieci Web protokołu HTTP/2 i porównanie z HTTP/1.1” . Sieciowe systemy informacyjne i technologie . Notatki z wykładów w zakresie przetwarzania informacji biznesowych. Tom. 322. s. 87–114. doi : 10.1007/978-3-319-93527-0_5 . hdl : 1942/26146 . ISBN 978-3-319-93526-3 . S2CID 52009597 .
- Nowlan, Michael F.; Woliński, Dawid; Ford, Bryan (2013). Zmniejszanie opóźnień w obwodach Tora dzięki dostarczaniu nieuporządkowanemu . III Warsztaty USENIX nt. Wolnej i Otwartej Komunikacji w Internecie.