Э. Таненбаум - Компьютерные сети. (4-е издание) (PDF) (1130118), страница 67
Текст из файла (страница 67)
В зависимости от того, что в конкретной ситуации является более критичным, может использоваться тот или иной метод. В листинге 3.6 показан конвейерный протокол, в котором принимающий уровень передачи данных принимает кадры по порядку. Все кадры, следующие за ошибочным, игнорируются.В данном протоколе мы впервые отказались от предположения, что у сетевогоуровня всегда есть неограниченное количество пакетов для отсылки.
Когда у сетевого уровня появляется пакет, который он хочет отправить, уровень инициирует событие networkJ ayer_ready. Однако чтобы ограничить количество неподтвержденных пакетов числом MAX_SEQ, уровень передачи данных должен иметьвозможность отключать на время сетевой уровень. Для этой цели служит парабиблиотечных процедур — enabl e_network_l ауег и disabl ejietworkj ауег.Обратите внимание на то, что в любой момент времени может быть МАХ_SEQ, а не MAX_SEQ + 1 неподтвержденных пакетов, хотя различаются МАХ_SEQ + 1 порядковых номеров: от 0 до MAX_SEQ.
Чтобы понять, почему необходимо такое ограничение, рассмотрим сценарий с MAX__SEQ = 7.1. Отправитель посылает кадры с 0 по 7.2. Подтверждение для кадра 7 наконец прибывает к отправителю.2633. Отправитель посылает следующие восемь кадров, снова с номерами с 0 по 7.4. Еще одно подтверждение для кадра 7 прибывает к отправителю.Но вот вопрос: все восемь кадров, входящих во второй набор, благополучнодошли до адресата или все они потерялись (включая игнорированные кадры после ошибочного)? В обоих случаях получатель отправит кадр 7 в качестве подтверждения. У отправителя нет способа отличить один случай от другого.
Поэтой причине максимальное количество неподтвержденных кадров должно бытьограничено числом MAX_SEQ.Хотя в протоколе 5 кадры, поступившие после ошибки, не буферизируютсяполучателем, тем не менее, отправитель должен хранить отправленные кадры всвоем буфере, пока не получит на них подтверждение. Если поступает подтверждение на кадр п, кадры я - 1, « - 2 (то есть все предыдущие кадры) автоматическисчитаются подтвержденными.
Эта особенность наиболее важна в случае потериили повреждения какого-либо кадра с подтверждением. Получив подтверждение, уровень передачи данных проверяет, не освободился ли у него какой-нибудьбуфер. Если буфер освобождается, то заблокированному ранее сетевому уровнюможно снова разрешить инициировать события network_layer_ready.Для этого протокола предполагается, что всегда есть обратный трафик, по которому можно отправлять подтверждение. Если же это условие не выполняется,то никакие подтверждения отосланы не будут. Протокол 4 не нуждается в подобном допущении, поскольку за каждым принятым кадром следует обратный,даже если только что уже был отправлен какой-то кадр в сторону отправителя.В следующем протоколе проблема отсутствия обратного трафика будет решенагораздо элегантней.Поскольку протокол 5 хранит несколько неподтвержденных кадров, ему требуется несколько таймеров, по одному на кадр.
Для каждого кадра время считается независимо от других. Все таймеры могут симулироваться программно, использую единственные аппаратные часы, вызывающие периодические прерывания.Данные таймеров могут храниться в программе в виде связанного списка, каждый узел которого будет хранить количество временных интервалов системныхчасов, оставшихся до истечения срока ожидания, номер кадра и указатель на следующий узел списка./-Реальное время\ \ \N.
N^ Указатель на следующий таймерN 4 / 4 Номер кадра^ Интервал времени в тикахабРис. 3.12. Программная симуляция работы нескольких таймеров264Протоколы скользящего окнаГлава 3. Уровень передачи данныхВ качестве иллюстрации приводится рис. 3.12, на котором показана программная реализация нескольких таймеров. Предположим, что часы изменяют своесостояние каждые 100 мс.
Пусть начальное значение реального времени будет10:00:00.0, и имеются три таймера тайм-аутов, установленные на время 10:00:00.5,10:00:01.3 и 10:00:01.9. Каждый раз, когда аппаратные часы изменяют свое значение, реальное время обновляется и счетчик этих изменений в голове списка уменьшается на единицу. Когда значение счетчика становится равным нулю, инициируется тайм-аут, а узел удаляется из списка, как показано на рис.
3.12, б. Такаяорганизация таймеров не требует выполнения большой работы при каждом прерывании от системных часов, хотя при работе процедур start_timer и stop_timerтребуется сканирование списка. В протоколе у данных процедур имеется входной параметр, означающий номер кадра, таймер которого нужно запустить илиостановить.Протокол с выборочным повторомПротокол 5 хорошо работает, если ошибки встречаются нечасто, однако при плохой линии он тратит впустую много времени, передавая кадры по два раза. В качестве альтернативы можно использовать протокол, в котором получатель буферизирует кадры, принятые после потерянного или испорченного кадра. Такойпротокол не отвергает кадры только лишь потому, что предыдущий кадр был поврежден или потерян.В этом протоколе и отправитель, и получатель работают с окнами допустимых номеров кадров.
Размер окна отправителя начинается с нуля и растет до некоторого определенного уровня, MAX_SEQ. Размер окна получателя, напротив,всегда фиксированного размера, равного MAX_SEQ. Получатель должен иметьбуфер для каждого кадра, номер которого находится в пределах окна. С каждымбуфером связан бит, показывающий, занят буфер или свободен. Когда прибываеткадр, функция between проверяет, попал ли его порядковый номер в окно. Еслида, то кадр принимается и хранится в буфере. Это действие производится независимо от того, является ли данный кадр следующим кадром, ожидаемым сетевым уровнем.
Он должен храниться на уровне передачи данных до тех пор, покавсе предыдущие кадры не будут переданы сетевому уровню в правильном порядке. Алгоритм протокола показан в листинге 3.7./* отрицательное подтверждение (nak) еще не посылалосьboolean nojiak = true;*//* начальное значение для симулятора */seq_nr oldest_frame = MAX_SEQ+1:static boolean between(seq_nг a. seqjir b, seqjir c)/* то же. что и в протоколе 5, но короче и понятнее */return ((а <= Ь) && (Ь < с)) || ((с < а) && (а <= b)) || ((b < с)#define MAX_SEQ 7/* должно быть 2*п-1 */#define NR_BUFS ((MAX_SEQtypedef enum {frame_arrival, cksum_err, timeout, network_layer_ready, ack_timeout}event_type:l i n c i u d e "protocol,h"(с < а));static void send_frame(frame_kind fk, seqjir framejir, seqjir frame_expected. packetbuffer[]){/* сформировать и послать данные, а также положительное или отрицательноеподтверждение */frame s:/* временная переменная */s.kind = fk:/* kind == data, ack, или nak */if (fk = data) s.info = buffer[frame_nr % NR_BUFS];s.seq = framejir;/* имеет значение только для информационных кадров*/s.ack = (framejexpected + MAXjSEQ) % (MAXjSEQ + 1);if (fk = nak) nojiak = false; /* один nak на кадр, пожалуйста */to_physical_layer(&s):/* переслать кадр */if (fk = data) start_timer(framejir % NR_BUFS);stop_ack_timer();/* отдельный кадр с подтверждением не нужен */}void protoco!6(void){/* нижний край окна отправителя */seqjir ack_expected:/* верхний край окна отправителя + 1 */seqjir next_frame_to_send;/* нижний край окна получателя */seqjir frame_expected;/* верхний край окна получателя + 1 */seqjir too_far;/* индекс массива буферов */jfit i;/* временная переменная */^ f r a m e r;/* буферы для исходящего потока */packet out_buf[NR_BUFS]:/* буферы для входящего потока */packet in_buf[NR_BUFS];/* входящая битовая карта */boolean arrived[NRj3UFS];seqjir nbuffered;/* количество использующихся в данный момент выходных буферов*/eventjtype event;Листинг 3.7.
Протокол скользящего окна с выборочным повтором/* Протокол б (выборочный повтор) принимает кадры в любом порядке, но передает ихсетевому уровню, соблюдая порядок. С каждым неподтвержденным кадром связан таймер. Присрабатывании таймера передается повторно только этот кадр, а не все неподтвержденныекадры, как в протоколе 5. */265*/enabl ejietworkj ayer ():ack_expected = 0;/* инициализация *//* следующий номер подтверждения во входном потокеnext_frame_toj3end = 0;frame_expected = 0:too_far = NR_BUFS:nbuffered = 0:/*/*/*/*for (i = 0; i < NR_BUFS:while (true) {номер следующего посылаемого кадра */номер следующего ожидаемого входящего кадра */верхний край окна получателя + 1 */вначале буфер пуст */arrived[i] = false:266wait_for_event(&event):/* пять возможных событий: см.
event_type выше*/switch(event) {case network_layer_ready:/* получить, сохранить и передать новый кадр*/nbuffered = nbuffered + 1 ; /* увеличить окно отправителя */from_network_layer(&out_buf[next_frame_to_send % NRJ3UFS]): /* получитьновый пакет у сетевого уровня */send_frame(data, next_frame_to_send. frame_expected, out_buf): /*передать кадр */inc(next_frame_to_send): /* увеличить верхний край окна отправителя */break;case frame_arrival: /* прибыл кадр с данными или с подтверждением */from_physical_1ayer(&r); /* получить пришедший кадр у физическогоуровня */if ( г . k i n d = data) {/* кадр прибыл в целости */if ((r.seq != frame_expected) && nojiak)send_frame(nak, 0. frame_expected, out_buf): else start_ack_timer!);BUFS] == f a l s e ) ) {*/*/Протоколы скользящего окнаГлава 3.
Уровень передачи данныхif (between(frame_expected, r.seq. too_far) && (arrived[r.seq^NR_/* кадры могут приниматься в любом порядке */267case 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.O.frame_expected, out_buf): /* истекпериод ожидания «попутки» для подтверждения: послать подтверждение */}if (nbuffered < NR_BUFS) enable_network_layer(); else disable_network_layer():Способность протокола принимать кадры в произвольном порядке вызываетнекоторые проблемы, отсутствовавшие в предыдущих протоколах, в которых всепакеты принимались строго по порядку номеров.
Проще всего проиллюстрировать это на примере. Предположим, что порядковый номер кадра состоит из 3 бит,так что отправитель может посылать до семи кадров, прежде чем перейти в режим ожидания подтверждения. Начальное состояние окон отправителя и получателя изображено на рис. 3.13, а. Отправитель передает кадры с 0 по 6. Окно получателя позволяет ему принимать любые кадры с номерами от 0 по 6 включительно.Все семь кадров прибывают успешно, поэтому получатель подтверждает их прием и передвигает окно для приема кадров с номерами 7, 0, 1, 2, 3, 4 и 5, как показано на рис. 3.12, б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
