Компьютерные сети. 6-е изд. - Эндрю Таненбаум

не расходуются ресурсы. Подход, при котором подтверждения временно откладываются и прикрепляются к следующему исходящему фрейму данных, называется вложенным подтверждением (piggybacking).

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

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

Раздвижное окно

Следующие три протокола являются двунаправленными и принадлежат к классу протоколов раздвижного окна (sliding window). Как будет показано ниже, они отличаются друг от друга эффективностью, сложностью и требованиями к размерам буфера. Во всех протоколах раздвижного окна каждый исходящий фрейм содержит порядковый номер (в диапазоне от 0 до некоторого максимума). Этот номер должен поместиться в поле размером n бит, поэтому его максимальное значение обычно составляет 2n – 1. В протоколах раздвижного окна с остановкой и ожиданием n = 1; это ограничивает порядковый номер значениями 0 и 1, однако в более сложных версиях может использоваться произвольное значение n.

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

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

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

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

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

Илл. 3.15. Раздвижное окно размера 1 с 3-битным порядковым номером. (а) Начальная ситуация. (б) После отправки первого фрейма. (в) После приема первого фрейма. (г) После приема первого подтверждения

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

На илл. 3.15 показан пример для окна с максимальным размером 1. Вначале фреймов в окне нет, поэтому оно пустое и его верхний и нижний края совпадают, однако с течением времени ситуация меняется. В отличие от окна отправителя, окно получателя всегда сохраняет первоначальный размер, сдвигаясь по мере приема и передачи на сетевой уровень очередного фрейма.

3.4.2. Примеры дуплексных протоколов раздвижного окна

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

Однобитное раздвижное окно

Прежде чем рассматривать общий случай, изучим протокол раздвижного окна, равного 1. Такой протокол использует метод ожидания: отослав фрейм, отправитель должен дождаться подтверждения, прежде чем послать следующий фрейм.

Данный протокол показан на илл. 3.16. Как и другие протоколы, он начинается с определения некоторых переменных. Переменная next_frame_to_send содержит номер фрейма, который отправитель пытается послать. Аналогично переменная frame_expected хранит номер фрейма, ожидаемого получателем. В обоих случаях возможными значениями могут быть только 0 и 1.

/* Протокол 4 (раздвижное окно) является дуплексным

#define MAX_SEQ 1                              /* в протоколе 4 должно быть равно 1

typedef enum {frame_arrival, cksum_err, timeout} event_type;

#include "protocol.h"

void protocol4 (void)

{

seq_nr next_frame_to_send;                    /* только 0 или 1 */

seq_nr frame_expected;                        /* только 0 или 1 */

frame r, s;                                   /* временные переменные */

packet buffer;                                /* текущий отправленный пакет */

event_type event;

next_frame_to_send = 0;                       /* номер следующего фрейма в исходящем потоке */

frame_expected = 0;                           /* номер ожидаемого фрейма */

from_network_layer(&buffer);                  /* получить первый пакет у сетевого уровня */

s.info = buffer;                              /* подготовить первый фрейм для передачи */

s.seq = next_frame_to_send;                   /* вставить порядковый номер во фрейм */

s.ack = 1 – frame_expected;                   /* подтверждение, вложенное во фрейм данных */

to_physical_layer(&s);                        /* передать фрейм */

start_timer(s.seq);                           /* запустить таймер ожидания подтверждения */

while (true) {

     wait_for_event(&event);                   /* ждать события frame_arrival, cksum_err или timeout */

     if (event == frame_arrival) {             /* фрейм пришел в целости */

           from_physical_layer(&r);            /* получить пришедший фрейм */

           if (r.seq == frame_expected) {      /* обработать входящий поток фреймов */

                  to_network_layer(&r.info);   /* передать пакет сетевому уровню */

                  inc(frame_expected);         /* инвертировать порядковый номер фрейма, ожидаемого в следующий раз */

           }

           if