 | Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . ( Август 2010 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
Скользящее окно протокол является функцией пакетной передачи данных протоколов . Протоколы скользящего окна используются там, где требуется надежная упорядоченная доставка пакетов, например, на уровне канала данных ( уровень 2 OSI ), а также в протоколе управления передачей (TCP). Они также используются для повышения эффективности, когда канал может иметь большую задержку .
Пакетные системы основаны на идее отправки пакета данных, пакета вместе с дополнительными данными, которые позволяют получателю убедиться, что он был получен правильно, возможно, контрольной суммой . Когда получатель проверяет данные, он отправляет сигнал подтверждения , или «ACK», обратно отправителю, чтобы указать, что он может отправить следующий пакет. В простом протоколе автоматического запроса на повторение (ARQ) отправитель останавливается после каждого пакета и ждет, пока получатель подтвердит подтверждение. Это гарантирует, что пакеты приходят в правильном порядке, так как за один раз можно отправлять только один.
Время, необходимое для приема сигнала ACK, может представлять собой значительный промежуток времени по сравнению со временем, необходимым для отправки пакета. В этом случае общая пропускная способность может быть намного ниже теоретически возможной. Чтобы решить эту проблему, протоколы скользящего окна позволяют отправлять выбранное количество пакетов, окно , без необходимости ждать ACK. Каждый пакет получает порядковый номер, и ACK отправляют этот номер обратно. Протокол отслеживает, какие пакеты были подтверждены, и при их получении отправляет больше пакетов. Таким образом, окно скользит по потоку пакетов, составляющих передачу.
Раздвижные окна - ключевая часть многих протоколов. Это ключевая часть протокола TCP, который по своей сути позволяет пакетам приходить не по порядку, а также используется во многих протоколах передачи файлов, таких как UUCP-g и ZMODEM, как способ повышения эффективности по сравнению с протоколами без окон, такими как XMODEM .
Основная концепция [ править ]
Концептуально каждой части передачи (пакетам на большинстве уровней канала передачи данных, но байтам в 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 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 . То есть:
- n a ≤ n r : Наивысшее подтверждение, полученное передатчиком, не может быть выше, чем наивысшее n r, подтвержденное получателем.
- n r ≤ n s : диапазон полностью принятых пакетов не может выходить за пределы частично принятых пакетов.
- n s ≤ n t : Максимальный полученный пакет не может быть больше самого высокого отправленного пакета.
- 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 .
Требуется диапазон порядковых номеров [ изменить ]
До сих пор протокол описывался так, как будто порядковые номера имеют неограниченный размер и постоянно увеличиваются. Однако вместо передачи полной последовательности чисел х в сообщениях, можно передавать только х мод N , для некоторого конечного N . ( N обычно степень двойки .)
Например, передатчик будет получать подтверждения только в диапазоне от 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 . Как это распространено иметь ш г < ш т (например , см Go-Back-N ниже), это может позволить больший вес т в фиксированном N .
Примеры [ править ]
Простейшее скользящее окно: остановка и ожидание [ править ]
Хотя протокол ARQ с остановкой и ожиданием обычно отличается от протокола скользящего окна, на самом деле он является самой простой из возможных его реализаций. Окно передачи составляет 1 пакет, а окно приема - 1 пакет. Таким образом, требуется N = 2 возможных порядковых номера ( обычно представляемых одним битом ).
Пример неоднозначности [ править ]
Передатчик поочередно отправляет пакеты, помеченные как «нечетные» и «четные». В благодарностях также написано «нечетное» и «четное». Предположим, что передатчик, отправив нечетный пакет, не ждал нечетного подтверждения, а вместо этого немедленно отправил следующий четный пакет. Затем он может получить подтверждение о том, что «следующий ожидает нечетный пакет». Это поставило бы передатчик в затруднительное положение: получатель получил оба пакета или ни один из них?
Go-Back-N [ править ]
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 увеличивается до 3, w t необходимо уменьшить до 6.
Предположим, что w r = 2, но используется немодифицированный передатчик с w t = 7, как обычно используется с вариантом HDLC с возвратом N. Далее предположим, что приемник начинается с n r = n s = 0.
Теперь предположим, что получатель видит следующую серию пакетов (все по модулю 8):
- 0 1 2 3 4 5 6 (пауза) 0
Поскольку w r = 2, получатель примет и сохранит последний пакет 0 (считая, что это пакет 8 в серии), одновременно запрашивая повторную передачу пакета 7. Однако также возможно, что передатчик не получил никаких подтверждений и повторно передал пакет 0. В последнем случае получатель принял бы неправильный пакет как пакет 8.
Решение состоит в том, чтобы передатчик ограничил w t ≤6. С этим ограничением приемник знает, что если бы все подтверждения были потеряны, передатчик остановился бы после пакета 5. Когда он принимает пакет 6, приемник может сделать вывод, что передатчик получил подтверждение для пакета 0 ( n a ≥1 передатчика ). , и, следовательно, следующий пакет с номером 0 должен быть пакетом 8.
Расширения [ править ]
Существует много способов расширения протокола:
- В приведенных выше примерах предполагается, что пакеты никогда не переупорядочиваются при передаче; они могут быть потеряны при транспортировке ( обнаружение ошибок делает повреждение эквивалентным потере), но никогда не появятся вне очереди. Протокол может быть расширен для поддержки переупорядочивания пакетов при условии, что расстояние может быть ограничено; модуль порядкового номера N должен быть увеличен на максимальное расстояние разупорядочения.
- Можно не подтверждать каждый пакет, если в конце концов будет отправлено подтверждение, если есть пауза. Например, TCP обычно подтверждает каждый второй пакет.
- Обычно передатчик немедленно информирует, если обнаружен разрыв в последовательности пакетов. Для этого HDLC имеет специальный пакет REJ (отклонение).
- Передающие и приемных размеры окна могут быть изменены во время сеанса связи, пока их сумма остается в пределах лимита N . Обычно каждому из них назначаются максимальные значения, соответствующие этому пределу, но рабочее значение в любой момент времени может быть меньше максимального. В частности:
- Обычно размер окна передачи уменьшается, чтобы замедлить передачу в соответствии со скоростью канала, избегая насыщения или перегрузки .
- Одним из распространенных упрощений выборочного повторения является так называемый SREJ-REJ ARQ. Это работает с w r = 2 и буферизует пакеты, следующие за промежутком, но допускает только один потерянный пакет; в ожидании этого пакета w r = 1, и если второй пакет потерян, пакеты больше не буферизуются. Это дает большую часть преимущества в производительности полного протокола выборочного повторения с более простой реализацией.
См. Также [ править ]
- Федеральный стандарт 1037C
- Составной TCP
- Арифметика серийных номеров
- TCP Fast Open
Ссылки [ править ]
- ^ Петерсон, Ларри Л. и Дэви, Брюс С. « Компьютерные сети: системный подход », Морган Кауфманн, 2000. ISBN 1-55860-577-0
- Комер, Дуглас Э. " Межсетевое взаимодействие с TCP / IP, Том 1: Принципы, протоколы и архитектура", Прентис Холл, 1995. ISBN 0-13-216987-8
- Петерсон, Ларри Л. и Дэви, Брюс С. «Компьютерные сети: системный подход», Морган Кауфманн, 2000. ISBN 1558605142
Внешние ссылки [ править ]
- RFC 1323 - Расширения TCP для высокой производительности
- Масштабирование окна TCP и сломанные маршрутизаторы , 2004 г.
- Демонстрация скользящего окна ( требуется Flash )
