Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Переключатели [ править ]

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

См. Также [ править ]

Ссылки [ править ]

  1. ^ М. Каро; М. Глучий; С. Морган (декабрь 1987 г.). «Очередь ввода и вывода на коммутаторе пакетов с пространственным разделением». Транзакции IEEE по коммуникациям . 35 (12): 1347–1356. DOI : 10.1109 / TCOM.1987.1096719 .
  2. ^ Ник Маккеун ; Адисак Меккиттикуль ; Венкат Анантарам; Жан Вальран (август 1999 г.). «Достижение 100% пропускной способности коммутатора с очередью ввода» (PDF) . Транзакции IEEE по коммуникациям . 47 (8): 1260–1267. CiteSeerX 10.1.1.18.7529 . DOI : 10.1109 / 26.780463 .  
  3. ^ Джон CR Беннетт; Крейг Партридж; Николас Шектман (декабрь 1999 г.). «Переупорядочивание пакетов не является патологическим поведением сети». Транзакции IEEE / ACM в сети . 7 (6): 789–798. CiteSeerX 10.1.1.461.7629 . DOI : 10.1109 / 90.811445 . 
  4. ^ Беннетт, JCR; Куропатка, C .; Шектман, Н. (апрель 2000 г.). Сариски, Дэн (ред.). «Переупорядочение пакетов не является патологическим поведением сети [слайды]» (PDF) . SC N Research . Архивировано из оригинального (PDF) 20 августа 2017 года . Проверено 19 августа 2017 .
  5. ^ Defago, X .; Шипер; А., Урбан, П. (2004). «Алгоритмы широковещательной и многоадресной рассылки полного порядка: таксономия и обзор». ACM Computing Surveys 36 (4) : 372-421. DOI : 10.1145 / 1041680.1041682 .CS1 maint: multiple names: authors list (link)
  6. ^ Тайлер Макмаллен. «Наверное, работает» . acmqueue 2015.
  7. ^ Grigorik Илья (октябрь 2013 г. ). «Делаем Интернет быстрее с помощью HTTP 2.0» . Очередь ACM . 11 (10): 40 . Проверено 10 июня 2019 .
  8. ↑ Хавьер Гарса (октябрь 2017 г.). «Как HTTP / 2 решает проблему блокировки заголовка (HOL)» .