Оконная очередь сообщений

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

История возникновения

Концепция оконной очереди сообщений тесно связана с развитием протоколов управления передачей данных в сетях с негарантированной доставкой (например, в ранних версиях TCP/IP и X.25). В 1970-х годах, с ростом популярности пакетной коммутации, возникла необходимость в механизме, который бы предотвращал переполнение буферов приёмника и обеспечивал надёжную доставку без блокировки отправителя на время ожидания подтверждения.

Первое формальное описание «скользящего окна» (sliding window) как основы оконной очереди было предложено в рамках разработки протокола TCP в 1974 году (RFC 675, авторы — Винтон Серф, Йохан Постел и др.). Идея заключалась в том, чтобы хранить в очереди не все отправленные пакеты, а только те, которые входят в текущее окно — диапазон последовательных номеров, разрешённых для передачи без получения подтверждения. Это позволило значительно повысить пропускную способность по сравнению с простым протоколом «остановись и жди» (stop-and-wait), где каждое сообщение требовало индивидуального подтверждения.

Принцип работы

Оконная очередь сообщений реализуется на стороне отправителя и приёмника. Основные компоненты:

• Окно отправки — диапазон номеров последовательности (sequence numbers), которые отправитель может передать в данный момент. Размер окна (W) измеряется в байтах или пакетах.
• Окно приёма — диапазон номеров, которые приёмник готов принять и буферизовать. Приёмник сообщает отправителю свой размер окна (обычно через поле Window Size в заголовках TCP).
• Буфер очереди — хранилище для сообщений, ожидающих отправки (на стороне отправителя) или ожидающих сборки (на стороне приёмника).

Процесс передачи выглядит следующим образом:

1. Отправитель помещает в оконную очередь сообщение с номером N.
2. Если N входит в текущее окно отправки (N ≤ последний_подтверждённый + W), сообщение отправляется немедленно.
3. При получении подтверждения (ACK) на сообщение с номером K, отправитель сдвигает окно: последний_подтверждённый = K, и может отправлять новые сообщения с номерами до K + W.
4. Если окно исчерпано (все номера в диапазоне уже отправлены, но не подтверждены), отправитель приостанавливает передачу до получения следующего ACK.

На стороне приёмника оконная очередь работает как буфер с пропусками: пришедшие сообщения могут быть не по порядку (например, из-за потери или задержки предыдущих). Приёмник хранит их в очереди до тех пор, пока не будет получено недостающее сообщение, после чего вся последовательность передаётся приложению.

Виды оконных очередей

По принципу управления размером окна

• Статическое окно — размер окна фиксирован и согласован заранее. Прост в реализации, но не адаптируется к изменениям нагрузки.
• Динамическое окно — размер окна изменяется в зависимости от состояния сети (например, алгоритм медленного старта TCP, алгоритм предотвращения перегрузки). Позволяет избежать перегрузок и эффективно использовать пропускную способность.

По направлению передачи

• Однонаправленная оконная очередь — используется только для передачи данных в одном направлении (например, в протоколах без обратной связи, таких как UDP с ручным управлением окном).
• Двунаправленная (полнодуплексная) оконная очередь — обе стороны могут одновременно отправлять и принимать данные, используя отдельные окна для каждого направления. Реализована в TCP.

По способу обработки потерь

• Оконная очередь с повторной передачей по тайм-ауту — при отсутствии подтверждения в течение заданного времени сообщение отправляется заново.
• Оконная очередь с выборочным повтором (Selective Repeat) — приёмник может запросить повторную передачу только потерянных сообщений, а не всего окна. Более эффективна при высоких задержках, но требует сложной логики на стороне приёмника.
• Оконная очередь с возвратом на N (Go-Back-N) — при потере сообщения отправитель повторно передаёт все сообщения, начиная с потерянного. Проще в реализации, но менее эффективна.

Применение

Сетевые протоколы

