Максимальное число неподтвержденных кадров в любой момент времени не совпадает с размером пространства порядковых номеров. Для протокола с возвратом на 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 (то есть все предыдущие кадры) автоматически считаются подтвержденными. Такой тип подтверждения называется кумулятивным (cumulative acknowledgement). Эта особенность наиболее важна в случае потери или повреждения какого-либо кадра с подтверждением. Получив подтверждение, канальный уровень проверяет, не освободился ли у него какой-нибудь буфер. Если буфер освобождается, то заблокированному ранее сетевому уровню можно снова разрешить инициировать события 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, б. Такая организация таймеров не требует выполнения большой работы при каждом прерывании от системных часов,

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

Рис. 3.14. Программная симуляция работы нескольких таймеров

3.4.3. Протокол с выборочным повтором

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

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

Листинг 3.7. Протокол скользящего окна с выборочным повтором

Листинг 3.7 (продолжение)

Листинг 3.7 (продолжение)

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

Рис. 3.15. Пример работы протокола: а — начальная ситуация при размере окна 7; б — 7 кадров были посланы и приняты, но не подтверждены; в — начальная ситуация при размере окна 4; г — ситуация после того, как 4 кадра были отправлены и получены, но не подтверждены

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

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

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