Компьютерные сети. 6-е изд.

3.4. Повышение эффективности

В предыдущих протоколах фреймы данных передавались только в одну сторону. На практике чаще всего требуется передача в обоих направлениях. Кроме того, канальный уровень работает более эффективно, если по нему можно отправлять сразу несколько фреймов, не дожидаясь, пока придет подтверждение. Далее мы изучим обе эти концепции и рассмотрим несколько примеров протоколов, реализующих поставленные цели.

3.4.1. Цель: двунаправленная передача, отправка сразу нескольких фреймов

Ниже представлен метод так называемого вложенного подтверждения, позволяющий протоколу канального уровня обеспечить двунаправленную (дуплексную) передачу, а также метод раздвижного окна, позволяющий повысить эффективность передачи за счет отправки сразу нескольких фреймов.

Двунаправленная передача данных: вложенное подтверждение

Один из способов осуществления дуплексной передачи — использование двух экземпляров описанных выше протоколов, каждый из которых передает данные по отдельной симплексной связи (в противоположных направлениях). При этом каждое соединение включает прямой канал для данных и обратный — для подтверждений. В обоих случаях пропускная способность обратного канала почти не используется.

Гораздо эффективнее использовать для дуплексной передачи один канал. К тому же в протоколах 2 и 3 фреймы уже передавались по каналу в двух направлениях, при этом обратный канал обладает той же пропускной способностью, что и прямой. В такой модели фреймы данных и подтверждения, которые устройство A отправляет устройству B, перемешиваются. Получатель может отличить фрейм данных от фрейма с подтверждением по специальному полю заголовка фрейма — kind.

Помимо чередования подтверждений и информационных фреймов возможно и другое улучшение протокола. Приняв фрейм данных, получатель может не посылать фрейм с подтверждением сразу, а подождать, пока сетевой уровень даст ему следующий пакет. Подтверждение добавляется к исходящему фрейму данных с помощью поля ack в заголовке. В результате на передачу подтверждения почти не расходуются ресурсы. Подход, при котором подтверждения временно откладываются и прикрепляются к следующему исходящему фрейму данных, называется вложенным подтверждением (piggybacking).

Основное преимущество вложенного подтверждения — более эффективное использование пропускной способности канала. Поле ack в заголовке фрейма занимает всего несколько битов, тогда как отдельный фрейм потребует заголовка и контрольной суммы. Кроме того, чем меньше входящих фреймов, тем меньше нагрузка на получателя. В следующем протоколе, который мы рассмотрим, расходы на поле вложенного подтверждения в заголовке фрейма составляют всего 1 бит (они редко превышают несколько битов).

Однако использование вложенного подтверждения ведет к появлению новых проблем. Как долго канальный уровень должен ждать пакета, с которым следует переслать подтверждение? Если он будет ждать дольше, чем отправитель, то последний пошлет фрейм повторно и сама идея подтверждений потеряет смысл. Если бы канальный уровень мог предсказывать будущее, он бы знал, ждать ему пакет или отправить подтверждение отдельно. К сожалению, это невозможно, поэтому следует установить еще один интервал ожидания (меньший, чем у отправителя), по истечении которого подтверждение отправляется отдельным фреймом. Если же сетевой уровень успеет передать пакет канальному уровню, то подтверждение будет отослано вместе с ним в одном фрейме.

Раздвижное окно

Следующие три протокола являются двунаправленными и принадлежат к классу протоколов раздвижного окна (sliding window). Как будет показано ниже, они отличаются друг от друга эффективностью, сложностью и требованиями к размерам буфера. Во всех протоколах раздвижного окна каждый исходящий фрейм содержит порядковый номер (в диапазоне от 0 до некоторого максимума). Этот номер должен поместиться в поле размером n бит, поэтому его максимальное значение обычно составляет 2n – 1. В протоколах раздвижного окна с остановкой и ожиданием n = 1; это ограничивает порядковый номер значениями 0 и 1, однако в более сложных версиях может использоваться произвольное значение n.

Суть всех протоколов раздвижного окна заключается в том, что отправитель постоянно работает с набором порядковых номеров, соответствующих фреймам, которые ему разрешено передавать. Эти фреймы находятся в передающем окне. Аналогично получатель работает с приемным окном, содержащим набор фреймов, которые можно принять. Окна получателя и отправителя не должны иметь одинаковые нижний и верхний пределы или даже быть одного размера. В одних протоколах размеры фиксируются, а в других они могут увеличиваться или уменьшаться по мере передачи или приема фреймов.

