ARQ с остановкой и ожиданием

Методы повторной передачи

Повторная передача испорченных и потерянных блоков данных является широко используемой адаптационной процедурой и основным механизмом обеспечения безошибочной передачи данных. Повторная передача используется протоколами разных уровней сетевого стека, но не обязательно всеми. В стеке TCP/IP, например, она предусмотрена только на транспортном уровне.

В общем случае, передающий и принимающий модули уровневого протокола, в котором предусмотрен механизм повторной передачи, обмениваются своими протокольными блоками (для краткости будем называть их кадрами), типы которых представлены на рисунке 3.4. Хост А, отправляя какую-то порцию информации хосту B, формирует I-кадр, в котором кроме информационного поля содержатся заголовок (Н) и контрольная сумма (CRC). Уровневый протокол хоста B информирует хост-отправитель о результатах проверки достоверности I-кадра посылкой управляющего кадра (С-кадр), содержащего только заголовок и контрольную сумму. В случае фиксации ошибки в принятом I-кадре инициируется автоматический запрос его повторной передачи (Automatic Repeat reQuest, ARQ).

Хост А

		Рис.3.4. Основные типы пакетов ARQ-протоколов

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

Существует несколько вариантов реализации ARQ, из которых наибольший интерес представляют ARQ с остановкой и ожиданием, ARQ с возвратом на N и ARQ с выборочным повторением. Общая схема работы этих механизмов следующая. Отправитель при посылке каждого кадра сохраняет его копию в буфере и запускает специальный таймер time-out обратного отсчета. Получатель обязан направлять подтверждение о каждом принятом без ошибок кадров (положительное подтверждение, Acknowledgement, АСК). Если управляющий кадр-подтверждение не пришел к отправителю до момента, когда таймер time-out достиг нулевого значения, он (отправитель) считает, что отправленный ранее кадр потерян (испорчен) и инициализирует его повторную отправку. Перечисленные выше варианты ARQ отличаются дисциплиной передачи кадров данных и подтверждений, а также правилами, которыми руководствуется приемник, контролируя их прибытие.

ARQ с остановкой и ожиданием

Протокол, использующий механизм ARQ с остановкой и ожиданием (Stop-and-Wait ARQ, SW-ARQ), организует работу передатчика и приемника так, что в любой момент времени в канале связи находится не более одного кадра; поэтому, такой метод ARQ может использоваться и при полудуплексном режиме связи. Рис.3.5.а показывает, каким образом механизм тайм-аута и управляющие кадры только положительных подтверждений (АСК) обеспечивают надежную доставку данных.

На первый взгляд, такая процедура никаких требований к нумерации ни I- ни С-кадров не предъявляет. Однако, на рис. 3.5.б и 3.5.в представлены ситуации, когда без нумерации отправляемых кадров этот механизм ARQ теряет работоспособность.

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

Для рассматриваемого механизма ARQ даже двоичная нумерация отправляемых кадров является достаточной. Действительно, пусть передатчик в двоичной переменной сохраняет номер (0 или 1) последнего отправленного кадра, а приемник в двоичной переменной записывает значение на единицу большее номера последнего принято кадра (т.е. номер следующего кадра). В целом, состояние системы «передатчик-приемник» описывается вектором ( , ). В начальном состоянии – это вектор (0, 0). Такое состояние системы не может измениться до тех пор, пока приемник не получит без ошибок кадр с номером 0, т.е. до этого момента станция А(передатчик) с периодичностью, определяемой значением тайм-аута, будет отсылать кадр с номером 0. Получив кадр 0 и убедившись, что указанный в нем порядковый номер совпадает с текущим значением , станция Вустанавливает иотсылает управляющий кадр АСК, в специальном поле заголовка которого передает значение этой переменной. Так система переходит в состояние (0, 1). Начиная с этого момента любой кадр данных, имеющий порядковый номер 0, будет восприниматься станцией В как дубликат уже принятого кадра и уничтожаться; при этом, на каждый уничтоженный дубликатный кадр приемником будет отсылаться АСК со значением .

Как только станция А получит АСК с , она установит значение своей переменной и отправит очередной кадр номер 1. Тем самым, система переходит в состояние (1, 1). После успешного приема 1-го кадра состояние системы будет описываться вектором (1, 0), а получение хостом Аподтверждения успешного приема кадра с порядковым номером 1 изменит значение вектора состояния протокола в (0,0). Таким образом, протокол с двоичной нумерацией кадров обеспечивает строго определенные состояния системы «передатчик-приемник» и гарантирует корректную доставку и прием всех информационных кадров.

