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

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

Начальное состояние окон отправителя и получателя изображено на илл. 3.22 (а). Отправитель передает фреймы с 0-го по 6-й. Окно получателя позволяет ему принимать любые фреймы с номерами от 0 по 6 включительно. Все семь фреймов успешно доставляются, поэтому получатель подтверждает их прием и передвигает окно для приема фреймов с номерами 7, 0, 1, 2, 3, 4 и 5, как показано на илл. 3.22 (б). Все семь буферов помечаются как свободные.

Именно в этот момент происходит авария: молния ударяет в телефонный столб и стирает все подтверждения. Протокол обязан отработать правильно, несмотря ни на какие чрезвычайные ситуации. Отправитель, не дождавшись подтверждений, посылает повторно фрейм 0. Когда он приходит получателю, производится проверка на предмет того, попадает ли он в его окно. На илл. 3.22 (б) фрейм 0, к сожалению, попадает в новое окно и потому принимается получателем как новый фрейм. Получатель также отправляет вложенное подтверждение для фрейма 6, поскольку были приняты все фреймы с 0-го по 6-й.

Отправитель с радостью узнает, что все переданные им фреймы успешно достигли адресата, поэтому он тут же передает фреймы 7, 0, 1, 2, 3, 4 и 5. Фрейм 7 принимается получателем, и содержащийся в нем пакет передается сетевому уровню. Сразу после этого принимающий канальный уровень проверяет наличие фрейма 0, обнаруживает его и передает старый буферизированный пакет сетевому уровню как новый. Таким образом, сетевой уровень получает неверный пакет; это означает, что протокол со своей задачей не справился.

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

Чтобы решить эту проблему, нужно убедиться, что в сдвинутом положении окно не перекроет исходное окно. Размер окна не должен превышать половины от количества порядковых номеров, как показано на илл. 3.22 (в) и 3.22 (г). Например, если для порядковых номеров используются 3 бита, они должны изменяться в пределах от 0 до 7. В таком случае в любой момент времени только четыре фрейма могут быть неподтвержденными. Таким образом, если будут получены фреймы с 0-го по 3-й и будет передвинуто окно для приема фреймов с 4-го по 7-й, получатель сможет безошибочно отличить повторную передачу (фреймы с 0-го по 3-й) от новых фреймов (с 4-го по 7-й). Поэтому в протоколе 6 применяется окно размером (MAX_SEQ + 1)/2.

Возникает новый вопрос: сколько буферов должно быть у получателя? Ни при каких условиях он не должен принимать фреймы, номера которых не попадают в окно. Поэтому количество необходимых буферов равно размеру окна, а не диапазону порядковых номеров. В приведенном выше примере 3-битных номеров требуется четыре буфера с номерами от 0 до 3. Когда приходит фрейм i, он помещается в буфер i mod 4. Обратите внимание, что хотя i и (i + 4), взятые по модулю 4, «соревнуются» за один и тот же буфер, они никогда не оказываются в одном окне одновременно, потому что это привело бы к увеличению размера окна по крайней мере до 5.

/* Протокол 6 (выборочный повтор) принимает фреймы в любом порядке, но передает их сетевому уровню, соблюдая порядок. С каждым неподтвержденным фреймом связан таймер. При срабатывании таймера передается повторно только этот фрейм, а не все неподтвержденные фреймы, как в протоколе 5.

#define MAX_SEQ 7                 /* должно быть 2^n-1 */

#define NR_BUFS ((MAX_SEQ + 1)/2)

typedef enum {frame_arrival, cksum_err, timeout, network_layer_ready, ack_timeout} event_type;

#include "protocol.h"

boolean no_nak = true;            /* отрицательное подтверждение (nak) еще не посылалось */

seq_nr oldest_frame = MAX_SEQ+1;  /* начальное значение для симулятора */

static boolean between(seq_nr a, seq_nr b, seq_nr c)

{

/* То же, что и в протоколе 5, но короче и запутаннее.

return ((a <= b) && (b < c)) || ((c < a) && (a <= b)) || ((b < c) && (c < a));

}

static void send_frame(frame_kind fk, seq_nr frame_nr, seq_nr frame_expected, packet buffer[ ])

{

/* Сформировать и послать данные, а также положительное или отрицательное подтверждение */

frame s;                         /* временная переменная */

s.kind = fk;                     /* kind == data, ack или nak */

if (fk == data) s.info = buffer[frame_nr % NR_BUFS];

s.seq = frame_nr;                /* имеет значение только для информационных фреймов */

s.ack = (frame_expected + MAX_SEQ) % (MAX_SEQ + 1);

if (fk == nak) no_nak = false;   /* один nak на фрейм, пожалуйста */

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

if (fk == data) start_timer(frame_nr % NR_BUFS);

stop_ack_timer();                /* отдельный фрейм с подтверждением не нужен */

}

void protocol6(void)

{

seq_nr ack_expected;             /* нижний край окна отправителя */

seq_nr next_frame_to_send;       /* верхний край окна отправителя + 1 */

seq_nr frame_expected;           /* нижний край окна получателя */

seq_nr too_far;                  /* верхний край окна получателя + 1 */

int i;                           /* индекс массива буферов */

frame r;                         /* временная переменная */

packet out_buf[NR_BUFS];         /* буферы для исходящего потока */

packet in_buf[NR_BUFS];          /* буферы для входящего потока */

boolean arrived[NR_BUFS];        /* входящая битовая карта */

seq_nr nbuffered;                /* количество использующихся в данный момент выходных буферов */

event_type event;

enable_network_layer();          /* инициализация */

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

next_frame_to_send = 0;          /* номер следующего посылаемого фрейма */

frame_expected = 0;

too_far = NR_BUFS;

nbuffered = 0;                   /* вначале буфер пуст */

for (i = 0; i < NR_BUFS; i++) arrived[i] = false;

while