Анализ эффективности алгоритмов повторной передачи
Эффективная скорость передачи протокольного блока данных определим выражением:
,
Здесь: 
- число бит, отведенных для заголовка кадра;
- число бит в протокольном блоке данных (для краткости, далее, в кадре).
Производительность протокола оценим отношением эффективной скорости передачи информации к номинальной пропускной способности канала R, т.е.
.
Для упрощения анализа примем следующие допущения:
· передача информации (I-кадры) осуществляется лишь в одном направлении, а обратный канал используется только для доставки сообщений ARQ;
· ошибки и повторная передача отсутствуют;
· все I-кадры имеют одинаковый размер, и передатчик всегда располагает кадрами, нуждающимися в отправке.
Рис.3.13 иллюстрирует составляющие задержки 
, вносимой в информационный обмен механизмом ARQ с остановкой и ожиданием.
, (3.4)
где: 
- число бит в I- и С-кадрах соответственно, а R – скорость, с которой данные передаются в канал (номинальная пропускная способность канала), бит/с.
 |
Тогда, производительность протокола определится выражением
. (3.5)
Полученное соотношение ясно показывает факторы, отрицательно влияющие на эффективность алгоритма ARQ. В их числе: «расход» бит на заголовок кадра ( 
), необходимость служебных кадров ( 
) и величина произведения 
(задержка распространения 
производительность интерфейса).
| R | ||||
| 30 Кбит/с | 1,5 Мбит/с | 45 Мбит/с | 2,4 Гбит/с | ||
| 5∙10-3 | 0,95 | 0,35 | 1,77∙10-2 | 3,39∙10-4 |
| 5∙10-2 | 0,72 | 5,14∙10-2 | 1,80∙10-3 | 3,39∙10-5 | |
| 5∙10-1 | 0,21 | 5,39∙10-3 | 1,81∙10-4 | 3,39∙10-6 | |
| |||||
|
| 5∙10-3 | 0,99 | 0,97 | 0,53 | 2,1∙10-2 |
| 5∙10-2 | 0,99 | 0,77 | 1,04∙10-1 | 2,18∙10-3 | |
| 5∙10-1 | 0,21 | 0,26 | 1,15∙10-2 | 2,18∙10-4 |
В таблице 3.2 представлены значения 
протокола SW-ARQ в условиях применения его на различных линиях передачи.
Таблица 3.2
При получении этих данных было принято, что ( 
) = 5мс, 50мс и 500мс. При скорости распространения электромагнитных волн 3∙108 м/с эти задержки соответствуют линиям протяженностью 1,5∙103 км, 1,5∙104 км и 1,5∙105 км, что является характерным для национальных, межконтинентальных и спутниковых линий связи. Номинальная пропускная способность линий составляла R = 30 Кбит/с (модемное соединение), 1,5 Мбит/с (линия T1), 45 Мбит/с и 2,4 Гбит/с (линия современной базовой сети). Выражение (3.5) и приведенные в таблице 3.2. значения наглядно показывают, что ARQ с остановкой и ожиданием эффективен лишь при условии
,
которое выполняется при работе на низкоскоростных линиях с относительно небольшим временем распространения сигнала (линия малой протяженности).
Полученное выше выражение (3.5) не учитывает повторные передачи испорченных (потерянных) кадров. Рассмотрим эффективность протокола SW-ARQ в условиях наличия ошибок передачи. Напомним, что при повреждении кадра для его повторной передачи используется только механизм тайм-аута. Будем считать появление ошибочных кадров случайными независимыми событиями и обозначим 
- вероятность искажения (потери) кадра. Тогда, вероятность доставки кадра за i попыток составит
.
Пусть 
- число передач одного кадра, необходимое для его безошибочной доставки. Учтем, что при этом ( 
) неудачных попыток потребовали задержек длительностью, равной тайм-ауту. Полное среднее время передачи кадра определяется выражением:
(3.6)
Пусть, для упрощения, 
, тогда
.
Соответственно, эффективная скорость передачи информации составит
.
Окончательно, эффективность работы протокола в условиях наличия ошибок описывается выражением
. (3.7)
Теперь обратимся к оценке эффективности протокола ARQ с возвратом на N. Будем считать, что размер окна передачи 
выбран так, что канал оказывается постоянно занятым. При отсутствии ошибок в кадрах это дает возможность получить 
. Однако, такое предположение не очень реалистично. Как и прежде, пусть 
- число передач одного кадра, требуемое для его успешной доставки. Если 
= i, то это означает, что потребовалась (i-1) повторная передача группы из кадров и одна удачная пересылка кадра. Следовательно, среднее общее время доставки кадра составит:
(3.8)
Эффективная скорость передачи информации, при этом, составит
.
Производительность же протокола ARQ с возвратом на N описывается выражением
. (3.9)
Из этого выражения хорошо видно, что увеличение окна передачи ведет к снижению производительности протокола.
Для протокола с выборочным повторением каждая неудачная передача кадра влечет за собой повторную передачу лишь одного кадра. Следовательно, среднее время, затрачиваемое на передачу кадра, составляет
. (3.10)
Соответственно, эффективная скорость передачи равна
.
Производительность протокола:
. (3.11)
Отметим, что выражения (3.9) и (3.11) не содержат в явном виде величину произведения 
, которая, как показано выше, существенно влияет на эффективность работы протокола с остановкой и ожиданием. Это обстоятельство является следствием предположения об отсутствии «простоев» в работе передатчика, что требует вполне определенной величины окна передачи и организации соответствующих буферов в передатчике и приемнике. В табл. 3.3 приведены размеры окна , обеспечивающего постоянную занятость канала на линиях, для которых были получены результаты, представленные в табл.3.2.
Таблица 3.3
| R | ||||
| 30 кбит/с | 1,5 мбит/с | 45 мбит/с | 2,4 Гбит/с | ||
|
| 5∙10-3 | ||||
| 5∙10-2 | |||||
| 5∙10-1 | |||||
| |||||
|
| 5∙10-3 | ||||
| 5∙10-2 | |||||
| 5∙10-1 |
Эти данные показывают, что приемлемая величина окна, при котором канал полностью загружается, может быть получена лишь для относительно низкоскоростных каналов. Уже для канала 45 Мбит/с разумный размер окна можно получить только для очень «длинных» кадров. Однако такие кадры больше подвержены влиянию помех, поэтому «разумный» размер кадра должен выбираться с учетом закона распределения вероятности ошибок в канале. Для канала с равномерным распределением ошибок по битам и при вероятности возникновения ошибки в одном бите равной p получаем
.
Требование <<1, очевидно, накладывает ограничение на длину кадра 
.
Рис.3.14 дает сравнительную картину эффективности рассмотренных протоколов при работе их на каналах с ошибками. Эти кривые получены при следующих значениях параметров: = 1024 Б, R = 1,5 Мбит/с, 
.
 |
