WWW.KNIGA.LIB-I.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Онлайн материалы
 

«УДК 621.391 Использование управляемого хоппинга для уменьшения коэффициента потерь блоков с ограниченным числом переспросов О.Г. Мелентьев, И.Е. ...»

Вестник СибГУТИ. 2012. № 1 61

УДК 621.391

Использование управляемого хоппинга

для уменьшения коэффициента потерь блоков

с ограниченным числом переспросов

О.Г. Мелентьев, И.Е. Шевнина

В работе рассматривается задача передачи потока данных с ограниченным временем на

доставку блока по пучку каналов с группирующимся характером поражения блоков.

Предложены два алгоритма управления хоппингом, позволяющие уменьшить коэффициент потерь блоков. Проведено сравнение предложенных алгоритмов с идеальным алгоритмом управления и алгоритмом, не использующим управляемый хоппинг.

Ключевые слова: пучок каналов, простая марковская цепь, модель Гилберта, управление хоппингом.

1. Введение Довольно часто между двумя узлами сети имеется несколько каналов или маршрутов.

Это могут быть каналы с частотным разделением, каналы, организованные в разных кабелях, разными системами передачи (например: кабельный и радиорелейный или спутниковый) или каналы, проходящие через сеть по разным географическим маршрутам. Мы не будем привязываться к конкретной системе и физической природе каналов. Рассмотрим абстрактную систему передачи данных, имеющую между передатчиком и примником пучок параллельных каналов. Временные слоты канала предоставляются для передачи блоков данных.

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



Имеющийся ресурс пучка из N каналов предоставляется для обслуживания потока данных с ограничением временем на доставку блока. Причинами задержек блоков обычно являются занятость выходных портов передачей данных других приложений и повторные передачи, обусловленные возникновением ошибок. Так как в нашем случае весь пучок каналов предоставляется для обслуживания одного приложения реального времени, то причиной задержек будут только повторные передачи. Время задержки блока будет кратно количеству переспросов, поэтому далее будем использовать ограничение числа переспросов Lm. Если за Lm попыток блок не доставлен, он отбрасывается и система переходит к передаче следующего блока. Количественно потери блоков будем характеризовать коэффициентом потерь K П. Данный коэффициент определяется отношением числа блоков, отброшенных из-за превышения допустимой задержки, к числу безошибочно доставленных блоков. Очевидно, что для повышения качества передачи необходимо уменьшать K П. Попытаемся уменьшить потери блоков, используя управляемый хоппинг. Под хоппингом будем понимать синхронное изменение каналов между передатчиком и приемником по определнному алгоритму.

Мелентьев О.Г., Шевнина И.Е.

2. Алгоритмы управления хоппингом В работе [1] были получены предельные численные оценки выигрыша от применения управляемого хоппинга при использовании идеального алгоритма управления. Идеальный алгоритм абсолютно точно прогнозирует поражнные слоты. В данной работе предлагаются два алгоритма управления хоппингом, обеспечивающие количественную оценку вероятности успеха при приме следующего слота во всех каналах пучка, ранжирование каналов по качеству, ранжирование блоков, находящихся в буфере, по приоритету и предоставление блокам льшим приоритетом слота в канале с лучшим прогнозом.

Алгоритмы управляемого хоппинга являются расширенной модификацией алгоритмов построения приоритетного логического канала (ПЛК), рассмотренных в [2].





Как показано в [3, 4], статистика поражений блоков имеет группирующийся характер и удовлетворительно аппроксимируется моделями на основе цепей Маркова с двумя состояниями. Свойство группирования ошибок мы попытаемся использовать для прогнозирования качества передачи в будущем по результатам предыдущих попыток. Для математического описания группирования поражений слотов мы будем использовать простую марковскую цепь с двумя состояниями, или модель Гилберта.

Модель Гилберта предполагает наличие двух состояний канала, хорошего ( g ), в котором поражения слотов не происходит и плохого ( b ), в котором слоты поражаются с некоторой вероятностью Pош. Дискретным шагом системы является передача слота. Сохранение и смена состояний на следующем шаге описываются соответствующими переходными вероятностями: Pgg, Pbb, Pgb, и Pbg.

Простая марковская цепь является частным случаем модели Гилберта при Pош 1.

Каждый исходный канал при моделировании представляется вектором длиной V, элементы которого принимают значение 0 при безошибочной передаче слота и 1, если в слоте есть ошибки. Распределение нулей и единиц подчиняется модели Гилберта с заданными параметрами. Пучок исходных каналов представлен объединением соответствующих векторов в матрицу каналов M размерностью V N.

В общем случае приоритет блоков может задаваться приложением, генерирующим поток. Мы же рассмотрим ситуацию, когда изначально все блоки обслуживаемого потока имеют одинаковый приоритет. В процессе передачи некоторые блоки поражаются ошибками и требуют повторения. Так как время жизни блока (или максимальное число переспросов) ограничено, то пропорционально числу неудачных попыток повышается и приоритет блока.

Блоки обслуживаемого потока передаются в канальных слотах пучка параллельно по N блоков. При отсутствии управления хоппингом, слоты каналов пучка заполняются блоками в порядке их поступления и для повторения поражнных блоков канал не меняется. Клетка с тмным фоном на рис. 1 символизирует поражение пятого блока, который повторно передается в том же канале.

Рис. 1. Заполнение слотов по алгоритму A0.

Использование хоппинга для уменьшения потерь блоков с ограниченным числом переспросов 63 Назовем такой порядок заполнения алгоритмом А0. Он будет использован как база для сравнения эффективности рассмотренных алгоритмов, реализующих управление.

На прохождение блока по сети затрачивается некоторое время. Для учта временных задержек от момента отправки блока до момента получения квитанции о качестве прима блока при моделировании вводится величина x, выраженная в слотах.

В процессе управления параллельной передачей по какому-либо алгоритму из матрицы каналов формируется матрица передач. Нули матрицы соответствуют успешной передаче слота, ненулевые элементы указывают количество неудачных примов блока, передаваемого в данном слоте. Пример матрицы передач для трх параллельных каналов показан на рис. 2.

Отмеченные фоном клетки соответствуют ошибочным слотам, диагональные линии указывают на изменение канала после неудачной попытки. Числа в клетках отражают количество неудач при передаче блоков.

Рис. 2. Пример матрицы передач

Анализируя матрицы передач, сформированные рассматриваемыми алгоритмами, получим все необходимые характеристики.

Как показано в [2], все алгоритмы прогноза по использованию информации о результатах предыдущих попыток передачи можно разделить на две группы:

– алгоритмы с единичной памятью принимают решения о выделении слота на основании анализа качества прима последнего блока в каждом канале пучка, информация о котором к текущему моменту известна на передаче (под качеством прима будем понимать отсутствие или наличие ошибок в принятом блоке);

– алгоритмы с длительной памятью принимают решения о выделении слота на основании анализа результатов некоторого числа последних попыток.

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

АБ-СКО – алгоритмы выбора по среднему коэффициенту ошибок / – с неограниченным буфером; /L – с ограниченным буфером длиной L. Алгоритмы предполагают организацию буферов, в которых хранятся результаты качества последних примов в каждом канале.

Для каждого канала по содержимому буфера оценивается средний коэффициент правильного прима блоков, в соответствии с которым каналы ранжируются по качеству. Далее для более приоритетного блока на каждом шаге предоставляется слот исходного канала с меньшим числом ошибок в буфере. При неограниченном буфере или известных коэффициентах ошибок алгоритм является идеализированным и представляет интерес только как объект для сравнения при оценке эффективности реальных алгоритмов. Вариант блок-схемы алгоритма АБ-СКО/L с фиксированной длиной буфера показан на рис. 3.

В блоке 5 проводится заполнение вектора неудачных передач блоков ( E ). Элементами вектора является количество неудачных попыток передачи для N блоков, находящихся в буфере наибольшее время. Блоки 7 – 9 обеспечивают просмотр L элементов буфера в установившемся режиме, блоки 10 – 12 реализуют анализ на начальном этапе передачи, когда буфер ещ не содержит L квитанций. Элементы вектора положительного прогноза W в данном алгоритме имеют смысл количества положительных квитанций из L последних, полученных передатчиком. Для определения приоритетов была разработана процедура сортировки массива (Pr(x)), которая возвращает индексы элементов массива x, расположенных в порядке убывания значений.

