/* Протокол 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 у данных процедур имеется входной параметр, означающий номер фрейма, таймер которого нужно запустить или остановить.
В этом протоколе и отправитель, и получатель работают с окнами неподтвержденных и допустимых номеров фреймов соответственно. Размер окна отправителя начинается с нуля и растет до определенного уровня. Размер окна получателя, напротив, всегда фиксированного размера. Получатель должен иметь буфер для каждого фрейма, номер которого находится в пределах окна. С каждым буфером связан бит, показывающий, занят буфер или свободен. Когда приходит фрейм, функция 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, обнаруживает его и передает старый буферизированный пакет сетевому уровню как новый. Таким образом, сетевой уровень получает неверный пакет; это означает, что протокол со своей задачей не справился.
Причина неудачи в том, что при сдвиге окна получателя новый интервал допустимых номеров фреймов перекрыл старый. Соответственно, присылаемый набор фреймов может содержать как новые фреймы (если все подтверждения были получены), так и повторно высланные старые (если подтверждения были потеряны). У принимающей стороны нет возможности отличить их.