Возникает новый вопрос: сколько буферов должно быть у получателя? Ни при каких условиях он не должен принимать фреймы, номера которых не попадают в окно. Поэтому количество необходимых буферов равно размеру окна, а не диапазону порядковых номеров. В приведенном выше примере 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 (true) {
wait_for_event(&event); /* пять возможных событий: см. event_type выше */
switch(event) {
case network_layer_ready: /* получить, сохранить и передать новый фрейм */
nbuffered = nbuffered + 1; /* увеличить окно отправителя */
from_network_layer(&out_buf[next_frame_to_send % NR_BUFS]); /* получить новый пакет у сетевого уровня */
send_frame(data, next_frame_to_send, frame_expected, out_buf); /* передать фрейм */
inc(next_frame_to_send); /* увеличить верхний край окна отправителя */
break;
case frame_arrivaclass="underline" /* пришел фрейм данных или с подтверждением */
from_physical_layer(&r); /* получить пришедший фрейм у физического уровня */
if (r.kind == data) {
/* Фрейм пришел в целости. */
if ((r.seq != frame_expected) && no_nak)
send_frame(nak, 0, frame_expected, out_buf); else start_ack_timer();
if (between(frame_expected,r.seq,too_far) && (arrived[r.seq%NR_BUFS]==false)) {
/* Фреймы могут приниматься в любом порядке. */
arrived[r.seq % NR_BUFS] = true; /* пометить буфер как занятый */
in_buf[r.seq % NR_BUFS] = r.info; /* поместить данные в буфер */
while (arrived[frame_expected % NR_BUFS]) {
/* Передать пакет сетевому уровню и сдвинуть окно
to_network_layer(&in_buf[frame_expected % NR_BUFS]);
no_nak = true;
arrived[frame_expected % NR_BUFS] = false;
inc(frame_expected); /* передвинуть нижний край окна получателя */
inc(too_far); /* передвинуть верхний край окна получателя */
start_ack_timer(); /* запустить вспомогательный таймер на случай, если потре-буется пересылка подтверждения отдельным фреймом */
}
}
}
if((r.kind==nak) && between(ack_expected,(r.ack+1)%(MAX_SEQ+1), next_frame_to_send))
send_frame(data, (r.ack+1) % (MAX_SEQ + 1), frame_expected, out_buf);
while (between(ack_expected, r.ack, next_frame_to_send)) {
nbuffered = nbuffered – 1; /* отправить подтверждение вместе с информационным фреймом */
stop_timer(ack_expected % NR_BUFS); /* фрейм пришел в целости */
inc(ack_expected); /* передвинуть нижний край окна отправителя */
}
break;
case cksum_err:
if (no_nak) send_frame(nak, 0, frame_expected, out_buf); /* поврежденный фрейм */
break;
case timeout:
send_frame(data, oldest_frame, frame_expected, out_buf); /* время истекло */
break;
case ack_timeout:
send_frame(ack,0,frame_expected, out_buf); /* истек период ожидания «попутки» для подтверждения; послать подтверждение */
}
if (nbuffered < NR_BUFS) enable_network_layer(); else disable_network_layer();
}
}
Илл. 3.21. Протокол раздвижного окна с выборочным повтором
Илл. 3.22. Пример работы протокола. (а) Начальная ситуация при размере окна 7. (б) Семь фреймов были посланы и приняты, но не подтверждены. (в) Начальная ситуация при размере окна 4. (г) Ситуация после того, как четыре фрейма были отправлены и получены, но не подтверждены
По этой же причине количество необходимых таймеров также равно числу буферов, а не диапазону порядковых номеров; то есть с каждым буфером связывается один таймер. Когда интервал времени истекает, содержимое буфера высылается повторно.
Протокол 6 также ослабляет неявное допущение, что загрузка канала довольно высока. Мы сделали это предположение в протоколе 5, в котором подтверждения вкладывались во фреймы данных, отсылаемые в обратном направлении. Если обратный поток информации невелик, подтверждения могут задерживаться на довольно большой период времени, создавая проблемы. В исключительной ситуации, когда в одном направлении посылается много информации, а во встречном — вообще ничего, протокол останавливается, как только окно отправителя достигает максимума.
В протоколе 6 эта проблема решена. Когда приходит последовательный фрейм данных, процедура start_ack_timer запускает вспомогательный таймер. Если таймер сработает раньше, чем появится фрейм с данными для передачи, то будет выслано отдельное подтверждение. Прерывание от вспомогательного таймера называется событием ack_timeout. При такой организации возможен однонаправленный поток данных, так как отсутствие встречных фреймов данных, в которые можно было бы вкладывать подтверждения, больше не является препятствием. Требуется всего один таймер. При вызове процедуры start_ack_timer, если таймер уже запущен, ничего не происходит. Таймер не сбрасывается и не продлевается, так как он нужен лишь для обеспечения некоторого минимального количества подтверждений.