Данные протоколы предоставляют канальному уровню большую свободу в отношении последовательности передачи и приема фреймов. Но требование доставки пакетов целевому сетевому уровню в том же порядке, в котором они были получены от передающего сетевого уровня, по-прежнему действует. Физический канал связи также должен доставлять фреймы в порядке отправления (подобно проводу).

Порядковые номера в передающем окне соответствуют уже отправленным фреймам, для которых еще не пришли подтверждения. Пришедший от сетевого уровня пакет получает наибольший порядковый номер, и верхняя граница окна увеличивается на единицу. Когда поступает подтверждение, на единицу возрастает нижняя граница окна. Таким образом, окно постоянно содержит список неподтвержденных фреймов. Пример такого протокола показан на илл. 3.15.

Фреймы, находящиеся в окне отправителя, могут быть потеряны или повреждены во время передачи, поэтому их нужно хранить в памяти на случай возможной повторной отправки. Таким образом, если максимальный размер окна равен n, то отправителю потребуется n буферов для хранения неподтвержденных фреймов. Если окно достигает максимального размера, канальный уровень должен отключить сетевой уровень до тех пор, пока не освободится буфер.

Окно принимающего канального уровня соответствует фреймам, которые он может принять. Любой фрейм, попадающий в окно, помещается в буфер получателя. Когда приходит фрейм с порядковым номером, соответствующим нижнему краю окна, он передается на сетевой уровень и окно сдвигается на одну позицию. Любой фрейм, не попадающий в окно, удаляется. В любом случае формируется подтверждение, чтобы отправитель мог понять, как ему действовать

Илл. 3.15. Раздвижное окно размера 1 с 3-битным порядковым номером. (а) Начальная ситуация. (б) После отправки первого фрейма. (в) После приема первого фрейма. (г) После приема первого подтверждения

дальше. Обратите внимание, что если размер окна равен единице, то канальный уровень может принимать фреймы только в установленном порядке, однако при больших размерах окна последовательность может нарушаться. Сетевому уровню, напротив, данные всегда предоставляются в строгом порядке, независимо от размера окна канального уровня.

На илл. 3.15 показан пример для окна с максимальным размером 1. Вначале фреймов в окне нет, поэтому оно пустое и его верхний и нижний края совпадают, однако с течением времени ситуация меняется. В отличие от окна отправителя, окно получателя всегда сохраняет первоначальный размер, сдвигаясь по мере приема и передачи на сетевой уровень очередного фрейма.

3.4.2. Примеры дуплексных протоколов раздвижного окна

Теперь рассмотрим пример простого однобитного протокола раздвижного окна, а также протоколы, способные обеспечить повторную передачу ошибочных фреймов в случае передачи сразу нескольких фреймов.

Однобитное раздвижное окно

Прежде чем рассматривать общий случай, изучим протокол раздвижного окна, равного 1. Такой протокол использует метод ожидания: отослав фрейм, отправитель должен дождаться подтверждения, прежде чем послать следующий фрейм.

Данный протокол показан на илл. 3.16. Как и другие протоколы, он начинается с определения некоторых переменных. Переменная next_frame_to_send содержит номер фрейма, который отправитель пытается послать. Аналогично переменная frame_expected хранит номер фрейма, ожидаемого получателем. В обоих случаях возможными значениями могут быть только 0 и 1.

/* Протокол 4 (раздвижное окно) является дуплексным

#define MAX_SEQ 1 /* в протоколе 4 должно быть равно 1

typedef enum {frame_arrival, cksum_err, timeout} event_type;

#include "protocol.h"

void protocol4 (void)

{

seq_nr next_frame_to_send; /* только 0 или 1 */

seq_nr frame_expected; /* только 0 или 1 */

frame r, s; /* временные переменные */

packet buffer; /* текущий отправленный пакет */

event_type event;

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); /* ждать события frame_arrival, cksum_err или timeout */

if (event == frame_arrival) { /* фрейм пришел в целости */

from_physical_layer(&r); /* получить пришедший фрейм */

if (r.seq == frame_expected) { /* обработать входящий поток фреймов */

to_network_layer(&r.info); /* передать пакет сетевому уровню */

inc(frame_expected); /* инвертировать порядковый номер фрейма, ожидаемого в следующий раз */

}

if (r.ack == next_frame_to_send) { /* обработать исходящий поток фреймов */

stop_timer(r.ack); /* остановить таймер */

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); /* запустить таймер ожидания подтверждения */

}

}

