Модели и методы анализа показателей эффективности функционирования мультисервисных и одноранговых сетей Гайдамака Юлия Васильевна

Содержание к диссертации

Введение

Особенности построения математических моделей мультисервисных сетей 28

Обзор моделей мультисервисных сетей по теме работы 28

Показатели эффективности мультисервисных сетей 33

Модели обслуживания трафика мультисервисных сетей 37

Модели управления перегрузками сервера протокола установления сессий 42

Модели одноранговых потоковых сетей и беспроводных сетей взаимодействующих устройств 48

Анализ моделей мультисервисных сетей c мультипликативным распределением 60

Замечания о мультипликативных решениях 60

Модель мультисервисной сети с многоадресным трафиком 63

Мультипликативное решение для модели сети с одноадресным и многоадресным трафиком 68

Модель обслуживания трафика межмашинных взаимодействий в сети LTE 80

Модель обслуживания трафика в пассивной оптической сети 85

Модели систем и сетей массового обслуживания установления соединений в мультисервисных сетях 91

Математические модели систем установления соединения 91

Двухпотоковая поллинговая модель с пороговым управлением нагрузкой сервера протокола установления сессий 95

Двухпотоковая поллинговая модель с пороговым управлением нагрузкой сервера протокола установления сессий 109

Модель гистерезисного управления нагрузкой в сети серверов протокола установления сессий 119

Обзор методов порогового управления нагрузкой 119

Исследование механизма контроля перегрузок сервера протокола установления сессий 125

4.3. Базовая модель гистерезисного управления нагрузкой 133

4.4. Особенности анализа модели с групповым поступлением заявок 140

ГЛАВА 5. Построение моделей для анализа показателей эффективности одноранговых сетей 153

5.1. Предварительные замечания к главам 5 и 6 153

5.2. Аналитическая модель сети массового обслуживания для одноранговой сети вещательного телевидения 155

5.3. Аппроксимация нормальным законом вероятности всеобщей передачи в одноранговой сети с двумя типами пользователей 158

5.4. Базовая модель одноранговой сети взаимодействия беспроводных устройств 162

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

ГЛАВА 6. Модель буферизации данных в потоковых одноранговых сетях 180

6.1. Анализ процесса обмена данными между пользователями в потоковых сетях 180

6.2. Модель буферизации данных в виде цепи Маркова с учетом задержки воспроизведения видеоданных 185

6.3. Аналитический метод расчета матрицы переходных вероятностей 193

6.4. Модель стратегий обмена данными с учетом местоположения и активности пользователей 202

Заключение 210

Библиография

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

Введение к работе

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

информацию (речь, видео, аудио).

Это изменение влечет за собой существенные перемены в научных исследованиях, в том числе, в принципах построения математических моделей и разработки на их базе методов анализа показателей эффективности сети. Во-первых, в мультисервисных сетях связи появились новые типы соединений, применяемых при передаче потокового видео, что потребовало существенной модификации моделей сети с коммутацией каналов и методов их анализа, обеспечивающих возможность создания эффективных вычислительных алгоритмов. Во-вторых, кардинально изменились системы управления процессом установления соединений (т.н. «системы сигнализации»), и были обнаружены проблемы, связанные с перегрузками узлов сети. Возникла необходимость в создании новых математических моделей управления входящими потоками сообщений и разработки на базе этих моделей механизмов управления перегрузками. В-третьих, появились новые типы наложенных одноранговых сетей с высокими требованиями к пропускной способности - т.н. «пиринговые» сети (peer-to-peer, P2P) и сети прямого взаимодействия беспроводных устройств (device-to-device communications, D2D). Потребовались новые математические модели для анализа показателей эффективности, которые являются функционалами как от показателей качества обслуживания сети (Quality of Service, QoS), так и от показателей качества восприятия услуг пользователем (Quality of Experience, QoE). Наиболее важными показателями QoS являются вероятность блокировки запросов пользователей, время установления соединения, параметры механизмов управления соединением, характеристики интерференции в D2D сети, а наиболее важными показателями QoE является вероятность непрерывного воспроизведения видео потока в P2P-сети и др.

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

продолжились в направлении развития новых подходов, учитывающих

