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

brief description

Милованова, Татьяна Александровна. Анализ показателей эффективности функционирования телекоммуникационных систем с вероятностным приоритетом обслуживания и пороговым управлением нагрузкой : диссертация ... кандидата физико-математических наук : 05.13.17 / Милованова Татьяна Александровна; [Место защиты: Рос. ун-т дружбы народов].- Москва, 2013.- 135 с.: ил. РГБ ОД, 61 13-1/464

Милованова Татьяна Александровна Анализ показателей эффективности функционирования телекоммуникационных систем с вероятностным приоритетом обслуживания и пороговым управлением нагрузкой
05.13.17 — теоретические основы информатики
Диссертация на соискание ученой степени кандидата физико-математических наук
Научный руководитель: доктор физико-математических наук, профессор Печинкин А.В.
Москва — 2013
Содержание
Введение 4
1. Система BMAP/G/1/оо с инверсионной вероятностной дис¬циплиной обслуживания 13
1.1. Описание системы 13
1.2. Стационарное распределение очереди 17
1.3. Стационарное распределение времени ожидания и пребыва¬ния заявки в системе 26
2. Система BMAP/G/1/r, г < оо, с инверсионной вероятност-
' ной дисциплиной обслуживания 32
2.1. Описание системы 32
2.2. Стационарное распределение очереди 35
2.3. Стационарные вероятности потери и недообслуживания за¬явки 45
2.4. Стационарные распределение времени ожидания и пребыва¬ния заявки в системе 52
2.5. Численный результат 58
3. Система M/G/1/r, г < оо, с инверсионной вероятностной дисциплиной обслуживания и гистерезисной политикой 62
3.1. Описание системы 62
3.2. Стационарное распределение очереди 63
3.3. Стационарное распределение времени пребывания заявки в системе 73
3.4. Накопитель конечной ёмкости 80
3.-5. Численный результат 86
Заключение 89
Список литературы 91
Введение
Современные телекоммуникационные сети являются результатом длитель¬ного развития ряда основополагающих технологий — информационных, компьютерных, телекоммуникационных и других. Общей целью такого развития является информатизация общества, т.е. формирование единой информационной среды, охватывающей все сферы деятельности челове¬ка. Выполнение этой задачи подразумевает развитие целой индустрии по производству, хранению, передаче и обработке информации. Для разви¬тия современных систем передачи и обработки данных требуется создание адекватных аналитических моделей, учитывающих как характерные осо¬бенности систем передачи и обработки данных, так и новые механизмы обеспечения качества их функционирования.
Математические методы теории массового обслуживания (ТМО) (зна¬чительный вклад в развитие ТМО и теории телетрафика внесли и продол¬жают вносить А.Я. Хинчин. Б.В. Гнеденко, А.А. Боровков, Д. Кендалл, Д. Литтл, Д. Кокс, В. Смит, Л. Клейнрок, Б.А. Севастьянов, Л. Такач, Ф. Поллачек, П.П. Бочаров, Г.П. Башарин, В.М. Вишневский, А.Н. Дудин, В.А. Ивницкий, И.Н. Коваленко, В.А. Наумов, А.В. Печинкин, А.П. Пше¬ничников, К.Е. Самуйлов, С.Н. Степанов, И.И. Цитович и др.) позволя¬ют создавать стохастические модели протоколов систем передачи данных, обеспечивают возможность решения задач по управлению потоками дан¬ных, расчету показателей эффективности функционирования различных компонент телекоммуникационных систем, включая оценку вероятностно¬временных характеристик их узлов.
Телекоммуникационные системы третьего (3G) и четвертого (4G) по¬колений обеспечивают предоставление широкого класса услуг, таких как передача голосовой информации в режиме реального времени, аудио кон¬ференция, услуги мгновенных сообщений, высокоскоростного доступа в сеть Интернет и др. Для этого на каждом из уровней и участков сети (например, от базовой станции мобильного терминала и от базовой стан¬ции до контроллера радиосети) необходимы соответствующие механизмы и методы обработки и коммутации, обеспечивающие, в том числе, и каче¬ство передачи информации. Для этих целей необходимы адекватные ана¬литические модели, в частности, на основе систем массового обслужива¬ния (СМО) с групповым марковским входящим потоком (ВМАР-поток) и специальными дисциплинами обслуживания. Так, например, информаци¬онные потоки в сетях доступа UMTS (Universal Mobile Telecommunications System) с высокой степенью достоверности моделируются с помощью груп¬пового марковского потока. Кроме того, технология обеспечения качества соединений в сетях доступа (уровень AAL2/ATM) UMTS остается предме¬том дискуссий и исследований и в настоящее время, а, как давно замечено, использование в системах передачи специальных дисциплин обслужива-ния может значительно улучшить качество их функционирования, прак¬тически без каких либо усовершенствований. Рассмотренная в диссертации специальная дисциплина обслуживания — инверсионный порядок с веро¬ятностным приоритетом (далее — LCFS РР) — может рассматриваться как дополнительный механизм обеспечения эффективности функциониро¬вания систем. Вследствие развития телекоммуникационых услуг, в теле¬коммуникационных системах и, в том числе UMTS, возникают перегрузки. Это обстоятельство требует построения и исследования адекватных меха¬низмов управления перегрузками, в частности, гистерезисной стратегии, которая доказала свою эффективность для управления перегрузками в
традиционных телекоммуникационных системах с коммутацией каналов.
По проблематике диссертационного исследования написан ряд работ как теоретического [6], [8], [16]—[19], [22]—[24], [28]—[34], так и прикладно¬го характера [39], [47], [52], [54].
Диссертация продолжает и развивает работы в области исследования показателей эффективности функционирования телекоммуникационных систем третьего и четвертого поколений. В ней в более общих предполо¬жениях рассматривается дисциплина LCFS РР, что позволяет создавать аналитические модели, применимые для следующих целей:
— расчет показателей эффективности функционирования протоколов сетей доступа UMTS - общей задержки передачи и среднего числа пере¬данных сообщений;
— расчет вероятности сброса поступающего сообщения, распределе¬ния времени пребывания в системе принятого сообщения при реализации на основе дисциплины LCFS РР механизма управления очередью;
— анализ показателей эффективности телекоммуникационных сетей с учетом особенностей поступающих пакетов, в том числе с групповым поступлением и пульсирующим трафиком [41], [45], [53],
— исследование системы гистерезисного управления нагрузкой в сети прокси-серверов протоколаинициализации сеансов связи [38].
Задача диссертации — разработка методов анализа эффективности те-лекоммуникационных систем третьего и четвертого поколений, а именно: построение аналитических моделей расчета показателей эффективности функционирования (задержка в очереди на обработку, потеря сообщений) телекоммуникационных систем с помощью СМО с групповым марковским потоком, произвольным (рекуррентным) обслуживанием, конечной и бес¬конечной очередью, дисциплиной обслуживания LCFS РР и гистерезис- ной политикой. Варьирование значений функций вероятностного приори¬тета является альтернативным (к классическому) механизмом обеспечения качества обслуживания сообщений в системе. Кроме того, учитывая теку¬щие результаты деятельности международных стандартизирующих орга¬низаций в предметной области, можно заключить, что вопросы разработки методов и анализа качества всевозможных аспектов телекоммуникацион¬ных сетей 3G и 4G являются весьма важными. В связи с этим тематика диссертационного исследования является актуальной.
Цель диссертационной работы.
1. Разработка методов анализа показателей эффективности функци¬онирования телекоммуникационных систем 3G и 4G (задержка передачи сообщения, вариация задержки) в виде СМО с конечной и бесконечной ем¬костью накопителя, с групповым марковским входящим потоком, произ¬вольным (рекуррентным) обслуживанием и дисциплиной LCFS РР (ин¬версионный порядок обслуживания с вероятностным приоритетом);
2. Разработка математических методов расчета показателей эффек¬тивности (например, вероятность потерь поступающих сообщений) одно¬линейной СМО с пуассоновским входящим потоком, рекуррентным обслу¬живанием. накопителем конечной емкости, дисциплиной LCFS РР и ги- стерезисной политикой;
3. Разработка численных методов расчета вероятностно-временных характеристик рассмотренных систем по полученным математическим со¬отношениям.
Результаты, выносимые на защиту.
1. Для телекоммуникационных систем 3G модель в виде СМО
BMAP/G/l/r, г < оо, с инверсионной дисциплиной обслуживания и ве¬роятностным приоритетом и интегро-дифференциальные уравнения для стационарных плотностей вероятностей марковского процесса, описываю¬щего функционирование данной системы.
2. Метод анализа и расчета вероятностно-временных характеристик СМО BMAP/G/1/r, г < оо, — стационарные вероятности числа заявок в системе, среднее число заявок в системе, стационарные вероятности поте¬ри и недообслуживания заявки (случай г < оо), преобразования Лапласа- Стилтьеса (ПЛС) времени ожидания и времени пребывания заявок в си¬стеме.
3. Для телекоммуникационных систем 4G построение и анализ модели с гистерезисной политикой в виде СМО M/G/1/r, г < оо, с инверсионным порядком обслуживания и вероятностным приоритетом.
4. Для СМО M/G/1/r, г < оо. с инверсионной вероятностной дисци¬плиной обслуживания и гистерезисным управлением нагрузкой — интегро- дифференциальные уравнения для стационарных плотностей вероятно¬стей того, что в системе находится п заявок, а остаточная длина заявки на приборе х, и численный анализ ее вероятностно-временных характеристик.
Научная новизна. Все результаты диссертации являются новыми. По сравнению с известными результатами, в диссертации получены следую¬щие результаты:
1. Предложен подход к построению аналитических моделей анализа эффективности функционирования телекоммуникационных систем 3G и 4G, который заключается в комбинировании сложной дисциплины обслу¬живания (LCFS РР), входящего В МАР- потока, произвольного обслу¬живания и механизма управления перегрузками.
2. Рассмотрены общие варианты СМО с дисциплиной LCFS РР, в которых обслуживание рекуррентно, а входящие потоки являются обобще- ниями потока фазового типа и не являются рекуррентными. Ранее резуль¬таты были получены для СМО MAP/G/1/r с дисциплиной LCFS РР.
3. Для анализа показателей эффективности систем доступа UMTS впервые предложена модель с групповым марковским входящим потоком, произвольным (рекуррентным) обслуживанием и дисциплиной LCFS РР, а также получен метод нахождения ее стационарных характеристик (за¬держки и разброса задержки передачи, среднего числа переданных сооб¬щений, вероятности потери).
4. Разработан метод для вычисления показателей эффективности функционирования SIP-серверов с двухнороговым гистерезисным управ¬лением. произвольным обслуживанием и дисциплиной LCFS РР. Ранее результаты были получены для дисциплины FCFS.
Методы исследования. В работе используются методы теории веро¬ятностей, теории случайных процессов, теории массового обслуживания, численные методы.
Обоснованность и достоверность результатов. Достоверность ра¬боты следует из использования строгих математических методов исследо¬вания и подтверждается вычислительным экспериментом.
Обоснованность предположений о входящем потоке следуют из различ¬ных исследований (см., например, [48], [49], [52]), в которых подтверждает¬ся, что информационные потоки в телекоммуникационных сетях 3G с вы¬сокой степенью достоверности моделируются с помощью группового мар¬ковского потока.
Теоретическая и практическая ценность. Математические и вы¬числительные методы, разработанные в диссертации, могут применяться для расчета и анализа характеристик качества телекоммуникационных се¬тей третьего поколения, в частности при моделировании работы протоко¬лов сети доступа UMTS, компьютерных систем, в которых входящий поток заданий не является рекуррентным, а их объем известен лишь с некото¬рой вероятностью. Полученные в диссертации методы и результаты могут также найти применение в дальнейшем исследовании более сложных СМО с марковским входящим потоком, рекуррентным обслуживанием и други¬ми особенностями функционирования. Созданные на основе полученных теоретических результатов программы позволяют производить расчет ка¬чественных характеристик для таких систем при их эксплуатации и про¬ектировании.
Исследования проводились в рамках грантов Российского фонда фун-даментальных исследований (РФФИ) № 02-07-90147 «Математические ме¬тоды и программное обеспечение моделирования информационных, вы¬числительных и телекоммуникационных систем», № 06-07-89056 «Матема¬тические модели, методы, алгоритмы и программное обеспечение, осно¬ванное на веб-технологиях, для проведения фундаментальных исследова¬ний в области анализа производительности сетевых систем», № 11-07-00112 «Информационная технология и программные средства моделирования и анализа функциональных и структурных характеристик потоков в инфор¬мационных и телекоммуникационных системах с большим числом пользо¬вателей» и №12-07-00108 «Информационная технология и программные средства моделирования и анализа механизмов управления перегрузками прокси-серверов в сети связи следующего поколения (NGN)».
Реализация результатов работы. Результаты диссертации исполь¬зовались в научно-исследовательских работах (НИР), проводимых Инсти¬тутом проблем информатики Российской академии наук:
— Разработка общих базовых математических методов расчёта систем массового обслуживания, функционирующих в дискретном времени;
— Исследование систем и сетей массового обслуживания специального вида и информационно-управляющих систем с новыми видами обратной связи;
— Исследование систем и сетей массового обслуживания специального вида с ненадёжными приборами и отрицательными заявками.
Кроме того результаты диссертации были внедрены в учебный процесс (дисциплина "Дополнительные главы ТМО”, читаемая студентам третье¬го курса направления "Прикладная математика и информатика” РУДН) и вошли в программу “WEB-ориентированный программный комплекс уда¬ленного расчета стационарных характеристик систем массового обслужи¬вания'11.
Апробация работы. Результаты, полученные в ходе выполнения дис-сертационной работы, докладывались на
— мемориальном семинаре, посвященном 60-летию со дня рождения Владимира Калашникова «Прикладные вероятностные модели и инфор¬мационные процессы (Петрозаводск, 2002 год);
— на Всероссийских конференциях по проблемам математики, инфор¬матики, физики, химии и методики преподавания естественнонаучных дис¬циплин (Москва, 2003, 2004, 2009 годы);
— на Всероссийской конференции «Прикладная теория вероятностей и теоретическая информатика» (Москва, 2012 год);
’Дата регистрации РОСПАТЕНТом 11.01.2010г.. номер свидетельства о регистрации № 2010610026.
— на научных семинарах РУДН и Института проблем информатики РАН.
Публикации. По теме диссертации опубликовано 12 работ (из них 5 - тезисы докладов на всероссийских и международных конференциях, 7 - статьи в научных журналах), список которых приводится в конце авторе¬ферата. Основные результаты представлены в работах, опубликованных в изданиях, рекомендованных ВАК, и получены лично соискателем. В ра¬ботах, опубликованных в соавторстве, личный вклад соискателя состоит в проведении исследований и интерпретации полученных результатов.
Структура и объем диссертации. Диссертация состоит из введе¬ния, трёх глав, разделённых на пункты, заключения и списка литературы. Текст диссертации изложен на 135 страницах, включая 6 приложений.

