Повторная передача и скользящее окно

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

Чтобы убедиться в необходимости повторной передачи данных, отправитель ну­мерует отправляемые кадры и для каждого кадра ожидает от приемника так на­зываемой положительной квитанции (Positive Acknowledgment, АСК) — слу­жебного кадра, извещающего о том, что исходный кадр получен и данные в нем корректны. Для того чтобы организовать такую нумерацию, и нужна процедура логического соединения — она дает точку отсчета, с которой начинается нумера­ция. Время ожидания квитанции ограничено — при отправке каждого кадра пе­редатчик запускает таймер, и, если по истечении заданного времени положи­тельная квитанция на получена, кадр считается утерянным. Приемник в случае получения кадра с искаженными данными может отправить отрицательную квитанцию (Negative Acknowledgment, NACK) — явное указание на то, что дан­ный кадр нужно передать повторно.

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

Метод простоя источника требует, чтобы источник, пославший кадр, ожидал по­лучения квитанции (положительной или отрицательной) от приемника и только после этого посылал следующий кадр (или повторял искаженный). Если же кви­танция не приходит в течение тайм-аута, то кадр (или квитанция) считается утерянным и его передача повторяется. На рис. 6.6, а видно, что в этом случае производительность обмена данными ниже потенциально возможной, — хотя пе­редатчик и мог бы послать следующий кадр сразу же после отправки предыду­
щего, он обязан ждать прихода положительной квитанции. (Далее, где это не искажает существо рассматриваемого вопроса, положительные квитанции для краткости будут называться просто «квитанциями».)

р-----------------

— 2

|Ч----------------

->\ 3

^ кадры

--------- ►

Интервал отправки

I АСК'1

IАСК 2

IАСК 31

Квитанции

Полученные кадры

И

W!

w₀

п + 11

••I m

w + n

w + 11"

ACK n|

\JACK11JACK 2\

N im

W₀ = _W1 = w_n

Направление скольжения окна

W-j

W₀

H--- h-

^{123 n + 1 ww + 1 w + n} Номеракадров

Рис. 6.6. Методы восстановления искаженных и потерянных кадров

Недостатки этого метода коррекции особенно заметны на низкоскоростных ка­налах связи, то есть в территориальных сетях.

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

-h

В начальный момент, когда еще не послано ни одного пакета, окно определяет диапазон пакетов с номерами от 1 до W включительно. Источник начинает пере­давать пакеты и получать в ответ квитанции. Для простоты предположим, что квитанции поступают в той же последовательности, что и пакеты, которым они
соответствуют. В момент t_t при получении первой квитанции К_{ окно сдвигается на одну позицию, определяя новый диапазон от 2 до (W + 1).

Процессы отправки пакетов и получения квитанций идут достаточно независи­мо друг от друга. Рассмотрим произвольный момент времени t_n, когда источник получает квитанцию на пакет с номером п. Окно сдвигается вправо и определяет диапазон разрешенных к передаче пакетов от (п + 1) до (W + п). Все множество пакетов, выходящих из источника, можно разделить на перечисленные ниже группы (см. рис. 6.6, б).

□ Пакеты с номерами от 1 до п уже были отправлены и квитанции на них полу­чены, то есть они находятся за пределами окна слева.

□ Пакеты, начиная с номера (п + 1) и заканчивая номером (W + п), находятся в пределах окна и потому могут быть отправлены, не дожидаясь прихода ка­кой-либо квитанции. Этот диапазон может быть разделен еще на два поддиа­пазона:

О пакеты с номерами от (п + 1) до m уже отправлены, но квитанции на них еще не получены;

О пакеты с номерами от m до (W + п) пока не отправлены, хотя запрета на это нет.

□ Все пакеты с номерами, большими или равными (W + п + 1), находятся за пределами окна справа и поэтому пока не могут быть отправлены.

Перемещение окна вдоль последовательности номеров пакетов иллюстрирует рис. 6.6, в. Здесь t₀ — исходный момент, t_t и t_n — моменты прихода квитанций на первый и п-й пакет соответственно. Каждый раз, когда приходит квитанция, окно сдвигается влево, но его размер при этом не меняется и остается равным W.

При отправке пакета в источнике устанавливается тайм-аут. Если за это время квитанция на отправленный пакет не придет, пакет (или квитанция на него) счи­тается утерянным, и пакет передается снова.

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

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

В других методах используются отрицательные квитанции. Отрицательные кви­танции бывают двух типов — групповые и избирательные. Групповая квитанция содержит номер пакета, начиная с которого нужно повторить передачу всех па­кетов, отправленных передатчиком в сеть. Избирательная отрицательная кви­танция требует повторной передачи только одного пакета.

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

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

Размер окна может быть постоянным параметром алгоритма скользящего окна. В этом случае он выбирается при установлении соединения и не меняется в те­чение сеанса. Существуют также адаптивные версии алгоритма, когда размер окна меняется в течение сеанса в соответствии с текущим состоянием сети и узла назначения.

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

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

Существуют также реализации метода скользящего окна, в которых в качестве размера окна используется не количество пакетов, а количество байтов. Наибо­лее известным примером такого подхода является протокол TCP.

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