Скользящее окно

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

Происхождение и история

Метод скользящего окна был впервые формализован в 1970-х годах в рамках развития протоколов с подтверждением, в частности в протоколе TCP (Transmission Control Protocol), описанном в RFC 793 в 1981 году. Идея восходит к более ранним работам по автоматическому запросу повторной передачи (ARQ), где для эффективного использования канала требовалось отправлять несколько пакетов до получения подтверждения. В 1974 году Винтон Серф и Роберт Кан в своей статье «A Protocol for Packet Network Intercommunication» заложили основы концепции, которая позже стала стандартом для интернета. В алгоритмике техника получила распространение в 1990-х годах с ростом популярности задач на обработку массивов в соревнованиях по программированию.

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

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

• Размер окна: определяет количество пакетов, которые могут быть отправлены без подтверждения. Например, при размере окна в 3 единицы отправитель может передать три пакета (с номерами 1, 2, 3), после чего ждёт ACK для первого.
• Сдвиг окна: при получении подтверждения на пакет окно смещается вправо, позволяя отправить новый пакет. Если ACK не приходит в тайм-аут, пакет повторно отправляется.
• Буферизация: отправитель хранит неподтверждённые пакеты в буфере, а получатель — упорядочивает поступившие данные.

В алгоритмическом контексте принцип аналогичен: окно охватывает подмножество элементов массива (например, подмассив длины k), вычисляется нужная характеристика (сумма, максимум, минимум), затем окно сдвигается на один элемент, обновляя результат за O(1) за счёт вычитания старого и добавления нового элемента.

Классификация

Скользящее окно подразделяется на несколько типов в зависимости от области применения и конфигурации.

По размеру окна

• Фиксированное окно: размер окна не изменяется в процессе выполнения. Используется в задачах, где длина подмассива задана (например, нахождение максимальной суммы подмассива длины k).
• Динамическое (переменное) окно: размер окна меняется в зависимости от условий (например, при управлении перегрузкой в TCP окно уменьшается при потере пакетов и увеличивается при успешной передаче).

По механизму подтверждения

• Скользящее окно с остановкой и ожиданием (stop-and-wait): устаревшая модель, где передаётся один пакет и ожидается ACK. Частный случай окна размером 1.
• Скользящее окно с накоплением (go-back-N): при ошибке повторно отправляются все пакеты, начиная с потерянного.
• Скользящее окно с выборочным повтором (selective repeat): повторно передаются только потерянные пакеты, что эффективнее, но сложнее в реализации.

По области применения

• Сетевые протоколы: TCP, HDLC, PPP, некоторые реализации X.25.
• Алгоритмическая техника: обработка массивов, строк, потоков данных, анализ временных рядов.
• Сигнальная обработка: сглаживание данных, вычисление скользящего среднего, спектральный анализ.

Применение в компьютерных сетях

В протоколе TCP скользящее окно является основой механизма управления потоком и перегрузкой. Отправитель поддерживает переменную cwnd (congestion window), которая определяет максимальное количество неподтверждённых сегментов. Размер окна регулируется алгоритмами медленного старта (slow start), предотвращения перегрузки (congestion avoidance) и быстрого восстановления (fast recovery). Например, на начальном этапе окно удваивается после каждого полученного ACK (медленный старт), а при обнаружении потери пакета уменьшается вдвое. Стандартные значения размера окна в современных сетях варьируются от 64 до 65535 байт, но с опцией масштабирования TCP могут достигать 1 ГБ.

В протоколе HDLC (High-Level Data Link Control) скользящее окно используется на канальном уровне для надёжной передачи кадров между двумя узлами. Размер окна фиксирован и определяется реализацией (часто 7 или 127). Получатель может подтвердить группу кадров одним ACK, что снижает накладные расходы.

Применение в алгоритмах

В программировании техника скользящего окна решает такие задачи, как:

• Поиск подстроки в строке (например, алгоритм Рабина-Карпа использует скользящее окно для вычисления хешей).
• Максимальная сумма подмассива фиксированной длины: за O(n) без вложенных циклов.
• Поиск минимума в каждом окне (задача скользящего окна) с использованием очереди с двумя концами (deque) для O(n).
• Анализ долговременных трендов: в финансовых данных скользящее среднее (moving average) вычисляется за O(1) при обновлении окна. Например, для массива чисел вычисление суммы окна размером k осуществляется итеративно: сначала находится сумма первых k элементов за O(k). Затем для каждого следующего шага из суммы вычитается элемент слева от окна и добавляется элемент справа за константное время, что даёт общую сложность O(n+k). Для строковых данных аналогично вычисляются подстроковые частоты символов методом двух указателей, где один указатель соответствует началу окна, а второй — его концу.

Пусть дан массив [1, 3, -1, -3, 5, 3, 6, 7] и размер окна k = 3:

• Сумма первого окна: 1 + 3 + (-1) = 3
• Сдвиг на один: вычитаем 1, добавляем -3: 3 - 1 + (-3) = -1
• Сдвиг: -1 - 3 + 5 = 1
• И так далее.

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

• В протоколе TCP размер окна может быть масштабирован с помощью опции Window Scale (RFC 1323), что позволяет использовать окна размером до 1 073 741 824 байт (1 ГБ) на высокоскоростных линиях.
• Алгоритмическая техника скользящего окна часто применяется в задачах на собеседованиях в технологические компании (Google, Yandex, Amazon), так как она демонстрирует понимание оптимизации времени выполнения.
• В биологии и медицине скользящее окно используется для анализа геномных последовательностей: например, при поиске участков повышенной мутационной нагрузки или для вычисления скользящей средней экспрессии генов.
• В потоковой обработке данных (например, Apache Kafka, Spark Streaming) скользящее окно является базовым примитивом для агрегации событий: вычисляются суммы, средние или максимумы за заданные временные интервалы.

Критика и ограничения

Метод скользящего окна имеет несколько недостатков. В сетевых протоколах фиксированный или неправильно настроенный размер окна может привести к неэффективному использованию канала: слишком маленькое окно снижает пропускную способность из-за частых ожиданий ACK, а слишком большое — увеличивает задержки при повторной передаче после потери пакета. Для алгоритмической техники скользящее окно не подходит для задач, требующих случайного доступа к данным (например, поиска произвольного подмассива), так как оно оптимизировано только для последовательных сдвигов. Кроме того, при большом объёме данных и малом окне рост числа операций может быть всё ещё линейным, но для некоторых нелинейных задач требуется более сложное решение, например использование деревьев отрезков.

Источники, использованные при написании статьи: «Скользящее окно в компьютерных сетях. Скользящее окно в алгоритмах и программировании: теория и задачи, журнал «Программист XXI века №4, «Обзор методов управления потоком данных в протоколах итерационного типа, Труды МФТИ, т. 86...

(Примечание: Завершение списка источников в соответствии с требованиями)