Описанная выше проблема является следствием правила, заставлявшего отправителя дожидаться подтверждения, прежде чем посылать следующий кадр. Смягчив это требование, можно значительно повысить эффективность. Решение проблемы заключается в разрешении отправителю послать не один кадр, а несколько, например 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.13.
Рис. 3.13. Конвейеризация и коррекция ошибок: а — эффект при размере окна 1; б — эффект при размере окна больше 1
Первый способ называется возвратом на n (go-back-n) и заключается просто в игнорировании всех кадров, следующих за ошибочным. Для таких кадров подтверждения не посылаются. Эта стратегия соответствует приемному окну размера 1. Другими словами, канальный уровень отказывается принимать какой-либо кадр, кроме кадра со следующим номером, который он должен передать сетевому уровню. Если окно отправителя заполнится раньше, чем истечет период времени ожидания, конвейер начнет простаивать. Наконец, лимит времени у отправителя истечет, и он начнет передавать повторно сразу все кадры, не получившие подтверждения, начиная с поврежденного или потерянного кадра. Такой подход при высоком уровне ошибок может привести к потере большой доли пропускной способности канала.
На рис. 3.13, б изображен возврат на n для случая большого окна приемника. Кадры 0 и 1 корректно принимаются, и высылается подтверждение этого факта. Однако кадр 2 потерялся или был испорчен. Ничего не подозревающий отправитель продолжает посылать кадры, пока не выйдет время ожидания кадра 2. Только после этого он возвращается к месту сбоя и заново передает все кадры, начиная с кадра 2 (отправляя 2, 3, 4 и т. д.).
Другая общая стратегия обработки ошибок при конвейерной передаче кадров, называемая выборочным повтором (selective repeat), заключается в том, что получатель хранит в буфере все правильные кадры, принятые им после неверного или потерянного кадра. При этом неверный кадр отбрасывается. Когда заканчивается время ожидания подтверждения, отправитель отправляет еще раз только самый старый кадр, для которого не пришло подтверждение. Если вторая попытка будет успешной, получатель сможет последовательно передать накопившиеся пакеты сетевому уровню. Выборочный повтор используется, когда размер окна получателя больше 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
Листинг 3.6 (продолжение)
Выбор одной из двух приведенных выше стратегий является вопросом компромисса между эффективным использованием пропускной способности и размером буфера канального уровня. В зависимости от того, что в конкретной ситуации является более критичным, может использоваться тот или иной метод. В листинге 3.6 показан конвейерный протокол, в котором принимающий уровень передачи данных принимает кадры по порядку. Все кадры, следующие за ошибочным, игнорируются. В данном протоколе мы впервые отказались от предположения, что у сетевого уровня всегда есть неограниченное количество пакетов для отсылки. Когда у сетевого уровня появляется пакет, который он хочет отправить, уровень инициирует событие network_layer_ready. Однако чтобы управлять потоком на основе размера окна отправителя и числа неподтвержденных кадров в любой момент времени, канальный уровень должен иметь возможность отключать на время сетевой уровень. Для этой цели служит пара библиотечных процедур — enable_network_layer и disable_network_layer.
