Blokování čela fronty

Blokování čela fronty 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

Síťový přepínač se obvykle skládá ze vstupních portů s vyrovnávací pamětí, přepojovací sítě 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. +more 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ý.

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

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. +more 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í

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ů. +more Blokování čela fronty může vést k výraznému zvýšení změn pořadí paketů.

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. +more 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í.

HTTP

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. +more 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).

Spolehlivé bajtové proudy

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. +more To působí problémy např. u protokolu url=HTTP/2,]který [[Rámec (počítačová síť)|balí[/url]] více dvojic požadavek-odezva do jednoho proudu; url=HTTP/3,]které využívá [[vytváření rámců v aplikační vrstvě[/url]] a používá přenos datagramů místo přenosu proudu, tímto problémem netrpí. 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. 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í.

Odkazy

Reference

Literatura

Související články

Bufferbloat * Metoda FIFO * HTTP pipelining * Síťový plánovač * Pipeline stall * Fronta (datová struktura)

Kategorie:Aplikovaná matematika Kategorie:Operační výzkum