различные типы трафика, специфику новых систем сигнализации и особенности
функционирования одноранговых сетей. Фундаментальные исследования
ведутся в области классических моделей мультисервисных сетей с различными
комбинациями трех типов трафика – одноадресного, многоадресного и
эластичного – и для различных приложений, например, межмашинных
взаимодействий (machine-to-machine communications, M2M). В области создания
надежного механизма по предотвращению перегрузок в сети серверов,
управляющих установлением соединения, исследуются новые модели систем
массового обслуживания (СМО) с пороговым управлением входящим потоком.
В связи с активным внедрением беспроводных сетей LTE (Long Term Evolution)
исследования развиваются как в области задач разделения радиоресурсов и
задач оценки характеристик интерференции в сети радиодоступа, так и в
области анализа и расчета показателей качества обслуживания на базе моделей
теории телетрафика и теории массового обслуживания. Наконец, исследования
одноранговых сетей в области обслуживания трафика ведутся по нескольким
направлениям с использованием теории конечных цепей Маркова (ц.м.), в т.ч.
числе в области моделирования и анализа показателей качества восприятия
услуг, например, услуги цифрового вещательного телевидения. Теоретические и
прикладные основы исследований в перечисленных направлениях базируются в
основном на результатах в области дискретной математики, теории конечных
графов, теории вероятностей, теории случайных процессов и теории массового
обслуживания. В числе российских исследователей и математиков в этой
области следует назвать Г.П. Башарина, П.П. Бочарова, Е.В. Булинскую,
В.М. Вишневского, Б.В. Гнеденко, А.Н. Дудина, А.И. Зейфмана,

В.А. Ивницкого, В.Ю. Королева, А.А. Назарова, А.Е. Кучерявого, А.И. Ляхова,
В.А. Наумова, Е.В. Морозова, С.П. Моисееву, Ю.Н. Орлова, А.В. Печинкина,
А.П. Пшеничникова, О.Н. Ромашкову, К.Е. Самуйлова, И.А. Соколова,

С.Н. Степанова, И.И. Цитовича, С.Я. Шоргина и др., а наиболее значимыми зарубежными авторами являются J.G. Andrews, F. Baskett, E. Gelenbe, M. Dohler, V.B. Iversen, M. Haenggi, F. Kelly, L. Kleinrock, P.J. Kuhn, Y. Liu, D. Lucantoni, D.M. Chiu, M.F. Neuts, O. Martikainen, B. Mukherjee, R. Ramaswami, K.W. Ross, H. Takagi, W. Whitt и др.

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

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

Цель и задачи исследований. Диссертация посвящена решению

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

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

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

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

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

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

Научная новизна работы состоит в следующем.

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

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

оценки времени установления соединений в мультисервисных сетях не применялся.

3. Разработаны методы анализа показателей эффективности сервера протокола установления сессий в условиях перегрузок на базе моделей СМО с поллингом и СМО с гистерезисным управлением нагрузкой. Ранее ни поллинг с пороговым управлением, ни гистерезисное управление не применялись при построении моделей сервера протокола установления сессий.

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

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

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

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

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

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

4. Построенная модель СМО с гистерезисным двухпороговым управлением входящим потоком применима для анализа механизма управления перегрузками сервера протокола установления сессий. Модель позволяет вычислять показатели эффективности управления – вероятность блокировки

и характеристики случайной величины (с.в.) времени выхода сервера из состояния перегрузки.

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

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

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

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

формулировки проблем и постановки задач обсуждались с научным консультантом проф. К.Е. Самуйловым и с заслуженным деятелем науки РФ проф. Г.П. Башариным, что отражено в совместных публикациях, в которых основные результаты и их доказательства принадлежат диссертанту.

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

Результаты диссертационной работы легли в основу учебно-методических комплексов для лекционных курсов, постановок задач для выпускных работ бакалавров по направлениям подготовки 010200.62 «Математика и компьютерные науки» и 010400.62 «Прикладная математика и информатика», магистерских диссертаций по специализации «Теория вероятностей и математическая статистика» и кандидатских диссертаций по специальности 05.13.17 «Теоретические основы информатики» на кафедре прикладной информатики и теории вероятностей факультета физико-математических и естественных наук РУДН.