Мелентьев О.Г., Шевнина И.Е.

Рис. 3. Блок-схема выбора ПЛК по алгоритму АБ-СКО/L

Блок 13 обеспечивает сортировку каналов по качеству, анализируя вектор положительного прогноза ( Pr(W ) ), и сортировку блоков по числу неудачных попыток ( Pr(E) ). Далее блок с высшим приоритетом (или большим числом неудач) передатся по каналу с лучшим качеИспользование хоппинга для уменьшения потерь блоков с ограниченным числом переспросов 65 ством. При этом (блоки 14 – 17) изменение элемента M [i,Wpr j ] матрицы передач (т.е. увеличение количества неудачных попыток передачи блока) производится только тогда, когда элементы M [i x, Epr j ] и M [i,Wpr j ] не нулевые (т.е. при повторной передаче блок передатся в слоте с ошибкой).

Следующий алгоритм учитывает параметры группирования ошибок. Для принятия решений он использует оценки переходных вероятностей простых цепей Маркова (А1Б-ПЦМ) (или модели Гилберта – А1Б-Г), описывающих процессы поражения слотов исходных каналов.

Первоначальное определение параметров модели Гилберта и последующие их оперативные корректировки в процессе работы обеспечиваются соответствующим алгоритмом корректировки. Методики оперативной оценки параметров модели Гилберта по результатам статистических испытаний и определение объмов испытаний, необходимых для обеспечения требуемой точности оценок, подробно рассмотрены в [4].

По результатам прима последнего блока и известным переходным вероятностям вычисляются коэффициенты положительного прогноза для каждого канала. Определим коэффициент положительного прогноза при ошибке в последнем слоте для случая, когда канал удовлетворительно описывается моделью Гилберта и задержка квитанций отсутствует.

Если текущий слот поражн, то, в соответствии с моделью Гилберта, канал действительно находится в плохом состоянии, а это значит, что вероятность прима следующего слота без ошибок складывается из двух альтернатив:

1 – канал сохраняет плохое состояние, но ошибки не происходит;

2 – при передаче следующего слота канал переходит в хорошее состояние, где ошибок нет по определению.

В данном случае для вероятности прима следующего слота без ошибок можно записать Wbg Pbb (1 Pош ) Pbg. (1) Если последний слот был передан без ошибок, то коэффициент положительного прогноза Pg Pb (1 Pош ) Pbb (1 Pош ) Pbg. (2) Wgg Pgg Pgb (1 Pош ) 1 Pb Pош 1 Pb Pош Здесь Pgg, Pgb, Pbg, Pbb – переходные, Pg, Pb – финальные вероятности модели Гилберта, Pош – вероятность ошибки в плохом состоянии канала.

Для произвольной задержки квитанций коэффициенты прогноза качества доставки текущих слотов по результатам предыдущих попыток получены в работе [5].

Ранжирование каналов осуществляется по коэффициентам положительного прогноза.

В качестве лучшего выбирается канал с максимальным коэффициентом прогноза.

Блок-схема управления хоппингом в соответствии с алгоритмом А1Б-ПЦМ представлена на рис. 4.

После сортировки каналов и приоритизации блоков повторные передачи высокоприоритетных блоков производятся в каналах с максимальным коэффициентом положительного прогноза. Такой подход позволяет различать каналы по качеству даже при одинаковых исходах в последней попытке.

В блоке 2 формируется матрица коэффициентов положительного прогноза Wg. Число строк матрицы определяется числом каналов пучка.

Число столбцов равно двум. Нулевой столбец содержит коэффициенты положительного прогноза для случая, когда последний переданный в канале слот, квитанция о качестве прима которого получена на передаче, не содержал ошибок. Первый столбец содержит коэффициенты для случая с ошибками. Блок 5 заполняет вектор неудачных передач блоков. Блоки 6 – 8 обеспечивают формирование вектора коэффициентов положительного прогноза на основании квитанций о качестве прима последних блоков в каждом канале пучка.

