Блокировка начала линии
Блокировка начала строки ( блокировка HOL ) в сетях — это явление, ограничивающее производительность, которое возникает, когда очередь пакетов компьютерных задерживается первым пакетом в очереди. Это происходит, например, в сетевых коммутаторах с буферизацией ввода , доставке вне очереди и множественных запросах при конвейерной обработке HTTP .
Сетевые коммутаторы
[ редактировать ]
Коммутатор может состоять из буферизованных входных портов, коммутационной матрицы и буферизованных выходных портов. Если используются входные буферы 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]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ М. Каро; М. Глучий; С. Морган (декабрь 1987 г.). «Очередь ввода и вывода на коммутаторе пакетов с пространственным разделением». Транзакции IEEE в области коммуникаций . 35 (12): 1347–1356. дои : 10.1109/TCOM.1987.1096719 .
- ^ Ник МакКаун ; Адисак Меккиттикул ; Венкат Анантарам; Жан Вальран (август 1999 г.). «Достижение 100% пропускной способности в коммутаторе с очередью ввода» (PDF) . Транзакции IEEE в области коммуникаций . 47 (8): 1260–1267. CiteSeerX 10.1.1.18.7529 . дои : 10.1109/26.780463 .
- ^ Джон С.Р. Беннетт; Крейг Партридж; Николас Шектман (декабрь 1999 г.). «Переупорядочение пакетов не является патологическим поведением сети». Транзакции IEEE/ACM в сети . 7 (6): 789–798. CiteSeerX 10.1.1.461.7629 . дои : 10.1109/90.811445 . S2CID 26573611 .
- ^ Беннетт, JCR; Партридж, К.; Шектман, Н. (апрель 2000 г.). Сариски, Дэн (ред.). «Переупорядочение пакетов не является патологическим поведением сети [слайды]» (PDF) . СК Н Исследования . Архивировано из оригинала (PDF) 20 августа 2017 г. Проверено 19 августа 2017 г.
- ^ Дефаго, X.; Шипер; А., Урбан П. (2004). «Алгоритмы широковещательной и многоадресной рассылки общего порядка: таксономия и обзор» (PDF) . Обзоры вычислительной техники ACM . 36 (4): 372–421. дои : 10.1145/1041680.1041682 . S2CID 207155989 .
{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Тайлер Макмаллен (2015). «Наверное, это работает» . Очередь АКМ .
- ^ Григорик, Илья (октябрь 2013 г.). «Ускорение работы в Интернете с помощью HTTP 2.0» . Очередь АКМ . 11 (10): 40. дои : 10.1145/2542661.2555617 . S2CID 34623442 . Проверено 10 июня 2019 г.
- ^ Хавьер Гарса (октябрь 2017 г.). «Как HTTP/2 решает проблему блокировки начала линии (HOL)» .
- ^ Jump up to: а б Бриско и др. 2016 , стр. 29–30.
- ^ Лэнгли и др. 2017 , с. 184, 186.
- ^ Маркс и др. 2018 , стр. 22–23.
- ^ Ноулан, Волински и Форд, 2013 , стр. 6.
- ^ Хейлигерс 2021 , с. 65.
Библиография
[ редактировать ]- Бриско, Боб; Брунстрем, Анна; Петлунд, Андреас; Хейс, Дэвид; Рос, Дэвид; Цанг, Инг-Джых; Йессинг, Штейн; Фэрхерст, Горри; Гриводз, Карстен; Вельцль, Майкл (2016). «Уменьшение задержки в Интернете: обзор методов и их преимуществ». Опросы и учебные пособия IEEE по коммуникациям . 18 (3): 2149–2196. дои : 10.1109/COMST.2014.2375213 . hdl : 2164/8018 . S2CID 206576469 .
- Хейлигерс, Яап (2021). Tor поверх QUIC (Диссертация).
- Лэнгли, Адам; Риддок, Алистер; Уилк, Алисса; Висенте, Антонио; Красич, Чарльз; Чжан, Дэн; Ян, Фань; Куранов, Федор; Светт, Ян; Айенгар, Джанардхан; Бейли, Джефф; Дорфман, Джереми; Роскинд, Джим; Кулик, Джоанна; Вестин, Патрик; Теннети, Раман; Шейд, Робби; Гамильтон, Райан; Васильев, Виктор; Чанг, Ван-Те; Ши, Чжунъи (2017). «Транспортный протокол QUIC». Материалы конференции Специальной группы ACM по передаче данных . стр. 183–196. дои : 10.1145/3098822.3098842 . ISBN 9781450346535 . S2CID 2768765 .
- Маркс, Робин; Вейнантс, Мартен; Квакс, Питер; Фаес, Аксель; Ламотт, Вим (2018). «Характеристики веб-производительности HTTP/2 и сравнение с HTTP/1.1». Веб-информационные системы и технологии . Конспекты лекций по обработке деловой информации. Том. 322. стр. 87–114. дои : 10.1007/978-3-319-93527-0_5 . HDL : 1942/26146 . ISBN 978-3-319-93526-3 . S2CID 52009597 .
- Ноулан, Майкл Ф.; Волински, Дэвид; Форд, Брайан (2013). Уменьшение задержки в цепях Tor с неупорядоченной доставкой . 3-й семинар USENIX по свободным и открытым коммуникациям в Интернете.