/* пришел неповрежденный фрейм */
from_physical_layer(&r); /* получить пришедший фрейм */
if (r.seq == frame_expected) { /* именно этот фрейм и ожидался */
to_network_layer(&r.info); /* передать данные сетевому уровню */
inc(frame_expected); /* в следующий раз ожидать фрейм с другим порядковым номером */
}
s.ack = 1 – frame_expected; /* номер фрейма, для которого посылается подтверждение */
to_physical_layer(&s); /* отправить подтверждение */
}
}
}
Илл. 3.14. Протокол с положительным подтверждением и повторной передачей
сылке следующего фрейма, часто называется PAR (Positive Acknowledgement with Retransmission — положительное подтверждение с повторной передачей) или ARQ (Automatic Repeat reQuest — автоматический запрос повторной передачи). Подобно протоколу 2, он передает данные только в одном направлении.
Протокол 3 отличается от своих предшественников тем, что и отправитель, и получатель содержат переменную, значение которой хранится, пока канальный уровень находится в режиме ожидания. Отправитель запоминает номер следующего фрейма в переменной next_frame_to_send, а получатель записывает номер следующего ожидаемого фрейма в переменной frame_expected. Каждый протокол имеет короткую фазу инициализации перед началом бесконечного цикла.
После передачи фрейма отправитель запускает таймер. Если он уже работал, он перезапускается для отсчета нового полного интервала времени. Этот интервал должен быть достаточно большим, чтобы даже при наихудшем сценарии фрейм успел дойти до получателя, тот успел его обработать и подтверждение вернулось к отправителю. Только по истечении отведенного времени можно предположить потерю фрейма или его подтверждения и отправить дубликат. Если интервал слишком короткий, то передающее устройство будет повторно посылать слишком много фреймов, в которых нет необходимости. Хотя лишние фреймы в данном случае не повлияют на правильность приема данных, это снизит производительность системы.
После передачи фрейма отправитель запускает таймер и ждет какого-либо события. Возможны три ситуации: либо придет неповрежденный фрейм подтверждения, либо будет получен поврежденный фрейм подтверждения, либо просто истечет интервал времени. В первом случае отправитель возьмет у сетевого уровня следующий пакет и разместит его в буфере поверх предыдущего, а также увеличит порядковый номер фрейма. Если же прибудет поврежденный фрейм подтверждения или время истечет, то ни буфер, ни номер не будут изменены и будет отправлен дубликат фрейма. В любом случае затем посылается содержимое буфера (следующий пакет либо дубликат предыдущего).
Когда неповрежденный фрейм прибывает к получателю, проверяется его номер. Если это не дубликат, то фрейм принимается и передается сетевому уровню, после чего формируется подтверждение. Дубликаты и поврежденные фреймы на сетевой уровень не передаются, но при их получении подтверждается прибытие последнего правильного фрейма, благодаря чему отправитель понимает, что нужно перейти к следующему фрейму или повторить передачу поврежденного.
3.4. Повышение эффективности
В предыдущих протоколах фреймы данных передавались только в одну сторону. На практике чаще всего требуется передача в обоих направлениях. Кроме того, канальный уровень работает более эффективно, если по нему можно отправлять сразу несколько фреймов, не дожидаясь, пока придет подтверждение. Далее мы изучим обе эти концепции и рассмотрим несколько примеров протоколов, реализующих поставленные цели.
3.4.1. Цель: двунаправленная передача, отправка сразу нескольких фреймов
Ниже представлен метод так называемого вложенного подтверждения, позволяющий протоколу канального уровня обеспечить двунаправленную (дуплексную) передачу, а также метод раздвижного окна, позволяющий повысить эффективность передачи за счет отправки сразу нескольких фреймов.
Двунаправленная передача данных: вложенное подтверждение
Один из способов осуществления дуплексной передачи — использование двух экземпляров описанных выше протоколов, каждый из которых передает данные по отдельной симплексной связи (в противоположных направлениях). При этом каждое соединение включает прямой канал для данных и обратный — для подтверждений. В обоих случаях пропускная способность обратного канала почти не используется.
Гораздо эффективнее использовать для дуплексной передачи один канал. К тому же в протоколах 2 и 3 фреймы уже передавались по каналу в двух направлениях, при этом обратный канал обладает той же пропускной способностью, что и прямой. В такой модели фреймы данных и подтверждения, которые устройство A отправляет устройству B, перемешиваются. Получатель может отличить фрейм данных от фрейма с подтверждением по специальному полю заголовка фрейма — kind.
Помимо чередования подтверждений и информационных фреймов возможно и другое улучшение протокола. Приняв фрейм данных, получатель может не посылать фрейм с подтверждением сразу, а подождать, пока сетевой уровень даст ему следующий пакет. Подтверждение добавляется к исходящему фрейму данных с помощью поля ack в заголовке. В результате на передачу подтверждения почти не расходуются ресурсы. Подход, при котором подтверждения временно откладываются и прикрепляются к следующему исходящему фрейму данных, называется вложенным подтверждением (piggybacking).
Основное преимущество вложенного подтверждения — более эффективное использование пропускной способности канала. Поле ack в заголовке фрейма занимает всего несколько битов, тогда как отдельный фрейм потребует заголовка и контрольной суммы. Кроме того, чем меньше входящих фреймов, тем меньше нагрузка на получателя. В следующем протоколе, который мы рассмотрим, расходы на поле вложенного подтверждения в заголовке фрейма составляют всего 1 бит (они редко превышают несколько битов).
Однако использование вложенного подтверждения ведет к появлению новых проблем. Как долго канальный уровень должен ждать пакета, с которым следует переслать подтверждение? Если он будет ждать дольше, чем отправитель, то последний пошлет фрейм повторно и сама идея подтверждений потеряет смысл. Если бы канальный уровень мог предсказывать будущее, он бы знал, ждать ему пакет или отправить подтверждение отдельно. К сожалению, это невозможно, поэтому следует установить еще один интервал ожидания (меньший, чем у отправителя), по истечении которого подтверждение отправляется отдельным фреймом. Если же сетевой уровень успеет передать пакет канальному уровню, то подтверждение будет отослано вместе с ним в одном фрейме.
Раздвижное окно
Следующие три протокола являются двунаправленными и принадлежат к классу протоколов раздвижного окна (sliding window). Как будет показано ниже, они отличаются друг от друга эффективностью, сложностью и требованиями к размерам буфера. Во всех протоколах раздвижного окна каждый исходящий фрейм содержит порядковый номер (в диапазоне от 0 до некоторого максимума). Этот номер должен поместиться в поле размером n бит, поэтому его максимальное значение обычно составляет 2n – 1. В протоколах раздвижного окна с остановкой и ожиданием n = 1; это ограничивает порядковый номер значениями 0 и 1, однако в более сложных версиях может использоваться произвольное значение n.
Суть всех протоколов раздвижного окна заключается в том, что отправитель постоянно работает с набором порядковых номеров, соответствующих фреймам, которые ему разрешено передавать. Эти фреймы находятся в передающем окне. Аналогично получатель работает с приемным окном, содержащим набор фреймов, которые можно принять. Окна получателя и отправителя не должны иметь одинаковые нижний и верхний пределы или даже быть одного размера. В одних протоколах размеры фиксируются, а в других они могут увеличиваться или уменьшаться по мере передачи или приема фреймов.
Данные протоколы предоставляют канальному уровню большую свободу в отношении последовательности передачи и приема фреймов. Но требование доставки пакетов целевому сетевому уровню в том же порядке, в котором они были получены от передающего сетевого уровня, по-прежнему действует. Физический канал связи также должен доставлять фреймы в порядке отправления (подобно проводу).
Порядковые номера в передающем окне соответствуют уже отправленным фреймам, для которых еще не пришли подтверждения. Пришедший от сетевого уровня пакет получает наибольший порядковый номер, и верхняя граница окна увеличивается на единицу. Когда поступает подтверждение, на единицу возрастает нижняя граница окна. Таким образом, окно постоянно содержит список неподтвержденных фреймов. Пример такого протокола показан на илл. 3.15.
Фреймы, находящиеся в окне отправителя, могут быть потеряны или повреждены во время передачи, поэтому их нужно хранить в памяти на случай возможной повторной отправки. Таким образом, если максимальный размер окна равен n, то отправителю потребуется n буферов для хранения неподтвержденных фреймов. Если окно достигает максимального размера, канальный уровень должен отключить сетевой уровень до тех пор, пока не освободится буфер.
Окно принимающего канального уровня соответствует фреймам, которые он может принять. Любой фрейм, попадающий в окно, помещается в буфер получателя. Когда приходит фрейм с порядковым номером, соответствующим нижнему краю окна, он передается на сетевой уровень и окно сдвигается на одну позицию. Любой фрейм, не попадающий в окно, удаляется. В любом случае формируется подтверждение, чтобы отправитель мог понять, как ему действовать
Илл. 3.15. Раздвижное окно размера 1 с 3-битным порядковым номером. (а) Начальная ситуация. (б) После отправки первого фрейма. (в) После приема первого фрейма. (г) После приема первого подтверждения