Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Феномен ограничения производительности в компьютерных сетях Блокировка головы линии (HOL-блокировка) в компьютерных сетях - это феномен ограничения производительности, который возникает, когда очередь пакетов задерживается первым пакетом в очереди. Это происходит, например, в входных буферированных сетевых коммутаторах, в непорядочной доставке и в многократных запросах в HTTP-проводах.
Performance limiting phenomenon in computer networks
Head of line blocking (HOL blocking) in computer networking is a performance limiting phenomenon that occurs when a queue of packets is held up by the first packet in the queue. This occurs, for example, in input buffered network switches, out of order delivery and multiple requests in HTTP pipelining.
Сетевые коммутаторы
Выключатель может состоять из буферных входных портов, конструкции выключателя и буферных выходной портов. Если используются входные буферы "первый вход, первый выход" (FIFO), только самый старый пакет доступен для пересылки. Если самый старый пакет не может быть передан из-за занятого выхода, то более поздние пакеты не могут быть переданы. Выход может быть занят, если есть выходная ссора. Без блокировки HOL, новые прибывшие потенциально могли бы быть перенаправлены вокруг застрявшего старейшего пакета к их соответствующим пунктам назначения. Блокировка HOL может привести к снижению производительности в системах с буферным входом. Это явление ограничивает пропускную способность коммутаторов. Для буферов FIFO, простые модели фиксированных ячеек с равномерно распределенными пунктами назначения, приводят к тому, что пропускная способность ограничивается 58,6% от общей, поскольку количество ссылок становится большим. Один из способов преодолеть это ограничение - использование виртуальных выходной очередей. Только коммутаторы с буферизированной входной системой могут страдать от блокировки HOL. При наличии достаточной внутренней полосы пропускания буферизация входа не требуется; вся буферизация обрабатывается на выходах и блокировка HOL избегается. Эта архитектура без буферизации входа распространена на небольших и средних Ethernet-свичах.
A switch may be composed of buffered input ports, a switch fabric and buffered output ports. If first in first out (FIFO) input buffers are used, only the oldest packet is available for forwarding. If the oldest packet cannot be transmitted due to its target output being busy, then more recent arrivals cannot be forwarded. The output may be busy if there is output contention. Without HOL blocking, the new arrivals could potentially be forwarded around the stuck oldest packet to their respective destinations. HOL blocking can produce performance degrading effects in input buffered systems. This phenomenon limits the throughput of switches. For FIFO input buffers, a simple model of fixed sized cells to uniformly distributed destinations, causes the throughput to be limited to 58.6% of the total as the number of links becomes large. One way to overcome this limitation is by using virtual output queues. Only switches with input buffering can suffer HOL blocking. With sufficient internal bandwidth, input buffering is unnecessary; all buffering is handled at outputs and HOL blocking is avoided. This no input buffering architecture is common in small to medium sized ethernet switches.
Непоставка по заказу
Непорядочная доставка происходит, когда последовательность пакетов прибывает не в порядке. Это может произойти из-за различных путей, которые проходят пакеты, или из-за пакетов, которые падают и пересылаются. Блокировка HOL может значительно увеличить переустройство пакетов. Надежное передача сообщений через сеть с потерями среди большого количества сверстников является сложной проблемой. В то время как алгоритмы атомной трансляции решают проблему с одной точкой сбоя централизованных серверов, эти алгоритмы вводят проблему блокировки головных линий. Бимодальный алгоритм мультикаста, рандомизированный алгоритм, использующий протокол сплетен, избегает блокировки линий, позволяя получать некоторые сообщения не в порядке.
Out of order delivery occurs when sequenced packets arrive out of order. This may happen due to different paths taken by the packets or from packets being dropped and resent. HOL blocking can significantly increase packet reordering. Reliably broadcasting messages across a lossy network among a large number of peers is a difficult problem. While atomic broadcast algorithms solve the single point of failure problem of centralized servers, those algorithms introduce a head of line blocking problem. The Bimodal Multicast algorithm, a randomized algorithm that uses a gossip protocol, avoids head of line blocking by allowing some messages to be received out of order.
В HTTP
Одной из форм блокировки HOL в HTTP/1.1 является то, что количество разрешенных параллельных запросов в браузере исчерпано, и последующие запросы должны ждать, пока предыдущие завершатся. HTTP/2 решает эту проблему посредством мультиплексирования запросов, что устраняет блокировку HOL на уровне приложения, но HOL все еще существует на уровне транспорта (TCP).
One form of HOL blocking in HTTP/1.1 is when the number of allowed parallel requests in the browser is used up, and subsequent requests need to wait for the former ones to complete. HTTP/2 addresses this issue through request multiplexing, which eliminates HOL blocking at the application layer, but HOL still exists at the transport (TCP) layer.
В надежных потоках байтов
Блокировка на начале линии может возникать в надежных байтовых потоках: если пакеты перестроены или потеряны и их нужно перенаправить (и, таким образом, они прибывают не в порядке), данные из последовательно более поздних частей потока могут быть получены до последовательно более ранних частей потока; однако поздние данные обычно не могут быть использованы до получения более ранних данных, что приводит к задержке сети. Если несколько независимых сообщений более высокого уровня инкапсулированы и мультиплексированы в один надежный байтовый поток, то блокировка на начале строки может привести к обработке полностью полученного сообщения, которое было отправлено позже, чтобы дождаться доставки сообщения, которое было отправлено ранее. Это влияет, например, на HTTP/2, который встраивает несколько пар запросов и ответов в один поток; HTTP/3, который имеет конструкцию встраивания на уровне приложения и использует датграмму, а не транспорт потока, избегает этой проблемы. Ухудшение латентности от блокировки на начале линии зависит от базовой скорости потери пакетов и времени прибытия и возвращения, причем более высокие потери приводят к ухудшению латентности. Без изменения абстракции потока, уменьшение потери пакетов может уменьшить вред от блокировки линии; альтернативным вариантом является реализация надежного потока байтов с использованием коррекции ошибок вперед для отправки избыточных данных, чтобы можно было терпеть определенное количество потерь без возникновения ретрансляций.
Head of line blocking can occur in reliable byte streams: if packets are reordered or lost and need to be retransmitted (and thus arrive out of order), data from sequentially later parts of the stream may be received before sequentially earlier parts of the stream; however, the later data cannot typically be used until the earlier data has been received, incurring network latency. If multiple independent higher level messages are encapsulated and multiplexed onto a single reliable byte stream, then head of line blocking can cause processing of a fully received message that was sent later to wait for delivery of a message that was sent earlier. This affects, for example, HTTP/2, which frames multiple request–response pairs onto a single stream; HTTP/3, which has an application layer framing design and uses datagram rather than stream transport, avoids this problem. The latency degradation from head of line blocking depends on the underlying packet loss rate and round trip time, with higher losses producing worse latency. Without changing the stream abstraction, reducing packet loss can reduce the harm from head of line blocking; an alternative is to implement the reliable byte stream using forward error correction to send redundant data so that a certain amount of loss can be tolerated without incurring retransmissions.