Э. Таненбаум, Д. Уэзеролл - Компьютерные сети (1114668), страница 74
Текст из файла (страница 74)
1-битовый протокол скользящего окна/* Протокол 4 (скользящее окно) является дуплексным. */#define MAX_SEQ 1/* в протоколе 4 должно быть равно 1 */typedef enum {frame_arrival, cksum_err, timeout} event_type;#include "protocol.h"void protocol4 (void)продолжение 254 Глава 3. Канальный уровеньЛистинг 3.5 (продолжение){seq_nr next_frame_to_send;seq_nr frame_expected;frame r, s;packet buffer;event_type event;/*/*/*/*только 0 или 1 */только 0 или 1 */временная переменная */текущий посланный пакет */next_frame_to_send = 0;frame_expected = 0;from_network_layer(&buffer);s.info = buffer;s.seq = next_frame_to_send;s.ack = 1 - frame_expected;/*/*/*/*/*/*номер следующего кадра в исходящем потоке */номер ожидаемого кадра */получить первый пакет у сетевого уровня */подготовить первый кадр для передачи */вставить порядковый номер в кадр */подтверждение, посылаемое "верхом" на кадре данных*/to_physical_layer(&s);start_timer(s.seq);while (true) {wait_for_event(&event);/* послать кадр по каналу *//* запустить таймер ожидания подтверждения *//*/*if (event == frame_arrival) { /*from_physical_layer(&r); /*ждать возможного события: frame_arrival, */cksum_err или timeout */кадр прибыл в целости */получить кадр */if (r.seq == frame_expected) {/* обработать входящий поток кадров */to_network_layer(&r.info); /* передать пакет сетевому уровню */inc(frame_expected); /* инвертировать порядковый номер кадра, *//* ожидаемого в следующий раз */}if (r.ack == next_frame_to_send) { /* обработать исходящий поток кадров */from_network_layer(&buffer);/* получить следующий пакет *//* у сетевого уровня */inc(next_frame_to_send);/* инвертировать порядковый номер *//* посылаемого кадра */}}s.info = buffer;s.seq = next_frame_to_send;s.ack = 1 - frame_expected;to_physical_layer(&s);start_timer(s.seq);/*/*/*/*/*подготовить кадр для передачи */вставить порядковый номер в кадр */порядковый номер последнего полученного кадра */передать кадр */запустить таймер ожидания подтверждения */}}В нормальной ситуации только один канальный уровень может начинать передачу.
Другими словами, только одна из программ должна содержать обращения кпроцедурам to_physical_layer и start_timer вне основного цикла. Начинающая машинаполучает первый пакет от своего сетевого уровня, создает из него кадр и посылает его.3.4. Протоколы скользящего окна 255Когда этот (или другой) кадр прибывает, получающий канальный уровень проверяет,не является ли этот кадр дубликатом, аналогично протоколу 3. Если это тот кадр,который ожидался, он передается сетевому уровню, и окно получателя сдвигаетсявверх.Поле подтверждения содержит номер последнего полученного без ошибок кадра.Если этот номер совпадает с номером кадра, который пытается передать отправитель,последний понимает, что этот кадр успешно принят получателем и что он можетпересылать следующий кадр.
В противном случае он должен продолжать попыткипереслать тот же кадр.Теперь давайте изучим протокол 4 и посмотрим, насколько он устойчив к нестандартным ситуациям. Предположим, что машина A пытается послать кадр 0 машине B,а машина B пытается послать кадр 0 машине A. Предположим также, что на машине Aустановлен слишком короткий период ожидания подтверждения. Соответственно,машина A посылает серию одинаковых кадров со значениями полей seq=0 и ack=1.Когда первый неповрежденный кадр прибудет на машину B, он будет принят,и значение переменной frame_expected будет установлено равным 1. Все последующиевходящие кадры будут проигнорированы, поскольку машина B будет теперь ожидатькадр с порядковым номером 1, а не 0.
Более того, поскольку у всех кадров дубликатовзначение поля ack=1, а машина B продолжает ожидать подтверждения для кадра 0, то Bи не станет запрашивать новый пакет у своего сетевого уровня.В ответ на каждый отвергнутый дубликат, присылаемый машиной A, машина B посылает кадр, содержащий поля seq=0 и ack=0. Наконец, один из этих кадровпринимается машиной A, в результате чего машина A переходит к передаче следующего пакета. Никакая комбинация потерянных кадров или преждевременноистекших интервалов ожидания не может заставить этот протокол ни выдать сетевому уровню дубликат пакета, ни пропустить пакет, ни зависнуть.
Протокол работаеткорректно.Рис. 3.12. Два сценария для протокола 4: а — нормальная ситуация; б — нештатная ситуация.Нотация: (seq, ack, номер пакета). Звездочка означает, что сетевой уровень принял пакет256 Глава 3. Канальный уровеньОднако отношения между протоколами могут быть довольно непростыми. Еслиобе стороны одновременно вышлют друг другу начальный пакет, возникает запутанная ситуация, проиллюстрированная на рис. 3.12.
В левой части рисунка показанонормальное функционирование протокола. Правая часть рисунка демонстрирует аномальную ситуацию. Если машина B ожидает первого кадра от машины A, прежде чемпослать свой первый кадр, то последовательность будет такой, как показана в левойчасти рисунка. При этом принимается каждый кадр.Однако если машины A и B одновременно начнут передачу, их первые кадры пересекутся, и канальные уровни попадут в ситуацию б. В ситуации а с каждым кадромприбывал новый пакет, и дубликатов нет.
В ситуации б половина кадров содержитдубликаты, несмотря на то что ошибок в канале связи не было. Подобные ситуациимогут возникнуть в результате преждевременного истечения периода ожидания, дажеесли одна сторона начнет диалог первой. В самом деле, если время ожидания истечетслишком быстро, кадр может быть послан три и более раз, приводя к ненужной тратеценных ресурсов.3.4.2. Протокол с возвратом на nДо сих пор мы по умолчанию подразумевали, что время, необходимое на передачу кадра от отправителя к получателю, и время, необходимое на передачу подтверждения отполучателя к отправителю, пренебрежимо мало. Иногда это предположение являетсясовершенно неверным. В таких ситуациях большое время прохождения кадров по сетиможет значительно снижать эффективность использования пропускной способностиканала.
В качестве примера рассмотрим спутниковый канал связи с пропускной способностью 50 Кбит/с и временем, требуемым для прохождения сигнала в оба конца,равным 500 мс. Попытаемся использовать протокол 4 для пересылки кадров размеромв 1000 бит через спутник. В момент времени t = 0 отправитель начинает посылатьпервый кадр. В момент времени t = 20 мс кадр полностью послан. В момент времениt = 270 мс получатель принял кадр полностью и отправил обратно подтверждение.В итоге в лучшем случае только через 520 мс после начала передачи кадра подтверждение будет получено отправителем. В данном случае еще предполагается, что приемникне тратит времени на обработку принятого кадра и подтверждение такое короткое, чтовременем его передачи и приема можно пренебречь.
Это означает, что передающаямашина была заблокирована в течение 500/520, или 96 % времени. Другими словами,использовалось только 4 % доступной пропускной способности. Очевидно, что сочетание большого времени прохождения сигнала, высокой пропускной способностии коротких кадров совершенно неприемлемо с точки зрения эффективности.Описанная выше проблема является следствием правила, заставлявшего отправителя дожидаться подтверждения, прежде чем посылать следующий кадр. Смягчивэто требование, можно значительно повысить эффективность. Решение проблемы заключается в разрешении отправителю послать не один кадр, а несколько, например w,прежде чем остановиться и перейти в режим ожидания подтверждений. Если подобрать достаточно большое число w, то отправитель сможет безостановочно посылатькадры, так как подтверждения для предыдущих кадров будут прибывать до того, какокно заполнится, и блокировка отправителя производиться не будет.3.4.
Протоколы скользящего окна 257Для того чтобы найти подходящее значение w, необходимо понять, сколько кадров«вмещается» в канал, в то время как они путешествуют от отправителя к получателю.Емкость определяется путем умножения полосы пропускания в битах в секунду навремя пересылки в одну сторону. Это значение можно разделить на число бит в кадре,чтобы выразить количество кадров.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
