stringtranslate.com

Блокировка начала линии

Блокировка начала строки ( блокировка HOL ) в компьютерных сетях — это явление, ограничивающее производительность, которое возникает, когда строка пакетов задерживается в очереди первым пакетом. Примеры включают сетевые коммутаторы с буферизацией ввода , доставку вне очереди и множественные запросы в конвейерной обработке HTTP .

Сетевые коммутаторы

Пример блокировки начала линии: 1-й и 3-й входные потоки конкурируют за отправку пакетов на один и тот же выходной интерфейс. В этом случае, если коммутационная структура решит передать пакет из 3-го входного потока, 1-й входной поток не сможет быть обработан в том же временном интервале. Обратите внимание, что первый входной поток блокирует пакет для выходного интерфейса 3, который доступен для обработки.

Коммутатор может состоять из буферизованных входных портов, коммутационной матрицы и буферизованных выходных портов. Если используются входные буферы FIFO, для пересылки доступен только самый старый пакет. Если самый старый пакет не может быть передан из-за того, что его целевой выход занят, то более поздние поступления не могут быть перенаправлены. Выход может быть занят, если существует конфликт на выходе .

Без блокировки HOL новые поступления потенциально могут быть перенаправлены вокруг застрявшего самого старого пакета в соответствующие пункты назначения. Блокировка HOL может привести к снижению производительности в системах с буферизацией ввода.

Это явление ограничивает пропускную способность коммутаторов. Для входных буферов FIFO простая модель ячеек фиксированного размера с равномерно распределенными пунктами назначения приводит к ограничению пропускной способности до 58,6% от общей суммы, поскольку количество каналов становится большим. [1]

Одним из способов преодоления этого ограничения является использование виртуальных очередей вывода . [2]

Только коммутаторы с буферизацией ввода могут подвергаться блокировке HOL. При достаточной внутренней пропускной способности буферизация ввода не требуется; вся буферизация осуществляется на выходах, а блокировка HOL избегается. Такая архитектура без входной буферизации распространена в коммутаторах Ethernet малого и среднего размера .

Доставка вне заказа

Доставка вне очереди происходит, когда упорядоченные пакеты поступают не по порядку. Это может произойти из-за того, что пакеты прошли по разным путям, или из-за того, что пакеты были отброшены и повторно отправлены. Блокировка HOL может значительно увеличить переупорядочение пакетов. [3] [4]

Надежная передача сообщений по сети с потерями среди большого числа одноранговых узлов является сложной проблемой. Хотя алгоритмы атомарного вещания решают проблему единой точки отказа централизованных серверов, эти алгоритмы создают проблему блокировки начала линии. [5] Алгоритм бимодальной многоадресной рассылки, рандомизированный алгоритм , использующий протокол сплетен , позволяет избежать блокировки начала линии, позволяя получать некоторые сообщения не по порядку. [6]

В HTTP

Одна из форм блокировки HOL в HTTP/1.1 заключается в том, что количество разрешенных параллельных запросов в браузере исчерпано, и последующим запросам приходится ждать завершения предыдущих. HTTP/2 решает эту проблему посредством мультиплексирования запросов, которое устраняет блокировку HOL на уровне приложения, но HOL все еще существует на транспортном уровне (TCP). [7] [8]

В надежных потоках байтов

Блокировка начала строки может происходить в надежных потоках байтов : если пакеты переупорядочены или потеряны и их необходимо передать повторно (и, таким образом, они поступают не по порядку), данные из последовательно более поздних частей потока могут быть получены раньше, чем последовательно более ранние части. ручья; однако более поздние данные обычно не могут быть использованы до тех пор, пока не будут получены более ранние данные, что приводит к задержке в сети . Если несколько независимых сообщений более высокого уровня инкапсулируются и мультиплексируются в один надежный поток байтов, то блокировка начала строки может привести к обработке полностью полученного сообщения, которое было отправлено позже, в ожидании доставки сообщения, которое было отправлено ранее. [9] Это касается, например, HTTP/2 , который объединяет несколько пар запрос-ответ в один поток; HTTP/3 , который имеет структуру кадрирования прикладного уровня и использует дейтаграммную , а не потоковую транспортировку, позволяет избежать этой проблемы. [10] [11] Ухудшение задержки из-за блокировки начала линии зависит от базовой скорости потери пакетов и времени прохождения туда и обратно , при этом более высокие потери приводят к худшей задержке. [12] [13] Без изменения абстракции потока сокращение потерь пакетов может снизить вред от блокировки начала строки; Альтернативой является реализация надежного потока байтов с использованием прямого исправления ошибок для отправки избыточных данных, чтобы можно было допустить определенный объем потерь без повторных передач. [9]

Смотрите также

Рекомендации

  1. ^ М. Каро; М. Глучий; С. Морган (декабрь 1987 г.). «Очередь ввода и вывода на коммутаторе пакетов с пространственным разделением». Транзакции IEEE в области коммуникаций . 35 (12): 1347–1356. дои : 10.1109/TCOM.1987.1096719.
  2. ^ Ник МакКаун ; Адисак Меккиттикул ; Венкат Анантарам; Жан Вальран (август 1999 г.). «Достижение 100% пропускной способности в коммутаторе с очередью ввода» (PDF) . Транзакции IEEE в области коммуникаций . 47 (8): 1260–1267. CiteSeerX 10.1.1.18.7529 . дои : 10.1109/26.780463. 
  3. ^ Джон CR Беннетт; Крейг Партридж; Николас Шектман (декабрь 1999 г.). «Переупорядочение пакетов не является патологическим поведением сети». Транзакции IEEE/ACM в сети . 7 (6): 789–798. CiteSeerX 10.1.1.461.7629 . дои : 10.1109/90.811445. S2CID  26573611. 
  4. ^ Беннетт, JCR; Партридж, К.; Шектман, Н. (апрель 2000 г.). Сариски, Дэн (ред.). «Переупорядочение пакетов не является патологическим поведением сети [слайды]» (PDF) . СК Н Исследования . Архивировано из оригинала (PDF) 20 августа 2017 г. Проверено 19 августа 2017 г.
  5. ^ Дефаго, X.; Шипер; А., Урбан П. (2004). «Алгоритмы широковещательной и многоадресной рассылки общего порядка: таксономия и обзор» (PDF) . Обзоры вычислительной техники ACM . 36 (4): 372–421. дои : 10.1145/1041680.1041682. S2CID  207155989.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
  6. ^ Тайлер МакМаллен (2015). «Наверное, это работает». Очередь АКМ .
  7. ^ Григорик, Илья (октябрь 2013 г.). «Ускорение работы в Интернете с помощью HTTP 2.0». Очередь АКМ . 11 (10): 40. дои : 10.1145/2542661.2555617 . S2CID  34623442 . Проверено 10 июня 2019 г.
  8. ^ Хавьер Гарса (октябрь 2017 г.). «Как HTTP/2 решает проблему блокировки начала линии (HOL)».
  9. ^ аб Бриско и др. 2016, стр. 29–30.
  10. ^ Лэнгли и др. 2017, стр. 184, 186.
  11. ^ Маркс и др. 2018, стр. 22–23.
  12. ^ Ноулан, Волински и Форд 2013, стр. 6.
  13. ^ Хейлигерс 2021, с. 65.

Библиография