Из приведенных графиков хорошо видно, что эффективность алгоритма повторной передачи с остановками и ожиданием остается малой ( 
<0,33) даже при очень низкой вероятности битовых ошибок. При вероятностях ошибок, превышающих значение 10-4, эффективность любого механизма ARQ оказывается достаточно низкой, что является следствием высокого значения вероятности искажения кадров. Действительно, 
, т.е. более трех четвертей кадров могут содержать ошибки!
Контрольные вопросы
- Почему в протоколе ARQ с остановками и ожиданием приемник отправляет кадр ACK даже при получении информационного кадра с ошибочным порядковым номером?
- Файл, величина которого 1 Мбайт, передается по каналу с пропускной способностью 1 Мбит/сек.; вероятность битовых ошибок в канале p=10-6.
- Какова при этом вероятность безошибочной передачи файла одним блоком данных? При больших n и малых p можно считать
. - Какова вероятность безошибочной передачи файла при его фрагментации на N кадров одинаковой величины?
- Каково среднее время доставки файла, если на канальном уровне используется механизм ARQ с остановками и ожиданием? Как будет изменяться это время при N = 80, 800, 8000?
- Вероятность искажения информационного кадра Pfr, а кадра ACK - Pa. Величина информационного кадра в m раз больше кадра подтверждения. На канальном уровне работает протокол ARQ с остановками и ожиданием, а скорость передачи равна R бит/сек. Временем распространения сигнала и временем обработки кадров передатчиком и приемником можно пренебречь.
- Каково среднее время перехода системы «передатчик – приемник» из состояния (0,0) в состояние (0,1)?
- Каково среднее время перехода системы «передатчик – приемник» из состояния (0,1) в состояние (1,1)?
- Что произойдет с протоколом ARQ с возвратом на N, если:
- исключить в нем механизм time-out?
- исключить кумулятивный принцип подтверждения полученных без ошибок кадров и заменить его подтверждением каждого полученного кадра?
- Пусть возможны три стратегии подтверждения полученных кадров:
- немедленная отправка АСК после получения корректного информационного кадра;
- отправка одного АСК на каждые два полученных информационных кадра;
- отправка АСК вместе с «попутным» информационным кадром в обратном направлении.
Какая из этих стратегий будет более подходящей для:
a. поддержки терминального приложения, которое отправляет кадр на сервер при каждом нажатии клавиши на клавиатуре клиента, а сервер немедленно подтверждает прием, отправкой клиенту пакета с этим символом?
b. Поддержки приложения, передающего большой файл с предварительной его фрагментацией на достаточно большое количество пакетов?
6. Длина линии, соединяющей 2 узла, равна 100 км. Скорость распространения электромагнитной волны в линии 2,4*108 м/сек. Пропускная способность канала 8,448 Мбит/сек., а вероятность битовой ошибки 2*10-6. По каналу должны передаваться кадры, размер которых 1 Кбит. Вычислить эффективность такого звена при использовании на нем механизмов ARQ с остановкой и ожиданием, с возвратом на N и с выборочным повторением.
7. Используя диаграмму последовательности кадров, опишите, как механизм SR-ARQ работает при потере информационного кадра и кадра ACK.
8. Какова роль механизма тайм-аута в рассмотренных схемах ARQ? Какие факторы влияют на величину интервала тайм-аута?