Часть результатов диссертационной работы получена при выполнении ряда крупных научно-исследовательских проектов, где автор диссертационной работы являлась руководителем и исполнителем, в том числе, при исследованиях по грантам РФФИ, РНФ, а также НИР, выполняемых по приоритетным научным направлениям в РУДН.

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

фундаментальных методов, соответствием полученных теоретических

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

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

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

2. Исследование информационных структур, разработка и анализ моделей информационных процессов и структур.

13. Общие принципы организации телекоммуникационных систем и оценки их эффективности.

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

семинарах: Всероссийская научная конференция факультета физико-

математических наук РУДН, Москва, 2002-2010 гг.; Всероссийская конференция
«Информационно-телекоммуникационные технологии и математическое

моделирование высокотехнологичных систем», Москва; 2011-2016 гг.; International
IEEE Conference Eurocon 2009, St.Petersburg, 2009; International Conference on Next
Generation Wired/Wireless Networking NEW2AN, St.Petersburg, 2009-2016;
International Congress on Ultra Modern Telecommunications and Control Systems
ICUMT, Moscow, 2010, St.Petersburg, 2012, 2014; European Conference on Modelling
and Simulation ECMS, Koblenz, 2012, Aalesund, 2013, Brescia, 2014, Albena, 2015,
Regensburg, 2016; Международная конференция «Распределенные компьютерные и
телекоммуникационные сети: теория и приложения» DCCN, 2010, 2013, 2015; XII
Всероссийское совещание по проблемам управления ВСПУ, Москва, 2014;
Международная научно-практическая конференция «Современные

информационные технологии и ИТ-образование», Москва, ВМиК МГУ, 2011-2015;
Международная конференция «Теория вероятностей и ее приложения»,
посвященная 100-летию со дня рождения Б.В. Гнеденко, Москва, 2012; 12^th Annual
International Conference «Reliability and Statistics in Transportation and Communication
(RelStat’12)», Riga, 2012; International Workshop on Simulation IWS, Rimini, 2013,
Vienna, 2015; European Conference on Operational Research EURO, Vilnius, 2012,
Glasgow, 2015; International Conference of Numerical Analysis and Applied Mathematics
ICNAAM, Rhodes, 2014, 2015; Международная научно-практическая конференция
имени А.Ф. Терпугова «Информационные технологии и математическое

моделирование» ИТММ, 2014, 2015, 2016; Всероссийская научная конференция «Современные тенденции развития теории и практики управления в системах специального назначения», Москва, 2013, 2014; 68-я Всероссийская конференция, посвященная дню радио РНТОРЕС им. А.С. Попова, Москва, 2013; International Seminar on Stability Problems for Stochastic Models ISSPSM, Svetlogorsk, 2011, 2012, Moscow, 2013, Trondheim, 2014, Tampere, 2015; International Conference INternet of THings and ITs ENablers INTHITEN, St. Petersburg, 2013; 13^th International Conference on Networks ICN, Nice, 2014; 20^th Conference of the International Federation of Operational Research Societies IFORS, Barcelona, 2014; International Science and Technology Conference Modern Networking Technologies MoNeTec, Moscow, 2014; 22^nd European Wireless conference EW, Oulu, 2016; VII Международная научная конференция «Компьютерные науки и информационные технологии», Саратов, 2016; семинары РУДН, МТУСИ, СПб ГУТ, ИПИ РАН, ИПУ РАН, Большой семинар кафедры теории вероятностей МГУ.

Публикации. Основные результаты диссертации изложены в

40 опубликованных работах, в том числе в 1 монографии; в 24 статьях,
опубликованных в журналах, включенных в Перечень российских

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

доктора и кандидата наук, и в журналах, индексируемых Web of Science и Scopus; в 11 полнотекстовых статьях, опубликованных в трудах конференций, индексируемых Web of Science и Scopus.

Структура и объем работы. Диссертация состоит из введения, шести глав, заключения и списка литературы. Общий объем диссертации 235 страниц, включая 59 рисунков, 7 таблиц, список литературы из 258 наименований.

Модели обслуживания трафика мультисервисных сетей

