Блокування початку черги (HOL-блокування) у комп'ютерних мережах — це явище, що обмежує продуктивність і виникає, коли черга пакетів затримується через перший пакет у черзі. Це відбувається, наприклад, у мережевих комутаторах із вхідною буферизацією, під час доставки в зміненому порядку та при виконанні кількох запитів у конвеєризації HTTP.
Мережеві комутатори
Комутатор може складатися з буферизованих вхідних портів, комутаційної матриці та буферизованих вихідних портів. Якщо використовуються вхідні буфери «першим прийшов — першим вийшов» (FIFO), для пересилання доступний лише найстаріший пакет. Якщо найстаріший пакет не може бути переданий через те, що його цільовий вихід зайнятий, новіші пакети не можуть бути переслані. Вихід може бути зайнятий через конкуренцію за вихід.
Без HOL-блокування нові пакети потенційно могли б бути переслані в обхід застряглого найстарішого пакета до відповідних пунктів призначення. HOL-блокування може спричиняти погіршення продуктивності систем із вхідною буферизацією.
Це явище обмежує пропускну здатність комутаторів. Для вхідних буферів FIFO проста модель комірок фіксованого розміру з рівномірно розподіленими пунктами призначення призводить до обмеження пропускної здатності до 58,6 % від загальної, коли кількість ліній стає великою.
Одним зі способів подолання цього обмеження є використання віртуальних вихідних черг.
Лише комутатори з вхідною буферизацією можуть страждати від HOL-блокування. За достатньої внутрішньої пропускної здатності вхідна буферизація непотрібна; вся буферизація виконується на виходах, і HOL-блокування уникається. Ця архітектура без вхідної буферизації поширена в комутаторах Ethernet малого та середнього розміру.
Доставка не в порядку Невпорядкована доставка відбувається, коли пронумеровані пакети надходять не в тому порядку. Це може статися через різні шляхи, якими проходять пакети, або через те, що пакети були відкинуті та надіслані повторно. HOL-блокування може значно збільшити перевпорядкування пакетів.
Надійна широкомовна передача повідомлень через мережу з втратами між великою кількістю вузлів є складною проблемою. Хоча алгоритми атомарної широкомовної передачі розв'язують проблему єдиної точки відмови централізованих серверів, ці алгоритми створюють проблему блокування початку черги. Алгоритм Bimodal Multicast, увипадковлений алгоритм, що використовує Gossip протокол, уникає блокування початку черги, дозволяючи деяким повідомленням бути отриманими не в порядку.
У HTTP Однією з форм HOL-блокування в HTTP/1.1 є ситуація, коли кількість дозволених паралельних запитів у браузері вичерпано, а наступні запити мають чекати завершення попередніх. HTTP/2 розв'язує цю проблему за допомогою мультиплексування запитів, яке усуває HOL-блокування на рівні застосунків, але HOL все ще існує на транспортному рівні (TCP).
У надійних потоках байтів
Блокування початку черги може виникати в надійних потоках байтів: якщо пакети перевпорядковано або втрачено й вони потребують повторного передавання (і тому надходять не в порядку), дані з послідовно пізніших частин потоку можуть бути отримані раніше за послідовно ранніші частини потоку; однак пізніші дані зазвичай не можуть бути використані, доки не буде отримано ранніші дані, що спричиняє мережеву затримку. Якщо кілька незалежних повідомлень вищого рівня інкапсулюються та мультиплексуються в один надійний потік байтів, тоді блокування початку черги може призвести до того, що обробка повністю отриманого повідомлення, яке було надіслано пізніше, очікуватиме доставки повідомлення, яке було надіслано раніше. Це впливає, наприклад, на HTTP/2, який розбиває на кадри кілька пар запит–відповідь в одному потоці; HTTP/3, який має конструкцію фреймінг на рівні застосунків і використовує дейтаграми, а не потоковий транспорт, уникає цієї проблеми. Погіршення затримки через блокування початку черги залежить від базового рівня втрат пакетів та часу проходження в обидва боки, причому більша кількість втрат спричиняє гіршу затримку. Без зміни абстракції потоку зменшення втрат пакетів може зменшити шкоду від блокування початку черги; альтернативним підходом є реалізація надійного потоку байтів за допомогою корекції помилок вперед, щоб надсилати надлишкові дані, завдяки чому певний рівень втрат можна витримати без необхідності повторного передавання.
Див. також Надлишкова мережева буферизація Алгоритм заміщення комірок пам'яті FIFO
Примітки