Протокол скользящего окна является функцией протоколов пакетной передачи данных . Протоколы скользящего окна используются там, где требуется надежная доставка пакетов в определенном порядке, например, на уровне канала передачи данных ( уровень OSI 2 ), а также в протоколе управления передачей (TCP). Они также используются для повышения эффективности, когда канал может включать высокую задержку .
Пакетные системы основаны на идее отправки пакета данных, пакета , вместе с дополнительными данными, которые позволяют получателю убедиться, что он был получен правильно, возможно, контрольной суммой . Парадигма похожа на окно, раздвигающееся вбок, чтобы разрешить ввод новых пакетов и отклонить те, которые уже были подтверждены. Когда получатель проверяет данные, он отправляет сигнал подтверждения , или «ACK», обратно отправителю, чтобы указать, что он может отправить следующий пакет. В простом автоматическом протоколе повторного запроса (ARQ) отправитель останавливается после каждого пакета и ждет, пока получатель не подтвердит. Это гарантирует, что пакеты прибудут в правильном порядке, так как за один раз может быть отправлен только один.
Время, необходимое для получения сигнала ACK, может составлять значительное количество времени по сравнению со временем, необходимым для отправки пакета. В этом случае общая пропускная способность может быть намного ниже теоретически возможной. Чтобы решить эту проблему, протоколы скользящего окна позволяют отправлять выбранное количество пакетов, окно , без необходимости ожидания ACK. Каждый пакет получает порядковый номер, и ACK отправляют обратно этот номер. Протокол отслеживает, какие пакеты были ACK, и когда они получены, отправляет больше пакетов. Таким образом, окно скользит по потоку пакетов, составляющих передачу.
Скользящие окна являются ключевой частью многих протоколов. Это ключевая часть протокола TCP, которая по своей сути позволяет пакетам прибывать не по порядку, а также встречается во многих протоколах передачи файлов, таких как UUCP-g и ZMODEM, как способ повышения эффективности по сравнению с неоконными протоколами, такими как XMODEM . См. также SEAlink .
Концептуально, каждой части передачи (пакетам в большинстве уровней канала передачи данных, но байтам в TCP) назначается уникальный последовательный порядковый номер, и получатель использует эти номера для размещения полученных пакетов в правильном порядке, отбрасывая дублирующиеся пакеты и идентифицируя отсутствующие. Проблема в том, что нет ограничений на размер порядкового номера, который может потребоваться.
Устанавливая ограничения на количество пакетов, которые могут быть переданы или получены в любой момент времени, протокол скользящего окна позволяет передавать неограниченное количество пакетов с использованием порядковых номеров фиксированного размера. Термин «окно» на стороне передатчика представляет логическую границу общего количества пакетов, которые еще должны быть подтверждены получателем. Приемник сообщает передатчику в каждом пакете подтверждения текущий максимальный размер буфера приемника (границу окна). Заголовок TCP использует 16-битное поле для сообщения отправителю размера окна приемника. Таким образом, наибольшее окно, которое может быть использовано, составляет 2 16 = 64 килобайта.
В режиме медленного старта передатчик начинает с малого количества пакетов и увеличивает количество пакетов в каждой передаче после получения пакетов подтверждения от приемника. Для каждого полученного пакета ack окно сдвигается на один пакет (логически) для передачи одного нового пакета. Когда достигается пороговое значение окна, передатчик отправляет один пакет для одного полученного пакета ack.
Если ограничение окна составляет 10 пакетов, то в режиме медленного старта передатчик может начать передавать один пакет, затем два пакета (перед передачей двух пакетов должен быть получен один пакет ack), затем три пакета и так далее до 10 пакетов. Но после достижения 10 пакетов дальнейшие передачи ограничиваются одним переданным пакетом на один полученный пакет ack. В моделировании это выглядит так, как будто окно перемещается на расстояние одного пакета для каждого полученного пакета ack. На стороне приемника окно также перемещается на один пакет для каждого полученного пакета.
Метод скользящего окна гарантирует, что перегрузка трафика в сети будет исключена. Уровень приложений будет по-прежнему предлагать данные для передачи в TCP, не беспокоясь о проблемах перегрузки сетевого трафика, поскольку TCP на стороне отправителя и получателя реализует скользящие окна буфера пакетов. Размер окна может динамически меняться в зависимости от сетевого трафика.
Для максимально возможной пропускной способности важно, чтобы передатчик не был вынужден прекратить отправку протоколом скользящего окна раньше, чем через одно время задержки приема-передачи (RTT). Предел объема данных, которые он может отправить до остановки для ожидания подтверждения, должен быть больше, чем произведение полосы пропускания на задержку канала связи. Если это не так, протокол ограничит эффективную полосу пропускания канала.
В любом протоколе связи, основанном на автоматическом запросе повтора для контроля ошибок , получатель должен подтвердить полученные пакеты. Если отправитель не получает подтверждения в течение разумного времени, он повторно отправляет данные.
Передатчик, не получивший подтверждения, не может знать, действительно ли получатель получил пакет; возможно, он был утерян или поврежден при передаче. Если механизм обнаружения ошибок выявит повреждение, получатель проигнорирует пакет, а получатель отправит отрицательное или дублирующее подтверждение. Получатель также может быть настроен так, чтобы вообще не отправлять никаких подтверждений. Аналогично получатель обычно не уверен в том, принимаются ли его подтверждения. Возможно, подтверждение было отправлено, но было утеряно или повреждено в среде передачи. В этом случае получатель должен подтвердить повторную передачу, чтобы предотвратить постоянную повторную отправку данных, но в противном случае должен ее игнорировать.
Передатчик и приемник имеют текущий порядковый номер n t и n r соответственно. У каждого из них также есть размер окна w t и w r . Размеры окна могут меняться, но в более простых реализациях они фиксированы. Размер окна должен быть больше нуля для любого прогресса.
Как правило, n t — это следующий пакет для передачи, т. е. порядковый номер первого пакета, который еще не передан. Аналогично, n r — это первый пакет, который еще не получен. Оба числа монотонно увеличиваются со временем; они только увеличиваются.
Получатель также может отслеживать наивысший полученный порядковый номер; переменная n s на единицу больше порядкового номера наивысшего полученного порядкового номера. Для простых приемников, которые принимают пакеты только по порядку ( w r = 1), это то же самое, что и n r , но может быть больше, если w r > 1. Обратите внимание на различие: все пакеты ниже n r были получены, ни один пакет выше n s не был получен, а между n r и n s были получены некоторые пакеты.
Когда получатель получает пакет, он соответствующим образом обновляет свои переменные и передает подтверждение с новым n r . Передатчик отслеживает наивысшее полученное им подтверждение n a . Передатчик знает, что все пакеты до, но не включая n a , были получены, но не уверен относительно пакетов между n a и n s ; т. е. n a ≤ n r ≤ n s .
Порядковые номера всегда подчиняются правилу, что n a ≤ n r ≤ n s < n t ≤ n a + w t . То есть:
Всякий раз, когда у передатчика есть данные для отправки, он может передать до w t пакетов до последнего подтверждения n a . То есть он может передать пакет с номером n t до тех пор, пока n t < n a + w t .
При отсутствии ошибки связи передатчик вскоре получает подтверждение для всех отправленных им пакетов, оставляя n a равным n t . Если этого не происходит после разумной задержки, передатчик должен повторно передать пакеты между n a и n t .
Методы определения «разумной задержки» могут быть чрезвычайно сложными, но они влияют только на эффективность; базовая надежность протокола скользящего окна не зависит от деталей.
Каждый раз, когда принимается пакет с номером x , получатель проверяет, попадает ли он в окно приема, n r ≤ x < n r + w r . (Простейшие получатели должны отслеживать только одно значение n r = n s .) Если он попадает в окно, получатель принимает его. Если он имеет номер n r , порядковый номер приема увеличивается на 1 и, возможно, больше, если ранее были получены и сохранены последующие пакеты. Если x > n r , пакет сохраняется до тех пор, пока не будут получены все предыдущие пакеты. [1] Если x ≥ n s , последний обновляется до n s = x +1.
Если номер пакета не находится в пределах окна приема, получатель отбрасывает его и не изменяет n r или n s .
Независимо от того, был ли принят пакет или нет, получатель передает подтверждение, содержащее текущий n r . (Подтверждение может также включать информацию о дополнительных пакетах, полученных между n r и n s , но это только повышает эффективность.)
Обратите внимание, что нет смысла делать окно приема w r больше окна передачи w t , поскольку нет необходимости беспокоиться о получении пакета, который никогда не будет передан; полезный диапазон составляет 1 ≤ w r ≤ w t .
До сих пор протокол описывался так, как будто порядковые номера имеют неограниченный размер, постоянно увеличиваясь. Однако, вместо того, чтобы передавать полный порядковый номер x в сообщениях, можно передавать только x mod N , для некоторого конечного N . ( N обычно является степенью 2 .)
Например, передатчик будет получать подтверждения только в диапазоне от n a до n t включительно. Поскольку это гарантирует, что n t − n a ≤ w t , существует не более w t +1 возможных порядковых номеров, которые могут поступить в любой момент времени. Таким образом, передатчик может однозначно декодировать порядковый номер, пока N > w t .
Более сильное ограничение накладывается приемником. Работа протокола зависит от способности приемника надежно отличать новые пакеты (которые должны быть приняты и обработаны) от повторных передач старых пакетов (которые должны быть отброшены, а последнее подтверждение передано повторно). Это можно сделать, зная размер окна передатчика. После получения пакета с номером x приемник знает, что x < n a + w t , поэтому n a > x − w t . Таким образом, пакеты с номерами x − w t больше никогда не будут переданы повторно.
Наименьшее порядковое число, которое мы когда-либо получим в будущем, это n s − w t
Приемник также знает, что n a передатчика не может быть выше, чем наивысшее подтверждение, когда-либо отправленное, которое равно n r . Таким образом, наивысший порядковый номер, который мы могли бы увидеть, равен n r + w t ≤ n s + w t .
Таким образом, есть 2 w t различных порядковых номеров, которые получатель может получить в любой момент времени. Поэтому может показаться, что мы должны иметь N ≥ 2 w t . Однако фактический предел ниже.
Дополнительное понимание заключается в том, что получателю не нужно различать порядковые номера, которые слишком малы (меньше n r ) или слишком велики (больше или равны n s + w r ). В любом случае получатель игнорирует пакет, за исключением повторной передачи подтверждения. Таким образом, необходимо только, чтобы N ≥ w t + w r . Поскольку обычно w r < w t (например, см. Go-Back-N ниже), это может разрешить большие w t в пределах фиксированного N .
Хотя его обычно отличают от протокола скользящего окна, протокол ARQ с остановкой и ожиданием на самом деле является его простейшей возможной реализацией. Окно передачи составляет 1 пакет, а окно приема — 1 пакет. Таким образом, требуется N = 2 возможных порядковых номера (удобно представленных одним битом ).
Передатчик поочередно отправляет пакеты с пометками «нечетный» и «четный». Подтверждения также говорят «нечетный» и «четный». Предположим, что передатчик, отправив нечетный пакет, не стал дожидаться нечетного подтверждения, а вместо этого немедленно отправил следующий четный пакет. Затем он может получить подтверждение с надписью «ожидаю нечетный пакет следующим». Это поставит передатчика в затруднительное положение: получил ли приемник оба пакета или ни одного?
Go-Back-N ARQ — это протокол скользящего окна с w t >1, но фиксированным w r =1. Приемник отказывается принимать любой пакет, кроме следующего в последовательности. Если пакет теряется при передаче, последующие пакеты игнорируются до тех пор, пока отсутствующий пакет не будет передан повторно, что составляет минимальную потерю одного времени на круговую передачу . По этой причине он неэффективен на соединениях, где часто теряются пакеты.
Предположим, что мы используем 3-битный порядковый номер, такой как типичный для HDLC . Это дает N =2 3 =8. Поскольку w r =1, мы должны ограничить w t ≤7. Это связано с тем, что после передачи 7 пакетов существует 8 возможных результатов: Любое от 0 до 7 пакетов могло быть успешно получено. Это 8 возможностей, и передатчику необходимо достаточно информации в подтверждении, чтобы различить их все.
Если передатчик отправит 8 пакетов, не дожидаясь подтверждения, он может оказаться в затруднительном положении, аналогичном случаю остановки и ожидания: означает ли подтверждение, что все 8 пакетов были успешно получены или ни один из них?
Наиболее общим случаем протокола скользящего окна является Selective Repeat ARQ . Для этого требуется гораздо более производительный приемник, который может принимать пакеты с порядковыми номерами выше текущего n r и хранить их до тех пор, пока пробел не будет заполнен.
Преимущество, однако, в том, что нет необходимости отбрасывать следующие правильные данные в течение одного времени кругового обхода, прежде чем передатчик может быть проинформирован о необходимости повторной передачи. Поэтому это предпочтительно для соединений с низкой надежностью и/или высоким показателем задержки полосы пропускания.
Размер окна w r должен быть больше, чем допустимое количество последовательных потерянных пакетов. Таким образом, популярны небольшие значения; w r =2 является обычным.
Чрезвычайно популярный протокол HDLC использует 3-битный порядковый номер и имеет опциональное положение для выборочного повтора. Однако, если необходимо использовать выборочный повтор, необходимо соблюдать требование n t + n r ≤ 8; если w r увеличивается до 2, w t необходимо уменьшить до 6.
Предположим, что w r =2, но используется немодифицированный передатчик с w t =7, как это обычно используется с вариантом HDLC go-back-N. Далее предположим, что приемник начинается с n r = n s =0.
Теперь предположим, что получатель видит следующую серию пакетов (все по модулю 8):
Поскольку w r =2, приемник примет и сохранит последний пакет 0 (думая, что это пакет 8 в серии), одновременно запросив повторную передачу пакета 7. Однако также возможно, что передатчик не получил никаких подтверждений и повторно передал пакет 0. В этом последнем случае приемник примет неправильный пакет как пакет 8.
Решение заключается в том, чтобы передатчик ограничил w t ≤6. При таком ограничении приемник знает, что если бы все подтверждения были потеряны, передатчик остановился бы после пакета 5. Когда он получает пакет 6, приемник может сделать вывод, что передатчик получил подтверждение для пакета 0 ( n a передатчика ≥1), и, таким образом, следующий пакет с номером 0 должен быть пакетом 8.
Существует множество способов расширения протокола: