Э. Таненбаум, Д. Уэзеролл - Компьютерные сети (1114668), страница 75
Текст из файла (страница 75)
Назовем это количество BD (bandwidth-delayproduct, то есть полоса пропускания, умноженная на задержку). Следовательно, значение w нужно выбрать как 2BD + 1. 2BD — это число кадров, которое может находитьсяв пути (неподтвержденные кадры), если отправитель отправляет кадры непрерывно(двойка обозначает, что мы также учитываем время, необходимое на получение подтверждения).
Единица прибавляется, так как кадр подтверждения отправляетсятолько после получения полного кадра данных.Возьмем в качестве примера канал с полосой пропускания 50 Кбит/с, в которомна пересылку кадра в одну сторону тратится 250 мс. Значение BD равно 12,5 Кбит/сили 12,5 кадра, каждый из которых включает 1000 бит. 2BD + 1 равно 26 кадрам. Отправитель начинает, как и ранее, с передачи кадра 0 и отправляет очередной кадр каждые 20 мс. К тому моменту, когда он закончит отправку 26 кадров (в момент времениt = 520 мс), как раз прибудет подтверждение кадра 0.
Затем подтверждения станутприбывать каждые 20 мс. Таким образом, отправитель будет получать разрешения напередачу следующего кадра как раз вовремя. Начиная с этого момента у отправителябудет 25 или 26 неподтвержденных кадров и, следовательно, достаточно будет окнаразмером 26.Если размер окна невелик, то канал будет загружен не на 100 %, так как иногда отправитель будет блокироваться.
Загрузку можно выразить как долю времени, когдаотправитель не заблокирован:wзагрузка канала !.1 + 2BDЭто значение выражает верхнюю границу, так как не учитывает время на обработкукадра. Также считается, что длина кадра подтверждения равна нулю — обычно онидействительно короткие.
Из этого неравенства понятно, что для больших значенийBD необходимо выбирать большое значение размера окна w. Если задержка большая,то отправитель быстро опустошит свое окно даже при средней полосе пропускания,как в примере со спутником. Если полоса пропускания широкая, то даже при среднейзадержке отправитель быстро опустошит окно, если только оно не отличается особокрупным размером (например, канал с пропусной способностью 1 Гбит/с и задержкойв 1 мс удерживает 1 Мбит). Если у протокола с ожиданием значение w = 1, то дажеесли задержка распространения равна всего одному кадру, его эффективность ужепадает ниже 50 %.Такая техника, когда в пути находится сразу несколько кадров, называется конвейерной обработкой (pipelining).
При конвейерном режиме передачи кадров по ненадежному каналу возникает ряд серьезных проблем. Во-первых, что произойдет, еслиповредится или потеряется кадр в середине длинного потока? Большое количествопоследующих кадров прибудет к получателю прежде, чем отправитель обнаружит, чтопроизошла ошибка. Когда поврежденный кадр приходит к получателю, он, конечно,должен быть отвергнут, однако что должен делать получатель со всеми правильными258 Глава 3. Канальный уровеньпоследующими кадрами? Как уже говорилось, получающий канальный уровень обязанпередавать пакеты сетевому уровню, соблюдая строгий порядок.Существует два базовых подхода к исправлению ошибок при конвейерной обработке. Они проиллюстрированы на рис.
3.13.8234DDDDk3AcD9AcD8AcE7AcAc16AcAc05k77k66k55k44k23Ac2k11k002345678TimeAck132Ack1Ack115Ack114113012k9k8k611Ac510Ac49Ac38AcE7k76k2Ac12NaAc05k54Ac3k121k00267891011121314Рис. 3.13. Конвейеризация и коррекция ошибок: а — эффект при размере окна 1;б — эффект при размере окна больше 1Первый способ называется возвратом на n (go-back-n) и заключается просто в игнорировании всех кадров, следующих за ошибочным. Для таких кадров подтверждения не посылаются. Эта стратегия соответствует приемному окну размера 1.
Другимисловами, канальный уровень отказывается принимать какой-либо кадр, кроме кадрасо следующим номером, который он должен передать сетевому уровню. Если окно отправителя заполнится раньше, чем истечет период времени ожидания, конвейер начнетпростаивать. Наконец, лимит времени у отправителя истечет, и он начнет передаватьповторно сразу все кадры, не получившие подтверждения, начиная с поврежденногоили потерянного кадра. Такой подход при высоком уровне ошибок может привестик потере большой доли пропускной способности канала.На рис. 3.13, б изображен возврат на n для случая большого окна приемника.
Кадры 0и 1 корректно принимаются, и высылается подтверждение этого факта. Однако кадр 2потерялся или был испорчен. Ничего не подозревающий отправитель продолжает посылать кадры, пока не выйдет время ожидания кадра 2. Только после этого он возвращается к месту сбоя и заново передает все кадры, начиная с кадра 2 (отправляя 2, 3, 4 и т. д.).Другая общая стратегия обработки ошибок при конвейерной передаче кадров,называемая выборочным повтором (selective repeat), заключается в том, что полу-3.4.
Протоколы скользящего окна 259чатель хранит в буфере все правильные кадры, принятые им после неверного или потерянного кадра. При этом неверный кадр отбрасывается. Когда заканчивается времяожидания подтверждения, отправитель отправляет еще раз только самый старыйкадр, для которого не пришло подтверждение. Если вторая попытка будет успешной,получатель сможет последовательно передать накопившиеся пакеты сетевому уровню. Выборочный повтор используется, когда размер окна получателя больше 1. Онможет потребовать, чтобы канальному уровню получателя было доступно большоеколичество памяти.Выборочный повтор часто комбинируется с отправкой получателем «отрицательного подтверждения» (NAK — Negative Acknowledgement) при обнаружении ошибки,например, при неверной контрольной сумме или при измененном порядке следованиякадров. NAK стимулируют повторную отправку еще до того, как закончится времяожидания подтверждения от отправителя.
Таким образом, эффективность работынесколько повышается.На рис. 3.13, б кадры 0 и 1 снова принимаются корректно, а кадр 2 теряется. Послеполучения кадра 3 канальный уровень приемника замечает, что один кадр выпал из последовательности. Для кадра 2 отправителю посылается ���������������������������NAK������������������������, однако кадр 3 сохраняется в специальном буфере. Далее прибывают кадры 4 и 5, они также буферизируютсяканальным уровнем вместо передачи на сетевой уровень.
�����������������������NAK �������������������2 приходит к отправителю, заставляя его переслать кадр 2. Когда последний оказывается у получателя,у уровня передачи данных уже имеются кадры 2, 3, 4 и 5, которые сразу же в нужномпорядке отдаются сетевому уровню. Теперь уже можно выслать подтверждение получения всех кадров, включая пятый, что и показано на рисунке. Если NAK вдругпотеряется, то отправитель по окончании времени ожидания 2 сам отправит кадр 2(и только его!), однако это может произойти значительно позже, чем при помощи NAK.Листинг 3.6. Протокол скользящего окна с возвратом на n/* Протокол 5 (конвейерный) допускает наличие нескольких неподтвержденных кадров.Отправитель может передать до MAX_SEQ кадров, не ожидая подтверждения. Кроме того,в отличие от предыдущих протоколов, не предполагается, что у сетевого уровня всегда естьновые пакеты. При появлении нового пакета сетевой уровень инициирует событие network_layer_ready */#define MAX_SEQ 7/* должно быть 2^n-1 */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);elsereturn(false);}static void send_data(seq_nr frame_nr, seq_nr frame_expected, packet buffer[])продолжение 260 Глава 3.
Канальный уровеньЛистинг 3.6 (продолжение){/* подготовить и послать информационный кадр */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;/*seq_nr ack_expected;/*seq_nr frame_expected;/*frame r;/*packet buffer[MAX_SEQ+1];/*seq_nr nbuffered;/* количествоseq_nr i;/*event_type event;MAX_SEQ > 1; используется для исходящего потока */самый старый неподтвержденный кадр */следующий кадр, ожидаемый во входящем потоке */временная переменная */буферы для исходящего потока */использующихся в данный момент выходных буферов */индекс массива буферов */enable_network_layer();ack_expected = 0;next_frame_to_send = 0;frame_expected = 0;nbuffered = 0;/*/*/*/*/*разрешить события network_layer_ready */номер следующего ожидаемого входящего подтверждения */номер следующего посылаемого кадра */номер следующего ожидаемого входящего кадра */вначале буфер пуст */while (true) {wait_for_event(&event);/* четыре возможных события: см.
event_type выше */switch(event) {case network_layer_ready:/* у сетевого уровня есть пакетдля передачи *//* получить, сохранить и передать новый кадр */from_network_layer(&buffer[next_frame_to_send]); /* получить новыйпакет у сетевого уровня */nbuffered = nbuffered + 1; /* увеличить окно отправителя */send_data(next_frame_to_send, frame_expected, buffer); /* передатькадр */inc(next_frame_to_send); /* увеличить верхний край окнаотправителя */break;case frame_arrival:/* прибыл кадр с данными или с подтверждением */from_physical_layer(&r); /* получить пришедший кадр у физическогоуровня */if (r.seq == frame_expected) {/* кадры принимаются только по порядку номеров */3.4. Протоколы скользящего окна to_network_layer(&r.info);inc(frame_expected);получателя */261/* передать пакет сетевому уровню *//* передвинуть нижний край окна}/* подтверждение для кадра n подразумевает также кадрыn - 1, n - 2 и т. д.
*/while (between(ack_expected, r.ack, next_frame_to_send)) {/* отправить подтверждение вместе с информационным кадром */nbuffered = nbuffered - 1; /* в буфере на один кадр меньше */stop_timer(ack_expected);/* кадр прибыл в целости;остановить таймер */inc(ack_expected);/* уменьшить окно отправителя */}break;case cksum_err: break;/* плохие кадры просто игнорируются */case timeout: /* время истекло; передать повторно всенеподтвержденные кадры */next_frame_to_send = ack_expected; /* номер первого посылаемогоповторно кадра */for (i = 1; i <= nbuffered; i++) {send_data(next_frame_to_send, frame_expected, buffer);/* переслать повторно 1 кадр */inc(next_frame_to_send); /* приготовиться к пересылкеследующего кадра */}}if (nbuffered < MAX_SEQ)enable_network_layer();elsedisable_network_layer();}}Выбор одной из двух приведенных выше стратегий является вопросом компромисса между эффективным использованием пропускной способности и размером буфераканального уровня.
В зависимости от того, что в конкретной ситуации является болеекритичным, может использоваться тот или иной метод. В листинге 3.6 показан конвейерный протокол, в котором принимающий уровень передачи данных принимаеткадры по порядку. Все кадры, следующие за ошибочным, игнорируются. В данномпротоколе мы впервые отказались от предположения, что у сетевого уровня всегда естьнеограниченное количество пакетов для отсылки. Когда у сетевого уровня появляетсяпакет, который он хочет отправить, уровень инициирует событие network_layer_ready.Однако чтобы управлять потоком на основе размера окна отправителя и числа неподтвержденных кадров в любой момент времени, канальный уровень должен иметьвозможность отключать на время сетевой уровень.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
