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