Э. Таненбаум, Д. Уэзеролл - Компьютерные сети (1114668), страница 76
Текст из файла (страница 76)
Для этой цели служит пара библиотечных процедур — enable_network_layer и disable_network_layer.Максимальное число неподтвержденных кадров в любой момент времени не совпадает с размером пространства порядковых номеров. Для протокола с возвратом на262 Глава 3. Канальный уровень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.Хотя в протоколе 5 кадры, поступившие после ошибки, не буферизируются получателем, тем не менее отправитель должен хранить отправленные кадры в своембуфере, пока не получит на них подтверждение.
Если поступает подтверждение накадр n, кадры n – 1, n – 2 (то есть все предыдущие кадры) автоматически считаютсяподтвержденными. Такой тип подтверждения называется кумулятивным (cumulativeacknowledgement). Эта особенность наиболее важна в случае потери или повреждениякакого-либо кадра с подтверждением. Получив подтверждение, канальный уровеньпроверяет, не освободился ли у него какой-нибудь буфер. Если буфер освобождается,то заблокированному ранее сетевому уровню можно снова разрешить инициироватьсобытия network_layer_ready.Для этого протокола предполагается, что всегда есть обратный трафик, по которомуможно отправлять подтверждение. Протокол 4 не нуждается в подобном допущении,поскольку за каждым принятым кадром следует обратный, даже если уже был отправлен какой-то кадр в сторону отправителя.
В следующем протоколе проблемаотсутствия обратного трафика будет решена гораздо элегантней.Поскольку протокол 5 хранит несколько неподтвержденных кадров, ему требуетсянесколько таймеров, по одному на кадр. Для каждого кадра время считается независимо от других. Однако все таймеры могут симулироваться программно, используяединственные аппаратные часы, вызывающие периодические прерывания. Данныетаймеров могут храниться в программе в виде связанного списка, каждый узел которого будет хранить количество временных интервалов системных часов, оставшихсядо истечения срока ожидания, номер кадра и указатель на следующий узел списка.В качестве иллюстрации приводится рис. 3.14, на котором показана программнаяреализация нескольких таймеров.
Предположим, что часы изменяют свое состояниекаждые 1 мс. Пусть начальное значение реального времени будет 10:00:00.000 и имеются три таймера тайм-аутов, установленные на время 10:00:00.005, 10:00:00.013и 10:00:00.019. Каждый раз, когда аппаратные часы изменяют свое значение, реальное время обновляется и счетчик этих изменений в голове списка уменьшается наединицу. Когда значение счетчика становится равным нулю, инициируется тайм-аут,а узел удаляется из списка, как показано на рис. 3.14, б. Такая организация таймеровне требует выполнения большой работы при каждом прерывании от системных часов,3.4.
Протоколы скользящего окна 263хотя при работе процедур start_timer и stop_timer требуется сканирование списка.В протоколе у данных процедур имеется входной параметр, означающий номер кадра,таймер которого нужно запустить или остановить.Рис. 3.14. Программная симуляция работы нескольких таймеров3.4.3. Протокол с выборочным повторомПротокол с возвратом на n хорошо работает, если ошибки встречаются нечасто, однакопри плохой линии он тратит впустую много времени и ресурсов, передавая кадры подва раза. В качестве альтернативы можно использовать протокол с выборочным повтором, который позволяет получателю принимать и буферизировать кадры, переданныепосле поврежденного или утерянного кадра.В этом протоколе и отправитель, и получатель работают с окнами неподтвержденных и допустимых номеров кадров соответственно.
Размер окна отправителяначинается с нуля и растет до некоторого определенного уровня. Размер окна получателя, напротив, всегда фиксированного размера. Получатель должен иметь буфердля каждого кадра, номер которого находится в пределах окна. С каждым буферомсвязан бит, показывающий, занят буфер или свободен. Когда прибывает кадр, функцияbetween проверяет, попал ли его порядковый номер в окно.
Если да, то кадр принимается и хранится в буфере. Это действие производится независимо от того, является лиданный кадр следующим кадром, ожидаемым сетевым уровнем. Он должен хранитьсяна канальном уровне до тех пор, пока все предыдущие кадры не будут переданы сетевому уровню в правильном порядке. Алгоритм протокола показан в листинге 3.7.Листинг 3.7.
Протокол скользящего окна с выборочным повтором/* Протокол 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;продолжение 264 Глава 3. Канальный уровеньЛистинг 3.7 (продолжение)#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, packetbuffer[]){/* сформировать и послать данные, а также положительное или отрицательное подтверждение */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;/*/*/*/*/*/*инициализация */следующий номер подтверждения во входном потоке */номер следующего посылаемого кадра */номер следующего ожидаемого входящего кадра */верхний край окна получателя + 1 */вначале буфер пуст */for (i = 0; i < NR_BUFS; i++) arrived[i] = false;while (true) {wait_for_event(&event);/* пять возможных событий:см.
event_type выше */3.4. Протоколы скользящего окна 265switch(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); /* кадр прибыл в целости */продолжение 266 Глава 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