Показано, что стационарное распределение м.п. удовлетворяет системе уравнений равновесия, которая решается численно методом LU-разложения. При этом для представления матрицы интенсивностей переходов в блочном трехдиагональном виде достаточно определить лексикографический порядок по введенному для состояний м.п. отношению предшествования. Доказана [238] лемма 3.1, в которой формализованы условия предшествования, определяющие метод вычисления диагональных, наддиагональных и поддиагональных блоков матрицы интенсивностей переходов. Для вычисления характеристик исчерпывающей дисциплины применен тот же подход, в заключение проведен сравнительный анализ шлюзовой и исчерпывающей дисциплин марковских систем поллинга. Показано преимущество исчерпывающей дисциплины обслуживания по следующим показателям эффективности: 1) меньшее время ожидания начала обслуживания заявок в приоритетной очереди для поллинговой модели с ненулевым временем переключения; 2) меньшее среднее число заявок в приоритетной очереди и меньшая вероятность пребывания в состояниях перегрузки для поллинговой модели конечной емкости с пороговым управлением.

Четвертая глава диссертационной работы посвящена построению и методам анализа модели гистерезисного управления нагрузкой SIP серверов в мультисервисной сети.

В разделах 4.1 и 4.2 разработан обзор [1, 52, 56, 64, 65, 79, 111, 119, 124-126, 167, 168, 180, 196, 225, 232, 246, 248] методов управления сигнальной нагрузкой в мультисервисных сетях, а также исследован механизм контроля перегрузок сервера протокола установления сессий. Показано, что применим метод управления нагрузкой, разработанный в рекомендациях МСЭ для протоколов

ОКС77. Обработка перегрузки в ОКС7 включает в себя два этапа - обнаружение перегрузки и действия по ее снижению или предотвращению. Для обнаружения перегрузки производится контроль числа сообщений в очереди, а действия по снижению перегрузки заключаются в ограничении поступающего потока сообщений. Разработанный метод управления нагрузкой в мультисервисных сетях предполагает использует три типа порогов - порог Н обнаружения перегрузки, порог L снижения перегрузки и порог В сброса нагрузки. При достижении очередью порога обнаружения перегрузки производится снижение входящей нагрузки, при этом при продолжении перегрузки и достижении очередью порога сброса нагрузки производится сброс поступающих на систему сообщений. Во избежание осцилляции при падении длины очереди возврат к нормальной нагрузке происходит не сразу после снижения наполненности буфера ниже значения порога обнаружения перегрузки, а лишь после пересечения длиной очереди порога снижения перегрузки. Описанный механизм соответствует гистерезисному управлению нагрузкой. Определена качественная зависимость интенсивности l(s,n) потока сообщений от длины п очереди при процедуре гистерезисного управления. Также определен s статус перегрузки: s=0 - нормальная нагрузка, s=\ - перегрузка, s=2 - сброс нагрузки. При обнаружении перегрузки при длине очереди п = Н нормальное значение Л интенсивности входящего потока снижается до величины X Л. Если длина очереди достигает величины п = В, происходит сброс сообщений, т.е. /l(s,ft)=0 для п В. При последующем уменьшении очереди до величины п Н интенсивность входящего потока вырастет до значения X и сохранится до момента достижения очередью значения п = L, когда интенсивность входящего потока вернется к нормальному уровню Л. Проведенные исследования показали, что именно этот механизм может быть положен в основу принципов управления перегрузками в сети SIP-серверов сетей последующих поколений.

Согласно проведенному обзору литературы, известен ряд статей [183, 188, 208, 214, 217, 225], где изложены подходы к построению моделей функционирования SIP-серверов с пороговым управлением в условиях перегрузок. Но практически во всех известных источниках, включая рекомендации IETF , в явном виде отсутствует метод гистерезисного управления, а все численные результаты получены либо с помощью измерений, либо с использованием имитационных моделей. Поэтому для математического анализа параметров управления нагрузкой в сети SIP-серверов предложено применять СМО с гистерезисным управлением нагрузкой.

