Анализ эффективности алгоритмов повторной передачи

Эффективная скорость передачи протокольного блока данных определим выражением:

,

Здесь: - число бит, отведенных для заголовка кадра;

- число бит в протокольном блоке данных (для краткости, далее, в кадре).

Производительность протокола оценим отношением эффективной скорости передачи информации к номинальной пропускной способности канала 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∙10⁸ м/с эти задержки соответствуют линиям протяженностью 1,5∙10³ км, 1,5∙10⁴ км и 1,5∙10⁵ км, что является характерным для национальных, межконтинентальных и спутниковых линий связи. Номинальная пропускная способность линий составляла 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 оказывается достаточно низкой, что является следствием высокого значения вероятности искажения кадров. Действительно, , т.е. более трех четвертей кадров могут содержать ошибки!

Контрольные вопросы

1. Почему в протоколе ARQ с остановками и ожиданием приемник отправляет кадр ACK даже при получении информационного кадра с ошибочным порядковым номером?
2. Файл, величина которого 1 Мбайт, передается по каналу с пропускной способностью 1 Мбит/сек.; вероятность битовых ошибок в канале p=10^-6.
1. Какова при этом вероятность безошибочной передачи файла одним блоком данных? При больших n и малых p можно считать .
2. Какова вероятность безошибочной передачи файла при его фрагментации на N кадров одинаковой величины?
3. Каково среднее время доставки файла, если на канальном уровне используется механизм ARQ с остановками и ожиданием? Как будет изменяться это время при N = 80, 800, 8000?
3. Вероятность искажения информационного кадра P_fr, а кадра ACK - P_a. Величина информационного кадра в m раз больше кадра подтверждения. На канальном уровне работает протокол ARQ с остановками и ожиданием, а скорость передачи равна R бит/сек. Временем распространения сигнала и временем обработки кадров передатчиком и приемником можно пренебречь.
1. Каково среднее время перехода системы «передатчик – приемник» из состояния (0,0) в состояние (0,1)?
2. Каково среднее время перехода системы «передатчик – приемник» из состояния (0,1) в состояние (1,1)?
4. Что произойдет с протоколом ARQ с возвратом на N, если:
1. исключить в нем механизм time-out?
2. исключить кумулятивный принцип подтверждения полученных без ошибок кадров и заменить его подтверждением каждого полученного кадра?
5. Пусть возможны три стратегии подтверждения полученных кадров:
1. немедленная отправка АСК после получения корректного информационного кадра;
2. отправка одного АСК на каждые два полученных информационных кадра;
3. отправка АСК вместе с «попутным» информационным кадром в обратном направлении.

Какая из этих стратегий будет более подходящей для:

a. поддержки терминального приложения, которое отправляет кадр на сервер при каждом нажатии клавиши на клавиатуре клиента, а сервер немедленно подтверждает прием, отправкой клиенту пакета с этим символом?

b. Поддержки приложения, передающего большой файл с предварительной его фрагментацией на достаточно большое количество пакетов?

6. Длина линии, соединяющей 2 узла, равна 100 км. Скорость распространения электромагнитной волны в линии 2,4*10⁸ м/сек. Пропускная способность канала 8,448 Мбит/сек., а вероятность битовой ошибки 2*10^-6. По каналу должны передаваться кадры, размер которых 1 Кбит. Вычислить эффективность такого звена при использовании на нем механизмов ARQ с остановкой и ожиданием, с возвратом на N и с выборочным повторением.

7. Используя диаграмму последовательности кадров, опишите, как механизм SR-ARQ работает при потере информационного кадра и кадра ACK.

8. Какова роль механизма тайм-аута в рассмотренных схемах ARQ? Какие факторы влияют на величину интервала тайм-аута?