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

Вопрос: все восемь фреймов из второго набора благополучно дошли до адресата или все они потерялись (включая проигнорированные фреймы после ошибочного)? В обеих ситуациях получатель отправит фрейм 7 в качестве подтверждения. У отправителя нет способа отличить один случай от другого. По этой причине максимальное количество неподтвержденных фреймов должно быть ограничено числом MAX_SEQ (а не MAX_SEQ + 1).

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

Если поступает подтверждение на фрейм n, фреймы n – 1, n – 2 (и все предыдущие фреймы) автоматически считаются подтвержденными. Такой тип подтверждения называется кумулятивным (cumulative acknowledgement). Он наиболее полезен в случае потери или повреждения предыдущих подтверждений. Получив подтверждение, канальный уровень проверяет, не освободился ли у него буфер (то есть не появилось ли свободное место в окне). Если место доступно, то заблокированному ранее сетевому уровню можно снова разрешить инициировать события network_layer_ready.

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

/* Протокол 5 (конвейерный) допускает наличие нескольких неподтвержденных фреймов. Отправитель может передать до MAX_SEQ фреймов, не ожидая подтверждения. Кроме того, в отличие от предыдущих протоколов, не предполагается, что у сетевого уровня всегда есть новые пакеты. При появлении нового пакета сетевой уровень инициирует событие network_layer_ready. */

#define MAX_SEQ 7

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

#include "protocol.h"

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

{

/* Возвращает true, если a <=b < c циклично; иначе false.

if (((a <= b) && (b < c)) || ((c < a) && (a <= b)) || ((b < c) && (c < a)))

       return(true);

    else

       return(false);

}

static void send_data(seq_nr frame_nr, seq_nr frame_expected, packet buffer[ ])

{

/* Подготовить и послать информационный фрейм. */

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

s.info = buffer[frame_nr];           /* вставить пакет во фрейм */

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

s.ack = (frame_expected + MAX_SEQ) % (MAX_SEQ + 1);  /* подтверждение, вкладываемое во фрейм данных */

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

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

}

void protocol5(void)

{

seq_nr next_frame_to_send;           /* MAX_SEQ > 1; используется для исходящего потока */

seq_nr ack_expected;                 /* самый старый неподтвержденный фрейм */

seq_nr frame_expected;               /* следующий фрейм, ожидаемый во входящем потоке */

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

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

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

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

event_type event;

enable_network_layer();              /* разрешить события network_layer_ready */

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

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

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

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

while (true) {

    wait_for_event(&event);           /* четыре возможных события: см. event_type выше */

    switch(event) {

      case network_layer_ready:       /* у сетевого уровня есть пакет для передачи */

       /* Получить, сохранить и передать новый фрейм

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

       nbuffered = nbuffered + 1;     /* увеличить окно отправителя */

       send_data(next_frame_to_send, frame_expected, buffer); /* передать фрейм */

       inc(next_frame_to_send);       /* увеличить верхний край окна отправителя */

       break;

      case frame_arrival:             /* пришел фрейм с данными или с подтверждением */

       from_physical_layer(&r);       /* получить пришедший фрейм у физического уровня */

       if (r.seq == frame_expected) {

           /* Фреймы принимаются только по порядку номеров. */

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

           inc(frame_expected);       /* передвинуть нижний край окна получателя */

       }

       /* Подтверждение для фрейма n подразумевает также фреймы n - 1, n - 2 и т.д. */

       while (between(ack_expected, r.ack, next_frame_to_send)) {

           /* Отправить подтверждение вместе с информационным фреймом. */

           nbuffered = nbuffered – 1; /* в буфере на один фрейм меньше */

           stop_timer(ack_expected);  /* фрейм пришел в целости; остановить таймер */

           inc(ack_expected);         /* уменьшить окно отправителя */

       }

       break;

      case cksum_err: break;          /* плохие фреймы просто игнорируются */

      case timeout:                   /* время истекло; передать повторно все неподтвержденные фреймы

       next_frame_to_send = ack_expected; /* номер первого посылаемого повторно фрейма */

       for (i = 1; i <= nbuffered; i++) {

           send_data(next_frame_to_send, frame_expected, buffer); /* переслать повторно 1 фрейм */

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

       }

    }

    if (nbuffered < MAX_SEQ)

       enable_network_layer();

    else

       disable_network_layer();

}

}

Илл. 3.19. Протокол раздвижного окна с возвратом к n

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

Илл. 3.20. Программная симуляция работы нескольких таймеров. (а) Очередь из нескольких периодов ожидания. (б) Ситуация после истечения первого периода ожидания

Пример того, как можно реализовать несколько таймеров, приведен на илл. 3.20 (а). Предположим, что часы изменяют свое состояние каждую 1 мс. Пусть начальное значение реального времени будет 10:00:00.000, при этом имеются три таймера тайм-аутов, установленные на 10:00:00.005, 10:00:00.013 и 10:00:00.019. Каждый раз, когда аппаратные часы изменяют свое значение, реальное время обновляется и счетчик этих изменений в начале списка уменьшается на единицу. Когда значение счетчика становится равным нулю, инициируется тайм-аут, а узел удаляется из списка, как показано на илл. 3.20 (б). Такая организация таймеров не требует большой работы при каждом прерывании от системных часов, хотя при вызове процедур start_timer и stop_timer требуется сканирование списка. В протоколе 5 у данных процедур имеется входной параметр, означающий номер фрейма, таймер которого нужно запустить или остановить.

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