Илл. 3.16. Однобитный протокол раздвижного окна

В обычной ситуации только один канальный уровень может начинать передачу. Другими словами, лишь одна из программ должна содержать обращения к процедурам to_physical_layer и start_timer вне основного цикла. Отправитель получает первый пакет от своего сетевого уровня, создает из него фрейм и посылает его. Когда этот (или другой) фрейм приходит, получающий канальный уровень проверяет, не является ли он дубликатом, аналогично протоколу 3. Если это тот фрейм, который ожидался, он передается сетевому уровню и окно получателя сдвигается вверх.

Поле подтверждения содержит номер последнего полученного без ошибок фрейма. Если он совпадает с номером фрейма, который пытается передать отправитель, тот понимает, что этот фрейм успешно принят получателем и что можно пересылать следующий. В противном случае он продолжает попытки передачи того же фрейма. При каждом получении фрейма производится отправка фрейма в обратном направлении.

Теперь изучим протокол 4 и посмотрим, насколько он устойчив к нестандартным ситуациям. Представим, что устройство A пытается послать фрейм 0 устройству B, при этом B пытается отправить A фрейм 0. Предположим, что на A установлен слишком короткий период ожидания подтверждения. Соответственно, A посылает серию одинаковых фреймов со значениями полей seq = 0 и ack = 1.

Когда первый неповрежденный фрейм придет на устройство B, он будет принят и значение переменной frame_expected будет равно 1. Все последующие входящие фреймы будут проигнорированы, поскольку B теперь ожидает фрейм с порядковым номером 1, а не 0. Более того, поскольку у всех дубликатов значение поля ack = 1, а устройство B продолжает ожидать подтверждения для фрейма 0, оно не станет запрашивать новый пакет у своего сетевого уровня.

В ответ на каждый отвергнутый дубликат, присылаемый устройством A, B посылает фрейм, содержащий поля seq = 0 и ack = 0. Наконец, один из этих фреймов принимается A, в результате чего A переходит к передаче следующего пакета. Никакая комбинация потерянных фреймов или преждевременно истекших интервалов ожидания не может заставить этот протокол ни выдать сетевому уровню дубликат пакета, ни пропустить пакет, ни зависнуть. Протокол работает корректно.

Однако отношения между протоколами могут быть довольно непростыми. Если обе стороны одновременно вышлют друг другу начальный пакет, возникает запутанная ситуация, представленная на илл. 3.17. В левой части рисунка показан случай нормального функционирования протокола. Правая часть демонстрирует отклонение. Если B ожидает первый фрейм от A, прежде чем послать свой первый фрейм, то последовательность будет как в левой части рисунка (а). При этом принимается каждый фрейм.

Но если A и B одновременно начнут передачу, их первые фреймы пересекутся и канальные уровни попадут в ситуацию (б). В ситуации (а) с каждым фреймом приходит новый пакет и дубликатов нет. В случае (б) половина фреймов содержит дубликаты, несмотря на то что ошибок в канале связи не было. Причиной может стать преждевременный тайм-аут, даже если одна сторона явно начинает диалог первой. Получается, если время ожидания истечет слишком быстро, фрейм может быть послан три и более раза, приводя к ненужной трате ценных ресурсов.

Илл. 3.17. Два сценария для протокола 4. (а) Нормальная ситуация. (б) Нештатная ситуация. Обозначения в скобках: (seq, ack, номер пакета). Звездочка показывает, что сетевой уровень принял пакет

Протокол с возвратом к n

До сих пор мы по умолчанию подразумевали, что время, необходимое на передачу фрейма от отправителя к получателю и на обратную передачу подтверждения, пренебрежимо мало. Иногда это совершенно не так. Длительное время прохождения фреймов по сети может значительно снижать эффективность использования пропускной способности канала. В качестве примера рассмотрим 50-килобитный спутниковый канал. Время прохождения сигнала в оба конца равно 500 мс. Попытаемся использовать протокол 4 для пересылки фреймов размером 1000 бит через спутник. В момент времени t = 0 начинается отправка первого фрейма. При t = 20 мс фрейм полностью отправлен. Не раньше чем при t = 270 мс получатель принимает фрейм целиком и высылает подтверждение. Отправитель получает его в момент времени t = 520 мс (в самом лучшем случае — при нулевом времени ожидания на принимающей стороне и коротком фрейме подтверждения). Это означает, что отправляющее устройство заблокировано в течение 500/520, или 96 % времени. Другими словами, использовалось только 4 % доступной полосы пропускания. Очевидно, что сочетание большого времени прохождения сигнала, высокой пропускной способности и коротких фреймов совершенно неприемлемо с точки зрения эффективности.

