Содержание к диссертации
Введение
1. Модели теории очередей для информационных систем на транспорте 20
1.1. Анализ подходов и методов моделирования систем обслуживания и информационных потоков в них 20
1.2. Теоретическая база моделирования сетей массового обслуживания 34
1.2.1. Структура и параметры сети массового обслуживания 3 5
1.2.2. Значение марковских случайных процессов для исследования сетей массового обслуживания 36
1.2.3. ФормулаЛиттла 39
1.2.4. Вероятностный аппарат теории очередей 41
1.3. Системный анализ и формализация свойств объектов
исследования 46
1.3.1. Принципы организации сети передачи данных информационных систем на транспорте 46
1.3.2. Модель сегмента сети передачи данных в виде сети массового обслуживания 53
1.3.3. Информационные потоки подсистемы поддержки принятия решений в автоматизированной системе управления станцией 60
1.4. Разработка методов численного анализа характеристик
узлов сетей массового обслуживания 65
1.4.1. Метод свертки и его модификация 66
1.4.2. Метод анализа средних значений и его модификации 71
1.5. Выводы 83
2. Стохастические модели информационных систем на транспорте в условиях потоков с пиковыми нагрузками 85
2.1. Анализ условий моделирования 86
2.1.1. Анализ структурных показателей потоков 86
2.1.2. Анализ пиковых факторов при моделировании 92
2.2. Анализ моделей для информационных потоков 95
2.2.1. Марковские модели и модели по аналогии с физическими явлениями 95
2.2.2. Обоснования выбора вида модели потока 97
2.2.3. Методы предварительного статистического анализа потоков 102
2.2.4. Моделирование базовых случайных распределений и процессов 106
2.2.5. Распределение числа заявок в системе с ординарным входным потоком общего типа 109
2.3. Модели потоков с пиковыми нагрузками 111
2.3.1. Чисто скачкообразные процессы как инструмент для моделирования пиковых нагрузок 111
2.3.2. Основные определения и классификация распределений с тяжелыми хвостами 118
2.3.3. Статистический анализ потоков с пиковыми
нагрузками 126
2.3.4. Генерация а -устойчивых последовательностей случайных величин 129
2.3.5. Распределение времени обращения к системе массового обслуживания в случае пиковых нагрузок 133
2.4. Модели с использованием распределения направленных значений 138
2.4.1. Предпосылки использования методов круговой статистики 138
2.4.2. Статистические круговые характеристики потоков... 140
2.4.3. Модифицированные методы нахождения индекса устойчивости 145
2.5. Выводы 153
3. Статистическая автомодельность елетрафика в информационных системах 155
3.1. Свойство автомодельности случайных процессов 155
3.2. Моделирование автомодельных процессов Леви 157
3.3. Моделирование симметричных автомодельных процессов Леви с трендом 162
3.4. Некоторые автомодельные процессы, не являющиеся процессами Леви 165
3.5. Моделирование фрактального броуновского движения... 167
3.5.1. Моделирование с использованием спектральной плотности последовательности А 168
3.5.2. Моделирование последовательности А
с использованием скользящего среднего 173
3.53. Моделирование последовательности А на основе триангуляции ковариационной матрицы 174
3.5.4 Моделирование последовательности А с использованием дискретного преобразования Фурье 177
3.6. Автомодельность процессов в широком смысле 183
3.7. Статистический анализ автомодельных потоков 184
3.8. Автомодельность потоков в широком смысле и свойство сильного последействия 190
3.9. Выводы 200
4. Среда визульнои разработки и имитационного моделирования информационных систем с использованием методов объектно- ориентированного проектирования 202
4.1. Имитационное и визуальное моделирование: подходы и методологии 203
4.1.1. Сравнительный анализ стандартов и спецификаций компьютерного моделирования 203
4.1.2. Общие положения имитационного моделирования 212
4.2. Разработка методики моделирования информационных систем 215
4.3. Визуальная среда имитационного моделирования 221
4.3.1. Программная реализация объектно-ориентированной
технологии при разработке сложных программных
комплексов 221
4.3.2. Создание и редактирование модели предметной области. Описание среды 231
4.3.3. Архитектура классов объектов 241
4.3.4. Набор функций и алгоритмы их выполнения 249
4.4. Выводы 254
5. Практическое применение среды визуальной разработки и имитационного моделирования информационных систем для оценки качества функцио нирования информационно-управляющих систем на транспорте
5.1. Моделирование работы железнодорожных информацион
но-управляющих систем и их основных компонентов 257
5.1.1. Алгоритм моделирования работы пакетных маршрутизирующих коммутаторов и телекоммуникационных каналов... 257
5.1.2. Алгоритм моделирования работы сервера приложений... 268
5.2. Оценка параметров информационных потоков в автомати
зированных информационно-управляющих системах 280
5.2.1. Формирование и агрегирование экспериментальных выборок 280
5.2.2. Оценка параметров при наличии хвоста распределения... 283
5.2.3. Оценка параметров при наличии свойств автомоделъности и сильного последействия 289
5.2.4. Оценка параметров методами круговой статистики 297
5.3. Выводы 3 00
Заключение 302
Список литературы
- Структура и параметры сети массового обслуживания
- Анализ пиковых факторов при моделировании
- Моделирование симметричных автомодельных процессов Леви с трендом
- Общие положения имитационного моделирования
Введение к работе
Актуальность темы. Начиная с 1997 г. автоматизированные системы управления железнодорожным транспортом (АСУЖТ) поэтапно переоборудовались в соответствии с современными информационными технологиями, базирующимися на распределенных компьютерных сетях с пакетной коммутацией данных. Этот процесс не сопровождался комплексными исследованиями, предваряющими проектирование и использование информационных систем как в центрах управления транспортными перевозками, так и на рабочих местах основных пользователей этих систем. В результате не были учтены особенности функционирования крупных железнодорожных узлов, потребности, как руководящего звена, так и непосредственных исполнителей, участвующих в управлении перевозочным процессом, в качественном и своевременном обеспечении необходимой информацией, требующейся для оперативного принятия ответственных решений, что привело к резкому снижению качества информационного обслуживания важнейших АСУЖТ, нарушению стабильности и безотказности их функционирования. Это связано, с одной стороны, с масштабами внедрения новых технологий в такую крупнейшую отрасль, как железнодорожный транспорт, с большой разнородностью технологических объектов, обеспечивающих их информационную поддержку, а также в различиях технической базы основных источников, требующих информационного обслуживания. С другой стороны, отсутствовала технология, опирающаяся на теоретические предпосылки и учитывающая одновременное функционирование в АСУЖТ разнородных объектов, обеспечивающих работу информационно-управляющих систем. В этой связи руководством ОАО «РЖД» перед исследователями была поставлена задача устранения указанных недостатков.
Основные структурные элементы важнейших АСУЖТ, а именно, серверы баз данных, РРеб-серверы, серверы файловых архивов и корпора-
тивной электронной почты, активное телекоммуникационное оборудование, располагаются, как правило, на информационно-вычислительных центрах железных дорог, что дает возможность осуществления контроля за использованием информационных ресурсов и получения статистических данных по различным видам информационных потоков, как в реальном времени, так и за любой предшествующий период, поскольку протоколирование запросов к серверу баз данных ведется непрерывно.
Анализ работы указанных систем позволил выявить основные факторы, приводящие к нарушению ритмичности и безотказности их функционирования. К таким факторам относятся, в первую очередь, критические нагрузки на информационную сеть, возникающие вследствие как нештатных ситуаций, так и циклических изменений в потребности информационных ресурсов, связанных с особенностями технологических процессов на транспорте. Указанные пиковые факторы проявляются в резком увеличении активности сетевых подключений вследствие обращения огромного числа пользователей к одним и тем же информационным ресурсам и невозможности автоматизированных систем своевременно обеспечить всех пользователей актуальной информацией.
К основным математическим методам исследования информационных систем (ИС) относится теория массового обслуживания (ТМО) или теория очередей.
Современное состояние ТМО обеспечили работы А.К. Эрланга и А.А. Маркова, А.Я. Хинчина, А.А. Боровкова, Б.В. Гнеденко, И.Н. Коваленко, Т.Л. Саати, Д.Г. Кендалла, Дж. Литтла, П.П. Бочарова, А.В. Печин-кина.
Однако, анализируя возможность использования существующих методов теории очередей для разработки математических моделей современных ИС, можно сделать вывод о том, что возникают проблемы, которые этими методами либо не решаются, либо требуют существенного развития
7 для их решения. В связи с этим, весьма актуальной становится задача развития методов теории очередей и сетей массового обслуживания (СеМО).
Исследования в области СеМО проводились Дж.Р. Джексоном, В. Гордоном, Г. Ньюэллом, Ф. Баскетом, К.М. Чанди, P.P. Мунцом, Ф.Г. Па-лачиосом, Ф.Р. Келли, Е. Геленбе. Из современных работ по СеМО следует выделить многочисленные труды В.А. Ивницкого, а также М. Шварца, В.А. Жожикашвили.
Существующий разрыв между достижениями в области аналитических исследований телекоммуникационных сетей средствами СеМО и их практической реализацией определил необходимость развития аппарата имитационного моделирования в применении к указанным системам.
Большой вклад в развитие теории моделирования компьютерных сетей средствами ТМО внесли Л. Клейнрок, В.М. Вишневский. В теории телетрафика можно выделить работы В.Е. Леланда, М.С. Такку, В. Вил-линджера, В.В. Крылова, B.C. Лагутина, СИ. Степанова.
При моделировании ИС в виде СМО и СеМО важнейшими характеристиками становятся законы распределения случайных величин и случайные процессы, в соответствии с которыми происходит поступление требований в систему и их обслуживание. В этой области следует отметить работы А.Н. Колмогорова, Ю.В. Прохорова, Г. Пойя, П. Леви, В. Феллера, А.Я. Хинчина, Дж. Дуба, М. Лоэва, Е. Лукача, Б. Мандельброта, А.В. Скорохода, А.Н. Ширяева, В.Н. Золотарева, А.В. Булинского, Г.Г. Галустова.
Теории и языкам имитационного моделирования (ИМ) посвящены работы Дж. Гордона, Е. Сейджвика, А. Лоу, В. Кельтона, В.В. Емельянова, В.М. Курейчика, В.В. Курейчика. Работы Г. Буча, П. Коуда, позволили создавать системы моделирования и программирования с использованием объектно-ориентированных принципов, труды М. Фоулера - с возможностями программного рефакторинга.
Таким образом, были обозначены проблемы, для решения которых потребовалось привлечение математических методов в сочетании с имита-
8 ционным моделированием и разработкой программного обеспечения. Отметим, что указанные проблемы в настоящее время далеки от всестороннего и законченного исследования. Поэтому задачи, решению которых посвящена диссертация, относятся к актуальным проблемам проектирования и модернизации ИС, построенных на базе телекоммуникационных сетей с пакетной коммутацией данных.
Цель и задачи исследования. Основной целью и задачами исследования является развитие теории и разработка нового класса случайных процессов для моделирования современных ИС на транспорте.
Для достижения поставленной цели необходимо решение следующих задач.
Разработка адекватных моделей ИС на транспорте, имеющих сложную структуру и множество параметров в виде СеМО.
Разработка стохастических моделей информационных потоков, отражающих реальные процессы, возникающие в ИС.
Разработка численных методов и алгоритмов анализа моделей (систем обслуживания) и модификация существующих методов.
4. Разработка методов оценки параметров моделей с использованием
средств современной математической статистики.
Разработка эффективных генераторов для исследуемого класса стохастических моделей процессов.
Развитие методов имитационного моделирования и создание программного комплекса для оценки качества обслуживания в ИС на основе объектно-ориентированного подхода с возможностями программного ре-факторинга.
Экспериментальная проверка разработанных теоретических подходов и положений на адекватность в практических задачах ИС на транспорте.
Методы исследования основываются на использовании фундаментальных исследований в области случайных процессов, математической
9 статистики, теории систем и сетей массового обслуживания, теории моделирования дискретных систем. При разработке моделей информационных потоков использовались методы генерации и оценки устойчивых распределений, методы статистики направленных значений. Для моделирования телетрафика в информационных системах применялись автомодельные процессы типа Леви, модели фрактального броуновского движения, а также их обобщения.
Практическая проверка разработанных моделей и методов осуществлялась путем программной эмуляции, проведения имитационных экспериментов на модельных и на реальных объектах ИС на транспорте.
Научная новизна работы заключается в теоретическом обобщении и решении научно-технической проблемы, связанной с разработкой нового подхода к моделированию потоков информационного обмена в телекоммуникационных системах и сетях, в разработке на его основе нового класса моделей случайных процессов, отражающих и позволяющих учесть при анализе и проектировании новые свойства исследуемых систем и процессов в них и имеющих важное значение для оценки качества функционирования и информационного обслуживания ИС.
К наиболее существенным научным результатам работы относятся следующие.
1. На основании анализа особенностей функционирования существующих ИС на транспорте:
выявлены проблемы информационного взаимодействия в подсистемах управления транспортной отраслью и факторы снижения качества предоставления информационных услуг;
выявлены причинно-следственные связи изменений режимов стабильного функционирования информационно-управляющих систем;
определены технические элементы телекоммуникационных систем и структурные показатели потоков, оказывающие наибольшее влияние на производительность этих систем, и, как следствие, качество обслуживания.
2. На основании анализа статистических данных в исследуемых сис
темах:
выявлены наиболее значимые для моделирования характеристики случайных процессов, протекающих в ИС, и установлена необходимость учета пиковых нагрузок, периодических зависимостей в загрузке информационных сетей на транспорте, а также свойств автомодельности и сильного последействия информационных потоков в них;
выполнено обоснование выбора вида модели потока, и предложен широкий класс чисто скачкообразных стохастических процессов, использующих конструкцию процессов типа Леви;
предложены законы для моделирования информационных потоков с пиковыми нагрузками на основе использования чисто скачкообразных процессов, являющихся и не являющихся процессами Леви, и вероятностных распределений с тяжелым хвостом;
разработаны методы расчета числовых характеристик СеМО на основе моделей, использующих распределения направленных значений;
практически реализована комплексная методика исследования информационных потоков в автоматизированной системе управления железнодорожным узлом, позволившая выполнить экспериментальную оценку параметров потоков информации, а также проверить наличие в них свойств пиковых нагрузок, автомодельности и цикличности.
3. На основании анализа существующих численных методов модели
рования ИС и случайных процессов:
- разработаны модификации методов численного анализа характери
стик узлов сетей массового обслуживания: на основе алгоритмов вычисле
ния сверток быстрыми преобразованиями Фурье и приближенного алго
ритма анализа средних значений параметров сети, позволившие сущест
венно повысить быстродействие алгоритмов, уменьшить их вычислитель
ную сложность и снять ограничения, существующие в информационных
системах на транспорте на бесконечное число обслуживающих устройств и тип входного потока;
предложен новый метод генерации а -устойчивых последовательностей случайных величин;
разработаны новые методы нахождения индекса устойчивости: метод оценки параметров кругового симметричного а -устойчивого распределения по методу тригонометрических моментов и модификация оценки Хилла;
получены новые типы моделей и эффективные алгоритмы генерации самоподобного Леви процесса; симметричных автомодельных процессов Леви с трендом; фрактального броуновского движения с использованием спектральной плотности последовательности, скользящего среднего, на основе триангуляции ковариационной матрицы, с использованием дискретных преобразований Фурье;
получены соотношения для определения статистических характеристик потока в случае сильного последействия в последовательности приращений стохастического процесса.
4. Разработана методология имитационного моделирования транспортных ИС на основе структурной и параметрической идентификации узлов и потоков заявок в системах обслуживания и схем информационного взаимодействия функциональных компонентов систем с пакетной коммутацией данных, на базе которых построено большинство современных ИС:
разработана методика моделирования ИС в визуальной среде с использованием наиболее подходящих для исследуемых объектов принципов имитационного моделирования существующих программных комплексов, стандартов языков моделирования на основе С4Ж-технологий, принципов объектно-ориентированного проектирования и программирования и возможностей программного рефакторинга;
разработана полнофункциональная система ИМ информационных потоков в системах телекоммуникаций на транспорте в виде программного
12 комплекса, который позволяет применять его для моделирования предметно-ориентированных ИС: задавать структуру и параметры системы, генерировать потоки заявок и телетрафик, рассчитывать временные характеристики подсистем ИС, определять причины снижения качества обслуживания по сравнению с проектными характеристиками и формировать рекомендации по устранению этих причин.
5. На основании анализа проблем обеспечения информационной поддержки существующих ИС на транспорте разработаны модели численного анализа для информационно-вычислительных центров железных дорог и систем поддержки и принятия решений в автоматизированных системах управления железнодорожными станциями:
с применением «Среды визуальной разработки и имитационного моделирования информационных систем с использованием методов объектно-ориентированного проектирования» на уровне специалиста предметной области разработаны алгоритмы моделирования основных узлов обслуживания сетевых интегрированных АСУЖТ, впервые представленные средствами СеМО;
разработана методика статистического анализа данных для подсистемы поддержки принятия решений в автоматизированной системе управления станцией.
Практическая ценность. Предложенные теоретические подходы к представлению ИС в виде СеМО и формальному описанию случайных процессов в них используются в интегрированных информационно-управляющих системах железнодорожного транспорта для оценки качества их функционирования.
Практическую ценность представляют следующие результаты.
1. Разработан, внедрен и адаптирован комплекс программ (КП) для моделирования работы АСУЖТ Северо-Кавказской железной дороги (СКжд). Внедрение этого комплекса позволило определить «узкие места» в системах управления и предложить обоснованные рекомендации по их
13 устранению.
Разработаны и внедрены в АСУЖТ СКжд методы моделирования и оценки потоков данных, позволяющие повысить эффективность и качество функционирования действующих систем поддержки принятия решений в автоматизированных системах управления сортировочным процессом.
Разработан комплекс программ, в котором практически реализованы методы численного расчета подсистем в составе сети передачи данных «ОАО» РЖД, позволяющие оценить их производительность и, как следствие, повысить эффективность и устойчивость функционирования сети.
На основе статистического анализа потоков информации в системах СИРИУС, автоматизированной системе оперативного управления перевозками (АСОУП) и автоматизированной системе управления станцией (АСУ СТ) были выявлены следующие закономерности:
наличие пиковых режимов работы ИС, как случайных, возникающих в случае нештатных ситуаций, так и циклических, связанных с особенностями технологического процесса, приводящих к сбоям в работе систем, неудовлетворительному качеству обслуживания клиентов, несвоевременности предоставления информации, а также предложены методы по устранению этих недостатков в работе АСУЖТ;
наличие свойства автомодельности и сильного последействия в телетрафике, свидетельствующие о долговременной корреляционной зависимости в данных, что приводило к неверной оценке основных показателей работы информационных подсистем.
В соответствии с выявленными особенностями потоков данных разработаны:
- методика оперативного статистического анализа свойств информа
ционных потоков с использованием как наиболее распространенных мето
дов оценки параметров потоков, так и разработанных автором;
- методика оперативного прогноза нагрузки в реальном времени на
информационные подсистемы сети обслуживания, который может быть
распространен на различные масштабы времени и использован для плани
рования пропускной способности;
- методика анализа и контроля использования АСОУП и СИРИУС.
Достоверность научных и практических результатов работы.
Научные положения, результаты и выводы, сформулированные в диссертации, строго аргументированы. Сформулированные в работе законы моделирования, разработанные численные методы и алгоритмы основываются на известных в теории очередей, теории случайных процессов, теории телетрафика фундаментальных понятиях и подходах. Достоверность теоретических результатов подтверждается четкостью постановок задач, формулировок основных утверждений и определений, корректностью математических доказательств. Достоверность результатов и выводов подтверждается данными экспериментальных исследований и имитационных экспериментов, а также результатами эксплуатации разработанных методов и комплексов программ, внедренных в качестве подсистем в функционирующие ИС.
Реализация результатов работы. Работа выполнялась в рамках утвержденной Правительством РФ Федеральной целевой программы «Модернизация транспортной системы России 2002 - 2010 годы», подпрограмма «Железнодорожный транспорт», а также в рамках программы «Фундаментальные и поисковые научно-исследовательские работы», выполняемой по заказу Департамента Технической политики ОАО «РЖД» по следующим тематикам, непосредственным исполнителем которых являлся автор: «Методология исследования и синтеза информационно-управляющих систем железнодорожного транспорта на основе теории массового обслуживания» (2003 г., № 680/28 от 28.05.2003); «Автоматизация железнодорожных комплексов (сортировочных станций): проблемы моделирования и управления» (2004 г., № 535/770 от 7.09.2004); «Методы и
15 средства контроля и диагностирования устройств железнодорожной автоматики и связи» (2005 г., № 835/312 от 24.06.2005), раздел «Модели и методы обработки информации в контрольно-диагностическом комплексе (КДК) устройств сортировочной станции»); «Обработка информации в подсистемах и устройствах комплексной системы автоматизированного управления сортировочным процессом (КСАУ СП)» (2006 г.).
Работа поддержана докторским грантом Ростовского государственного университета путей сообщения и грантом Российского фонда фундаментальных исследований 04-01-002 77-а (2004 - 2006 г.г.).
Результаты работы прошли успешную апробацию, внедрены и используются: на информационно-вычислительном центре СКжд в системах АСОУП и СИРИУС; в Российском научно-исследовательском и проектно-конструкторском институте информатизации, автоматизации и связи МПС России в системе поддержки принятия решений автоматизированной системы управления станцией СППР АСУ СТ.
Разработанные автором программные комплексы зарегистрированы в отраслевом фонде алгоритмов и программ.
Научные результаты работы используются в учебном процессе Ростовского государственного университета путей сообщения.
Основные результаты, выносимые на защиту.
Теоретический подход к моделированию ИС, опирающийся на аппарат теории очередей, предназначенный для анализа эксплуатационных показателей, модернизации и проектирования автоматизированных информационно-управляющих систем на транспорте.
Модели потоков в СМО, которые учитывают пиковые нагрузки и периодичность поступления требований, в которых использован класс чисто скачкообразных процессов типа Леви.
Законы и алгоритмы моделирования телекоммуникационного трафика со свойством автомодельности: процессы Леви, в том числе симметричные и с трендом; процессы, не являющиеся процессами Леви, но про-
являющие указанное свойство; модели фрактального броуновского движения с использованием спектральной плотности последовательности, скользящего среднего, триангуляции ковариационной матрицы, с использованием быстрых преобразований Фурье, а также процессов, автомодельных в широком смысле и со свойством сильного последействия.
Численные методы, их модификации и алгоритмы реализации. В области СеМО: модификации методов свертки и анализа средних значений. В области устойчивых распределений: распределение времени обращения к СМО в случае пиковых нагрузок и метод нахождения индекса устойчивости. В области распределений направленных значений: метод оценки параметров кругового симметричного устойчивого распределения.
Предметно-ориентированный программный комплекс для имитационного моделирования ИС с использованием методов объектно-ориентированного проектирования и программирования и программного рефакторинга.
Методы оценки параметров информационных потоков данных в ИС при наличии: тяжелого хвоста распределения; свойств автомодельности и сильного последействия; циклического изменения информационных нагрузок.
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на Всероссийских симпозиумах по прикладной и промышленной математике и Школах-коллоквиумах по стохастическим методам (2001 - 2006 г.г., Сочи, Йошкар-Ола, Петрозаводск, С.-Петербург, Ростов-на-Дону, Кисловодск); на Межведомственных и международных конференциях «Телекоммуникационные и информационные технологии на транспорте России» (2001, 2003, 2005, 2006 г.г.); на Международных конференциях «Математика. Экономика. Образование» (2002 г., 2006 г., Новороссийск); на Международном симпозиуме «Ряды Фурье и их приложения» (2006 г., Новороссийск); на международной научно-технической конференции «Новые технологии управления движени-
17 ем технических объектов» (2002 г., Новочеркасск); международной научно-практической конференции «Актуальные проблемы информатики и информационных технологий» (2005 г., Тамбов); на Всероссийской научно-практической конференции ученых транспортных вузов, инженерных работников и представителей академической науки «Современные технологии - железнодорожному транспорту России» (2006 г., Хабаровск); на Международной научно-практической конференции «Моделирование. Теория, методы и средства» (2006 г., Новочеркасск); на научно-теоретических и научно-практических конференциях профессорско-преподавательского состава Ростовского государственного университета путей сообщения (2000 - 2006 г.г.).
Публикации. Полученные в диссертации теоретические и практические результаты нашли свое отражение в 52 печатных работах, в том числе 2-х монографиях, 28 статьях в центральных научных журналах, в 1 учебнике и 1 учебном пособии.
Структура и объем работы. Диссертация состоит из введения, 5 глав, заключения, 2-х приложений, списка литературных источников. Общий объем диссертации составляет 345 стр., из которых объем основного текста составляет 298 стр.
Во введении обосновывается актуальность проведенных исследований, формулируются цели и задачи исследований, приводятся основные научные и практические результаты, а также кратко рассматривается содержание диссертации по главам.
В 1 главе выполнен анализ современного состояния в области исследования ИС, построенных на базе компьютерных сетей с пакетной передачей данных (СПКД), методами теории очередей. Дана характеристика объектов исследования, и предложены принципы моделирования исследуемых ИС в виде сетей массового обслуживания. Предложены модифи-
18 кации существующих алгоритмов численного анализа характеристик
СеМО.
В главе 2 исследуются стохастические модели потоков в СМО с учетом периодичности и пиковых нагрузок. При этом выполнен анализ существующих моделей, и предложен широкий класс чисто скачкообразных стохастических процессов, использующих конструкцию процессов Леви, позволяющих моделировать потоки с заявленными свойствами. В качестве ядра модели рассматривается класс устойчивых распределений с тяжелыми хвостами. Изложены методы статистического анализа моделей, и описан генератор рассматриваемого класса случайных процессов.
Структура и параметры сети массового обслуживания
Одним из базовых понятий в теории очередей является понятие случайного процесса. Это объясняется тем, что практически все процессы, протекающие в СеМО, являются случайными: входные потоки заявок на обслуживание, длительность обслуживания, циркуляция заявок внутри сети и т. д.
Определение 1.1.
Векторным случайным процессом называется векторная функция X(t), teT, значения X{t) которой при каждом t являются векторными случайными величинами.
Под параметром t здесь понимается время, а в качестве множества Т моментов рассматриваются два множества Т = {0,\,-} и Г = [0,оо). В первом случае говорят о случайном процессе с дискретным временем, во втором - с непрерывным временем. Множество значений случайного процесса будем обозначать N. Конечномерные распределения данного случайного процесса определяются совместными распределениями вероятностей его значений X{tx),..., X(tn) при различных /,,..., tn. Исследования в области СеМО как более ранние, так и современные показывают, что наиболее известным аппаратом их описания являются марковские случайные процессы.
Определение 1.2 [70]. Случайный процесс X(t), t є Т, называется марковским, если VTcN, я 0, tl ... tn t, tteT, / = 1,..., и, t єТ, имеет место равенство р{дг(г)е О=пЧ..., я)=пМ}=р{дг(0бУ я)=пМ}, П(/)є7, / = 1,...,и. П Определение 1.3. Функция P(t ,n,t,Y) = p{x(t) є Y\X{t ) = n} для марковского процесса X(f), t t называется функцией переходных вероятностей. П
Особая роль марковских случайных процессов и многообразие их применения в различных прикладных задачах объясняется тем, что для них «будущее» (X(t)eY) не зависит от «прошлого» (гг ,...,Гг ) при извест М ном «настоящем» (П ). Этот факт позволяет, рассматривая переходную функцию в моменты времени t и t + At при А/ - 0, получать для нее систему обыкновенных дифференциальных уравнений или систему дифференциальных уравнений в частных производных, что дает возможность получения как точных аналитических решений для переходных функций, так и применения приближенных методов: численных методов, имитационного моделирования. Для целей исследования СМО и СеМО важное значение марковских процессов состоит в том, что процесс функционирования практически любой такой системы можно с достаточной степенью адекватности описать тем или иным видом марковского процесса.
Еще одним фундаментальным понятием теории очередей является понятие состояния системы (сети). Оно введено для того, чтобы можно было судить о качестве функционирования системы в каждый момент времени и в будущем. Определение 1.3 (а) [76]. Состоянием СМО (СеМО) называется вектор с таким компонентами, чтобы его задание в любой момент времени полностью определяло дальнейшее развитие процесса функционирования СМО (СеМО), или, на основе определения 1.2, можно сформулировать следующее определение Определение 1.3(6). Состоянием СМО (СеМО) называется вектор, изменение которого во времени представляет собой марковский процесс. О
Опишем этапы общей методологии численного приближенного определения параметров СеМО и СМО, в основе которых лежат марковские процессы.
1. Определяется требующийся параметр СМО (СеМО).
2. Если его изменение во времени является марковским процессом, то для вероятностей его состояний составляется соответствующая система уравнений баланса, производится ее решение и определяется нужный параметр.
3. Если его изменение во времени не является марковским процессом, то производится дробление этой характеристики (состояния) до тех пор, пока изменение раздробленного состояния во времени не станет марковским процессом. Далее повторяется 2 этап.
4. Определяются вероятности нераздробленных состояний суммированием (интегрированием) и требующийся параметр.
Анализ пиковых факторов при моделировании
Одним из главных требований к ИС является обеспечение высокого качества обслуживания пользователей. Выбор системы показателей, характеризующих качество их обслуживания, относится к числу наиболее важных и сложных проблем нормирования параметров функционирования как всей сети передачи данных, так и ее элементов, что показано в [87].
Согласно рекомендациям [107] качество обслуживания определяется как степень удовлетворенности пользователя обслуживанием на сети. Его составляет совокупность таких свойств, как обеспеченность обслуживанием, эксплутационная пригодность обслуживания, эффективность и целостность обслуживания (рис. 2.1). Данное определение, на взгляд автора, следует дополнить следующими требованиями: регламентированный доступ к информационным ресурсам, обеспечение необходимого уровня защищенности от помех в каналах передачи данных и пунктах обработки информации, невосприимчивость к аварийно значимым внутренним и внешним возмущениям системы.
Практическим аспектом применения работы является анализ пограничных режимов, предельных режимов и режимов пиковой нагрузки. Одна из причин, приводящих к этому состоянию - это пиковые факторы (ПКФ) - явления, действие которых может привести к нарушению работоспособности ИС или ее элементов, а, следовательно, к резкому снижению качества обслуживания. Пиковые факторы могут влиять как на всю сеть, так и на какой-либо ее элемент или группу элементов.
Источники ПКФ многочисленны и разнообразны. Часто обобщением ПКФ являются дестабилизирующие факторы, однако подчеркнем, что в такой термин во многих случаях вкладывается смысл преднамеренного нарушения работоспособности телекоммуникационной инфраструктуры. Вопросы классификации ПКФ еще требуют проработки. Например, в [79] предложены следующие признаки классификации:
1) место расположения источника дестабилизирующих факторов относительно ИС, определяющее возможности сети в части его ликвидации или уменьшения его влияния (внутренние или внешние);
2) пространственно-временные показатели воздействий, характеризующие масштабы возможных одновременных разрушений или нарушений работоспособности элементов сети (локальные или массовые);
3) характер воздействий, определяющий преднамеренные или непреднамеренные действия.
Можно предложить вариант классификации ПКФ (рис. 2.2) на основе перечисленных признаков с указанием свойств ИС, на которые влияют эти факторы.
Такая или подобные классификации источников ПКФ позволяют выявить стратегические направления формирования и использования ресурсов ИС для обеспечения ее функционирования в условиях, создаваемых деятельностью этих источников.
Задача исследования качества обслуживания без учета ПКФ хорошо изучена. Однако, при наличии последних традиционные методы исследования на основе теории вероятностей (и также ТМО) не могут быть адекватно применены. При решении этой задачи потребуется разработка моделей потоков с использованием специальных видов распределений на базе теории случайных процессов, причем модели должны учитывать различные проявления и свойства ПКФ, в частности, как предложено автором в работах [42, 96]. В пределах данной главы будут выявляться некоторые, недостаточно изученные свойства моделей с ПКФ, и предлагаться новые методы моделирования и оценки стохастических процессов в ИС.
Переходя к построению математических моделей статистических данных, получаемых в результате анализа потоков информации в СПКД, целесообразно произвести анализ подходов, применяемых при моделировании телекоммуникационного трафика. Этот обзор, выполненный в работе [65], позволит также в дальнейшем, опираясь на известные результаты, выявить отличия, предлагаемые в комплексе моделей данной работы.
Модели информационных потоков, применяемые в анализе сетей с пакетной коммутацией данных, можно разделить на два вида.
Первыми моделями, предложенными для СПКД, были модели, основанные на марковских процессах. Это было связано с тем, что сети телефонных коммуникаций успешно описывались этими моделями. Можно выделить четыре вида марковских моделей для описания информационных потоков в СПКД. 1. Пуассоновские процессы с лежащими в их основе марковскими цепями, то есть модели с непрерывным временем и одиночным поступлением пакетов [184, 227, 264], называемые ММРР. 2. Марковские процессы пакетного поступления с непрерывным временем с групповым поступлением пакетов [69, 115] ВМАР. 3. Марковские процессы пакетного поступления с дискретным временем с групповым поступлением пакетов [146] D-BMAP. 4. Бернуллиевские процессы на основе марковских цепей [146] ММВР.
Моделирование симметричных автомодельных процессов Леви с трендом
Пусть задан интервал [0,г], который разбит на п элементарных ин Т тервалов 1/,-1, ]"=1, tQ = 0, tn=T. Длина каждого интервала hn= — . Рас п смотрим интервал [О, і]. Назовем этот интервал стандартным интервалом моделирования. В соответствии с разбиением интервала [0,Г] получим разбиение стандартного интервала [T/_1,T/J, где т,- = —, при этом длина каждого из интервалов разбиения р = —. В силу автомодельности процесса п Law[XT ,i = 1,...,nj- Law\THXt ,i = \,...nj. Поэтому, получив выборку на стандартном интервале, с помощью последнего соотношения можно получить выборку на произвольном интервале [О,г]. Из свойств процесса Леви случайные величины (А,- =ХТ. -Xz, J1 независимы и одинаково распределены. При этом Law( ) = Law{XXrJ=Law(X1]).
Пусть ф/(9) = Еехр(/0Х/) - характеристическая функция, тогда в силу однородности и независимости приращений фт (0) = фДб)фДб). Реше 158 ниєм последнего уравнения является функция ф, (б) = exp(ft/(9)). Функцию v/(0) называют кумулянтой. Положим в последнем соотношении t = \, в результате получим ф, (О) = ехр(\/(9)) - характеристическая функция для Law{Xx). Из автомодельности следует, что это распределение является устойчивым распределением с индексом устойчивости а = —. Следователь Н но, характеристическая функция имеет вид (2.6). Как уже отмечалось выше, наиболее интересным случаем для моделирования является симметричный случай (J3 = 0). В этом случае характеристическая функция Ф,(Є) = ехр(-ааЄа). Рассмотрим автомодельный процесс Леви Xtc характеристической функцией ф,(0) = ехр[-0а ), тогда для процесса Xt справедливо равенство Xt = GX, . Пусть v - стандартная нормальная случайная величина, а Ь, независящая от нее случайная величина, большая нуля. Потребуем, чтобы характеристическая функция Ф (Є) = Фі(Є) = ехР(-0а).
Вычислим Eexp(/0 v). Для этого воспользуемся тождеством Eexp(/0v) = E(E(exp(z0 v)/)). Условное математическое ожидание E(exp(/0v)/ ) = exp № і і2 Пусть X = 0 , С, = —, тогда Eexp(/0 v) = Eexp(- ).
Сопоставив все факты, получаем уравнение для неизвестной плотности распределения случайной величины : 159 Eexp(- XC,)= exp(- Xx)p(x)dx =exp(- )?J, (3.2) о ot где P = —. Таким образом, С, является устойчивой случайной величиной с индексом устойчивости Р, причем 0 Р 1. В [138] установлено, что 1-р 4LP)YP ( піч ftP і sinpxV-P sin(l-p)x где а (х,Р)= I smxj sinPx a x и 5 - независимые случайные величины, % распределена равномерно на [0,2л], 5 - экспоненциально с единичным параметром. Таким образом, для случайной величины д/2у справедливо Law\:pLyj=Law\Xx). Отсюда, необходимый для моделирования закон выражается следующей формулой:
LawiA Law aJl v). (3.3) Напомним, что А, - независимы и одинаково распределены, поэтому правая часть (3.3) не зависит от /. Случайные величины А; моделируются с помощью трех независимых случайных величин х, Р V, и случайные і величины Хх = ] Ак, причем Х0 = 0. Алгоритм моделирования автомодельного Леви процесса 1. Задаем входные параметры а, п (число генерируемых значений), Г (интервал моделирования), а (дисперсия случайного процесса). Будем рассчитывать Ак по формуле (3.3). 2. Начало цикла 1 для / = 1,...,п. 160 2.1. Начало цикла 2 для k = \,...i. 2.2. Вызов функции для расчета Ак. 23.S:=S + AkT. 2.4. Конец цикла 2 по к. 3. Конец цикла 1 по і. Функция для расчета Ак Параметры: а, и, а. П 2.Н-І. а 3.(3 = . 2 4.ДА=0. 5-X = i/[o,i] 27C 6. Ь = Хщу 7. v=X (01)(cM.n.2.2.4).
Яримечание 1. Для генерирования равномерной случайной величины на отрезке [0, 1] можно воспользоваться встроенным в программное обеспечение генератором псевдослучайных чисел, генератором Марсалья [221], а также специальные аппаратные платы, устанавливаемые в компьютер, как предложено в [58].
Пр имечание 2. Для получения широкого класса процессов следует в качестве случайной величины V выбирать не только генератор нормального распределения, но и других известных законов распределения, что выполнено автором в программной реализации алгоритма (см., например, рис. 3.1). Подробное объяснение способов генерации случайных величин, соответствующих различным законам распределения приведено, например, в [58,162].
Общие положения имитационного моделирования
Область ИМ является достаточно обширной и проработанной на протяжении нескольких последних десятилетий, за которые накоплен позитивный опыт. Рассмотрим подробнее существенные идеи ИМ как базу построения новых концепций моделирования информационных процессов. Общие принципы имитационного моделирования случайных процессов в информационных системах и сетях, использованные при разработке среды моделирования, изложены автором в [29]. Сети массового обслуживания оказываются подходящим инструментом для имитационного моделирования по нескольким причинам. Во-первых, с помощью элементов графиче ских обозначений СеМО можно визуально отобразить структуру изучаемой системы, что придает имитационной модели свойство наглядности. Во-вторых, СеМО позволяет произвести иерархическую декомпозицию моделируемой системы, причем составные блоки будут унифицированными (то есть содержать определенное число параметров) на всех уровнях декомпозиции. Это свойство позволяет также осуществлять обмен данными между блоками, моделируемыми как отдельные СеМО. В-третьих, расчет параметров узлов СеМО «мгновенно» в реальном времени, а точнее, в модельном времени, позволяет имитировать процессы, происходящие в моделируемой системе при наличии любых произвольных законов распределения входных параметров моделей узлов СеМО.
Рассмотрим конкретные параметры узлов СеМО при их формализации в виде имитационных моделей. Входными параметрами для имитационного блока должны быть, по крайней мере, следующие: - промежуток времени, в течение которого проводится наблюдение (системное время); - таймер модельного времени, позволяющий выполнить имитацию модели либо пошагово, либо блоком итераций; - количество заявок (прибытий, поступлений, запросов в зависимости от физической природы моделируемого объекта), наблюдаемых на входе узла СеМО; - количество завершенных узлом действий, выполняемых по отношению к поступающим заявкам, операций обслуживания. Причем действия могут быть как направленными на обслуживание, так и на игнорирование или частичное обслуживание заявок.
Перечисленные характеристики, за исключением системного времени, которое логично принимать за основу модельного времени имитационной системы, могут задаваться произвольно, а точнее, в соответствии с любым, желаемым для исследователя, законом распределения или стохастическим процессом.
Исходя из этих характеристик, и в соответствии с базовыми положениями теории систем и сетей массового обслуживания можно в первом приближении определять такие характеристики и их размерности, как: - интенсивность поступления заявок, число заявок в единицу времени; - производительность узла СеМО, количество операций обслуживания в единицу времени.
Если узел СеМО имеет один обслуживающий прибор, то он либо может выполнить обслуживание (быть занятым), или же простаивать (быть свободным), тогда исследователь может измерить эту величину (при имитационном моделировании она является случайной) и найти интервал времени занятости узла обслуживания. Далее можно рассчитать коэффициент использования узла СеМО (разделив последний показатель на единицы системного времени). Также можно определить такую характеристику как среднее время, требуемое для обслуживания одной заявки прибором узла СеМО. При моделировании системы в целом требуется «расширить» имитационную модель от единичных заявок на классы и потоки заявок. Например, среди заявок, обслуживаемых вычислительной системой, моделируемой как один узел СеМО, могут быть заявки, относящиеся к классу операций с жестким диском, с выводом на монитор, обращениями к компьютерной сети. Таким образом, при моделировании часто используется допущение о пропорциональности, соблюдении баланса между величинами прибытий заявок в узел СеМО и выполненных действий по их обслуживанию. Заметим, что здесь речь идет не о строгом равенстве, так как в реальных моделируемых системах возможны потери и игнорирование обслуживания заявок при некоторых условиях, а о том, что за некоторое модельное время поступающий поток заявок будет в целом обслуживаться узлом СеМО и передаваться далее, а не игнорироваться или задерживаться.
