Блокировка начала линии - Head-of-line blocking

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

Переключатели

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

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

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

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

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

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

Доставка вне очереди

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

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

В HTTP

Одна из форм блокировки HOL в HTTP / 1.1 - это когда количество разрешенных параллельных запросов в браузере исчерпывается, и последующие запросы должны ждать завершения первых.

HTTP / 2 решает эту проблему с помощью мультиплексирования запросов, которое устраняет блокировку HOL на уровне приложений, но HOL по-прежнему существует на транспортном уровне (TCP).[6][7]

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

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

  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. ^ Джон С. Р. Беннетт; Крейг Партридж; Николас Шектман (декабрь 1999 г.). «Переупорядочение пакетов не является патологическим поведением сети». Транзакции IEEE / ACM в сети. 7 (6): 789–798. CiteSeerX  10.1.1.461.7629. Дои:10.1109/90.811445.
  4. ^ Bennett, J. C. R .; Куропатка, C .; Шектман, Н. (апрель 2000 г.). Сариски, Дэн (ред.). «Переупорядочение пакетов не является патологическим поведением сети [Слайды]» (PDF). SC N Research. Архивировано из оригинал (PDF) на 2017-08-20. Получено 2017-08-19.
  5. ^ Тайлер Макмаллен."Наверное, работает".acmqueue 2015.
  6. ^ Григорик, Илья (октябрь 2013 г.). «Делаем Интернет быстрее с помощью HTTP 2.0». Очередь ACM. 11 (10): 40. Получено 10 июн 2019.
  7. ^ Хавьер Гарса (октябрь 2017 г.). "Как HTTP / 2 решает проблему блокировки заголовка (HOL)".