Описанная выше проблема — следствие правила, которое обязывает отправителя дожидаться подтверждения, прежде чем посылать следующий фрейм. Смягчив это требование, можно значительно повысить эффективность. Нужно разрешить отправителю посылать не один фрейм, а несколько, например w, прежде чем остановиться и перейти в режим ожидания подтверждений. Если подобрать достаточно большое число w, то отправитель сможет безостановочно посылать фреймы, так как подтверждения для предыдущих фреймов будут приходить до того, как окно заполнится. Это предотвратит блокировку отправителя.

Чтобы найти подходящее значение w, необходимо понять, сколько фреймов «вмещается» в канал, в то время как они передаются от отправителя к получателю. Емкость определяется путем умножения полосы пропускания в битах в секунду на время пересылки в одну сторону. Это значение можно разделить на число битов во фрейме, чтобы выразить число фреймов. Назовем эту величину BD (bandwidth-delay product — полоса пропускания, умноженная на задержку). Следовательно, 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 %, так как иногда отправитель будет блокироваться. Коэффициент загруженности можно выразить как долю времени, когда отправитель не заблокирован:

Данное значение выражает верхнюю границу, при этом не учитывается время на обработку фрейма и считается, что длина фрейма подтверждения равна нулю (обычно они действительно короткие). Из этого неравенства понятно, что для высоких значений BD необходимо устанавливать большое значение размера окна w. Если задержка большая, то отправитель быстро опустошит свое окно даже при средней полосе пропускания, как в примере со спутником. Если полоса пропускания широкая, то даже при средней задержке отправитель также быстро обработает окно, если только оно не отличается особо крупным размером (например, канал с пропускной способностью 1 Гбит/с и задержкой в 1 мс удерживает 1 Мбит). Если у протокола с остановкой и ожиданием значение w = 1, то даже при задержке распространения, равной всего одному фрейму, его эффективность падает ниже 50 %.

Метод одновременной отправки сразу нескольких фреймов называется конвейерной обработкой (pipelining). При конвейерном режиме передачи фреймов по ненадежному каналу возникает ряд серьезных проблем. Что произойдет, если в середине длинного потока повредится или потеряется фрейм? Большое количество последующих фреймов придет к получателю прежде, чем отправитель обнаружит ошибку. Когда поврежденный фрейм приходит к получателю, он, конечно, должен быть отвергнут. Но что делать получателю со всеми правильными последующими фреймами? Как уже говорилось, получающий канальный уровень обязан передавать пакеты сетевому уровню, соблюдая строгий порядок.

Существует два базовых подхода к исправлению ошибок при конвейерной обработке. Они показаны на илл. 3.18.

Илл. 3.18. Конвейеризация и коррекция ошибок. (а) Эффект при размере окна, равном 1. (б) Эффект при размере окна больше 1

Первый способ называется возвратом к n (go-back-n) и заключается в том, что получатель просто игнорирует все фреймы, следующие за ошибочным. Для таких фреймов подтверждения не посылаются. Эта стратегия соответствует окну получателя размером 1. Другими словами, канальный уровень отказывается принимать какой-либо фрейм, кроме фрейма со следующим номером, который он должен передать сетевому уровню. Если окно отправителя заполнится раньше, чем истечет период времени ожидания, конвейер начнет простаивать. Наконец, лимит времени у отправителя истечет, и он станет передавать повторно сразу все фреймы, не получившие подтверждения, начиная с поврежденного или потерянного фрейма. Такой подход при высоком уровне ошибок может привести к потере большой доли пропускной способности канала.

На илл. 3.18 (а) изображен возврат к n при большом окне получателя. Фреймы 0 и 1 корректно принимаются, и высылается подтверждение этого факта. Однако фрейм 2 потерялся или был испорчен. Ничего не подозревающий отправитель продолжает посылать фреймы, пока не выйдет время ожидания фрейма 2. Только после этого он возвращается к месту сбоя и заново передает все фреймы, начиная с фрейма 2 (отправляя 2, 3, 4 и т.д.).