Мелентьев О.Г., Шевнина И.Е.

Рис. 4. – Блок-схема управления хоппингом по алгоритму А1Б-ПЦМ

Для оценки предельных возможностей алгоритмов управления хоппингом был использован идеальный алгоритм, который абсолютно точно прогнозирует качество передачи блоков в следующей попытке. В имитационной модели это обеспечивается тем, что при заполнении Использование хоппинга для уменьшения потерь блоков с ограниченным числом переспросов 67 вектора прогноза качества передачи используются не результаты качества прима последней попытки, а элементы матрицы каналов текущей i -той попытки, т.е. непосредственно результаты прима слотов, из которых производится выбор.

3. Результаты моделирования Для рассмотренных выше алгоритмов было проведено имитационное моделирование, позволившее получить количественные оценки эффективности их применения. На рис. 5 приведены зависимости вероятности доставки блока точно с заданной попытки при задержке квитанции на один слот и трх каналах в пучке. Параметры модели Гилберта, описывающей исходные каналы, соответственно равны P1gg 0.95, P1bb 0.93 ; P 2 gg 0.93, 0.93, при этом вероятность поражения слота в плохом соP3gg 0.98, P3bb P2 bb стоянии всех каналов равна 0.5.

Рис. 5. Зависимости вероятности доставки блока точно с заданной попытки при задержке квитанции на один слот и трх каналах в пучке. a – в логарифмическом и b – в линейном масштабе.

1 – А0; 2 – АБ-СКО/10; 3 – А1Б-Г; 4 – Идеальный алгоритм Как видим, применение рассмотренных алгоритмов управления хоппингом позволяют значительно увеличить вероятности успешной доставки со второй и третьей попыток и уменьшить тем самым необходимость большого числа повторений. Для более детального анализа рассмотрим начальный участок в линейном масштабе (рис.5b). Как видим, применение алгоритмов управления несколько снижает вероятность успешной доставки с первой попытки, но за счт этого существенно увеличивает успех во второй и третьей попытках. В результате такого перераспределения значительно возрастает вероятность успешной доставки при заданном ограничении максимального числа переспросов пакетов (рис.6а).

Мелентьев О.Г., Шевнина И.Е.

Зависимость коэффициента потерь блоков от допустимого числа переспросов показана на рис. 6b. Как видим, при использовании алгоритмов управления потери блоков уменьшаются в 2 – 11 раз. В каналах, где статистика поражений слотов подчиняется простой марковской цепи (т.е. вероятность ошибки в плохом состоянии равна единице), рассмотренные алгоритмы показывают результаты, соизмеримые с идеальным алгоритмом. В этом случае потери блоков можно снизить в десятки раз.

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

Рис. 6. Зависимости вероятности успешной доставки блока (а) и коэффициента потерь (b) от допустимого числа переспросов при задержке квитанции на один слот Литература

1. Мелентьев О.Г. Шевнина И.Е. Оценка эффективности управления хоппингом при передаче по каналам с группирующимися ошибками. Вестник СибГУТИ, 2008, № 2, C. 28-30.

2. Мелентьев О.Г. Шевнина И.Е. Оценка алгоритмов выбора логического канала с учтом приоритетов. Электросвязь.– 2010. -№ 2 С.50-52

3. Коричнв Л.П., Королв В.Д. Статистический контроль каналов связи.–М.: Радио и связь, 1989. 240 с.

4. Мелентьев О.Г. Теоретические аспекты передачи данных по каналам с группирующимися ошибками /под редакцией профессора В.П. Шувалова – М.: Горячая линия –Телеком, 2007. –232с.:ил.

5. Шевнина И.Е. Прогнозирование качества прима слота по результатам предыдущих попыток в каналах с группирующимися ошибками. – Материалы X международной конференции «Проблемы функционирования информационных сетей», 2008. – С. 143-145.

Использование хоппинга для уменьшения потерь блоков с ограниченным числом переспросов 69

–  –  –

