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

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

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

Здесь: Анализ эффективности алгоритмов повторной передачи - student2.ru - число бит, отведенных для заголовка кадра;

Анализ эффективности алгоритмов повторной передачи - student2.ru - число бит в протокольном блоке данных (для краткости, далее, в кадре).

Производительность протокола оценим отношением эффективной скорости передачи информации к номинальной пропускной способности канала R, т.е.

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

Для упрощения анализа примем следующие допущения:

· передача информации (I-кадры) осуществляется лишь в одном направлении, а обратный канал используется только для доставки сообщений ARQ;

· ошибки и повторная передача отсутствуют;

· все I-кадры имеют одинаковый размер, и передатчик всегда располагает кадрами, нуждающимися в отправке.

Рис.3.13 иллюстрирует составляющие задержки Анализ эффективности алгоритмов повторной передачи - student2.ru , вносимой в информационный обмен механизмом ARQ с остановкой и ожиданием.

Анализ эффективности алгоритмов повторной передачи - student2.ru , (3.4)

где: Анализ эффективности алгоритмов повторной передачи - student2.ru - число бит в I- и С-кадрах соответственно, а R – скорость, с которой данные передаются в канал (номинальная пропускная способность канала), бит/с.

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

Тогда, производительность протокола определится выражением

Анализ эффективности алгоритмов повторной передачи - student2.ru . (3.5)

Полученное соотношение ясно показывает факторы, отрицательно влияющие на эффективность алгоритма ARQ. В их числе: «расход» бит на заголовок кадра ( Анализ эффективности алгоритмов повторной передачи - student2.ru ), необходимость служебных кадров ( Анализ эффективности алгоритмов повторной передачи - student2.ru ) и величина произведения Анализ эффективности алгоритмов повторной передачи - student2.ru (задержка распространения Анализ эффективности алгоритмов повторной передачи - student2.ru производительность интерфейса).

Анализ эффективности алгоритмов повторной передачи - student2.ru R
30 Кбит/с 1,5 Мбит/с 45 Мбит/с 2,4 Гбит/с
Анализ эффективности алгоритмов повторной передачи - student2.ru 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
Анализ эффективности алгоритмов повторной передачи - student2.ru  
Анализ эффективности алгоритмов повторной передачи - student2.ru 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 представлены значения Анализ эффективности алгоритмов повторной передачи - student2.ru протокола SW-ARQ в условиях применения его на различных линиях передачи.

Таблица 3.2

При получении этих данных было принято, что ( Анализ эффективности алгоритмов повторной передачи - student2.ru ) = 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 с остановкой и ожиданием эффективен лишь при условии

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

которое выполняется при работе на низкоскоростных линиях с относительно небольшим временем распространения сигнала (линия малой протяженности).

Полученное выше выражение (3.5) не учитывает повторные передачи испорченных (потерянных) кадров. Рассмотрим эффективность протокола SW-ARQ в условиях наличия ошибок передачи. Напомним, что при повреждении кадра для его повторной передачи используется только механизм тайм-аута. Будем считать появление ошибочных кадров случайными независимыми событиями и обозначим Анализ эффективности алгоритмов повторной передачи - student2.ru - вероятность искажения (потери) кадра. Тогда, вероятность доставки кадра за i попыток составит

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

Пусть Анализ эффективности алгоритмов повторной передачи - student2.ru - число передач одного кадра, необходимое для его безошибочной доставки. Учтем, что при этом ( Анализ эффективности алгоритмов повторной передачи - student2.ru ) неудачных попыток потребовали задержек длительностью, равной тайм-ауту. Полное среднее время передачи кадра определяется выражением:

Анализ эффективности алгоритмов повторной передачи - student2.ru (3.6)

Пусть, для упрощения, Анализ эффективности алгоритмов повторной передачи - student2.ru , тогда

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

Соответственно, эффективная скорость передачи информации составит

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

Окончательно, эффективность работы протокола в условиях наличия ошибок описывается выражением

Анализ эффективности алгоритмов повторной передачи - student2.ru . (3.7)

Теперь обратимся к оценке эффективности протокола ARQ с возвратом на N. Будем считать, что размер окна передачи Анализ эффективности алгоритмов повторной передачи - student2.ru выбран так, что канал оказывается постоянно занятым. При отсутствии ошибок в кадрах это дает возможность получить Анализ эффективности алгоритмов повторной передачи - student2.ru . Однако, такое предположение не очень реалистично. Как и прежде, пусть Анализ эффективности алгоритмов повторной передачи - student2.ru - число передач одного кадра, требуемое для его успешной доставки. Если Анализ эффективности алгоритмов повторной передачи - student2.ru = i, то это означает, что потребовалась (i-1) повторная передача группы из Анализ эффективности алгоритмов повторной передачи - student2.ru кадров и одна удачная пересылка кадра. Следовательно, среднее общее время доставки кадра составит:

