WikiDer > Протокол скользящего окна

Sliding window protocol

А протокол скользящего окна это особенность пакетной передача данных протоколы. Протоколы скользящего окна используются там, где требуется надежная упорядоченная доставка пакетов, например, в уровень канала передачи данных (Уровень OSI 2), а также в Протокол управления передачей (TCP). Они также используются для повышения эффективности, когда канал может включать высокие задержка.

Пакетные системы основаны на идее отправки пакета данных, пакет, наряду с дополнительными данными, которые позволяют получателю убедиться, что он был получен правильно, возможно, контрольная сумма. Когда получатель проверяет данные, он отправляет сигнал подтвержденияили «ACK» обратно отправителю, чтобы указать, что он может отправить следующий пакет. В простом автоматический повторный запрос протокол (ARQ), отправитель останавливается после каждого пакета и ждет, пока получатель подтвердит подтверждение. Это гарантирует, что пакеты приходят в правильном порядке, так как одновременно может быть отправлен только один.

Время, необходимое для приема сигнала ACK, может представлять собой значительное количество времени по сравнению со временем, необходимым для отправки пакета. В этом случае общая пропускная способность может быть намного ниже теоретически возможного. Чтобы решить эту проблему, протоколы скользящего окна допускают выбранное количество пакетов, окно, чтобы быть отправленным без ожидания ACK. Каждый пакет получает порядковый номер, и ACK отправляют этот номер обратно. Протокол отслеживает, какие пакеты были подтверждены, и при их получении отправляет больше пакетов. Таким образом, окно слайды по потоку пакетов, составляющих передачу.

Раздвижные окна - ключевая часть многих протоколов. Это ключевая часть протокола TCP, которая по своей сути позволяет пакетам приходить не по порядку, а также встречается во многих протоколы передачи файлов подобно UUCP-g и ZMODEM как способ повышения эффективности по сравнению с протоколами без окон, такими как XMODEM.

Основная концепция

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

Установив ограничения на количество пакетов, которые могут быть переданы или получены в любой момент времени, протокол скользящего окна позволяет передавать неограниченное количество пакетов с использованием порядковых номеров фиксированного размера. Термин «окно» на стороне передатчика представляет собой логическая граница общего количества пакетов, еще не подтвержденных получателем. Приемник сообщает передатчику в каждом пакете подтверждения текущий максимальный размер буфера приемника (граница окна). Заголовок TCP использует 16-битное поле, чтобы сообщить отправителю размер окна получателя. Следовательно, самое большое окно, которое можно использовать, - 216 = 64 килобайта.

В режиме медленного старта передатчик начинает с малого количества пакетов и увеличивает количество пакетов в каждой передаче после получения пакетов подтверждения от приемника. Для каждого пакет подтверждения получено, окно сдвигается на один пакет (логически) для передачи одного нового пакета. При достижении порогового значения окна передатчик отправляет один пакет на один полученный пакет подтверждения.

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

Метод скользящего окна гарантирует, что трафик скопление в сети избегается. Прикладной уровень по-прежнему будет предлагать данные для передачи в TCP, не беспокоясь о проблемах перегрузки сетевого трафика, поскольку TCP на стороне отправителя и получателя реализует скользящие окна буфера пакетов. Размер окна может динамически изменяться в зависимости от сетевого трафика.

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

Мотивация

В любом протоколе связи на основе автоматический повторный запрос за контроль ошибок, получатель должен подтверждать получение пакетов. Если передатчик не получает подтверждения в течение разумного времени, он повторно отправляет данные.

Передатчик, не получивший подтверждения, не может знать, действительно ли получатель получил пакет; возможно, он был утерян или поврежден при передаче. Если обнаружение ошибок Механизм обнаруживает повреждение, пакет будет проигнорирован получателем, и получатель отправит отрицательное или дублированное подтверждение. Приемник также может быть настроен так, чтобы вообще не отправлять никаких подтверждений. Точно так же получатель обычно не уверен, принимаются ли его подтверждения. Возможно, подтверждение было отправлено, но было потеряно или повреждено в среде передачи. В этом случае получатель должен подтвердить повторную передачу, чтобы предотвратить постоянную повторную отправку данных, но в противном случае должен игнорировать это.