Мелентьев Олег Геннадьевич д.т.н., профессор кафедры передачи дискретных сообщений и метрологии СибГУТИ, декан факультета автоматической электросвязи (630102, Новосибирск, ул. Кирова, 86) тел. (383) 2-698-240, e-mail: melog@sibsutis.ru Шевнина Ирина Евгеньевна Доцент кафедры передачи дискретных сообщений и метрологии СибГУТИ, заместитель декана факультета автоматической электросвязи (630102, Новосибирск, ул. Кирова, 86) тел. (383) 2-698-244, e-mail: pdsm@yandex.ru Managed Hopping Usage for BER Decreasing with Constraint of Repeat Request Numbers O. G. Melentyev, I.E.Shevnina In this paper, we consider a task of data transmission over a few dedicated channels with bursty errors. Moreover, we introduce a time constraint for one data block delivery.

We propose two algorithms of hopping management that make it possible to decrease Block Error Rate (BER). A comparison of suggested algorithms with ideal managed hopping algorithm and no hopping algorithm was made.

Похожие работы:

«В данном сборнике представлены инструкции на модели радиостанций: Модель Страница Аргут А-23 New 4 Аргут А-24 11 Аргут А-24 New 20 Аргут А-41 32 Аргут А-41 New 51 Аргут А-43 71 Аргут А-44 75 Аргут А-45 91 Аргут А-53 109 Аргут А-54 114 Аргут А-75 132 Спасибо! Благодарим...»

«Проведение 27.12.2014г. Составитель: Пенькова Е.А., Декорации: 1) оформление сцены к 3 спектаклям 2) костюмы участников 3) выставка с книгами 4) афоризмы писателей Цели литературного вечера: расширить и закрепить знания учащихся по творчеству А. П. Чехова; раскрыть актерский потен...»

«Информационная графика облегчает восприятие информации путем объединения элементов в целое. Она не только предоставляет критерии для такого объединения, но и задает вектор экспертного мышления (например, оценка тенденций, выявление аналогий, сравнение по различному...»

«МИНИСТЕРСТВО ОБОРОНЫ РОССИЙСКОЙ ФЕДЕРАЦИИ КОНЦЕПТУАЛЬНЫЕ ВЗГЛЯДЫ НА ДЕЯТЕЛЬНОСТЬ ВООРУЖЕННЫХ СИЛ РОССИЙСКОЙ ФЕДЕРАЦИИ В ИНФОРМАЦИОННОМ ПРОСТРАНСТВЕ 2011 г. Концептуальные взгляды на деятельность Вооруженных Сил Российской Федерации в информационном пространстве СОДЕРЖАНИЕ Введение.. 3 Ос...»

«СОДЕРЖАНИЕ От Издательского центра.. 4 Размышления. Поиски. Мнения Система УМК "Начальная школа XXI века" как фактор повышения качества начального образования Е.А. Менчинская.. 6 Система УМК "Начальная школа XXI века" в образовательном процессе начальной школы Е.М. Т...»

«Республика Татарстан Министерство лесного хозяйства Республики Татарстан ЛЕСОХОЗЯЙСТВЕННЫЙ РЕГЛАМЕНТ Арского лесничества Казань, 2013 г. ОГЛАВЛЕНИЕ ВВЕДЕНИЕ Законодательные акты Российской Федерации Информационная база для составления лесохозяйственного регламента ГЛАВА 1. ОБЩИЕ СВЕДЕНИЯ 1.1. Кратка...»

«Х977 г. Сентябрь Том 123, вып. 1 УСПЕХИ ФИЗИЧЕСКИХ НАУК 539,171 РАССЕЯНИЕ НАЗАД ПИОНОВ НА НУКЛОНАХ В. А. Любимов СОДЕРЖАНИЕ 1. Начало исследования пион-нуклонного рассеяния назад. Рассеяние в "резонансной" области энергий 3 2. Рассеяние пионов на нуклонах назад в "послерезонансной" промежуточной...»

«SF-2200-woLable.doc AWARENESS Technology, Inc. StatFax 2200 Микропланшетный инкубатор/шейкер Руководство пользователя Содержание Раздел Страница 1. Введение и представление 2. Установка 3. Требования по питанию 4. Получение сведений по...»








 
2017 www.kniga.lib-i.ru - «Бесплатная электронная библиотека - онлайн материалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.