Исследование выходящего потока марковской модели узла обработки запросов с повторными обращениями и вызываемыми заявками
|
Аннотация 2
Введение 3
1 Исследование моделей с простейшим входящим потоком 7
1.1 Суммарный выходящий поток RQ-системы 7
1.1.1 Уравнения Колмогорова 8
1.1.2 Метод асимптотического анализа 11
1.1.3 Переход к явному распределению вероятностей 14
1.2 Двумерный выходящий поток RQ-системы 15
1.2.1 Уравнения Колмогорова 15
1.2.2 Метод асимптотического анализа 16
1.2.3 Переход к явному распределению вероятностей 19
1.2.4 Коэффициент корреляции 20
2 Исследование модели с входящим MMPP-потоком 21
2.1 Двумерный выходящий поток RQ-системы с MMPP 21
2.1.1 Уравнения Колмогорова 21
2.1.2 Метод асимптотического анализа 23
2.1.3 Переход к явному распределению вероятностей 28
3 Имитационное моделирование 29
3.1 Объектная модель предметной области 29
3.2 Процесс моделирования 35
3.3 Функционирование элементов системы массового обслуживания 37
3.4 Интерфейс и работа программы 41
3.4.1 Моделирование в реальном времени 42
3.4.2 Ускоренное моделирование 44
3.4.3 Работа с главным графиком 45
3.4.4 Экспорт результатов моделирования 49
3.5 Особенности реализации 50
3.5.1 Генерация псевдослучайных чисел 51
3.5.2 Отображение статуса при ускоренном моделировании 51
4 Численные эксперименты 53
4.1 Проверка стабильности имитационной модели 53
4.2 Оценка точности асимптотических результатов 55
4.3 Анализ корреляции выходящих процессов 58
Заключение 64
Список использованной литературы 67
Введение 3
1 Исследование моделей с простейшим входящим потоком 7
1.1 Суммарный выходящий поток RQ-системы 7
1.1.1 Уравнения Колмогорова 8
1.1.2 Метод асимптотического анализа 11
1.1.3 Переход к явному распределению вероятностей 14
1.2 Двумерный выходящий поток RQ-системы 15
1.2.1 Уравнения Колмогорова 15
1.2.2 Метод асимптотического анализа 16
1.2.3 Переход к явному распределению вероятностей 19
1.2.4 Коэффициент корреляции 20
2 Исследование модели с входящим MMPP-потоком 21
2.1 Двумерный выходящий поток RQ-системы с MMPP 21
2.1.1 Уравнения Колмогорова 21
2.1.2 Метод асимптотического анализа 23
2.1.3 Переход к явному распределению вероятностей 28
3 Имитационное моделирование 29
3.1 Объектная модель предметной области 29
3.2 Процесс моделирования 35
3.3 Функционирование элементов системы массового обслуживания 37
3.4 Интерфейс и работа программы 41
3.4.1 Моделирование в реальном времени 42
3.4.2 Ускоренное моделирование 44
3.4.3 Работа с главным графиком 45
3.4.4 Экспорт результатов моделирования 49
3.5 Особенности реализации 50
3.5.1 Генерация псевдослучайных чисел 51
3.5.2 Отображение статуса при ускоренном моделировании 51
4 Численные эксперименты 53
4.1 Проверка стабильности имитационной модели 53
4.2 Оценка точности асимптотических результатов 55
4.3 Анализ корреляции выходящих процессов 58
Заключение 64
Список использованной литературы 67
Во многих жизненных ситуациях человек сталкивается с необходимостью получить доступ к различным распределенным ресурсам. Ресурсы могут быть разного вида и про исхождения — касса в магазине, запись к врачу и многое другое. Помимо повседневной деятельности, такая необходимость в распределенных ресурсах возникает и в других более специализированных сферах жизнедеятельности и науке — протоколы множественного се тевого доступа, автоматизированное производство. Во всех данных ситуациях при доступе к ресурсу существует очередь, которая может быть упорядоченной, либо неупорядоченной.
Теория массового обслуживания занимается изучением и математическим модели рованием различных способов организации доступа к распределенному ресурсу [1]. Своим возникновением теория массового обслуживания обязана А.К. Эрлангу, который получил ряд базовых формул для исследования это области, решая практические задачи оптимизации систем телефонной связи [2]. Терминология, используемая в теории массового обслужива ния также взяла свое начало в практических задачах Эрланга — заявка, прибор, требование, буфер и другие.
Классическими моделями массового обслуживания являются модели с очередью и модели с отказами. В моделях с очередью заявка (требование), которая обратилась к при бору (ресурсу) и застала его занятым, встает в очередь для ожидания обслуживания. В мо делях с отказами заявка при невозможности получить обслуживание теряется. Существует достаточно много модификаций и комбинаций таких моделей. Во второй половине ХХ века происходит бурное развитие телекоммуникационных сетей, что приводит к необходимости моделировать и проектировать сети передачи данных различной структуры и назначения. Для этого стали применяться модели систем массового обслуживания с повторными вызо вами. В системах такого типа заявка, которая не может получить доступ к ресурсу повторяет попытку захвата ресурса через случайную задержку, а не встает в очередь. В таком случае, в рамках теории массового обслуживания, говорят, что заявка находится на орбите. В ан глоязычной литературе такие модели называются retrial queue (RQ), большой обзор работ по исследованию которых приведен в монографии [3]. Основные принципы функциониро вания моделей систем с повторными вызовами изложены в [4, 5]. Такие модели массового обслуживания возникают при стохастическом моделировании многих протоколов связи и локальных сетей. В частности, данные модели использовались при проектировании алгорит мов доступа и устранения заторов транспортных и канальных уровней модели OSI [6, 7, 8], так как позволяют моделировать поведение системы при различных дисциплинах обслужи вания и параметрах.
Помимо повторных вызовов, существуют ситуации (например, сценарий call-центра), когда обслуживающие единицы имеют возможность делать исходящие запросы на обслужи вание в тот период времени, когда они находятся в простое. Эта модель организации известна как парная коммутация. В [9] получены интегральные формулы для частичных производя щих функций и явные выражения для ожидаемого значения некоторых характеристик про изводительности системы с повторными вызовами и двухсторонней связью (парной комму тацией) в предположении, что длительности входящих и исходящих вызовов соответствуют одинаковым распределениям вероятностей времени обслуживания. Однако на практике это предположение носит ограничительный характер, поскольку разные типы клиентов обычно демонстрируют разное поведение и, следовательно, у них должны быть разные потребно сти в обслуживании. В [10] использовали метод анализа среднего значения для получения некоторых ожидаемых значений, связанных со временем ожидания в очереди на повторное обращение с двусторонней связью и различным распределением времени обслуживания вхо дящих и исходящих вызовов.
Особенность RQ-систем с вызываемыми заявками заключается в том, что в них пред ставлены разные типы заявок, что порождает множество новых дисциплин обслуживания, что, в свою очередь, является мощным инструментом при проектировании и оптимизации систем с множественным случайным доступом к ресурсу.
Также, в современных телекоммуникационных сетях возникают точечные процессы с изменяющейся скоростью поступления заявок. Для моделирования таких процессов в рам ках теории массового обслуживания используется процесс Пуассона с марковской модуля цией (MMPP) [11, 12], потому что он имеет механизм для учета временной неоднородно сти скорости поступления заявок, но даёт аналитически поддающиеся обработке результаты организации очередей [13]. По этой причине MMPP широко используется в исследовани ях сети Интернет, в частности, при помощи MMPP в [14] была построена модель трафи ка, которая точно аппроксимирует LRD (Long Range Dependence) характеристики трассиро вок интернет-трафика. С использованием понятий сеансов и потоков, предлагаемая модель MMPP имитирует реальное иерархическое поведение процесса генерации пакетов пользова телями сети Интернет. Она позволяет генерировать трафик с желаемыми характеристиками с возможностью устанавливать несколько входных параметров, которые имеют четкий фи зический смысл. Результаты доказывают, что поведение трафика в очередях, генерируемого моделью MMPP согласуется с моделью, созданной реальными следами пакетов, собранных на граничном маршрутизаторе при различных сценариях и нагрузке.
Функционирование систем массового обслуживания, предлагаемых к рассмотрению в данной работе соответствуют ряду реальных технологий, использующихся в телекомму никационных сетях. В сетях Ethernet обеспечения множественного доступа к ресурсу ис пользуется CSMA [15, 16] — вероятностный сетевой протокол, а так же его модификация CSMA/CD, имеющая механизм обнаружения коллизий при передаче данных. RQ-система с интенсивностью вызова заявок стремящейся к нулю в полной мере имитирует работу дан ного протокола.
Также, в стеке протоколов TCP/IP на сетевом уровне используется ICMP (Internet Control Message Protocol) [17], который базируется на протоколе IP, однако выполняет ряд служебных функций: передача сообщений об ошибках передачи данных, проверка доступ ности маршрутизатора, а так же отслеживание маршрута отправляемых пакетов. Так как про токол IP не спроектирован для надежной передачи данных (передача дейтаграмм), обеспе чивает успешную доставку пакетов и отслеживание ошибок служебный протокол ICMP. Ис следование модели RQ-системы с парной коммутацией позволяет получить характеристики работы узлов сети при использовании данного протокола, поскольку в отношении принци па его работы также можно использовать термин «парная коммутация». Это означает, что маршрутизатор, принимая и обрабатывая пакеты ICMP, может также вести отправку своих пакетов соседним маршрутизаторам.
Несмотря на большое количество исследований в рассматриваемой области [10, 18, 19, 20, 21], наименее изученной составляющей RQ-систем является выходящий поток за явок [22], иначе, - заявки, покидающие систему по завершении обслуживания. Сведения о выходящем потоке крайне важны, так как в целом характеризуют работу системы и являют ся показательными в задачах, связанных с оптимизацией обслуживания. Усложняют анализ выходящего потока наличие разных типов заявок — объем обслуженных заявок одного ти па напрямую влияет на другой. При различных параметрах обслуживания результат работы системы и степень зависимости выходящих потоков заявок могут существенно разниться.
В данной работе будут рассматриваться несколько моделей RQ-систем: с суммарных выходящим потоком и двумерным, а так же модель системы, интенсивность поступления заявок в котором периодически меняется.
Целью данной работы является разработка и реализация комплекса аналитических, численных и имитационных средств исследования характеристик двумерного выходящего потока узла обработки запросов с повторными обращениями и вызываемыми заявками. В рамках данной цели поставлены следующие задачи:
1. Построить математические модели функционирования узла обработки запросов с по вторными обращениями, вызываемыми заявками и различными входящими потоками обращений.
2. Для предложенных моделей с помощью метода асимптотического анализа получить аналитические формулы аппроксимации двумерной характеристической функции чис ла обслуженных заявок входящего потока и обслуженных вызываемых требований.
3. На основании полученных аппроксимаций характеристической функции реализовать алгоритм вычисления распределения вероятностей, коэффициента корреляции и дру гих числовых характеристик двумерного случайного процесса числа обслуженных за явок входящего потока и обслуженных вызываемых требований.
4. Разработать имитационную модель предложенных математических моделей узлов об работки запросов.
5. Реализовать предложенную имитационную модель математических моделей узлов об работки запросов.
6. C помощью имитационной модели сделать оценку области применимости асимптоти ческих результатов.
7. Провести численный анализ коэффициента корреляции компонент двумерного выхо дящего потока предложенных математических моделей узла обработки запросов.
Работа содержит 70 страниц, 36 рисунков, 7 таблиц, 40 источников.
В первом разделе рассматривается модель системы с простейшим входящим пото ком, во втором разделе — модель система с MMPP. В третьем разделе описана разработка, реализация и функционирование имитационной модели. В четвертом разделе проводится численный анализ асимптотических результатов с использование имитационной модели.
Теория массового обслуживания занимается изучением и математическим модели рованием различных способов организации доступа к распределенному ресурсу [1]. Своим возникновением теория массового обслуживания обязана А.К. Эрлангу, который получил ряд базовых формул для исследования это области, решая практические задачи оптимизации систем телефонной связи [2]. Терминология, используемая в теории массового обслужива ния также взяла свое начало в практических задачах Эрланга — заявка, прибор, требование, буфер и другие.
Классическими моделями массового обслуживания являются модели с очередью и модели с отказами. В моделях с очередью заявка (требование), которая обратилась к при бору (ресурсу) и застала его занятым, встает в очередь для ожидания обслуживания. В мо делях с отказами заявка при невозможности получить обслуживание теряется. Существует достаточно много модификаций и комбинаций таких моделей. Во второй половине ХХ века происходит бурное развитие телекоммуникационных сетей, что приводит к необходимости моделировать и проектировать сети передачи данных различной структуры и назначения. Для этого стали применяться модели систем массового обслуживания с повторными вызо вами. В системах такого типа заявка, которая не может получить доступ к ресурсу повторяет попытку захвата ресурса через случайную задержку, а не встает в очередь. В таком случае, в рамках теории массового обслуживания, говорят, что заявка находится на орбите. В ан глоязычной литературе такие модели называются retrial queue (RQ), большой обзор работ по исследованию которых приведен в монографии [3]. Основные принципы функциониро вания моделей систем с повторными вызовами изложены в [4, 5]. Такие модели массового обслуживания возникают при стохастическом моделировании многих протоколов связи и локальных сетей. В частности, данные модели использовались при проектировании алгорит мов доступа и устранения заторов транспортных и канальных уровней модели OSI [6, 7, 8], так как позволяют моделировать поведение системы при различных дисциплинах обслужи вания и параметрах.
Помимо повторных вызовов, существуют ситуации (например, сценарий call-центра), когда обслуживающие единицы имеют возможность делать исходящие запросы на обслужи вание в тот период времени, когда они находятся в простое. Эта модель организации известна как парная коммутация. В [9] получены интегральные формулы для частичных производя щих функций и явные выражения для ожидаемого значения некоторых характеристик про изводительности системы с повторными вызовами и двухсторонней связью (парной комму тацией) в предположении, что длительности входящих и исходящих вызовов соответствуют одинаковым распределениям вероятностей времени обслуживания. Однако на практике это предположение носит ограничительный характер, поскольку разные типы клиентов обычно демонстрируют разное поведение и, следовательно, у них должны быть разные потребно сти в обслуживании. В [10] использовали метод анализа среднего значения для получения некоторых ожидаемых значений, связанных со временем ожидания в очереди на повторное обращение с двусторонней связью и различным распределением времени обслуживания вхо дящих и исходящих вызовов.
Особенность RQ-систем с вызываемыми заявками заключается в том, что в них пред ставлены разные типы заявок, что порождает множество новых дисциплин обслуживания, что, в свою очередь, является мощным инструментом при проектировании и оптимизации систем с множественным случайным доступом к ресурсу.
Также, в современных телекоммуникационных сетях возникают точечные процессы с изменяющейся скоростью поступления заявок. Для моделирования таких процессов в рам ках теории массового обслуживания используется процесс Пуассона с марковской модуля цией (MMPP) [11, 12], потому что он имеет механизм для учета временной неоднородно сти скорости поступления заявок, но даёт аналитически поддающиеся обработке результаты организации очередей [13]. По этой причине MMPP широко используется в исследовани ях сети Интернет, в частности, при помощи MMPP в [14] была построена модель трафи ка, которая точно аппроксимирует LRD (Long Range Dependence) характеристики трассиро вок интернет-трафика. С использованием понятий сеансов и потоков, предлагаемая модель MMPP имитирует реальное иерархическое поведение процесса генерации пакетов пользова телями сети Интернет. Она позволяет генерировать трафик с желаемыми характеристиками с возможностью устанавливать несколько входных параметров, которые имеют четкий фи зический смысл. Результаты доказывают, что поведение трафика в очередях, генерируемого моделью MMPP согласуется с моделью, созданной реальными следами пакетов, собранных на граничном маршрутизаторе при различных сценариях и нагрузке.
Функционирование систем массового обслуживания, предлагаемых к рассмотрению в данной работе соответствуют ряду реальных технологий, использующихся в телекомму никационных сетях. В сетях Ethernet обеспечения множественного доступа к ресурсу ис пользуется CSMA [15, 16] — вероятностный сетевой протокол, а так же его модификация CSMA/CD, имеющая механизм обнаружения коллизий при передаче данных. RQ-система с интенсивностью вызова заявок стремящейся к нулю в полной мере имитирует работу дан ного протокола.
Также, в стеке протоколов TCP/IP на сетевом уровне используется ICMP (Internet Control Message Protocol) [17], который базируется на протоколе IP, однако выполняет ряд служебных функций: передача сообщений об ошибках передачи данных, проверка доступ ности маршрутизатора, а так же отслеживание маршрута отправляемых пакетов. Так как про токол IP не спроектирован для надежной передачи данных (передача дейтаграмм), обеспе чивает успешную доставку пакетов и отслеживание ошибок служебный протокол ICMP. Ис следование модели RQ-системы с парной коммутацией позволяет получить характеристики работы узлов сети при использовании данного протокола, поскольку в отношении принци па его работы также можно использовать термин «парная коммутация». Это означает, что маршрутизатор, принимая и обрабатывая пакеты ICMP, может также вести отправку своих пакетов соседним маршрутизаторам.
Несмотря на большое количество исследований в рассматриваемой области [10, 18, 19, 20, 21], наименее изученной составляющей RQ-систем является выходящий поток за явок [22], иначе, - заявки, покидающие систему по завершении обслуживания. Сведения о выходящем потоке крайне важны, так как в целом характеризуют работу системы и являют ся показательными в задачах, связанных с оптимизацией обслуживания. Усложняют анализ выходящего потока наличие разных типов заявок — объем обслуженных заявок одного ти па напрямую влияет на другой. При различных параметрах обслуживания результат работы системы и степень зависимости выходящих потоков заявок могут существенно разниться.
В данной работе будут рассматриваться несколько моделей RQ-систем: с суммарных выходящим потоком и двумерным, а так же модель системы, интенсивность поступления заявок в котором периодически меняется.
Целью данной работы является разработка и реализация комплекса аналитических, численных и имитационных средств исследования характеристик двумерного выходящего потока узла обработки запросов с повторными обращениями и вызываемыми заявками. В рамках данной цели поставлены следующие задачи:
1. Построить математические модели функционирования узла обработки запросов с по вторными обращениями, вызываемыми заявками и различными входящими потоками обращений.
2. Для предложенных моделей с помощью метода асимптотического анализа получить аналитические формулы аппроксимации двумерной характеристической функции чис ла обслуженных заявок входящего потока и обслуженных вызываемых требований.
3. На основании полученных аппроксимаций характеристической функции реализовать алгоритм вычисления распределения вероятностей, коэффициента корреляции и дру гих числовых характеристик двумерного случайного процесса числа обслуженных за явок входящего потока и обслуженных вызываемых требований.
4. Разработать имитационную модель предложенных математических моделей узлов об работки запросов.
5. Реализовать предложенную имитационную модель математических моделей узлов об работки запросов.
6. C помощью имитационной модели сделать оценку области применимости асимптоти ческих результатов.
7. Провести численный анализ коэффициента корреляции компонент двумерного выхо дящего потока предложенных математических моделей узла обработки запросов.
Работа содержит 70 страниц, 36 рисунков, 7 таблиц, 40 источников.
В первом разделе рассматривается модель системы с простейшим входящим пото ком, во втором разделе — модель система с MMPP. В третьем разделе описана разработка, реализация и функционирование имитационной модели. В четвертом разделе проводится численный анализ асимптотических результатов с использование имитационной модели.
В рамках данной работы был рассмотрен ряд Марковских систем массового обслу живания с повторными вызовами и вызываемыми заявками, имеющих в качестве источника заявок простейший и MMPP-потоки. Согласно указанной цели исследования был выполнен ряд задач.
Были построены математические модели функционирования рассматриваемых узлов обработки запросов. В зависимости от типа системы, описывающий ее Марковский процесс имеет разную размерность. Так, для системы с одномерным выходящим потоком и простей шим входящим он будет трехмерным— {k(t), i(t), m(t)}, при построении модели с разными типами заявок был добавлен процесс m2(t), а для системы с входящим потоком MMPP- потоком был добавлен процесс n(t), описывающий состояние управляющей цепи MMPP. На основе Марковских процессов были составлены системы уравнений Колмогорова. Для нахождения характеристик выходящего потока был осуществлен переход к характеристиче ским функциям и применен метод асимптотического анализа в предельном условии большой задержки заявок на орбите. В результате были получены формулы (11,22,41) для вычисления асимптотического приближения характеристической функции числа заявок, окончивших об служивание в системе к моменту времени t.
Для вычисления значений распределения вероятностей числа обслуженных заявок были получены формулы (12,23,42), в которых используется преобразование подобия мат риц для вычисления матричной экспоненты и обратное преобразование Фурье, позволяю щее перейти от характеристической функции к явному виду распределения вероятностей. Помимо этого, в разделе 1.2.4 были приведены выкладки для вычисления коэффициента корреляции компонентов двумерного распределения при помощи полученных асимптоти ческих приближений характеристической функции числа обслуженных заявок. Применение указанных формул позволило проводить анализ решений в системе компьютерной алгебры Mathcad и при заданных параметрах системы получать численные характеристики работы системы.
Для оценки применимости полученных асимптотических результатов был разрабо тан и реализован программный продукт, позволяющий проводить имитационное модели рование рассматриваемых систем. В первую очередь, были выделены сущности, принадле жащие к предметной области работы. Далее, была построена объектная модель программы, позволяющая расширять набор используемых элементов теории массового обслуживания при помощи общего для них интерфейса, формализующего изменение состояния элемента при наступлении очередного события в модели. Процесс моделирования, заключающийся в регистрации моментов наступления событий, позволил проводить моделирование итератив но и регистрировать необходимые для анализа характеристики работы системы. Реализация программы представляет собой две составных части - библиотеку, реализованная с учетом построенной объектной модели и оболочку для ее использования с графическим пользо вательским интерфейсом. Раздельная реализация дает возможность легко добавлять новый функционал к имеющемуся.
Процесс работы с программой предусматривает два подхода. В первом случае, по умолчанию, моделирование производится в реальном времени с настраиваемым интерва лом таймера, который отсчитывает проведение следующей итерации моделирования. Дан ный подход дает возможность пользователю получать результаты моделирования и прово дить их предварительный анализ с помощью встроенных графических средств, таких как трехмерное представление распределения вероятностей с возможностью масштабирования и выделения необходимой области с отсечением. Второй способ позволяет быстро полу чить результаты моделирования для последующего анализа с помощью других программ ных средств, для чего реализована функция экспорта данных распределения вероятностей в текстовый формат.
Имитационная модель была протестирована на стабильность получаемых результа тов при помощи расстояния Колмогорова. В ходе эксперимента его значение не превышало 0.002, что говорит о высокой стабильности моделирования.
Из-за асимптотической природы полученных результатов встает вопрос об их при менимости на практике в реальных системах, соответствующих рассматриваемых моделям. Для ее оценки была применена указанная имитационная модель и расстояние Колмогорова, показывающие, насколько соответствует эмпирическое распределение вероятностей пред ложенной модели. Расчеты показали, что при увеличении задержки заявок на орбите ана литические формулы дают более точное распределение вероятностей числа обслуженных заявок. Такой результат является закономерным ввиду того, что аналитические решения бы ли получены при соответствующем асимптотическом условии, однако, даже при меньшей задержке заявок на орбите расчеты оказываются до статочно точными, чтобы их можно бы ло применять на практике. Внимания требует так же распределение вероятностей, получае мое при большей загруженности системы. В таких условиях расчеты становятся еще более точными. В ходе проведенных численных экспериментов значение расстояния Колмогорова не превышало 0.066 — данный результат был получен при увеличенной загрузке системы с MMPP-потоком при интенсивности возврата заявок с орбиты равной 10.
Для рассматриваемых систем был проведен численный анализ корреляции выходя щих процессов, в ходе которого были выявлены некоторые закономерности изменения их корреляции при различных параметрах системы. В частности, при варьировании парамет ров для разных типов заявок коэффициент корреляции всегда меньше нуля и тем меньше, чем больше интенсивность поступления заявок, входящих либо вызываемых, в систему; в то время как при изменении параметров системы для одного типа заявок коэффициент корре ляции принимает как положительные, так и отрицательные значения. Также были найдены параметры системы, при которых компоненты выходящего потока становятся независимы ми. Эти результаты крайне важны для понимая функционирования выходящих процессов системы, однако для интерпретации этого открытия требуется дальнейшее исследование.
В конечном итоге, проведенное исследование позволяет применять полученные в хо де него аналитические решения и результаты численного анализа для изучения функциони рования и отладки реальных систем массового обслуживания [28, 16] с высокой точностью. Крайне важным и трудно исследуемым аспектом функционирования таких систем является выходящих поток обслуженных требований, поскольку он представляет собой характери стику работы системы в совокупности, а она, в свою очередь, зависит от других процессов, происходящих в рамках системы. Помимо этого, исследование выходящего потока требо ваний и его характеристик является необходимым при построении телекоммуникационных сетей, поскольку обслуженные требования одного узла является входящими для другого, что для сетей значительного размера представляет собой еще более важный аспект проектиро вания.
Результаты проведенного исследования были представлены в качестве докладов и об суждались на пяти международных конференциях:
• XIX Международная конференции по информационным технологиям и математиче скому моделированию имени А.Ф. Терпугова (ITMM) (май 2020, Томск);
• VIII Международная молодежная научная конференция «Математическое и программ ное обеспечение информационных, технических и экономических систем» (май 2021, Томск);
• VII Международная конференция «Математика, её приложения и математическое об разование» (МПМО) (сентябрь 2020, Улан-Удэ);
• V Международная конференции по стохастическим методам (ноябрь 2020, Москва);
• VII Международная молодеждная научная конференция «Математическое и программ ное обеспечение информационных, технических и экономических систем» (май 2020, Томск).
Материалы, представленные в работе были опубликованы в трех сборниках материалов кон ференций [29, 30, 31] и одной статье, индексируемой в Scopus [32]. Также, для основного алгоритма имитационной модели было получено свидетельство о регистрации программы для ЭВМ [33].
Были построены математические модели функционирования рассматриваемых узлов обработки запросов. В зависимости от типа системы, описывающий ее Марковский процесс имеет разную размерность. Так, для системы с одномерным выходящим потоком и простей шим входящим он будет трехмерным— {k(t), i(t), m(t)}, при построении модели с разными типами заявок был добавлен процесс m2(t), а для системы с входящим потоком MMPP- потоком был добавлен процесс n(t), описывающий состояние управляющей цепи MMPP. На основе Марковских процессов были составлены системы уравнений Колмогорова. Для нахождения характеристик выходящего потока был осуществлен переход к характеристиче ским функциям и применен метод асимптотического анализа в предельном условии большой задержки заявок на орбите. В результате были получены формулы (11,22,41) для вычисления асимптотического приближения характеристической функции числа заявок, окончивших об служивание в системе к моменту времени t.
Для вычисления значений распределения вероятностей числа обслуженных заявок были получены формулы (12,23,42), в которых используется преобразование подобия мат риц для вычисления матричной экспоненты и обратное преобразование Фурье, позволяю щее перейти от характеристической функции к явному виду распределения вероятностей. Помимо этого, в разделе 1.2.4 были приведены выкладки для вычисления коэффициента корреляции компонентов двумерного распределения при помощи полученных асимптоти ческих приближений характеристической функции числа обслуженных заявок. Применение указанных формул позволило проводить анализ решений в системе компьютерной алгебры Mathcad и при заданных параметрах системы получать численные характеристики работы системы.
Для оценки применимости полученных асимптотических результатов был разрабо тан и реализован программный продукт, позволяющий проводить имитационное модели рование рассматриваемых систем. В первую очередь, были выделены сущности, принадле жащие к предметной области работы. Далее, была построена объектная модель программы, позволяющая расширять набор используемых элементов теории массового обслуживания при помощи общего для них интерфейса, формализующего изменение состояния элемента при наступлении очередного события в модели. Процесс моделирования, заключающийся в регистрации моментов наступления событий, позволил проводить моделирование итератив но и регистрировать необходимые для анализа характеристики работы системы. Реализация программы представляет собой две составных части - библиотеку, реализованная с учетом построенной объектной модели и оболочку для ее использования с графическим пользо вательским интерфейсом. Раздельная реализация дает возможность легко добавлять новый функционал к имеющемуся.
Процесс работы с программой предусматривает два подхода. В первом случае, по умолчанию, моделирование производится в реальном времени с настраиваемым интерва лом таймера, который отсчитывает проведение следующей итерации моделирования. Дан ный подход дает возможность пользователю получать результаты моделирования и прово дить их предварительный анализ с помощью встроенных графических средств, таких как трехмерное представление распределения вероятностей с возможностью масштабирования и выделения необходимой области с отсечением. Второй способ позволяет быстро полу чить результаты моделирования для последующего анализа с помощью других программ ных средств, для чего реализована функция экспорта данных распределения вероятностей в текстовый формат.
Имитационная модель была протестирована на стабильность получаемых результа тов при помощи расстояния Колмогорова. В ходе эксперимента его значение не превышало 0.002, что говорит о высокой стабильности моделирования.
Из-за асимптотической природы полученных результатов встает вопрос об их при менимости на практике в реальных системах, соответствующих рассматриваемых моделям. Для ее оценки была применена указанная имитационная модель и расстояние Колмогорова, показывающие, насколько соответствует эмпирическое распределение вероятностей пред ложенной модели. Расчеты показали, что при увеличении задержки заявок на орбите ана литические формулы дают более точное распределение вероятностей числа обслуженных заявок. Такой результат является закономерным ввиду того, что аналитические решения бы ли получены при соответствующем асимптотическом условии, однако, даже при меньшей задержке заявок на орбите расчеты оказываются до статочно точными, чтобы их можно бы ло применять на практике. Внимания требует так же распределение вероятностей, получае мое при большей загруженности системы. В таких условиях расчеты становятся еще более точными. В ходе проведенных численных экспериментов значение расстояния Колмогорова не превышало 0.066 — данный результат был получен при увеличенной загрузке системы с MMPP-потоком при интенсивности возврата заявок с орбиты равной 10.
Для рассматриваемых систем был проведен численный анализ корреляции выходя щих процессов, в ходе которого были выявлены некоторые закономерности изменения их корреляции при различных параметрах системы. В частности, при варьировании парамет ров для разных типов заявок коэффициент корреляции всегда меньше нуля и тем меньше, чем больше интенсивность поступления заявок, входящих либо вызываемых, в систему; в то время как при изменении параметров системы для одного типа заявок коэффициент корре ляции принимает как положительные, так и отрицательные значения. Также были найдены параметры системы, при которых компоненты выходящего потока становятся независимы ми. Эти результаты крайне важны для понимая функционирования выходящих процессов системы, однако для интерпретации этого открытия требуется дальнейшее исследование.
В конечном итоге, проведенное исследование позволяет применять полученные в хо де него аналитические решения и результаты численного анализа для изучения функциони рования и отладки реальных систем массового обслуживания [28, 16] с высокой точностью. Крайне важным и трудно исследуемым аспектом функционирования таких систем является выходящих поток обслуженных требований, поскольку он представляет собой характери стику работы системы в совокупности, а она, в свою очередь, зависит от других процессов, происходящих в рамках системы. Помимо этого, исследование выходящего потока требо ваний и его характеристик является необходимым при построении телекоммуникационных сетей, поскольку обслуженные требования одного узла является входящими для другого, что для сетей значительного размера представляет собой еще более важный аспект проектиро вания.
Результаты проведенного исследования были представлены в качестве докладов и об суждались на пяти международных конференциях:
• XIX Международная конференции по информационным технологиям и математиче скому моделированию имени А.Ф. Терпугова (ITMM) (май 2020, Томск);
• VIII Международная молодежная научная конференция «Математическое и программ ное обеспечение информационных, технических и экономических систем» (май 2021, Томск);
• VII Международная конференция «Математика, её приложения и математическое об разование» (МПМО) (сентябрь 2020, Улан-Удэ);
• V Международная конференции по стохастическим методам (ноябрь 2020, Москва);
• VII Международная молодеждная научная конференция «Математическое и программ ное обеспечение информационных, технических и экономических систем» (май 2020, Томск).
Материалы, представленные в работе были опубликованы в трех сборниках материалов кон ференций [29, 30, 31] и одной статье, индексируемой в Scopus [32]. Также, для основного алгоритма имитационной модели было получено свидетельство о регистрации программы для ЭВМ [33].