Работа протокола

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

Как обычно реализовано, пт - это следующий пакет, который должен быть передан, т.е. порядковый номер еще не переданного первого пакета. Так же, пр это первый еще не полученный пакет. Оба числа монотонно возрастающий со временем; они только увеличиваются.

Получатель может также отслеживать самый высокий порядковый номер, который был получен; переменная пs на единицу больше, чем порядковый номер самого высокого полученного порядкового номера. Для простых приемников, которые принимают пакеты только по порядку (шр = 1), это то же самое, что пр, но может быть больше, если шр > 1. Обратите внимание на различие: все пакеты ниже пр получены, пакетов выше нет пs были получены, и между пр и пs, получено несколько пакетов.

Когда получатель получает пакет, он соответствующим образом обновляет свои переменные и передает подтверждение с новым пр. Передатчик отслеживает самое высокое подтверждение, которое он получил па. Передатчик знает, что все пакеты до, но не включая па были получены, но не уверен насчет пакетов между па и пs; т.е. па ≤ пр ≤ пs.

Порядковые номера всегда подчиняются правилу, что па ≤ пр ≤ пs ≤ пт ≤ па + шт. То есть:

  • па ≤ пр: Наивысшее подтверждение, полученное передатчиком, не может быть выше самого высокого. пр подтвержден получателем.
  • пр ≤ пs: Диапазон полностью полученных пакетов не может выходить за пределы конца частично полученных пакетов.
  • пs ≤ пт: Максимальный полученный пакет не может быть больше самого высокого отправленного пакета.
  • пт ≤ па + шт: Самый высокий отправленный пакет ограничен наивысшим полученным подтверждением и размером окна передачи.

Работа передатчика

Когда передатчик имеет данные для отправки, он может передать до шт пакеты перед последним подтверждением па. То есть он может передать номер пакета пт так долго как пт < па+шт.

При отсутствии ошибки связи передатчик вскоре получает подтверждение для всех отправленных пакетов, оставляя па равно пт. Если этого не происходит после разумной задержки, передатчик должен повторно передать пакеты между па и пт.

Методы определения «разумной задержки» могут быть чрезвычайно сложными, но они влияют только на эффективность; базовая надежность протокола скользящего окна не зависит от деталей.

Работа приемника

Каждый раз, когда пакет пронумерован Икс получен, получатель проверяет, не попадает ли он в окно приема, пр ≤ Икс < пр+шр. (Самые простые приемники должны отслеживать только одно значение пр=пs.) Если он попадает в окно, получатель принимает его. Если он пронумерован пр, порядковый номер приема увеличивается на 1 и, возможно, больше, если ранее были приняты и сохранены дополнительные последовательные пакеты. Если Икс > пр, пакет сохраняется до тех пор, пока не будут получены все предыдущие пакеты.[1] Если Икс≥пs, последний обновлен до пs=Икс+1.

Если номер пакета не находится в окне приема, получатель отбрасывает его и не изменяет пр или же пs.

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

Обратите внимание, что нет смысла иметь окно приема шр больше, чем окно передачи шт, потому что нет необходимости беспокоиться о получении пакета, который никогда не будет передан; полезный диапазон 1 ≤ шр ≤ шт.

Требуется диапазон порядковых номеров

Основная статья: арифметика серийных номеров
Порядковые номера по модулю 4, с шр= 1. Первоначально, пт=пр=0

До сих пор протокол описывался так, как будто порядковые номера имеют неограниченный размер и постоянно увеличиваются. Однако вместо передачи полного порядкового номера Икс в сообщениях можно передавать только Икс модN, для некоторого конечного N. (N обычно степень 2.)