bibliography

Заключение
В диссертационной работе решена задача разработки методов анализа эффективности телекоммуникационных систем третьего и четвертого по¬колений. а именно построение аналитических моделей расчета показате¬лей эффективности функционирования (задержка в очереди на обработку, джиттер, потеря сообщений) телекоммуникационных систем с помощью СМО с групповым марковским потоком, произвольным (рекуррентным) обслуживанием, конечной и бесконечной очередью, дисциплиной обслу¬живания LCFS РР и гистерезисной политикой Варьирование значений функций вероятностного приоритета является альтернативным (к клас¬сическому) механизмом обеспечения качества обслуживания сообщений в системе
В диссертации
1 Предложен аналитический метод нахождения показателей эффек¬
тивности функционирования телекоммуникационных систем, моделируе¬мых с помощью СМО с групповым марковским входящим потоком, про¬извольным (рекуррентным) обслуживанием, инверсионной дисциплиной обслуживания с вероятностным приоритетом (LCFS РР).
2. Для телекоммуникационных систем 3G и 4G на основе СМО BMAP/G/1/r с инверсионной дисциплиной обслуживания и вероятност¬ным приоритетом, накопителем конечной и бесконечной емкости, разрабо¬таны математические методы анализа и расчета вероятностно-временных характеристик: стационарных распределений числа заявок, вероятности блокировки и недообслуживаиия заявки, распределения времени пребы¬вания заявки в системе.
3. Для телекоммуникационных систем, моделируемых с помощью СМО M/G/1/r с инверсионным порядком обслуживания и вероятност¬ным приоритетом и гистерезисной политикой, накопителем конечной и бесконечной емкости, получены уравнения для расчета вероятностно¬временных характеристик: стационарных распределений числа заявок, распределения времени пребывания заявки в системе.
4. Разработан метод расчета и проведен численный анализ стацио¬нарных характеристик рассмотренных моделей по полученным матема¬тическим соотношениям, а также метод анализа и расчета вероятностно¬временных характеристик телекоммуникационных систем, моделируемых с помощью СМО MAP/G/1/r и СМО M/G/1/r с накопителем конечной и бесконечной емкости.
Список литературы
[1] Башарин Г. П., Бочаров П. П., Коган А. Я. Анализ очередей в вычис¬лительных сетях. Теория и методы расчета. - М.: Наука, 1989. - 336 с.
[2] Беллман Р. Введение в теорию матриц. - М.: Физматгиз, 1969. - 367 с.
[3] Беляев Ю. К. Линейчатые марковские процессы и их приложения к задачам теории надежности. // Труды VI Всесоюзного совещания по теории вероятностей и математической статистике. - Вильнюс: Гос. изд-во полит, и научн. литературы Литовской ССР, 1962. - С. 309-323.
[4] Боровков А.А. Асимптотические методы в теории массового обслужи¬вания. - М.: Наука, 1980. - 367 с.
[5] Боровков А.А. Вероятносные процессы в теории массового обслужи¬вания. - М.: Наука, 1972. - 368 с.
[6] Бочаров П.П. Анализ системы массового обслуживания MAP/G/1/r конечной емкости. // Вестник РУДН. Сер. «Прикладная математика и информатика». - 1995. - j"s 1. - С. 52-67.
[7] Бочаров П.П.. Печинкин А.В. Теория массового обслуживания. - М.: Изд-во РУДН, 1995. - 529 с.