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

    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, если таймер уже запущен, ничего не происходит. Таймер не сбрасывается и не продлевается, так как он нужен лишь для обеспечения некоторого минимального количества подтверждений.

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

Протокол 6 использует более эффективную стратегию обработки ошибок, чем протокол 5. При появлении у получателя подозрений в том, что произошла ошибка, он высылает отправителю фрейм отрицательного подтверждения (NAK). Он представляет собой запрос на повторную передачу фрейма. NAK используется в двух случаях: если фрейм пришел поврежденным или если его номер отличается от ожидаемого (возможность потери фрейма). Чтобы избежать передачи нескольких запросов на повторную передачу одного и того же фрейма, получатель должен запоминать, был ли уже отправлен NAK для данного фрейма. В протоколе 6 для этой цели применяется переменная no_nak, принимающая значение true, если NAK для ожидаемого фрейма (с номером frame_expected) еще не был послан. Если NAK повреждается или теряется по дороге, это не имеет большого значения, так как у отправителя рано или поздно истечет период ожидания положительного подтверждения и он вышлет недостающий фрейм еще раз. Если неправильный фрейм пришел после того, как NAK был выслан и потерян, переменной no_nak опять присваивается true и запускается вспомогательный таймер. Когда время истечет, для восстановления синхронизации текущих состояний отправителя и получателя будет отправлено положительное подтверждение (ACK).

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

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

С вопросом тайм-аутов и отрицательных подтверждений тесно связана проблема определения фрейма, вызвавшего тайм-аут. В протоколе 5 это всегда фрейм с номером ack_expected, поскольку он является старшим. В протоколе 6 нет столь простого способа определить фрейм с истекшим интервалом ожидания. Предположим, были переданы фреймы с 0-го по 4-й, то есть список неподтвержденных фреймов выглядит так: 01234 (от первого к последнему). Теперь допустим, что у фрейма 0 истекает интервал ожидания и он передается повторно, затем посылается фрейм 5 (новый), далее интервал ожидания истекает у фреймов 1 и 2 и посылается фрейм 6 (также новый). В результате список неподтвержденных фреймов принимает вид 3405126, начиная с самого старого и заканчивая самым новым. Если весь встречный