Например, передатчик будет получать подтверждения только в диапазоне па к пт, включительно. Поскольку это гарантирует, что пт−па ≤ шт, есть не более шт+1 возможных порядковых номера, которые могут появиться в любой момент времени. Таким образом, передатчик может однозначно декодировать порядковый номер до тех пор, пока N > шт.

Приемник накладывает более сильное ограничение. Работа протокола зависит от способности получателя надежно отличать новые пакеты (которые должны быть приняты и обработаны) от повторных передач старых пакетов (которые должны быть отброшены, и повторной передачи последнего подтверждения). Это можно сделать, зная размер окна передатчика. После получения пакета пронумерованный Икс, получатель знает, что Икс < па+шт, так па > Икс−шт. Таким образом, пакеты пронумерованы Икс−шт больше никогда не будет передаваться повторно.

Самый низкий порядковый номер, который мы когда-либо получим в будущем, - это пs−шт

Приемник также знает, что передатчик па не может быть выше, чем наивысшее из когда-либо отправленных подтверждений, которое пр. Итак, самый высокий порядковый номер, который мы могли бы увидеть, это пр+шт ≤ пs+шт.

Таким образом, есть 2шт разные порядковые номера, которые получатель может получить в любой момент. Может показаться, что мы должны иметь N ≥ 2шт. Однако фактический предел ниже.

Дополнительное понимание состоит в том, что получателю не нужно различать слишком низкие порядковые номера (менее пр) или слишком высокие (больше или равны пs+шр). В любом случае получатель игнорирует пакет, за исключением повторной передачи подтверждения. Таким образом, необходимо только, чтобы N ≥ шт+шр. Как обычно бывает шр<шт (например, см. Go-Back-N ниже), это может позволить шт в пределах фиксированного N.

Примеры

Самое простое скользящее окно: остановка и ожидание

Хотя обычно отличается от протокола скользящего окна, остановка и ожидание ARQ протокол на самом деле является самой простой из возможных его реализаций. Окно передачи составляет 1 пакет, а окно приема - 1 пакет. Таким образом, N = 2 возможных порядковых номера (удобно представленных одним кусочек) необходимы.

Пример неоднозначности

Передатчик поочередно отправляет пакеты, помеченные как «нечетные» и «четные». В благодарностях также говорится «нечетное» и «четное». Предположим, что передатчик, отправив нечетный пакет, не ждал нечетного подтверждения, а вместо этого немедленно отправил следующий четный пакет. Затем он может получить подтверждение, говорящее «ожидает следующего нечетного пакета». Это поставило бы передатчик в затруднительное положение: получатель получил оба пакета или ни один из них?

Go-Back-N

Go-Back-N ARQ протокол скользящего окна с шт> 1, но фиксированная шр= 1. Получатель отказывается принимать любой пакет, кроме следующего по порядку. Если пакет теряется при передаче, следующие пакеты игнорируются до тех пор, пока отсутствующий пакет не будет повторно передан, минимальная потеря одного время поездки туда и обратно. По этой причине он неэффективен для каналов, которые часто теряют пакеты.

Пример неоднозначности

Предположим, что мы используем 3-битный порядковый номер, типичный для HDLC. Это дает N=23= 8. С шр= 1, мы должны ограничить шт≤7. Это связано с тем, что после передачи 7 пакетов возможны 8 результатов: От 0 до 7 пакетов могло быть успешно получено. Это 8 возможностей, и передатчику требуется достаточно информации в подтверждении, чтобы различить их все.

Если передатчик отправил 8 пакетов, не дожидаясь подтверждения, он может оказаться в затруднительном положении, аналогичном случаю остановки и ожидания: означает ли подтверждение, что все 8 пакетов были получены успешно, или ни один из них?

Выборочный повтор

Самый общий случай протокола скользящего окна: Селективный повторный ARQ. Это требует гораздо более мощного приемника, который может принимать пакеты с порядковыми номерами выше, чем текущий. пр и храните их, пока не заполните пробел.