• TCP (Transmission Control Protocol) — основной протокол транспортного уровня, использующий оконную очередь сообщений для обеспечения надёжности и управления потоком. Размер окна в TCP может достигать 65 535 байт (классический) или до 1 ГБ (при использовании опции Window Scaling).
• SCTP (Stream Control Transmission Protocol) — использует оконную очередь для передачи сообщений в рамках нескольких потоков, поддерживая частичную упорядоченность.
• Протоколы канального уровня — например, HDLC (High-Level Data Link Control) и его варианты, где оконная очередь применяется для управления кадровыми передачами.

Операционные системы

• Буферизация ввода/вывода — в ядре Linux оконная очередь используется для организации очередей сообщений между процессами (например, в механизме mqueue), где размер окна ограничивает количество непрочитанных сообщений.
• Драйверы сетевых карт — для временного хранения пакетов перед отправкой или после приёма, с использованием кольцевых буферов, реализующих принцип оконной очереди.

Промышленные системы и телекоммуникации

• Протоколы реального времени — в системах управления движением, телеметрии и связи с ограниченной задержкой оконная очередь позволяет гарантировать доставку критически важных сообщений без перегрузки канала.
• Системы массового обслуживания — в программных комплексах для обработки запросов (например, в веб-серверах или очередях задач) оконная очередь используется для ограничения числа одновременно обрабатываемых запросов.

Преимущества и недостатки

Преимущества

• Повышение пропускной способности — за счёт одновременной передачи нескольких сообщений без ожидания подтверждения каждого.
• Управление перегрузками — динамическое изменение окна позволяет адаптироваться к состоянию сети и избежать потери пакетов.
• Надёжность — механизм подтверждений и повторной передачи обеспечивает доставку даже при потерях.
• Эффективное использование буферов — приёмник может хранить только сообщения в пределах окна, а не весь поток.

Недостатки

• Задержка при потере — в режиме Go-Back-N при потере одного сообщения приходится повторно передавать все последующие, что увеличивает задержку.
• Сложность реализации — динамическое управление окном, обработка тайм-аутов и выборочных повторов требуют значительных вычислительных ресурсов и точной настройки.
• Чувствительность к задержкам — при высокой задержке канала (например, в спутниковой связи) окно должно быть большим, что может привести к перегрузке буферов.
• Необходимость синхронизации — отправитель и приёмник должны согласовывать размер окна и номера последовательности, что может быть уязвимо для атак (например, TCP-сессионный захват).

Критика и альтернативы

Оконная очередь сообщений в классическом виде (особенно в TCP) подвергалась критике за неэффективность в высокоскоростных сетях с большими задержками (так называемая «проблема длинных толстых сетей»). В ответ были разработаны альтернативные механизмы:

• Протокол QUIC (разработан Google, используется в HTTP/3) — использует мультиплексирование потоков и независимые оконные очереди для каждого потока, что уменьшает влияние потери одного пакета на другие.
• Протоколы с кодированием (Network Coding) — например, в системах на основе RLNC (Random Linear Network Coding) сообщения кодируются так, что приёмник может восстановить данные, получив любые K из N пакетов, без необходимости повторной передачи.
• Протоколы без оконной очереди — в некоторых приложениях (например, потоковое видео) используются протоколы с негарантированной доставкой (UDP), где оконная очередь не применяется, а потеря пакетов компенсируется на уровне приложения.

Интересные факты

• В TCP размер окна может быть увеличен с помощью опции Window Scaling, что позволяет передавать до 1 ГБ данных без подтверждения, что критически важно для высокоскоростных каналов (например, 10 Гбит/с и выше).
• Алгоритм медленного старта TCP, управляющий размером оконной очереди, был разработан Ван Якобсоном в 1988 году и до сих пор является основой для большинства реализаций TCP в мире.
• В некоторых системах реального времени оконная очередь используется не для передачи данных, а для синхронизации процессов — например, в очереди сообщений с фиксированным окном в ядре FreeBSD.

Источники

• RFC 675 — Specification of Internet Transmission Control Program (1974)
• RFC 793 — Transmission Control Protocol (1981)
• RFC 5681 — TCP Congestion Control (2009)
• Tanenbaum, A. S., Wetherall, D. J. — Computer Networks, 5th Edition (2011)
• Kurose, J. F., Ross, K. W. — Computer Networking: A Top-Down Approach, 7th Edition (2017)
• Документация Linux Kernel — mqueue (7), tcp (7)