Выборочный повтор

Протокол с возвратом к 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; /* номер следующего посылаемого фрейма */

frame_expected = 0; /* номер ожидаемого входящего фрейма */

nbuffered = 0; /* вначале буфер пуст */

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) {

/* Фреймы принимаются только по порядку номеров. */

to_network_layer(&r.info); /* передать пакет сетевому уровню */

inc(frame_expected); /* передвинуть нижний край окна получателя */

}

/* Подтверждение для фрейма 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();

else

disable_network_layer();

}

}

Илл. 3.19. Протокол раздвижного окна с возвратом к n

Поскольку протокол 5 хранит несколько неподтвержденных фреймов, ему требуется несколько таймеров, по одному на фрейм. Для каждого фрейма время считается независимо от других. Однако все таймеры могут симулироваться программно, с помощью единственных аппаратных часов, периодически вызывающих прерывания. Данные таймеров могут храниться в программе в виде связанного списка. Каждый узел этого списка хранит число временных интервалов системных часов, оставшихся до истечения срока ожидания, а также номер фрейма и указатель на следующий узел списка.

Илл. 3.20. Программная симуляция работы нескольких таймеров. (а) Очередь из нескольких периодов ожидания. (б) Ситуация после истечения первого периода ожидания

Пример того, как можно реализовать несколько таймеров, приведен на илл. 3.20 (а). Предположим, что часы изменяют свое состояние каждую 1 мс. Пусть начальное значение реального времени будет 10:00:00.000, при этом имеются три таймера тайм-аутов, установленные на 10:00:00.005, 10:00:00.013 и 10:00:00.019. Каждый раз, когда аппаратные часы изменяют свое значение, реальное время обновляется и счетчик этих изменений в начале списка уменьшается на единицу. Когда значение счетчика становится равным нулю, инициируется тайм-аут, а узел удаляется из списка, как показано на илл. 3.20 (б). Такая организация таймеров не требует большой работы при каждом прерывании от системных часов, хотя при вызове процедур start_timer и stop_timer требуется сканирование списка. В протоколе 5 у данных процедур имеется входной параметр, означающий номер фрейма, таймер которого нужно запустить или остановить.

В этом протоколе и отправитель, и получатель работают с окнами неподтвержденных и допустимых номеров фреймов соответственно. Размер окна отправителя начинается с нуля и растет до определенного уровня. Размер окна получателя, напротив, всегда фиксированного размера. Получатель должен иметь буфер для каждого фрейма, номер которого находится в пределах окна. С каждым буфером связан бит, показывающий, занят буфер или свободен. Когда приходит фрейм, функция between проверяет, попал ли его порядковый номер в окно. Если да, то фрейм принимается и хранится в буфере. Это действие производится независимо от того, является ли он следующим фреймом, ожидаемым сетевым уровнем. Он должен храниться на канальном уровне до тех пор, пока все предыдущие фреймы не будут переданы сетевому уровню в правильном порядке. Пример протокола, использующего такой алгоритм, показан на илл. 3.21.

Способность протокола принимать фреймы в произвольной последовательности накладывает дополнительные ограничения на номера фреймов по сравнению с протоколами, в которых все пакеты принимались строго по порядку. Проще всего проиллюстрировать это на примере. Предположим, порядковый номер фрейма состоит из 3 бит, поэтому отправитель может посылать до семи фреймов, прежде чем перейти в режим ожидания подтверждения.

Начальное состояние окон отправителя и получателя изображено на илл. 3.22 (а). Отправитель передает фреймы с 0-го по 6-й. Окно получателя позволяет ему принимать любые фреймы с номерами от 0 по 6 включительно. Все семь фреймов успешно доставляются, поэтому получатель подтверждает их прием и передвигает окно для приема фреймов с номерами 7, 0, 1, 2, 3, 4 и 5, как показано на илл. 3.22 (б). Все семь буферов помечаются как свободные.

Именно в этот момент происходит авария: молния ударяет в телефонный столб и стирает все подтверждения. Протокол обязан отработать правильно, несмотря ни на какие чрезвычайные ситуации. Отправитель, не дождавшись подтверждений, посылает повторно фрейм 0. Когда он приходит получателю, производится проверка на предмет того, попадает ли он в его окно. На илл. 3.22 (б) фрейм 0, к сожалению, попадает в новое окно и потому принимается получателем как новый фрейм. Получатель также отправляет вложенное подтверждение для фрейма 6, поскольку были приняты все фреймы с 0-го по 6-й.

Отправитель с радостью узнает, что все переданные им фреймы успешно достигли адресата, поэтому он тут же передает фреймы 7, 0, 1, 2, 3, 4 и 5. Фрейм 7 принимается получателем, и содержащийся в нем пакет передается сетевому уровню. Сразу после этого принимающий канальный уровень проверяет наличие фрейма 0, обнаруживает его и передает старый буферизированный пакет сетевому уровню как новый. Таким образом, сетевой уровень получает неверный пакет; это означает, что протокол со своей задачей не справился.

Причина неудачи в том, что при сдвиге окна получателя новый интервал допустимых номеров фреймов перекрыл старый. Соответственно, присылаемый набор фреймов может содержать как новые фреймы (если все подтверждения были получены), так и повторно высланные старые (если подтверждения были потеряны). У принимающей стороны нет возможности отличить их.

Чтобы решить эту проблему, нужно убедиться, что в сдвинутом положении окно не перекроет исходное окно. Размер окна не должен превышать половины от количества порядковых номеров, как показано на илл. 3.22 (в) и 3.22 (г). Например, если для порядковых номеров используются 3 бита, они должны изменяться в пределах от 0 до 7. В таком случае в любой момент времени только четыре фрейма могут быть неподтвержденными. Таким образом, если будут получены фреймы с 0-го по 3-й и будет передвинуто окно для приема фреймов с 4-го по 7-й, получатель сможет безошибочно отличить повторную передачу (фреймы с 0-го по 3-й) от новых фреймов (с 4-го по 7-й). Поэтому в протоколе 6 применяется окно размером (MAX_SEQ + 1)/2.

Возникает новый вопрос: сколько буферов должно быть у получателя? Ни при каких условиях он не должен принимать фреймы, номера которых не попадают в окно. Поэтому количество необходимых буферов равно размеру окна, а не диапазону порядковых номеров. В приведенном выше примере 3-битных номеров требуется четыре буфера с номерами от 0 до 3. Когда приходит фрейм i, он помещается в буфер i mod 4. Обратите внимание, что хотя i и (i + 4), взятые по модулю 4, «соревнуются» за один и тот же буфер, они никогда не оказываются в одном окне одновременно, потому что это привело бы к увеличению размера окна по крайней мере до 5.

/* Протокол 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;

#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, packet buffer[ ])

{

/* Сформировать и послать данные, а также положительное или отрицательное подтверждение */

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; /* вначале буфер пуст */