Преимущество, однако, состоит в том, что нет необходимости отбрасывать следующие правильные данные в течение одного времени приема-передачи до того, как передатчик может быть проинформирован о необходимости повторной передачи. Поэтому это предпочтительнее для ссылок с низкой надежностью и / или высокой продукт задержки полосы пропускания.

Размер окна шр должно быть только больше, чем количество последовательный потерянные пакеты, которые можно терпеть. Таким образом, популярны небольшие значения; шр= 2 является обычным.

Пример неоднозначности

Чрезвычайно популярный Протокол HDLC использует 3-битный порядковый номер и имеет возможность выборочного повтора. Однако, если необходимо использовать селективный повтор, требование, чтобы пт+пр ≤ 8 необходимо поддерживать; если шр увеличивается до 3, шт необходимо уменьшить до 6.

Предположим, что шр = 2, но используется немодифицированный передатчик с шт = 7, как обычно используется с вариантом HDLC с возвратом N. Далее предположим, что получатель начинается с пр =пs =0.

Теперь предположим, что получатель видит следующую серию пакетов (все по модулю 8):

0 1 2 3 4 5 6 (Пауза) 0

Потому что шр = 2, получатель примет и сохранит последний пакет 0 (считая, что это пакет 8 в серии), одновременно запрашивая повторную передачу пакета 7. Однако также возможно, что передатчик не получил никаких подтверждений и повторно передал пакет 0. В последнем случае получатель примет неправильный пакет как пакет 8.

Решение состоит в том, чтобы передатчик ограничил шт ≤6. С этим ограничением получатель знает, что, если бы все подтверждения были потеряны, передатчик остановился бы после пакета 5. Когда он принимает пакет 6, получатель может сделать вывод, что передатчик получил подтверждение для пакета 0 ( па ≥1), и, следовательно, следующий пакет с номером 0 должен быть пакетом 8.

Расширения

Есть много способов расширения протокола:

  • В приведенных выше примерах предполагается, что пакеты никогда не переупорядочиваются при передаче; они могут быть потеряны при транспортировке (обнаружение ошибок делает коррупцию эквивалентной потере), но никогда не выходит из строя. Протокол может быть расширен для поддержки переупорядочения пакетов при условии, что расстояние может быть ограничено; модуль порядкового номера N должно быть увеличено на максимальное расстояние разупорядочения.
  • Можно не подтверждать каждый пакет, если в конце концов будет отправлено подтверждение, если есть пауза. Например, TCP обычно подтверждает каждый второй пакет.
    • Обычно передатчик немедленно информирует, если обнаружен разрыв в последовательности пакетов. Для этого HDLC имеет специальный пакет REJ (отклонение).
  • Размеры окон передачи и приема могут быть изменены во время связи, пока их сумма остается в пределах N. Обычно каждому из них назначаются максимальные значения, соответствующие этому пределу, но рабочее значение в любой момент времени может быть меньше максимального. Особенно:
    • Обычно размер окна передачи уменьшают, чтобы замедлить передачу в соответствии со скоростью канала, избегая насыщенность или же скопление.
    • Одним из распространенных упрощений выборочного повторения является так называемый SREJ-REJ ARQ. Это работает с шр= 2 и буферизует пакеты, следующие за промежутком, но допускает только один потерянный пакет; в ожидании этого пакета, шр= 1, и если второй пакет потерян, пакеты больше не буферизуются. Это дает большую часть преимущества в производительности полного протокола выборочного повторения с более простой реализацией.

Смотрите также

Рекомендации

  1. ^ Петерсон, Ларри Л. и Дэви, Брюс С. "Компьютерные сети: системный подход", Морган Кауфманн, 2000. ISBN 1-55860-577-0
  • Комер, Дуглас Э. "Межсетевое взаимодействие с TCP / IP, Том 1: Принципы, протоколы и архитектура", Prentice Hall, 1995. ISBN 0-13-216987-8
  • Петерсон, Ларри Л. и Дэви, Брюс С. «Компьютерные сети: системный подход», Морган Кауфманн, 2000. ISBN 1558605142

внешняя ссылка