В разделе 4.3 построена [1, 38, 56, 124, 125, 164, 167] базовая математическая модель управления нагрузкой в сети SIP-серверов в виде СМО M(X,p)M1(L,H)B согласно обозначениям Кендалла-Башарина [13, 72, 73], где В объем буферного накопителя, L порог нижнего уровня, Н порог верхнего уровня контроля перегрузок. Интенсивность входящего потока A(s,n) зависит от статуса перегрузки и числа заявок в очереди рассматриваемой СМО. Предполагается, что в состоянии нормальной загрузки система может обслуживать поток интенсивности 1, а при достижении очередью значения Н порога верхнего уровня поток уменьшается до величины Л = рЛ, где 1-р доля сброшенных сообщений. Сформулированным утверждением 4.1 построена базовая модель гистерезисного управления нагрузкой в сети SIP-серверов, которая была использована в ряде работ, в том числе в работах автора диссертационной работы. Для базовой модели стационарное распределение вероятностей состояний было получено в лемме 4.1 в аналитическом виде. Важнейшей характеристикой управления SIP-сервером является время его пребывания в состоянии перегрузки, которое подлежит минимизации [1, 52, 56, 124-126, 167, 168, 232]. Обозначим т12 св. времени пребывания заявок в множестве перегрузки, от момента, когда м.п. Y(t) вошел в множество %12 = J1 2, те. в состояние (1,Я) , до момента, когда процесс в первый раз вернулся в множество К0 состояний нормальной нагрузки, то есть в состояние (0,Z-1). Здесь % множество состояний перегрузки и % множество состояний сброса нагрузки. В реальной технической системе св. г12 соответствует времени функционирования SIP-сервера в режиме перегрузки, когда управление

Модель обслуживания трафика в пассивной оптической сети

В этой главе, следуя [91], кратко излагается подход к анализу модели марковского процесса мультисервисной сети c потерями (loss network), известной по работам Ф. Келли [193, 194] и К. Росса [222]. В первом разделе главы в виде многомерного м.п. построена модель мультисервисной сети, в явном мультипликативном виде получены стационарное распределение, а также выражения для вероятностей блокировки установления соединений. Во втором разделе изложены методы анализа модели отдельного звена сети, функционирование которой описывается мультисервисной моделью Эрланга с явными потерями [14], и приведен алгоритм типа Кауфмана-Робертса [192, 221].

Построение модели проводим для сети с конечным числом узлов, соединенных звеньями, имеющей произвольную топологию. Перенумеруем звенья сети от 1 до L и обозначим множество звеньев = {1,2,...,L}, а емкость /-звена С/ условных единиц. Для соединений типа «точка-точка» введем понятие класса соединений, который определяется двумя параметрами: т.н. «маршрутом», то есть множеством звеньев сети, через которые устанавливается соединение, и требованием к емкости, которую необходимо выделить соединению на каждом звене соответствующего маршрута. Множество классов соединений обозначим Ж = {1,2,...,К}, и пусть 2к 2 - маршрут, а dk требование к емкости, выделяемой на каждом звене маршрута для соединения -класса. Пусть в систему поступают запросы пользователей на установление соединений различных классов. Введем предположения о пуассоновском потоке интенсивности vk поступления запросов пользователей на установление соединения -класса, о независимости в совокупности длительности соединений, которые к тому же не зависят от моментов установления соединения и одинаково распределены по произвольному закону со средним 1кк . Интенсивность предложенной нагрузки обозначим ак =Ук/кк .