for (i = 0; i < NR_BUFS; i++) arrived[i] = false;

while (true) {

wait_for_event(&event); /* пять возможных событий: см. event_type выше */

switch(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); /* фрейм пришел в целости */

inc(ack_expected); /* передвинуть нижний край окна отправителя */

}

break;

case 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,0,frame_expected, out_buf); /* истек период ожидания «попутки» для подтверждения; послать подтверждение */

}

if (nbuffered < NR_BUFS) enable_network_layer(); else disable_network_layer();

}

}

Илл. 3.21. Протокол раздвижного окна с выборочным повтором

Илл. 3.22. Пример работы протокола. (а) Начальная ситуация при размере окна 7. (б) Семь фреймов были посланы и приняты, но не подтверждены. (в) Начальная ситуация при размере окна 4. (г) Ситуация после того, как четыре фрейма были отправлены и получены, но не подтверждены

По этой же причине количество необходимых таймеров также равно числу буферов, а не диапазону порядковых номеров; то есть с каждым буфером связывается один таймер. Когда интервал времени истекает, содержимое буфера высылается повторно.

Протокол 6 также ослабляет неявное допущение, что загрузка канала довольно высока. Мы сделали это предположение в протоколе 5, в котором подтверждения вкладывались во фреймы данных, отсылаемые в обратном направлении. Если обратный поток информации невелик, подтверждения могут задерживаться на довольно большой период времени, создавая проблемы. В исключительной ситуации, когда в одном направлении посылается много информации, а во встречном — вообще ничего, протокол останавливается, как только окно отправителя достигает максимума.

