Выборочный повтор
Протокол с возвратом к n хорошо работает, если ошибки встречаются нечасто, однако при плохом соединении он впустую тратит время и ресурсы, передавая фреймы по два раза. В качестве альтернативы можно использовать протокол с выборочным повтором (selective repeat), который позволяет получателю принимать и буферизировать фреймы, переданные после поврежденного или утерянного фрейма.
При этом неверный фрейм отбрасывается. Когда заканчивается время ожидания подтверждения, отправитель посылает еще раз только самый старый фрейм, для которого не пришло подтверждение. Если вторая попытка будет успешной, получатель сможет последовательно передать накопившиеся пакеты сетевому уровню. Выборочный повтор используется, когда размер окна получателя больше 1. При большом окне этот подход может потребовать значительного количества памяти для принимающего канального уровня.
Выборочный повтор часто комбинируется с отправкой получателем отрицательного подтверждения (negative acknowledgement, NAK) при обнаружении ошибки (например, неверной контрольной суммы или измененного порядка следования фреймов). NAK стимулируют повторную отправку еще до того, как закончится время ожидания подтверждения от отправителя. Таким образом, эффективность работы несколько повышается.
На илл. 3.18 (б) фреймы 0 и 1 снова принимаются корректно, а фрейм 2 теряется. После получения фрейма 3 канальный уровень получателя замечает, что один фрейм выпал из последовательности. Для фрейма 2 отправителю посылается NAK, однако фрейм 3 сохраняется в специальном буфере. Далее приходят фреймы 4 и 5, они также буферизируются канальным уровнем вместо передачи на сетевой уровень. NAK 2 приходит к отправителю, заставляя его переслать фрейм 2. Когда последний оказывается у получателя, у уровня передачи данных уже имеются фреймы 2, 3, 4 и 5, которые сразу же в нужном порядке отдаются сетевому уровню. Теперь можно выслать подтверждение получения всех фреймов, включая пятый, что и показано на рисунке. Если NAK вдруг потеряется, то отправитель по окончании времени ожидания подтверждения сам повторит отправку фрейма 2 (и только его), однако это может произойти значительно позже, чем при помощи NAK.
Выбор одной из двух приведенных выше стратегий является компромиссом между эффективным использованием пропускной способности и размером буфера канального уровня. В зависимости от того, что в конкретной ситуации является более критичным, может использоваться тот или иной метод. На илл. 3.19 показан протокол с возвратом к n, в котором канальный уровень принимает фреймы по порядку. Все фреймы, следующие за ошибочным, игнорируются. В данном протоколе мы впервые отказались от допущения, что у сетевого уровня всегда есть неограниченное количество пакетов для отсылки. Когда появляется готовый для отправки пакет, сетевой уровень может инициировать событие network_layer_ready. Чтобы контролировать размер окна отправителя или число неподтвержденных фреймов в любой момент времени, канальный уровень должен иметь возможность на время отключать сетевой. Для этой цели служит пара библиотечных процедур: enable_network_layer и disable_network_layer.
В любой момент времени максимальное число неподтвержденных фреймов не совпадает с количеством порядковых номеров. Для протокола с возвратом к n таких фреймов может быть MAX_SEQ, при этом имеется MAX_SEQ + 1 порядковых номеров: от 0 до MAX_SEQ. В протоколе с выборочным повтором мы увидим еще более жесткое ограничение. Чтобы понять, почему оно необходимо, рассмотрим сценарий с MAX_SEQ = 7.
1. Отправитель посылает фреймы с 0-го по 7-й.
2. Вложенное подтверждение для фрейма 7 приходит к отправителю.
3. Отправитель посылает следующие восемь фреймов, снова с номерами с 0 по 7.
4. Еще одно вложенное подтверждение для фрейма 7 доставляется отправителю.
Вопрос: все восемь фреймов из второго набора благополучно дошли до адресата или все они потерялись (включая проигнорированные фреймы после ошибочного)? В обеих ситуациях получатель отправит фрейм 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; /* номер следующего посылаемого фрейма */