Анализ эффективности алгоритмов повторной передачи - student2.ru (3.8)

Эффективная скорость передачи информации, при этом, составит

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

Производительность же протокола ARQ с возвратом на N описывается выражением

Анализ эффективности алгоритмов повторной передачи - student2.ru . (3.9)

Из этого выражения хорошо видно, что увеличение окна передачи ведет к снижению производительности протокола.

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

Анализ эффективности алгоритмов повторной передачи - student2.ru . (3.10)

Соответственно, эффективная скорость передачи равна

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

Производительность протокола:

Анализ эффективности алгоритмов повторной передачи - student2.ru . (3.11)

Отметим, что выражения (3.9) и (3.11) не содержат в явном виде величину произведения Анализ эффективности алгоритмов повторной передачи - student2.ru , которая, как показано выше, существенно влияет на эффективность работы протокола с остановкой и ожиданием. Это обстоятельство является следствием предположения об отсутствии «простоев» в работе передатчика, что требует вполне определенной величины окна передачи и организации соответствующих буферов в передатчике и приемнике. В табл. 3.3 приведены размеры окна Анализ эффективности алгоритмов повторной передачи - student2.ru , обеспечивающего постоянную занятость канала на линиях, для которых были получены результаты, представленные в табл.3.2.

Таблица 3.3

Анализ эффективности алгоритмов повторной передачи - student2.ru R
30 кбит/с 1,5 мбит/с 45 мбит/с 2,4 Гбит/с
Анализ эффективности алгоритмов повторной передачи - student2.ru 5∙10-3
5∙10-2
5∙10-1
Анализ эффективности алгоритмов повторной передачи - student2.ru        
Анализ эффективности алгоритмов повторной передачи - student2.ru 5∙10-3
5∙10-2
5∙10-1

Эти данные показывают, что приемлемая величина окна, при котором канал полностью загружается, может быть получена лишь для относительно низкоскоростных каналов. Уже для канала 45 Мбит/с разумный размер окна можно получить только для очень «длинных» кадров. Однако такие кадры больше подвержены влиянию помех, поэтому «разумный» размер кадра должен выбираться с учетом закона распределения вероятности ошибок в канале. Для канала с равномерным распределением ошибок по битам и при вероятности возникновения ошибки в одном бите равной p получаем

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

Требование Анализ эффективности алгоритмов повторной передачи - student2.ru <<1, очевидно, накладывает ограничение на длину кадра Анализ эффективности алгоритмов повторной передачи - student2.ru .

Рис.3.14 дает сравнительную картину эффективности рассмотренных протоколов при работе их на каналах с ошибками. Эти кривые получены при следующих значениях параметров: Анализ эффективности алгоритмов повторной передачи - student2.ru = 1024 Б, R = 1,5 Мбит/с, Анализ эффективности алгоритмов повторной передачи - student2.ru .

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

Из приведенных графиков хорошо видно, что эффективность алгоритма повторной передачи с остановками и ожиданием остается малой ( Анализ эффективности алгоритмов повторной передачи - student2.ru <0,33) даже при очень низкой вероятности битовых ошибок. При вероятностях ошибок, превышающих значение 10-4, эффективность любого механизма ARQ оказывается достаточно низкой, что является следствием высокого значения вероятности искажения кадров. Действительно, Анализ эффективности алгоритмов повторной передачи - student2.ru , т.е. более трех четвертей кадров могут содержать ошибки!

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

  1. Почему в протоколе ARQ с остановками и ожиданием приемник отправляет кадр ACK даже при получении информационного кадра с ошибочным порядковым номером?
  2. Файл, величина которого 1 Мбайт, передается по каналу с пропускной способностью 1 Мбит/сек.; вероятность битовых ошибок в канале p=10-6.
    1. Какова при этом вероятность безошибочной передачи файла одним блоком данных? При больших n и малых p можно считать Анализ эффективности алгоритмов повторной передачи - student2.ru .
    2. Какова вероятность безошибочной передачи файла при его фрагментации на N кадров одинаковой величины?
    3. Каково среднее время доставки файла, если на канальном уровне используется механизм ARQ с остановками и ожиданием? Как будет изменяться это время при N = 80, 800, 8000?
  3. Вероятность искажения информационного кадра Pfr, а кадра ACK - Pa. Величина информационного кадра в 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*108 м/сек. Пропускная способность канала 8,448 Мбит/сек., а вероятность битовой ошибки 2*10-6. По каналу должны передаваться кадры, размер которых 1 Кбит. Вычислить эффективность такого звена при использовании на нем механизмов ARQ с остановкой и ожиданием, с возвратом на N и с выборочным повторением.

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

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

Наши рекомендации