Книга Компьютерные сети. 6-е изд. - Эндрю Таненбаум

прибудет подтверждение фрейма 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. Еще одно вложенное подтверждение для фрейма