Протокол скользящего окна — это особенность пакетных протоколов передачи данных . Протоколы скользящего окна используются там, где требуется надежная упорядоченная доставка пакетов, например, на уровне канала передачи данных ( уровень OSI 2 ), а также в протоколе управления передачей (TCP). Они также используются для повышения эффективности, когда канал может иметь большую задержку .
Пакетные системы основаны на идее отправки пакета данных ( пакета) вместе с дополнительными данными, которые позволяют получателю убедиться, что он был получен правильно, например, контрольной суммой . Эта парадигма аналогична окну, сдвигающемуся вбок, чтобы разрешить ввод новых пакетов и отклонить те, которые уже были подтверждены. Когда получатель проверяет данные, он отправляет сигнал подтверждения или «ACK» обратно отправителю, чтобы указать, что он может отправить следующий пакет. В простом протоколе автоматического запроса повторения (ARQ) отправитель останавливается после каждого пакета и ждет подтверждения от получателя. Это гарантирует, что пакеты прибудут в правильном порядке, поскольку одновременно может быть отправлен только один.
Время, необходимое для получения сигнала ACK, может представлять собой значительный промежуток времени по сравнению со временем, необходимым для отправки пакета. В этом случае общая пропускная способность может оказаться значительно ниже теоретически возможной. Чтобы решить эту проблему, протоколы скользящего окна позволяют отправлять выбранное количество пакетов ( окно ) без необходимости ожидания подтверждения. Каждый пакет получает порядковый номер, и подтверждения отправляют обратно этот номер. Протокол отслеживает, какие пакеты были подтверждены, и при их получении отправляет дополнительные пакеты. Таким образом, окно скользит по потоку пакетов, составляющих передачу.
Скользящие окна являются ключевой частью многих протоколов. Это ключевая часть протокола TCP, которая по своей сути позволяет пакетам приходить не по порядку, а также встречается во многих протоколах передачи файлов, таких как UUCP-g и ZMODEM , как способ повышения эффективности по сравнению с неоконными протоколами, такими как XMODEM . См. также SEAlink .
Концептуально каждой части передачи (пакетам на большинстве канальных уровней, но байтам в TCP) присваивается уникальный последовательный номер, и получатель использует эти номера для размещения полученных пакетов в правильном порядке, отбрасывая повторяющиеся пакеты и идентифицируя недостающие. . Проблема заключается в том, что размер требуемого порядкового номера не ограничен.
Устанавливая ограничения на количество пакетов, которые могут быть переданы или получены в любой момент времени, протокол скользящего окна позволяет передавать неограниченное количество пакетов с использованием порядковых номеров фиксированного размера. Термин «окно» на стороне передатчика представляет собой логическую границу общего количества пакетов, которые еще не подтверждены получателем. Приемник сообщает передатчику в каждом пакете подтверждения текущий максимальный размер буфера приемника (границу окна). Заголовок TCP использует 16-битное поле для сообщения отправителю размера окна получателя. Следовательно, максимальное окно, которое можно использовать, составляет 2 16 = 64 килобайта.
В режиме медленного старта передатчик начинает с малого количества пакетов и увеличивает количество пакетов в каждой передаче после получения пакетов подтверждения от приемника. Для каждого полученного пакета подтверждения окно сдвигается на один пакет (логически) для передачи одного нового пакета. Когда порог окна достигнут, передатчик отправляет один пакет на один полученный пакет подтверждения.
Если ограничение окна составляет 10 пакетов, то в режиме медленного запуска передатчик может начать передачу одного пакета, за которым следуют два пакета (перед передачей двух пакетов необходимо получить подтверждение одного пакета), затем три пакета и так далее, пока не будет получено 10 пакетов. Но после достижения 10 пакетов дальнейшие передачи ограничиваются одним переданным пакетом на один полученный пакет подтверждения. В моделировании это выглядит так, как будто окно перемещается на расстояние одного пакета для каждого полученного пакета подтверждения. На стороне получателя окно также перемещает один пакет на каждый полученный пакет.
Метод скользящего окна позволяет избежать перегрузок сети. Уровень приложений по-прежнему будет предлагать данные для передачи 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 не получены. ns были получены, а между n r и ns было получено несколько пакетов .
Когда получатель получает пакет, он соответствующим образом обновляет свои переменные и передает подтверждение с новым n r . Передатчик отслеживает самое высокое подтверждение, которое он получил . Передатчик знает, что все пакеты до n a , кроме n a , были получены, но не уверен относительно пакетов между n a и n s ; т.е. п а ≤ п р ≤ п 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 становится равным nt . Если этого не происходит после разумной задержки, передатчик должен повторно передать пакеты между n a и nt .
Методы определения «разумной задержки» могут быть чрезвычайно сложными, но они влияют только на эффективность; базовая надежность протокола скользящего окна не зависит от деталей.
Каждый раз, когда принимается пакет с номером x , получатель проверяет, попадает ли он в окно приема, n r ≤ x < n r + w r . (Простейшие получатели должны отслеживать только одно значение n r = n s .) Если оно попадает в окно, получатель его принимает. Если он имеет номер n r , порядковый номер приема увеличивается на 1 и, возможно, больше, если ранее были получены и сохранены дальнейшие последовательные пакеты. Если x > n r , пакет сохраняется до тех пор, пока не будут получены все предыдущие пакеты. [1] Если x ≥ n s , последнее обновляется до ns = x +1 .
Если номер пакета находится за пределами окна приема, получатель отбрасывает его и не изменяет n r или ns .
Независимо от того, принят пакет или нет, получатель передает подтверждение, содержащее текущий номер n r . (Подтверждение может также включать информацию о дополнительных пакетах, полученных между n r и ns , но это только повышает эффективность.)
Обратите внимание, что нет смысла иметь окно приема w r больше, чем окно передачи w t , поскольку нет необходимости беспокоиться о получении пакета, который никогда не будет передан; полезный диапазон: 1 ≤ w r ≤ w t .
До сих пор протокол описывался так, как будто порядковые номера имеют неограниченный размер и постоянно увеличиваются. Однако вместо передачи полного порядкового номера x в сообщениях можно передавать только x mod N для некоторого конечного N. ( N обычно представляет собой степень 2. )
Например, передатчик будет получать подтверждения только в диапазоне от n a до n t включительно. Поскольку он гарантирует, что nt − 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 различных порядковых номера, которые получатель может принять в любой момент времени. Поэтому может показаться, что мы должны иметь 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 пакетов были получены успешно, или ни один из них?
Наиболее общим случаем протокола скользящего окна является выборочный повторный 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 с возвратом-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.
Существует множество способов расширения протокола: