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

На правах рукописи

Чупахина Лилия Равилевна

АНАЛИЗ ХАРАКТЕРИСТИК СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ ПРИ ПЕРЕДАЧЕ НЕПУАССОНОВСКОГО ТРАФИКА МЕТОДОМ АППРОКСИМАЦИИ ФУНКЦИЙ РАСПРЕДЕЛЕНИЯ

Специальность 05.12.13 — Системы, сети и устройства телекоммуникаций

1 г ДЕК 2013

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

Самара-2013

005543905

005543905

Работа выполнена в Федеральном государственном образовательном бюджетном учреждении высшего профессионального образования «Поволжский государственный университет телекоммуникаций и информатики» (ФГОБУ ВПО ПГУТИ)

Научный кандидат технических наук, доцент

руководитель: Киреева Наталья Валерьевна

Официальные Тарасов Вениамин Николаевич

оппоненты: доктор технических наук, профессор, ФГОБУ ВПО

ПГУТИ, заведующий кафедрой программного обеспечения и управления в технических системах

Сухов Андрей Михайлович

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

Ведущая Федеральное государственное бюджетное

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

Защита состоится 23 декабря в 12-00 на заседании диссертационного совета Д 219.003.02 при Поволжском государственном университете телекоммуникаций и информатики по адресу: 443010, г. Самара, ул. Льва Толстого, 23.

С диссертацией можно ознакомиться в библиотеке ФГОБУ ВПО ПГУТИ. Автореферат разослан 22 ноября 2013 г.

Учёный секретарь

диссертационного совета Д219.003.02

доктор технических наук, профессор Мишин Д.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

Бурное развитие мультисервисных сетей связи (МСС), которые определенным образом характеризуют структуру и поведение пакетов в ней, рост объема передаваемой информации, привели к новом)' восприятию современной телекоммуникационной инфраструктуры. В связи с этим построение моделей МСС и их исследование от частного случая к общему, является актуальной задачей, и в настоящее время привлекают внимание многих исследователей.

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

В силу непуассоновского характера поведения реального трафика в качестве модели целесообразнее использовать СМО типа G/G/l (G/G/n), так как на практике, при исследовании реальных систем, редко бывают, известны законы распределения и обслуживания поступающего на вход системы трафика.

Существенный вклад в решение задач анализа и проектирования сетей внесли российские ученые Б. С. Цыбаков, В. И. Нейман, В. М. Вишневский, С. Н. Степанов, О. И. Шелухин, Г. П. Башарин, А. Е. Кучерявый,

К. Е. Самуйлов, Г. Г. Яновский и др., а также зарубежные ученые К. Park, W. Willinger, P. Abry, M. S. Taqqu, I. Norros и др. исследователи.

На данный момент анализ СМО типа G/G/1 не решен, с точки зрения того, чтобы можно было описать эту систему с помощью любого математического аппарата, либо любого другого программно-аппаратного комплекса для решения данной задачи.

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

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

Содержание диссертации соответствует пунктам 4 и 14 паспорта специальности 05.12.13 — «Исследование путей совершенствования управления информационными потоками», «Разработка методов исследования, моделирования и проектирования сетей, систем и устройств телекоммуникаций».

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

Для достижения поставленной цели в диссертационной работе были сформулированы и решены следующие основные задачи:

— исследование математических моделей, описывающих непуассоновский трафик МСС и не марковский характер обслуживания;

— использование методов аппроксимации для моделирования плотностей распределения вероятностей интервалов времени между поступлениями пакетов и распределения вероятностей длительностей обслуживания пакетов, с учетом самоподобных свойств процессов поступления и обслуживания;

— разработка метода аппроксимации функций плотностей распределения суммой затухающих экспонент;

— анализ функций распределений с «тяжелыми хвостами» (РТХ) для получения аппроксимирующих выражений в виде суммы затухающих экспонент;

— анализ статистических данных, собранных с реальной сети, построение моделей функций плотностей распределения интервалов времени между пакетами и длительности обслуживания пакетов;

— разработка алгоритма решения интегрального уравнения (ИУ) Линдли для СМО типа G/G/1 с помощью спектрального метода.

Методы исследования. Основные теоретические и экспериментальные исследования диссертационной работы выполнены с применением методов математического анализа, математической статистики, теории вероятностей, статистической обработки данных и вычислительных методов, реализованных в пакете Matlab и Matead.

Научная новизна исследований, проведенных в диссертации, состоит в следующем:

— разработан метод аппроксимации гиперэкспоненциальных функций плотности распределения вероятностей суммой затухающих экспонент для анализа входящего и обслуживаемого трафика МСС;

— получена аппроксимация функций плотности распределения вероятностей для реального входящего и обслуживаемого в узле МСС трафика;

— получено решение ИУ Линдли для СМО типа G/G/1 для гиперэкспоненциальных распределений.

Практическая ценность диссертации.

Полученный в данной работе метод решения ИУ Линдли позволяет использовать в качестве математической модели СМО типа G/G/1. На основе разработанных методов аппроксимации можно проанализировать работу СМО типа G/G/1 спектральным методом.

Результаты работы внедрены в ОАО «Концерн «Автоматика», в курсах «Основы теории массового обслуживания», «Сетевые технологии высокоскоростной передачи данных» ФГОБУ ВПО ПГУТИ, что подтверждается актами внедрения.

Основные положения и результаты, выносимые на защиту:

— последовательности интервалов времени между пакетами и длительностей пакетов для трафика МСС обладают свойством самоподобия и могут быть описаны РТХ;

— аппроксимацию распределений вероятностей характеристик реального трафика целесообразно проводить с использованием методов кумулянтного анализа;

— используемые РТХ могут быть аппроксимированы суммой затухающих экспонент, при условии, что коэффициенты аппроксимации должны быть вещественными и отрицательными при положительных значениях аргумента;

— для решения ИУ Линдли при применении предложенных методов аппроксимации может быть использован алгоритмически простой спектральный метод.

Личный вклад автора. Все основные научные результаты, теоретических и прикладных исследований, выводы, изложенные в

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

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

Внедрение результатов работы. Результаты диссертационной работы внедрены в ОАО «Концерн «Автоматика» г. Москва и в учебный процесс кафедры «Мультисервисных сетей и информационной безопасности» ФГОБУ ВПО ПГУТИ, что подтверждено актами внедрения.

Апробация работы. Основные научные и практические результаты диссертации докладывались и обсуждались на 7-й Отраслевой научно-технической конференции-форуме «Технологии информационного общества», (г. Москва, 2013), на XII, XIII Международной научно-технической конференции «Проблемы техники и технологий телекоммуникаций» (г. Уфа, 2010, г. Казань, 2011), на 14-й и 15-й Международной Конференции «Цифровая обработка сигналов и ее применение» (г. Москва, 2012 - 2013 гг.), на XXXIX Международной научно-практической конференции «Физико-математические и технические науки как постиндустриальный фундамент эволюции информационного общества», (г. Лондон, 2013), на X Международная научно-техническая конференция «Физика и технические приложения волновых процессов» (г. Самара, 2011), на Международной научно-практической Интернет-конференции «Современные направления теоретических и прикладных исследований'2013», (г. Одесса, 2013), на Международной научно-практической Интернет-конференции «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании'2013», (г. Одесса, 2013), на Всероссийской научно-практической конференции «Проблемы передачи информации в инфокоммуникационных системах» (г. Волгоград, 2013), на Первой Международной научно-практической конференции «Проблемы инфокоммуникаций. Наука и технологии» (Р1С8&Т-2013) (г. Харьков, 2013), на XVII, XVIII, XIX, XX Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов (ФГОБУ ВПО ПГУТИ, г. Самара, 2010 -2013 гг.).

Публикации результатов. По результатам исследования опубликовано 18 печатных работ, 4 из них в изданиях из перечня ВАК, 9 публикаций международных научных конференций, 5 тезисов докладов.

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

содержит 134 страниц машинописного текста, 100 рисунков, 23 таблицы. В списке литературы 113 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассмотрены основные понятия и характеристики качества обслуживания МСС, дается краткий обзор СМО, их структура и классификация, дисциплины обслуживания, математические модели, основные свойства потока событий. При анализе МСС рассматривается подход от одной системы к целой совокупности систем, что, во-первых, упрощает громоздкость вычислений, а во-вторых, позволяет расширить и более детально изучить происходящие процессы в канале передачи. Рассматривая на входе сетевого устройства поток информации, закон распределения которого подчиняется функциям РТХ, можно смоделировать модель, адекватно описывающую работу любого сетевого элемента, обрабатывающего самоподобный трафик. Для определения параметров МСС, таких как интенсивности поступления и обслуживания пакетов, среднее время ожидания пакетов в очереди и др., можно использовать классическую теорию телетрафика, с учетом существующих требований к качеству и скорости передачи.

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

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

Представлен первый способ аппроксимации — кумулянтный анализ произвольной функции плотности распределения вероятностей. Вычисления проводились для РТХ Вейбулла, логнормального, Парето, а также реального трафика МСС. Возможность определения через кумулянты функции плотности распределения вероятностей, позволяет получить ее

аппроксимирующее выражение и построить график. Результат аппроксимации представляется в виде ряда Эджворта (1).

Решение данной задачи представлено в виде алгоритма нахождения неизвестных функций плотностей распределения вероятностей поступления пакетов УУ(т) и обслуживания пакетов Ж(^). На рис. 1 представлена блок-

схема реализации, где БВМ

1 1

2 а

БВМ ..JL* БВК * БА

олок вычисления значении моментов т, ,

к 7

БВК - блок вычисления значений " кумулянтов х ■■ БА — блок анализа и

Рис. 1

определения вида закона плотностей распределения W(t) и W(^). Используя данную блок-схему, реализуется алгоритм аппроксимации неизвестной функции плотности распределения вероятностей с помощью кумулянтов в общем виде W(x) (1) (W(x) = W(t) или W(£) ).

Результат аппроксимации функции распределения Вейбулла /(х) (2) при параметрах а = 0,8 и /0 = 0,4 представлены в виде графиков на рис. 2а.

г k ßk

W О) = Wf(:с) + I (-1) —-W]

(к)

(х)

к!

-« «-1 /(х) = а(5 х* е ^

График погрешности приближенного значения К(х)

плотности распределения Вейбулла представлен на рис. 26.

(1) (2)

функции

а б

Рис. 2

После анализа результатов аппроксимации для функций РТХ, которые подтверждают возможность использования данного метода с минимальными значениями погрешностей, исследованы характеристики реального трафика МСС. С помощью программы-снифера \\%е8Ьагк сняты статистические данные потока, поступающего на вход сетевого интерфейса. Схема регистрации графика представлена на рис.3.

<Ъ1

Рис. 3

Реализации последовательностей интервалов времени между пакетами и длительностей обслуживания пакетов представлены на рис. 4.

В

I !

™(0

Рис. 4

Применяя кумулянтный анализ для выборки произвольных величин длительности обслуживания £., где г =1,...,3 176, вычисляем ряд Эджворта

по алгоритму (рис. 1). Как видно из графика на рис. 5, функция плотности

распределения вероятностей длительности обслуживания пакетов IV (£) реального трафика лучше описывается РТХ. Таким образом, полученные аппроксимирующие выражения для функций плотностей РТХ с помощью кумулянтов, позволяют сравнить их с известными значениями, а для реального трафика получить представление функции плотности распределения вероятностей на выходе обрабатывающего устройства. В качестве второго способа аппроксимации неизвестной функции плотности распределения для СМО типа О/С/1 рассмотрен метод Прони. При реализации алгоритма по методу Прони точность аппроксимации зависит от количества выбранных на начальном этапе отсчетов N функции /(х), которую необходимо интерполировать. В диссертационной работе рассмотрены частные случаи для гиперэкспоненциальных распределений. Исследование показало, что аппроксимация функций РТХ с помощью кумулянтного метода

Рис. 5

удовлетворительна, а с помощью метода Прони имеет ограничения при реализации алгоритма.

В третьей главе описывается разработанный метод аппроксимации функций плотности распределения вероятностей суммой затухающих экспонент. Рассматривается реализация данного алгоритма на примере РТХ и реального трафика.

Пусть достаточно гладкая функция /(х) задана на промежутке [а, 6] . Требуется построить ее аппроксимацию вида

и оценить погрешность х) .

Для аппроксимации заданной плотности распределения /(х) суммами экспонент в случае [я, ¿>] = [0,1] необходимо:

1. Задать количество узлов интерполирования и значение параметра

т > 0.

2. Определить узлы интерполирования ук вспомогательной функции Я(У) =/(~т\пу).

3. Вычислить коэффициенты рк, решая систему линейных

алгебраических уравнений.

4. Записать аппроксимирующую функцию в виде формулы (3). Замечание 1. В случае произвольного промежутка [а, 6], как

отмечалось выше, достаточно применить приведенный алгоритм к функции /(х= /(<з + (Ь - а)х') , где х' е [0,1 ], а затем вернуться к исходной переменной х = а + (Ь — а)х'.

Замечание 2. Значение параметра т определяется экспериментально для каждой аппроксимируемой функции /(х) .

Данный алгоритм реализован для аппроксимации функции плотности логнормального распределения /(х) (4) с параметрами ¿¿=0 и <г = 1,5, при

количестве узлов интерполирования п = 5 .

/О) = Z Рке"кХ + ЯМ, <*к > 0

(3)

е

L 2 2

\\2я(Т х

(4)

Аналитическое выражение аппроксимирующей функции имеет вид

х

/„р00 = Z РкеакХ = Р,е + р2е + ... + р5е " ,m = 1,15. (5)

Результат аппроксимации представлен в виде графика рис. 6а. График погрешности приближенного значения R(x) плотности логнормального распределения представлен на рис. 66.

При логнормальном распределении возможны осцилляции в окрестности точки 0, однако полученный результат интерполирования позволяет сделать вывод о точности приближенных значений. Из графика рис. 5б видно, что погрешность отклонения R(x) = 0, 03.

R»

Рис.6

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

Рассмотрен алгоритм аппроксимации функции плотности распределения вероятностей реального трафика для интервалов времени между пакетами т . Аналогично, как и в кумулянтном анализе, выбираем статистические данные потока (выборку), поступающую на вход сетевого элемента. Для выборки

величин длительности поступления т., где i — моменты поступления пакетов, = 1,..., 116 424, строим гистограмму значений произвольного распределения

(рис. 7). Используя программный ' продукт EasyFit Professional

(EasyFit), определили, что

искомой функции плотности распределения интервалов

Щ \ времени между пакетами

с' __________________________ соответствует функция плотности

8 " 04 00 ** 1 " м распределения Берра (Burr) (6).

Для лучшей аппроксимации Рис. 7 плотности распределения Берра

(Burr) выбрано количество узлов интерполирования п = 5 .

Согласно алгоритму аппроксимации суммой затухающих экспонент получено аппроксимирующее выражение (7) и построена графическая

е.-

/¡™».ш<и(Н>

«:•-!>,0733»

7 «О

Алгоритм решения ИУ Линдли СМО типа G/G/1 спектральным методом:

1. Найти аппроксимирующие выражения, согласно алгоритму аппроксимации суммой экспонент, для функций плотности интенсивности поступления а(т) и интенсивности обслуживания пакетов Ь{£,) , и представить

их в виде (3). Определить узлы интерполирования у вспомогательной функции g(y) = f {—m In у) используя формулу нулей полиномов Чебышева

Ь+а Ь-а {л{2к—Х))

у. =--1--cos-.

к 2 2 In

Интервал аппроксимации рассматривать такой, чтобы он захватывал область существования искомых функций плотностей а(т) и .

2. Найти их прямое преобразование Лапласа A(—s) и B(s) для функций в виде (3).

3. Вычислить A(-s) ■ B(s) - 1 = ^ + ^ . Найти все корни получившегося

(//_ (s)

многочлена, и в зависимости от условий записать у/ (s) и \¡/ (s).

4. Вычислить постоянную К и определить выражение для преобразования Лапласа функции распределения времени ожидания Ф (s) .

5. Вычислить обратное преобразование Лапласа W (s),

(W (s) = j<J>+(,y)) , и, интегрируя его, получить функцию W(y) .

В диссертационной работе рассмотрено вычисление функции IV(у) по вышеизложенному алгоритму на примере РТХ.

Пусть а(т) - функция плотности распределения интенсивности поступления пакетов ( ег = 1,5, ц = 0 ) имеет логнормальное распределение, a b{Ç) - функция плотности распределения интенсивности обслуживания пакетов (« = 0,8, /? = 0,4) в СМО типа G/G/1 имеет распределение Вейбулла.

Согласно спектральному методу реализуем для данного случая алгоритм решения ИУ Линдли. Вычисление проводим при количестве узлов интерполирования п = 5. Соответственно, получаем выражение и графики зависимости для функции распределения времени ожидания W{y) (8) в СМО THnaG/G/l при п = 5 (рис.9).

W(y) = 1+0, W¿XX5y sin(0,64у) - 0,093с"3,15-'' cos(0, (Ay) - (8)

-1,04 у -6 96« -6,96v

—0,295 е + 0,048е cos(l,47_y) + 0,11 le sin(l, 47j>).

3. Чупахина, Л.Р. Исследование самоподобного трафика в мультисервисной сети / Н.В. Киреева, Л.Р. Чупахина // Т-Сотт - Телекоммуникации и Транспорт. -2013,-№8.-С. 88-89.

4. Чупахина, Л.Р. Метод аппроксимации произвольной плотности распределения суммами экспонент / И.А. Блатов, В.Г. Карташевский, Н.В Киреева, Л.Р. Чупахина// Вестник ВГУ. -2013. -№2. - С. 53-57.

Публикации в других изданиях

5. Гарипова, Л.Р. Особенности обслуживания одноадресного и многоадресного потоков в звене мультисервисной сети / Н.В. Киреева, Л.Р. Гарипова // Материалы X Международ, науч.-техн. конф. Физика и технические приложения волновых процессов. — Самара, 2011. — С. 333-334.

6. Гарипова, Л.Р. Исследование звена мультисервисной сети с повторными вызовами на основе системы М/М/1/ Н.В. Киреева, Л.Р. Гарипова // Материалы XVII Российской науч. конф. ППС, НС и аспирантов. - Самара: ПГУТИ, 2010. — С. 50.

7. Гарипова, Л.Р. Частные случаи модели мультисервисной сети с повторными вызовами / Н.В. Киреева, Л.Р. Гарипова // Материалы XVIII Российской науч. конф. ППС, НС и аспирантов. - Самара: ПГУТИ, 2011. - С. 57-58.

8. Гарипова, Л.Р. Анализ характеристик в случаях обслуживания одноадресных и многоадресных соединений / Н.В. Киреева, Л.Р. Гарипова // Проблемы техники и технологии телекоммуникаций : тр. XII Междунар. научно-техн. конф. — Казань,

2011.-С. 183-184.

9. Гарипова, Л.Р. Аппроксимация характеристик системы С/С/1 через кумулянты / Н.В. Киреева, ЛР. Гарипова // Материалы XIX Российской науч. конф. ППС, НС и аспирантов. — Самара: ПГУТИ, 2012. — С. 47.

10. Чупахина, Л.Р. Исследование плотности распределения через разложение в ряд Эджворта / Н.В. Киреева, Л.Р. Чупахина // Материалы XX Российской науч. конф. ППС, НС и аспирантов. - Самара: ПГУТИ, 2013. - С. 49.

11. Чупахина, Л.Р. Исследование характеристик сетевого трафика / Н.В. Киреева, Л.Р. Чупахина // Сбор. науч. тр. 8\УогИ. Материалы междунар. научно-пракг. Интернет-конференции «Современные направления теоретических и прикладных исследований'2013», — Одесса, 2013. -вып. 1,Т.5. — С. 19-20.

12. Гарипова, Л.Р. Кумулянтный подход к исследованию системы 0/0/1 / Н.В. Киреева, ЛР. Гарипова // Тр. 14-ой Междунар. конф. и «Цифровая обработка сигналов и ее применеиие». — Москва, 2012. — вып. XVI, Т. 2. — С. 503-504.

13. Чупахина, Л.Р. Оценка вероятностных характеристик мультисервисной сети с помощью кумулянтов / Н.В. Киреева, Л.Р. Чупахина // Проблемы техники и технологии телекоммуникаций : тр. XIII Междунар. научно-техн. конф. — Уфа,

2012.-С. 41-43.

14. Чупахина, Л.Р. Аппроксимация функций плотности распределения с «тяжелыми» хвостами» / Н.В. Киреева, Л.Р. Чупахина // Тр. 15-ой Междунар. конф. «Цифровая обработка сигналов и ее применение». — Москва, 2013. — вып. XVI, Т. 2.-С. 74-77.

15. Чупахина, Л.Р. Исследование системы GZGZ1 с помощью метода Про™ Z Н.В. Киреева, Л.Р. Чупахина ZZ Сбор. докл. и тез. Всеросс. научно-практ. конф. «Проблемы передачи информации в инфокоммуникационных системах». -Волгоград, 2013. - С. 41-44.

16. Чупахина, Л.Р. Моделирование произвольной функции плотности распределения суммой экспонент Z Н.В. Киреева, Л.Р. Чупахина ZZ Сбор. науч. тр. SWorld мсждунар. научно-практ. Интернет-конференции «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании'2013», -Одесса, 2013. - вып. 2, Т. 8. - С. 21-22.

17. Chupakhina, L.R. Approximation of the density function of the Weibull distribution using analysis cumulant Z N. V. Kireeva, L.R. Chupakhina ZZ XXXIX International Research and Practice Conference «Physico-mathematical and technical sciences as postindustrial foundation of the informational society evolution». - London, 2013. — P. 48-49.

18. Чупахина, Л.Р. Аппроксимация плотности распределения Парето суммой затухающих экспонент Z И.А. Блатов, В.Г. Карташевский, Н.В Киреева, Л.Р. Чупахина ZZ Сбор. науч. тр. Первой Междунар. научно-практ. конф. «Проблемы инфокоммуникаций. Наука и технологии» (PICS&T-2013) - Харьков, 2013. — С. 132-134.

* — Гарипова Л.Р. сменила фамилию на Чупахина Л.Р. 29.06.2012 г.

Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования "Поволжский государственный университет телекоммуникаций и информатики" 443010, г. Самара, ул. Льва Толстого 23

Подписано в печать 17.11.13 г. Формат 60 x84Z 16 Бумага офсетная№1. Гарнитура Тайме. Заказ 1636. Печать оперативная. Усл. печ. л. 0,91. Тираж 100 экз.

Отпечатано в издательстве учебной и научной литературы Поволжского государственного университета телекоммуникаций и информатики 443090, г. Самара, Московское шоссе 77, т. (846) 228-00-44

ч

Федеральное агентство связи

Федеральное государственное образовательное бюджетное учреждение высшего

профессионального образования ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ

На правах рукописи

Чупахина Лилия Равилевна

АНАЛИЗ ХАРАКТЕРИСТИК СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ ПРИ ПЕРЕДАЧЕ НЕПУАССОНОВСКОГО ТРАФИКА МЕТОДОМ АППРОКСИМАЦИИ ФУНКЦИЙ

РАСПРЕДЕЛЕНИЯ

Специальность 05.12.13 - Системы, сети и устройства телекоммуникаций

Диссертация на соискание учёной степени кандидата технических наук

Научный руководитель: Кандидат технических наук, доцент Киреева Н.В.

Самара - 2013

СОДЕРЖАНИЕ

Перечень сокращений................................................................................................................................4

Введение....................................................................................................................................................................6

Глава 1. Мультисервисные сети, основные понятия..............................................................12

1.1. Общая характеристика системы массового обслуживания....................15

1.2. Структура и классификации систем массового обслуживания................16

1.3. Поток событий. Простейший поток и его свойства..........................................19

1.4. Дисциплина обслуживания......................................................................................................20

1.5. Модели систем массового обслуживания....................................................................20

1.5.1 Простейшие случаи систем массового обслуживания..........................22

1.6. Аппроксимация функций распределений, методы аппроксимации.. 26 Выводы по главе 1......................................................................................................................................30

Глава 2. Исследование функций плотности распределения

вероятностей........................................................................................................................................................32

2.1 Кумулянтный анализ........................................................................................................................35

2.1.1 Аппроксимация функций плотности распределения

вероятностей с помощью ряда Эджворта..............................................................................37

2.2 Метод Прони........................................................................................................................................56

2.2.1 Алгоритм аппроксимации функции плотности распределения

с помощью метода Прони............................................................................................................................58

Выводы по главе 2....................................................................................................................................66

Глава 3. Аппроксимация функций распределения вероятностей........................68

3.1. Метод аппроксимации функции плотности распределения вероятностей с «тяжелым» хвостом суммами экспонент............................................68

3.1.1 Алгоритм аппроксимации функции плотности распределения

вероятностей суммами экспонент................................................................................................70

3.2. Метод аппроксимации произвольной функции плотности

распределения вероятностей суммами экспонент........................................................81

Выводы по главе 3......................................................................................................................................99

Глава 4. Интегральное уравнение Линдли....................................................................................101

4.1 Решение интегрального уравнения Линдли..............................................................103

4.2 Решение интегрального уравнения Линдли для системы массового обслуживания типа G/G/1......................................................................................................................107

4.3 Решение интегрального уравнения Линдли для системы массового

обслуживания типа G/G/1 для частных случаев..............................................................109

Выводы по главе 4......................................................................................................................................119

Заключение................................................................................................................................................................120

Список использованных источников..................................................................................................121

Акты внедрения......................................................................................................................................................133

Перечень основных сокращений

ИУ - интегральное уравнение

МНК - метод наименьших квадратов

МСС - мультисервисная сеть связи

ОУ - обрабатывающее устройство

РТХ - распределение с «тяжелыми хвостами»

СЛАУ - система линейных алгебраических уравнений

СМО - система массового обслуживания

ТМО - теория массового обслуживания

FIFO (first-in, first-out) - алгоритм обработки очередей - «первый пришёл -первый вышел»

G/G/1 - СМО с одной обслуживающей линией, произвольным входящим потоком, произвольным распределением времени обслуживания

G/G/n - СМО с п обслуживающими линиями, интервалы времени между пакетами распределены произвольно, произвольным распределением времени обслуживания

G/M/1 - СМО с одной обслуживающей линией, интервалы времени между пакетами распределены произвольно, время обслуживания распределено экспоненциально

GOF (Goodness of fit) - критерий согласия

IPTV (Internet Protocol Television) - интерактивное телевидение LIFO (last-in, first-out) - алгоритм обработки очередей - «последний пришёл —первый вышел»

M/D/1 - СМО с одной обслуживающей линией, пуассоновским входящим потоком, детерминированным распределением времени обслуживания

M/G/1 - СМО с одной обслуживающей линией, пуассоновским входящим потоком, произвольным распределением времени обслуживания

M/M/l - СМО с одной обслуживающей линией, пуассоновским входящим потоком, экспоненциальным распределением времени обслуживания

MLE (maximum-likelihood estimation) - Метод максимального правдоподобия

NGN (Next Generation Network ) - сети следующего поколения

QoS (Quality of Service) - качество обслуживания

Введение

Современные телекоммуникационные системы характеризуются значительной сложностью происходящих в них процессов. Марковская классическая модель системы массового обслуживания (СМО) [11, 40, 41, 87] не может полностью описать параметры современных телекоммуникационных систем, что в свою очередь порождает серьезную недооценку реальной нагрузки и значительное ухудшению качества обслуживания (С^оБ) при реализации услуг разного вида. Стандартные методы моделирования СМО для анализа и прогнозирования процессов, происходящих в обслуживающем устройстве, зачастую приводят к неудовлетворительным оценкам результатов его работы. Следовательно, непуассоновский характер трафика современной телекоммуникационной системы требует применения новых математических методов его исследования.

Бурное развитие мультисервисных сетей связи (МСС), которые определенным образом характеризуют структуру и поведение пакетов в ней, рост объема передаваемой информации, привели к новому восприятию современной телекоммуникационной инфраструктуры. В связи с этим построение моделей МСС и их исследование от частного случая к общему, является актуальной задачей, и в настоящее время привлекают внимание многих исследователей [4, 5, 6, 28, 43, 49, 90, 97, 102, 106, 108, 110].

В последнее время все больше исследований посвящается вопросу анализа непуассоновского трафика МСС, обладающего самоподобием [37, 40, 51, 54, 73, 103]. Математическая теория самоподобных процессов изучена довольно хорошо, однако практическая реализация все еще оставляет ряд нерешенных вопросов, особенно при передаче информационного потока в МСС. Существует большое количество исследований, посвященных имитационному моделированию работы сетевого устройства при передаче самоподобного потока. Однако теоретическая база процесса передачи

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

В силу непуассоновского характера поведения реального трафика в качестве модели целесообразнее использовать СМО типа G/G/l (G/G/n), так как на практике, при исследовании реальных систем, редко бывают, известны законы распределения и обслуживания поступающего на вход системы трафика.

Существенный вклад в решение задач анализа и проектирования сетей внесли российские ученые Б. С. Цыбаков, В. И. Нейман, В. М. Вишневский, С. Н. Степанов, О. И. Шелухин, Г. П. Башарин, А. Е. Кучерявый, К. Е. Самуйлов, Г. Г. Яновский и др., а также зарубежные ученые К. Park, W. Willinger, P. Abry, M. S. Taqqu, I. Norros и др. исследователи.

На данный момент анализ СМО типа G/G/1 не решен, с точки зрения того, чтобы можно было описать эту систему с помощью любого математического аппарата, либо любого другого программно-аппаратного комплекса для решения данной задачи.

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

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

Содержание диссертации соответствует пунктам 4 и 14 паспорта специальности 05.12.13 - «Исследование путей совершенствования управления информационными потоками», «Разработка методов исследования, моделирования и проектирования сетей, систем и устройств телекоммуникаций».

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

Для достижения поставленной цели в диссертационной работе были сформулированы и решены следующие основные задачи:

— исследование математических моделей, описывающих непуассоновский трафик МСС и не марковский характер обслуживания;

— использование методов аппроксимации для моделирования плотностей распределения вероятностей интервалов времени между поступлениями пакетов и распределения вероятностей длительностей обслуживания пакетов, с учетом самоподобных свойств процессов поступления и обслуживания;

— разработка метода аппроксимации функций плотностей распределения суммой затухающих экспонент;

— анализ функций распределений с «тяжелыми хвостами» (РТХ) для получения аппроксимирующих выражений в виде суммы затухающих экспонент;

— анализ статистических данных, собранных с реальной сети, построение моделей функций плотностей распределения интервалов времени между пакетами и длительности обслуживания пакетов;

— разработка алгоритма решения интегрального уравнения (ИУ) Линдли для СМО типа вЛл/! с помощью спектрального метода.

Методы исследования. Основные теоретические и экспериментальные исследования диссертационной работы выполнены с применением методов математического анализа, математической статистики, теории вероятностей, статистической обработки данных и вычислительных методов, реализованных в пакете Matlab и Matead.

Научная новизна исследований, проведенных в диссертации, состоит в следующем:

— разработан метод аппроксимации гиперэкспоненциальных функций плотности распределения вероятностей суммой затухающих экспонент для анализа входящего и обслуживаемого трафика МСС;

— получена аппроксимация функций плотности распределения вероятностей для реального входящего и обслуживаемого в узле МСС трафика;

— получено решение ИУ Линдли для СМО типа G/G/1 для гиперэкспоненциальных распределений.

Практическая ценность диссертации.

Полученный в данной работе метод решения ИУ Линдли позволяет использовать в качестве математической модели СМО типа G/G/1. На основе разработанных методов аппроксимации можно проанализировать работу СМО типа G/G/1 спектральным методом.

Результаты работы внедрены в ОАО «Концерн «Автоматика», в курсах «Основы теории массового обслуживания», «Сетевые технологии высокоскоростной передачи данных» ФГОБУ ВПО ПГУТИ, что подтверждается актами внедрения.

Основные положения и результаты, выносимые на защиту:

— последовательности интервалов времени между пакетами и длительностей пакетов для трафика МСС обладают свойством самоподобия и могут быть описаны РТХ;

— аппроксимацию распределений вероятностей характеристик реального трафика целесообразно проводить с использованием методов кумулянтного анализа;

— используемые РТХ могут быть аппроксимированы суммой затухающих экспонент, при условии, что коэффициенты аппроксимации должны быть вещественными и отрицательными при положительных значениях аргумента;

— для решения ИУ Линдли при применении предложенных методов аппроксимации может быть использован алгоритмически простой спектральный метод.

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

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

Внедрение результатов работы. Результаты диссертационной работы внедрены в ОАО «Концерн «Автоматика» г. Москва и в учебный процесс кафедры «Мультисервисных сетей и информационной безопасности» ФГОБУ ВПО ПГУТИ, что подтверждено актами внедрения.

Апробация работы. Основные научные и практические результаты диссертации докладывались и обсуждались на 7-й Отраслевой научно-технической конференции-форуме «Технологии информационного общества», (г. Москва, 2013), на XII, XIII Международной научно-

технической конференции «Проблемы техники и технологий телекоммуникаций» (г. Уфа, 2010, г. Казань, 2011), на 14-й и 15-й Международной Конференции «Цифровая обработка сигналов и ее применение» (г. Москва, 2012-2013 гг.), на XXXIX Международной научно-практической конференции «Физико-математические и технические науки как постиндустриальный фундамент эволюции информационного общества», (г. Лондон, 2013), на X Международная научно-техническая конференция «Физика и технические приложения волновых процессов» (г. Самара, 2011), на Международной научно-практической Интернет-конференции «Современные направления теоретических и прикладных исследований'2013», (г. Одесса, 2013), на Международной научно-практической Интернет-конференции «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании'2013», (г. Одесса, 2013), на Всероссийской научно-практической конференции «Проблемы передачи информации в инфокоммуникационных системах» (г. Волгоград, 2013), на Первой Международной научно-практической конференции «Проблемы инфокоммуникаций. Наука и технологии» (Р1С8&Т-2013) (г. Харьков, 2013), на XVII, XVIII, XIX, XX Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов (ФГОБУ ВПО ПГУТИ, г. Самара, 2010-2013 гг.).

Публикации результатов. По результатам исследования опубликовано 18 печатных работ, 4 из них в изданиях из перечня ВАК, 9 публикаций международных научных конференций, 5 тезисов докладов.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 134 страниц машинописного текста, 100 рисунков, 23 таблицы. В списке литературы 113 наименований.

Глава 1. Мультисервисные сети, основные понятия

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

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

мсс.

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

Основные услуги, предоставляемые МСС:

— передача традиционного телефонного трафика;

— передача трафика данных (например, данных Интернет);

— передача трафика данных корпоративной сети;

— передача трафика мобильных сетей;

— доступ в Интернет;

— доступ к сетям передачи данных.

Одним из математических методов исследования сложных телекоммуникационных систем является ТМО, занимающаяся анализом эффективности функционирования СМО [82].

Система массового обслуживания - динамическая система, предназначенная для эффективного обслуживания случайного потока заявок при ограниченных �