Блокировка начала строки ( блокировка HOL ) в компьютерных сетях — это явление, ограничивающее производительность, которое возникает, когда строка пакетов задерживается в очереди первым пакетом. Примеры включают сетевые коммутаторы с буферизацией ввода , доставку вне очереди и множественные запросы в конвейерной обработке HTTP .
Коммутатор может состоять из буферизованных входных портов, коммутационной матрицы и буферизованных выходных портов. Если используются входные буферы FIFO, для пересылки доступен только самый старый пакет. Если самый старый пакет не может быть передан из-за того, что его целевой выход занят, то более поздние поступления не могут быть перенаправлены. Выход может быть занят, если существует конфликт на выходе .
Без блокировки HOL новые поступления потенциально могут быть перенаправлены вокруг застрявшего самого старого пакета в соответствующие пункты назначения. Блокировка HOL может привести к снижению производительности в системах с буферизацией ввода.
Это явление ограничивает пропускную способность коммутаторов. Для входных буферов FIFO простая модель ячеек фиксированного размера с равномерно распределенными пунктами назначения приводит к ограничению пропускной способности до 58,6% от общей суммы, поскольку количество каналов становится большим. [1]
Одним из способов преодоления этого ограничения является использование виртуальных очередей вывода . [2]
Только коммутаторы с буферизацией ввода могут подвергаться блокировке HOL. При достаточной внутренней пропускной способности буферизация ввода не требуется; вся буферизация осуществляется на выходах, а блокировка HOL избегается. Такая архитектура без входной буферизации распространена в коммутаторах Ethernet малого и среднего размера .
Доставка вне очереди происходит, когда упорядоченные пакеты поступают не по порядку. Это может произойти из-за того, что пакеты прошли по разным путям, или из-за того, что пакеты были отброшены и повторно отправлены. Блокировка HOL может значительно увеличить переупорядочение пакетов. [3] [4]
Надежная передача сообщений по сети с потерями среди большого числа одноранговых узлов является сложной проблемой. Хотя алгоритмы атомарного вещания решают проблему единой точки отказа централизованных серверов, эти алгоритмы создают проблему блокировки начала линии. [5] Алгоритм бимодальной многоадресной рассылки, рандомизированный алгоритм , использующий протокол сплетен , позволяет избежать блокировки начала линии, позволяя получать некоторые сообщения не по порядку. [6]
Одна из форм блокировки HOL в HTTP/1.1 заключается в том, что количество разрешенных параллельных запросов в браузере исчерпано, и последующим запросам приходится ждать завершения предыдущих. HTTP/2 решает эту проблему посредством мультиплексирования запросов, которое устраняет блокировку HOL на уровне приложения, но HOL все еще существует на транспортном уровне (TCP). [7] [8]
Блокировка начала строки может происходить в надежных потоках байтов : если пакеты переупорядочены или потеряны и их необходимо передать повторно (и, таким образом, они поступают не по порядку), данные из последовательно более поздних частей потока могут быть получены раньше, чем последовательно более ранние части. ручья; однако более поздние данные обычно не могут быть использованы до тех пор, пока не будут получены более ранние данные, что приводит к задержке в сети . Если несколько независимых сообщений более высокого уровня инкапсулируются и мультиплексируются в один надежный поток байтов, то блокировка начала строки может привести к обработке полностью полученного сообщения, которое было отправлено позже, в ожидании доставки сообщения, которое было отправлено ранее. [9] Это касается, например, HTTP/2 , который объединяет несколько пар запрос-ответ в один поток; HTTP/3 , который имеет структуру кадрирования прикладного уровня и использует дейтаграммную , а не потоковую транспортировку, позволяет избежать этой проблемы. [10] [11] Ухудшение задержки из-за блокировки начала линии зависит от базовой скорости потери пакетов и времени прохождения туда и обратно , при этом более высокие потери приводят к худшей задержке. [12] [13] Без изменения абстракции потока сокращение потерь пакетов может снизить вред от блокировки начала строки; Альтернативой является реализация надежного потока байтов с использованием прямого исправления ошибок для отправки избыточных данных, чтобы можно было допустить определенный объем потерь без повторных передач. [9]
{{cite journal}}
: CS1 maint: несколько имен: список авторов ( ссылка )