В протоколе 6 эта проблема решена. Когда приходит последовательный фрейм данных, процедура start_ack_timer запускает вспомогательный таймер. Если таймер сработает раньше, чем появится фрейм с данными для передачи, то будет выслано отдельное подтверждение. Прерывание от вспомогательного таймера называется событием ack_timeout. При такой организации возможен однонаправленный поток данных, так как отсутствие встречных фреймов данных, в которые можно было бы вкладывать подтверждения, больше не является препятствием. Требуется всего один таймер. При вызове процедуры start_ack_timer, если таймер уже запущен, ничего не происходит. Таймер не сбрасывается и не продлевается, так как он нужен лишь для обеспечения некоторого минимального количества подтверждений.

Важно, что период времени вспомогательного таймера должен быть существенно короче интервала ожидания подтверждения. При этом условии подтверждение доставки правильного фрейма должно приходить прежде, чем у отправителя истечет период ожидания и он повторит передачу этого фрейма.

Протокол 6 использует более эффективную стратегию обработки ошибок, чем протокол 5. При появлении у получателя подозрений в том, что произошла ошибка, он высылает отправителю фрейм отрицательного подтверждения (NAK). Он представляет собой запрос на повторную передачу фрейма. NAK используется в двух случаях: если фрейм пришел поврежденным или если его номер отличается от ожидаемого (возможность потери фрейма). Чтобы избежать передачи нескольких запросов на повторную передачу одного и того же фрейма, получатель должен запоминать, был ли уже отправлен NAK для данного фрейма. В протоколе 6 для этой цели применяется переменная no_nak, принимающая значение true, если NAK для ожидаемого фрейма (с номером frame_expected) еще не был послан. Если NAK повреждается или теряется по дороге, это не имеет большого значения, так как у отправителя рано или поздно истечет период ожидания положительного подтверждения и он вышлет недостающий фрейм еще раз. Если неправильный фрейм пришел после того, как NAK был выслан и потерян, переменной no_nak опять присваивается true и запускается вспомогательный таймер. Когда время истечет, для восстановления синхронизации текущих состояний отправителя и получателя будет отправлено положительное подтверждение (ACK).

Иногда время, необходимое для прохождения фрейма по каналу, его обработки и отправки подтверждения, остается практически неизменным. В этом случае отправитель может установить время ожидания чуть больше ожидаемого интервала между отправкой фрейма и получением подтверждения. NAK при этом использовать бесполезно.

Однако в других ситуациях время прохождения сигнала в обе стороны может сильно варьироваться. Если встречный поток данных нерегулярен, то время прихода подтверждений также будет непостоянным, уменьшаясь при наличии встречного потока и увеличиваясь при его отсутствии. Перед отправителем возникает непростой выбор значения времени ожидания. Если выбрать слишком короткий интервал, то увеличится риск ненужных повторных передач. При выборе чересчур большого значения протокол будет тратить много времени на ожидания после ошибки. В обоих случаях пропускная способность тратится впустую. В целом если среднеквадратичное отклонение интервала ожидания подтверждения намного больше самого интервала, то таймер может быть установлен довольно «свободно». При этом NAK могут существенно ускорить повторную передачу потерянных или поврежденных фреймов.

С вопросом тайм-аутов и отрицательных подтверждений тесно связана проблема определения фрейма, вызвавшего тайм-аут. В протоколе 5 это всегда фрейм с номером ack_expected, поскольку он является старшим. В протоколе 6 нет столь простого способа определить фрейм с истекшим интервалом ожидания. Предположим, были переданы фреймы с 0-го по 4-й, то есть список неподтвержденных фреймов выглядит так: 01234 (от первого к последнему). Теперь допустим, что у фрейма 0 истекает интервал ожидания и он передается повторно, затем посылается фрейм 5 (новый), далее интервал ожидания истекает у фреймов 1 и 2 и посылается фрейм 6 (также новый). В результате список неподтвержденных фреймов принимает вид 3405126, начиная с самого старого и заканчивая самым новым. Если весь встречный поток данных потеряется, интервалы ожидания этих семи фреймов истекут именно в таком порядке.

Чтобы не усложнять и без того непростой пример протокола, мы не углуб­ляемся в детали управления таймером. Вместо этого мы просто предполагаем, что при наступлении тайм-аута переменной oldest_frame присваивается номер фрейма, интервал времени которого истек.