Соединение требуемого класса, который определяется узлами подключения пользователя, отправившего запрос на предоставление услуги, и источника, содержащего данные, соответствующие запрошеной услуге, будет установлено, если на всех звеньях соответствующего маршрута число свободных единиц емкости звена не меньше требования этого класса. Если хотя бы на одном из звеньев маршрута не окажется требуемого числа свободных единиц ресурса, произойдет блокировка, и запрос буде потерян. Пусть емкости всех звеньев сети неограничены: Сг - со, / є 9В. В этом случае запрос пользователя на установление соединения любого класса будет принят на обслуживание, и потери не произойдет. Обозначим Nk{t) число установленных в момент t соединений Л-класса. Тогда состояние системы можно описать с помощью многомерного случайного процесса \j$(t) = (Nl(t),N2(t),...,NK(i)),t o}, каждая компонента которого соответствует одному классу соединений. Поскольку емкости звеньев неограниченны, то множество состояний случайного процесса {N(0, t 6\ имеет вид .# = {0,1,2,...} . Известно, что м.п. {Nk(t\t o} является процессом размножения и гибели (п.р.г.) со стационарным распределением pk(nk) = V{Nk{t) = nk} = e-a\ илє{0,1,2,...}. пк! Поскольку, в силу неограниченной емкости звеньев, компоненты м.п. (N(Y), t 0 независимы, он является обратимым (о.м.п.) и его стационарное распределение имеет мультипликативный вид: щ (n) = P{N(0 = n}=TT— е"%, neJ. ыж пк! Пусть теперь емкости звеньев снова ограничены: Q оо, / є ЗИ . Введем множество Ж1={кєЖ:Ієк} классов соединений, маршруты которых проходят через /-звено, и функцию 4(п)= 2 dknk, (2.1) соответствующую числу единиц емкости, занятых на /-звене, когда система находится в состоянии п є Jf. Теперь пространство состояний системы с ограниченной емкостью звеньев можно представить в виде

Количество возможных состояний модели зависит от числа и емкости звеньев сети, что приводит к экспоненциальному росту числа возможных маршрутов при увеличении любого их этих показателей. Поэтому метод нахождения вероятностей блокировок непосредственно по формулам (2.3)-(2.6) применим лишь для простейших случаев. Более того, для сети произвольной топологии вычисление нормировочной константы G(A) по формуле (2.4) относится к NP-полным проблемам, для которых не существует эффективных комбинаторных алгоритмов. Поэтому много внимания уделялось [91] и уделяется разработке приближенных методов вычисления вероятностных характеристик модели, пригодных для анализа широкого класса моделей. Приближенным методам расчета сетей рассматриваемого типа посвящена, например, глава 5 книги [93].

В этом разделе диссертации показано основное свойство моделей мультисервисных сетей, приведенное в теореме 2.1 на примере классических сетей Келли для случай одноадресных соединений [193, 194]. Целью данной главы является анализ мультипликативных решений для сетей с одноадресными и многоадресными соединениями, а также соответствующие им вычислительные алгоритмы для основных вероятностных характеристик. В разделе 2.2 исследованы сети с многоадресными соединениями, т.н. сети мультивещания, которые сейчас имеют широкое применение в сетях 4G и 5G. Получена теорема о мультипликативном решении для сети с несколькими источниками информации, а также исследован важный частный случай отдельного звена сети, для которого получен рекурсивный алгоритм типа Кауфмана-Робертса. В разделе 2.3 исследована сеть с двумя типами соединений, введена еще одна, эрланговская, модель звена сети с многоадресными соединениями, доказана теорема о мультипликативном решении и получен рекурсивный алгоритм для отдельного звена сети как комбинация алгоритма Кауфмана-Робертса и алгоритма, разработанного автором диссертации для сети с многоадресными соединениями. В разделах 2.4 и 2.5 показано применение разработанных методов к двум важным моделям сетей 4G и 5G. Первая модель [237] показывает мультипликативное решение для беспроводной сети 5G, где наряду с традиционным речевым трафиком (Н2Н) обслуживается трафик межмашинных взаимодействий (М2М). Вторая модель [16, 17] построена для наземных коммуникаций - пассивных оптических сетей с реализованной на них технологией мультиплексирования по длине волны (wave division multipexing, WDM).

Базовая модель гистерезисного управления нагрузкой

По данным ежегодного прогноза Cisco22 в течение 5 лет трафик от мобильных устройств увеличится почти в восемь раз и к 2020 году составит 30,6 эксабайт (1018 ) в месяц. Ожидается рост количества мобильных устройств до 11,6 млрд, так что при прогнозируемой численности населения 7,8 млрд на душу населения будет приходится 1,5 мобильных устройства. Скорости подключения к сети мобильных пользователей увеличатся более чем в три раза: в 2017 году средняя скорость подключения к сети мобильной связи превышает 2 Мбит/с, а к 2020 году она достигнет 6,5 Мбит/с. Объем мобильного трафика видеоданных в период между 2015 и 2020 годами вырастет в 11 раз и будет составлять к 2020 году 75 % от общего объема трафика мобильных данных. Передача видео конечному пользователю требует от телекоммуникационных операторов высокого качества обслуживания (QoS) и качества восприятия пользователем (QoE).

Базой для внедрения новых мультимедийных услуг в мультисервисных сетях последующих поколений является мультимедийная IP-подсистема (IP multimedia subsystem, IMS)23, позволяющая предоставлять на базе протокола IP на транспортоном уровне единой сети передачи данных как традиционные услуги связи (телефонная связь, передача факсимильных сообщений), так и новые услуги (аудио-, видеоконференции, потоковое видео, в т.ч. интерактивное телевидение IPTV, веб-услуги, передача файлов, электронная коммерция, интерактивные игры, распределенные вычисления, электронная почта, контроль присутствия, обмен мгновенными сообщениями, справочно-информационные услуги) мультисервисных сетей. В связи с высокой востребованностью этих услуг мультисервисные сети на базе IMS, работающие на основе протокола SIP, часто функционируют в условиях перегрузки. Важно, что при предоставлении мультимедийных услуг характер сигнального трафика, к кторому относится трафик установления сессий, существенно меняется. В частности, при предоставлении услуги контроля присутствия [86, 151, 251] (presence service24) сеть одновременно отправляет сообщения уведомления нескольким пользователям, что при построении математических моделей следует учитывать посредством неординарного потока, в частности строить модели в виде СМО с групповым поступлением заявок.

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

В работе [151] можно найти одну из первых постановок задач с использованием для анализа производительности SIP-сервера системы с групповым потоком и ненадежным прибором. Известны работы, посвященные исследованию подобных моделей как с ординарным, так и групповым входящим потоком (см., например, [75, 86, 152, 168, 205, 251]). Отметим также публикации, в которых рассматриваются т.н. «модели с разогревом» [52, 124, 126, 167, 168, 232]. В этих системах, как правило, исследуются среднее время ожидания и его дисперсия, а для систем конечной емкости еще и вероятность потерь. При этом автору не известны публикации, в которых была бы получена формула вероятности потерь в явном виде для систем с групповым потоком и ненадежным прибором типа М[Х] \G\l\r. Проблема предотвращения перегрузок в системах сигнализации была известна и ранее [64, 105, 207, 225, 241, 246]. В современных сетях, которые используют SIP в качестве протокола сигнализации, проблема осложняется отсутствием детально проработанного механизма управления нагрузкой в первоначальных спецификациях этого протокола. Пик интереса к этой проблеме приходится на 2008-2009 годы, когда IETF активно разрабатывались эффективные механизмы предотвращения перегрузок [183, 188, 209, 214, 217, 235]. При управлении нагрузкой в качестве параметров эффективности в них, как правило, рассмативается среднее время возврата из режимов перегрузки и вероятность пребывания в режимах перегрузки. Эти параметры порогового управления нагрузкой исследованы с помощью моделей с одной петлей, при этом в [125] анализируется модель типа M\G\l\{L,R), а в [3, 124] используется модель типа ММ1(і) с прогулками прибора. Модель с двумя петлями анализируется в статьях [3, 52, 124-129, 167, 168, 218, 225], при этом в [125, 167] проведено имитационное моделирование системы с детерминированной длительностью обслуживания, а в [225] для анализа использован аппарат мартингалов. Формулировке и решению задачи минимизации среднего времени возврата из состояний перегрузки за счет размещения в очереди порогов управления посвящены работы [52, 125, 126].

Модели М[Х] G11 с групповым входящим потоком, гистерезисным управлением и различными политиками обслуживания исследованы в [86, 107]. Отметим работы [43, 46-48, 215], где получены выражения для среднего значения и среднеквадратического отклонения длины очереди, среднего времени ожидания начала обслуживания для модели типа М[Х] G 11. В этих же работах проведен анализ указанных характеристик от нагрузочных параметров для нескольких распределений размера группы заявок: логарифмического детерминированного, Ципфа, геометрического и дискретного равномерного. Еще одним механизмом, защищающим сервер, обслуживающий сигнальный трафик, от перегрузки является приоритезация сообщений [25, 57]. Такие модели исследованы в [1, 214].

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

С ростом числа пользователей услуг, предоставляемых на базе протокола SIP, возникают различного рода перегрузки SIP-серверов из-за отсутствия достаточных ресурсов для установления и завершения сессий между агентами пользователей. Различают два типа перегрузок – перегрузки типа «клиент-сервер» и типа «сервер-сервер» [1]. Перегрузки «клиент-сервер» возникают в серверах-отправителях из-за избыточной нагрузки, создаваемой группами SIP-терминалов. Примером перегрузки «клиент-сервер» служит так называемый лавинный перезапуск, который происходит, когда большое число UAc пытаются зарегистрироваться на серверах-отправителях. Еще одним примером является сценарий «Манхэттенского перезапуска», когда в результате аварии произошло отключение электричества в этом крупнейшем районе города, и после восстановления электроснабжения все SIP-терминалы одновременно пытались зарегистрироваться на серверах, создав тем самым поток сообщений Register высокой интенсивности.

Отметим, что проблема перегрузки «клиент-сервер» может быть решена оператором сети связи простым увеличением числа SIP-серверов, но кроме того, в 2009 году в протокол SIP были внесены изменения в части механизма предотвращения лавинных подключений UAc к серверу, которые во многом решили проблему. Поэтому далее мы рассматриваем только перегрузки типа «сервер-сервер», которые могут возникать в ситуации, когда большое число вызовов начинает одновременно поступать на один номер (UAs). Примером такой ситуации является участие пользователей в телеголосовании или их реакция на рекламный ролик, сообщающий о том, что первые дозвонившиеся пользователи получат ценный подарок.

В протоколе SIP в части механизма контроля перегрузок до сих пор имеются существенные недоработки. Далее приведем описание этого механизма, после чего в соответствии с RFC 539034 кратко сформулируем проблемы, которые этот механизм не позволяет разрешить.

Базовый механизм контроля перегрузок. определенный в RFC 3261 (далее - механизм 503), в случае перегрузки прокси-получателя предусматривает отправку прокси-отправителю сообщения 503 Service Unavailable. В случае, когда сервер не может обработать запрос из-за временной перегрузки, ему следует отклонить этот запрос с кодом ошибки 503. Отправителю, получившему сообщение 503, следует действовать так, как в случае получения сообщения 500 Server Internal Error, и не следует перенаправлять сообщение с кодом 503 далее вверх по цепочке SIP-серверов, уведомляя их о перегрузке на одном из ниже лежащих серверов, до тех пор, пока прокси-отправитель не определит, что прокси-получатель имеет возможность отвечать на каждое его сообщение сообщением с кодом 503. Прокси-отправитель должен повторить исходное сообщение прокси-получателю или направить его на другой сервер. Перегруженный прокси-получатель также может добавить заголовок Retry-After в сообщение с кодом 503, указав время в секундах, в течение которого он не будет реагировать на любые сообщения от отправителя. Отправитель на этот период времени прекращает направлять сообщения получателю, вместо этого сообщения направляются на альтернативные сервера. Отправка сообщений на сервер, сообщивший о перегрузке, возобновляется по истечении интервала времени, указанного в заголовке Retry-After сообщения 503. Отметим, что RFC 3261 предусматривает в случае перегрузки возможность получателю сбрасывать поступающие сообщения без уведомления отправителя.

Перчислим также проблемы, возникающие в результате применения механизма 503 контроля перегрузок SIP-серверов согласно c RFC 5390. Заметим, что в документах IETF эти проблемы до сих пор не решены полностью. - Проблема усугубления перегрузки (load amplification); - Проблема неполного использования кластера SIP-серверов (underutilization); - Проблема использования сообщения 503 с заголовком Retry-After (Retry-After problem); - Проблема неоднозначного использования сообщения 503 (ambiguous usages);

Эти и некоторые другие проблемы достаточно подробно исследованы в обзоре [1] с участием автора. Перечислим теперь согласно с RFC 5390 основные требования к механизмам, отвечающие сформулированным выше проблемам. - Механизмы контроля перегрузок должны поддерживать производительность серверов на приемлемом уровне с учетом требований к заданному показателю качества обслуживания. Минимальное значение производительности сервера является критическим значением для оценки эффективности механизма контроля перегрузок. Существенно, что в случае ретрансляции сообщений по причине перегрузки получателя сервер-отправитель должен направлять сообщения только на серверы, работающие в нормальном режиме.