Описанный механизм нумерации кадров является простейшей реализацией алгоритма «скользящего окна», широко используемого механизмами ARQ в уровневых протоколах. Сущностью этого алгоритма является то, что передающий хост всегда «знает» диапазон последовательных номеров кадров, которые он имеет право отослать. Нижняя (левая) граница этого диапазона равна максимальному номеру благополучно отправленного кадра +1, а верхняя граница определяются величиной окна передачи. При отсылке каждого кадра увеличивается значение левой границы окна (левая граница сдвигается вправо, окно уменьшается), а при получении подтверждения успешной доставки очередного из отправленных кадров – увеличивается значение правой границы окна передачи (граница сдвигается вправо, ширина окна увеличивается и оно «перемещается» вправо).В свою очередь, узел-получатель поддерживает приемное окно, т.е. диапазон номеров кадров, которые он имеет право принять. Получение кадра без ошибок и с номером, равным нижней границе окна, приводит к увеличению ее значения на единицу; передача кадра модулю протокола вышестоящего уровня смещает вправо верхнюю границу окна приема. Любой пришедший кадр с порядковым номером, не попадающим в окно приема, игнорируется (уничтожается) без каких-либо дополнительных действий. Таким образом, входящие в диапазон окна передачи номера, соответствуют кадрам, которые передатчик имеет право отослать, а номера, входящие в окно приема, являются номерами кадров, которые при получении не будут уничтожены. Очевидно, что текущий размер окон может изменяться от некоторого максимального значения до нуля. Максимальные размеры окон передачи и приема не обязаны быть одинаковыми; более того, они могут изменяться и, тем самым, регулировать интенсивность потока кадров. В алгоритме SW-ARQ размеры окон фиксированы и равны 1.

Рассмотренный вариант ARQ становится весьма неэффективным на линиях с высокой пропускной способностью и/или большим временем полного оборота. Пусть, например, время передачи кадра в 1000 бит и получение подтверждения его приема по каналу с номинальной пропускной способностью 1,5 Мбит/с, составляет 40 мс. Использование механизма SW-ARQ приведет к тому, что коэффициент использования этого канала (отношение числа переданных за определенный интервал времени бит Q к номинальному числу бит, которые могли бы быть переданы за тот же интервал времени, Q_nom) составит

.

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

Тем не менее, SW-ARQ успешно используется протоколами, управляющими передачей данных по линиям с низкой номинальной пропускной способностью, в частности, модемным протоколом передачи файлов XMODEM. Используется этот механизм повторной передачи и в канальном протоколе современных беспроводных сетей IEEE 802.11.

ARQ c возвратом на N

Невысокая производительность протоколов, использующих ARQ с остановкой и ожиданием, на относительно высокоскоростных линиях может быть преодолена, если разрешить передатчику посылать кадры «пачками», не ожидая получения подтверждения успешной доставки каждого из них. Именно это и предусматривает протокол ARQ с возвратом на N (GO-Back-N ARQ, GBN-ARQ).

Будем считать, что все кадры снабжены порядковыми номерами 0, 1, 2,…. Пусть также задана величина «пачки», т.е. максимальное число кадров , которое передатчик имеет право отослать в канал, не дожидаясь получения подтверждения успешного приема первого кадра из этой «пачки» ( – это размер окна передачи). Значение обычно выбирается примерно равным величине , где - время, затрачиваемое протоколом на отправку информационного кадра и получение подтверждения его доставки, С – номинальная пропускная способность канала (битовая скорость его интерфейса) и n – средняя величина кадра (бит). Такой выбор величины гарантирует полную загрузку канала при наличии кадров для передачи и отсутствии ошибок.

Пусть передатчик отправил кадры с номерами 0, 1, …., . Если к моменту готовности отсылки кадра с номером подтверждение успешной доставки нулевого кадра, было получено, то кадр с номером отсылается. В общем случае, если в момент времени, когда готов к отправке кадр с номером L+1, оказывается, что доставка кадра с номером не подтверждена, то передатчик останавливается, ожидает некоторое заранее определенное время (тайм-аут) и, после его истечения, считает все последние кадров утерянными (следствие единичного окна приема). Далее выполняется повторная отсылка кадров с номерами , и т.д. (рис.3.6).

ARQ с возвратом на N является алгоритмом управления передатчиком посредством механизма скользящего окна. Его работу иллюстрирует рис. 3.7. Передатчик ведет учет кадров, разрешенных к отправке. Начальный номер этого списка является порядковым номером кадра, следующего за тем, чья успешная доставка была уже подтверждена и, одновременно, левой границей окна передачи. Правой границей окна передачи является значение . Номер соответствует последнему из отправленных кадров. Каждый отосланный, но еще не подтвержденный кадр сохраняется в специальной буферной памяти передатчика. Когда счетчик достигает значения , т.е. верхней границы окна передачи, отправка кадров прекращается до момента получения сообщения ACK, подтверждающего доставку кадра с номером большим, или равным . Это увеличивает значение на единицу или более и, тем самым, смещает вправо верхнюю границу диапазона разрешенных к передаче кадров.

