Blokování čela fronty

Z Wikipedie, otevřené encyklopedie

Blokování čela fronty (anglicky Head-of-line blocking, HOL blocking) je jev omezující výkonnost v počítačových sítích, ke kterému dochází, když zpracování prvního paketu zdržuje celou frontu následujících paketů. K blokování čela fronty dochází například u síťových přepínačů se vstupními vyrovnávacími paměťmi, při doručování mimo pořadí, nebo pokud se při HTTP pipeliningu zpracovává více než jeden požadavek.

Síťové přepínače[editovat | editovat zdroj]

Síťový přepínač se obvykle skládá ze vstupních portů s vyrovnávací pamětí, přepojovací sítě (anglicky switch fabric) a výstupních portů s vyrovnávací pamětí. Pokud vstupní vyrovnávací paměti pracují metodou FIFO, je pro forwardování dostupný pouze nejstarší paket. Pokud tento paket nemůže být forwardován, protože například jeho příjemce nereaguje, nemůže být forwardován žádný další paket. K zablokování výstupu může dojít, pokud dochází k soupeření o prostředky na výstupu (viz obrázek), nebo když je výstupní vyrovnávací paměť plná kvůli zahlcení (například když součet rychlostí vstupů je větší než výstupní rychlost).

Bez blokování čela fronty by nově příchozí pakety mohly být forwardovány na požadované cíle bez ohledu na zaseknutý nejstarší paket. Jev může v systémech se vstupními vyrovnávacími paměťmi vést k závažnému snížení výkonnosti.

Popsaný jev omezuje propustnost přepínačů. Pro jednoduchý model s buňkami pevné velikosti posílanými na rovnoměrně rozdělené cíle a se vstupními vyrovnávacími paměťmi pracujícími metodou FIFO může být omezena propustnost až 58,6 % linek je-li jejich počet velký.[1]

Jednou z možností jak zabránit tomuto omezení je používání virtuálních výstupních front.[2]

Blokování čela fronty se objevuje pouze u přepínačů s vyrovnávacími paměťmi na vstupu. Při dostatečné interní šířce pásma je použití vyrovnávacích pamětí na vstupu zbytečné; vyrovnávací paměti jsou použity pouze na výstupech a k blokování čela fronty nemůže dojít. Architektura bez vstupních vyrovnávacích pamětí je obvyklá u malých na středně velkých ethernetových přepínačů.

Doručování mimo pořadí[editovat | editovat zdroj]

K doručování mimo pořadí dochází, když jsou seřazené pakety doručeny ve špatném pořadí. K tomu může dojít kvůli posílání paketů různými cestami nebo kvůli zahazování nebo opakovanému přenosu paketů. Blokování čela fronty může vést k výraznému zvýšení změn pořadí paketů.[3][4]

V sítích, ve které dochází k částým ztrátám paketů, je spolehlivý všesměrový přenos zpráv mezi velkým počtem uzlům obtížný problém. Algoritmy, které používají atomický broadcast sice řeší problém jediného bodu selhání centralizovaných serverů, ale přinášejí problém blokování čela fronty.[5] Bimodální algoritmus multicastu je pravděpodobnostní algoritmus, jehož využívá gossip protokol, se vyhýbá blokování čela fronty tím, že dovoluje, aby některé zprávy byly přijaty mimo pořadí.[6]

HTTP[editovat | editovat zdroj]

Jednou z forem blokování čela fronty v HTTP/1.1 je, když počet současně povolených požadavků v prohlížeč je plně využit, a následující požadavky musí čekat, než budou první požadavky dokončeny. HTTP/2 řeší tento problém multiplexovánín požadavků, které odstraňuje blokování čela fronty na aplikační vrstvě, ale může k němu stále docházet na transportní vrstvě (TCP).[7][8]

Spolehlivé bajtové proudy[editovat | editovat zdroj]

K blokování čela fronty může dojít při používání spolehlivých bajtových proudů: pokud dojde k ztrátě nebo změně pořadí paketů, a je třeba opakovat přenos některých paketů (které kvůli tomu dorazí mimo pořadí), data z pozdějších částí proudu mohou být přijata před dřívějšími daty; tato data obvykle nemohou být použita, dokud nebudou přijata, data která jsou v produ před nimi, což zvyšuje latenci sítě. Pokud je do jednoho spolehlivého bajtového proudu zapouzdřeno a časově multiplexováno více nezávislých zpráv vyšší úrovně, pak blokování čela fronty může způsobit, že na zpracování plně přijaté zpráva, které byl odeslána později, se musí čekat dokud nebude doručena zpráva, která jí v proudu měla předcházet.[9] To působí problémy např. u protokolu HTTP/2, který balí více dvojic požadavek–odezva do jednoho proudu; HTTP/3, které využívá vytváření rámců v aplikační vrstvě a používá přenos datagramů místo přenosu proudu, tímto problémem netrpí.[10][11] Zhoršení latence kvůli blokování čela fronty závisí na podílu ztracených paketů a obousměrném zpoždění; vyšší ztráty způsobují horší latence.[12][13] Pro omezení problémů způsobených blokováním čela fronty je nutné buď snížit ztráty paketů nebo implementovat spolehlivé bajtové proudy s použitím dopředné opravy chyb, s níž si určitá míra ztrát paketů nevynutí jejich opakované vysílání.[9]

Odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Head-of-line blocking na anglické Wikipedii.

  1. ↑ M. Karo; M. Hluchyj; S. Morgan, 1987. Input Versus Output Queuing on a Space-Division Packet Switch. IEEE Transactions on Communications. Prosinec 1987, roč. 35, čís. 12, s. 1347–1356. DOI 10.1109/TCOM.1987.1096719. 
  2. ↑ Nick McKeown; Adisak Mekkittikul; Venkat Anantharam; Jean Walrand, 1999. Achieving 100% Throughput in an Input-Queued Switch. IEEE Transactions on Communications. Srpen 1999, roč. 47, čís. 8, s. 1260–1267. Dostupné online. DOI 10.1109/26.780463. 
  3. ↑ Jon C. R. Bennett; Craig Partridge; Nicholas Shectman, 1999. Packet reordering is not pathological network behavior. IEEE/ACM Transactions on Networking. Prosinec 1999, roč. 7, čís. 6, s. 789–798. DOI 10.1109/90.811445. S2CID 26573611. 
  4. ↑ BENNETT, J. C. R.; PARTRIDGE, C.; SHECTMAN, N., 2000. Packet Reordering is Not Pathological Network Behavior (Přerovnávání paketů není patologickým chováním sítě) [Slidy] [online]. SC N Research, duben 2000 [cit. 2017-08-19]. Dostupné v archivu pořízeném dne 2017-08-20. 
  5. ↑ Defago, X.; Schiper; A., Urban, P., 2004. Total order broadcast and multicast algorithms: taxonomy and survey. ACM Computing Surveys. Roč. 36, čís. 4, s. 372–421. Dostupné online. DOI 10.1145/1041680.1041682. S2CID 207155989. 
  6. ↑ Tyler McMullen. It Probably Works. ACM Queue. 2015. Dostupné online. 
  7. ↑ GRIGORIK, Ilya. Making the Web Faster with HTTP 2.0. ACM Queue. October 2013, roč. 11, čís. 10, s. 40. Dostupné online [cit. 2019-06-10]. DOI 10.1145/2542661.2555617. S2CID 34623442. 
  8. ↑ Javier Garza. How does HTTP/2 solve the Head of Line blocking (HOL) issue [online]. October 2017. Dostupné online. 
  9. ↑ a b Briscoe et al. 2006, s. 29-30.
  10. ↑ Langley et al. 2017, s. 184,186.
  11. ↑ Marx et al. 2018, s. 22-23.
  12. ↑ Nowlan, Wolinsky a Ford 2013, s. 6.
  13. ↑ Heijligers 2021, s. 65.

Literatura[editovat | editovat zdroj]

  • BRISCOE, Bob; BRUNSTROM, Anna; PETLUND, Andreas; HAYES, David; ROS, David; TSANG, Ing-Jyh; GJESSING, Stein, 2016. Reducing Internet Latency: A Survey of Techniques and Their Merits. IEEE Communications Surveys & Tutorials. Roč. 18, čís. 3, s. 2149–2196. DOI 10.1109/COMST.2014.2375213. S2CID 206576469. 
  • HEIJLIGERS, Jaap. Tor over QUIC. , 2021. . . Dostupné online.
  • LANGLEY, Adam; RIDDOCH, Alistair; WILK, Alyssa; VICENTE, Antonio; KRASIC, Charles; ZHANG, Dan; YANG, Fan, 2017. Proceedings of the Conference of the ACM Special Interest Group on Data Communication. [s.l.]: [s.n.]. ISBN 9781450346535. DOI 10.1145/3098822.3098842. S2CID 2768765. Kapitola The QUIC Transport Protocol, s. 183–196. 
  • MARX, Robin; WIJNANTS, Maarten; QUAX, Peter; FAES, Axel; LAMOTTE, Wim, 2018. Web Information Systems and Technologies. [s.l.]: [s.n.]. (Lecture Notes in Business Information Processing). ISBN 978-3-319-93526-3. DOI 10.1007/978-3-319-93527-0_5. S2CID 52009597. Kapitola Web Performance Characteristics of HTTP/2 and Comparison to HTTP/1.1, s. 87–114. 
  • NOWLAN, Michael F.; WOLINSKY, David; FORD, Bryan, 2013. Reducing Latency in Tor Circuits with Unordered Delivery. In: 3rd USENIX Workshop on Free and Open Communications on the Internet. Washington, D.C.: [s.n.]. Dostupné online.

Související články[editovat | editovat zdroj]

Citováno z „https://cs.wikipedia.org/w/index.php?title=Blokování_čela_fronty&oldid=22596379“