Для того, чтобы обеспечить правильный учет принятых кадров и соответствующее информирование передатчика, приемное устройство формирует окно приема, размер которого равен 1, а указателем является переменная , принимающая значение на единицу больше номера принятого кадра. Очередной принятый кадр, в котором не обнаружены ошибки и порядковый номер которого равен , передается протоколу вышестоящего уровня, а значение увеличивается на единицу. Каждый кадр АСК, отправляемый приемником, содержит обновленное значение , чем и подтверждается успешный прием всех кадров, номера которых меньше . Передатчик, получив такой АСК, фиксирует успешный прием всех кадров с номерами 0, 1, 2,…, даже, если подтверждение о приеме какого-то из этих блоков данных ранее им получены не были. (Эта кумулятивность подтверждений важна, поскольку прием подтверждений не подтверждается и особенно полезна для высокопроизводительных передатчиков). Фиксация успешной передачи осуществляется передатчиком посредством модификации значения своей переменной . Устанавливая = , передатчик перемещает указатель как нижней, так и верхней границ разрешенных к передаче кадров на единицу, или более, вверх.

Если за время тайм-аута, отсчитываемого по кадру с номером , кадр АСК с не получен, то передатчик считает ранее переданные кадры с номерами от и выше (вплоть до ) утерянными и повторяет их передачу. Время тайм-аута должно несколько превосходить суммарное среднее время, необходимое для пересылки кадра максимального размера и получения положительного подтверждения (время полного оборота, Round Trip Time, RTT). С учетом возможности пересылки подтверждения в составе заголовка информационного кадра, передаваемого в обратном направлении, продолжительность тайм-аута должна включать в себя удвоенное время передачи кадра максимальной длины (2 ), удвоенное время распространения электромагнитных колебаний в среде передачи (2 ) и удвоенное время обработки кадра принимающим модулем (2 )

.

Очевидно, что для корректной работы протокола очень важна нумерация кадров. Пусть число двоичных разрядов, отведенных в заголовке кадра для его порядкового номера, равно m. Это позволяет последовательно пронумеровать не более кадров. Ясно, что в передаваемом потоке будут присутствовать серии кадров, порядковые номера которых повторяются с периодом . Механизма, позволяющего приемнику самостоятельно однозначно определить, какой из серий принадлежит прибывший кадр с порядковым номером , не существует. Поэтому, для исключения ошибочной интерпретации кадров необходим запрет отправки в канал кадра с номером равным номеру еще не подтвержденного кадра предыдущего цикла (приемник принципиально не должен получать кадры с одинаковыми номерами). Это требование накладывает ограничения на величину окна передачи . Рис.3.8.б показывает, что если , то механизм ARQ с возвратом на N не будет допускать ошибок в идентификации кадров.

	Рис.3.8. Размер окна передачи GBN-ARQ должен быть меньше 2m

В условиях, когда (т.е. время тайм-аута заметно больше времени полного оборота между передатчиком и приемником) потеря кадра и повторная его передача через будет сопровождаться интервалом бездействия канала. Для ослабления этого негативного эффекта в качестве сигнала потери кадра с номером k принимается получение нескольких кадров АСК с неизменным (равным k) значением параметра (так называемые, дубликатные АСК). Обычно, считают надежной индикацией потери получение трех АСК с неизменным . Однако, следует отметить, что если не все кадры, разрешенные величиной переданы (вышестоящий модуль может их просто не сформировать еще), то передатчик до истечения тайм-аута, связанного с неподтвержденным кадром, не сможет возвратиться к повторной передаче, несмотря на наличие информации о её необходимости (получение дубликатных R_next).

Очевидно, что ARQ с возвратом на N для реализации своих преимуществ в части исключения «простоя» линии связи требует организации обратного канала и может применяться лишь при дуплексном режиме связи. Если между взаимодействующими сетевыми узлами осуществляется взаимный информационный обмен, то объем пересылаемых управляющих кадров может быть уменьшен посредством включения сообщений АСК в заголовок информационных кадров, направляемых в обратном направлении. Если в момент получения корректного информационного кадра станция В не располагает своим информационным кадром для станции А, то она запускает АСК-таймер, определяющий максимально допустимое время ожидания от своего вышестоящего уровня такого кадра. По истечении АСК-тайм-аута станция B отправляет подтверждение посредством обычного АСК-кадра.

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

ARQ с возвратом на N является базисным механизмом обеспечения надежности передачи данных в современных канальных протоколах; используется он и протоколом TCP.